[scala] Tail recursion question

[Arnaud Bailly]

Hello,
I am a bit puzzled. Sometimes ago, I followed a thread about tail
recursion that stated clearly it was not optimized in all cases in
scala: only self tail recursion is optimized, tail recursion to other
methods is not.

While trying to learn scala for fun and profit, I turned to liftweb,
the nice web framework by David Pollak. I started studying the code
but was startled to see that the ControllerActor trait uses
tail-recursion between methods. I disassembled the thing, and also did
some experiments with simple code fragments and clearly saw tail
recursion was encoded as plain invokestatic/invokeinterface opcodes.

My question is then: is this code doomed to overflow stack or is there
some magic in the JVM or  in scala that circumvents this problem ?
Maybe this is not a problem and I am completely missing some point (or
my version of scala is old...).

Thansk

Arnaud Bailly

[dpp]

Arnaud,

Event based Actors are a special case.  It looks like tail recursion, but it's not.

Here's what happens under the covers:

• a call to "loop" happens
• loop calls 'react'
• if there's a message available for the Actor, the Actor services the message and calls loop
• if there's no message, the Actor throws an exception that causes the scheduler to release the thread (and also unwinds the stack)

The stack depth will only be a problem for event-based actors if they have a mailbox full on messages that are more than the maximum stack depth for the JVM.

So, the compiler does not do tail recursion optimization on these calls (it would be pretty difficult given that lift assembles the partial functions from a bunch of different methods that have nothing to do with 'loop') but in reality, there's no stack depth issue.

Does that address your question?

Thanks,

David

PS -- enjoy lift and I look forward to your feedback and questions!

On 5/8/07, Arnaud Bailly <[hidden email]> wrote:

Hello,
I am a bit puzzled. Sometimes ago, I followed a thread about tail
recursion that stated clearly it was not optimized in all cases in
scala: only self tail recursion is optimized, tail recursion to other
methods is not.

While trying to learn scala for fun and profit, I turned to liftweb,
the nice web framework by David Pollak. I started studying the code
but was startled to see that the ControllerActor trait uses
tail-recursion between methods. I disassembled the thing, and also did
some experiments with simple code fragments and clearly saw tail
recursion was encoded as plain invokestatic/invokeinterface opcodes.

My question is then: is this code doomed to overflow stack or is there
some magic in the JVM or  in scala that circumvents this problem ?
Maybe this is not a problem and I am completely missing some point (or
my version of scala is old...).

Thansk

Arnaud Bailly

--
lift, the fast, powerful, easy web framework
http://liftweb.net

[Philipp Haller-2]

David Pollak wrote:

> Event based Actors are a special case.  It looks like tail recursion,
> but it's not.
>
> Here's what happens under the covers:
>
>     * a call to "loop" happens
>     * loop calls 'react'
>     * if there's a message available for the Actor, the Actor services
>       the message and calls loop
>     * if there's no message, the Actor throws an exception that causes
>       the scheduler to release the thread (and also unwinds the stack)
>
> The stack depth will only be a problem for event-based actors if they
> have a mailbox full on messages that are more than the maximum stack
> depth for the JVM.

Almost. ;-)

In fact, even a full mailbox is not a problem. Reactions (even if
immediately possible because of an already existing message) are always
executed on the empty stack of a worker thread.

Cheers,
   Philipp

>
> So, the compiler does not do tail recursion optimization on these calls
> (it would be pretty difficult given that lift assembles the partial
> functions from a bunch of different methods that have nothing to do with
> 'loop') but in reality, there's no stack depth issue.
>
> Does that address your question?
>
> Thanks,
>
> David
>
> PS -- enjoy lift and I look forward to your feedback and questions!
>
> On 5/8/07, * Arnaud Bailly* <[hidden email]
> <mailto:[hidden email]>> wrote:
>
>     Hello,
>     I am a bit puzzled. Sometimes ago, I followed a thread about tail
>     recursion that stated clearly it was not optimized in all cases in
>     scala: only self tail recursion is optimized, tail recursion to other
>     methods is not.
>
>     While trying to learn scala for fun and profit, I turned to liftweb,
>     the nice web framework by David Pollak. I started studying the code
>     but was startled to see that the ControllerActor trait uses
>     tail-recursion between methods. I disassembled the thing, and also did
>     some experiments with simple code fragments and clearly saw tail
>     recursion was encoded as plain invokestatic/invokeinterface opcodes.
>
>     My question is then: is this code doomed to overflow stack or is there
>     some magic in the JVM or  in scala that circumvents this problem ?
>     Maybe this is not a problem and I am completely missing some point (or
>     my version of scala is old...).
>
>     Thansk
>
>     Arnaud Bailly
>
>
>
>
> --
> lift, the fast, powerful, easy web framework
> http://liftweb.net