Tail Recursion In Erjang

[Tom Hall]

I thought tail recursion was actually not possible on the JVM but saw
a talk on the Erlang VM yesterday and Robert Virding mentioned that
Erjang managed to do it.

I'm sure the core guys have seen it but just in case others thought
the same as me here are a few links:
http://www.javalimit.com/2009/12/tail-recursion-in-erjang.html
https://github.com/trifork/erjang/wiki/How-Erjang-compiles-tail-recursion

If someone could comment briefly on why one would not want to do this
in clojure too that would be nice.

Tom

[Stuart Sierra]

Clojure does tail-call elimination for simple cases with loop/recur. This is by far the most common case. Most other tail-recursive situations can be represented as lazy sequences, which are another way to handle recursive functions without consuming stack space. For the final rare cases (e.g. mutually recursive functions) Clojure has `trampoline`, which does something similar to (on first glance) Erjang.

One nice thing about Clojure's approach is that any function can be invoked from Java just like any other method. On a quick read, I can't tell if  the Erjang approach requires special handling from Java code.

The underlying goal of Clojure's recursion semantics is to always be explicit about where compilation strategies will differ. Loop/recur, lazy seqs, and trampoline all have different performance characteristics. You don't have to guess which method is being used.

-Stuart Sierra
clojure.com

[Tassilo Horn]

Tom Hall <thatto...@gmail.com> writes:

> I'm sure the core guys have seen it but just in case others thought
> the same as me here are a few links:
> http://www.javalimit.com/2009/12/tail-recursion-in-erjang.html
> https://github.com/trifork/erjang/wiki/How-Erjang-compiles-tail-recursion
>
> If someone could comment briefly on why one would not want to do this
> in clojure too that would be nice.

Isn't that pretty much what clojure's `recur' special form does, i.e.,
converting a self-recursion into a non-stack-consuming loop?

Bye,
Tassilo

[Chouser]

On Fri, Oct 21, 2011 at 10:14 AM, Stuart Sierra
<the.stua...@gmail.com> wrote:
> Clojure does tail-call elimination for simple cases with loop/recur. This is
> by far the most common case. Most other tail-recursive situations can be
> represented as lazy sequences, which are another way to handle recursive
> functions without consuming stack space. For the final rare cases (e.g.
> mutually recursive functions) Clojure has `trampoline`, which does something
> similar to (on first glance) Erjang.

I agree, it seems that Erjang is doing a form of trampoline
automatically. Besides Clojure's solution being manual, another
difference is that Clojure returns the data necessary to execute the
next step while Erjang stores that data in a mutable spot that's used
only by the current thread.

> One nice thing about Clojure's approach is that any function can be invoked
> from Java just like any other method. On a quick read, I can't tell if  the
> Erjang approach requires special handling from Java code.

This is a critical question for Java. It looks like every Erjang
function provides an .invoke() method than handles any required
trampolining, so calling that from Java should be safe.

> The underlying goal of Clojure's recursion semantics is to always be
> explicit about where compilation strategies will differ. Loop/recur, lazy
> seqs, and trampoline all have different performance characteristics. You
> don't have to guess which method is being used.

This, combined with the fact that together these techniques cover an
overwhelming majority of use cases (and the fact that they're already
done and work) means the cost/benefit of now adding something like
Erjang does may not be so good.

Hm, and besides performance there are implications for stack traces.
Trampolines, either explicit in Clojure or automatic in Erjang, surely
would make Java stack traces harder to understand as information about
intermediate function calls would be completely missing.

Might be an interesting experiment though.

So... is a function call that could be either of two things (a
loop/recur or a trampoline site) simple or complected?

--Chouser