Automatic TCO in Clojure

Question

Is there a way to define a function in Clojure that is automatically tail-call-optimized?

e.g.

(defrecur fact [x]
    (if (= x 1)
        1
        (* x (fact (dec x)))))

would be translated internally to something like:

(defn fact [x]
    (loop [n x f 1]
        (if (= n 1)
            f
            (recur (dec n) (* f n)))))

Can you tell me if something like this already exists?

Answer 1

To the best of my knowledge, there is no automatic way to generate tail recursion in Clojure.

There are examples of functions that use recursion without using loop .. recur that work without overflowing the stack. That is because those functions have been carefully written to use lazy sequences.

Here is an example of replacing flatten with a hand-written function. This example came from http://yyhh.org/blog/2011/05/my-solutions-first-50-problems-4clojure-com

(fn flt [coll]
  (let [l (first coll) r (next coll)]
    (concat 
      (if (sequential? l)
        (flt l)
        [l])
      (when (sequential? r)
        (flt r)))))

Answer 2

One of the guiding principals behind this decision was to make the special part look special. that way it is obvious where tail calls are in use and where they are not. This was a deliberate design decision on which some people have strong opinions though in practice I rarely see recur used in idomatic Clojure anyway so In practice it's not a common problem.

Answer 3

The short answer is "No".

The slightly longer answer is that Clojure is deliberately designed to require explicit indication where Tail Call Optimisation is desired, because the JVM doesn't support it natively.

Incidentally, you can use recur without loop, so there's no more typing required, e.g.:

(defn func [x]
  (if (= x 1000000)
    x
    (recur (inc x))))

Update, April 29:

Chris Frisz has been working on a Clojure TCO research project with Dan Friedman, and whilst nobody is claiming it to be 'the answer' at this time, the project is both interesting and promising. Chris recently gave an informal talk about this project, and he's posted it on his blog.