
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 8:24 AM
Edited Jul 10, 2009 at 8: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



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



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



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(x1)
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



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?



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?



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();

