tail recursion (was: Equality of Recursive Structures)

Jecel Assumpcao Jr jecel at merlintec.com
Fri May 11 20:40:14 UTC 2007


Tony Garnock-Jones wrote:
> sig wrote:
> > But then, what to deal with such cases:
> > 
> > aClass>>add: a with: b
> > ^ self add: a with: b+1
> 
> This is a call in tail position, and it's a crying shame that the Squeak
> VM doesn't presently allow the associated degenerate stack frames to be
> elided.

Lukas Renggli gave a series of examples where replacing the "tail send"
with a "goto" would give use the wrong semantics. That, however, is a
separate issue from avoiding the creation of stack frames.

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