History of tail-call optimization

David Hopwood david.nospam.hopwood@REDACTED
Tue Aug 22 02:06:41 CEST 2006


Thomas Lindgren wrote:
> "Joe Armstrong (TN/EAB)" <joe.armstrong@REDACTED> wrote:
> 
>>In this case we can omit the code that pushes a return address and
>>jumps into the code and replace it with a simple jump into the code
>>since the function itself will return to the correct place when it
>>executes a RET instruction.  
>>
>>Now I don't know exactly who pointed this out, I might have been Knuth
>>but I am unsure five minutes Googling did not turn up the answer.

>From R5RS:
<http://www.schemers.org/Documents/Standards/R5RS/HTML/r5rs-Z-H-6.html#%_idx_78>

# Proper tail recursion was one of the central ideas in Steele and Sussman's
# original version of Scheme. Their first Scheme interpreter implemented both
# functions and actors. Control flow was expressed using actors, which differed
# from functions in that they passed their results on to another actor instead
# of returning to a caller. In the terminology of this section, each actor
# finished with a tail call to another actor.
#
# Steele and Sussman later observed that in their interpreter the code for
# dealing with actors was identical to that for functions

[... because they only implemented a sequential subset of actors ...]

# and thus there was no need to include both in the language.

The "actors" referred to here are from Carl Hewitt and Henry Baker's
Actors model. In fact their paper "Actors and Continuous Functionals"

<http://www.lcs.mit.edu/publications/pubs/pdf/MIT-LCS-TR-194.pdf>

has an example of a tail-recursive 'factorial' implementation in which they
make the point that only a constant amount of "working store" is needed.
(This is the earliest Actors paper I know of that is on-line, but there were
several others predating 1977.)

The assembly language-level hack of replacing JSR+RET with JMP was probably
known earlier, and special cases of it had been used in the implementation of
Forth interpreters by Charles Moore. However, Steele was certainly responsible
for popularizing it as an automatic optimization for higher-level languages:

> It could be Guy L. Steele, Debunking the "Expensive Procedure Call" Myth,
> AI Memo 443, MIT, 1977. (Subtitled "Lambda: the Ultimate Goto")

<http://repository.readscheme.org/ftp/papers/ai-lab-pubs/AIM-443.pdf>

which is well worth reading. The following paragraph, which I have generalized
slightly, could have been applied to *numerous* programming constructs in the
years since the paper was written:

# In other words, we are now so afraid of [perceived-to-be-expensive construct]
# that, rather than fix our compilers, we wish to teach programmers complex
# techniques for using [lower-level, more error-prone construct] to circumvent
# the shortcomings of our compilers! Such a desire is completely outrageous.
# Not only does it violate the philosophical principles of clarity in language
# design and programming style we have slowly been forced to accept, but it is
# demonstrably ridiculous, because while the complete generality of these
# [optimization] techniques has perhaps not been implemented in a compiler, a
# good part of it has, and has worked for [some time]. Such is the ludicrous
# position we have come to.

-- 
David Hopwood <david.nospam.hopwood@REDACTED>





More information about the erlang-questions mailing list