notes/Rewriting.txt

   1 Some notes on rewriting:
   2
   3 The bottom up tree matching algorithm is basically from Todd Proesting's
   4 PhD thesis.  The index map compression scheme is due to a 1987 paper
   5 by David Chase.   In fast mode (-f) this is essentially what's generated.
   6 In the default slow mode, however, the index maps(mu) are actually compressed
   7 for a second time using the usual sparse 2-D array -> 1-D array compression
   8 algorithm (due to Tarjan and Yao, I think.)
   9
  10 This second compression makes the tables a lot smaller without any asymtotic
  11 degradation in time so it is the default.   If the secondary compression
  12 actually make it use _more_ storage than the uncompressed method, then
  13 the indices will be not compressed automatically.  You can explicitly
  14 disable this optimization using the -f option (for fast).
  15
  16 Rewriting in Prop actually encompasses the following different things:
  17   (1)  Perform some side effect upon matching each pattern.
  18        This is very similar to the behavior of `match', except that
  19        the action is performed on all matching subtrees, not just
  20        from the root, i.e. implicitly the entire tree is traversed.
  21   (2)  Translation, i.e. some other data value is synthesized in a bottom up
  22        manner from the traversal, and
  23   (3)  In place replacement, i.e. the subject tree is altered in place
  24        and matching is performed using the altered tree.
  25
  26 All three types of actions can be performed at the same time.  Furthermore,
  27 features such as cost minimization functions and pattern guards are also
  28 applicable to the pattern set, making rewriting a very general and powerful
  29 tool (and also making it quite difficult to implement ;-)
  30
  31 The actual source code for implement the algorithm is in the files
  32 src/automata/tree*  and src/rewrite/burs_*.
  33