If you are familiar with tail recursion, then loop/recur this is Clojure's way to achieve tail recursion.
http://en.wikipedia.org/wiki/Tail_call The general tail call optimization mechanism as implemented in the programming language Scheme, for example, means that tail-position calls must not consume additional stack, and must effectively work like a goto appropriate muddling of stack frames to pass the parameters to the new function (which might be a recursive call, or could be to a different function). Whether the tail call is recursive or not, the return address of the original calling function doesn't change after the goto. Clojure's loop/recur only implements tail recursion, not general tail-call optimization. tail recursion is far more commonly used in languages that have it than the general tail-call optimization to arbitrary functions. Specifically on your questions about the return address, suppose function foo calls function bar, and bar has the loop/recur inside of it. At the time when foo first calls bar, it saves a return address inside of foo so that when bar returns, it continues in foo just after where the call to bar was. loop/recur never touches that return address. It stays there the whole time. The loop is effectively a target label for a goto, and one or more occurrences of recur inside of it simply rebind the loop variable values, and goot the loop's target label. Anything deeper down on the stack is not changed, and there is no pushing or popping of any return addresses. Just a goto. Rich would have liked to implement general tail recursion in Clojure. Here are a couple of relevant excerpts from Rich Hickey's "Clojure for Lispers" talk, transcript here: http://jafingerhut.github.com/clojure-info/clojure-for-lispers-transcript.txt Clojure does not have tail call optimization. Not because I'm against it. I'm all for it. It's something I had to trade off in being on the JVM. However, I was just at the JVM languages summit, and tail call optimization, every language designer who cam up there said "tail call optimization, tail call optimization". And they've heard it, and hopefully it will come in a future VM, hopefully soon. You've seen languages... SISC Scheme does tail calls in the JVM, right. It does it with this whole other infrastructure. They're calling scheme is nothing like Java's, right? You have to pass additional things, or trampoline, or whatever. Clojure does none of that. Clojure has pedal to the metal calling conventions that match Java's, so I don't have tail recursion, because you can't do that unless the JVM does that. Andy On Nov 19, 2012, at 4:38 PM, Curtis wrote: > Clojure Koans - Recursion > (defn recursive-reverse [coll] > (loop [coll coll > acc '() ] > (if (= (count coll) 0) > acc > (recur (rest coll) (cons (first coll) acc)) > ) > ) > ) > I struggled with this one for a while - I don’t want to admit it, but > honestly even though i have been coding since I was 16 years old - there are > still many areas where I am rusty or weak. > > There is actually a surprising amount of low level concepts operating in a > list recursive reverse in clojure. > > tail-call recursion > accumulator > loop construct > I have some questions about how this “special form” loop operates with recur > > I think I need to make sure that I always remember the following : > > the arity of the recur call must match the arity of the loop form > recur must be in the tail position. > I’m not sure how this loop / recur mechanism is implemented in the JVM - I > imaging that the binding created by ‘loop’ is associated with registers that > are overwritten as part of the call to ‘recur’. The documentation says the > bindings are rebound on call of recur in parallel and the execution of recur > - is done in order. > > My questions are > > Is recur causing some kind of local jump after each binding? > What happens with the return address? > If recur doesn’t consume stack - what is going on with the return address? > Is the return address always the same for the same recursive call? > More importantly - Is there a chapter in Knuth AOC that could help me with > this? Any other resources? > > I feel like I am really missing some context. Am I missing anything obvious, > important or insightful? -- You received this message because you are subscribed to the Google Groups "Clojure" group. To post to this group, send email to [email protected] Note that posts from new members are moderated - please be patient with your first post. To unsubscribe from this group, send email to [email protected] For more options, visit this group at http://groups.google.com/group/clojure?hl=en
