Relay-Version: version B 2.10 5/3/83; site utzoo.UUCP
Path: utzoo!mnetor!seismo!rutgers!sri-spam!sri-unix!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: <785@tekchips.UUCP>
Date: Mon, 27-Oct-86 17:54:22 EST
Article-I.D.: tekchips.785
Posted: Mon Oct 27 17:54:22 1986
Date-Received: Tue, 28-Oct-86 19:09:47 EST
References: <20000003@uicsrd> <20000008@uicsrd>
Reply-To: willc@tekchips.UUCP (Will Clinger)
Organization: Tektronix, Inc., Beaverton, OR.
Lines: 34

In article <20000008@uicsrd> harrison@uicsrd.CSRD.UIUC.EDU writes:
>It seems to me that if tail recursion incurs a penalty of space proportional
>to the number of calls, plus time to garbage collect the space, then it is
>significantly more expensive than iteration.

Tail recursion in Scheme doesn't incur any space penalty at all.  I can't
speak for all implementations of Scheme (because many pure interpreters do
indeed create garbage as part of the interpretation process) but I know that
if you say something like

        ((rec loop (lambda () (loop))))

in PC Scheme or MacScheme or compiled T3 you will get a tight infinite
tail-recursive loop in which no storage is allocated and the garbage
collector never runs.  (Not all infinite loops have this property, of
course; for example ((rec loop (lambda (n) (loop (1+ n)))) 0) will
eventually allocate storage for bignums.)

>                                              I have always assumed that the
>'stack' in Scheme is actually maintained as a heap; my confusion came in
>reading the claim above (and in several other presentations of Scheme) that
>tail-recursive calls occur with no net growth in the stack.  What this seems
>to mean in reality is merely that unwinding from a series of tail recursive
>calls takes constant time (if we ignore the expense of garbage collecting
>all the stack frames allocated).

No, it means that tail-recursion is as efficient as iteration in both
time and space.  That's not to say that any particular compiler will
generate exactly the same code for a do loop that it does for an equivalent
tail recursion, but if there's a significant difference in performance then
something's wrong with the compiler.

Peace, William Clinger
Tektronix Computer Research Lab