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.
-- Main.EelcoVisser - 14 Aug 2003