why scala doesn't make tail call optimization?

Question

Just playing with continuations. The goal is to create function which will receive another function as parameter, and execution amount - and return function which will apply parameter given amount times.

The implementation looks pretty obvious

def n_times[T](func:T=>T,count:Int):T=>T = {
  @tailrec
  def n_times_cont(cnt:Int, continuation:T=>T):T=>T= cnt match {
        case _ if cnt < 1 => throw new IllegalArgumentException(s"count was wrong $count")
        case 1 => continuation
        case _ => n_times_cont(cnt-1,i=>continuation(func(i)))
      }
  n_times_cont(count, func)
}

def inc (x:Int) = x+1

    val res1 = n_times(inc,1000)(1)  // Works OK, returns 1001

val res = n_times(inc,10000000)(1) // FAILS

But there is no problem - this code fails with StackOverflow error. Why there is no tail-call optimization here?

I'm running it in Eclipse using Scala plugin, and it returns Exception in thread "main" java.lang.StackOverflowError at scala.runtime.BoxesRunTime.boxToInteger(Unknown Source) at Task_Mult$$anonfun$1.apply(Task_Mult.scala:25) at Task_Mult$$anonfun$n_times_cont$1$1.apply(Task_Mult.scala:18)

p.s.

F# code, which is almost direct translation, is working without any issues

let n_times_cnt func count = 
    let rec n_times_impl count' continuation = 
        match count' with
        | _ when count'<1 -> failwith "wrong count"
        | 1 -> continuation
        | _ -> n_times_impl (count'-1) (func >> continuation) 
    n_times_impl count func

let inc x = x+1
let res = (n_times_cnt inc 10000000) 1

printfn "%o" res

possible duplicate of [Does the JVM prevent tail call optimizations?](http://stackoverflow.com/questions/105834/does-the-jvm-prevent-tail-call-optimizations) — n. m. could be an AI, May 14 '13 at 09:29

score 5 · Accepted Answer · answered Jul 04 '13 at 03:57

The Scala standard library has an implementation of trampolines in scala.util.control.TailCalls. So revisiting your implementation... When you build up the nested calls with continuation(func(t)), those are tail calls, just not optimized by the compiler. So, let's build up a T => TailRec[T], where the stack frames will be replaced with objects in the heap. Then return a function that will take the argument and pass it to that trampolined function:

import util.control.TailCalls._
def n_times_trampolined[T](func: T => T, count: Int): T => T = {
  @annotation.tailrec
  def n_times_cont(cnt: Int, continuation: T => TailRec[T]): T => TailRec[T] = cnt match {
    case _ if cnt < 1 => throw new IllegalArgumentException(s"count was wrong $count")
    case 1 => continuation
    case _ => n_times_cont(cnt - 1, t => tailcall(continuation(func(t))))
  }
  val lifted : T => TailRec[T] = t => done(func(t))
  t => n_times_cont(count, lifted)(t).result
}

pagoda_5b · Answer 2 · 2013-05-15T08:39:34.597

1

I could be wrong here but I suspect that the n_times_cont inner function is properly converted to use tail recursion; the culprit's not there.

The stack is blown up by the collected continuation closures (i.e. the i=>continuation(func(i))) which make 10000000 nested calls to your inc method, once you apply the result of the main function.

in fact you can try

scala> val rs = n_times(inc, 1000000)
rs: Int => Int = <function1> //<- we're happy here

scala> rs(1) //<- this blows up the stack!

As an aside, you can rewrite

i=>continuation(func(i))

as

continuation compose func

for the sake of greater readability

edited May 15 '13 at 08:39

answered May 14 '13 at 10:24

pagoda_5b

7,333
1
27
40

As I understand the whole idea of CPS is this collection of closures. But it looks like Scala just cannot make such construct working. http://stackoverflow.com/questions/8549433/is-it-possible-to-use-continuations-to-make-foldright-tail-recursive?rq=1 p.s. Thanks for compose trick, I didn't know about that – AndyG May 14 '13 at 14:35
1

Yeah, you want that `i => ...` lambda to make a tail call to `continuation`, which `@tailrec` isn't going to do for you and nor is anything else in Scala land. You can build your own trampoline, I guess :) – Mysterious Dan May 14 '13 at 17:50
1

@MyseriousDan, well, "anything else in Scala land" may be a strong statement. The standard library has `util.control.TailCalls`... – huynhjl Jul 04 '13 at 03:58
@huynhjl hah, that's more or less what I meant by build your own trampoline :) – Mysterious Dan Jul 04 '13 at 14:57

why scala doesn't make tail call optimization?

2 Answers2

Linked