Re: proper tail-recursion proposal

[Guy Steele - Sun Microsystems Labs <gls@livia.East.Sun.COM>]

   Date: Fri, 9 Jan 1998 10:44:01 -0500
   From: Richard Kelsey <kelsey@research.nj.nec.com>
   ...
   The rationale was not meant to explain why we don't switch back to
   primitive iteration constructs now, but to explain why the original
   designers didn't choose them in the first place (I'm guessing of
   course; they might have gone with proper tail recursion simply
   because it is a clever idea).

Well, my memory is (and therefore you should take it with a grain of salt):

Gerry and I wanted to understand actors.  After reading Carl Hewitt's papers
and talking it over with Carl, we still didn't understand what it would
"feel" like to write programs using actors.  So we set out to build a
minimal actor language that would suffice for coding up some of the
examples, so we could get some experience.

We both knew Lisp, of course, and we were familar with the FUNARG problem.
We also both knew how to code simple interpreters in Lisp, so that seemed
to be the fastest implementation path to our goal.

We knew ordinary (that is, dynamic) Lisp variable bindings would not
behave properly for naming the "acquaintances" of an actor.  Gerry had
been teaching about Algol 60, and he suggested that our interpreter
should use Algol-style lexical scoping, which would presumably support
acquaintances properly.

We then coded a simple interpreter with constants, variables,
a few primitive functions and/or actors, a conditional (IF),
functions (lambda expressions), actors (alpha expressions),
function calls, and message sends.  That way we could mix
actor and functional programming.  (This was in the spirit of
a line of "AI programming languages" that had been constructed
in that laboratory using the strategy of starting with an interpreter,
coded in Lisp, for a Lisp-like language, then adding desired
extra constructs.  In fact, Scheme was originally called Schemer,
because we expected it to be another AI language, following in the
footsteps of Planner and Conniver.)

As an example, the actor expression corresponding to

	(lambda (a b) (+ a b))

would be

	(alpha (a b k) (k (+ a b)))

and, if its value were named "z", it would be called with an expression
such as

	(send z 3 5 (alpha (v) ...))

As long as we were using lexical scoping for the actors, we decided
to use it for the functions as well (to make it more like Algol).  And
that way we needed only one environment mechanism.  So the value of
a lambda expression was a closure over a lexical enviroment, and the
value of an alpha expression was an actor.

This worked just fine, and we wrote some small programs using actors.

It was only later, examining the code of the interpreter, that we realized
that the *implementations* of lambda expressions and of alpha expressions
were IDENTICAL, and that the implementations of function call and message
send were IDENTICAL.  We didn't notice that at first, as we were writing
the code, because we so strongly had the mind-set that "functions return
values and actors don't return".

Once we made this empirical discovery, we realized that, with lexical
scoping, closures were the same as actors (except---pace Carl---for
certain special-purpose primitive actors called cells and synchronizers).
At that point we removed alpha and send from the language, before publishing
the first report, because they were demonstrably redundant.

Of course, part of the point of actor theory was to explain all kinds of
patterns of control, including iteration, using a single mechanism, the
sending of messages among actors.  We didn't have primitive iteration
constructs in Scheme precisely because we intended to code such constructs
as macros in terms of actors, using models such as Carl's.  To be able
to do so was the entire original point of the exercise.  Once the
equivalance of actors and closures dawned on us, we naturally coded
iterations constructs as macros in terms of closures of lambda expressions.
And there you are.

That's my memory, anyway.

--Guy