3.4 Using optimized constructs

3.4.1 Tail call optimization

Unless directed otherwise, the Compiler optimizes self-recursive function calls, tail calls, and self-tail calls. In particular, self-tail calls are automatically compiled as loops. While these function calls are efficient, they can be difficult to trace because they do not appear on the stack.

(defun fact (n) 
  (if (< n 1) 1 (* n (fact (1- n)))))

Unless compiled asnotinline, self-recursive function calls jump directly to the start of the code rather than going through thesymbol-function slot. A trace of a self-recursive function shows only the initial call, not the resulting recursive calls. For example, if you tracefact, a call to (fact2) shows only the initial call tofact, not the recursive calls to (fact1) and (fact0).

(defun analyze-cereal (cereal)
  (case (cereal-kind cereal)
    (oat (analyze-oat-cereal cereal))
    (wheat (analyze-wheat-cereal cereal))
    (sugar (analyze-sugar-cereal cereal))
    (t (analyze-other-cereal cereal))))

(defun my-last (x)
 (if (cdr x) (my-last (cdr x)) x))

A function defined using self-tail calls is a tail-recursive function. Because of tail merging, tail-recursive functions are usually as efficient as functions defined using iterative constructs.

When the Compiler compiles either a tail call or a self-tail call, it reuses the calling function's stack frame rather than creating a new stack frame. This optimization is called tail merging.

The Advanced User's Guide - 9 SEP 1996

Generated with Harlequin WebMaker