Thank you Andy - This was fabulously helpful - I really appreciate your explanation.
Would you permit me to include your answer in a blog post about the above question? On Monday, November 19, 2012 6:25:30 PM UTC-8, Andy Fingerhut wrote: > > 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<http://clojure.org/special_forms#Special%20Forms--(loop%20%5Bbindings*%20%5D%20exprs*)> > operates > with recur<http://clojure.org/special_forms#Special%20Forms--(recur%20exprs*)> > > 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 clojure@googlegroups.com Note that posts from new members are moderated - please be patient with your first post. To unsubscribe from this group, send email to clojure+unsubscr...@googlegroups.com For more options, visit this group at http://groups.google.com/group/clojure?hl=en
