Calling LambdaExpression recursively

Jul 10, 2009 at 4:56 AM

I am new to DLR. I would like to know how to construct a lambdaexpression for recursive call. The C# equivalent of the function looks like:

        public static int factorial(int n)
        {
            if (n > 1)
                return n * factorial(n - 1);
            else
                return 1;
        }

The following is the code that I attempted to construct dlr tree version:

            ParameterExpression input = Expression.Parameter(typeof(int));

            var test = Expression.GreaterThan(input, Expression.Constant(1));
            var exit = Expression.Label(typeof(int));

            Expression body = null;
            var lamda = Expression.Lambda>(body, input);

            body = Expression.IfThenElse(
                test, 
                Expression.Return(exit,
                    Expression.Multiply(input, 
                        Expression.Invoke(lamda, Expression.Subtract(input, Expression.Constant(1))))),
                Expression.Return(exit, Expression.Constant(1)));

Now the trouble is if I create body first, I have to pass an unassigned lamda variable; if I create the lamda first, I am using an unassigned body. So I am in a chicken and egg scenario. How do I get out of this? Thank you.
Jul 10, 2009 at 7:24 AM
Edited Jul 10, 2009 at 7:59 AM

You're just not thinking 4th dimensionally!

Quoting Back to the Future is especially sweet when it's actually topical.

 

This is untested, but it should work:


let input = Expression.Parameter(typeof(int))

let test = Expression.GreaterThan(input, Expression.Constant(1))
let exit = Expression.Label(typeof(int))


let recursive_lambda = Expression.Parameter()

let body = Expression.IfThenElse(
                test, 
                Expression.Return(exit,
                    Expression.Multiply(input, 
                        Expression.Invoke(recursive_lambda, Expression.Subtract(input, Expression.Constant(1))))),
                Expression.Return(exit, Expression.Constant(1)))


let lambda = Expression.Lambda>(body, input)

let returnValue = Expression.Block([|recursive_lambda|],                                                             
                                                   Expression.Assign(recursive_lambda, 
                                                    lambda),
recursive_lambda)

returnValue

 

Since the ParameterExpression recursive_lambda is set to be the function in question during compilation(but before that function is invoked), it'll work.

 

Let me know if I've suggested something that doesn't work.

 

Mike Kohout

 

Coordinator
Jul 10, 2009 at 4:06 PM

The other way to accomplish this is by using LambdaExpression.CompileToMethod.  What you need to do is first create a MethodBuilder and then build your AST.  In the AST you simply build a node which calls the MethodBuilder (which is a subclass of MethodInfo).  Then you do CompileToMethod on the LambdaExpression and you have a recursive function.

From: mwkohout [mailto:notifications@codeplex.com]
Sent: Friday, July 10, 2009 12:25 AM
To: Dino Viehland
Subject: Re: Calling LambdaExpression recursively [dlr:62080]

From: mwkohout

It's not often that I get to quote Back to the Future, but you're just not thinking 4th dimensionally!

This is untested, but it should work:

let lam = Expression.Parameter()
 
let input = Expression.Parameter(typeof(int))
 
let test = Expression.GreaterThan(input, Expression.Constant(1))
let exit = Expression.Label(typeof(int))
 
 
let recursive_lambda = Expression.Parameter()
 
let body = Expression.IfThenElse(
                test, 
                Expression.Return(exit,
                    Expression.Multiply(input, 
                        Expression.Invoke(recursive_lambda, Expression.Subtract(input, Expression.Constant(1))))),
                Expression.Return(exit, Expression.Constant(1)))
 
 
let lamda = Expression.Lambda>(body, input)
 
let returnValue = Expression.Block([|recursive_lambda|],                                                             
                                                   Expression.Assign(recursive_lambda, 
                                                    lambda),
recursive_lambda)
 
returnValue

Since the ParameterExpression recursive_lambda is set to be the function in question during compilation(but before that function is invoked), it'll work.

Let me know if I've suggested something that doesn't work.

Mike Kohout

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

Coordinator
Jul 10, 2009 at 6:02 PM

Sorry, I’m told this doesn’t actually work L

From: dinov [mailto:notifications@codeplex.com]
Sent: Friday, July 10, 2009 9:07 AM
To: Dino Viehland
Subject: Re: Calling LambdaExpression recursively [dlr:62080]

From: dinov

The other way to accomplish this is by using LambdaExpression.CompileToMethod. What you need to do is first create a MethodBuilder and then build your AST. In the AST you simply build a node which calls the MethodBuilder (which is a subclass of MethodInfo). Then you do CompileToMethod on the LambdaExpression and you have a recursive function.

From: mwkohout [mailto:notifications@codeplex.com]
Sent: Friday, July 10, 2009 12:25 AM
To: Dino Viehland
Subject: Re: Calling LambdaExpression recursively [dlr:62080]

From: mwkohout

It's not often that I get to quote Back to the Future, but you're just not thinking 4th dimensionally!

This is untested, but it should work:

let lam = Expression.Parameter()
 
let input = Expression.Parameter(typeof(int))
 
let test = Expression.GreaterThan(input, Expression.Constant(1))
let exit = Expression.Label(typeof(int))
 
 
let recursive_lambda = Expression.Parameter()
 
let body = Expression.IfThenElse(
                test, 
                Expression.Return(exit,
                    Expression.Multiply(input, 
                        Expression.Invoke(recursive_lambda, Expression.Subtract(input, Expression.Constant(1))))),
                Expression.Return(exit, Expression.Constant(1)))
 
 
let lamda = Expression.Lambda>(body, input)
 
let returnValue = Expression.Block([|recursive_lambda|],                                                             
                                                   Expression.Assign(recursive_lambda, 
                                                    lambda),
recursive_lambda)
 
returnValue

Since the ParameterExpression recursive_lambda is set to be the function in question during compilation(but before that function is invoked), it'll work.

Let me know if I've suggested something that doesn't work.

Mike Kohout

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

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

Coordinator
Jul 10, 2009 at 6:06 PM

Here’s an example of how to do a recursive lambda ... supplied by the dev who probably rubbed Dino’s nose in his previous response :-) ... maybe you could use something like this pattern

using System;

using System.Linq.Expressions;

using System.Runtime.CompilerServices;

namespace LambdaRecursion

{

class Program

{

static void Main(string[] args)

{

// fact = (x) => x <= 1 ? 1 : x*fact(x-1)

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

var factorial = new StrongBox<Func<int, int>>();

var lambda = Expression.Lambda<Func<int, int>>(

Expression.Condition(

Expression.LessThanOrEqual(x, Expression.Constant(1)),

Expression.Constant(1),

Expression.Multiply(

x,

Expression.Invoke(

Expression.Field(Expression.Constant(factorial), "Value"),

Expression.Subtract(x, Expression.Constant(1))))),

x);

factorial.Value = lambda.Compile();

Console.WriteLine(factorial.Value(5));

}

}

}

Bill

From: dinov [mailto:notifications@codeplex.com]
Sent: Friday, July 10, 2009 11:03 AM
To: Bill Chiles
Subject: Re: Calling LambdaExpression recursively [dlr:62080]

From: dinov

Sorry, I’m told this doesn’t actually work L

From: dinov [mailto:notifications@codeplex.com]
Sent: Friday, July 10, 2009 9:07 AM
To: Dino Viehland
Subject: Re: Calling LambdaExpression recursively [dlr:62080]

From: dinov

The other way to accomplish this is by using LambdaExpression.CompileToMethod. What you need to do is first create a MethodBuilder and then build your AST. In the AST you simply build a node which calls the MethodBuilder (which is a subclass of MethodInfo). Then you do CompileToMethod on the LambdaExpression and you have a recursive function.

From: mwkohout [mailto:notifications@codeplex.com]
Sent: Friday, July 10, 2009 12:25 AM
To: Dino Viehland
Subject: Re: Calling LambdaExpression recursively [dlr:62080]

From: mwkohout

It's not often that I get to quote Back to the Future, but you're just not thinking 4th dimensionally!

This is untested, but it should work:

let lam = Expression.Parameter()
 
let input = Expression.Parameter(typeof(int))
 
let test = Expression.GreaterThan(input, Expression.Constant(1))
let exit = Expression.Label(typeof(int))
 
 
let recursive_lambda = Expression.Parameter()
 
let body = Expression.IfThenElse(
                test, 
                Expression.Return(exit,
                    Expression.Multiply(input, 
                        Expression.Invoke(recursive_lambda, Expression.Subtract(input, Expression.Constant(1))))),
                Expression.Return(exit, Expression.Constant(1)))
 
 
let lamda = Expression.Lambda>(body, input)
 
let returnValue = Expression.Block([|recursive_lambda|],                                                             
                                                   Expression.Assign(recursive_lambda, 
                                                    lambda),
recursive_lambda)
 
returnValue

Since the ParameterExpression recursive_lambda is set to be the function in question during compilation(but before that function is invoked), it'll work.

Let me know if I've suggested something that doesn't work.

Mike Kohout

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

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

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

Jul 10, 2009 at 8:18 PM

billchi's code worked. Thanks a lot. So the main idea as I see is to use a place holder (StrongBox in this case) and invoke on the place holder that would evaludate to delegate a runtime. We then compile the LamdaExpression and store the compiled delegate in the place holder.

Now suppose I have a large number of functions than can potentially call each other. I can compile them one at a time and store them in a dictionary. Is this the most efficient way?

Coordinator
Jul 10, 2009 at 8:36 PM

I don’t get the entire problem, but if a dictionary looks right to you, then I’d consider using one of our ExpandObjects to hold the functions since you can then emit code to “dot” into the ExpandoObject to invoke the functions.  This should produce rules that our call site caching (as well as member look up on Expando being highly tuned) would make faster than always indirecting through a standard dictionary lookup.

Bill

From: dotneteer [mailto:notifications@codeplex.com]
Sent: Friday, July 10, 2009 1:18 PM
To: Bill Chiles
Subject: Re: Calling LambdaExpression recursively [dlr:62080]

From: dotneteer

billchi's code worked. Thanks a lot. So the main idea as I see is to use a place holder (StrongBox in this case) and invoke on the place holder that would evaludate to delegate a runtime. We then compile the LamdaExpression and store the compiled delegate in the place holder.

Now suppose I have a large number of functions than can potentially call each other. I can compile them one at a time and store them in a dictionary. Is this the most efficient way?

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

Jul 15, 2009 at 9:22 PM

I tried mwkohout's method and it worked too. It took me a while to figure out the C# equivalent :)

The difference to billchi's code is that I do not need to explicitely compile the lamda expression. Instead, I only need to assign it to a parameter expression.

I then just need to compile the BlockExpression that contains both my script code and function definition once. This would be helpful if I need to save the compiled script as a single assembly.

            ParameterExpression input = Expression.Parameter(typeof(int));

            var test = Expression.GreaterThan(input, Expression.Constant(1));

            var factorial = Expression.Parameter(typeof(Func));

            Expression body = Expression.Block(
                    Expression.Condition(
                        test,
                        Expression.Multiply(
                            input,
                            Expression.Invoke(
                                factorial,
                                Expression.Subtract(
                                    input,
                                    Expression.Constant(1)))),
                        Expression.Constant(1))
                    );

            var fact = Expression.Lambda>(body, input);

            var block = Expression.Block(
                            new ParameterExpression[] { factorial },
                            Expression.Assign(factorial, fact),
                            Expression.Invoke(factorial, Expression.Constant(5))
                                );

Then I just need to do Expression.Lambda(block).Compile().Invoke();