Runtime Compiled Symbolic Expressions

• Download source files - 72 Kb
• Download demo project - 33.1 Kb

Introduction

This program demonstrates the expressiveness of the C# language and the flexibility of the .NET framework, implementing a Symbolic Expression system. This small library lets you enter expression by string or directly into the code, derive against a symbol, make symbolic substitutions, evaluate and runtime compile using the Intermediate Language.

There are many applications for this kind of library, just an example valid for me: use it in a Ray Tracing program to let user define implicit functions in the form f(x,y,z) = 0 and calculate numerically the intersection with a ray.

What this program shows?

1. C# custom operators
2. Dynamic assembly generation for fast evaluation
3. The Visitor pattern

Details

An expression is a Node object, there is a hierarchy of different Nodes that represent literals, symbols, binary and unary operators. The expression can be specified using two different methods: the first is a string and uses a parser, the second is directly in code and uses C# operator overloading. Let show something.

The string based method is really simple:

Parser par = new Parser();
Node expr = par.Parse("x+y^2*3");

When the expression is known, we can use also the in-code method in two flavors:

Node expr = (Node)"x" + ((Node)"y" ^ 2) * 3;
// or

Node x = (Node)"x";
Node y = (Node)"y";
Node expr2 = x + (y^2)*3;

Now the expression can be evaluated, just in time compiled or derived. I've chosen to separate the different features using a Visitor pattern, so you can use only the features that you want. The Derivator derives an expression against a symbol and it's quite simple.

Node expr = (Node)"x" + 5;
Derivator deriv = new Derivator();
Node n = deriv.Derive(expr, "x");

To evaluate the expression "slowly" just create an Evaluator object, set-up the symbols' values and get the result. Actually the evaluator uses just float, but the Visitor approach lets us define new kinds of Evaluators like a Complex one.

Node expr = par.Parse("cos(y)+5*3+2*x");
Evaluator ev = new Evaluator();
ev["x"] = 5;
ev["y"] = 7;
float f = ev.Evaluate(expr);

Other possible operations are Symbolic Substitution and Constant Folding but they are straightforward.

Just In Time compile

I wanted these expressions run fast, so I decided to dynamically compile the expressions using the System.Reflection.Emit package. The translation is done by the NodeCompiler using a recursive stack based technique. The resulting code is quite good, if compared to the same C# expression because the JIT makes a good job. Here is the code to compile an expression; the Functor is an abstract class with a method evaluate that takes just a float (I'm working on multiple variable evaluators).

Node expr = par.Parse("x+3*sin(x)");
NodeCompiler nc = new NodeCompiler();
Functor f = nc.Compile(expr);
float v = f.evaluate(5);

The NodeCompiler class has a method for each kind of Node and generates the IL OpCodes using an ILGenerator; the following code shows the case for the multiplication and division.

public override void VisitMulDiv(MulDivNode n) 
{
    n.Left.Accept(this);
    n.Right.Accept(this);
    methodIL.Emit(n.IsMultiplication ? OpCodes.Mul : OpCodes.Div);
}

The Visitor pattern

The Visitor pattern is used to traverse the Expression tree in an extendible way: the Derivator, Evaluator, Node Compiler and the other functionalities of the library are classes that implement the NodeVisitor interface. The other solution to this problem is to put virtual methods in the Node class, like compile, eval, derive and so on but it limits the extendibility of the classes. This pattern is described in the great book Design Pattern Elements of Reusable Object-Oriented Software by Gamma and others.

The interface NodeVisitor has a method for each kind of node that can be visited during the traversal, and each method is fully typed. Each Node implements the method Accept, that is called by a NodeVisitor to descend the tree. The following two snippets of code show the difference.

public interface NodeVisitor
{
    void VisitLiteral(LiteralNode n);
    void VisitSymbol(SymbolNode n);
    void VisitAddSub(AddSubNode n);
    void VisitMulDiv(MulDivNode n);
    ...
}

public abstract class Node : ICloneable
{
    ...
    public virtual void Accept(NodeVisitor nv) { nv.VisitNode(this); }
    ...
}
// this is the other approach 

public abstract class Node : ICloneable
{
    ...
    public abstract float Evaluate(EvaluationContext ec);
    public abstract void  Compile(CompileContext cc);
    public abstract Node  Derive(string symbol);
    ...
}

The problem with the Visitor approach compared with a classic set of virtual methods is relative to the stack based algorithms, e.g. the evaluation, because, in the case of virtual methods, the results are easily returned on the machine stack. With the Visitor pattern we require our own stack class like FloatStack or NodeStack. But this is a just little tradeoff.

The demo

The demo code shows some uses of the library and in particular the intersection of a ray with a circle where the circle is specified as a string. The intersection point is calculated numerically using the Newton-Raphson method and it's fast because the expressions are JIT compiled.

I hope you've enjoyed this!

Updates

• 16 Dec 2002

  Fixed:

  • Swapping constants in \ operator
  • Bad parenthesis printing
  • Right associativity problem

  Added:

  • Relational and logical operators: < > != >= <= && ||. The result is a floating point with value 1 or 0. They are not derivable.
  • Custom functions through delegate. Not derivable nor compilable. E.g. helloFx(10+x) > 12 || y < 25
  • Separated the project into a library and some test projects