CPS / Continuations StackOverflowError on (tail-) recursive functions

Question

Is there a way to have a tail recursive function inside CPS without throwing StackOverflow?

import scala.util.continuations._ object CPSStackOverflow { def main(args: Array[String]) = { reset { def recurse(i: Int): Unit @suspendable = { println(i) shift { k: (Unit => Unit) => k( () ) // just continue } recurse(i + 1) } recurse(1) } } } 

results in the following StackOverflowError:

 1298 1299 1300 Exception in thread "main" java.lang.StackOverflowError at java.nio.CharBuffer.wrap(CharBuffer.java:350) at sun.nio.cs.StreamEncoder.implWrite(StreamEncoder.java:246) at sun.nio.cs.StreamEncoder.write(StreamEncoder.java:106) at java.io.OutputStreamWriter.write(OutputStreamWriter.java:190) at java.io.BufferedWriter.flushBuffer(BufferedWriter.java:111) at java.io.PrintStream.write(PrintStream.java:476) at java.io.PrintStream.print(PrintStream.java:619) at java.io.PrintStream.println(PrintStream.java:773) at scala.Console$.println(Console.scala:198) at scala.Predef$.println(Predef.scala:182) at test.CPSStackOverflow$$anonfun$main$1.recurse$1(CPSStackOverflow.scala:9) at test.CPSStackOverflow$$anonfun$main$1$$anonfun$recurse$1$2.apply(CPSStackOverflow.scala:13) at test.CPSStackOverflow$$anonfun$main$1$$anonfun$recurse$1$2.apply(CPSStackOverflow.scala:10) at scala.util.continuations.ControlContext$$anonfun$flatMap$2$$anonfun$apply$2.apply(ControlContext.scala:71) at test.CPSStackOverflow$$anonfun$main$1$$anonfun$recurse$1$1.apply(CPSStackOverflow.scala:11) at test.CPSStackOverflow$$anonfun$main$1$$anonfun$recurse$1$1.apply(CPSStackOverflow.scala:10) at scala.util.continuations.package$$anonfun$shiftR$1.apply(package.scala:58) at scala.util.continuations.package$$anonfun$shiftR$1.apply(package.scala:58) at scala.util.continuations.ControlContext$$anonfun$flatMap$2.apply(ControlContext.scala:68) at scala.util.continuations.ControlContext$$anonfun$flatMap$2.apply(ControlContext.scala:67) at scala.util.continuations.ControlContext$$anonfun$flatMap$2$$anonfun$apply$2.apply(ControlContext.scala:73) at test.CPSStackOverflow$$anonfun$main$1$$anonfun$recurse$1$1.apply(CPSStackOverflow.scala:11) at test.CPSStackOverflow$$anonfun$main$1$$anonfun$recurse$1$1.apply(CPSStackOverflow.scala:10) at scala.util.continuations.package$$anonfun$shiftR$1.apply(package.scala:58) at scala.util.continuations.package$$anonfun$shiftR$1.apply(package.scala:58) etc... 

Any way around this error? trampoline? stack-unwinding, throwing exceptions? Thanks!

Answer 1

You call another function inside the continuation. Scala does not support the cross tail recursion method because the JVM does not.

Answer 2

You can run Java with -Xss2M , however this error can only happen after a thousand iterations later. As long as your method is not recursive, you cannot get around this problem.