Tail Recursion Without TCO

It is well known that Emacs Lisp, like many other Lisp dialects, has no Tail Call Optimization (TCO). Nevertheless, it’s possible to add proper recursion to Emacs Lisp with the help of a few macros.

Here is a very simple method of enabling Clojure-style tail call recursion in Emacs lisp:

;; A simple linearized Y combinator.
;; All the state management stuff is incapsulated here.
;; Don't call it directly.
(defun rloop- (body &rest args)
  (let ((res nil))
    (while (progn
             ;; here's the idea: we keep calling body
             ;; while it returns the recursion marker
             (setq res (apply body args))
             (when (and (consp res)
                        (eq :loop-recur-marker (car res)))
               (progn (setq args (cdr res))
                      t))))
    res))

;; Recursion marker factory
(defun recur (&rest args)
  ;; instead of a real recursive call,
  ;; just signal an intention to make one
  (cons :loop-recur-marker args))

;; The form macro
(defmacro rloop (init body)
  (let ((args (mapcar 'car init)))
    ;; a little courtesy to the macro users
    `(let* ,init
       ;; make a lambda from the body and pass it
       ;; to the combinator
       (rloop- (function (lambda (,@args) ,body))
               ,@args))))

Here’s how to use it:

(defun factorial (x)
  ;; this is the recursion entry point
  (rloop ((x   x)
          (acc 1))
         (if (< x 1)
             acc ;; done, just return the result
           ;; not done, start the whole rloop block again
           (recur (1- x)
                  (* x acc)))))

ELISP> (factorial 10)
3628800

It is interesting that defun is not necessary. You can have as many sequential inlined rloop’s as you want. I really like this approach: all the state management stuff is off the sight. The function code is almost identical to the underlying algorithm. Another classic example:

(defun fibo (x)
  (rloop ((x    x)
          (curr 0)
          (next 1))
         (if (= x 0)
             curr
           (recur (1- x)
                   next
                  (+ curr next)))))

ELISP> (fibo 10)
55

Of course, this kind of beauty comes with a price. Here is how the rloop macro expands:

ELISP> (macroexpand '(rloop ((n 0)) (if (> n 5) n (recur (1+ n)))))

(let* ((n 0))
  (rloop-
   #'(lambda (n)
       (if (> n 5)
           n
         (recur (1+ n))))
   n))

…which means two extra function calls on each iteration. But realistically, it’s not such a big deal. Clarity of the code is more important.