Doug Quale  <quale1@charter.net> wrote:
+---------------
| David Feuer <David_Feuer@brown.edu> writes:
| > I don't really understand what tail-call optimization (the
| > compilation/interpretation technique) really has to do with Scheme (the
| > language).
| 
| As you suspect, you have to look at the history of Scheme to answer
| this question.  In 1975 Guy Steele and Gerald Sussman were designing
| and writing some experimental lisp interpreters and compilers...
...
| Better yet go to http://library.readscheme.org/page1.html and read all
| of the lambda papers on that page.  Scheme's recorded history goes
| back to 1975.  In 1975 I was still in high school so I didn't see
| these papers until a few years later when I was in college.  Still, to
| someone who was programming in Pascal at the time, "The Art of the
| Interpreter, or the Modularity Complex (Parts Zero, One, and Two)"
| made a tremendous impression on me.  Scheme changed the way that I
| thought about programming and computing forever.
+---------------

In particular, in those very papers it is stated explicitly that
tail-call optimization was what allowed the merger of the ideas
of "actors" and "procedures". [Early Scheme was largely about
experimenting with "actors".] *If* (and only if) procedure calls
in tail position were equivalent to "jump-with-arguments", then
"actors" (stateful objects that were sent messages) and "procedures"
turned out to be *identical* in the implementation of that early
interpreter. At which point, Steele realized he could get rid of
a separate "actor" object type, and just use (TCO-safe) procedures.

+---------------
| Anyone who chooses not to implement TCO is perfectly free to do so.
| The resulting language may look a lot like Scheme, but it won't be Scheme.
| In Scheme, proper implementation of tail recursion is non-negotiable.
+---------------

Exactly so. IMHO.

An example of "actor-like" procedures is a long-running finite-state
machine written as one procedure per state, somewhat in this style:

	(define (stateXXX entry-event)
	  (begin ...do stuff we always do when entering this state,
		    possibly conditioned by "entry-event"...)
	    (let ((x (get-next-event)))
	      (case x
		((this)
		 ...do something [perhaps output?]...
		 (stateYYY x))	; switch to state YYY
		((that)
		 ...do something...
		 (stateZZZ x))	; switch to state ZZZ
		((the other things)
		 ...do something with one of {the,other,things}...
		 (stateWWW x))	; switch to state WWW
		(else
		 ...maybe output, maybe not...
		 (stateXXX x))))) ; loop in state XXX

	(define (stateYYY entry-event) ...whatever...)
	(define (stateZZZ entry-event) ...whatever...)
	(define (stateWWW entry-event) ...whatever...)

You can view the "entry-event" as a "message" "sent" to the next-state
"actor", or as a parameter to a tail-called procedure, your choice.
*Because* Scheme guarantees TCO, the above will not run out of space,
no matter how long the state machine runs [good plan, if the state
machine is, say, an operating system!!].


-Rob

-----
Rob Warnock, 30-3-510		<rpw3@sgi.com>
SGI Network Engineering		<http://www.meer.net/~rpw3/>
1600 Amphitheatre Pkwy.		Phone: 650-933-1673
Mountain View, CA  94043	PP-ASEL-IA