On 12 April 2016 at 14:58, Cornelius Goh <cornelius...@gmail.com> wrote:
> True. Clojure doesn't provide tail call optimization. According to Daniel
> Higginbotham book "Clojure for the Brave and True" (Page 102) he suggests
> using "recur" for performance reasons.
>
> That is, in Olivier's original code, (sorry, without understanding his
> puzzle):
>
>
> (defn permutations [s]
> (lazy-seq
> ...
> ...
> (map # (...) (recur (remove #...)))))
> ...
>
> See if it improves performance by just using "recur" ?
But you can't do that, because you're using the return value there
(specifically, as the argument to map). If you try it, you'll see that the
compiler throws an error.
The idea behind tail call elimination is that, if the very last thing that
your function, say fnA, does is returning the result of a call to another
function, say fnB, then you do not need the stack frame of fnA during the
call to fnB, and you can preemptively pop it before calling fnB. But this
only works if calling fnB is the very last thing that fnA does: if fnA
still has some work to do with the result of fnB, its stack cannot be
destroyed. (You could argue that a sufficiently smart compiler could "trim"
the stack to just what will be needed after the call to fnB, but it's not
the same.)
A simple, well-known example is the case of the recursive factorial
function:
(defn non-tce-fact
[n]
(if (zero? n)
1
(* n (non-tce-fact (dec n)))))
(defn tce-fact
([n] (tce-fact n 1))
([n p]
(if (zero? n)
p
(recur (dec n) (* n p)))))
Note that in the first function, the result of the recursive call is used
in the multiplication, whereas in the second function the result is
directly the result of the recursive call.
Most common examples are of recursive functions, but TCE is (in principle)
a general technique that can be applied to any function whose last
instruction is a call to another function.
In Clojure, only recursive tail call elimination is supported, and only
when the programmer explicitly requires it by using recur instead of an
explicit recursive call. This has the advantage (and disadvantage) of being
explicit and checked by the compiler (i.e. if you use recur in a non-tail
position, you get an error).
--
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
---
You received this message because you are subscribed to the Google Groups
"Clojure" group.
To unsubscribe from this group and stop receiving emails from it, send an email
to clojure+unsubscr...@googlegroups.com.
For more options, visit https://groups.google.com/d/optout.
