The Matcher - an overview

methods & patterns

The following example demonstrates the definition of matcher methods. The methods, called "calculate", are of little use but highlight the basic syntax of the matcher described here.

(defmatch calculate ((?x plus ?y))
  (+ #?x #?y))

(defmatch calculate ((?x minus ?y))
  (- #?x #?y))

The first method is defined to be applicable to an argument matching the pattern (?x plus ?y). The use of the "?" character prefixes the name of a matcher variable in common with other pattern matchers. The pattern (?x plus ?y) will match with any three element list containing the symbol "plus" as its second element.

The use of symbols like "#?x" in the body of the method definition is to retrieve the value of a matcher variable (see note).

calculate is used as follows:

> (calculate '(5 plus 3))  ==>  8
> (calculate '(5 minus 3))  ==>  2

In each case the calculate method used is that which matches the argument provided.

The matcher which underpins the use of DEFMATCH provides various matcher directives/tags. In addition to the single "?" prefix for matcher variables (for matching with single list elements). The "??" prefix will bind to zero or more list elements. This allows methods to be defined in a Prolog-like style and provides an alternative approach to structuring recursive forms. An example of this is a pair of list length methods (other prefixes).

(defmatch len1 (())  0)

(defmatch len1 ((??x))
  (1+ (len1 (rest #?x))))

> (len1 '(herring haddock hake)) ? 3

Note that where more than one method is applicable (because two or more match the argument provided) the method used is always the one which was defined first, like Prolog. Unlike Prolog there is no backtracking so other methods will never be invoked.

a matcher form of LET

In addition to the implicit use of the matcher when matcher methods are invoked it can be used explicitly through a small number of macro calls. The most basic of these is a LET form called MLET which provides a convenient mechanism for destructuring data.

An example of MLET in use follows, note that matcher forms other than DEFMATCH need their patterns to be quoted - this allows patterns to be dynamically constructed or stored in variables.

> (mlet ('(the ?subj ate the ?obj)
         '(the mouse ate the cheese))
    (list #?subj #?obj))

Two other matcher tags act as wildcards. These are "=" and "==" which are the matching tag for a single element wildcard and multiple element wildcard respectively.

> (mlet ('(= ?2nd == ?last) '(a b c d e f g))
    (list #?2nd #?last))
==> (B G)


foreach & forevery

FOREACH and FOREVERY are two iterative constructs which work by passing patterns over lists of possibly matching statements, they are based on the keywords of the same name in POP-11. One obvious use for these forms is with a set of related facts as in the following examples. With both FOREACH and FOREVERY forms the result returned is a collection of the results produced by their body of statements for each successful match.

(defvar db1
  ;; a simple set of facts concerning 4 boxes
  '((isa b1 box) (color b1 red)  (size b1 large)
    (isa b2 box) (color b2 red)  (size b2 small)
    (isa b3 box) (color b3 blue) (size b3 small)
    (isa b4 box) (color b3 blue) (size b4 small)
    (supports b1 b2) (supports b2 b3)

FOREACH iterates with single patterns, FOREVERY with multiple patterns...

> (foreach ('(size ?x small) db1)
    (format T "~&~a is small" #?x)   ; side effect
    #?x)                             ; result values

==> B2 is small
==> B3 is small
==> B4 is small
==> (B2 B3 B4)

> (forevery ('((isa ?b box)(color ?b red)
               (supports ?b ?x)) db1)
    (format T "~&~a is a red block which supports ~a"
               #?b #?x)
    (list 'red-block #?b))          ; value returned

==> B1 is a red block which supports B2
==> B2 is a red block which supports B3