Subject: Re: OpenScheme 1.3.5 available
From: (Rob Warnock)
Date: 27 Nov 2000 02:28:51 GMT
Newsgroups: comp.lang.scheme
Message-ID: <8vsgt3$2f3ti$>
Guilhem de WAILLY  <> 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)))
	      ((freeble? event)
	       (start-state-freeble-seen event)		; output side-effect
	      ((quux? event)
	       (start-state-quux-seen event)
	      ((gorp? event)
	       (start-state-gorp-seen event)
	      ; ... more tests ...
	       (report-unexpected-event 'start event)

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

	(define (freeble-state)
	  (let ((event (get-next-event)))
	      ((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)
	       (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 Warnock, 31-2-510
Network Engineering
Silicon Graphics, Inc.		Phone: 650-933-1673
1600 Amphitheatre Pkwy.		PP-ASEL-IA
Mountain View, CA  94043