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

Last change on this file since 13306 was 13306, checked in by felix winkelmann, 12 years ago

added xlib page and removed download links

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