How is tail-recursion optimized in Smalltalk? 
Author Message
 How is tail-recursion optimized in Smalltalk?

I understand what tail-recusion is, and how to use it, but I am curious how
it is optimized in Smalltalk.  When a tail-recursive method ( or a set of
mutually tail-recursive methods ) finishes the base case it can simply
return the result.  In one fell swoop, all of the recursed activation
records can be eliminated from the stack and the result return to the
sending activation record.  

How does it know how far to "peel back" the stack?  It would seem that each
activation record would have to mantain some data and/or link to the tell
it how much the stack has grown, and how far down the sending activation
record is if should have the opportunity to return the result.

Any help would be appreciated.

Sincerely,

Maurice



Wed, 09 Jul 1997 07:29:30 GMT  
 How is tail-recursion optimized in Smalltalk?
As far as I know, none of the standard Smalltalk implementation
perform tail-recursion optimization.  Instead, they have looping
primitives.  In particular, whileTrue: and methods like that
are optimized directly by the compiler, so what you see in
the browser is NOT the same as the code the compiler produces.
The same goes for ifTrue:ifFalse:, but that doesn't involve
tail-recursion.

-Ralph Johnson



Thu, 10 Jul 1997 00:58:55 GMT  
 How is tail-recursion optimized in Smalltalk?

Quote:
> When a tail-recursive method ( or a set of
> mutually tail-recursive methods ) finishes the base case it can simply
> return the result.  In one fell swoop, all of the recursed activation
> records can be eliminated from the stack and the result return to the
> sending activation record.  

That's not the typical way tail-recursion optimization is done.
Usually, instead of making a recursive call, the optimization
causes a jump to be performed instead, so that no new activation
record is corrected.  Then when returning, it just does this
normally.  Ie, recursive calls are converted to jumps instead.
--
Darin Johnson

    "You used to be big."
    "I am big.  It's the pictures that got small."


Thu, 10 Jul 1997 08:13:49 GMT  
 How is tail-recursion optimized in Smalltalk?

Quote:

>I understand what tail-recusion is, and how to use it, but I am curious how
>it is optimized in Smalltalk.

Currently, I don't believe that any Smalltalk implementations do tail-recursion
elimination.

Quote:
>How does it know how far to "peel back" the stack?

Typically, the stack is not peeled back.  When it processes a function
the compiler just determines that no further use of local stack frame
will be necessary after the last function call in the function body.
With that knowledge it can just recycle the current stack frame instead
of building up a new one.  That optimization actually applies to any
sort of function call, not just a recursive one.  In the recursive
case, you can make things even faster by detecting that you don't
even need to rebuild the stack frame.

-Scott



Thu, 10 Jul 1997 09:09:44 GMT  
 How is tail-recursion optimized in Smalltalk?


 > >I understand what tail-recusion is, and how to use it, but I am curious how
 > >it is optimized in Smalltalk.

 > Currently, I don't believe that any Smalltalk implementations do tail-recursion
 > elimination.

 > >How does it know how far to "peel back" the stack?

 > Typically, the stack is not peeled back.  When it processes a function
 > the compiler just determines that no further use of local stack frame
 > will be necessary after the last function call in the function body.
 > With that knowledge it can just recycle the current stack frame instead
 > of building up a new one.  That optimization actually applies to any
 > sort of function call, not just a recursive one.  In the recursive
 > case, you can make things even faster by detecting that you don't
 > even need to rebuild the stack frame.

This can be improved on a little bit, as is done by WAM (Warren Abstract
Machine) based Prolog compilers. The compiler can analyze the sequence of
calls and expressions that make up the body of a procedure. It can then
arrange the stack frame in a way that the locals are ordered such that those
that cease to be used earlier in the procedure are placed first. It is then
possible to trim the stack frame progressively as the execution of the
procedure body takes place, i.e., after the last useage of a local the next
procedure call can clobber its slot on the stack.

 > -Scott

Peter



Sun, 13 Jul 1997 22:56:53 GMT  
 
 [ 5 post ] 

 Relevant Pages 

1. Tail-optimized recursion

2. Tail recursion and complete recursion?

3. Any Smalltalk supporting tail recursion optimization ?

4. Optimizing tail-recursive operations using jumps

5. OO, lexical scope, closure, tail-recursion, continuation

6. Lisp type list, recursion and tail call optimisation

7. Tail recursion ???

8. Tail recursion

9. Thanks for the tail recursion

10. tail recursion analysis

11. tail recursion -- what's a good name

12. Recognising tail recursion

 

 
Powered by phpBB® Forum Software