Portable Tail Recursion Optimization in Common Lisp with Trampolines -------------------------------------------------------------------- Recursion is a tool for thought. I use tail recursion, but have to rewrite my program to move it over to ABCL or other non-TCO Lisps. Here is a way to avoid that effort. Terminology for this article ---------------------------- Tail call: When the caller has no more work beyond returning, after the callee returns. Tail call optimization (TCO): (Approximately) making such a call without growing the stack. Can be done because caller's own stack frame is no longer necessary. Recursion: When a function calls itself. Mutual recursion: When there's a cycle in a function call graph. f->g->f Tail recursion: When the recursive call is a tail call. Motivation ---------- - It's hard to optimize a tail call to another function. - But it's easy to optimize a tail _recursion_ by just rewriting the function body. - Relying on TCO is non-portable. - So here is a portability layer that optimizes tail recursion (but not other tail calls, and therefore not mutual recursion). Mechanics --------- Whenever you define a tail recursive function, use defun/tro instead of defun. That's all. (defun/tro factorial (ans n) (if (zerop n) ans (factorial (* ans n) (1- n)))) On Lisps with TCO built-in, define defun/tro to just reduce to a defun: (defmacro defun/tro (&rest args) `(defun ,@args)) On others, define it to rewrite the function. Here is how it works. The macro is shown afterwards. We want the (defun/tro factorial ...) above to expand to the pair: (defun =factorial (ans n) (macrolet ((factorial (&rest a) `(list 'more #'=factorial ,@a))) (if (zerop n) ans (factorial (* ans n) (1- n))))) (defun factorial (&rest a) (do ((x (apply #'=factorial a) (apply (cadr x) (cddr x)))) ((not (and (consp x) (eql 'more (car x)))) x))) That is, instead of making the recursive call, return an indication for the caller to make it. By returning, you pop the stack frame. This is like or the same as a trampoline, if I've understood trampolines. Here is the actual macro. (defun aliasfn (sym fn) (setf (symbol-function sym) fn)) ;only tail recursions are optimised, not other tail calls (defmacro defun/tro (name (&rest args) &body body) (let ((a (gensym)) (=name (gensym)) (more (gensym))) `(progn (defun ,=name (,@args) (macrolet ((,name (&rest ,a) `(list ',',more #',',=name ,@,a))) ,@body)) (aliasfn ',name (tramp #',=name ',more))))) (defun tramp (fn more) (lambda (&rest a) (do ((x (apply fn a) (apply (cadr x) (cddr x)))) ((not (and (consp x) (eql more (car x)))) x))))