Scala: extended syntax of batuming function breaks tail recursion
This is an exercise in Functional Programming in Scala, Chapter 13, to implement a trampoline for interpreting tail recursive functions.
runTrampoline2
is not tail recursive and floods the stack with my test inputs. Also, the annotation tailrec
gives a compiler error for runTrampoline2
. runTrampoline
is tail-recursive and passes compile-time checking annotations.
My best bet is that the difference between these two trampolines is what val
grabs or does not grab a Unit, like here:
scala> val foo = println("abc")
val foo = println("abc")
abc
foo: Unit = ()
scala> foo
foo
scala> val bar: Int = {println("xyz"); 5}
val bar: Int = {println("xyz"); 5}
xyz
bar: Int = 5
scala> bar
bar
res8: Int = 5
Otherwise, these two trampolines look identical to me. I'll include code for Free monad and Suspend, Return and FlatMap in case anyone notices that they are important for this question, but I don't think they are. Is runTrampoline2
tail recursion a broken side effect leaking from val
s? Thank!
@annotation.tailrec
def runTrampoline[A](tra: Free[Function0,A]): A =
tra match {
// case Return(A)
case Return(a1) => a1
// case Suspend(Function0[A])
case Suspend(function0A1) => function0A1()
// case FlatMap(Free[Function0[_],A], A=>Free[Function0,B]]
case FlatMap(free1, aFree2) => free1 match {
// case Return(A)
case Return(a2) => runTrampoline(aFree2(a2))
// case Suspend(Function0[A])
case Suspend(function0A) => runTrampoline(aFree2(function0A()))
// case FlatMap(Free[Function0[_],A], A=>Free[Function0,B]]
case FlatMap(a0,g) =>
runTrampoline {
a0 flatMap { a0 => g(a0) flatMap aFree2 }
}
}
}
//@annotation.tailrec
def runTrampoline2[A](tra: Free[Function0,A]): A =
tra match {
// case Return(A)
case Return(a1) => a1
// case Suspend(Function0[A])
case Suspend(function0A1) => {
val a1: A = function0A1()
a1
}
// case FlatMap(Free[Function0[_],A], A=>Free[Function0,A]]
case FlatMap(free1, aFree2) => free1 match {
// case Return(A)
case Return(a2) => {
val free2: Free[Function0,A] = aFree2(a2)
val a3: A = runTrampoline2(free2)
a3
}
// case Suspend(Function0[A])
case Suspend(function0A) => {
val a2: A = function0A()
val free2: Free[Function0,A] = aFree2(a2)
val a3: A = runTrampoline2(free2)
a3
}
// case FlatMap(Free[Function0[_],A], A=>Free[Function0,B]]
case FlatMap(a0,g) =>
runTrampoline2 {
a0 flatMap { a0 => g(a0) flatMap aFree2 }
}
}
}
I asked a similar question a month ago about type annotations breaking tail recursion: Scala: type annotations make tail recursion check fail
Solved by Aivean. Here is the revised version of the trampoline. Each recursive call is at the very end of the case containing it.
@annotation.tailrec
def runTrampoline3[A](tra: Free[Function0,A]): A =
tra match {
case Return(a1) => a1
case Suspend(function0A1) => {
val a1 = function0A1()
a1
}
case FlatMap(free1, aFree2) => free1 match {
case Return(a2) => {
val free2 = aFree2(a2)
runTrampoline3(free2)
}
case Suspend(function0A) => {
val a2 = function0A()
val free2 = aFree2(a2)
runTrampoline3(free2)
}
case FlatMap(a0,g) =>
runTrampoline3 {
a0 flatMap { a0 => g(a0) flatMap aFree2 }
}
}
}
source to share
It looks like the Scala compiler only recognizes tail recursion when the call itself is the last operation in that function.
I have decompiled two different examples to test this.
Tail recursion:
scala:
def rec:Int = rec
Java:
public final class _$$anon$1 {
private int rec() {
while (true) {}
}
}
No tail recursion:
scala:
def rec:Int = {
val i = rec
i
}
Java:
public final class _$$anon$1 {
private int rec() {
final int i = this.rec();
return i;
}
}
source to share