Pattern Match Compilation

The pattern match optimizer of the Stratego compiler optimizes choices of strategies guarded with a pattern match operation ?t. A strategy of the form

   {xs1 : ?t1; s1} 
   <+ {xs2 : ?t2; s2}
   <+ ...
   <+ {xsn : ?tn; sn}

is transformed to a strategy of the form

   let f1(|ys1) = s1
       ...
       fn(|ysn) = sn
    in { zs :
         ?F1(z1,...,zn)
         < (!z1
            ; ?G1(z) 
              < fi(|z1,...,zn)
              + fail)
         + ?F2(zn+1,...,zn+m)
           < (fj(|zn+1,...,zn+m) <+ fk(|zn+1,...,zn+m)
           + ...
       }

In such a way that no constructor Fi is matched more than once at the same node. That is, the patterns are merged as much as possible. If there still exists overlap between two patterns, the continuation has a choice between the continuations, as illustrated by the branch resulting in a choice between fj and fk.

Pattern match compilation requires strategy inlining to ensure that the pattern matches are actually exposed.

-- EelcoVisser - 14 Aug 2003