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

Reply via email to