GreenThread: Problems with Recursive Functions

In previous blog posts on GreenThreads I mentioned that the downsides of using GreenThreads meant you couldn't write recursive functions. In one of the comments I was asked to expand on this idea, and after the comment got so long I figured a blog article might be a better forum for this topic. I'm going to discuss the issues with regular recursive functions, then we'll explore the differences between two types of recursive functions, and potential changes that could be made to help make it easier to write recursive GreenThreads.

Let's start by examining the following function:

public function factorial( i : int ) : int {
   if( i == 0 ) return 1;
   return i * factorial( i - 1 );
}

It's like the "hello world" of recursive functions. What makes a function recursive is the fact factorial() function calls itself in evaluating the value of the function. If we were to run it in a GreenThread there's no way for the system to interrupt the function calls should this function take longer than the length of a frame. For example, say you ran factorial(5) in the GreenThread. The call stack will look like the following:

factorial(5) -> factorial(4) -> factorial(3) -> factorial(2) -> factorial(1) -> factorial(0)

There's no way to let Flash insert a paint in between factorial(3) calling factorial(2) because factorial(3) calls factorial(2) directly.

The way GreenThread framework works is that it handles repeatedly calling your GreenThread until the time has elapsed for a single frame. At that point it let's Flash have control again and then resumes on the next frame repeating this process until your GreenThread says it's finished. This is actually implemented using a big loop outside your GreenThread.

It gets even harder for recursive functions. Look back at factorial() function. Notice that factorial(5) has to compute factorial(4) before multiplying by 5 so it can return it's value. Therefore, it's not possible break out of the function call, allow Flash to paint, then resume within a function so it can multiply by 5 to finish the computation. (Not unless Flash supported continuations, but that's a whole another topic). So now recursive functions can't be interrupted because the function directly calls itself, and depending on how you write your recursive function it's not possible to put a break because of operations that might come after the recursive call finishes.

There are other issues with recursive functions, but they are not possible to use in a GreenThread because of the dependencies between stack frames. However, there is another type of recursion that can help eliminate dependencies. Let's write our recursive function to remove the dependency on local operations:

public function factorial( i : int, accumlator : int = 1 ) : int {
   if( i == 0 ) return accumlator;
   return factorial( i - 1, i * accumlator );
}

Now notice that factorial(5) doesn't have extra work to run after factorial(4,5) runs like we did before. This means factorial(5) could be replaced by the return from factorial( 4, 5 ). In fact factorial(5) == factorial(4,5)! This technique is called tail recursion, and in certain languages it helps make recursion work without growing the stack frames so large iterations don't overflow the stack. Now Actionscript doesn't benefit from this, but this will allow us to work around the second problem we have. We still have our original problem so we'll have to tackle that before we're done.

Now we still have factorial(5) directly calling factorial( 4, 5 ) so Flash can't interrupt the function calls so it can paint. However, what if we had a special call that would delay calling factorial(4,5) so we could do whatever Flash wanted, then it would resume our recursive function.

Well there exists such a function: callLater(). callLater() can be used to schedule a function to be called in the next frame, and in fact from all of the testing done it's safe to use callLater() as a technique for implementing GreenThreads. However, directly using it will suffer from poor performance because of long waits between function calls. So, let's assume there is a new function in GreenThread that acts like callLater(), but achieves better performance. Now our recursive function could look like:

public function factorial( i : int, accumlator : int = 1 ) : Boolean {
   if( i == 0 ) return false;
   return invokeOnThread( factorial, i - 1, i * accumlator );
}

Now invokeOnThread() doesn't exist in the current code base, but it could be written. Actually the accumlator would probably be best served as an instance variable within your GreenThread, and we'd need to change some more features to fit within the framework. Assuming that it is we could support recursive functions given these constraints:

• You must write your recursive calls so they conform to tail recursion.


• You must use invokeOnThread() to recursively call your function.


• You must conform to the contracts of the GreenThread framework.

The upside is the ability to think recursively. While every algorithm can be expressed either in iteration or recursion it's not easy to convert between each form. Some algorithms are easier to express using recursion and can be very hard to write iteratively. The downside is the requirement to write tail recursive algorithms which can be difficult for the uninitiated, but it's a skill that can be honed.