Does ANSI Common Lisp have pattern matching?

Previously I've accepted the conventional wisdom that ANSI
Common Lisp does NOT have pattern matching. It doesn't
strike me as an important question; there are pattern
matching macros out there if I need them.

Recently I have noticed that combining typecase and
destructing-bind does much the same thing as pattern
matching. An aside in another thread suggested that CL is at
a disadvantage compared to languages with pattern matching
for algebraic manipulations such as differentiation and
simplification. This goaded me into trying to write such
code using the typecase/duct-tape/destructuring-bind technique

Here is a differentiator (restricted to binary multiplication)

(defun diff (form variable)
(typecase form
(symbol (if (eql form variable)
1
0))
(number 0)
((cons (eql +) *)
(cons '+ (mapcar (lambda(subform)
(diff subform variable))
(rest form))))
((cons (eql *)
(cons *
(cons * null)))
(destructuring-bind (prod left right) form
`(+ (* ,(diff left variable) ,right)
(* ,(diff right variable) ,left))))
((cons (eql *)
(cons *
(cons * *)))
(error "Sorry ~A makes the example too complicated." form))

Trying it out on a cubic I've prepared earlier

CL-USER> *cubic*
(+ (* 3 (* X (* X X))) (* 5 (* X X)) (* 7 X) 11)

produces the usual sorry mess

CL-USER> (diff *cubic* 'x)
(+ (+ (* 0 (* X (* X X))) (* (+ (* 1 (* X X)) (* (+ (* 1 X) (* 1 X)) X)) 3))
(+ (* 0 (* X X)) (* (+ (* 1 X) (* 1 X)) 5))
(+ (* 0 X) (* 1 7))
0)

so I started hacking together a simplifier. I realise that
matching patterns in a hacky way doesn't have a future, one
needs cannonical forms and stuff for a real algebra
system. Nevertheless my goal was to see how well
typecase/duct-tape/destruction-bind works as a pattern
matching technique.

I found that hacking in extra patterns to make the
simplification work was really rather addictive and I kept
going until my test form could be fully simplified by
several applications of simplify

(defun simplify (form)
(typecase form
((cons (eql *)
(cons (eql 0)
(cons * null)))
;; (* 0 x) => 0
0)
((cons (eql *)
(cons *
(cons (eql 0) null)))
;; (* x 0) => 0
0)
((cons (eql *)
(cons (eql 1) *))
;; (* 1 x) => x
(simplify (third form)))
((cons (eql *)
(cons *
(cons (eql 1) null)))
;; (* x 1) => x
(simplify (second form)))
((cons (eql *)
(cons number
(cons number null)))
;; (* n1 n2) => n3
(* (second form) (third form)))
((cons (eql *)
(cons number
(cons (cons (eql *)
(cons number
(cons * nul)))
null)))
;; (* n1 (* n2 x)) => (* n3 x)
(destructuring-bind (op1 n (op2 m x)) form
(list '* (* n m) (simplify x))))
((cons (eql *)
(cons (cons (eql *)
(cons number
(cons * null)))
(cons number null)))
(destructuring-bind (op1 (op2 n x) m) form
(list '* (* n m) (simplify x))))
((cons (eql *)
(cons (cons (eql *)
(cons number
(cons * null)))
(cons * null)))
;; (* (* n x) y) => (* n (* x y))
(destructuring-bind (op1 (op2 n x) y) form
`(* ,n (* ,(simplify x) ,(simplify y)))))
((cons (eql *) *)
(destructuring-bind (op left right) form
(list op
(simplify left)
(simplify right))))
((cons (eql +)
(cons (eql 0)
(cons * null)))
;; (+ 0 x) => x
(third form))
((cons (eql +)
(cons *
(cons (eql 0) null)))
;; (+ x 0) => x
(second form))
((cons (eql +)
(cons *
(cons (cons (eql *)
(cons number
(cons * null)))
null)))
;; (+ x (* n x)) => (* n+1 x)
;; (+ x (* n y)) => (+ x (* n y))
(destructuring-bind (*1 x (*2 n y)) form
(let ((x (simplify x))
(y (simplify y)))
(if (equal x y)
(list '* (+ n 1) x)
`(+ ,x (* ,n ,y))))))
((cons (eql +)
(cons *
(cons * null)))
;; (+ x x) => (* 2 x)
;; (+ x y) => (+ x y)
(destructuring-bind (x y)
(mapcar #'simplify (rest form))
(if (equal x y)
`(* 2 ,x)
(list '+ x y))))
((cons (eql +)
(cons (eql 0)
(cons * (cons * null))))
(destructuring-bind (op x y z) form
(list op (simplify y) (simplify z))))
((cons (eql +)
(cons *
(cons (eql 0)
(cons * null))))
;; (+ x 0 y) => (+ x y)
(destructuring-bind (op x y z) form
(list op (simplify x) (simplify z))))
((cons (eql +)
(cons *
(cons *
(cons (eql 0) null))))
(destructuring-bind (op x y z) form
(list op (simplify x) (simplify y))))
((cons (eql +)
(cons number
(cons number
(cons * null))))
(destructuring-bind (op x y z) form
(list op (+ x y) (simplify z))))
((cons (eql +)
(cons *
(cons *
(cons number
(cons number null)))))
(destructuring-bind (op x y n m) form
(list op (simplify x) (simplify y)(+ n m))))
((cons (eql +) *)
(cons '+ (mapcar #'simplify (rest form))))
(t form)))

Invoking it repeatedly

CL-USER> (diff *cubic* 'x)
(+ (+ (* 0 (* X (* X X))) (* (+ (* 1 (* X X)) (* (+ (* 1 X) (* 1 X)) X)) 3))
(+ (* 0 (* X X)) (* (+ (* 1 X) (* 1 X)) 5))
(+ (* 0 X) (* 1 7))
0)

CL-USER> (simplify *)
(+ (+ 0 (* (+ (* X X) (* (* 2 X) X)) 3)) (+ 0 (* (* 2 X) 5)) (+ 0 (* 1 7)) 0)

CL-USER> (simplify *)
(+ (* (+ (* X X) (* (* 2 X) X)) 3) (* (* 2 X) 5) (* 1 7) 0)

CL-USER> (simplify *)
(+ (* (+ (* X X) (* 2 (* X X))) 3) (* 10 X) 7 0)

CL-USER> (simplify *)
(+ (* (* 3 (* X X)) 3) (* 10 X) 7)

CL-USER> (simplify *)
(+ (* 9 (* X X)) (* 10 X) 7)

3 2 2
3x + 5x + 7x + 11 => 9x + 10x + 7

so that is a success of sorts.

I'm not sure what to make of this. The
typecase/duct-tape/destruction-bind technique clearly sucks,
and yet it is good enough to be addictive and fun :-) If a
program that I intended to distribute needed to do a modest
amount of pattern matching I would be very tempted to make
do with it and save myself a dependency on an external
package

There is a reason that typecase cannot bind variables. The
type (cons symbol number) cannot do

(let ((symbol (car x))
(number (cdr x)))
...

because it is already doing

(and (typep (car x) 'symbol)
(typep (cdr x) 'number))

The names are names of types. Since deftype lets symbols
name types, typecase cannot know that a symbol is supposed
to be a variable name and not a name for a type.

In my code I make use of this type matching. It is useful
and wins something back from the clunkiness of cons and eql.

The language design issue is that you cannot just write a
pattern

(a b c)

perhaps a is a literal, b a type and c a variable and I
would render it as

(typecase form
((cons (eql a) (cons b (cons * null)))
(destructuring-bind (x1 x2 c) form
(declare (ignore x1 x2))
...

So a fair summary could be that ANSI Common Lisp does have
built in pattern matching, but never fixed on a slick
notation to distinguish between literals, types, and
variables, leaving the programmer to make that choice and
define some macros to implement it.

Alan Crowe
Edinburgh
Scotland
.

Relevant Pages

  • Re: Does ANSI Common Lisp have pattern matching?
    ... (define simplify ... Common Lisp does NOT have pattern matching. ... (cons * null))) ... (destructuring-bind (prod left right) ...
    (comp.lang.lisp)
  • Re: Does ANSI Common Lisp have pattern matching?
    ... One candidate for your pattern matching needs could be ... (cons * null))) ... (destructuring-bind (prod left right) ... several applications of simplify ...
    (comp.lang.lisp)
  • Re: Does ANSI Common Lisp have pattern matching?
    ... (define simplify ... Common Lisp does NOT have pattern matching. ... (cons * null))) ... (destructuring-bind (prod left right) ...
    (comp.lang.lisp)
  • Re: destructuring-bind on infinite lists?
    ... This thread has prompted me to think about a better DESTRUCTURING-BIND ... Take the input pattern, ... macro that evaluates to a tree structure. ... (defun checked-car (cons) ...
    (comp.lang.lisp)
  • Re: Elemenrtary, My Dear Watson?
    ... The costume in question ... have a pattern for) is definitely an article of masculine attire. ... You wear trews then. ... They highlighted the pros and the cons of the matter. ...
    (soc.culture.scottish)