CL-PATTERN is a very fast ML-like pattern-matching library for Common Lisp.
match value &body clauses
match macro tries to match value with clauses and raise an error
if no clauses matched. A clause have to be a form of (pattern form*), where pattern is a pattern (see "Patterns").
(match '(1 2)
((x y) (+ x y)))
;;=> 3
(match '(x 1)
(('x x) x))
;;=> 1
(match '(1 2)
((1 &optional a) a))
;;=> 2
lambda-match &body clauses
lambda-match is a shorthand of lambda and match. For example,
(lambda-match
(('foo a) a))
will be expaneded to
(lambda (arg)
(match arg
(('foo a) a)))
A pattern must be one of a symbol, a cons, and an atom. If the pattern
is symbol, the pattern is called a variable pattern, which can be
matched with any value. A body of a clause will be evaluated with
using a binding of the variable and the valueThe variable can be used
in a body of a. If the variable is _, any binding will not be
made. Here is an example:
(match 1
(x x))
;;=> 1
If the pattern is a cons, there is three cases you have to know. If a
car of the cons is quote, the pattern is called a constant
pattern, which can be matched with a same value of a cadr of the
cons. Here is an example:
(match 'x
('x 1))
;;=> 1
Second case, if the car of the cons is &optional, the pattern is
called a optional variable pattern, which can be matched with any
value as same as usual variable patterns, but it can be not
matched. If not matched, we say the pattern is unbound, meaning an
undefined value (nil will bound to the pattern.
(match '(1)
((1 &optional x) x))
;;=> NIL
(match '(1 2)
((1 &optional x) x))
;;=> 2
Othewise, the pattern is called a structure pattern, which can be
matched if a car of the pattern and a cdr of the pattern are
matched with a value. Here is an example:
(match '(1 . 2)
((x . y) (+ x y)))
;;=> 1
As you may guess, the car of the pattern and the cdr of the
pattern are also patterns. So you can nest patterns infinitely.
If the pattern is an atom, the pattern is called a constant pattern too. As we said, the pattern can be matched with a same value of the pattern. Here is an example:
(match 1
(1 'matched))
;;=> MATCHED
Here is a micro benchmark comparing
(match triple
((a &optional b c) (+ a b c)))
and
(destructuring-bind (a &optional b c)
triple
(+ a b c))
- 10000000 times
- with
(declare (optimized (speed 3))) - on Core 2 Duo 1.6GHz
On Allegro CL, destructuring-bind seems to be tuned properly.
MATCH
; cpu time (non-gc) 0.190000 sec user, 0.000000 sec system
; cpu time (gc) 0.000000 sec user, 0.000000 sec system
; cpu time (total) 0.190000 sec user, 0.000000 sec system
; real time 0.188305 sec
; space allocation:
; 0 cons cells, 0 other bytes, 0 static bytes
DESTRUCTURING-BIND
; cpu time (non-gc) 0.040000 sec user, 0.000000 sec system
; cpu time (gc) 0.000000 sec user, 0.000000 sec system
; cpu time (total) 0.040000 sec user, 0.000000 sec system
; real time 0.040888 sec
; space allocation:
; 0 cons cells, 0 other bytes, 0 static bytes
On SBCL, even in such the simple case, destructuring-bind seems to
be a very high cost operation.
MATCH
Evaluation took:
0.007 seconds of real time
0.010000 seconds of total run time (0.010000 user, 0.000000 system)
142.86% CPU
10,040,848 processor cycles
0 bytes consed
DESTRUCTURING-BIND
Evaluation took:
0.983 seconds of real time
0.980000 seconds of total run time (0.970000 user, 0.010000 system)
99.69% CPU
1,568,842,248 processor cycles
0 bytes consed
On ECL, match and destructuring-bind are almost same cost in this
simple case.
MATCH
real time : 0.883 secs
run time : 0.890 secs
gc count : 2 times
consed : 66339433 bytes
DESTRUCTURING-BIND
real time : 0.970 secs
run time : 0.960 secs
gc count : 1 times
consed : 66346216 bytes
- Allegro CL v8.2
- SBCL v1.0.47
- CMU CL v20b
- Clozure CL v1.6
- ECL v11.1.1
- GNU CLISP v2.48
Copyright (C) 2011 Tomohiro Matsuyama <tomo@cx4a.org>.