Name Rascal/Concepts/RewriteRules

Synopsis Rewrite rules (deprecated)

Description A rewrite rule is a recipe on how to simplify values. Remember: (a + b)² = a2 + 2ab + b2? A rewrite rule has a pattern as left-hand side (here: (a + b)² and a replacement as right-hand side (here: a2 + 2ab + b2). 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, 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:

public Exp simp(add(con(n), con(m))) = con(n + m);   
public Exp simp(mul(con(n), con(m))) = con(n * m);

public Exp simp(mul(con(1), Exp e))  = e;
public Exp simp(mul(Exp e, con(1)))  = e;
public Exp simp(mul(con(0), Exp e))  = con(0);
public Exp simp(mul(Exp e, con(0)))  = con(0);

public Exp simp(add(con(0), Exp e))  = e;
public Exp simp(add(Exp e, con(0)))  = e;

public default Exp simp(Exp e)       = e;            

public Exp simplify(Exp e){                          
  return bottom-up visit(e){
           case Exp e1 => simp(e1)
         }
}

Starting at definitions of the function simp are given with different patterns as formal argument. Each definition is responsible for one particular simplification (here is where the similarity with rewrite rules surfaces).

At a default for simp is given: if no other definition applies, the default one is used.

At the actual simplify function is given: it performs a bottom up visit of the expression, replacing each subexpression by a simplified version.

See Recipes:derivative for a full explanation of this example.

Pitfalls Rascal does still have special syntax for rewrite rules, but this has been deprecated in favour of pattern-directed invocation that can achieve the same, see Function.

The above example can be written using rule notation:

rule simp1 product(con(1), Expression e) => e;
rule simp2 product(Expression e, con(1)) => e;
rule simp3 product(con(0), Expression e) => con(0);
rule simp4 product(Expression e, con(0)) => con(0);
rule simp5 sum(con(0), Expression e)     => e;
rule simp6 sum(Expression e, con(0))     => e;

[Edit] | [New Subconcept] | [Recompile Course] | [Warnings]