tail recursion

Lex Spoon lex at lexspoon.org
Sun May 13 09:52:13 UTC 2007


Tony Garnock-Jones <tonyg at lshift.net> writes:
> To me it's not a question of optimisation, but a question of not being
> able to express useful patterns of control flow directly. Instead, I am
> forced to encode them, often using otherwise-avoidable mutable state.

In Squeak, you should feel free to write recursive routines anyway.
Since the stack is heap-based, you will not run out of stack unless
you are already running out of memory with your manipulations, anyway.
It is not like in Java or C, where you have the ugly combination of
(a) fixed-size stacks and (b) no tail-call elimination.

You will see many recursive methods if you browse through the
Behavior classes.

Now, curiously, if your recursive method has an error, then the
debugger is not good at codensing long sequences of frames.  This is
curious because of Jecel's comment about not getting caught.  It might
actually be more helpful to the user, in most cases, to dump some
frames with tail-call elimination and thus end up displaying a more
concise debugging view!

-Lex


> > Dan Ingalls said that VM implementors can cheat as long as they don't
> > get caught and if you ever get into the debugger you will certainly
> > notice the lack of some stack frames and will curse whoever had the
> > brilhant idea of eliminating them to get some extra speed. The Self guys
> > were very fanatical about not getting caught this way no matter what the
> > costs in terms of performance.
> > 
> > For tinySelf 1, however, the cost in performance would have been
> > extremely high since having tail send optimization made programs far
> > more parallel than they would be otherwise. Unfortunately this single
> > feature was responsible for practically all the hard to find bugs in the
> > implementation and so when I had to move on to another project they
> > became the reason why tinySelf 1 remained unfinished. Given this
> > experience I think it would have been better for me to first have made
> > the system fully functional without this optimization and then add it in
> > a second version. But I would have added it.
> > 
> > - -Jecel
> > 
> > 




More information about the Squeak-dev mailing list