Skip to content
Newer
Older
100644 189 lines (140 sloc) 4.5 KB
3331d9b Added support for optional pattern.
Tomohiro Matsuyama authored Apr 9, 2011
1 CL-PATTERN
480c666 Reimplementation pattern-matching algorithm.
Tomohiro Matsuyama authored Feb 17, 2011
2 ==========
44a4330 Initial commit.
Tomohiro Matsuyama authored Jan 5, 2011
3
3331d9b Added support for optional pattern.
Tomohiro Matsuyama authored Apr 8, 2011
4 CL-PATTERN is a very fast ML-like pattern-matching library for Common
5 Lisp.
44a4330 Initial commit.
Tomohiro Matsuyama authored Jan 5, 2011
6
dbae21e Added with-match-paramters. Now match is hygienic.
Tomohiro Matsuyama authored Apr 19, 2011
7 API
8 ---
44a4330 Initial commit.
Tomohiro Matsuyama authored Jan 5, 2011
9
3331d9b Added support for optional pattern.
Tomohiro Matsuyama authored Apr 8, 2011
10 ### Macro: `match`
44a4330 Initial commit.
Tomohiro Matsuyama authored Jan 5, 2011
11
04fbb69 Added lambda-match.
Tomohiro Matsuyama authored Apr 10, 2011
12 match value &body clauses
44a4330 Initial commit.
Tomohiro Matsuyama authored Jan 5, 2011
13
dbae21e Added with-match-paramters. Now match is hygienic.
Tomohiro Matsuyama authored Apr 18, 2011
14 `match` macro tries to match `value` with `clauses` and raise an error
15 if no clauses matched. A clause have to be a form of `(pattern
16 form*)`, where `pattern` is a pattern (see "Patterns").
17
44a4330 Initial commit.
Tomohiro Matsuyama authored Jan 5, 2011
18 #### Examples
19
20 (match '(1 2)
21 ((x y) (+ x y)))
dbae21e Added with-match-paramters. Now match is hygienic.
Tomohiro Matsuyama authored Apr 18, 2011
22 ;;=> 3
23
44a4330 Initial commit.
Tomohiro Matsuyama authored Jan 5, 2011
24 (match '(x 1)
25 (('x x) x))
dbae21e Added with-match-paramters. Now match is hygienic.
Tomohiro Matsuyama authored Apr 18, 2011
26 ;;=> 1
27
3331d9b Added support for optional pattern.
Tomohiro Matsuyama authored Apr 8, 2011
28 (match '(1 2)
29 ((1 &optional a) a))
dbae21e Added with-match-paramters. Now match is hygienic.
Tomohiro Matsuyama authored Apr 18, 2011
30 ;;=> 2
31
04fbb69 Added lambda-match.
Tomohiro Matsuyama authored Apr 10, 2011
32 ### Macro: `lambda-match`
33
34 lambda-match &body clauses
35
dbae21e Added with-match-paramters. Now match is hygienic.
Tomohiro Matsuyama authored Apr 18, 2011
36 `lambda-match` is a shorthand of `lambda` and `match`. For example,
37
38 (lambda-match
39 (('foo a) a))
40
41 will be expaneded to
42
43 (lambda (arg)
44 (match arg
45 (('foo a) a)))
46
47 ### Patterns
48
49 A pattern must be one of a symbol, a cons, and an atom. If the pattern
50 is symbol, the pattern is called a variable pattern, which can be
c6b43b7 Obsolete match parameters.
Tomohiro Matsuyama authored Apr 21, 2011
51 matched with any value. A body of a clause will be evaluated with
52 using a binding of the variable and the valueThe variable can be used
53 in a body of a. If the variable is `_`, any binding will not be
54 made. Here is an example:
dbae21e Added with-match-paramters. Now match is hygienic.
Tomohiro Matsuyama authored Apr 18, 2011
55
56 (match 1
57 (x x))
58 ;;=> 1
59
976a91c Added documentation about optional variable pattern.
Tomohiro Matsuyama authored Apr 19, 2011
60 If the pattern is a cons, there is three cases you have to know. If a
dbae21e Added with-match-paramters. Now match is hygienic.
Tomohiro Matsuyama authored Apr 18, 2011
61 `car` of the cons is `quote`, the pattern is called a constant
62 pattern, which can be matched with a same value of a `cadr` of the
63 cons. Here is an example:
64
65 (match 'x
66 ('x 1))
67 ;;=> 1
68
976a91c Added documentation about optional variable pattern.
Tomohiro Matsuyama authored Apr 18, 2011
69 Second case, if the `car` of the cons is `&optional`, the pattern is
70 called a optional variable pattern, which can be matched with any
71 value as same as usual variable patterns, but it can be not
c6b43b7 Obsolete match parameters.
Tomohiro Matsuyama authored Apr 21, 2011
72 matched. If not matched, we say the pattern is unbound, meaning an
73 undefined value (`nil` will bound to the pattern.
976a91c Added documentation about optional variable pattern.
Tomohiro Matsuyama authored Apr 18, 2011
74
75 (match '(1)
76 ((1 &optional x) x))
77 ;;=> NIL
78
79 (match '(1 2)
80 ((1 &optional x) x))
81 ;;=> 2
82
83 Othewise, the pattern is called a structure pattern, which can be
84 matched if a `car` of the pattern and a `cdr` of the pattern are
dbae21e Added with-match-paramters. Now match is hygienic.
Tomohiro Matsuyama authored Apr 18, 2011
85 matched with a value. Here is an example:
86
87 (match '(1 . 2)
88 ((x . y) (+ x y)))
89 ;;=> 1
90
91 As you may guess, the `car` of the pattern and the `cdr` of the
92 pattern are also patterns. So you can nest patterns infinitely.
93
94 If the pattern is an atom, the pattern is called a constant pattern
95 too. As we said, the pattern can be matched with a same value of the
96 pattern. Here is an example:
97
98 (match 1
99 (1 'matched))
100 ;;=> MATCHED
101
aab07cc Added benchmark.
Tomohiro Matsuyama authored Apr 19, 2011
102 Micro Benchmark
103 ---------------
104
105 Here is a micro benchmark comparing
106
107 (match triple
108 ((a &optional b c) (+ a b c)))
109
110 and
111
112 (destructuring-bind (a &optional b c)
113 triple
114 (+ a b c))
115
116 * 10000000 times
117 * with `(declare (optimized (speed 3)))`
118 * on Core 2 Duo 1.6GHz
119
120 ### Allegro CL v8.2 (Express Edition)
121
122 On Allegro CL, `destructuring-bind` seems to be tuned properly.
123
124 MATCH
125 ; cpu time (non-gc) 0.190000 sec user, 0.000000 sec system
126 ; cpu time (gc) 0.000000 sec user, 0.000000 sec system
127 ; cpu time (total) 0.190000 sec user, 0.000000 sec system
128 ; real time 0.188305 sec
129 ; space allocation:
130 ; 0 cons cells, 0 other bytes, 0 static bytes
131 DESTRUCTURING-BIND
132 ; cpu time (non-gc) 0.040000 sec user, 0.000000 sec system
133 ; cpu time (gc) 0.000000 sec user, 0.000000 sec system
134 ; cpu time (total) 0.040000 sec user, 0.000000 sec system
135 ; real time 0.040888 sec
136 ; space allocation:
137 ; 0 cons cells, 0 other bytes, 0 static bytes
138
139 ### SBCL v1.0.47
140
141 On SBCL, even in such the simple case, `destructuring-bind` seems to
142 be a very high cost operation.
143
144 MATCH
145 Evaluation took:
146 0.007 seconds of real time
147 0.010000 seconds of total run time (0.010000 user, 0.000000 system)
148 142.86% CPU
149 10,040,848 processor cycles
150 0 bytes consed
151
152 DESTRUCTURING-BIND
153 Evaluation took:
154 0.983 seconds of real time
155 0.980000 seconds of total run time (0.970000 user, 0.010000 system)
156 99.69% CPU
157 1,568,842,248 processor cycles
158 0 bytes consed
159
160 ### ECL v11.1.1
161
162 On ECL, `match` and `destructuring-bind` are almost same cost in this
163 simple case.
164
165 MATCH
166 real time : 0.883 secs
167 run time : 0.890 secs
168 gc count : 2 times
169 consed : 66339433 bytes
170 DESTRUCTURING-BIND
171 real time : 0.970 secs
172 run time : 0.960 secs
173 gc count : 1 times
174 consed : 66346216 bytes
175
dbae21e Added with-match-paramters. Now match is hygienic.
Tomohiro Matsuyama authored Apr 18, 2011
176 Supported Implementations
177 -------------------------
178
179 * Allegro CL v8.2
180 * SBCL v1.0.47
181 * CMU CL v20b
182 * Clozure CL v1.6
183 * ECL v11.1.1
184 * GNU CLISP v2.48
04fbb69 Added lambda-match.
Tomohiro Matsuyama authored Apr 10, 2011
185
3331d9b Added support for optional pattern.
Tomohiro Matsuyama authored Apr 8, 2011
186 ----
44a4330 Initial commit.
Tomohiro Matsuyama authored Jan 5, 2011
187
188 Copyright (C) 2011 Tomohiro Matsuyama <<tomo@cx4a.org>>.
Something went wrong with that request. Please try again.