In Scala 2.8.x, a new annotation (@tailrec
) has been added that gives a compile-time error if the compiler cannot perform a tail-call optimization on the annotated method.
Is there some similar facility in Clojure with respect to loop/recur
?
EDIT: After reading the first answer to my question (thanks, Bozhidar Batsov) and further searching in the Clojure docs, I came across this:
(recur exprs*)
Evaluates the exprs in order, then, in parallel, rebinds the bindings of the recursion point to the values of the exprs. If the recursion point was a fn method, then it rebinds the params. If the recursion point was a loop, then it rebinds the loop bindings. Execution then jumps back to the recursion point. The recur expression must match the arity of the recursion point exactly. In particular, if the recursion point was the top of a variadic fn method, there is no gathering of rest args - a single seq (or null) should be passed. recur in other than a tail position is an error.
Note that recur is the only non-stack-consuming looping construct in Clojure. There is no tail-call optimization and the use of self-calls for looping of unknown bounds is discouraged. recur is functional and its use in tail-position is verified by the compiler [emphasis is mine].
(def factorial
(fn [n]
(loop [cnt n acc 1]
(if (zero? cnt)
acc
(recur (dec cnt) (* acc cnt))))))
Actually the situation in Scala w.r.t. Tail Call Optimisation is the same as in Clojure: it is possible to perform it in simple situations, such as self-recursion, but not in general situations, such as calling an arbitrary function in tail position.
This is due to the way the JVM works -- for TCO to work on the JVM, the JVM itself would have to support it, which it currently doesn't (though this might change when JDK7 is released).
See e.g. this blog entry for a discussion of TCO and trampolining in Scala. Clojure has exactly the same features to facilitate non-stack-consuming (= tail-call-optimised) recursion; this includes throwing a compile-time error when user code tries to call recur
in non-tail position.
There is no tail-call optimization when you use loop/recur AFAIK. A quote from the official docs:
In the absence of mutable local variables, looping and iteration must take a different form than in languages with built-in for or while constructs that are controlled by changing state. In functional languages looping and iteration are replaced/implemented via recursive function calls. Many such languages guarantee that function calls made in tail position do not consume stack space, and thus recursive loops utilize constant space. Since Clojure uses the Java calling conventions, it cannot, and does not, make the same tail call optimization guarantees. Instead, it provides the recur special operator, which does constant-space recursive looping by rebinding and jumping to the nearest enclosing loop or function frame. While not as general as tail-call-optimization, it allows most of the same elegant constructs, and offers the advantage of checking that calls to recur can only happen in a tail position.
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With