tail recursion

Tony Garnock-Jones tonyg at lshift.net
Mon May 14 15:31:12 UTC 2007


Lex Spoon wrote:
> In Squeak, you should feel free to write recursive routines anyway.

The kinds of routines I have in mind are e.g. state machines and
continuation-passing-style control structures.

MyStateMachine >> startState
  self someCondition
    ifTrue: [^ self nextState]
    ifFalse: [^ self otherState].

MyStateMachine >> nextState
  self otherCondition whileFalse: [^ self nextState].
  ^ self startState.

...

These *will* run out of stack given sufficiently large input, unless the
continuation is aggressively eta-reduced.

> 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!

That's an interesting observation. The "continuation mark" ideas used to
support debuggers etc in the Scheme world seem to indicate that you can
have the best of both worlds: retention of enough meta-level context
(continuation marks) to be useful in a debugger, while not retaining so
much that it affects the object-level (as happens in languages that
don't eta-reduce their continuations).

Regards,
  Tony




More information about the Squeak-dev mailing list