Click here to Skip to main content
15,867,308 members
Articles / Programming Languages / C#
Article

Runtime Compiled Symbolic Expressions

Rate me:
Please Sign up or sign in to vote.
4.70/5 (28 votes)
15 Dec 20024 min read 95.7K   1.7K   42   14
A symbolic expression manipulator with derivation and substitution that dynamically compiles the expressions for fast evaluation.

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:

C#
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:

C#
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.

C#
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.

C#
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).

C#
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.

C#
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.

C#
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:
      C#
      < > != >= <= 
      && ||
      . 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

License

This article has no explicit license attached to it but may contain usage terms in the article text or the download files themselves. If in doubt please contact the author via the discussion board below.

A list of licenses authors might use can be found here


Written By
Software Developer (Senior) Scuola Superiore S.Anna
Italy Italy
Assistant Professor in Applied Mechanics working in Virtual Reality, Robotics and having fun with Programming

Comments and Discussions

 
Generalsmall bug - Clone Pin
kevin1232-Jul-08 21:49
kevin1232-Jul-08 21:49 
QuestionA request from FrzMD Pin
Sean Ewington2-Apr-07 9:11
staffSean Ewington2-Apr-07 9:11 
AnswerRe: A request from FrzMD Pin
Emanuele Ruffaldi2-Apr-07 9:39
Emanuele Ruffaldi2-Apr-07 9:39 
QuestionRound(x,2)? Pin
Charly Does28-Jul-04 22:51
Charly Does28-Jul-04 22:51 
Generalsmall bug and strange results Pin
H.Salomons19-Oct-03 20:35
sussH.Salomons19-Oct-03 20:35 
GeneralRe: small bug and strange results Pin
Pau Serra23-Nov-04 6:40
Pau Serra23-Nov-04 6:40 
GeneralWell Done Pin
Paul Abarham5-Sep-03 19:11
Paul Abarham5-Sep-03 19:11 
GeneralMore problems with parser Pin
Jabes16-Dec-02 4:28
Jabes16-Dec-02 4:28 
GeneralRe: More problems with parser Pin
Emanuele Ruffaldi16-Dec-02 8:48
Emanuele Ruffaldi16-Dec-02 8:48 
GeneralRe: More problems with parser Pin
Jabes16-Dec-02 9:55
Jabes16-Dec-02 9:55 
GeneralParser is always right associative Pin
Jabes16-Dec-02 4:15
Jabes16-Dec-02 4:15 
GeneralVery nice Pin
Jabes11-Dec-02 4:00
Jabes11-Dec-02 4:00 
GeneralRe: Very nice Pin
Emanuele Ruffaldi12-Dec-02 3:30
Emanuele Ruffaldi12-Dec-02 3:30 
Generalcool! Pin
Anonymous10-Dec-02 21:44
Anonymous10-Dec-02 21:44 

General General    News News    Suggestion Suggestion    Question Question    Bug Bug    Answer Answer    Joke Joke    Praise Praise    Rant Rant    Admin Admin   

Use Ctrl+Left/Right to switch messages, Ctrl+Up/Down to switch threads, Ctrl+Shift+Left/Right to switch pages.