Previous Table of Contents Next


3.4.2. Tail Call Elimination

Because Lisp uses procedure calling (more specifically, recursion) as its main control mechanism, it has historically had a reputation for inefficiency compared to languages that have special iterative notations such as while or for.

As you saw earlier, in the definition of power and its iterative helper procedure, it is possible to express, using recursive procedure calls, the same iteration usually done with a special notation. power-helper invokes itself once for each iteration. If a loop is followed for 100 iterations, does the Scheme version require 100 procedure calls and 100 procedure returns? These operations are relatively expensive.

Luckily, a compiler or an interpreter can analyze a procedure and determine that a particular procedure call is the last thing this procedure must do before returning a value. In that case, the compiler can generate the same looping code that a more conventional compiler generates for a while or for loop, even though the program seems to demand a procedure call. The Scheme standard requires that every conforming implementation must do this tail call elimination. It is unusual for a programming language standard to specify anything about the implementation of the language, as opposed to the meaning of the language’s elements. If an algorithm can be carried out in bounded space (that is, without requiring more memory as the size of the program’s input data grows), then any Scheme implementation uses constant space for a program that represents the algorithm with tail calling.

The idea of tail call elimination did not originate with Scheme; in fact, it was widely used by assembly language programmers in the days before high-level languages. However, Scheme is the first language to include a guarantee of tail call elimination as part of the language specification. Scheme programmers can confidently write tail calls no matter which implementation they use.

The name tail recursion is often used to describe programs that can be run iteratively because tail calling is most important for recursive calls. In fact the compiler or interpreter must eliminate any tail call, whether or not it calls the same procedure in which it appears, in order to handle the case of mutual recursion. (Procedure A tail-calls procedure B, and procedure B tail-calls procedure A.)

3.4.3. First-Class Continuations

Composition of functions implicitly specifies a flow of control. For example, the Scheme expression

   (+ (* 2 3) 4)

implies that the multiplication must be done first and the result of that multiplication passed on to the addition as one of its operands.

An alternative programming style tells each procedure explicitly what to do with its result (this example will seem quite convoluted, compared to the preceding expression, but you’ll soon see how this style can be helpful):

   (define (add a b next)
     (next (+ a b)))

   (define (mult a b next)
     (next (* a b)))

   (mult 2
         3
         (lambda (result1) (add result1
                              4
                              (lambda (result2) result2))))

This code says “Multiply 2 by 3. Add the result to 4. Then return that result as the value of the entire expression.” The argument named next is called a continuation, and this technique is called continuation passing style (CPS).

Now suppose you want to multiply together all the numbers in a list. You could write this in conventional style:

   (define (list-mult nums)
     (if (null? nums)
         1
        (* (car nums) (list-mult (cdr nums)))))

Or you could write this CPS version:

   (define (list-mult nums)
     (define (helper nums next)
       (if (null? nums)
           (next 1)
           (list-mult (cdr nums)
                      (lambda (result) (next (* (car nums) result))))))
     (helper nums (lambda (x) x)))

The advantage of the CPS version becomes clear if you want to optimize the procedure by noticing if one of the numbers in the list is zero and avoiding further multiplication. Here’s how you’d modify the conventional program:

   (define (list-mult nums)
     (if (null? nums)
         1
         (if (= (car nums) 0)
      0
             (* (car nums) (list-mult (cdr nums))))))

If you call this procedure with the list (2 3 4 0 5 6 7), you avoid multiplying by 5, 6, and 7, but you don’t avoid multiplying by 2, 3, and 4. You are already committed to those operations before noticing the 0. Using CPS, you can avoid all the multiplications:

(define (list-mult nums)
     (define (helper nums next)
       (if (null? nums)
           (next 1)
           (if (= (car nums) 0)
               0
               (helper (cdr nums)
                      (lambda (result) (next (* (car nums) result)))))))
     (helper nums (lambda (x) x)))

Ordinarily, the helper procedure calls itself recursively with a continuation that extends the continuation next by one more multiplication. The multiplications are done when the resulting continuation is finally invoked with 1 as its argument. Here is roughly the sequence of events:

   (list-mult ‘(2 3 4))
   (helper ‘(2 3 4) (lambda (x) x))
   (helper ‘(3 4) (lambda (result)
                    ((lambda (x) x) (* 2 result))))
   (helper ‘(4) (lambda (result)
                  ((lambda (result)
                     ((lambda (x) x) (* 2 result)))
                   (* 3 result))))
   (helper ‘() (lambda (result)
                 ((lambda (result)
                    ((lambda (result)
                       ((lambda (x) x) (* 2 result)))
                     (* 3 result)))
                  (* 4 result))))
   ((lambda (result)
      ((lambda (result)
         ((lambda (result)
            ((lambda (x) x) (* 2 result)))
          (* 3 result)))
       (* 4 result)))
    1)
   ((lambda (result)
         ((lambda (result)
            ((lambda (x) x) (* 2 result)))
          (* 3 result)))
       (* 4 1))
   ((lambda (result)
      ((lambda (x) x) (* 2 result)))
    (* 3 (* 4 1)))
   ((lambda (x) x) (* 2 (* 3 (* 4 1))))
   (* 2 (* 3 (* 4 1)))
   (* 2 (* 3 4))
   (* 2 12)
   24


Previous Table of Contents Next