Uploaded image for project: 'Scala Programming Language'
  1. Scala Programming Language
  2. SI-5455

Unsound tail recursion optimization on trait lazy val


    • Type: Bug
    • Status: CLOSED
    • Priority: Major
    • Resolution: Fixed
    • Affects Version/s: Scala 2.9.1
    • Fix Version/s: Scala 2.10.0
    • Component/s: Compiler (Misc)
    • Labels:
    • Environment:

      Scala 2.9.1.final


      Consider the `bar` lazy val in the following snippet:

      trait Test {
        def root: Test
        private final lazy val bar: Thing[Double] = {
          if (this eq root) {
            Thing { () =>
          } else {
      case class Thing[A](f: () => A)

      If we look at the bytecode generated for that lazy val, we get the following:

             0: aload_0       
             1: aload_0       
             2: invokeinterface #12,  1           // InterfaceMethod Test.root:()LTest;
             7: if_acmpne     26
            10: new           #14                 // class Thing
            13: dup           
            14: new           #16                 // class Test$$anonfun$Test$$bar$1
            17: dup           
            18: aload_0       
            19: invokespecial #20                 // Method Test$$anonfun$Test$$bar$1."<init>":(LTest;)V
            22: invokespecial #23                 // Method Thing."<init>":(Lscala/Function0;)V
            25: areturn       
            26: aload_0       
            27: invokeinterface #12,  1           // InterfaceMethod Test.root:()LTest;
            32: astore_0      
            33: goto          0

      Specifically, here:

            32: astore_0      
            33: goto          0

      Ah, lovely tail recursion! Unfortunately, this is not a function, and it cannot be optimized in this way! Specifically, the bad case is if the value of `root` has already realized `bar`. In this case, the return result from `this.bar` will be a `Thing` which in turn returns a different value of `identityHashCode` than `root.bar` would have returned. Additionally, this tail recursion means that `root.bar` will not be realized if it hasn't already been, thus a fundamental lazy val semantic is violated.

      This seems to be an extremely tricky bug to actually reproduce. Simply changing the body of the function passed to `Thing` is sufficient to avoid the issue. Specifically:

            Thing { () =>

      With things in this position, the compiler sees bar as a recursive call not in tail position and refuses to perform the optimization (based on the error message I get if I turn bar into a def and use @tailrec). Technically, that assessment of the compiler's is overly-strict, but it happens to be sufficient to avoid the issue in this case.

      Anyway, the solution here is to just not ever do tail recursion on lazy vals unless you can prove that the 0 slot is remaining stable. That criterion would fail this lazy val (rightfully).


          Issue Links



              • Assignee:
                extempore Paul Phillips
                djspiewak Daniel Spiewak
              • Votes:
                0 Vote for this issue
                5 Start watching this issue


                • Created: