Structure matching and rewriting engine

1. Introduction

Structure matching is the ability to match a pattern over a data structure. By using block parsing, it is possible to easily implement structure matching with parse rules. It also becomes easy to implement a rewriting engine that replaces a substructure matched by a pattern with another. Such an engine can be very useful in some special (but very interesting) cases, such as tree rewriting (which is a technique often used by optimizing compilers).

2. Overview

We provide two functions, match and rewrite. (The latter is based on the former.) The former takes a block or string as input, and tries to find a match for the parse rule given as second argument; it returns true if a match is found, otherwise returns false. (Since the pattern is a parse rule, you can use parens to apply any code to the matches.)

rewrite takes a block or string as input, and modifies it according to the rules given as second argument; these consist of a list of pairs of blocks. The first block of each pair is a parse rule to use as a pattern, while the second block is compose'ed and replaces the content matched by the pattern whenever it matches. This rewrite process is iterative, and is repeated until no pattern in the rules matches. (So, be careful as it's easy to get infinite loops, e.g. if your pattern always matches the second block.)

3. Match the parse rule rule over data

We use result to hold the result of the match, which is false by default and becomes true as soon as we find one occurrence of the pattern. If data is a block, our parse rule needs to recurse into subblocks too; if it's a string instead, the into command is invalid; so we need two separate rules for strings and blocks.

As you see, rule is applied repeatedly over data. Note that it does not stop when a match is found, but it will look for other matches too; this is useful if you have code in the parse rule (for example you could collect all matches).

3.1 match's locals

3.2 Example

An interesting example use of match is a collect function that collects all matches of a giver rule:

4. Apply the rewrite rules to data

We need to apply the given rewrite rules (list of pairs of blocks in rules) to data. If rules is empty, we have nothing to do, so we just return data.

Otherwise, we create a parse rules containing all the patterns in the list, in order. The pair [rule] [production] is added to the parse rule rules* as [rule] (prod: compose/deep [production]) |; this means rules* becomes a list of alternatives in the form [... | ... | ... |], and we need to remove the last |.

Then, we use match with a pattern that tries to match rules*, and replaces any match with prod (that has been computed in rules*). After replacing the parse cursor is set back to the beginning of the change, so as to apply the rules again on it. The call to match is repeated until it returns false (nothing more to rewrite).

If the /trace refinement has been used, each iteration of rewriting is printed on screen and a step-by-step tracing is performed.

4.1 rewrite's locals

4.2 Examples