Simple trampoline implementation for stackless recursion in Java | Hacker News Reader

Simple trampoline implementation for stackless recursion in Java

github.com

21 pointsPaulHoule9 comments

Looks good, but honestly I can't imagine any practical usage of that thing.

I mean, I understand explicit trampolining in Clojure, but in Java you don't often use recursion.

Also, I love Clojure's out-of-the-box minimalist syntax for explicit trampolining. But this one is not that minimalistic + requires additional import.

But there is already a sub-project to support TCO in JVM (but it is very old and progress is very slow...why? I think that's because recursion is rare in Java-world. Nobody actually need this):

http://openjdk.java.net/projects/mlvm/subprojects.html

http://bugs.java.com/bugdatabase/view_bug.do?bug_id=6804517

Aaand AFAIK it is very difficult (impossible?) to do automatic TCO in OOP languages. Check https://archive.is/FfmYF:

But although it is well known how to automatically transform a tail-recursive function into a simple loop, the Java specification doesn't require that this transformation be made. Presumably, one reason it is not a requirement is that, in general, the transformation can't be made statically in an object-oriented language. Instead, the transformation from tail-recursive function to simple loop must be done dynamically by a JIT compiler.

You can do TCO in OOP languages just fine, because it's perfectly possible to have non-virtual functions in OOP languages. But even with virtual method dispatch you can do a tail call (by doing a function call that discards the old stack frame, that is, not by compiling the code to a loop), if you're using the right calling convention. Not that that's necessarily an optimization.

I prefer the term TCE (Tail Call Elimination) to TCO. While it is indeed an optimization of stack space, it transforms programs that use it from "cannot run forever with finite memory" to "can run forever with finite memory".

As long as it is an essential part of the compilation semantics, the description "Optimization" is IMHO unwarranted.

It also transforms programs that use it from "cannot run with a little bit more memory" to "can run forever with a little bit less but still finite memory" which sounds more like an optimization. People are probably solving a problem that needs more, but still a finite amount, of memory, and very likely not solving a problem which needs infinite memory. So calling it an optimization is perfectly warranted.

> People are probably solving a problem that needs more, but still a finite amount, of memory, and very likely not solving a problem which needs infinite memory. So calling it an optimization is perfectly warranted.

Consider the following C program:

    long long i; /* assume 64 bit */
    for (i=0;i>=0;++i) {
       if ((i*i*i -(i>>12) +(i>>24) -(i>>36) +(i>>48))%3819 == 5) {
           printf("found an example: %64i\n", i);
       }
    }

It is not directly useful itself, but variations on it are (e.g. hash cash proof of work computations are not dissimilar). It will run practically forever on every machine on which "long long" is 64 bits. It will likely terminate in finite time on a machine in which "long long" is 32 bit (there's undefined C overflow behaviour, so it might never terminate). And it will do so with zero additional space.

A tail-call equivalent (the only kind of loop available in Scheme, for example) will -- without TCE/TCO -- overflow the stack on a 64-bit integer-or-more (e.g. Scheme's arbitrary precision numbers) on every machine built so far. It will likely do the same even if ints are limited to 32 bit - although a machine with >16GB ram is likely to complete a 32 bit run with reasonably optimized language runtime and stack allocation scheme (neither of which is common - x64 ABI red zones would require >128GB just to do the 32 bit count with full stack frames).

If the int goes to 128 bit, all the memory chips ever produced in the world (and likely all those that will be produced in the next 20 years) would not be enough to stop this program from overflowing its stack - much unlike a TCE/TCO/C version.

In my opinion, something that switches between bounded and unbounded memory requirements should not be called "optimization", but to I guess to each their own.

Is this what clojure's trampoline function is for?

Don't Futures do pretty much the same thing?

I'd say they are vaguely related through decoupling the traditional structure of computations through reified objects.

Reply on news.ycombinator.com