Tail recursion 
Author Message
 Tail recursion

Do any brands of Smalltalk optimize tail recursion?
If not, is that a big advantage of Lisp over Smalltalk?


Wed, 18 Jun 1902 08:00:00 GMT  
 Tail recursion
Smalltalk MT (http://www.objectconnect.com) optimizes tail recursion.

Tarik Kerroum
Object Connect, Sarl


Quote:
> Do any brands of Smalltalk optimize tail recursion?
> If not, is that a big advantage of Lisp over Smalltalk?



Wed, 18 Jun 1902 08:00:00 GMT  
 Tail recursion

Quote:

> Do any brands of Smalltalk optimize tail recursion?
> If not, is that a big advantage of Lisp over Smalltalk?

Arguably most Smalltalks optimize tail recursion for whileTrue:, whileFalse:
whileTrue and whileFalse, since these are in-lined :)  The compiler
generates loop code using jump bytecodes.  e.g. in VisualWorks the following

        | i |
        i := 0.
        [i < 1] whileTrue:
            [thisContext method symbolic inspect.
             i := i + 1]

opens an inspector on the following string:

        normal AnnotatedMethod numArgs=0 numTemps=1 frameSize=12

        literals: (#method #symbolic #inspect )

        1 <49> push 0
        2 <4C> store local 0; pop
        3 <67> loop head
        4 <10> push local 0
        5 <4A> push 1
        6 <A2> send <
        7 <E8 09> jump false 18
        9 <54> push context
        10 <70> send method
        11 <71> send symbolic
        12 <72> send inspect
        13 <56> pop; push local 0
        14 <C8> push 1; send +
        15 <4C> store local 0; pop
        16 <E3 F1> jump 3
        18 <62> push nil; return

The problem with tail-recursion optimization for Smalltalk is debugging.
Traditional Smalltalk environments provide full debugability at all times.
Unwinding tail-recursion into a proper recursive stack is not possible in
general.  Hence tail-recursion conflicts with providing full debugability.

In practice this is not a performance limitation since Smalltalk has lots of
non-recursive iteration forms.  In languages with a strong functional
heritage (like Lisp & Scheme), where iteration is typically written as
recursive function application, tail-recursion optimization is essential for
iteration performance comparable with imperative languages.  But in
imperative OO languages like Smalltalk recursion typically isn't used to
implement iteration and hence tail-recursion optimization is typically not a
significant contibutor to high performance.

_______________,,,^..^,,,____________________________
Eliot Miranda              Smalltalk - Scene not herd



Wed, 18 Jun 1902 08:00:00 GMT  
 Tail recursion


Quote:

> > Do any brands of Smalltalk optimize tail recursion?
> > If not, is that a big advantage of Lisp over Smalltalk?

> Arguably most Smalltalks optimize tail recursion for whileTrue:,
whileFalse:
> whileTrue and whileFalse, since these are in-lined :)  The compiler
> generates loop code using jump bytecodes.  e.g. in VisualWorks the

following
[snip]

Quote:
> The problem with tail-recursion optimization for Smalltalk is
debugging.
> Traditional Smalltalk environments provide full debugability at all
times.
> Unwinding tail-recursion into a proper recursive stack is not possible
in
> general.  Hence tail-recursion conflicts with providing full
debugability.

> In practice this is not a performance limitation since Smalltalk has
lots of
> non-recursive iteration forms.  In languages with a strong functional
> heritage (like Lisp & Scheme), where iteration is typically written as
> recursive function application, tail-recursion optimization is
essential for
> iteration performance comparable with imperative languages.  But in
> imperative OO languages like Smalltalk recursion typically isn't used
to
> implement iteration and hence tail-recursion optimization is typically
not a
> significant contibutor to high performance.

I encountered this design decision in the implementation of Avail
( http://www.*-*-*.com/ ), and chose to leave it
to the optimizer layer to decide whether to perform tail recursion
elimination or not.  Most of the time it won't matter (same reason as
for Smalltalk), but if you're using a lot of higher order functions,
it's nice to have reason to believe the compiler/runtime can avoid
creating all those simultaneous stack frames.

I haven't actually implemented tail recursion elimination in the
optimizer yet, but it's possible in theory.  The problem is maintaining
exact debugging information at all times.  The answer lies in the code
generation technique in the back end of the optimizer (I believe).  When
translating a method, doing inlining etc., the initial flow graph is an
ordinary splice of the caller and callee flow graphs.  Any time a
nybblecode (the "visible" layer, like Smalltalk bytecodes) could lead to
a debugging situation, no matter how unlikely, there must be "offramp"
code inserted to create fully reified stack frames (and anything else
that was optimized away that a de{*filter*} would need to see).  Since the
reified stack frames in Avail are really immutable continuations (a la
Scheme), I don't have to worry about preserving their identity, so I can
build them as needed, instead of when the methods are invoked.  Note
that this "offramp" code is only executed if a thread is about to be
suspended (for debugging or other meta-operations).

One thing this allows is partial loop unrolling.  If a loop is
implemented recursively (such as the *actual text* of the whileTrue
methods in VisualWorks), one recursive invocation of it might be
inlined, which has the effect of unrolling by a factor of two.

Getting back to tail recursion elimination:  I can imagine a
transformation on a subset of possible recursive methods (or blocks)
that allows a rewriting as a loop.  The offramp code would have to know
how to build up to N separate stack frames (in the event that a de{*filter*}
or other metaoperation actually needed to examine the stack), but this
would be no more expensive than constructing them on every call, the way
Smalltalk does.  The applicable cases would be restricted to those that
require a fixed amount of information for the whole loop (like #do:),
excluding those that accumulate information on each iteration (like
#collect:).  I'll leave the implementation of this optimization as an
exercise for the reader, as Avail will eventually allow user-written
optimization rules to be added (only with formally verifiable proofs, of
course).

If you can think of a more precise precondition than the wishy-washy
"fixed a

Sent via Deja.com http://www.*-*-*.com/
Before you buy.



Wed, 18 Jun 1902 08:00:00 GMT  
 
 [ 4 post ] 

 Relevant Pages 

1. Tail recursion and complete recursion?

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

3. Tail recursion ???

4. Thanks for the tail recursion

5. How is tail-recursion optimized in Smalltalk?

6. Any Smalltalk supporting tail recursion optimization ?

7. tail recursion analysis

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

9. Recognising tail recursion

10. Tail recursion

11. eliminating tail recursion in a recursive-descent evaluator?

12. Has UCB Logo tail recursion optimization?

 

 
Powered by phpBB® Forum Software