[plt-scheme] guido on tail recursion

Since people are keenly interested in this, I am taking the liberty  
of forwarding excerpts from my conversation with Guy in preparation  
for my ECOOP invited talk.

First message:  Guy basically pointed me to the original paper (Dec  
1975) on Scheme, re-published in HOSC 98 11(4). There it says "The  
interpreter must provide for correctly
   resuming the caller ...  Just before the evaluation of a  
subexpression,
   the state of the current computation ... must be gathered together
   into a single data structure, which we will call a _frame_ ...
   we only build a new frame if further computation would result in
   losing information which might be be necessary.  This only occurs if
   we must somehow return to that state.  This in turn can only occur if
   we must evaluate an expression whose value must be obtained in order
   to continue computation in the current state.

   This implies that no frame need be created in order to _apply_
   a lambda expression to its arguments.  This in turn implies that the
   iterative and continuation-passing styles lead to _no net creation
   of frames_, because they are implemented _only_ in terms of
   explicit lambda applications, whereas the recursive style leads to
   the creation of one net frame per level of recursive depth,
   because the recursive invocation involves the evaluation of
   an expression containing the recursive lambda application as a
   subexpression."

In the same context, he does point back to Actors.

Second/Third message: Gerry, who was CCed replied and Guy confirmed  
like this:

> Gerald Jay Sussman wrote:
>
>> Actually, the tail-recursion idea came from PDP-6 assembly-language
>> programming, where
>>      PUSHJ P,FOO
>>      POPJ P,
>> Could always be replaced by
>>      JRST FOO
>> This was originally shown to me by Stuart Nelson in about 1964.
>> However, the talk on actors reminded us of that in the night we were
>> hacking up the original interpreter.  It simplified the idea
>> considerably.
>>
>
> Ah, so so so!  That now rings a bell.  I must have known that trick
> by 1975 as well, since it was used in quite a number of places in the
> MacLisp interpreter, which by then I knew VERY well.
>
> Thank you, Gerry.
>
> --Guy

I quoted these conversation also during my talk so I suspect it's  
okay to broadcast on a mailing list.

-- Matthias