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))
(progn
(while (;; 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
function (lambda (,@args) ,body))
(rloop- ( ,@args))))
Here’s how to use it:
defun factorial (x)
(;; this is the recursion entry point
(rloop ((x x)1))
(acc if (< x 1)
(;; done, just return the result
acc ;; not done, start the whole rloop block again
1- x)
(recur (* x acc)))))
(
10)
ELISP> (factorial 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)0)
(curr 1))
(next if (= x 0)
(
curr1- x)
(recur (
next+ curr next)))))
(
10)
ELISP> (fibo 55
Of course, this kind of beauty comes with a price. Here is how the rloop
macro expands:
macroexpand '(rloop ((n 0)) (if (> n 5) n (recur (1+ n)))))
ELISP> (
let* ((n 0))
(
(rloop-#'(lambda (n)
if (> n 5)
(
n1+ n))))
(recur ( 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.