Rewrite Rules

Dave DeLong edited this page Sep 19, 2015 · 1 revision

Rewrite rules are at the heart of rewriting expressions. A rewrite rule is a wrapper around three Expression objects: a predicate, a condition, and a pattern.

The Predicate

The predicate describes how an expression must be structured in order for the rewrite rule to be applied. The predicate looks for certain symbols. They are:

  • __num* - any numeric literal
  • __func* - any function
  • __var* - any variable
  • __exp* - any expression

As these special tokens are encounted in the predicate, the corresponding values from the source expression are extracted and saved.

The rewrite rule will make sure that all of the expressions in the source expression match the rule exactly before proceding. For example, let's say we have the rewrite rule of:

__exp1 * __exp1 * __exp1pow(__exp1, 3)

This will match these expressions:

sin(π) * sin(π) * sin(π)
(1+1) * (1+1) * (1+1)

But it will not match these:

sin(π) * sin(π) * cos(π)
(1+1) * (1+1) * (0+2)

The Condition

While the predicate dictates the structure an expression must have, the condition dictates values an expression may have. This is done via a simple boolean expression. For example, if we have the predicate of __exp1 / __exp1, we can rewrite this as long as __exp1 is not equal to zero. If __exp1 is equal to zero, then the overall expression would result in a division-by-zero operation, which results in a mathematical error.

Thus, we can specify a condition for the rewrite rule that __exp1 != 0. When an expression is found to match the predicate, it is then checked to see if the condition is met. If it is, then the pattern may be applied. If it is not, then the rule reports "no match".

The Pattern

If the expression is matched by the predicate and the condition is met, then the pattern is applied. The values extracted during predicate matching are substituted in to the pattern expression, and a new expression is created and returned.

Replacement patterns do not need to contain any of the special symbols. For example, a rule with the predicate of __exp1 - __exp1 can have a replacement of 0.

However, any symbol used in the replacement pattern must be used in the template.