Nested mutual recursion

Jan 7, 2010 at 10:21 AM
Edited Jan 7, 2010 at 1:31 PM

It's funny how things coincide, I've been working on implementing nested mutual recursive functions for my language I've built on top of the DLR - and dinov posted something about that in another thread (second reply here: http://dlr.codeplex.com/Thread/View.aspx?ThreadId=80000), which put me more on the right track then I was before at least.

However I'm still struggling to put all the pieces together, take this example code below (copied from dinovs post in the other thread)

int f(int x) {

	int g(int y) {

		if((x + y) < 100) {
			return f(x + y);
		}

		return x + y;

	}

	return g(x);
}

If I understood it correctly I have to detect recursive calls and lift out the functions into MethodBuilders? It would go something like this:

  1. Detect that f and g are mutually recursive
  2. Create a method builder each for f and g and put them in the local scope
  3. Build the g function and where it calls f(x + y) insert the f method builder
  4. Build the f function and where it calls g(x) insert the g method builder
  5. Call CompileToMethod on g, then call CompileToMethod on

Then when I need to refer to the f function anywhere in the code I will use the f method builder inserted in it's enclosing scope instead of the expression tree I generated for the lambda that is its body? Again I'm far from sure I got this right, and I still can't make it work properly in code (after reading the IronPython and IronRuby sources it got a bit clearer, but they are both huge projects and are very hard to use for grasping specific concepts).

If it is possible to explain how to go about this, preferably in code, that would be most appreciated. Also, are there any other ways to go about to accomplish this with the DLR?

Jan 7, 2010 at 10:56 AM

I'd figure I would post an update, this is how far I've come in my exploration of mutually recursive functions, following dinovs post in another thread I went down the MethodBuilder path:

    using System;
    using System.Reflection;
    using System.Reflection.Emit;

    using Et = System.Linq.Expressions.Expression;

    class Program
    {
        static void Main(string[] args)
        {
            var currentDomain = AppDomain.CurrentDomain;
            var asmName = new AssemblyName();
            asmName.Name = "RecursionTest";

            var asmBuilder =
                currentDomain.DefineDynamicAssembly(
                    asmName, 
                    AssemblyBuilderAccess.RunAndSave
                );

            var moduleBuilder = 
                asmBuilder.DefineDynamicModule(
                    "RecursionTest", 
                    "RecursionTest.dll"
                );

            var typeBuilder =
                moduleBuilder.DefineType(
                    "RecursionTestType",
                    TypeAttributes.Public
                );

            var f = typeBuilder.DefineMethod("f", MethodAttributes.Public);
            var g = typeBuilder.DefineMethod("g", MethodAttributes.Public);

            var x = Et.Parameter(typeof(int), "x");
            var y = Et.Parameter(typeof(int), "y");

            var writeLine = typeof(System.Console).GetMethod("WriteLine", new[] { typeof(object) });

            var fLambda = Et.Lambda(
                Et.Block(
                    Et.Call(g, x)
                ),
                x
            );

            fLambda.CompileToMethod(f);

            var gLambda = Et.Lambda(
                Et.Block(
                    Et.IfThenElse(
                        Et.LessThan(Et.Add(x, y), Et.Constant(100)),
                        Et.Call(f, Et.Add(x, y)),
                        Et.Call(writeLine, Et.Add(x, y))
                    )
                ),
                y
            );

            gLambda.CompileToMethod(g);

            var codeUnit = Et.Lambda(
                Et.Call(f, Et.Constant(10))
            );

            codeUnit.Compile().DynamicInvoke();
        }
    }

The above code is trying to compile this:

void f(int x) {

	void g(int y) {

		if((x + y) < 100) {
			f(x + y);

		} else {
			System.Console.WriteLine(x + y);

		}

	}

	g(x);
}

(I removed the returns in the function from the first post because it got to messy doing all the return labels by hand)

However I keep getting an NotSupportedException with the message 'Specified method is not supported.' exception thrown here:

 

            var fLambda = Et.Lambda(
                Et.Block(
                    Et.Call(g, x)
                ),
                x
            );

And honestly, I'm at a complete loss of what to do now.

Jan 7, 2010 at 4:06 PM
Edited Jan 7, 2010 at 4:33 PM

This is starting to look more and more like a monologue, but this is my third try to get this to work. Which actually does work, but I'm not sure of how efficient this is (this is of course only an example implementation, and I've not really cared for anything other then to make it work)

The general idea is this:

  1. Analyze the source code and extract all functions and compile them into lambdas in a function lookup table
  2. With every function call you create a new scope, push the arguments on it and then call the function with that scope
  3. You access the variables within the function body through the passed scope

The code used above, looking like this:

void f(int x) {

	void g(int y) {

		if((x + y) < 100) {
			f(x + y);

		} else {
			System.Console.WriteLine(x + y);

		}

	}

	g(x);
}

Would get analyzed into this:

void g(Scope scp) {

	if((scp["x"] + scp["y"]) < 100) {
		f_scope = scp.enter();
		f_scope.push("x", scp["x"] + scp["y"]);
		scp["f"](f_scope);

	} else {
		System.Console.WriteLine(scp["x"] + scp["y"]);

	}

}

void f(Scope scp) {
	g_scope = scp.enter();
	g_scope.push("y", scp["x"]);
	scp["g"](g_scope);
}

This of course involves a lot of dynamic binding (for variable access), etc. Is this (albeit simplified now) how IronPython and IronRuby do it? The C# code (which just naively implements this top to bottom, nothing else) follows here:

    using Et = System.Linq.Expressions.Expression;
    using Meta = System.Dynamic.DynamicMetaObject;
    using Restrict = System.Dynamic.BindingRestrictions;
    using AstUtils = Microsoft.Scripting.Ast.Utils;

    using System;
    using System.Dynamic;
    using System.Collections.Generic;

    class Scope : IDynamicMetaObjectProvider
    {
        readonly Scope _parent;

        readonly Dictionary<string, object> _values = 
             new Dictionary<string, object>();

        public Scope(Scope parent)
        {
            _parent = parent;
        }

        public object Set(string key, object value)
        {
            return _values[key] = value;
        }

        public object Get(string key)
        {
            if (_values.ContainsKey(key))
                return _values[key];

            if (_parent != null)
                return _parent.Get(key);

            throw new MissingFieldException("No variable named " + key + " exists");
        }

        public Scope Enter()
        {
            return new Scope(this);
        }

        #region IDynamicMetaObjectProvider Members

        Meta IDynamicMetaObjectProvider.GetMetaObject(Et parameter)
        {
            return new MetaScope(parameter, this);
        }

        #endregion
    }

    class MetaScope : DynamicMetaObject
    {
        public MetaScope(Et parameter, object value)
            : base(parameter, Restrict.Empty, value)
        {

        }

        public override Meta BindSetMember(SetMemberBinder binder, Meta value)
        {
            var keyExpr = Et.Constant(binder.Name);
            var valueExpr = Et.Convert(value.Expression, typeof(object));

            var target = Et.Call(
                Et.Convert(this.Expression, typeof(Scope)),
                typeof(Scope).GetMethod("Set"),
                keyExpr,
                valueExpr
            );

            var restrictions =
                Restrict.GetTypeRestriction(
                    this.Expression,
                    this.LimitType
                );

            return new Meta(target, restrictions);
        }

        public override Meta BindGetMember(GetMemberBinder binder)
        {
            var callExpr =
                Et.Call(
                    Et.Convert(this.Expression, typeof(Scope)),
                    typeof(Scope).GetMethod("Get"),
                    Et.Constant(binder.Name)
                );

            var restrictions =
                Restrict.GetTypeRestriction(
                    this.Expression,
                    this.LimitType
                );

            return new Meta(callExpr, restrictions);
        }
    }

    class SetBinder : SetMemberBinder
    {
        public SetBinder(string name)
            : base(name, false)
        {

        }

        public override Meta FallbackSetMember(Meta target, Meta value, Meta errorSuggestion)
        {
            throw new NotImplementedException();
        }
    }

    class GetBinder : GetMemberBinder
    {
        public GetBinder(string name)
            : base(name, false)
        {

        }

        public override Meta FallbackGetMember(Meta target, Meta errorSuggestion)
        {
            throw new NotImplementedException();
        }
    }

    class Program
    {
        static Et Scope(Et scope, string name)
        {
            return Et.Dynamic(
                new GetBinder(name),
                typeof(object),
                scope
            );
        }

        static Et Scope<T>(Et scope, string name)
        {
            return Et.Convert(Et.Dynamic(
                new GetBinder(name),
                typeof(object),
                scope
            ), typeof(T));
        }

        static Et Scope(Et scope, string name, Et value)
        {
            return Et.Dynamic(
                new SetBinder(name),
                typeof(object),
                scope,
                value
            );
        }

        static Et CallHelper(Et target, Et scope)
        {
            var invoke = typeof(Delegate).GetMethod("DynamicInvoke");

            return AstUtils.SimpleCallHelper(
                Et.Convert(target, typeof(Delegate)),
                invoke,
                Et.NewArrayInit(typeof(object), scope)
            );
        }

        static void Main(string[] args)
        {
            var enter = typeof(Scope).GetMethod("Enter");
            var writeLine = typeof(System.Console).GetMethod("WriteLine", new[] { typeof(object) });

            var gScope = Et.Parameter(typeof(Scope), "#g");
            var callTmpScope = Et.Parameter(typeof(Scope), "#tmp");
            var gLambda = Et.Lambda(
                Et.Block(
                    Et.IfThenElse(
                        Et.LessThan(
                            Et.Add(Scope<int>(gScope, "x"), Scope<int>(gScope, "y")),
                            Et.Constant(100)
                        ),
                        Et.Block(
                            new[] { callTmpScope },
                            Et.Assign(callTmpScope, Et.Call(gScope, enter)),
                            Scope(callTmpScope, "x", Et.Add(Scope<int>(gScope, "x"), Scope<int>(gScope, "y"))),
                            CallHelper(Scope(gScope, "f"), callTmpScope)
                        ),
                        Et.Call(writeLine, Et.Convert(Et.Add(Scope<int>(gScope, "x"), Scope<int>(gScope, "y")), typeof(object)))
                    )
                ),
                gScope
            );

            var fScope = Et.Parameter(typeof(Scope), "#f");
            var tmpScope = Et.Parameter(typeof(Scope), "#tmp");
            var fLambda = Et.Lambda(
                Et.Block(
                    new[] { tmpScope },
                    Et.Assign(tmpScope, Et.Call(fScope, enter)),
                    Scope(tmpScope, "y", Scope(fScope, "x")),
                    CallHelper(Scope(fScope, "g"), tmpScope)
                ),
                fScope
            );

            var gCompiled = gLambda.Compile();
            var fCompiled = fLambda.Compile();

            var scope = new Scope(null);

            scope.Set("g", gCompiled);
            scope.Set("f", fCompiled);
            scope.Set("x", 20);

            fCompiled.DynamicInvoke(scope);
        }
Jan 7, 2010 at 5:49 PM

"This is starting to look more and more like a monologue"

Please keep up your monologue. Your posts are very helpful. I'm still trying to sort out all of your posts. We're working on something similar, but your stuff is a bit more advanced.

I'd contribute, but unfortunately, I have nothing to offer but my own confusion.

Jan 7, 2010 at 8:54 PM

> However I keep getting an NotSupportedException with the message 'Specified method is not supported.' exception thrown here:

      var g = typeBuilder.DefineMethod("g", MethodAttributes.Public);
        <snip>

            var fLambda = Et.Lambda(

                Et.Block(
                    Et.Call(g, x)
                ),
                x
            );

> And honestly, I'm at a complete loss of what to do now.

I’m guessing the problem is with “g”. In a nutshell expression tree’s can’t call MethodBuilders. You have to create the type (TypeBuilder.CreateType) and then fetch the real MethodInfo off from it. The issue is that the MethodBuilder doesn’t implement enough of reflection for expression trees to compile it, so it’s throwing NotSupported somewhere. It’s kind of a fake MethodInfo.

There are a few ways around this problem, essentially you need some object to represent the functions as first class objects. That breaks the circularity and allows mutual recursion to work. The easiest way to do that is to store them in variables that have a delegate type. Then you can invoke the delegate using Et.Invoke.

- John

Coordinator
Jan 7, 2010 at 9:12 PM

Sorry – apparently I lead you down a useless path, I thought we had made this work but apparently not L

From: jmesserly [mailto:notifications@codeplex.com]
Sent: Thursday, January 07, 2010 1:55 PM
To: Dino Viehland
Subject: Re: Nested mutual recursion [dlr:80047]

From: jmesserly

> However I keep getting an NotSupportedException with the message 'Specified method is not supported.' exception thrown here:

      var g = typeBuilder.DefineMethod("g", MethodAttributes.Public);
        <snip>

var fLambda = Et.Lambda(

                Et.Block(
                    Et.Call(g, x)
                ),
                x
            );

> And honestly, I'm at a complete loss of what to do now.

I’m guessing the problem is with “g”. In a nutshell expression tree’s can’t call MethodBuilders. You have to create the type (TypeBuilder.CreateType) and then fetch the real MethodInfo off from it. The issue is that the MethodBuilder doesn’t implement enough of reflection for expression trees to compile it, so it’s throwing NotSupported somewhere. It’s kind of a fake MethodInfo.

There are a few ways around this problem, essentially you need some object to represent the functions as first class objects. That breaks the circularity and allows mutual recursion to work. The easiest way to do that is to store them in variables that have a delegate type. Then you can invoke the delegate using Et.Invoke.

- John

Read the full discussion online.

To add a post to this discussion, reply to this email (dlr@discussions.codeplex.com)

To start a new discussion for this project, email dlr@discussions.codeplex.com

You are receiving this email because you subscribed to this discussion on CodePlex. You can unsubscribe or change your settings on codePlex.com.

Please note: Images and attachments will be removed from emails. Any posts to this discussion will also be available online at codeplex.com

Jan 7, 2010 at 10:18 PM
Edited Jan 7, 2010 at 10:19 PM

CodeMoniker: Thanks for your kind words, most appreciated :)

dinov: You've got nothing to be sorry about, while it wasn't the correct path it taught me a whole lot about the DLR and I actually got mutual recursion + dynamic scopes working just now because your messages made me look in the right places in IronPython and search for the correct stuff on google.

jmesserly: I got an implementation working just now, and it uses a dynamic function table (sort of) like the one I handcrafted in my third post, is this a good solution? Basically I have a Function object which keeps the parameter lists and the delegate to call for each function, they are inserted into a lookup table (where they just get a random ID) and then are mapped, dynamically, into the current scope. The scopes are handled almost exactly the way I explained in my third post, a new frame being pushed on the calling stack for each function invocation, and then the parameters are pushed onto that stack frame instead of supplied as "real" arguments to the function, and then the frame is sent as a parameter into the function called, which uses it to resolve its arguments.

Using the, now well tried, test code from dinovs original post:

void f(int x) {

	void g(int y) {

		if((x + y) < 100) {
			f(x + y);

		} else {
			System.Console.WriteLine(x + y);

		}

	}

	g(x);
}

Would look like this:

// global context

funcs = new functable();

funcs[0] = fun (funcs, frame) {
	g = closure(frame, 1);
	g_frame = frame.new()
	g_frame.push(y, frame.x)
	g(funcs, g_frame);
};

funcs[1] = fun (funcs, frame) {
	if((frame.x + frame.y) < 100) {
		f_frame = frame.new();
		f_frame.push(x, frame.x + frame.y);
		funcs[0](funcs, f_frame); // no need for closure here
	} else {
		System.Console.WriteLine(x + y);
	}
};

// code added for calling f() the first time to start it
// which isn't in the example code
global_frame = new frame();
global_frame.push(x, 10);
funcs[0](funcs, global_frame);

Two questions here:

  1. Is this a good way to accomplish this? If not, how should it be done (at a high level view) ?
  2. Is this how IronPython/IronRuby does it? If not, how do they do it (at a high level view) ?

Most appreciated for everyones patience with my newbie questions, the DLR is a complex (but awesome) beast :)

Coordinator
Jan 8, 2010 at 3:14 AM

What you’re doing looks pretty good.  If you want to start optimizing this you might want to use a MutableTuple or something similar for your closures so that you don’t need to do array accesses.  Or if you’re doing ahead of time compilation you can even generate optimized closure classes like C# does.

Here’s how IronPython does this.  For us f is a global – and needs to be looked up each time (someone could mutate the module behind our back).  IronPython has many different ways to do this but the fastest is to store a PythonGlobal objects in a static field for each global.  We also have ways where these are stored in an array somewhere and closed over by the outer function or where it turns into a dictionary lookup. 

g is a local inside of f and isn’t closed over  so we just treat it as any other variable typed to object.

IronPython also maintains its own closures – this is largely because Python exposes the closure objects off of function objects and they can be inspected by programs.  Python also has a locals() feature which returns a python dictionary object and lets you access the locals – so we also want to put the closure cells into a dictionary which provides access to the closures.  So when we create a closure we create our CodeContext object which is the one thing which flows through the system.  It stores a dictionary which has a special storage class which knows how to access the tuples.

In IronPython this ends up looking something like:

// the $func object is provided by MetaPythonFunction including it in the result of an Invoke binding

object f(PythonFunction $func, object x) {           // no strong typing

                // define the new function object

                $x = new ClosureCell(x);

                CodeContext $localContext = new CodeContext(new PythonDictionary(new RuntimeVariablesDictionaryStorage(new MutableTuple<ClosureCell >($x))));

                object g = new PythonFunction($localContext, $functionCode, “__main__”, null);           // null is defaults

                // and invoke it

                _invokeSite.Target.Invoke(_invokeSite, g, $x.cell_contents);

                return null;

}

object g(PythonFunction $func, object y) {

                MutableTuple<ClosureCell > closure = PythonOps.GetClosureTupleFromFunction($func);           // pulls the tuple in the RuntimeVariablesDictionaryStorage back out

                if(_ltSite.Target.Invoke(_addSite.Target.Invoke(_addSite, closure.Item001, $y), 100)) {

                                _callSite.Target.Invoke(_callSite, closure.Item000, _addSite2.Target.Invoke(_addSite2, closure.Item001, $global_y.CurrentValue));           // global lookup here using the static field form

                }else {

                                // lots of dynamic get members

                }

                return null;

}

From: fholm [mailto:notifications@codeplex.com]
Sent: Thursday, January 07, 2010 3:18 PM
To: Dino Viehland
Subject: Re: Nested mutual recursion [dlr:80047]

From: fholm

CodeMoniker: Thanks for your kind words, most appreciated :)

dinov: You've got nothing to be sorry about, while it wasn't the correct path it taught me a whole lot about the DLR and I actually got mutual recursion + dynamic scopes working just now because your messages made me look in the right places in IronPython and search for the correct stuff on google.

jmesserly: I got an implementation working just now, and it uses a dynamic function table (sort of) like the one I handcrafted in my third post, is this a good solution? Basically I have a Function object which keeps the parameter lists and the delegate to call for each function, they are inserted into a lookup table (where they just get a random ID) and then are mapped, dynamically, into the current scope. The scopes are handled almost exactly the way I explained in my third post, a new frame being pushed on the calling stack for each function invocation, and then the parameters are pushed onto that stack frame instead of supplied as "real" arguments to the function, and then the frame is sent as a parameter into the function called, which uses it to resolve its arguments.

Using the, now well tried, test code from dinovs original post:

void f(int x) {
 
       void g(int y) {
 
              if((x + y) < 100) {
                      f(x + y);
 
              } else {
                      System.Console.WriteLine(x + y);
 
              }
 
       }
 
       g(x);
}

Would look like this:

// global context
 
funcs = new functable();
 
funcs[0] = fun (funcs, frame) {
       g = closure(frame, 1);
       g_frame = frame.new()
       g_frame.push(y, frame.x)
       g(funcs, g_frame);
};
 
funcs[1] = fun (funcs, frame) {
       if((frame.x + frame.y) < 100) {
              f_frame = frame.new();
              f_frame.push(x, frame.x + frame.y);
              funcs[0](funcs, f_frame); // no need for closure here
       } else {
              System.Console.WriteLine(x + y);
       }
};
 
// code added for calling f() the first time to start it
// which isn't in the example code
global_frame = new frame();
global_frame.push(x, 10);
funcs[0](funcs, global_frame);

Two questions here:

1. Is this a good way to accomplish this? If not, how should it be done (at a high level view) ?

2. Is this how IronPython/IronRuby does it? If not, how do they do it (at a high level view) ?

Most appreciated for everyones patience with my newbie questions, the DLR is a complex (but awesome) beast :)

Read the full discussion online.

To add a post to this discussion, reply to this email (dlr@discussions.codeplex.com)

To start a new discussion for this project, email dlr@discussions.codeplex.com

You are receiving this email because you subscribed to this discussion on CodePlex. You can unsubscribe or change your settings on codePlex.com.

Please note: Images and attachments will be removed from emails. Any posts to this discussion will also be available online at codeplex.com

Jan 8, 2010 at 7:34 AM

dinov: wow! That was exactly what I was looking for, confirmation that I was on the right track and a bit of insight in how IronPython does it, thanks so much!