module Matcher:sig
..end
Standalone module containing the algorithm for matching modulo associativity and associativity and commutativity (AAC). Additionnaly, some A or AC operators can have units (U).
This module could be reused outside of the Coq plugin.
Matching a pattern p
against a term t
modulo AACU boils down
to finding a substitution env
such that the pattern p
instantiated with env
is equal to t
modulo AACU.
We proceed by structural decomposition of the pattern, trying all
possible non-deterministic splittings of the subject, when needed. The
function Matcher.matcher
is limited to top-level matching, that is, the
subject must make a perfect match against the pattern (x+x
does
not match a+a+b
).
We use a search monad Search_monad
to perform non-deterministic
choices in an almost transparent way.
We also provide a function Matcher.subterm
for finding a match that is
a subterm of the subject modulo AACU. In particular, this function
gives a solution to the aforementioned case (x+x
against
a+b+a
).
On a slightly more involved level :
typesymbol =
int
typevar =
int
Relationship between units and operators. This is a sparse
representation of a matrix of couples (op,unit)
where op
is
the index of the operation, and unit
the index of the relevant
unit. We make the assumption that any operation has 0 or 1 unit,
and that operations can share a unit).
typeunits =
(symbol * symbol) list
type
ext_units = {
|
unit_for : |
|
is_ac : |
}
type'a
mset =('a * int) list
The arguments of sums (or AC operators) are represented using finite multisets.
(Typically, a+b+a
corresponds to 2.a+b
, i.e. Sum[a,2;b,1]
)
val linear : 'a mset -> 'a list
linear
expands a multiset into a simple list
module Terms:sig
..end
Representations of expressions
module Subst:sig
..end
Substitutions (or environments)
val matcher : ?strict:bool ->
ext_units ->
Terms.t -> Terms.t -> Subst.t Search_monad.m
matcher p t
computes the set of solutions to the given top-level
matching problem (p
is the pattern, t
is the term). If the
strict
flag is set, solutions where units are used to
instantiate some variables are excluded, unless this unit appears
directly under a function symbol (e.g., f(x) still matches f(1),
while x+x+y does not match a+b+c, since this would require to
assign 1 to x).
val subterm : ?strict:bool ->
ext_units ->
Terms.t ->
Terms.t ->
(int * Terms.t * Subst.t Search_monad.m) Search_monad.m
subterm p t
computes a set of solutions to the given
subterm-matching problem.
Return a collection of possible solutions (each with the
associated depth, the context, and the solutions of the matching
problem). The context is actually a Matcher.Terms.t
where the variables
are yet to be instantiated by one of the associated substitutions