tail recursion

Philippe Marschall philippe.marschall at gmail.com
Sun May 13 15:35:50 UTC 2007


13 May 2007 11:52:13 +0200, Lex Spoon <lex at lexspoon.org>:
> 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.

I thought GCC and VC++ do tail-call elimination.

Cheers
Philippe

> 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