source: project/wiki/eggref/4/matchable @ 29949

Last change on this file since 29949 was 29949, checked in by svnwiki, 8 years ago

Anonymous wiki edit for IP [213.250.31.28]: TOC and an example.

File size: 12.5 KB
Line 
1[[tags: egg]]
2
3== matchable
4
5This extension implements Andrew Wright's pattern matching macros.
6
7[[toc:]]
8
9=== Overview
10
11(This description has been taken mostly from Andrew Wright's
12postscript document.)
13
14Pattern matching allows complicated control decisions based on data
15structure to be expressed in a concise manner.  Pattern matching is
16found in several modern languages, notably Standard ML, Haskell and
17Miranda. These syntactic extensions internally use the {{match}}
18library unit.
19
20=== Interface
21
22<macro>(match exp (pat body 
) 
)</macro>
23
24The basic form of pattern matching expression,
25where {{exp}} is an expression, {{pat}} is a pattern, and
26{{body}} is one or more expressions
27(like the body of a lambda-expression).
28The {{match}} form matches its first subexpression against a sequence
29of patterns, and branches to the {{body}}
30corresponding to the first pattern successfully matched.
31
32For example, the following code defines the usual {{map}} function:
33
34<enscript highlight=scheme>
35(define map
36  (lambda (f l)
37    (match l
38      [() '()]
39      [(x . y) (cons (f x) (map f y))] )))
40</enscript>
41
42The first pattern {{()}} matches the empty list.  The second pattern
43{{(x . y)}} matches a pair, binding {{x}} to the first component of
44the pair and {{y}} to the second component of the pair.
45
46<macro>(match-lambda  (pat body 
) 
)</macro><br>
47<macro>(match-lambda* (pat body 
) 
)</macro><br>
48
49The {{match-lambda}} and {{match-lambda*}} forms are convenient
50combinations of {{match}} and {{lambda}}, and can be explained
51as follows:
52
53<enscript highlight=scheme>
54(match-lambda  (pat body 
) 
)
55  --> (lambda (x) (match x (pat body 
) 
))
56
57(match-lambda* (pat body 
) 
)
58  --> (lambda x   (match x (pat body) 
))
59</enscript>
60
61where {{x}} is a unique variable.
62
63The {{match-lambda}} form is convenient when defining a single argument
64function that immediately destructures its argument.
65The {{match-lambda*}} form constructs a function that accepts any number
66of arguments; the patterns of {{match-lambda*}} should be lists.
67
68For example, the {{map}} procedure can be written as:
69
70<enscript highlight=scheme>
71(define map
72  (match-lambda*
73    [(_ ()) '()]
74    [(f (x . y)) (cons (f x) (map f y))] ))
75</enscript>
76
77<macro>(match-let [var] ((pat exp) 
) body 
)</macro><br>
78<macro>(match-let*      ((pat exp) 
) body 
)</macro><br>
79<macro>(match-letrec    ((pat exp) 
) body 
)</macro><br>
80
81The {{match-let}}, {{match-let*}} and {{match-letrec}}
82forms generalize
83Scheme's {{let}}, {{let*}}, {{letrec}}, and {{define}}
84expressions to allow
85patterns in the binding position rather than just variables.
86For example, the following expression:
87
88<enscript highlight=scheme>
89(match-let (((x y z) (list 1 2 3)))
90            ((a b c) (list 4 5 6)))
91  body 
)
92</enscript>
93
94binds {{x}} to 1, {{y}} to 2, {{z}} to 3, {{a}} to 4, {{b}} to 5, and
95{{c}} to 6 in {{body 
}}.  These forms are convenient for
96destructuring the result of a function that returns multiple values as
97a list or vector.  As usual for {{letrec}}, pattern
98variables bound by {{match-letrec}} should not be
99used in computing the bound value.
100
101Analogously to named {{let}}, {{match-let}} accepts an optional loop
102variable {{var}} before the binding list, turning {{match-let}} into a
103general looping construct.
104
105=== Pattern Matching Expressions
106
107The complete syntax of the pattern matching expressions follows:
108
109 exp ::= (match exp clause 
)
110      |  (match-lambda clause 
)
111      |  (match-lambda* clause 
)
112      |  (match-let ([pat exp] 
) body)
113      |  (match-let* ([pat exp] 
) body)
114      |  (match-letrec ([pat exp] 
) body)
115      |  (match-let var ([pat exp] 
) body)
116
117 clause ::= [pat body]
118      |  [pat (=> identifier) body]
119
120 pat ::= identifier           matches anything, and binds identifier as a variable
121      |  _                    anything
122      |  ()                   itself (the empty list)
123      |  #t                   itself
124      |  #f                   itself
125      |  string               an `equal?' string
126      |  number               an `equal?' number
127      |  character            an `equal?' character
128      |  's-expression        an `equal?' s-expression
129      |  (pat-1 
 pat-n)    a proper list of n elements
130      |  (pat-1 
 pat-n . pat-n+1) 
131                              a list of n or more elements
132      |  (pat-1 
 pat-n pat-n+1 ...) 
133                              a proper list of n+k or more elements [1]
134      |  #(pat-1 
 pat-n)   a vector of n elements
135      |  #(pat-1 
 pat-n pat-n+1 ...) 
136                              a vector of n+k or more elements
137      |  ($ struct pat-1 
 pat-n) 
138                              a structure
139      |  (= field pat)        a field of a structure
140      |  (and pat-1 
 pat-n) 
141                              if all of pat-1 through pat-n match
142      |  (or pat-1 
 pat-n)
143                              if any of pat-1 through pat-n match
144      |  (not pat-1 
 pat-n)
145                              if none of pat-1 through pat-n match
146      |  (? predicate pat-1 
 pat-n) 
147                              if predicate true and pat-1 through pat-n all match
148      |  (set! identifier)    anything, and binds identifier as a setter
149      |  (get! identifier)    anything, and binds identifier as a getter
150      |  (pat-1 *** pat-2)    a tree pattern
151      |  `qp                  a quasipattern
152
153 qp ::= ()                    itself (the empty list)
154     |  #t                    itself
155     |  #f                    itself
156     |  string                an `equal?' string
157     |  number                an `equal?' number
158     |  character             an `equal?' character
159     |  symbol                an `equal?' symbol
160     |  (qp-1 
 qp-n)       a proper list of n elements
161     |  (qp-1 
 qp-n . qp-n+1) 
162                              a list of n or more elements
163     |  (qp-1 
 qp-n qp-n+1 ...) 
164                              a proper list of n+k or more elements
165     |  #(qp-1 
 qp-n)      a vector of n elements
166     |  #(qp-1 
 qp-n qp-n+1 ...) 
167                              a vector of n+k or more elements
168     |  ,pat                  a pattern
169     |  ,@pat                 a pattern, spliced
170
171==== Optional "=>" failure procedure syntax
172
173The {{match}}, {{match-lambda}}, and {{match-lambda*}} forms
174allow the optional syntax {{(=> identifier)}} between the pattern
175and the body of a clause.  When the pattern match for such a clause
176succeeds, the {{identifier}} is bound to a ''failure
177procedure'' of zero arguments within the {{body}}.  If this
178procedure is invoked, it jumps back to the pattern matching
179expression, and resumes the matching process as if the pattern had
180failed to match.  The {{body}} must not mutate the object being
181matched, otherwise unpredictable behavior may result.
182
183=== Patterns
184
185; {{identifier}}: matches anything, and binds a variable of this name to the matching value in the {{body}}.  Excludes the reserved names {{? , = _ ... and or not set! get!}}.
186
187; {{_}}: matches anything, without binding any variables.
188
189; {{()}}, {{#t}}, {{#f}}, {{string}}, {{number}}, {{character}}, '{{s-expression}}: These constant patterns match themselves, i.e., the corresponding value must be {{equal?}} to the pattern.
190
191; {{(pat-1 
 pat-n)}}: matches a proper list of {{n}} elements that match {{pat-1}} through {{pat-n}}.
192
193; {{(pat-1 
 pat-n . pat-n+1)}} : matches a (possibly improper) list of at least {{n}} elements that ends in something matching {{pat-n+1}}.
194
195; {{(pat-1 
 pat-n pat-n+1 ...)}}: matches a proper list of {{n}} or more elements, where each element of the tail matches {{pat-n+1}}.  Each pattern variable in {{pat-n+1}} is bound to a list of the matching values.  For example, the expression:
196
197<enscript highlight=scheme>
198(match '(let ([x 1][y 2]) z)
199  [('let ((binding values) ...) exp)  body ...])
200</enscript>
201
202binds {{binding}} to the list {{'(x y)}}, {{values}} to the list {{'(1 2)}}, and {{exp}} to {{'z}} in the body of the {{match}}-expression. For the special case where {{pat-n+1}} is a pattern variable, the list bound to that variable may share with the matched value.
203
204; {{(pat-1 
 pat-n pat-n+1 ___)}}: This pattern means the same thing as the previous pattern.
205
206; {{#(pat-1 
 pat-n)}}: matches a vector of length {{n}}, whose elements match {{pat-1}} through {{pat-n}}.
207
208; {{#(pat-1 
 pat-n pat-n+1 ...)}}: matches a vector of length {{n}} or more, where each element beyond {{n}} matches {{pat-n+1}}.
209
210; {{($ struct pat-1 
 pat-n)}}: matches a structure declared with {{define-record}} or {{define-record-type}}.
211
212; {{(= field pat)}}: is intended for selecting a field from a structure.  ''field'' may be any expression; it is applied to the value being matched, and the result of this application is matched against {{pat}}.
213
214; {{(and pat-1 
 pat-n)}}: matches if all of the subpatterns match. At least one subpattern must be present. This pattern is often used as {{(and x pat)}} to bind {{x}} to to the entire value that matches {{pat}} (cf. ''as-patterns'' in ML or Haskell).
215
216; {{(or pat-1 
 pat-n)}}: matches if any of the subpatterns match. At least one subpattern must be present. All subpatterns must bind the same set of pattern variables.
217
218; {{(not pat-1 
 pat-n)}}: matches if none of the subpatterns match. At least one subpattern must be present. The subpatterns may not bind any pattern variables.
219
220; {{(? predicate pat-1 
 pat-n)}}: In this pattern, {{predicate}} must be an expression evaluating to a single argument function. This pattern matches if {{predicate}} applied to the corresponding value is true, and the subpatterns {{pat-1 ... pat-n}} all match. The {{predicate}} should not have side effects, as the code generated by the pattern matcher may invoke predicates repeatedly in any order. The {{predicate}} expression is bound in the same scope as the match expression, i.e., free variables in {{predicate}} are not bound by pattern variables.
221
222; {{(set! identifier)}}: matches anything, and binds {{identifier}} to a procedure of one argument that mutates the corresponding field of the matching value. This pattern must be nested within a pair, vector, box, or structure pattern. For example, the expression:
223
224<enscript highlight=scheme>
225(define x (list 1 (list 2 3)))
226(match x [(_ (_ (set! setit)))  (setit 4)])
227</enscript>
228
229mutates the {{cadadr}} of {{x}} to 4, so that {{x}} is {{'(1 (2 4))}}.
230
231; {{(get! identifier)}}: matches anything, and binds {{identifier}} to a procedure of zero arguments that accesses the corresponding field of the matching value.  This pattern is the complement to {{set!}}. As with {{set!}}, this pattern must be nested within a pair, vector, box, or structure pattern.
232
233; {{`qp}} : Quasiquote introduces a quasipattern, in which identifiers are considered to be symbolic constants.  Like Scheme's quasiquote for data, {{unquote}} (,) and {{unquote-splicing}} (,@) escape back to normal patterns.
234
235=== Record Structures Pattern
236
237The {{$}} pattern handles native record structures and
238[[http://srfi.schemers.org/srfi-9/srfi-9.html|SRFI-9]] records
239transparently.  Currently it is required that
240[[http://srfi.schemers.org/srfi-9/srfi-9.html|SRFI-9]] record
241predicates are named exactly like the record type name, followed by a
242{{?}} (question mark) character.
243
244=== Tree Pattern
245
246Here we allow patterns of the form
247
248  (x *** y)
249
250to represent the pattern y located somewhere in a tree where the
251path from the current object to y can be seen as a list of the form
252(X 
).  Y can immediately match the current object in which case
253the path is the empty list.  In a sense it's a 2-dimensional
254version of the ... pattern.
255
256As a common case the pattern (_ *** y) can be used to search for Y
257anywhere in a tree, regardless of the path used.
258
259=== About this extension
260
261==== Author
262
263[[/users/alex-shinn|Alex Shinn]]
264
265==== License
266
267Public domain
268
269==== History
270
271; 2.7 : removed {{match-define}} from documentation which is not provided by this egg (thanks to Juergen Lorenz for pointing this out)
272; 2.6 : better implementation of some internal forms for E/R macros
273; 2.5 : removed {{-host}} option from setup script
274; 2.4 : fixing bug where (a ...) matched non-lists
275; 2.3 : allowing `...' with any backend, removing redundant check in vector patterns
276; 2.2 : uses srfi-46, if available (as it is in alexpander)
277; 2.1 : fixing quasiquote patterns
278; 2.0 : allowing ellipse patterns in other than the final position of a list
279; 1.41 : added syntax-error macro & specialized for Chicken [Kon Lovett]
280; 1.3 : updated to change in [[/eggref/3/syntactic-closures|syntactic-closures]] 0.91
281; 1.2 : bugfix, now all tests pass with [[/eggref/3/syntactic-closures|syntactic-closures]]
282; 1.1 : works now with [[/eggref/3/syntactic-closures|syntactic-closures]]
283; 1.0 : initial release
Note: See TracBrowser for help on using the repository browser.