connecting the dots . . .

Oh Joy!

A quote that very closely reflects my own feelings: "[It] feels like a minor miracle. It’s an astoundingly high-quality language, sure—in fact, I’m beginning to think it’s the best I’ve ever seen—yet somehow it has still managed to be fashionable. That’s quite a trick. It gives me renewed hope for the overall future of productivity in our industry." -- Steve Yegge in his foreword to "Joy of Clojure".

Tail recursion without TCO

Emacs lisp has no Tail Call Optimization (TCO), neither do many other lisp dialects. The lack of TCO is not a big deal--it's always possible to transform a tail recursive algorithm into a cycle. However, it makes procedures uglier. Here is a very simple method of enabling Clojure-style tail call recursion in Emacs lisp:

;; A very 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 function
       (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

The funny part is defun is not necessary. You can have as many sequential inlined rloops as you want. I like this approach a lot: all the state management stuff is off the sight. The procedure 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

Nice, eh? 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 way more important.