Pattern Matching

Here is a function we wrote when we were learning recursive methods.

(defun test-my-length ()
  (or (= 0 (my-length ()))
      (= 1 (my-length '(a)))
      (= 2 (my-length '(a b)))
      (= 3 (my-length '(a b c)))))

(defun my-length (ns &optional (acc 0))
  "Return the length of a list of numbers"
  (cond ((null ns) acc)
        ((consp ns) (my-length (rest ns) (+ 1 acc)))))

These were the first steps we took.

1. We said in the docstring that ns should be a list.
2. We know that a list can be either nil or a cons.
3. In the latter case we extract the first and rest of the cons.

Let's focus on the last line. We used consp to determine that the list was indeed made by cons As a result we were licensed to apply first and rest to it.

Another approach could be to say that ns matches a pattern (cons first rest). Or perhaps a better way to write that cons is to use the notation of quasiquote. We could say that ns matches `(,first ,@rest) This is the approach taken by the trivia package in combination with the fare-quasiquote package.

We load these packages and define a package to work in.

(ql:quickload '(:trivia :named-readtables :trivia.quasiquote))

(defpackage :patterns
  (:use :cl :iterate :trivia :named-readtables))

(in-package :patterns)

(in-readtable :fare-quasiquote)

Here we are actually using the named-readtables package to change the syntax of Lisp itself. We need this in order to use quasiquote in a reverse way.

Some other examples of changing the syntax of Lisp are:

• cmu-infix which allows us to write infix arithmetic expressions like this:

  (in-readtable cmu-infix:syntax)
  
  (defun roots (a b c)
    (values #I(- b + sqrt(b^^2 - 4 * a * c)
            #I(- b - sqrt(b^^2 - 4 * a * c))))
  

• Vacietis which changes the syntax of Lisp to read the syntax of the C programming language and then compiles it.

But this is a rather advanced topic so we will say no more than that we have a readtable that allows us to use quasiquote expressions to match patterns.

Let's see how our my-length function looks with pattern matching.

(defun my-length (ns &optional (acc 0))
  "Return the length of a list of numbers"
  (match ns
    (nil acc)
    (`(,first ,@rest) (my-length (rest ns) (+ 1 acc)))))

(test-my-length)

The match macro is imported from trivia. In my-length it matches ns against the two clauses in order.

1. If ns matches nil then it returns acc
2. If ns matches `(,first ,@rest), namely "a list with a first element and a rest", then first gets bound to the first element of ns and rest gets bound to the rest.
3. With those bindings, (my-length (rest ns) (+ 1 acc)) is called recursively.

This combination of writing pattern using quasiquote and then matching them in turn to generate bindings gives us a powerful programming technique.