Rewriting modes

  There are two basic modes of operations in a rewrite class: (i) tree rewriting and (ii) tree parsing. Tree rewriting repeatedly looks for redexes in a tree and transforms it into another tree. There are two sub-modes of operations: (a) applicative and (b) in-place. Applicative mode is specified using the applicative mode specifier when declaring a rewrite class. In this mode, a new tree is built from a bottom-up manner, and the subject tree is left unaltered. The default mode is ``in-place.'' In this mode, the subject tree is overwritten with the transformed expression.

On the other hand, in tree parsing mode, the left hand side of a rewrite rules specification is treated as a tree grammar. The tree parser will look for a derivation of given tree object from the start non-terminal. A guarded rule will only be used if the guard evaluates to true.

If rules are annotated with cost expressions, then the tree parser will try to locate a derivation chain with a minimal total cost. After a derivation tree is found, the tree can be repeated traversed. The rhs actions will be invoked during this traversal process.