optimizing mutual tail recursion without trampoline

letrec.clj

(ns letrec
  ;; add [org.clojure/tools.macro "0.1.1"] to :dependencies if you use Leiningen,
  ;; or download it from https://github.com/clojure/tools.macro
  (:use [clojure.tools.macro :only [macrolet]]))

(defmacro letrec [bindings & body]
  (let [fnames (map first bindings)
        fname->label (zipmap fnames (range))
        fsym (gensym)
        max-nargs (reduce #(max %1 (count %2)) 0 (map second bindings))
        arg-syms (repeatedly max-nargs gensym)
        pad-args (fn [args] (take max-nargs (concat args (repeat nil))))]
    `(let [~fsym (fn [label# ~@arg-syms]
                   (loop [label# (unchecked-long label#)
                          ~@(interleave arg-syms arg-syms)]
                     (macrolet ~(vec (for [[fname args] bindings]
                                       `(~fname ~args
                                                `(recur ~~(fname->label fname)
                                                        ~~@(pad-args args)))))
                       (case label#
                         ~@(mapcat (fn [[fname args & fbody]]
                                     [(fname->label fname)
                                      `(let [~@(interleave args arg-syms)] ~@fbody)])
                                   bindings)))))
           ~@(mapcat (fn [[fname args]]
                       [fname
                        `(fn ~args (~fsym ~(fname->label fname) ~@(pad-args args)))])
                     bindings)]
       ~@body)))


(comment
  
  ;; The following form:
  (letrec [(even? [n]
             (or (== n 0)
                 (odd? (dec n))))
           (odd? [n]
             (or (not (== n 0))
                 (even? (dec n))))]
    (even? 42))

  ;; is expanded to:
  (let [f (fn [label arg1]
            (loop [label (unchecked-long label), arg1 arg1]
              (macrolet [(even? [n] `(recur 0 ~n))
                         (odd? [n] `(recur 1 ~n))]
                (case label
                  0 (let [n arg1]
                      (or (== n 0)
                          (odd? (dec n))))
                  1 (let [n arg1]
                      (and (not (== n 0))
                           (even? (dec n))))))))
        even? (fn [n] (f 0 n))
        odd? (fn [n] (f 1 n))]
    (even? 42))

  ;; and finally, you'll get:
  (let [f (fn [label arg1]
            (loop [label (unchecked-long label), arg1 arg1]
              (case label
                0 (let [n arg1]
                    (or (== n 0)
                        (recur 0 (dec n))))
                1 (let [n arg1]
                    (and (not (== n 0))
                         (recur 1 (dec n)))))))
        even? (fn [n] (f 0 n))
        odd? (fn [n] (f 1 n))]
    (even? 42))


  ;; letrec is absolutely fast (compared to letfn + trampoline)
  (use letrec.test)

  (set! *unchecked-math* true)
  
  (defn f [^long n]
    (letrec [(even? [n]
               (or (== n 0)
                   (odd? (dec n))))
             (odd? [n]
               (and (not (== n 0))
                    (even? (dec n))))]
      (even? n)))

  (defn g [^long n]
    (letfn [(even? [^long n]
              (or (== n 0)
                  #(odd? (dec n))))
            (odd? [^long n]
              (and (not (== n 0))
                   #(even? (dec n))))]
      (trampoline even? n)))


  user=> (compile 'letrec.test)
  letrec.test
  user=> (dotimes [_ 10] (time (f 100000000)))
  "Elapsed time: 1581.101 msecs"
  "Elapsed time: 1579.477 msecs"
  "Elapsed time: 1611.283 msecs"
  "Elapsed time: 1695.647 msecs"
  "Elapsed time: 1567.76 msecs"
  "Elapsed time: 1584.695 msecs"
  "Elapsed time: 1557.601 msecs"
  "Elapsed time: 1694.939 msecs"
  "Elapsed time: 1572.647 msecs"
  "Elapsed time: 1586.902 msecs"
  nil
  user=> (dotimes [_ 10] (time (g 100000000)))
  "Elapsed time: 14510.544 msecs"
  "Elapsed time: 14781.057 msecs"
  "Elapsed time: 14253.152 msecs"
  "Elapsed time: 14311.466 msecs"
  "Elapsed time: 14150.456 msecs"
  "Elapsed time: 14491.068 msecs"
  "Elapsed time: 15399.248 msecs"
  "Elapsed time: 14647.143 msecs"
  "Elapsed time: 14778.581 msecs"
  "Elapsed time: 14260.018 msecs"
  nil
  user=>

)