Compiling nested mutually recursive function

Question

I'm creating a toy dynamic language (aching towards javascript) and while my implementation is on top of the DLR, I figured the solution to this problem would be pretty language/platform agnostic.

I have no problem with compiling recursive functions, or mutually recursive functions that exist next to each other. But compiling nested mutual recursive functions turned out to be a lot harder.

The example function I'm using to test is the following

void f(int x) {
 void g(int y) {
  if((x + y) < 100) {
   f(x + y);
  } else {
   print(x + y);
  }
 }
 g(x);
}

I figured that the solution to solving this has to be pretty general (maybe I'm wrong) and not specific to the DLR, I assume I somehow have to lift out the inner definition of g and define it before f and still keep the closure context.

Answer 1

I know you are creating a dynamic language but I think the same principles apply as a non-dynamic language - you still have a symbol table and you still have to process the source via multiple passes.

If you are creating a semantic tree before your code generation phase this is easy. The call to the function points to the object (node) which will contain the semantic definition for the function. Or it is just a node that says (semantically) call this function. Since the call to the function does not need to know what the function contains, just a pointer to the symbol table entry works fine.

If you are doing optimization (tail end recursion?) then you need to perform two passes before you can analyze it for this type of optimization. This is normal for all compilers I've seen as this phase happens after the semantic/lexical analysis.

I guess the diagram in this article is ok in showing what I'm talking about (however it has the extra bit of two different input languages.)

Answer 2

Closures are usually represented as combining function pointers and a list of arguments. The first step is, indeed to lift all nested functions to global scope, with any bound variables from their environment as parameters. This would be the equivalent of:

void _f(int x) 
{ 
  closure g = closure(_g,x);       
  call(g,x);  
}

void _g(int x, int y) 
{
  ...;
}

Once you have the 'closure' and 'call' primitives, it works. In a static language, closure() would only keep the relevant variables. In a dynamic language, closure() has to keep the entire context stack available in case the function needs it.

Answer 3

What you are trying to accomplish is an y-combinator

http://blogs.msdn.com/wesdyer/archive/2007/02/02/anonymous-recursion-in-c.aspx

http://stackoverflow.com/questions/93526/what-is-a-y-combinator