Relay-Version: version B 2.10 5/3/83; site utzoo.UUCP
Path: utzoo!mnetor!seismo!rutgers!clyde!cuae2!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: <20000010@uicsrd>
Date: Tue, 28-Oct-86 12:35:00 EST
Article-I.D.: uicsrd.20000010
Posted: Tue Oct 28 12:35:00 1986
Date-Received: Fri, 31-Oct-86 20:21:36 EST
References: <20000003@uicsrd>
Lines: 45
Nf-ID: #R:uicsrd:20000003:uicsrd:20000010:000:1893
Nf-From: uicsrd.CSRD.UIUC.EDU!harrison    Oct 28 11:35:00 1986


   >/* Written 10:04 am  Oct 26, 1986 by darrelj@sdcrdcf.UUCP
       in uicsrd:net.lang.lisp */
   >Tail recursion results in no stack growth and the efficiency of iteration
   >because by the time the compiler finishes with it, it IS iteration.
   
   ...
   
   >1.  Do as Scheme: use strict lexical binding -- if you can't see a reference
   >to a variable in directly embedded code, there ARE NO REFERENCES to it;
   >there is no such thing as a SPECIAL variable in scheme; thus tail recursion
   >is always safe based on static analysis of a single function.
   
I think that my first example demonstrates that this is not so, given call/cc.
Here is another example, a *bit* less contrived, since it actually does
something!

(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)))

consider the sequence:
   (set! entry-points nil)
   (f 5 0) ==> 15
   
if at this point we evaluate
   ((car entry-points) 3), we get 17;
if instead we evaluate
   ((cadr entry-points) 3), we get 19;
if instead we do
   ((caddr entry-points) 3), we get 21; and so on.

It would not be possible
to achieve this result if we performed the recursive calls of f without
preserving the bindings of x and y.  Notice that there are no side-effects
on anything local to f; all of the trickery is within h, which would (possibly)
be compiled separately.  (We could as easily make h a parameter, or grab it
off of an atom property, whatever.)

I agree that global analysis of the program is the answer; my point is that
the definition of scheme makes it seem as though one can state simply that
tail recursion can be made as efficient as iteration, which simply isn't so
in the presence of call/cc.