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?

A different (but still relevant) question might be, "Is there an automated way to transform a recursive function into a function that uses `recur`?" If not, is it provably impossible? — user100464, Apr 18 '12 at 16:00
To show why I need it, it might me important to know that I am still working on implementing [Shen](http://shenlanguage.org) in Clojure. Shen automatically performs TCO. — Dominik G, Apr 21 '12 at 12:33
just saw http://www.chrisfrisz.com/blog/?p=220 which reminded me of this q. don't know if you've seen it. — andrew cooke, Apr 29 '12 at 22:10

Scott · Answer 1 · 2012-04-29T13:51:09.677

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.

edited Apr 29 '12 at 13:51

answered Apr 18 '12 at 15:43

Scott

17,127
5
53
64

Thank you, I know that there is no inbuilt function to do this, I thought there might be some community function/macro which does this. I also know that you can use recur without loop. But sadly, just replacing the recursive call by recur doesn't make the trick. – Dominik G Apr 18 '12 at 15:52

score 1 · Answer 2 · answered Apr 18 '12 at 15:45

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)))))

score 1 · Answer 3 · answered Apr 18 '12 at 20:32

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.

Automatic TCO in Clojure

3 Answers3

Linked