Optimizing by Constant Folding

Part 7 of Parsing and Evaluating Mathematical Expressions

The sine of angles x measured in degrees can be plotted with the function sin(x*pi/180), where π/180 is the conversion factor from degrees to radians. Of course it is easier to remember that π radians is half the circle than to recall the equivalent value 0,017453293, but it would be much more efficient to enter the function to plot as sin(x*0,017453293) to avoid performing the costly division of π by 180 each time the parse tree is evaluated. Replacing the expression pi/180 with the equivalent constant when parsing the mathematical expression is a type of optimization called constant folding. This procedure will be implemented.

HasVariables

The brute force approach to identifying expressions that can be replaced by a constant is to call the corresponding tree’s Eval method. If an answer is obtained then it would be tempting to conclude that a constant has been found. Unfortunately, this could be wrong; it just happened that reasonable data was stored in a variable when the tree was evaluated.

There is no real solution to identifying expressions that potentially could be reduced to a constant other than to scan the tree looking for variables. To that end, a virtual boolean function called HasVariables is added to TTree, the ancestor class of all nodes in the parse tree. By default, that function returns false.

function TTree.HasVariables: boolean; begin result := false; end;

Of course, this is the proper result for a TNumberNode which, by definition, is a constant. It is not correct for TParameterNode because that does represent an unknown value such as x in the assignment f(x):= 2*x.

function TParameterNode.HasVariables: boolean; begin result := true; end;

The function is also overridden in the abstract class TParentNode. A parent node cannot be a variable when it represents an operation such as a sum or a product. All that needs be done is to check if any child node has variables.

function TParentNode.HasVariables: boolean; var i: integer; begin result := true; for I := 0 to FCount - 1 do if FNodes[i].HasVariables then exit; result := false; end;

This will be sufficient to handle all binary and unary nodes. However when the node is actually a TCallNode then it's target may be a TVariable which is obviously a variable.

function TCallNode.HasVariables: boolean; begin if FTarget is TVariable then result := true else result := inherited HasVariables; end;

There remains the class TIfNode. If the condition has variables, then there is no need to look further. Otherwise, the appropriate node needs to be looked at.

function TIfNode.HasVariables: boolean; begin result := Nodes[0].HasVariables; if not result then begin if Nodes[0].eval = 0 then result := Nodes[2].HasVariables else result := Nodes[1].HasVariables; end; end;

Constant Folding

...to be completed - note that the archive contains the completed source code implementing constant folding.

Source code

The source code for all units making up the parser is available along with a simple demonstration programme and test code. It is in the archive ParsingMathExpr-7.zip.

The demonstration program compiles with Delphi version 2 and up. It should also compile with Lazarus/FreePascal with minimal changes. As before, unit tests require DUnit.pas which works with newer versions of Delphi only. Unit testing was done with Delphi 2010.