Anti-Pattern Matching Modulo

Claude Kirchner (1) , Radu Kopetz (1) , Pierre-Etienne Moreau (1)

1 PROTHEO - Constraints, automatic deduction and software properties proofs

Negation is intrinsic to human thinking and most of the time when searching for something, we base our patterns on both positive and negative conditions. In a previous work, we have extended the notion of term to the one of anti-term that may contain complement symbols.Matching such anti-terms against terms has the nice property of being unitary. Here we generalize the syntactic anti-pattern matching to anti-pattern matching modulo an arbitrary equational theory E, and we study the specific and practically very useful case of associativity, possibly with a unity (AU). To this end, based on the syntacticness of associativity, we present a rule-based associative matching algorithm, and we extend it to AU. This algorithm is then used to solve AU anti-pattern matching problems. This allows us to be generic enough so that for instance, the AllDiff standard predicate of constraint programming becomes simply expressible in this framework. AU anti-patterns are implemented in the Tom language and we show some examples of their usage.

Mots clés: anti-pattern; equational theory; associative matching

Domaines: Informatique et langage [cs.CL]

Claude Kirchner, Radu Kopetz, Pierre-Etienne Moreau. Anti-Pattern Matching Modulo. The Fifth ASIAN Symposium on Programming Languages and Systems - APLAS 2007, Nov 2007, Singapore. ⟨inria-00129421v1⟩