## 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?

- C# custom operators
- Dynamic assembly generation for fast evaluation
- The Visitor pattern

## Details

An expression is a `Node`

object, there is a hierarchy of
different `Node`

s 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;
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 `Evaluator`

s 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); }
...
}
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