. navigate
The Scheme Environment    Page 28 left arrow
right arrow Page 30    The Scheme Environment
The Scheme Environment

LISP Pointers
Volume I, Number 1
April-May 1987

The Scheme Environment
page 29

Prev Article               Start of This Article               Next Article

make tail-recursive procedure calls run faster, they are often said to perform tail-recursion optimization. It would be more accurate to say that compilers that handle tail-recursion improperly perform tail-recursion pessimization.

What I've been saying is inaccurate in one respect. I've been saying that foo should return its result directly to f's caller, not to f. lf f was called tail-recursively, however, then the caller of f doesn't need to touch the result either. The truth is that foo should return its result directly to the last procedure in the call chain that needed to do something useful with the result (as opposed to returning it immediately).

What I've just said is mighty vague, and it's misleading because it makes it sound as though something special has to happen when foo returns; let me try again using the notion of a continuation. All procedures take a hidden extra argument, the continuation. The continuation corresponds roughly to the "control stack" or "dynamic link", but you should think of the continuation as an abstract, active object like a procedure, not as a concrete, passive data structure like a stack frame. Procedures return simply by passing their result(s) to the continuation they were passed, much as though the continuation were a procedure. I can now give a more precise definition of a tail-recursive call: A tail-recursive call is a procedure call in which the calling procedure passes the called procedure a continuation equivalent to the continuation it was passed. The difference between proper and improper implementation of tail-recursion is this: A properly tail-recursive implementation will pass the very same continuation; an improperly tail-recursive implementation effectively passes a copy of the continuation.

In practice, the copy shares nearly all of its structure with the original continuation so improperly tail-recursive implementations are more efficient than the above paragraph makes them sound. I'll return to this in my next article after we've seen continuations in action.

So far I may have left the impression that the main advantage of compiling tail-recursion properly is speed. There's nothing wrong with speed, but it's not the real reason that proper handling of tail-recursion is important. The real reason is portability. Implementations that handle tail-recursion improperly can't run certain perfectly good programs that run fine in properly tail-recursive implementations. That is why all implementations of Scheme are required to handle tail-recursion properly. Before we look at why someone might want to make heavy use of tail-recursion, let's examine a simple program whose only use is to tell whether an implementation handles tail-recursion properly. If it works, the implementation is properly tail-recursive; if it doesn't, it isn't.
    (define (fool x y)
      (if (zero? y)
          (if (zero? x) #t (foo1 (— x 1) 1000))
          (foo2 x (" Y 1))))
    (define (foo2 x y)
      (if (zero? y)
          (if (zero? x) #f (foo2 (- x 1) 1000))
          (foo1 x (- y 1))))
    (foo1 1000 0)
This program essentially counts down from one million before returning true. Two arguments are used instead of one to make it less likely that the program will be slowed by bignum arithmetic. Two procedures are used instead of one because some compilers handle self-tail-recursion, where a procedure calls itself tail-recursively, but do not handle general tail-recursion properly. Sometimes a compiler will handle tail-recursion properly even though a matching interpreter will not, or vice versa. This program will probably run for several CPU minutes if interpreted, and for several seconds if compiled, but on slow machines it may take a minute or more even when compiled or take nearly forever when interpreted. Please don't run this program on a time-shared machine during the busiest part of the day unless you want to get me in trouble.

Page Left left arrow         
right arrow Page Right
Vol. I, No. 1
Table of Contents

Home   Favorites   Computers   Map

IME logo Copyright © 2009, Mary S. Van Deusen