Iterative Method Execution Modell in Groovy?

I wonder if that is possible... what? uh, sure, you don't know what I mean. Ok, let us see...

def foo(){
 bar()
}

def bar(){
 foo()
}

You may know this example from the tail recursion article a few days ago. But I want to extend that example now and to this:

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

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

def baz(){}

So every method makes an recursion step and then calls the empty baz method. Congratulations, we succesfully eliminated a tail recursion. While executing these methods may never end in a endless loop, as we need to keep a trace to remember we have to call the baz methods, the available recursion depth isn't as deep as I wish it would be. The last time we work around the problem using Closures... Maybe this would work today again? But what to put in the closure? The calls? No that's no solution. Maybe a special version, that means "make a recursive call and give me what you intend to execute after". So our foo might transform into

def foo(){
 recursiveCall (this.&bar) {baz()}
}

we would put the Closure on our own Stack, leaving this method and then execute bar first.

def recursiveCall(Closure method, Closure tail){
 stack << tail  
 stack << method
}

And foo would not be called normally, but this way:

def recursiveCallEntry(Closure method) {
 stack << method  
 while (stack) {
   stack.pop().call()  
 }
} 
recursiveCallEntry(this.&foo) 

what about tree like structures?

def foo() {
 bar1()
 baz1()
 bar2()
 baz2()
}

could be a tree iteration or something. This would be converted into:

def foo() {
 recursiveCall(this.&bar1){baz1()}
 recursiveCall(this.&bar2){baz2()}
}

And does it still work as it should? After executing these methods we have a stack like this one:

bar2,baz2,bar1,baz1

With bar2 on top. That's bad, bar1 needs to be executed first. So we need to reorder that.. but not in recursiveCall. You may see that recursiveCall, is doing something like a collection step. Collecting all method calls that we need to do. So if we collect all the calls the recursiveCall methods do in a list or something, we can simply revert the list and then put the elements in the correct order on the stack. As our recursiveCallEntry method does have the real control over the custom stack, we can use that method.

def recursiveCallEntry(Closure method) {
 stack << method
 while (stack) {
   frame = []
   stack.pop().call()
   stack.addAll(frame.reverse())  
 }
} 

def recursiveCall(Closure method, Closure tail){   
 frame << method   
 frame << tail
}

As you see we no longer revert the order in recursiveCall, since we do this explicitly with frame.revert in recursiveCallEntry. Using this system we can bypass the normal stack, build our own stack and get a much better depth. But "recursiveCall(this.&bar1){baz1()}" looks really ugly. Oh.. do we need that? why distinguish between the real recursive call and the non-recusrive calls? No, I don't think so.

def foo() {
 recursiveCall this.&bar1
 recursiveCall this.&baz1
 recursiveCall this.&bar2
 recursiveCall this.&baz2
}

That is better, but still not nice. We could use Strings for the method name, but we then loose the object we want to execute the method closure on. Oh.. and parameters? In the end the code would look like

recursiveCall (this, "baz2", null)

to call the baz2 method. what most people probably don't know is that such a line already exists in the bytecode, because each normal method call is done by using a method of ScriptBytecodeAdapter. So if had a flag method or something we could use that to execute our methods and keep the readability. Oh no, again a crazy idea is born.

def foo() {
 switchToIterativeCallSystem()
 bar1()
 baz1()
 bar2()
 baz2()
 switchToRecursiveCallSystem()
}

but wait... do we really have to do that on the ScriptBytecodeAdapter? We can do that with the MetaClass too! We simply need to replace the MetaClass for "this" with our own crazy version...

class IterativeCallerMetaClass extends  DelegatingMetaClass {
 def stack =[]
 def frame
 boolean iterativeCallSystem=false

 public IterativeCallerMetaClass (final MetaClass delegate) {
   super(delegate);
 }

 def invokeMethod(Object object, String methodName, Object[] arguments) {
   if (iterativeCallSystem){
     frame << [object,methodName,arguments]  
   } else {    
     delegate.invokeMethod(object, methodName, arguments);  
   }  
   return null
 } 

 def recursiveCallEntry(Closure method) {   
   stack << method  
   while (stack) {
     frame = []
     def call = stack.pop()
     delegate.invokeMethod(call[0], call[1], call[2]);
     stack.addAll(frame.reverse())   
   }  
 }
} 

And the complete calling code would maybe llok like this:

def foo() {
  metaClass.iterativeCallSystem = true
  bar1()
  baz1()
  bar2()
  baz2()
  metaClass.iterativeCallSystem = false
}

this.setMetaClass ( new IterativeCallerMetaClass (this.getMetaClass()) )

Disadvantages? Yes, sure. This completly ignores the return value. And sadly I don't see a way to fizzle it in. I mean a call foo(foo(1)) is really something like "tmp = foo(1); foo(tmp)". That means I need the value of "tmp" while I am still in the collection phase, where it isn't available, since the call isn't done then. Next disadvantage is, that that MetaClass only works on one object. Any foo.toString(), where foo!=this, isn't collected. Which directly leads to the next problem, logic operations are executed before the values are available.

To work around that we can put all that code in Closure and add these closures to the custom MetaClass stack, but that gives again problems with local variables and such. If you have a tree with an unknown number of children and you want to do an depth first search on the children, you would normally do something like that:

def search(node,constraint) {
 if (constraint(node)) return node
 node.children.each{search(it,constraint)}
}

But when you want to use our iterative system...

def search(node,constraint) {
 metaClass.add {
   if (!found && !constraint(node)){
    node.children.each {search(it,constraint)}
  } else {
    found=node
  }
 }
}

That's an ugly level of indirection... I used the global variable found to indicate if we need to search deeper, this avoids the return value. Then the closure will be put on the stack and executed when the data is available, collecting the search calls and later execute each of them. This can only work if all actions other than pure method calls on this are done in closures.

Conclusion:
This let's me think that such an solution should be much more easy in Ruby. But as I don't know enough about Ruby I don't know if there is such a MetaClass system as we have in Groovy. But being able to simply put the method body on the stack instead of a closure would be nice. Anyway, it works. We can also remove the "metaClass.iterativeCallSystem=" lines with the convention that the system is always active. Of course this works with a builder just as fine as with a normal class, you only have to do the job of our MetaClass in the builder then.

You see, many tricks can be done with the MetaClass, even a total different method execution model. Ok, not toally different, as the VM still does the invocation and still keeps a trace, but we successfully shortend that stack trace. Oh, and of course the above works for tail recursion just as well. You can say we included them here already. Of course the solution developed into a completly different direction than my previous post about tail recursion.

And maybe a word about the execution speed. Of course you add an additional level of indirection for method calls, our delegating MetaClass. So instead of doing one mthod call we do much more of them, for example when testing the stack if it is empty, when getting the top frame and more. But if your focus is on avoiding a stack overflow it works just fine.