Relay-Version: version B 2.10 5/3/83; site utzoo.UUCP
Path: utzoo!watmath!clyde!rutgers!seismo!rochester!baldwin
From: baldwin@rochester.ARPA (Douglas Baldwin)
Newsgroups: net.lang.lisp
Subject: Re: call/cc and proper tail recursion
Message-ID: <22036@rochester.ARPA>
Date: Fri, 31-Oct-86 12:17:23 EST
Article-I.D.: rocheste.22036
Posted: Fri Oct 31 12:17:23 1986
Date-Received: Sat, 1-Nov-86 03:34:27 EST
References: <20000003@uicsrd> <20000010@uicsrd>
Organization: U of Rochester, CS Dept., Rochester, NY
Lines: 27
Summary: Tail Recursion vs. Closures

In article <20000010@uicsrd>, harrison@uicsrd.CSRD.UIUC.EDU writes:
> 
> (define f (lambda (x y) (if (zero? x) y (f (-1+ x) (+ y (* x (h)))))))
> 
> (define h (lambda () (set! multiplier (call/cc (lambda (x) x)))
>                      (set! entry-points (cons multiplier entry-points))
>                      (if (integer? multiplier) multiplier 1)))

	It seems to me (as a Scheme fan more than implementor) that a lot
of the confusion here has to do with distinguishing tail recursion
optimization from how closures are implemented. In particular, the
continuation accessed by call/cc is (presumably) a closure, i.e., a
procedure and bindings for its local variables. This closure obviously
has to contain bindings for X and Y, but these bindings can be copied
off the stack into the heap at the time the closure is created. Creation
of the closure could happen as late as the time at which call/cc is
invoked (i.e., interpreters and compilers presumably don't keep
continuations as full closures until something like call/cc forces
them to do so). What this means is that tail recursion optimization in
F and closure creation in H are entirely different activities. In
particular, tail recursion can happen with no net stack growth, it's
call/cc that increases heap size in order to save a closure, and the
implementation of closures that has to be smart enough to know that
bindings on the stack may be lost if they aren't copied somewhere.
(I realize that the stack might actually be part of the heap, and that
there are alternatives to copying for saving bindings in closures,
but I think the net effect is as I've described here.)