[scala] Tail-Recursive Calls possible inside CPS?

[Kai_Meder]

Hello,

i have already posted my question at SO [1].
This produces a StackOverflowError, any hint how to avoid this?

<code>
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)
    }
  }
}
</code>

[1]
http://stackoverflow.com/questions/2810359/cps-continuations-stackoverflowerror-on-tail-recursive-functions

[Colin Bullock]

If you haven't seen it, you might find this [1] blog entry helpful; it touches on using trampolining with CPS.

- Colin

[1] http://blog.richdougherty.com/2009/04/tail-calls-tailrec-and-trampolines.html

[Tiark Rompf]

Capturing delimited continuations inside a while loop turns the loop basically into a general recursive function. Consider the following code:

var x=0
reset {
  while (x < 5) {
    shift { k:(Unit=>Unit) => println("+"); k(); println("-") }
    x += 1
  }
}

Its output will be:

+
+
+
+
+
-
-
-
-
-

Clearly, this needs stack space. However, all is not lost. In cases that are structured like this:

var x = 0
while (x < 1000000) {
  if (x % 100000 == 0)
    shift { k => println("+"); k(); println("-") }
  x += 1
}

only the 'non-trivial' shift blocks i.e. the then-parts will cause allocation of another stack frame.

Some more details can be found in the appendix of this paper:
http://infoscience.epfl.ch/record/148043/files/DeprecatingObserversTR2010.pdf

Manual trampolining is also an option in some cases.

- Tiark


On May 18, 2010, at 2:31 PM, Kai Meder wrote:

> Hello,
>
> i have already posted my question at SO [1].
> This produces a StackOverflowError, any hint how to avoid this?
>
> <code>
> 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)
>    }
>  }
> }
> </code>
>
> [1]
> http://stackoverflow.com/questions/2810359/cps-continuations-stackoverflowerror-on-tail-recursive-functions