Relay-Version: version B 2.10 5/3/83; site utzoo.UUCP
Path: utzoo!mnetor!seismo!rutgers!clyde!cbatt!ihnp4!inuxc!pur-ee!uiucdcs!uiucuxc!uicsrd!harrison
From: harrison@uicsrd.CSRD.UIUC.EDU
Newsgroups: net.lang.lisp
Subject: Re: call/cc and proper tail recursion
Message-ID: <20000019@uicsrd>
Date: Fri, 31-Oct-86 21:08:00 EST
Article-I.D.: uicsrd.20000019
Posted: Fri Oct 31 21:08:00 1986
Date-Received: Tue, 4-Nov-86 03:20:56 EST
References: <20000003@uicsrd>
Lines: 33
Nf-ID: #R:uicsrd:20000003:uicsrd:20000019:000:2043
Nf-From: uicsrd.CSRD.UIUC.EDU!harrison    Oct 31 20:08:00 1986



	I read the reference you suggested, and think I understand how this
works now.  call/cc simply copies the stack into the heap; if a frame
representing a tail-recursive call is 'caught' by a call to call/cc, it will
be copied into the heap before the next call is made.  Barring an invocation
of call/cc (no doubt the perversity in my example is rare), only one frame's
worth of locations are allocated for the bindings of the local vars of the
tail-recursive function.
	This implementation of call/cc surprises me.  To quote from
"The Implementation of PC Scheme", by D. H. Bartley and John C. Jensen, p 88,

	When CALL-WITH-CURRENT-CONTINUATION is invoked, the stack is copied
	into the heap to make a continuation object.  To reduce the worst-case
	cost of this copying and to permit arbitrary growth of the stack,
	a small buffer is used to hold the topmost stack frames.  When
	this buffer overflows, all frames but the currently active one are
	copied into a continuation object in the heap.

It would seem that most stack frames would end up on the heap, especially if
either the buffer is small, or call/cc is used heavily.  Given that, why not
allocate all frames on the heap to start with?  Having done so directly,
call/cc becomes dirt cheap, as a continuation may be represented merely by a
pointer to a 'stack' frame and a code pointer.  Likewise, closure formation
would be dirt cheap, requiring only a code pointer and a lexical parent pointer
(a static link, as they call it in compilers for algol-ish languages).
We would have to garbage collect the entire stack, but if we have to do
(nearly) that anyway, why not make closure formation and call/cc cheap?
(We could still perform tail recursion 'properly', except in the event that a
closure was created which caught a local variable of the tail-recursive
function, such that the closure could out-live the stack frame of that
function, or call/cc was used as per my example.  In those cases, we could make
a normal recursive call instead of a properly tail-recursive one.)