Tail recursion.

Scott A Crosby crosby at qwes.math.cmu.edu
Thu Jan 31 07:19:54 UTC 2002


On Wed, 30 Jan 2002, Andrew C. Greenberg wrote:

> Not only that -- how, exactly, is this continuation example an example
> of a tail recursion?  Certainly, its been decades since my A-exams, but
> as I recall, a tail recursion is generally defined as a recursive call
> in a tail context.  This is neither.  And while I understand the notion
> of "mutual tail recursions," I'm not sure what optimizations are
> proposed here (or even possible.
>

An explicit continutation passing style is a non-trivial use of tail
recursion. It can be used when implementing proof or other types of
nondeterministic search, and other types of optimization problems.

I'm trying to give examples in my other response.

> How, exactly, can I safely and in straightforward manner optimize this
> for any Class, when the definitions of foo1 and foo2 may well depend
> upon definitions in subclasses, which in turn may change?  Moreover,
> since these kinds of expressions can be horribly complex, I would HATE
> if the debugger lost contexts when showing me the problem.

Actually, its not all that bad to implement. Tail recursion can be done by
replacing your own context with a new one..

IE:

foo
  blah blah
  ^self bar: 12

-- 

What happens is when foo sees the `^bar: 12' at the end, it replaces its
method context with the one for `^bar: 12'. (or, equivalently, it pops its
stack frame. and pushes the new one for ^bar.)

This would require a bytecode called 'tailcall' which does this extra pop
before creating the new frame. I believe that thats it.

The choice of when to replace a normal method call with a tailcall is
a little less certain.

You can always do the substitution if its the last invocation in a
function.

You can also do it in a block passed to a primitive
    ifTrue: [ blah.  ^...]

You have to deal with closure-related issues, but I *believe* you can also
do it in any block passed to any method.
   self foo: [blah. ^...]

This may change the semantics subtlely, in that #cannotReturn messages may
not be sent in places where they once were? (What's the requirement on
those?) If the function tailcalls, and has a block that tailcalls,

Somethign like

foo
  self bar: [^30].
  ^20.

bar: aBlock
  instvar := aBlock

test
  foo
  instvar value + 100

--
Do we get a 'cannotreturn', or '130'? Which are we required to get?

>
> In short, while I appreciate the virtue of recursion -- my observation
> is that TAIL recursion semantically equates to a straightforward
> iteration, I think, by definition.  These other traits, at least with
> the definition I was using, are not precisely tail recursions.

In general, yes.. But at the same level, closures are the exact same as
objects.

[ :method :args |  .... ]

And objects are the same as closures

FooClosure>>do
BarClosure>>do

But, being able to handle both idioms makes the language stronger.

Tailcalls can be considered optional in most cases except for code that
required them to function, where they may run the risk of overflowing
memory. Thus, this is an downward compatible and completely optional
change. It *may* help make the interpreter go faster, if it can reuse
stack space and have a higher cache hit rate.


Scott





More information about the Squeak-dev mailing list