Confirming Greenspun's 10th Law in C#

Question

I am trying to implement an infrastructure in C# that would allow me to make arbitrary mathematical expressions. For example, I want to be able to take an expression like

asin(sqrt(z - sin(x+y)^2))

and turn it into an object that will allow me to evaluate it in terms of x,y, and z, get derivatives, and possibly do some kind of symbolic algebra on it. What are people's thoughts on a good model for this in C#?

I have my own take, which I am afraid is heading off into architecture astronautics, so I want to make sure that is not the case.

Basically, the functions like sin, +, sqrt, etc. have classes based off a base class:

Function

Function<TOut> : Function
    TOut Value

Function<Tin, TOut> : Function
    TOut Evaluate(TIn value)
    Function Derivative
    Function<TOut, TIn> INverse

Function<TInA, TInB, TOut> : Function
    TOut Evaluate(TInA valueA, TInB valueB)
    Function PartialDerivativeA
    Function PartialDerivativeB

So far, so simple. The trick is how to compose the functions. Here I believe I want something like a currying approach so that I can evaluate the function for a single parameter, and have the other ones remain. So I am thinking of having a factory class like this:

Function<TInA, TInB, TOut> -> 
           Function<TInA, Function<TInB, TOut>>

(Function<TInA, TInB, TOut>, Function<TInX, TInA>, null) -> 
           Function<TInX, Function<TInB, TOut>>

(Function<TInA, TInB, TOut>, Function<TInA>, Function<TInX, TInY, TInB>) -> 
           Function<TInX, Function<TInY, TInB>>

and so on. My main concerns are that the generic types might make the system unusable (if the user is required to know the full generic types just to evaluate), and that I might not be able to construct all of the generic types from the input arguments.

Thanks for your input!

Answer 1

Note that it is possible to use the C# compiler to evaluate expressions.

Evaluating Mathematical Expressions by Compiling C# Code at Runtime http://www.codeproject.com/KB/recipes/matheval.aspx

Answer 2

I'm not entirely sure what currying is, but the usual approach to parsing expressions is to build an abstract syntax tree.
From this it shouldn't be difficult to evalute the expression, find the derivative, or whatever it is you want to do.

---

[Edit] I'm afraid your comments make no sense. From the sounds of it, you want to parse an expression and build an AST, from which you can do whatever you want with it. Yes, you will build classes for each type of node; something like this

public class PlusNode : BinaryNode
{
    public PlusNode(Node left, Node right) { base(left, right); }
    public virtual double Evaluate() { return Left.Evaluate() + Right.Evaluate(); }
    public virtual Node BuildDerivative()
    {
        return new PlusNode(Left.BuildDerivative(), Right.BuildDerivative());
    }
}

public class SinNode : UnaryNode
{
    public SinNode(Node child) { base(child); }
    public virtual double Evaluate() { return Math.Sin(Child.Evaluate()); }
    public virtual Node BuildDerivative()
    {
        return new MultiplyNode(new CosNode(Child.Clone()), Child.BuildDerivative()); //chain rule
    }
}

Answer 3

What about using Expression Trees? Note that on the linked page, there's even an example for building sort of a curried function (building a "less than five" function from a generic "less than" operator and a fixed constant)

Answer 4

Funny, I actually did this a few months ago in D and it wasn't received as particularly interesting. My approach was to use templated expression tree classes. I had a Binary class template that could be instantiated with +, *, etc, a unary class that could be instantiated with sin, exp, etc. Derivatives worked by mostly just recursively applying the chain and product rules. For example:

class Binary(alias fun) : MathExpression {
    MathExpression left, right;

    MathExpression derivative() {
        static if(is(fun == add)) {
            return left.derivative + right.derivative;
        } else static if(is(fun == mul)) {
            return left.derivative * right + right.derivative * left;
        }
    }

    real opCall(real x) {
        return fun(left(x), right(x));
    }
}


class Unary(alias fun) : MathExpression {
    MathExpression inner;

    MathExpression derivative() {
        static if(is(fun == sin)) {
            return Unary!(sin)(inner.derivative);
        }
    }

    real opCall(real x) {
        return fun(inner(x));
    }
}

class Constant : MathExpression {

    real val;

    real opCall(real x) {
        return val;
    }

    real derivative() {
        return new Constant(0);
    }
}