Home > Uncategorized > Grasp, A .NET Analysis Engine – Part 7: Compiling Calculations

Grasp, A .NET Analysis Engine – Part 7: Compiling Calculations

March 4th, 2012 Leave a comment Go to comments

In part 6, we started to define the compilation process and determined how to find all variable references in a calculation’s expression tree. In this post, we will see how to generate executable code for a calculation in the form of a delegate.

Rewriting Calculation Expressions

As discussed in part 6, expression trees don’t inherently know what variable nodes mean, only Grasp does. The first step we need to take in compiling an expression is to transform variable references into something meaningful. For example, consider the example calculation from part 3 (namespaces omitted for clarity):

OperatingProfit = TotalIncome – TotalExpenses

Here, OperatingProfit is the output variable and TotalIncome – TotalExpenses is the expression tree that produces the result. It looks like this:

 

calculation-before-rewrite

 

Our goal is to locate the nodes that represent TotalIncome and TotalExpenses and completely replace them with different nodes that represent how to access their values. The variables are merely placeholders for more complex logic. This is known as rewriting an expression tree.

We already know how to ask for variable values: the GraspRuntime.GetVariableValue method. Thus, given a parameter of type GraspRuntime, we simply need to call GetVariableValue and pass in the variable represented by the node. (We will worry about where we get the runtime parameter later; for now, assume we have one in scope.)

This means we will turn each variable node turn into the appropriate method call. The resulting code will be:

runtime.GetVariableValue(TotalIncome) – runtime.GetVariableValue(TotalExpenses)

The data structure that represents this expression looks like:

 

calculation-after-rewrite

 

We replaced each VariableExpression with a MethodCallExpression that invokes the GetVariableValue method of the runtime parameter, packaging the corresponding variable in a constant and passing it as the single argument. We now have a data structure that represents fully-executable code and can be compiled to a delegate we can invoke.

Visiting Variables

In order to perform the rewrite, we will create another implementation of CalculationExpressionVisitor:

internal sealed class CalculationCompiler : CalculationExpressionVisitor
{
  internal CalculationFunction CompileCalculation(CalculationSchema schema)
  {
    
  }
}

It encapsulates the transformation of a CalculationSchema (defined in part 6) to a CalculationFunction (defined in part 4). In essence, it takes a calculation expression and compiles a Func<GraspRuntime, object> representing a method that takes a runtime parameter (for variable value lookups) and returns the calculated value.

The first step is to get a reference to GraspRuntime.GetVariableValue:

private static readonly MethodInfo _getVariableValueMethod =
  typeof(GraspRuntime).GetMethod(
    "GetVariableValue",
    BindingFlags.Public | BindingFlags.Instance);

We use reflection to get an instance of MethodInfo representing GetVariableValue, specifying that we want the public instance method of that name. We make the variable static so we only pay the reflection tax once per application domain, no matter how many instances of CalculationCompiler we create.

The next step is to define the parameter representing the runtime on which we make calls to GetVariableValue (using the Expression.Parameter factory method):

private readonly ParameterExpression _runtimeParameter =
  Expression.Parameter(typeof(GraspRuntime), "runtime");

With the GetVariableValue method and runtime parameter in hand, we can define a method which turns a VariableExpression into the corresponding method call (using the Expression.Call and Expression.Constant factory methods):

private Expression GetGetVariableValueCall(VariableExpression variableNode)
{
  return Expression.Call(
    _runtimeParameter,
    _getVariableValueMethod,
    Expression.Constant(variableNode.Variable));
}

Now we can override the VisitVariable method and define what happens whenever we see a VariableExpression in the tree:

protected override Expression VisitVariable(VariableExpression node)
{
  return Expression.Convert(GetGetVariableValueCall(node), node.Variable.Type);
}

We get the call to GetVariableValue for the variable, then cast the result to the variable’s type (using the Expression.Convert factory method). This is necessary because expression trees are type-safe, but GetVariableValue returns object. Luckily, we have easy access to the variable’s type.

Compiling the Rewritten Expression

We have defined the process of rewriting variable nodes as corresponding calls to GetVariableValue. This will produce expressions that look like the second figure above. Now we can implement the CompileCalculation method:

internal FunctionCalculator CompileCalculation(CalculationSchema schema)
{
  var body = schema.Expression;

  try
  {
    body = Visit(body);

    return new FunctionCalculator(schema.OutputVariable, CompileFunction(body));
  }
  catch(Exception ex)
  {
    throw new CalculationCompilationException(schema, body, ex);
  }
}

First, we ask the base class to visit the expression represented by the calculation. This will walk through the entire tree, rewriting variable nodes whenever they are encountered. Once we have the rewritten expression, we call the CompileFunction method, which turns it into a Func<GraspRuntime, object> delegate; this is the executable form of the calculation. We enclose the process in a try/catch so we can provide detailed error information in the case that a calculation’s expression is invalid.

Here is the lambda expression for our example in C# syntax:

runtime =>

  runtime.GetVariableValue(TotalIncome) – runtime.GetVariableValue(TotalExpenses)

This is the same expression we saw before, but now we have defined the runtime parameter. This is conceptually an inline method; it has a set of parameters and a body. Code defined as expression trees must take the form of a method so we can invoke them. In expression trees, lambda expressions are what represent method definitions.

We can define a lambda expression with the Expression.Lambda factory method, passing in the body (the rewritten expression), the runtime parameter we defined earlier, and the type of delegate we want to create. Finally, we can call Compile to have .NET dynamically generate a method that executes the code represented by the expression tree:

private Func<GraspRuntime, object> CompileFunction(Expression body)
{
  if(body.Type != typeof(object))
  {
    body = Expression.Convert(body, typeof(object));
  }

  var lambda = Expression.Lambda<Func<GraspRuntime, object>>(
    body,
    _runtimeParameter);

  return lambda.Compile();
}

We do a little bookkeeping to ensure that the lambda body returns object instead of the variable’s type; for C# source code, the compiler would infer this for us, but since we are building an expression tree by hand, we need to be explicit.

What we have at the end of CompileFunction is a delegate that wraps a method created by .NET to execute exactly the code represented by the rewritten expression. The beauty of this system is that the delegate can contain code of arbitrary complexity; anything that represents a valid expression tree can be used to define a calculation. Combined with the ability to use variables anywhere within an expression tree, Grasp supports any conceivable logic that operates on a data set.

Summary

We defined the transformation from variable nodes to nodes which access their values. We also created a visitor which performs the replacement and compiles the rewritten expression to executable code.

Next time, we will tackle a more gnarly problem: dependencies between calculations.

Continue to Part 8: Calculation Dependencies

Tags: , ,