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
