Tail call optimisation

[rob....@gmail.com]

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? 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 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?

Thanks, in advance, for your thoughts.


R.

[Rich Hickey]

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

[Stuart Sierra]

On Aug 14, 8:05 am, Rich Hickey <richhic...@gmail.com> wrote:
> I'll let the users chime in on this point.

I've used Clojure with large-ish data sets (hundreds of MB in memory,
tens of GB on disk) and never had a StackOverflowException. After I
got used to the sequence functions, I rarely use recur. Now I think
of recur as a low-level primitive, like a while loop. Abstract
sequences are one of the most innovative features of Clojure, and I
find them easier to understand than classic Scheme-style recursion.

-Stuart