3

TL;DR

How can I build up the expression using an array of coefficients and turn it into a Func<int, double>? Is there a better way than expression trees?

I have an immutable Sequence type that is constructed using a Func<int, double> formula that is used to generate the term An for a sequence A. I started building a helper class to construct common math formulas with some simple parameters:

public static Sequence CreateLinearSequence (double m, double b)
{ return new Sequence (n => m * n + b); }

I built standard methods for constant sequences, logarithms, and simple polynomials (linear, quadratic, cubic, and quartic) but I want to extend it to support an arbitrary number of terms using the params keyword.

Here's the method I have:

 public static Sequence CreatePolynomialSequence (params double[] coeff)
 {
     Expression<Func<int, double>> e = x => 0;
     double pow = 0;

     for (int i = coeff.Length - 1; i >= 0; i--)
     {
         double c = coeff[i];
         var p = Expression.Parameter (typeof (int), "x");
         e = Expression.Lambda<Func<int, double>> (
             Expression.Add (
                 e, 
                 (Expression<Func<int, double>>)(x => c * Math.Pow (x, pow))
             ), 
             p);
         pow++; 
     }
     return new Sequence (e.Compile ());
 }

It might be obvious to you guys what I'm doing wrong; I messed around a bit until I got something that I felt like should work, but it doesn't.

The goal is for the Sequence to work like this for an array double[] coeff = {a,b,c,d,e,f,g,h}

x => h + gx + fx^2 + ex^3 + dx^4 + cx^5 + bx^6 + ax^7 using the appropriate Math.Pow(x, exponent) calls.

Running 

var s2 = SequenceHelper.CreatePolynomialSequence (new[] { 1d, 2 });
Console.WriteLine ("s2: " + s2);

results in

Unhandled Exception: System.InvalidOperationException: The binary operator Add is not defined for the types 'System.Func2[System.Int32,System.Double]' and 'System.Func2[System.Int32,System.Double]'. at System.Linq.Expressions.Expression.GetUserDefinedBinaryOperatorOrThrow (ExpressionType binaryType, System.String name, System.Linq.Expressions.Expression left, System.Linq.Expressions.Expression right, Boolean liftToNull) [0x0004a] in /private/tmp/source-mono-mac-4.2.0-branch/bockbuild-mono-4.2.0-branch/profiles/mono-mac-xamarin/build-root/mono-4.2.1/mcs/class/dlr/Runtime/Microsoft.Scripting.Core/Ast/BinaryExpression.cs:658 at System.Linq.Expressions.Expression.Add (System.Linq.Expressions.Expression left, System.Linq.Expressions.Expression right, System.Reflection.MethodInfo method) [0x00057] in /private/tmp/source-mono-mac-4.2.0-branch/bockbuild-mono-4.2.0-branch/profiles/mono-mac-xamarin/build-root/mono-4.2.1/mcs/class/dlr/Runtime/Microsoft.Scripting.Core/Ast/BinaryExpression.cs:1409 at System.Linq.Expressions.Expression.Add (System.Linq.Expressions.Expression left, System.Linq.Expressions.Expression right) [0x00000] in /private/tmp/source-mono-mac-4.2.0-branch/bockbuild-mono-4.2.0-branch/profiles/mono-mac-xamarin/build-root/mono-4.2.1/mcs/class/dlr/Runtime/Microsoft.Scripting.Core/Ast/BinaryExpression.cs:1390 at Sequence.SequenceHelper.CreatePolynomialSequence (System.Double[] coeff) [0x00110] in /Users/Knoble/MonoProjects/Sequences/Sequence/SequenceHelper.cs:88
at Sequence.Test.Main () [0x0001f] in /Users/Knoble/MonoProjects/Sequences/Sequence/Test.cs:53 [ERROR] FATAL UNHANDLED EXCEPTION: System.InvalidOperationException: The binary operator Add is not defined for the types 'System.Func2[System.Int32,System.Double]' and 'System.Func2[System.Int32,System.Double]'. at System.Linq.Expressions.Expression.GetUserDefinedBinaryOperatorOrThrow (ExpressionType binaryType, System.String name, System.Linq.Expressions.Expression left, System.Linq.Expressions.Expression right, Boolean liftToNull) [0x0004a] in /private/tmp/source-mono-mac-4.2.0-branch/bockbuild-mono-4.2.0-branch/profiles/mono-mac-xamarin/build-root/mono-4.2.1/mcs/class/dlr/Runtime/Microsoft.Scripting.Core/Ast/BinaryExpression.cs:658 at System.Linq.Expressions.Expression.Add (System.Linq.Expressions.Expression left, System.Linq.Expressions.Expression right, System.Reflection.MethodInfo method) [0x00057] in /private/tmp/source-mono-mac-4.2.0-branch/bockbuild-mono-4.2.0-branch/profiles/mono-mac-xamarin/build-root/mono-4.2.1/mcs/class/dlr/Runtime/Microsoft.Scripting.Core/Ast/BinaryExpression.cs:1409 at System.Linq.Expressions.Expression.Add (System.Linq.Expressions.Expression left, System.Linq.Expressions.Expression right) [0x00000] in /private/tmp/source-mono-mac-4.2.0-branch/bockbuild-mono-4.2.0-branch/profiles/mono-mac-xamarin/build-root/mono-4.2.1/mcs/class/dlr/Runtime/Microsoft.Scripting.Core/Ast/BinaryExpression.cs:1390 at Sequence.SequenceHelper.CreatePolynomialSequence (System.Double[] coeff) [0x00110] in /Users/Knoble/MonoProjects/Sequences/Sequence/SequenceHelper.cs:88
at Sequence.Test.Main () [0x0001f] in /Users/Knoble/MonoProjects/Sequences/Sequence/Test.cs:53 The application was terminated by a signal: SIGHUP

D. Ben Knoble
  • 4,273
  • 1
  • 20
  • 38

4 Answers4

6

I am confused by the question and by all three answers; why are you messing about with expression trees if all you intend to do is compile them into a delegate? Just return the delegate directly!

public static Func<double, double> CreatePolynomialFunction (params double[] coeff)
{
    if (coeff == null) throw new ArgumentNullException("coeff");
    return x => 
    {
        double sum = 0.0;
        double xPower = 1;
        for (int power = 0; power < coeff.Length; power += 1)
        {
            sum += xPower * coeff[power];
            xPower *= x;
        }
        return sum;
    };
}

Done. No messing about with expression trees required.

(I note that I assumed that the nth item in the array was the nth coefficient; apparently you list your coefficients backwards in your array. This seems prone to error, but if that's what you want then it is not difficult to modify this answer to run the loop down from Length-1 to zero.)

Eric Lippert
  • 647,829
  • 179
  • 1,238
  • 2,067
  • Wow. Thanks. Didn't think it could be that simple (forgot about blocks in lambdas). – D. Ben Knoble Jan 12 '16 at 15:22
  • @EricLippert, there is one flaw in your answer currently. array is a reference type and it gets captured in lambda. so code will produce unexpected results if original array elements are changed. it can easily fixed though: `coeff = coeff.ToArray();` after null-check. here is a little demo: https://dotnetfiddle.net/IyKAqj. p.s. i built expressions in my answer because i thought *that* was a requirement, and didn't want any capture – ASh Jan 13 '16 at 07:01
  • @ASh: Indeed, arrays are collections of variables, and variables can change. It would be even better to change the array into an immutable list and close over that. – Eric Lippert Jan 13 '16 at 07:04
  • I used the one-liner `Enumerable.Range(0, coeff.Length).Sum(power => coeff[power] * Math.Pow(x, power))`, but now I'm wondering if what I'm doing is inefficient. I do have a bad habit of overusing linq.. – Flynn1179 Jun 04 '18 at 09:29
  • @Flynn1179: Efficiency is defined as value produced divided by cost. So: write the code both ways, measure the value produced by the code both ways, and measure the cost both ways, and then you can compute the efficiency. How do you define "value" and "cost" in your case? – Eric Lippert Jun 04 '18 at 13:30
3

There's three things you need to fix:

  1. Use e.Body instead of e within Add.

  2. Use the same parameter object for everything. This is a bit more tricky: The x in Expression.Parameter(typeof (int), "x");, the x in e = x => 0 and the x in x => c * Math.Pow (x, pow) are different parameters.

  3. Create a copy of pow inside the loop. Otherwise, pow is captured and the same (final) value of pow is used for all the coefficients.

In the following code example, I work around the second problem by invoking the new expression using the parameter of the inner expression. The other option would be to build x => c * Math.Pow(x, pow) by hand rather than using a C# lambda expression or to unify the parameters as explained in this question.

static void Main(string[] args)
{
    var seq = CreatePolynomialSequence(1, 2, 3);
    Console.WriteLine(seq.Invoke(1)); // yields 6 = 1 + 2 + 3
    Console.WriteLine(seq.Invoke(2)); // yields 11 = 1*4 + 2*2 + 3
}

public static Func<int, double> CreatePolynomialSequence(params double[] coeff)
{
    Expression<Func<int, double>> e = x => 0;
    double pow = 0;

    for (int i = coeff.Length - 1; i >= 0; i--)
    {
        var p = e.Parameters[0];
        double c = coeff[i];
        var _pow = pow; // avoid closing over the outer variable
        var next = (Expression<Func<int, double>>)(x => c * Math.Pow(x, _pow));
        var nextInvoked = Expression.Invoke(next, p);

        e = Expression.Lambda<Func<int, double>>(Expression.Add(e.Body, nextInvoked), p);
        pow++;
    }
    return e.Compile();
}
Community
  • 1
  • 1
Heinzi
  • 167,459
  • 57
  • 363
  • 519
  • Of all the solutions, this feels the most readable to me. Thanks!! – D. Ben Knoble Jan 12 '16 at 14:13
  • Looks like our in-house exert Eric Lippert found a better solution that makes wayyyyy more sense. – D. Ben Knoble Jan 12 '16 at 15:21
  • @BenKnoble: Ah, a classic case of [XY problem](http://meta.stackexchange.com/q/66377/138661). :-) I'll still leave my answer here, since the question explicitly asked about "how to do it with expression trees" and the answer might be useful to someone else. – Heinzi Jan 12 '16 at 16:21
  • Indeed. Thanks again for the very informative answer. – D. Ben Knoble Jan 12 '16 at 19:30
3

Building on @Heinzi answer, here is how you can have the CreatePolynomialExpression method that builds the whole expression tree manually:

public static Expression<Func<int, double>> CreatePolynomialExpression(params double[] coeff)
{
    if (coeff.Length == 0)
        return x => 0;

    double pow = 1;

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

    Expression expression = Expression.Constant(coeff[coeff.Length - 1]);

    for (int i = coeff.Length - 2; i >= 0; i--)
    {
        Expression sub_expression =
            Expression.Multiply(
                Expression.Constant(coeff[i]),
                Expression.Power(
                    Expression.Convert(x_param, typeof(double)),
                    Expression.Constant(pow)));

        expression = Expression.Add(expression , sub_expression);

        pow++;
    }

    return Expression.Lambda<Func<int, double>>(expression, x_param);
}
Yacoub Massad
  • 27,509
  • 2
  • 36
  • 62
  • Nice one! Improvement suggestion: Use `Expression.Constant(0)` as the base case and start from `coeff.Length - 1`. Otherwise, your solution won't work for an empty list of coefficients. – Heinzi Jan 12 '16 at 14:01
  • That's right. Or I could simply return `x => 0` if the list is empty. – Yacoub Massad Jan 12 '16 at 14:03
1

another builder with fiddle, which doesn't use captured variable and Math.Pow and therefore works faster

 public static Func<int, double> CreatePolynomialSequence (params double[] coeff)
 {              
     // polynom builder
     // double argument
     var y = Expression.Variable(typeof(double), "y");  

     // func result
     var res = Expression.Variable(typeof(double), "res");       

     var expr = Expression.Assign(res, Expression.Constant(coeff[0]));

     // build polynom in format: ((a*x+b)*x+c)*x+d  <=>  a*x^3 + b*x^2 + c*x + d
     for (int i = 1; i < coeff.Length; i++)
     {
         expr = Expression.Add
                (
                    Expression.Multiply(expr, y), 
                    Expression.Constant(coeff[i]) 
                );
     }       

     // function body
     var x = Expression.Variable(typeof(int), "x"); 
     var block = Expression.Block
         (
             new ParameterExpression[]{ y, res },  // local variables
             new Expression[]
             {
                 // cast int argument to double
                 Expression.Assign(y, Expression.Convert(x, typeof(double))),
                 //compute result
                 expr
             }
        );

     return Expression.Lambda<Func<int, double>>(block, x).Compile();
 }
ASh
  • 34,632
  • 9
  • 60
  • 82