🚀 go-pugleaf

RetroBBS NetNews Server

Inspired by RockSolid Light RIP Retro Guy

Article View: net.lang.lisp
Article #692

call/cc and proper tail recursion

#692
From: harrison
Date: Sat, 11 Oct 1986 16:52
26 lines
1625 bytes
	A question about the definition of Scheme as "properly tail-recursive."

	Consider the following example:

	(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?
	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?
Technical Details
Message-ID: <20000003@uicsrd>
Path: arc1-ca.pugleaf.net!utzoo!watmath!clyde!cbatt!ihnp4!inuxc!pur-ee!uiucdcs!uicsrd!harrison

Show Full Headers
Complete Article Headers
Relay-Version: version B 2.10 5/3/83; site utzoo.UUCP
Path: arc1-ca.pugleaf.net!utzoo!watmath!clyde!cbatt!ihnp4!inuxc!pur-ee!uiucdcs!uicsrd!harrison
From: harrison@uicsrd.CSRD.UIUC.EDU
Newsgroups: net.lang.lisp
Subject: call/cc and proper tail recursion
Message-ID: <20000003@uicsrd>
Date: Sat, 11-Oct-86 12:52:00 EDT
Article-I.D.: uicsrd.20000003
Posted: Sat Oct 11 12:52:00 1986
Date-Received: Tue, 14-Oct-86 05:27:16 EDT
Lines: 26
Nf-ID: #N:uicsrd:20000003:000:1071
Nf-From: uicsrd.CSRD.UIUC.EDU!harrison    Oct 11 11:52:00 1986