Rewriting

rascal-0.33.7

Synopsis​

Rewriting using pattern-directed invocation

Description​

A rewrite rule is a recipe on how to simplify values. Remember: (a + b)^2^ = a^2^ + 2 ab + b^2^? A rewrite rule has a pattern as left-hand side -- here: (a + b)^2^ -- and a replacement as right-hand side -- here: a^2^ + 2 ab + b^2^. Given a value and a set of rewrite rules the patterns are tried on every subpart of the value and replacements are made if a match is successful. This is repeated as long as some pattern matches.

Rascal has ancestors, notably ASF+SDF, where rewriting was the most important computation mechanism. In Rascal, rewriting can be achieved using pattern-directed invocation, see Function Declaration, possibly combined with a Visit statement.

Examples​

In a package for symbolic differentiation it is desirable to keep expressions in simplified form in order to avoid intermediate results like `add(product(con(1), x), mul(con(0), y))` that can be simplified to `x`. The following definitions achieve this:

``Exp simp(add(con(n), con(m))) = con(n + m);       ❶  Exp simp(mul(con(n), con(m))) = con(n * m);Exp simp(mul(con(1), Exp e))  = e;Exp simp(mul(Exp e, con(1)))  = e;Exp simp(mul(con(0), Exp e))  = con(0);Exp simp(mul(Exp e, con(0)))  = con(0);Exp simp(add(con(0), Exp e))  = e;Exp simp(add(Exp e, con(0)))  = e;default Exp simp(Exp e)       = e;                 ❷  Exp simplify(Exp e){                               ❸    return bottom-up visit(e){           case Exp e1 => simp(e1)         }}``
• ❶ Definitions of the function `simp` are given with different patterns as formal arguments. Each definition is responsible for one particular simplification (here is where the similarity with rewrite rules surfaces).

• ❷ A default for `simp` is given: if no other definition applies, the default one is used.

• ❸ The actual `simplify` function: it performs a bottom up visit of the expression, replacing each subexpression by a simplified version.

See Derivative for a full explanation of this example.