I found Rich's answer August 14th, 2008:
On Aug 14, 6:35 am, "rob.la...@gmail.com" <rob.la...@gmail.com> wrote:
> As I understand it, Clojure does not have tail call optimisation,
> because of limitations of the JVM. Scala, however, has TCO, or at
> least something called Tail Recursion Optimisation which, from my
> newbie perspective seems to be more or less the same thing. ( I can't
> find a definitive reference on this, but the web is littered with
> references )
>
> Are they the same thing?
No they are not. Full TCO optimizes all calls in the tail position,
whether to the same function or another. No language that uses the JVM
stack and calling convention (e.g. Clojure and Scala) can do TCO since
it would require either stack manipulation capabilities not offered in
the bytecode spec or direct support in the JVM. The latter is the best
hope for functional languages on the JVM, but I'm not sure is a
priority for Sun as tail-calls are not idiomatic for JRuby/Jython/
Groovy.
IMO, either a language has full TCO or it simply doesn't support using
function calls for control flow, and shouldn't use the term. I didn't
implement self-tail-call optimizations because I think, for people who
rely on TCO, having some calls be optimized and some not is more a
recipe for error than a feature.
So, Clojure has recur, which clearly labels the only situations that
won't grow the stack, apologizes for no real TCO, doesn't pretend to
support function calls for control flow, and anxiously awaits TCO in
the JVM, at which point it will fully support it.
> Is this something that Clojure could/should
> copy?
>
> I ask, because I find that I develop a little nagging voice squeaking
> "beware the stack depth" every time I implement a recursive solution.
> Is this an irrational fear? Should I worry about this?
>
I don't think so, once you have an understanding of the options in
Clojure. In addition to recur, there are lazy sequences and lazy-cons.
To the extent you can structure your processing using the lazy
sequence model, including making your own calls to lazy cons, you can
write traditional-looking functional and recursive solutions that not
only don't grow the stack, but also don't create fully-realized result
lists on the heap, a terrific efficiency boost. I am not contending
that this is as general as TCO, but it has other nice properties, like
the ability to make results that are not tail calls (e.g. list
builders) space efficient.
You should be wary of transliterating Scheme code that relies on TCO
to Clojure.
> I haven't had any problems so far in the toy applications I've worked
> with; but in my day-job I've had to deal with large-ish data-sets that
> grow over time and the prospect of one day experiencing
> StackOverflowException on a production app scares me silly.
>
> Now, I know I could implement everything manually using recur, but it
> doesn't feel natural. Is this something that I should just get over?
> Will it feel natural in time?
>
I'll let the users chime in on this point.
Rich
On Wed, 26 Jan 2011 13:10:52 -0800 (PST)
Armando Blancas <armando_blan...@yahoo.com> wrote:
> From SICP: "With a tail-recursive implementation, iteration can be
> expressed using the ordinary procedure call mechanism". As I
> understand this, a tail call is a loop with functional notation but
> not actually a function call. That's why I find this issue difficult
> to follow, since loops are internal details of a function/method and
> don't get involved with calls, stack frames, access security, or how
> the jit-compiled code may or may not be optimized. So there's
> something key here that I'm missing.
>
> In a little project of mine I plan on doing this (hand-coded with ASM
> as my compiler doesn't do TCO yet). That seems to work but I wonder
> what issues may come up.
>
> int fact(int n, int r) {
> if (n == 0) return r;
> else return fact(n-1, n*r);
> }
> 0: iload_0
> 1: ifne 6
> 4: iload_1
> 5: ireturn
> 6: iload_0
> 7: istore_2 // temp for n
> 8: iload_2
> 9: iconst_1
> 10: isub
> 11: istore_0
> 12: iload_2
> 13: iload_1
> 14: imul
> 15: istore_1
> 16: goto 0
>
> On Jan 26, 11:20 am, Luc Prefontaine <lprefonta...@softaddicts.ca>
> wrote:
> > From what I recall from a previous thread it would require so much
> > byte code tweaking that Hot Spot optimizations would become useless.
> >
> > You can search the mailing list, you will find a couple of
> > instructive discussions about this.
> >
> > Luc P.
> >
> > On Wed, 26 Jan 2011 10:01:04 -0800
> >
> > Raoul Duke <rao...@gmail.com> wrote:
> > > On Wed, Jan 26, 2011 at 7:41 AM, Michael Gardner
> > > <gardne...@gmail.com> wrote:
> > > > However, the JVM does not support tail-call optimization.
> > > > Apparently Clojure can't support implicit TCO without support
> > > > from the JVM
> >
> > > always wondered about that also wrt scala etc., am under the
> > > impression that it is implementable, but it would be too slow?
> >
> > --
> > Luc P.
> >
> > ================
> > The rabid Muppet
>
--
Luc P.
================
The rabid Muppet
--
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
