On 11/27/12 9:17 PM, Curtis wrote:
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
<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
<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--%28loop%20%5Bbindings*%20%5D%20exprs*%29>
operates
with recur
<http://clojure.org/special_forms#Special%20Forms--%28recur%20exprs*%29>
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
Chirs Frisz has a post about the history of tail-call and his Clojure
Tail Call Optimization compiler here:
http://www.chrisfrisz.com/blog/?p=234
In it he shows how general tail-call is implemented using
continuations. Fantastic article, I highly recommend it.
-Ben
--
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