creating and then calling methods in an AST

Jan 6, 2010 at 11:28 PM

I'm having trouble implementing recursion and the ability to call methods that are defined below where the method is called in the language I am developing.

Currently I am creating LambdaExpressions for methods, and when the methods are called I just do a Expression.Invoke(pointerToLambda).

I am essentially inlining all the method calls by doing it this way.

Is there anyway to create something like a function look up table in Expressions?

I've looked at IronRuby and IronPython and I'm not clear on how to do it.

Any suggestions, links to examples, key words or terms to search for would be much appreciated.

 

thanks much

Coordinator
Jan 7, 2010 at 2:36 AM

Do you really want to do a function lookup or do you want to write something like the C# equivalent of?

void f() {

                …

                f();

}

IronPython and IronRuby currently do lookups – but those are name based lookups based upon each languages defined semantics for resolving any name.  In other words none of its going to happen a compile time.  And there’s lots of machinery related to generating code related to scopes and maintaining those scopes at runtime.

Given that you mentioned things are getting inlined I assume one potential problem for you is that Expression.Invoke(lambdaExpression) automatically inlines things.  You can easily defeat that by doing Expression.Convert(lambdaExpression, delegateType) – no extra code will be generated but the lambdas won’t get inlined.  Instead you’ll be doing an nice indirect delegate invocation which might be what you want.

But you also mention wanting to call methods defined below the method is called.  I assume the problem there is that you have an outer LambdaExpression that you want to invoke from an inner LambdaExpression, like in C#:

void f() {

                Action t = () => f();

}

This is obviously a problem because you can’t refer to f inside of f until f is created and you can’t create f until you’ve made the lambda which refers to it.  There’s no easy solution for this but there are some options.  The first option, which only partially helps, is not to use the closures the DLR gives you for free.  Instead you can do your own name binding, flow a closure object yourself, etc…  Now you can generate f() first and then generate the inner delegate.  Of course that’s a pain and doesn’t help you if you can have some nested mutual recursion C#-like  code such as:

int f(int x) {

                int g(int y) {

                                if((x + y) < 100) {

                                                return f(x + y);

                                }

                                return x+ y;

                }

                return g(x);

}

So the next option is to use LambdaExpression.CompileToMethod – it has the downside of not supporting DynamicMethods (so it’s uncollectable but in .NET 4.0 you could presumably use collectable assemblies).  Taking the last code snippet you figure out you have f and g methods.  Then you create a MethodBuilder for each one.  Then you create the trees – and for the recursive calls you use Expression.Call(methodBuilder, …) to do the recursive calls.  Finally you call LambdaExpression.CompileToMethod on each method.

From: CodeMoniker [mailto:notifications@codeplex.com]
Sent: Wednesday, January 06, 2010 4:28 PM
To: Dino Viehland
Subject: creating and then calling methods in an AST [dlr:80000]

From: CodeMoniker

I'm having trouble implementing recursion and the ability to call methods that are defined below where the method is called in the language I am developing.

Currently I am creating LambdaExpressions for methods, and when the methods are called I just do a Expression.Invoke(pointerToLambda).

I am essentially inlining all the method calls by doing it this way.

Is there anyway to create something like a function look up table in Expressions?

I've looked at IronRuby and IronPython and I'm not clear on how to do it.

Any suggestions, links to examples, key words or terms to search for would be much appreciated.

thanks much

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 8:20 AM
Edited Jan 7, 2010 at 8:21 AM

(sigh just wrote this exact reply once and my mobile internet connection swallowed it by crashing when I was going to post, rewriting it...)

First of about IronPython and IronRuby, to my (albeit limited) understanding of their sources they both implement their own dynamic scoping and closures instead of using the facilities supplied by the DLR (if I'm wrong on this someone please correct me, but this is what I've come to understand after reading the sources). I'm just in the process of moving my own language to use this form of dynamic resolution and scoping instead of the one supplied by the DLR, because it's just to limiting when you want to do stuff like dynamically named variables (who have their name decided at runtime) or implement something like eval() or pass execution contexts around between different code units.

But, for implementing a basic language to learn how the DLR works and runs, implementing your own scope handling will get you sidetracked and confused I think, so stay with the allready supplied model of the DLR for now. I'll try to outline how I implemented the variable and function scoping in my language below.

For anything but the absolute basics you will need some form of Global object that can hold references to variables, functions, etc. This is also used to allow you to define C# classes, methods and objects that you want to make available to the DLR (this is another matter, and the sympl.doc tutorial explains how to do that better then I ever could). When starting out I would recommend using the built in ExpandoObject for your globals, you can find it in the System.Dynamic namespace and it will do most of what you need, there are several reasons for implementing your own version instead, if you wanna get the gist of how to do it read the library authors documentation .doc and check the sources in the Samples/Library program to see how the example FastNBag is implemented.

Assuming you have some type of object implementing IDynamicMetaObjectProvider (for example: ExpandoObject) as your global object, the second thing you will need is some way to refer to it within your expression tree you generate, create a top level ParameterExpression for this which you compile as one of the parameters for your lambda function that holds the entire expression tree. This way you can define a new global object in C# code, set whatever properties you want on it and then pass it to the delegate that is your compiled code.

The third thing you will need is three binders: SetMemberBinder, GetMemberBinder and InvokeBinder. You can just extend the base classes for each (which you can find in System.Dynamic) and implement that abstract base class, leave the default "throw new NotImplementedException" implementation in each method you get generated for now. For learning more on what the binders do exactly, and how to custmize them, refer to the sympl.doc for an example implementation and to site-binders-dynobj-interop.doc for a deeper explanation of the concepts.

Assuming you have the above objects setup, what to do when you need to emit an assignment expression (in the global context, not dealing with local scopes here) like this:

var foo = <expr>

Instead of emitting a new VariableExpression as the left side and assigning it the result of the right side expression, you should emit code that causes a dynamic set operation in our global object instead. 
(Et is an alias for System.Linq.Expressions.Expression) 

                    var varName = "foo";
	            var tmp = Et.Parameter(typeof(object), "__tmp.Assign__");
	            var rhs = BuildRightExpression(right); // <- imaginary variable representing the right expression

                    return Et.Block(
                        new[] { tmp },
                        Et.Assign(tmp, rhs),
                        Et.Dynamic(
                            new Binders.SetMemberBinder(varName),
                            typeof(object), 
globalsExpr,
tmp ) );

globalsExpr here refers to the parameter expression representing the global variable in your code, I also make sure of a temporary variable that holds the value that is the evaluate right expression. The code above will cause a dynamic set member invocation on the value of the globalsExpr during runtime, which in effect is dynamic binding. If you then, later in your source code, pass over a reference that needs to get the value of our global foo variable, you have to emit a dynamic GetMember operation, that looks something like this:

                return Et.Dynamic(
                    new Binders.GetMemberBinder(name),
                    typeof(object), 
globalsExpr );

This will emit a dynamic GetMember operation on the value represented by the globalsExpr during runtime, when you want to invoke a function contained in the dynamic global object, it would look something like this (assuming the global variable foo holds a delegate or lambda expression that takes one int value as parameter)

                return Et.Invoke(
                    Et.Dynamic(
                        new Binders.GetMemberBinder(name),
                        typeof(object), 
                        globalsExpr
                    ),
                    Et.Constant(1)
                );

This will cause a dynamic get operation on the value represented b the globalsExpr, which then is invoked with one parameter of value int(1). This was just a simple explanation of how just the emitting of the expressions for dynamic Set/Get/Invoke operations would look like, there are a lot more to it and my best advice is to follow the sympl.doc and library-authors-introduction.doc tutorial from start to finish, they explain a lot of the basic concepts like DynamicMetaObject, IDynamicMetaObjectProvider and DynamicMetaObjectBinder - how they work together and what you can accomplish with them.