question about tail recursion optimization in Clojure

[Leo Antoli]

Hi,

I understand JVM doesn't support tail recursion optimization yet.

But couldn't it be done by Clojure itself ? I guess I'm missing something, but for instance for this code:

(def lineage-1 

   (fn [class-symbol so-far] 

      (if (nil? class-symbol) so-far 

         (lineage-1 

             (class-symbol-above class-symbol) 

             (cons class-symbol so-far)))))

the Reader and/or Eval could analyze it and add "recur" keyword if possible to get:

(def lineage-1 

   (fn [class-symbol so-far] 

      (if (nil? class-symbol) so-far 

         (lineage-1 

             (recur 

                (class-symbol-above class-symbol) 

                (cons class-symbol so-far))))))

Isn't that possible ? Is the problem that the Reader/Eval should be too much clever ?

Thanks.

Regards,

Leo

[Brian Marick]

On Sep 2, 2012, at 3:00 AM, Leo Antoli wrote:

> Hi,
> I understand JVM doesn't support tail recursion optimization yet.
>
> But couldn't it be done by Clojure itself ? I guess I'm missing something, but for instance for this code:
>
> (def lineage-1
> (fn [class-symbol so-far]
> (if (nil? class-symbol) so-far
> (lineage-1
> (class-symbol-above class-symbol)
> (cons class-symbol so-far)))))
>
> the Reader and/or Eval could analyze it and add "recur" keyword if possible to get:
>
> (def lineage-1
> (fn [class-symbol so-far]
> (if (nil? class-symbol) so-far
> (lineage-1
> (recur
> (class-symbol-above class-symbol)
> (cons class-symbol so-far))))))

I think the answer is that the way `def` works is that:

1. It creates the symbol `lineage-1`.
2. It creates a function that has a reference to the symbol `lineage-1`.
3. It binds the new function to the symbol `lineage-1`.

Note that at the time of step 2, the function doesn't know that `lineage-1` will be its own future name.

-----
Brian Marick, Artisanal Labrador
Contract programming in Ruby and Clojure
Occasional consulting on Agile
Writing /Functional Programming for the Object-Oriented Programmer/: https://leanpub.com/fp-oo

[Leo Antoli]

Thanks Brian, 

that makes sense.

Scala tries to optimize tail calls but it's a bit cheating because it's done in compilation time.

There is even a nice annotations @tailrec in case you want to know if a function has been optimised (you get an error if it's not).

According to a post http://blog.richdougherty.com/2009/04/tail-calls-tailrec-and-trampolines.html

"Luckily, even without JVM support, the Scala compiler can perform tail-call optimisation in some cases. The compiler looks for certain types of tail calls and translates them automatically into loops. At the moment it can optimise self calls in final methods and in local functions. It cannot optimise non-final methods (because they might be overridden by a subclass), and it cannot optimise tail calls that are made to different methods."

Of course it'll be better if JVM support tail recursion optimisation itself, and I think it'll eventually do.

Congratulations, I really enjoyed reading your book.

Regards,

Leo

--
You received this message because you are subscribed to the Google Groups "fp-oo" group.
To post to this group, send email to fp...@googlegroups.com.
To unsubscribe from this group, send email to fp-oo+un...@googlegroups.com.
For more options, visit https://groups.google.com/groups/opt_out.

[Brian Marick]

On Sep 26, 2012, at 2:59 AM, Leo Antoli wrote:

> Congratulations, I really enjoyed reading your book.

Thanks, but it's not done you know. Just finished the first draft of the javascript-in-clojure chapter.

[Leo Antoli]

I know, I'm talking about what's published so far :-)