Scala Stream Tail Evaluation

There was an unanswered question from our discussion of Scala Laziness last night: Why do we need all that code for managing the evaluation of the tail of a Stream?

package scala.collection.immutable

 
object Stream {

  ... 

  final class Cons[+A](hd: A, tl: => Stream[A]) 

      extends Stream[A] { 

    override def isEmpty = false 

    override def head = hd 

    @volatile private[this] var tlVal: Stream[A] = _ 

    def tailDefined: Boolean = tlVal ne null

    override def tail: Stream[A] = {

      if (!tailDefined)

        synchronized {

          if (!tailDefined) tlVal = tl

        }

      tlVal

    }

  }

}

It seemed like passing the tail parameter using call-by-name might be sufficient. Here’s my first attempt at trying that out:

abstract class MyStream1[+A] {

  def isEmpty: Boolean

  def head: A

  def tail: MyStream1[A]

}

object MyStream1 {

  object Empty extends MyStream1[Nothing] {

    override def isEmpty = true

    override def head = { throw new Exception("Bad!") }

    override def tail = { throw new Exception("Bad!") }

  }

  class Cons[A](head: A, tail: => MyStream1[A])
      extends MyStream1[A] {

    override def isEmpty = false

  }

}

Uh-oh, the compiler isn’t happy with this definition of Cons:

class Cons needs to be abstract, since:
method tail in class MyStream1 of type => MyStream1[A] is not defined
method head in class MyStream1 of type => A is not defined

This Cons doesn’t implement head and tail as specified in the parent class. It looks like putting them in the constructor argument list isn’t enough. So let’s try this:

abstract class MyStream2[+A] {

  def isEmpty: Boolean

  def head: A

  def tail: MyStream2[A]

}

object MyStream2 {

  object Empty extends MyStream2[Nothing] {

    override def isEmpty = true

    override def head = { throw new Exception("Bad!") }

    override def tail = { throw new Exception("Bad!") }

  }

  class Cons[A](hd: A, tl: => MyStream2[A])
      extends MyStream2[A] {

    override def isEmpty = false

    override val head = hd

    override lazy val tail = tl

  }

}

OK, that compiles. Let’s try running this:

object Foo2 {

  def from(n: Int): MyStream2[Int] = {

    println("from(" + n + ")")

    new MyStream2.Cons(n, from(n + 1))

  }

  def main(args: Array[String]) {

    val ints = from(0)

    println(ints.head)

    println(ints.tail.head)

    println(ints.tail.tail.head)

    println(ints.head)

    println(ints.tail.head)

    println(ints.tail.tail.head)

  }

}

Here’s what we get:

from(0)

0

from(1)

1

from(2)

2

0

1

2

Cool, that seems to work. We see the side effect of the node evaluation the first time we visit each node, but not afterwards.

So we need the tail passed as call-by-name to delay its evaluation, and we need to override head and tail to match the definition of the abstract parent class. I used lazy val for the tail, so that it isn’t evaluated right away when the node is constructed. Try changing that to just val:

...

from(1538)

from(1539)

from(1540)

Exception in thread "main" java.lang.StackOverflowError

Oops! Now as soon as you create a node, the tail is evaluated, and its tail is evaluated, and its tail…

So why doesn’t the Stream implementation in the Scala standard library use lazy val for the tail? I suspect it’s an optimization because I don’t think lazy val would have any threading issues. Or it could be that the tailDefined attribute is useful elsewhere in the class.