Scala tail-recursive Stream processor function defined in trait holds reference to stream-head

Question

In the following situation

trait T {

 @tailrec
 def consume[A](as: Stream[A]): Unit = {
    if (as.isEmpty) ()
    else consume(as.tail)
  }
 }

object O extends T

calling O.consume(Range(1, N).toStream) with N big enough, the program will run out of memory, or at least will consume O(N) instead of the needed O(1).

See also http://stackoverflow.com/questions/12529697/how-to-write-non-leaking-tail-recursive-stream-function-in-scala — ron, Sep 21 '12 at 11:37

score 12 · Accepted Answer · edited Sep 19 '12 at 01:58

12

The tail-recursive method is generated for the trait. The method entry in the extender of the trait (here O) forwards the call to the method of the trait, but while doing so, it keeps a reference to the head of the Stream.

Thus the method is tail-recursive, but memory still can't be released. Remedy: Don't define Stream functions in traits, just directly in objects.

An alternative is scalaz's EphemeralStream, which holds weak references to the stream head and tail, and recomputes them on demand.

edited Sep 19 '12 at 01:58

mergeconflict

8,156
34
63

answered Sep 18 '12 at 23:57

ron

9,262
4
40
73

[EphemeralStream](https://github.com/scalaz/scalaz/blob/scalaz-seven/core/src/main/scala/scalaz/EphemeralStream.scala) – Tony Morris Sep 19 '12 at 01:54

score 3 · Answer 2 · answered Jul 02 '14 at 03:14

There is a simple workaround. Just wrap your tail recursive stream consumer in another function that receives the stream via a by-name parameter:

import scala.annotation.tailrec

trait T {
  def consume[A](as: => Stream[A]): Unit = {
    @tailrec
    def loop[A](as: Stream[A]): Unit = {
        if (as.isEmpty) ()
       else loop(as.tail)
    }
    loop(as)
  }
}

object O extends T {
  def main(args: Array[String]): Unit = 
    O.consume(Range(1, 1000000000).toStream) 
}

The forwarder method will hold a reference to a function computing an expression the result of which is a stream:

public final class O$ implements T {
  public static final MODULE$;
  // This is the forwarder:
  public <A> void consume(Function0<Stream<A>> as) {
    T.class.consume(this, as);
  }
     .  .  .      

  public void main(String[] args) {
    consume(new AbstractFunction0() {
      public final Stream<Object> apply() {
        return package..MODULE$.Range().apply(1, 1000000000).toStream();
      }
    });
  }
}

Scala tail-recursive Stream processor function defined in trait holds reference to stream-head

2 Answers2

Linked