Geek Answers Handbook

Matching patterns with associative and commutative operators

Pattern matching (as shown, for example, in Prolog, languages ​​of the ML family, and various shells of expert systems) is usually performed by matching the query with the data element by element in a strict order.

In areas such as automatic theoretical proof, however, it must be borne in mind that some operators are associative and commutative. Suppose we have data

A or B or C

and request

C or $X

Based on the surface syntax, this does not correspond, but logically it should correspond $Xto A or Bit because it is orassociative and commutative.

Is there any existing system in any language that does such things?

+5
source share
3 answers

Associative-commutative pattern matching has been around since 1981 and earlier and is still a hot topic today .

There are many systems that implement this idea and make it useful; this means that you can avoid writing complex pattern matches if you can use associativity or commutativity to match the pattern. Yes, it can be expensive; better pattern matching does this automatically than you do it poorly by hand.

, . , , , , A-C, . , , .

+6

maude .

http://maude.cs.uiuc.edu/

+5

, .

- , .

, ( ), .. C or $X $X or C.

( , ) , ( !). , .

, , , , , :

foo (Or ({C} disjointUnion {X})) = ...

, , , Isabelle/HOL, , .

EDIT: , Isabelle function ( fun) , , , , .

EDIT 2: , , n, :

A | B | C | D, B | C | $X, $X . , , .

, , .

{ (B,B), (C,C)  }

, . .

, , , ( A D), $X, . , , , RHS , LHS , ( ).

, . , , , , !

For the record, this may not be a good approach in all cases. I had very complex concepts of “coincidence” on the sub-terminals (i.e. Not simple equality), and therefore building kits or something would not work. Perhaps this will work in your case, although you can directly calculate unrelated joins.

+1
source

More articles:


All Articles