What is pattern matching? Benefits?

Masataro Asai edited this page Jul 14, 2016 · 8 revisions

Pattern Matching is basically a combination of nested COND and destructuring, such as destructuring-bind , with-slot and with-accessors. There are already ample of introduction to pattern matching, but I’d like to give another try with a concrete example.

Consider the following test data. a1 is a list of length 3 and a2 is a structure of type foo.

(defvar a1 '(:a 2 10))
(defstruct foo
  bar baz)
(defvar a2 (make-foo :bar 2 :baz 5))

Then we would like to write a function that returns the element of given data only if the given data and its associated elements fulfill certain conditions.

(defun myfunc (x)
  (cond
    ;; when the input is of type foo
    ((and (typep x 'foo)
          (eq :a (slot-value x 'baz)))
     (let ((b (slot-value x 'bar)))
       ...body1...))

    ;; when the input is a list
    ((and (and (listp x)
               (= 3 (length x)))
          (eq (first x) :a))
     (let ((b (second x))) ;; b is bound to 10
       ...body2...))))

In short, with pattern matching, you can write the same program shorter, as follows:

(defun myfunc (x)
  (match x
    ((foo (bar b) (baz :a))
     ...body1...)
    ((list* :a b _)
     ...body2...)))

Let’s break it down into details.

+ (match x

Now above line starts a pattern matching construct. match is a macro and the first argument is a form that is evaluated and matched against.

The next line specifies that the first pattern checks if the given object is of type foo.

(match x
+  ((foo

This kind of pattern is called a class pattern, and matches against any objects under standard-object and structure-object.

The first subform of that class pattern, or a subpattern, is (bar b) and it specifies the pattern for a slot bar. It binds the slot-value of the slot to a variable b with let, just like with-slots.

(match x
-  ((foo
+  ((foo (bar b)

Any non-self-evaluating symbols such as b are called variable patterns. They create let bindings in the macroexpanded code.

Next, the second subpattern of foo specifies another slot baz. Here, the subpattern is :a which satisfies constantp. It is called a constant pattern and the elements are compared with eq,eql,equal,equalp depending on the type of the constant.

(match x
-  ((foo (bar b)
+  ((foo (bar b) (baz :a)) ;; <-- pattern <--+
+   ...body1...)           ;; <-- body    <--+-- clause

If all of these query matches the input x, then body1 is executed under the lexical environment where b is bound to the contents of the slot bar of x. The pair of a pattern and a body is called a clause.


short break


Now, consider we call the function myfunc with a1 as the argument. Below is same as the example above. I just copied it here for the reader’s convenience.

(defvar a1 '(:a 2 10))
(defstruct foo
  bar baz)
(defvar a2 (make-foo :bar 2 :baz 5))

(defun myfunc (x)
  (match x
    ((foo (bar b) (baz :a))
     ...body1...)
    ((list* :a b _)
     ...body2...)))

The argument x becomes the value of a1, which is a list (:a 2 10) . This is not of class foo and it does not satisfy the first pattern, hence body1 is not executed. Note that there is no need to check the constant pattern (baz :a) , in other words, (eq (slot-value x 'baz) :a). This is because the value of x is proven NOT to be of type foo, hence there is no possibility that the (slot-value x 'baz) runs without error. Pattern matcher skips these unsatisfiable tests and start checking the second pattern clause immediately.

(match x
  ((foo (bar b) (baz :a))
   ...body1...)
+  ((list :a b _)
+   ...body2...))

The next clause is a list pattern, and it checks if x is a list of length 3. Its first subpattern is a constant pattern. The second subpattern is a variable pattern. And the last subpattern is a wildcard pattern, which states it doesn’t care. It does check the length test, but it runs no check against the corresponding element of the list, nor does it bind any variables with let.

Since this pattern matches against (:a 2 10), execution goes to body2, which is treated as an implicit progn. The value of the body of the first matching clause is returned as the value of match. If none of the pattern matches, it returns nil.

Patterns can be nested. For example, the following code returns 4. This property allows us to access and test the elements of a deeply nested structure in a simple language, without writing the accessor code explicitly.

(match '(:a (3 4) 5)
  ((list :a (list _ c) _)
   c))

Go to the next page for a full catalogue of other patterns.

You can’t perform that action at this time.
You signed in with another tab or window. Reload to refresh your session. You signed out in another tab or window. Reload to refresh your session.
Press h to open a hovercard with more details.