Skip to Main content Skip to Navigation
New interface
Journal articles

Anti-patterns for Rule-based Languages

Horatiu Cirstea 1 Claude Kirchner 1 Radu Kopetz 1 Pierre-Etienne Moreau 1 
1 PAREO - Formal islands: foundations and applications
INRIA Lorraine, LORIA - Laboratoire Lorrain de Recherche en Informatique et ses Applications
Abstract : 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. This should be naturally reflected in software that provide pattern-based searches. We would like for example to specify that we search for white cars that are not station wagons, or that we search for a list of objects that does not contain two identical elements. In this paper we extend the notion of pattern to the one of anti-pattern, i.e. patterns that may contain complement symbols. This concept is appropriate to design powerful extensions to pattern-based programming languages like ML, AsfSdf, Stratego, Maude, Elan or Tom and we show how this is used to extend the expressiveness and usability of the~Tom language. We further define formally the semantics of anti-patterns both in the syntactic case, i.e. when the symbols have no specific theory associated, and modulo an arbitrary equational theory. We then extend the classical notion of matching between patterns and ground terms to matching between anti-patterns and ground terms. Solving such problems can be performed either using general techniques as disunification, which we exemplify in the syntactical case, or more tailored and efficient approaches, which we chose to illustrate on the specific and very useful case of associativity, possibly with a unity. This allows us to be generic enough to give in this framework a very simple and natural expression of, for instance, the AllDiff standard predicate of constraint programming.
Document type :
Journal articles
Complete list of metadata
Contributor : Horatiu Cirstea Connect in order to contact the contributor
Submitted on : Monday, November 2, 2009 - 10:02:07 AM
Last modification on : Saturday, June 25, 2022 - 7:46:59 PM

Links full text




Horatiu Cirstea, Claude Kirchner, Radu Kopetz, Pierre-Etienne Moreau. Anti-patterns for Rule-based Languages. Journal of Symbolic Computation, 2010, 54 (5), pp.523-550. ⟨10.1016/j.jsc.2010.01.007⟩. ⟨inria-00429226⟩



Record views