CPS and StackOverflowError

On Tue, Feb 24, 2009 at 12:57 PM, Max Katsev wrote:
> I'm trying to implement foldr using CPS to make it tail-recursive.
> Can anyone explain me why the following code results in StackOverflowError?
>
> def FoldRightC[a,b](combine : (a, b) => b, l : List[a], acc : b) : b = {
>  def Helper(l: List[a], cont: b => b) : b = l match {
>    case h :: t => Helper(t, racc => cont(combine(h, racc)))
>    case List() => cont(acc)
>  }
>  Helper(l, identity)
> }
> println(FoldRightC((x:Int,y:Int)=>x+y, List.range(1,100000), 0))

Hi Max

Have you done some analysis about which lines seem to repeat in the stack trace?

Cheers
Rich

--
http://www.richdougherty.com/

Max Katsev schrieb:
> case List() => cont(acc)

Here you are calling a function that calls another function that again
calls a different function and so on for 100000 functions. This uses
100000 stack frames. Due to limitations of the JVM and perfomance
considerations, scala can only eliminate direct tail recursion (i.e. calls
to the same function).

- Florian.

So, you are basically saying that there is no way to get rid of recursion here?

2009/2/24 Florian Hars :
> Max Katsev schrieb:
>>     case List() => cont(acc)
>
> Here you are calling a function that calls another function that again
> calls a different function and so on for 100000 functions. This uses
> 100000 stack frames. Due to limitations of the JVM and perfomance
> considerations, scala can only eliminate direct tail recursion (i.e. calls
> to the same function).
>
> - Florian.
>

On Tue, Feb 24, 2009 at 9:52 AM, Max Katsev <mkatsev@gmail.com> wrote:

So, you are basically saying that there is no way to get rid of recursion here?

The Programming in Scala  book states:

"You also won't get a tail-call optimization if the final call goes to a function value"

I think this may be the issue. If you take out the 'cont(combine(...))' it works.

Check this:

    def FoldRightC[a,b](combine : (a, b) => b, l : List[a], acc : b) : b = {
      def Helper(l: List[a], cont: b => b) : b = l match {
        case List() =>
          println("I hit the bottom")
          cont(acc)
        case h::t =>
          Helper(t, racc => cont(combine(h, racc)) )
      }
      Helper(l, identity)
    }
Yields:

I hit the bottom
Exception in thread "main" java.lang.StackOverflowError

So the tail-call optimization is happening, the cont(combine(..)) is the one that is recursive.

2009/2/24 Florian Hars <hars@bik-gmbh.de>:
> Max Katsev schrieb:
>>     case List() => cont(acc)
>
> Here you are calling a function that calls another function that again
> calls a different function and so on for 100000 functions. This uses
> 100000 stack frames. Due to limitations of the JVM and perfomance
> considerations, scala can only eliminate direct tail recursion (i.e. calls
> to the same function).
>
> - Florian.
>

Will this be fixed when/if tail-call support[1] is added to the VM?

-Arthur

[1]  http://openjdk.java.net/projects/mlvm/subprojects.html#TailCalls


On Thu, Feb 26, 2009 at 9:36 AM, Thomas Sant Ana <mailleux@gmail.com> wrote:

On Tue, Feb 24, 2009 at 9:52 AM, Max Katsev <mkatsev@gmail.com> wrote:

So, you are basically saying that there is no way to get rid of recursion here?

The Programming in Scala  book states:

"You also won't get a tail-call optimization if the final call goes to a function value"

I think this may be the issue. If you take out the 'cont(combine(...))' it works.

Check this:

    def FoldRightC[a,b](combine : (a, b) => b, l : List[a], acc : b) : b = {
      def Helper(l: List[a], cont: b => b) : b = l match {
        case List() =>
          println("I hit the bottom")
          cont(acc)
        case h::t =>
          Helper(t, racc => cont(combine(h, racc)) )
      }
      Helper(l, identity)
    }
Yields:

I hit the bottom
Exception in thread "main" java.lang.StackOverflowError

So the tail-call optimization is happening, the cont(combine(..)) is the one that is recursive.

2009/2/24 Florian Hars <hars@bik-gmbh.de>:
> Max Katsev schrieb:
>>     case List() => cont(acc)
>
> Here you are calling a function that calls another function that again
> calls a different function and so on for 100000 functions. This uses
> 100000 stack frames. Due to limitations of the JVM and perfomance
> considerations, scala can only eliminate direct tail recursion (i.e. calls
> to the same function).
>
> - Florian.
>

On Thu, Feb 26, 2009 at 4:28 PM, Arthur Peters wrote:
> Will this be fixed when/if tail-call support[1] is added to the VM?
>
Yes, we definitely plan this. Once tailcalls are in
a mainstream JVM we'll support them.

Cheers