Erlang article #1 on programming.reddit.com
Mon Aug 21 14:42:43 CEST 2006
--- "Joe Armstrong (TN/EAB)"
> I'm usure - but I feel that this was known well
> before this,
> in the golden Knuthian days
I think it's reasonable to say that, if so, the
technique was, at the very least, not widely known.
(The related topic of continuations _is_ earlier than
that, though: see John Reynolds' history, for example.
But that was used "in the other direction", for the
mathematical description of imperative control.)
Steele mentions some prior attempts at the similar
sort of recursion-elimination in the "Debunking"
report, but Steele and Sussman can be credited with
popularizing the concept (while inventing Scheme), and
quite possibly with actually getting the
implementation right too. (E.g., your description of
what to do sounds much like Steele's, except he uses
PDP assembly language.)
Clinger's paper on proper tail recursion (PLDI'98) has
as its earliest tail-recursion reference Sussman and
Steele's Scheme report from 1975. That Scheme report
describes, among other things, how recursive programs
can execute in constant space by looking at Lisp-level
examples, but not the low-level implementation.
Steele and Sussman wrote a cluster of papers on Scheme
and its compilation. These papers are, as far as I can
tell, where our understanding of tail-recursion
elimination in programming languages came from.
Do You Yahoo!?
Tired of spam? Yahoo! Mail has the best spam protection around
More information about the erlang-questions