Subject: Re: OpenScheme 1.3.5 available
From: rpw3@rigden.engr.sgi.com (Rob Warnock)
Date: 27 Nov 2000 02:28:51 GMT
Newsgroups: comp.lang.scheme
Message-ID: <8vsgt3$2f3ti$1@fido.engr.sgi.com>
Guilhem de WAILLY  <gdw@erian-concept.com> wrote:
+---------------
| To be exact, if a function call itself in a tail position, even if some
| internal frame are activated (by some let, for exemple), then the
| tail call is properly replaced by a goto.
| 
| If a function f taill-cals another function g that also tail-calls f,
| that this is not replaced by a goto, because each functions f and
| g create a C function in the produced code, and goto cannot be
| used in this situation. Therefore, in some situation, osm can take
| the decision to replace the body of g into f, and transforms the
| call to f into a goto.
| 
| In conclusion, osm is not fully tail-recursive, but it is in most of the
| situations.
+---------------

O.k., but just so you realize just how *serious* a limitation this is...

Consider the following code, which some consider to be a "natural"
representation for certain kinds of long-running [months or *years*!]
state machines [such as server daemons or operating systems or embedded
controllers]. This is *required* by R5RS to be safe-for-space, but
OpenScheme -- if it behaves as you have described it above -- will
surely break with an "out-of-memory" exception sooner or later:

	(define (start-state)
	  (let ((event (get-next-event)))
	    (cond
	      ((freeble? event)
	       (start-state-freeble-seen event)		; output side-effect
	       (freeble-state))
	      ((quux? event)
	       (start-state-quux-seen event)
	       (quux-state))
	      ((gorp? event)
	       (start-state-gorp-seen event)
	       (gorp-state))
	      ; ... more tests ...
	      (else
	       (report-unexpected-event 'start event)
	       (start-state)))))

	(define (quux-state)
	  (let ((event (get-next-event)))
	    (cond
	      ((quux? event)
	       (quux-state-quux-seen event)
	       (if (quux-minor-distinction? event)
	         (gorp-state)
	         (quux-state)))
	      ((gorp? event)
	       (quux-state-gorp-seen event)
	       (if (quux-major-weirdness? event)
	         (quux-state)
	         (gorp-state)))
	      (else
	       (report-unexpected-event 'quux event)
	       (start-state)))))

	(define (freeble-state)
	  (let ((event (get-next-event)))
	    (cond
	      ((freeble? event)
	       (do-freeble-action event)
	       (freeble-state))		; just keep freebling
	      ((quux? event)
	       (quux-state))		; no action for this transition
	      ((gorp? event)
	       (start-state-gorp-seen event)
	       (gorp-state))
	      (else
	       (freeble-state)))))	; hang here silently

	(define (gorp-state) ...)
	; ... and so on for other possible states ...

Also note that R5RS section "3.5 Proper tail recursion" requires that:

	Certain built-in procedures are also required to perform
	tail calls.  The first argument passed to apply and to
	call-with-current-continuation, and the second argument
	passed to call-with-values, must be called via a tail call.
	Similarly, eval must evaluate its argument as if it were in
	tail position within the eval procedure.

so it's not just "user" procedures that must obey the rules.


-Rob

-----
Rob Warnock, 31-2-510		rpw3@sgi.com
Network Engineering		http://reality.sgi.com/rpw3/
Silicon Graphics, Inc.		Phone: 650-933-1673
1600 Amphitheatre Pkwy.		PP-ASEL-IA
Mountain View, CA  94043