Relay-Version: version B 2.10 5/3/83; site utzoo.UUCP
Path: utzoo!mnetor!seismo!cmcl2!yale!husc6!think!nike!ucbcad!ucbvax!hplabs!tektronix!tekcrl!tekchips!willc
From: willc@tekchips.UUCP (Will Clinger)
Newsgroups: net.lang.lisp
Subject: Re: call/cc and proper tail recursion
Message-ID: <740@tekchips.UUCP>
Date: Wed, 15-Oct-86 19:38:11 EDT
Article-I.D.: tekchips.740
Posted: Wed Oct 15 19:38:11 1986
Date-Received: Thu, 16-Oct-86 22:41:40 EDT
References: <20000003@uicsrd>
Reply-To: willc@tekchips.UUCP (Will Clinger)
Organization: Tektronix, Inc., Beaverton, OR.
Lines: 49

In article <20000003@uicsrd> harrison@uicsrd.CSRD.UIUC.EDU has a question
about the definition of Scheme as "properly tail-recursive":
>
>	(define f (lambda (x y)
>			(if (f x y) (bad-function))
>			(function-with-side-effects x y)
>			(if (p x y) #!null (f (cdr x) (cdr y))) ))
>
>	This function is tail-recursive.  My understanding is that such
>a function is evaluated with no net growth in the stack.  This means,
>in short, that the parameters x and y will be assigned to (cdr x) and
>(cdr y), and the recursive call effected by jumping to the entrance of
>the function.  Is this so?

Almost.  x and y are bound, not assigned; this distinction is important
because assignment would throw away the old values but binding does not.
By the way, I assume you intended for (f x y) in the first line of the
lambda body to be (g x y) to avoid an infinite (non-tail-recursive) loop.

>	If so, then consider what happens when bad-function is defined
>as
>	(lambda () (set! g (call/cc (lambda (x) x))))
>
>i.e., bad-function records the current state, or continuation, in
>the global variable g, and exits.  Now, at the termination of f,
>g will contain some continuation which, if applied, would mean that
>the bindings of x and y would have to be restored  to a state which occured
>during one of the recursive instances of f.  My question is, how can this
>occur if we don't record these values in a stack frame?

It is best to think of Scheme as a heap-based language instead of a
stack-based language.  In other words, pretend that continuations
(analogous to stack frames) are allocated on a heap and reclaimed by
a garbage collector instead of by adjusting a stack pointer.  Pretend
also that the continuation stored in g was created for the sole purpose
of preserving registers across the call to bad-function, and that those
registers are restored immediately upon return from the call.

The tail-recursive call in the last line of the body doesn't need to
preserve registers, so no continuation is created for it.

If you're wondering how this semantics can be implemented efficiently,
you might start by reading the paper on PC Scheme that was presented at
the 1986 ACM conference on Lisp and functional programming.  That paper
tells how the speed of a stack-based implementation can be achieved
by making call-with-current-continuation an expensive procedure to call.

Will Clinger
Tektronix Computer Research Lab