This is perhaps a slight digression; just an extended expression of pleasure about the Clojure?s recur statement. It neatly squashes a bee I?ve had in my bonnet for some years now; if it?s wrong to loathe ?tail recursion optimization? then I don?t want to be right.

Terminology

I acknowledge that recur isn?t a ?statement?, it?s actually a ?special form? which is what languages that don?t want to admit having syntax call their keywords. But hey, it?s a built-in fixed-syntax thingie that usually stands on its own line and causes transfer of control to another place in the program, so for my money it walks like a statement and works like a statement.

Recur Details

There?s nothing to it, really. If you?re in a function and you say (recur*arg*arg*...)*?*the number of arguments has to be the same as the function takes*?*you restart the function with the new set of arguments from the recur. It?s a highly controlled and structured GOTO. This walks like a loop and smells like a loop, and so, sensibly enough, there?s another statement oops special form called loop:

(def factorial (fn [n] (loop [cnt n acc 1] (if (zero? cnt) acc (recur (dec cnt) (* acc cnt)))))) (Gosh, I can?t help but noticing how, in Erlang, you see tons of functions which exist only to do tail-recursive looping and have names like looper or whatever_loop. Nudge nudge, wink wink.)

recur is simple, it?s easy to understand, it doesn?t burn stack space, and the function or loop arguments are still immutable in the context of any single pass through. Also I find the name ?recur? to be an example of engineering elegance; obviously correct, once you think of it.

I?m amused by the write-ups in the Clojure literature; they all take the form of ?Since Clojure is based on Java, and the JVM doesn?t do tail-call optimization (how sad) we were forced to provide this recur thingie. Sorry ?bout that, and if Java gets its act together, we?ll do tail calls right.?

But it seems obvious to me that recur is better than tail-call-optimized recursion.

Why I Hate Tail Call Recursion Optimization

It feels like a big fat lie. It looks like a subroutine call, but in the case where it occurs as the last thing in the routine, it magically, silently, and automatically gets turned into, now how did I put it? ?A highly controlled and structured GOTO.?

If that?s what the programmer wants, then that?s what the programmer should bloody well ask for. I?ve always been irritated by the explanations, in the Erlang and Lisp introductory books, about how you must be careful to ensure that your recursive calls are the last thing executed, and I?ve observed this leading sometimes to some gnarly unintuitive if/else branch placement. Call me old-fashioned, but it just seems wrong when the semantics of two identical function invocations vary wildly as a function of whether there?s an executable statement between the invocation and the function exit.

I Know I Know I Know

Every time I write about this I get lectures in the comments, explaining in a superior tone of voice that I don?t really understand the wonders of the tail call, and pointing me at Guy Steele?s 1977 paper (PDF) on the subject. I think the semantics of computer programs should be made explicit in their syntax. recur does this. It?s a good thing.




More...