Tail Recursion in Groovy?

Is it possible?

Tail recursion can be very useful when traversing big lists or trees using recursive methods. The JVM doesn't support tail recursion - maybe there is a way to simlulate them. But first, what is a tail recursion?

A tail recursion is, well I thik the wikipedia explanation is quite good ;) For me the important thing here is to reduce the Stack pollution and not to get an exception from the JVM, because the trace got too big. So a transformation of one kind or another is needed to avoid that.

I know 3 kinds of techniques to accomlish this:

1. use the compiler to transform the recursion into a loop
2. let the vm recognize the recursion and eliminate it
3. mark tail recursion specially and react different then normal

To number 1 I must say, that we could do this in Groovy - partially. That would only work for self recursive functions and it requires the ability to ask the method execution part if that method call is a call to the current method or not. For Java, the last thing is out of question, there is no such query mechanism at runtime to do that. And there is no need, as all methods are selected at compile time. So Java could have this kind of tail recursion. In Groovy we can't be sure if the method we want to call is really being executed. And we may not be sure that the parameters we give really result in the desired method to be executed. Of course we could implement such a query system in Groovy and then we would have the answer. But that would give us only a partial solution as I mentioned already.

Then number 2. Well as long as the Java people don't decide that Java should have that, there is no way for us to get that done in Groovy. Groovy is not a VM in the VM, it is a runtime which does influence the method calls, yes, but it has no real control over the stack.

So what about number 3? Is there something we could do to get tail recursion? Before I get deep in the details imagine the stack that is created for

def foo(){
 bar()
}
def bar(){
 foo()
}

foo()

We will create a stack element for foo, then, when calling bar, we will create a new stack element for bar. After this one again for foo, and this would go on until the JVM complains about the stack becoming too big. What if we would now not directly cal the method, but return from the current stack frame and then do the call? Using Closures we can simulate that:

def foo(){
 {bar()}
}
def bar(){
 {foo()}
}
def cl = foo()
while (cl!=null) {
 cl = cl()
}

With the result, that the function foo is called and returns with the closure. After this, the closure is called, which does call bar. Then bar returns with the closure and the stack size becomes 0 again. Then the closure is again called. This continues till someone forcefully terminates the program, since we crated an endless loop. Of course it is not very nice to have to do that this way. An autmatism would be nice.

So let us say there are keywords like... trreturn and trcall, well not nice, but it is just for illustration. This signals the runtime to not to simply return after the call was made, but to examine the result and react to this. You need to know, that a normal method call foo() is in fact this: ScriptBytecodeAdapter.invokeMethod("foo"). So instead of using the normal invoke we use the our special invoke method invokeMethodTR.

def invokeMethodTR (String name) {
def c = invokeMethod(name)
while (c instanceof TailCall) {
 c = invokeMethod(c.name)
}
return c
}

and foo would be for the compiler:

def foo(){
 return new TailCall(name:"bar")
}

a normal user would see this:

def foo(){
 trreturn bar()
}

But the initial call to foo must be done using trcall, so the complete program would look like:

def foo(){
 trretrun bar()
}
def bar(){
trreturn foo()
}
trcall foo()

This way to do this has actually two problems:

1. Calling such a method from Java would give a TailCall isntance.
2. a void method can't return a TailCall instance

The most easy way to go around that would be not to avoid it. Instead we could use it as marker for the method and remove the trreturn:

TailCall foo(){
 bar()
}
TailCall bar(){
 foo()
}
trcall foo()

The TailCall instance may not only transport the method name and arguments, but also a return value if needed.

Conclusion:
All in all at last one additional keyword is needed to get it working? Maybe using a closure here not even that is needed. We could just say tailcall{foo()} and leave the loop part of the implementation to that method. The compiler is still needed, because someone does have to create the TailCall instances for the return. But the special invokeTR method isn't needed any longer. So any changes to the compiler are doable in no time. Regarding to my question at the start, if it is possible.. well, yes! It's not even very difficult!