CL and Tail-Call Elimination
Sunday, June 13, 2004
There has been a thread on c.l.l. discussing the lack of tail-call elimination in Common Lisp. Basically, tail-call elimination is a technique that allows the language implementation to release memory more efficiently for certain types of calls - here's a wiki definition:
"If the last thing a routine does before it returns is call another routine, rather than doing a jump-and-add-stack-frame immediately followed by a pop-stack-frame-and-return-to-caller, it should be safe to simply jump to the start of the second routine, letting it re-use the first routine's stack frame (environment)."Scheme provides for "Proper tail recursion" as part of the Scheme R5RS language definition. CL, on the other hand, does not mandate that tail-call elimination be provided by the language implementation. In practice, most CL's provide some mechanism for the programmer to tell the CL compiler to use tail-call elimination, but it is not a requirement of the ANSI CL standard.
Ok, so let's see an example so we understand what we're talking about. In Scheme, if we want to count down from a user-defined number to zero using a display function and a decrementing function, we might code something like this:
(define (f1 n)
(display n)
(display "\n")
(if (= n 0)
(display "Blastoff!")
(f2 n)))
(define (f2 n)
(f1 (- n 1)))
Running this code, you get this result:> (f1 9000) 9000 8999 [snipped] 2 1 0 Blastoff!>To code the equivalent in CL, you might code something like this:
(defun f1 (n) (print n) (if (eql n 0) (print "Blastoff!") (f2 n)))But if you run this program in CL, you get something like the following:
(defun f2 (n) (f1 (- n 1)))
CL-USER> (f1 9000) 9000 8999 [snipped] 4010 4009 4008 Error: `NIL' is not of the expected type `REAL'This is due to a stack overflow as repeated calls get pushed onto the stack. There are a couple ways around this problem:
- You can force tail-call elimination by declaring this specifically to the compiler (Joe Marshall shows how to do this for ACL and LW here and how to do it for CMUCL here). By doing this, the above code will run to "Blastoff!" just as the Scheme code did.
- Alternatively, if you don't want to use the compiler directives (or you're using a CL implementation that doesn't have such directives), you can use a technique known as "trampolining". Basically, this means that you write your functions in such a way that, instead of returning a value, they return the "continuation" (i.e. what to do next). Then the "outer loop" (or trampoline) repeatedly evaluates the current continuation. The following example (based on similar code by Gareth McCaughan) shows how the above code could be re-written in this manner:
(defun f1 (n) (print n) (if (eql n 0) (throw 'done 'Blastoff!) (values #'f2 n)))Running this version of the code does not result in a stack overflow:
(defun f2 (n) (values #'f1 (- n 1)))
(defun run-trampolined (f args) (catch 'done (loop (let ((new-f-and-args (multiple-value-list (apply f args)))) (setf f (first new-f-and-args) args (rest new-f-and-args))))))
CL-USER> (run-trampolined #'f1 '(9000)) 9000 8999 [snipped] 2 1 0 BLASTOFF!As with many things in CL, even if a feature is not built into the language, it is still possible to write code to do it!
