Add loadable modules.
[mes.git] / module / mes / match.upstream.mes
1 ;;; match.scm -- portable hygienic pattern matcher -*- coding: utf-8; mode: scheme -*-
2 ;;
3 ;; This code is written by Alex Shinn and placed in the
4 ;; Public Domain.  All warranties are disclaimed.
5
6 ;;> @example-import[(srfi 9)]
7
8 ;;> This is a full superset of the popular @hyperlink[
9 ;;> "http://www.cs.indiana.edu/scheme-repository/code.match.html"]{match}
10 ;;> package by Andrew Wright, written in fully portable @scheme{syntax-rules}
11 ;;> and thus preserving hygiene.
12
13 ;;> The most notable extensions are the ability to use @emph{non-linear}
14 ;;> patterns - patterns in which the same identifier occurs multiple
15 ;;> times, tail patterns after ellipsis, and the experimental tree patterns.
16
17 ;;> @subsubsection{Patterns}
18
19 ;;> Patterns are written to look like the printed representation of
20 ;;> the objects they match.  The basic usage is
21
22 ;;> @scheme{(match expr (pat body ...) ...)}
23
24 ;;> where the result of @var{expr} is matched against each pattern in
25 ;;> turn, and the corresponding body is evaluated for the first to
26 ;;> succeed.  Thus, a list of three elements matches a list of three
27 ;;> elements.
28
29 ;;> @example{(let ((ls (list 1 2 3))) (match ls ((1 2 3) #t)))}
30
31 ;;> If no patterns match an error is signalled.
32
33 ;;> Identifiers will match anything, and make the corresponding
34 ;;> binding available in the body.
35
36 ;;> @example{(match (list 1 2 3) ((a b c) b))}
37
38 ;;> If the same identifier occurs multiple times, the first instance
39 ;;> will match anything, but subsequent instances must match a value
40 ;;> which is @scheme{equal?} to the first.
41
42 ;;> @example{(match (list 1 2 1) ((a a b) 1) ((a b a) 2))}
43
44 ;;> The special identifier @scheme{_} matches anything, no matter how
45 ;;> many times it is used, and does not bind the result in the body.
46
47 ;;> @example{(match (list 1 2 1) ((_ _ b) 1) ((a b a) 2))}
48
49 ;;> To match a literal identifier (or list or any other literal), use
50 ;;> @scheme{quote}.
51
52 ;;> @example{(match 'a ('b 1) ('a 2))}
53
54 ;;> Analogous to its normal usage in scheme, @scheme{quasiquote} can
55 ;;> be used to quote a mostly literally matching object with selected
56 ;;> parts unquoted.
57
58 ;;> @example|{(match (list 1 2 3) (`(1 ,b ,c) (list b c)))}|
59
60 ;;> Often you want to match any number of a repeated pattern.  Inside
61 ;;> a list pattern you can append @scheme{...} after an element to
62 ;;> match zero or more of that pattern (like a regexp Kleene star).
63
64 ;;> @example{(match (list 1 2) ((1 2 3 ...) #t))}
65 ;;> @example{(match (list 1 2 3) ((1 2 3 ...) #t))}
66 ;;> @example{(match (list 1 2 3 3 3) ((1 2 3 ...) #t))}
67
68 ;;> Pattern variables matched inside the repeated pattern are bound to
69 ;;> a list of each matching instance in the body.
70
71 ;;> @example{(match (list 1 2) ((a b c ...) c))}
72 ;;> @example{(match (list 1 2 3) ((a b c ...) c))}
73 ;;> @example{(match (list 1 2 3 4 5) ((a b c ...) c))}
74
75 ;;> More than one @scheme{...} may not be used in the same list, since
76 ;;> this would require exponential backtracking in the general case.
77 ;;> However, @scheme{...} need not be the final element in the list,
78 ;;> and may be succeeded by a fixed number of patterns.
79
80 ;;> @example{(match (list 1 2 3 4) ((a b c ... d e) c))}
81 ;;> @example{(match (list 1 2 3 4 5) ((a b c ... d e) c))}
82 ;;> @example{(match (list 1 2 3 4 5 6 7) ((a b c ... d e) c))}
83
84 ;;> @scheme{___} is provided as an alias for @scheme{...} when it is
85 ;;> inconvenient to use the ellipsis (as in a syntax-rules template).
86
87 ;;> The @scheme{..1} syntax is exactly like the @scheme{...} except
88 ;;> that it matches one or more repetitions (like a regexp "+").
89
90 ;;> @example{(match (list 1 2) ((a b c ..1) c))}
91 ;;> @example{(match (list 1 2 3) ((a b c ..1) c))}
92
93 ;;> The boolean operators @scheme{and}, @scheme{or} and @scheme{not}
94 ;;> can be used to group and negate patterns analogously to their
95 ;;> Scheme counterparts.
96
97 ;;> The @scheme{and} operator ensures that all subpatterns match.
98 ;;> This operator is often used with the idiom @scheme{(and x pat)} to
99 ;;> bind @var{x} to the entire value that matches @var{pat}
100 ;;> (c.f. "as-patterns" in ML or Haskell).  Another common use is in
101 ;;> conjunction with @scheme{not} patterns to match a general case
102 ;;> with certain exceptions.
103
104 ;;> @example{(match 1 ((and) #t))}
105 ;;> @example{(match 1 ((and x) x))}
106 ;;> @example{(match 1 ((and x 1) x))}
107
108 ;;> The @scheme{or} operator ensures that at least one subpattern
109 ;;> matches.  If the same identifier occurs in different subpatterns,
110 ;;> it is matched independently.  All identifiers from all subpatterns
111 ;;> are bound if the @scheme{or} operator matches, but the binding is
112 ;;> only defined for identifiers from the subpattern which matched.
113
114 ;;> @example{(match 1 ((or) #t) (else #f))}
115 ;;> @example{(match 1 ((or x) x))}
116 ;;> @example{(match 1 ((or x 2) x))}
117
118 ;;> The @scheme{not} operator succeeds if the given pattern doesn't
119 ;;> match.  None of the identifiers used are available in the body.
120
121 ;;> @example{(match 1 ((not 2) #t))}
122
123 ;;> The more general operator @scheme{?} can be used to provide a
124 ;;> predicate.  The usage is @scheme{(? predicate pat ...)} where
125 ;;> @var{predicate} is a Scheme expression evaluating to a predicate
126 ;;> called on the value to match, and any optional patterns after the
127 ;;> predicate are then matched as in an @scheme{and} pattern.
128
129 ;;> @example{(match 1 ((? odd? x) x))}
130
131 ;;> The field operator @scheme{=} is used to extract an arbitrary
132 ;;> field and match against it.  It is useful for more complex or
133 ;;> conditional destructuring that can't be more directly expressed in
134 ;;> the pattern syntax.  The usage is @scheme{(= field pat)}, where
135 ;;> @var{field} can be any expression, and should result in a
136 ;;> procedure of one argument, which is applied to the value to match
137 ;;> to generate a new value to match against @var{pat}.
138
139 ;;> Thus the pattern @scheme{(and (= car x) (= cdr y))} is equivalent
140 ;;> to @scheme{(x . y)}, except it will result in an immediate error
141 ;;> if the value isn't a pair.
142
143 ;;> @example{(match '(1 . 2) ((= car x) x))}
144 ;;> @example{(match 4 ((= sqrt x) x))}
145
146 ;;> The record operator @scheme{$} is used as a concise way to match
147 ;;> records defined by SRFI-9 (or SRFI-99).  The usage is
148 ;;> @scheme{($ rtd field ...)}, where @var{rtd} should be the record
149 ;;> type descriptor specified as the first argument to
150 ;;> @scheme{define-record-type}, and each @var{field} is a subpattern
151 ;;> matched against the fields of the record in order.  Not all fields
152 ;;> must be present.
153
154 ;;> @example{
155 ;;> (let ()
156 ;;>   (define-record-type employee
157 ;;>     (make-employee name title)
158 ;;>     employee?
159 ;;>     (name get-name)
160 ;;>     (title get-title))
161 ;;>   (match (make-employee "Bob" "Doctor")
162 ;;>     (($ employee n t) (list t n))))
163 ;;> }
164
165 ;;> The @scheme{set!} and @scheme{get!} operators are used to bind an
166 ;;> identifier to the setter and getter of a field, respectively.  The
167 ;;> setter is a procedure of one argument, which mutates the field to
168 ;;> that argument.  The getter is a procedure of no arguments which
169 ;;> returns the current value of the field.
170
171 ;;> @example{(let ((x (cons 1 2))) (match x ((1 . (set! s)) (s 3) x)))}
172 ;;> @example{(match '(1 . 2) ((1 . (get! g)) (g)))}
173
174 ;;> The new operator @scheme{***} can be used to search a tree for
175 ;;> subpatterns.  A pattern of the form @scheme{(x *** y)} represents
176 ;;> the subpattern @var{y} located somewhere in a tree where the path
177 ;;> from the current object to @var{y} can be seen as a list of the
178 ;;> form @scheme{(x ...)}.  @var{y} can immediately match the current
179 ;;> object in which case the path is the empty list.  In a sense it's
180 ;;> a 2-dimensional version of the @scheme{...} pattern.
181
182 ;;> As a common case the pattern @scheme{(_ *** y)} can be used to
183 ;;> search for @var{y} anywhere in a tree, regardless of the path
184 ;;> used.
185
186 ;;> @example{(match '(a (a (a b))) ((x *** 'b) x))}
187 ;;> @example{(match '(a (b) (c (d e) (f g))) ((x *** 'g) x))}
188
189 ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
190 ;; Notes
191
192 ;; The implementation is a simple generative pattern matcher - each
193 ;; pattern is expanded into the required tests, calling a failure
194 ;; continuation if the tests fail.  This makes the logic easy to
195 ;; follow and extend, but produces sub-optimal code in cases where you
196 ;; have many similar clauses due to repeating the same tests.
197 ;; Nonetheless a smart compiler should be able to remove the redundant
198 ;; tests.  For MATCH-LET and DESTRUCTURING-BIND type uses there is no
199 ;; performance hit.
200
201 ;; The original version was written on 2006/11/29 and described in the
202 ;; following Usenet post:
203 ;;   http://groups.google.com/group/comp.lang.scheme/msg/0941234de7112ffd
204 ;; and is still available at
205 ;;   http://synthcode.com/scheme/match-simple.scm
206 ;; It's just 80 lines for the core MATCH, and an extra 40 lines for
207 ;; MATCH-LET, MATCH-LAMBDA and other syntactic sugar.
208 ;;
209 ;; A variant of this file which uses COND-EXPAND in a few places for
210 ;; performance can be found at
211 ;;   http://synthcode.com/scheme/match-cond-expand.scm
212 ;;
213 ;; 2012/05/23 - fixing combinatorial explosion of code in certain or patterns
214 ;; 2011/09/25 - fixing bug when directly matching an identifier repeated in
215 ;;              the pattern (thanks to Stefan Israelsson Tampe)
216 ;; 2011/01/27 - fixing bug when matching tail patterns against improper lists
217 ;; 2010/09/26 - adding `..1' patterns (thanks to Ludovic Court├Ęs)
218 ;; 2010/09/07 - fixing identifier extraction in some `...' and `***' patterns
219 ;; 2009/11/25 - adding `***' tree search patterns
220 ;; 2008/03/20 - fixing bug where (a ...) matched non-lists
221 ;; 2008/03/15 - removing redundant check in vector patterns
222 ;; 2008/03/06 - you can use `...' portably now (thanks to Taylor Campbell)
223 ;; 2007/09/04 - fixing quasiquote patterns
224 ;; 2007/07/21 - allowing ellipse patterns in non-final list positions
225 ;; 2007/04/10 - fixing potential hygiene issue in match-check-ellipse
226 ;;              (thanks to Taylor Campbell)
227 ;; 2007/04/08 - clean up, commenting
228 ;; 2006/12/24 - bugfixes
229 ;; 2006/12/01 - non-linear patterns, shared variables in OR, get!/set!
230
231 ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
232 ;; force compile-time syntax errors with useful messages
233
234 (define-syntax match-syntax-error
235   (syntax-rules ()
236     ((_) (match-syntax-error "invalid match-syntax-error usage"))))
237
238 ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
239
240 ;;> @subsubsection{Syntax}
241
242 ;;> @subsubsubsection{@rawcode{(match expr (pattern . body) ...)@br{}
243 ;;> (match expr (pattern (=> failure) . body) ...)}}
244
245 ;;> The result of @var{expr} is matched against each @var{pattern} in
246 ;;> turn, according to the pattern rules described in the previous
247 ;;> section, until the the first @var{pattern} matches.  When a match is
248 ;;> found, the corresponding @var{body}s are evaluated in order,
249 ;;> and the result of the last expression is returned as the result
250 ;;> of the entire @scheme{match}.  If a @var{failure} is provided,
251 ;;> then it is bound to a procedure of no arguments which continues,
252 ;;> processing at the next @var{pattern}.  If no @var{pattern} matches,
253 ;;> an error is signalled.
254
255 ;; The basic interface.  MATCH just performs some basic syntax
256 ;; validation, binds the match expression to a temporary variable `v',
257 ;; and passes it on to MATCH-NEXT.  It's a constant throughout the
258 ;; code below that the binding `v' is a direct variable reference, not
259 ;; an expression.
260
261 (define-syntax match
262   (syntax-rules ()
263     ((match)
264      (match-syntax-error "missing match expression"))
265     ((match atom)
266      (match-syntax-error "no match clauses"))
267     ((match (app ...) (pat . body) ...)
268      (let ((v (app ...)))
269        (match-next v ((app ...) (set! (app ...))) (pat . body) ...)))
270     ((match #(vec ...) (pat . body) ...)
271      (let ((v #(vec ...)))
272        (match-next v (v (set! v)) (pat . body) ...)))
273     ((match atom (pat . body) ...)
274      (let ((v atom))
275        (match-next v (atom (set! atom)) (pat . body) ...)))
276     ))
277
278 ;; MATCH-NEXT passes each clause to MATCH-ONE in turn with its failure
279 ;; thunk, which is expanded by recursing MATCH-NEXT on the remaining
280 ;; clauses.  `g+s' is a list of two elements, the get! and set!
281 ;; expressions respectively.
282
283 (define-syntax match-next
284   (syntax-rules (=>)
285     ;; no more clauses, the match failed
286     ((match-next v g+s)
287      ;; Here we call error in non-tail context, so that the backtrace
288      ;; can show the source location of the failing match form.
289      (begin
290        (error 'match "no matching pattern" v)
291        #f))
292     ;; named failure continuation
293     ((match-next v g+s (pat (=> failure) . body) . rest)
294      (let ((failure (lambda () (match-next v g+s . rest))))
295        ;; match-one analyzes the pattern for us
296        (match-one v pat g+s (match-drop-ids (begin . body)) (failure) ())))
297     ;; anonymous failure continuation, give it a dummy name
298     ((match-next v g+s (pat . body) . rest)
299      (match-next v g+s (pat (=> failure) . body) . rest))))
300
301 ;; MATCH-ONE first checks for ellipse patterns, otherwise passes on to
302 ;; MATCH-TWO.
303
304 (define-syntax match-one
305   (syntax-rules ()
306     ;; If it's a list of two or more values, check to see if the
307     ;; second one is an ellipse and handle accordingly, otherwise go
308     ;; to MATCH-TWO.
309     ((match-one v (p q . r) g+s sk fk i)
310      (match-check-ellipse
311       q
312       (match-extract-vars p (match-gen-ellipses v p r  g+s sk fk i) i ())
313       (match-two v (p q . r) g+s sk fk i)))
314     ;; Go directly to MATCH-TWO.
315     ((match-one . x)
316      (match-two . x))))
317
318 ;; This is the guts of the pattern matcher.  We are passed a lot of
319 ;; information in the form:
320 ;;
321 ;;   (match-two var pattern getter setter success-k fail-k (ids ...))
322 ;;
323 ;; usually abbreviated
324 ;;
325 ;;   (match-two v p g+s sk fk i)
326 ;;
327 ;; where VAR is the symbol name of the current variable we are
328 ;; matching, PATTERN is the current pattern, getter and setter are the
329 ;; corresponding accessors (e.g. CAR and SET-CAR! of the pair holding
330 ;; VAR), SUCCESS-K is the success continuation, FAIL-K is the failure
331 ;; continuation (which is just a thunk call and is thus safe to expand
332 ;; multiple times) and IDS are the list of identifiers bound in the
333 ;; pattern so far.
334
335 (define-syntax match-two
336   (syntax-rules (_ ___ ..1 *** quote quasiquote ? $ = and or not set! get!)
337     ((match-two v () g+s (sk ...) fk i)
338      (if (null? v) (sk ... i) fk))
339     ((match-two v (quote p) g+s (sk ...) fk i)
340      (if (equal? v 'p) (sk ... i) fk))
341     ((match-two v (quasiquote p) . x)
342      (match-quasiquote v p . x))
343     ((match-two v (and) g+s (sk ...) fk i) (sk ... i))
344     ((match-two v (and p q ...) g+s sk fk i)
345      (match-one v p g+s (match-one v (and q ...) g+s sk fk) fk i))
346     ((match-two v (or) g+s sk fk i) fk)
347     ((match-two v (or p) . x)
348      (match-one v p . x))
349     ((match-two v (or p ...) g+s sk fk i)
350      (match-extract-vars (or p ...) (match-gen-or v (p ...) g+s sk fk i) i ()))
351     ((match-two v (not p) g+s (sk ...) fk i)
352      (match-one v p g+s (match-drop-ids fk) (sk ... i) i))
353     ((match-two v (get! getter) (g s) (sk ...) fk i)
354      (let ((getter (lambda () g))) (sk ... i)))
355     ((match-two v (set! setter) (g (s ...)) (sk ...) fk i)
356      (let ((setter (lambda (x) (s ... x)))) (sk ... i)))
357     ((match-two v (? pred . p) g+s sk fk i)
358      (if (pred v) (match-one v (and . p) g+s sk fk i) fk))
359     ((match-two v (= proc p) . x)
360      (let ((w (proc v))) (match-one w p . x))
361      ;;(let ((W (proc v))) (match-one W p . x))
362      )
363     ((match-two v (p ___ . r) g+s sk fk i)
364      (match-extract-vars p (match-gen-ellipses v p r g+s sk fk i) i ()))
365     ((match-two v (p) g+s sk fk i)
366      (if (and (pair? v) (null? (cdr v)))
367          (let ;;((w (car v)))
368              ((W (car v)))
369            ;;(match-one w p ((car v) (set-car! v)) sk fk i)
370            (match-one W p ((car v) (set-car! v)) sk fk i)
371            )
372          fk))
373     ((match-two v (p *** q) g+s sk fk i)
374      (match-extract-vars p (match-gen-search v p q g+s sk fk i) i ()))
375     ((match-two v (p *** . q) g+s sk fk i)
376      (match-syntax-error "invalid use of ***" (p *** . q)))
377     ((match-two v (p ..1) g+s sk fk i)
378      (if (pair? v)
379          (match-one v (p ___) g+s sk fk i)
380          fk))
381     ((match-two v ($ rec p ...) g+s sk fk i)
382      (if (is-a? v rec)
383          (match-record-refs v rec 0 (p ...) g+s sk fk i)
384          fk))
385     ((match-two v (p . q) g+s sk fk i)
386      (if (pair? v)
387          (let ;;((w (car v)) (x (cdr v)))
388              ((W (car v)) (X (cdr v)))
389            (match-one ;;w p ((car v) (set-car! v))
390                       W p ((car v) (set-car! v))
391                       ;;(match-one x q ((cdr v) (set-cdr! v)) sk fk)
392                       (match-one X q ((cdr v) (set-cdr! v)) sk fk)
393                       fk
394                       i))
395          fk))
396     ((match-two v #(p ...) g+s . x)
397      (match-vector v 0 () (p ...) . x))
398     ((match-two v _ g+s (sk ...) fk i) (sk ... i))
399     ;; Not a pair or vector or special literal, test to see if it's a
400     ;; new symbol, in which case we just bind it, or if it's an
401     ;; already bound symbol or some other literal, in which case we
402     ;; compare it with EQUAL?.
403     (;;(match-two v x g+s (sk ...) fk (id ...))
404      (match-two V X g+s (sk ...) fk (id ...))
405      (let-syntax
406          ((new-sym?
407            (syntax-rules (id ...)
408              ;;((new-sym? x sk2 fk2) sk2)
409              ((new-sym? X sk2 fk2) sk2)
410              ((new-sym? y sk2 fk2) fk2))))
411        (new-sym? random-sym-to-match
412                  ;;(let ((x v)) (sk ... (id ... x)))
413                  (let ((X V)) (sk ... (id ... X)))
414                  ;;(if (equal? v x) (sk ... (id ...)) fk)
415                  (if (equal? V X) (sk ... (id ...)) fk)
416                  )))
417     ))
418
419 ;; QUASIQUOTE patterns
420
421 (define-syntax match-quasiquote
422   (syntax-rules (unquote unquote-splicing quasiquote)
423     ((_ v (unquote p) g+s sk fk i)
424      (match-one v p g+s sk fk i))
425     ((_ v ((unquote-splicing p) . rest) g+s sk fk i)
426      (if (pair? v)
427        (match-one v
428                   (p . tmp)
429                   (match-quasiquote tmp rest g+s sk fk)
430                   fk
431                   i)
432        fk))
433     ((_ v (quasiquote p) g+s sk fk i . depth)
434      (match-quasiquote v p g+s sk fk i #f . depth))
435     ((_ v (unquote p) g+s sk fk i x . depth)
436      (match-quasiquote v p g+s sk fk i . depth))
437     ((_ v (unquote-splicing p) g+s sk fk i x . depth)
438      (match-quasiquote v p g+s sk fk i . depth))
439     ((_ v (p . q) g+s sk fk i . depth)
440      (if (pair? v)
441          (let ;;((w (car v)) (x (cdr v)))
442              ((W (car v)) (X (cdr v)))
443          (match-quasiquote
444           ;;w p g+s
445           W p g+s
446           ;;(match-quasiquote-step x q g+s sk fk depth)
447           (match-quasiquote-step X q g+s sk fk depth)
448           fk i . depth))
449        fk))
450     ((_ v #(elt ...) g+s sk fk i . depth)
451      (if (vector? v)
452          (let ((ls (vector->list v)))
453            (match-quasiquote ls (elt ...) g+s sk fk i . depth))
454        fk))
455     ((_ v x g+s sk fk i . depth)
456      (match-one v 'x g+s sk fk i))))
457
458 (define-syntax match-quasiquote-step
459   (syntax-rules ()
460     ((match-quasiquote-step x q g+s sk fk depth i)
461      (match-quasiquote x q g+s sk fk i . depth))))
462
463 ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
464 ;; Utilities
465
466 ;; Takes two values and just expands into the first.
467 (define-syntax match-drop-ids
468   (syntax-rules ()
469     ((_ expr ids ...) expr)))
470
471 (define-syntax match-tuck-ids
472   (syntax-rules ()
473     ((_ (letish args (expr ...)) ids ...)
474      (letish args (expr ... ids ...)))))
475
476 (define-syntax match-drop-first-arg
477   (syntax-rules ()
478     ((_ arg expr) expr)))
479
480 ;; To expand an OR group we try each clause in succession, passing the
481 ;; first that succeeds to the success continuation.  On failure for
482 ;; any clause, we just try the next clause, finally resorting to the
483 ;; failure continuation fk if all clauses fail.  The only trick is
484 ;; that we want to unify the identifiers, so that the success
485 ;; continuation can refer to a variable from any of the OR clauses.
486
487 (define-syntax match-gen-or
488   (syntax-rules ()
489     ((_ v p g+s (sk ...) fk (i ...) ((id id-ls) ...))
490      (let ((sk2 (lambda (id ...) (sk ... (i ... id ...)))))
491        (match-gen-or-step v p g+s (match-drop-ids (sk2 id ...)) fk (i ...))))))
492
493 (define-syntax match-gen-or-step
494   (syntax-rules ()
495     ((_ v () g+s sk fk . x)
496      ;; no OR clauses, call the failure continuation
497      fk)
498     ((_ v (p) . x)
499      ;; last (or only) OR clause, just expand normally
500      (match-one v p . x))
501     ((_ v (p . q) g+s sk fk i)
502      ;; match one and try the remaining on failure
503      (let ((fk2 (lambda () (match-gen-or-step v q g+s sk fk i))))
504        (match-one v p g+s sk (fk2) i)))
505     ))
506
507 ;; We match a pattern (p ...) by matching the pattern p in a loop on
508 ;; each element of the variable, accumulating the bound ids into lists.
509
510 ;; Look at the body of the simple case - it's just a named let loop,
511 ;; matching each element in turn to the same pattern.  The only trick
512 ;; is that we want to keep track of the lists of each extracted id, so
513 ;; when the loop recurses we cons the ids onto their respective list
514 ;; variables, and on success we bind the ids (what the user input and
515 ;; expects to see in the success body) to the reversed accumulated
516 ;; list IDs.
517
518 (define-syntax match-gen-ellipses
519   (syntax-rules ()
520     (;;(_ v p () g+s (sk ...) fk i ((id id-ls) ...))
521      (_ v P () g+s (sk ...) fk i ((id id-ls) ...))
522      (match-check-identifier
523       ;;p
524       P
525       ;; simplest case equivalent to (p ...), just bind the list
526       (let ;;((p v))
527           ((P v))
528         (if ;;(list? p)
529          (list? P)
530              (sk ... i)
531              fk))
532        ;; simple case, match all elements of the list
533        (let loop ((ls v) (id-ls '()) ...)
534          (cond
535            ((null? ls)
536             (let ((id (reverse id-ls)) ...) (sk ... i)))
537            ((pair? ls)
538             (let ;;((w (car ls)))
539                 ((W (car ls)))
540               (match-one ;;w p ((car ls) (set-car! ls))
541                          W p ((car ls) (set-car! ls))
542                          (match-drop-ids (loop (cdr ls) (cons id id-ls) ...))
543                          fk i)))
544            (else
545             fk)))))
546     ((_ v p r g+s (sk ...) fk i ((id id-ls) ...))
547      ;; general case, trailing patterns to match, keep track of the
548      ;; remaining list length so we don't need any backtracking
549      (match-verify-no-ellipses
550       r
551       (let* ((tail-len (length 'r))
552              (ls v)
553              (len (and (list? ls) (length ls))))
554         (if (or (not len) (< len tail-len))
555             fk
556             (let loop ((ls ls) (n len) (id-ls '()) ...)
557               (cond
558                 ((= n tail-len)
559                  (let ((id (reverse id-ls)) ...)
560                    (match-one ls r (#f #f) (sk ...) fk i)))
561                 ((pair? ls)
562                  (let ((w (car ls)))
563                    (match-one w p ((car ls) (set-car! ls))
564                               (match-drop-ids
565                                (loop (cdr ls) (- n 1) (cons id id-ls) ...))
566                               fk
567                               i)))
568                 (else
569                  fk)))))))))
570
571 ;; This is just a safety check.  Although unlike syntax-rules we allow
572 ;; trailing patterns after an ellipses, we explicitly disable multiple
573 ;; ellipses at the same level.  This is because in the general case
574 ;; such patterns are exponential in the number of ellipses, and we
575 ;; don't want to make it easy to construct very expensive operations
576 ;; with simple looking patterns.  For example, it would be O(n^2) for
577 ;; patterns like (a ... b ...) because we must consider every trailing
578 ;; element for every possible break for the leading "a ...".
579
580 (define-syntax match-verify-no-ellipses
581   (syntax-rules ()
582     ((_ (x . y) sk)
583      (match-check-ellipse
584       x
585       (match-syntax-error
586        "multiple ellipse patterns not allowed at same level")
587       (match-verify-no-ellipses y sk)))
588     ((_ () sk)
589      sk)
590     ((_ x sk)
591      (match-syntax-error "dotted tail not allowed after ellipse" x))))
592
593 ;; To implement the tree search, we use two recursive procedures.  TRY
594 ;; attempts to match Y once, and on success it calls the normal SK on
595 ;; the accumulated list ids as in MATCH-GEN-ELLIPSES.  On failure, we
596 ;; call NEXT which first checks if the current value is a list
597 ;; beginning with X, then calls TRY on each remaining element of the
598 ;; list.  Since TRY will recursively call NEXT again on failure, this
599 ;; effects a full depth-first search.
600 ;;
601 ;; The failure continuation throughout is a jump to the next step in
602 ;; the tree search, initialized with the original failure continuation
603 ;; FK.
604
605 (define-syntax match-gen-search
606   (syntax-rules ()
607     ((match-gen-search v p q g+s sk fk i ((id id-ls) ...))
608      (letrec ((try (lambda (w fail id-ls ...)
609                      (match-one w q g+s
610                                 (match-tuck-ids
611                                  (let ((id (reverse id-ls)) ...)
612                                    sk))
613                                 (next w fail id-ls ...) i)))
614               (next (lambda (w fail id-ls ...)
615                       (if (not (pair? w))
616                           (fail)
617                           (let ((u (car w)))
618                             (match-one
619                              u p ((car w) (set-car! w))
620                              (match-drop-ids
621                               ;; accumulate the head variables from
622                               ;; the p pattern, and loop over the tail
623                               (let ((id-ls (cons id id-ls)) ...)
624                                 (let lp ((ls (cdr w)))
625                                   (if (pair? ls)
626                                       (try (car ls)
627                                            (lambda () (lp (cdr ls)))
628                                            id-ls ...)
629                                       (fail)))))
630                              (fail) i))))))
631        ;; the initial id-ls binding here is a dummy to get the right
632        ;; number of '()s
633        (let ((id-ls '()) ...)
634          (try v (lambda () fk) id-ls ...))))))
635
636 ;; Vector patterns are just more of the same, with the slight
637 ;; exception that we pass around the current vector index being
638 ;; matched.
639
640 (define-syntax match-vector
641   (syntax-rules (___)
642     ((_ v n pats (p q) . x)
643      (match-check-ellipse q
644                           (match-gen-vector-ellipses v n pats p . x)
645                           (match-vector-two v n pats (p q) . x)))
646     ((_ v n pats (p ___) sk fk i)
647      (match-gen-vector-ellipses v n pats p sk fk i))
648     ((_ . x)
649      (match-vector-two . x))))
650
651 ;; Check the exact vector length, then check each element in turn.
652
653 (define-syntax match-vector-two
654   (syntax-rules ()
655     ((_ v n ((pat index) ...) () sk fk i)
656      (if (vector? v)
657          (let ((len (vector-length v)))
658            (if (= len n)
659                (match-vector-step v ((pat index) ...) sk fk i)
660                fk))
661          fk))
662     ((_ v n (pats ...) (p . q) . x)
663      (match-vector v (+ n 1) (pats ... (p n)) q . x))))
664
665 (define-syntax match-vector-step
666   (syntax-rules ()
667     ((_ v () (sk ...) fk i) (sk ... i))
668     ((_ v ((pat index) . rest) sk fk i)
669      (let ((w (vector-ref v index)))
670        (match-one w pat ((vector-ref v index) (vector-set! v index))
671                   (match-vector-step v rest sk fk)
672                   fk i)))))
673
674 ;; With a vector ellipse pattern we first check to see if the vector
675 ;; length is at least the required length.
676
677 (define-syntax match-gen-vector-ellipses
678   (syntax-rules ()
679     ((_ v n ((pat index) ...) p sk fk i)
680      (if (vector? v)
681        (let ((len (vector-length v)))
682          (if (>= len n)
683            (match-vector-step v ((pat index) ...)
684                               (match-vector-tail v p n len sk fk)
685                               fk i)
686            fk))
687        fk))))
688
689 (define-syntax match-vector-tail
690   (syntax-rules ()
691     ((_ v p n len sk fk i)
692      (match-extract-vars p (match-vector-tail-two v p n len sk fk i) i ()))))
693
694 (define-syntax match-vector-tail-two
695   (syntax-rules ()
696     ((_ v p n len (sk ...) fk i ((id id-ls) ...))
697      (let loop ((j n) (id-ls '()) ...)
698        (if (>= j len)
699          (let ((id (reverse id-ls)) ...) (sk ... i))
700          (let ((w (vector-ref v j)))
701            (match-one w p ((vector-ref v j) (vetor-set! v j))
702                       (match-drop-ids (loop (+ j 1) (cons id id-ls) ...))
703                       fk i)))))))
704
705 (define-syntax match-record-refs
706   (syntax-rules ()
707     ((_ v rec n (p . q) g+s sk fk i)
708      (let ((w (slot-ref rec v n)))
709        (match-one w p ((slot-ref rec v n) (slot-set! rec v n))
710                   (match-record-refs v rec (+ n 1) q g+s sk fk) fk i)))
711     ((_ v rec n () g+s (sk ...) fk i)
712      (sk ... i))))
713
714 ;; Extract all identifiers in a pattern.  A little more complicated
715 ;; than just looking for symbols, we need to ignore special keywords
716 ;; and non-pattern forms (such as the predicate expression in ?
717 ;; patterns), and also ignore previously bound identifiers.
718 ;;
719 ;; Calls the continuation with all new vars as a list of the form
720 ;; ((orig-var tmp-name) ...), where tmp-name can be used to uniquely
721 ;; pair with the original variable (e.g. it's used in the ellipse
722 ;; generation for list variables).
723 ;;
724 ;; (match-extract-vars pattern continuation (ids ...) (new-vars ...))
725
726 (define-syntax match-extract-vars
727   (syntax-rules (_ ___ ..1 *** ? $ = quote quasiquote and or not get! set!)
728     ((match-extract-vars (? pred . p) . x)
729      (match-extract-vars p . x))
730     ((match-extract-vars ($ rec . p) . x)
731      (match-extract-vars p . x))
732     ((match-extract-vars (= proc p) . x)
733      (match-extract-vars p . x))
734     ((match-extract-vars (quote x) (k ...) i v)
735      (k ... v))
736     ((match-extract-vars (quasiquote x) k i v)
737      (match-extract-quasiquote-vars x k i v (#t)))
738     ((match-extract-vars (and . p) . x)
739      (match-extract-vars p . x))
740     ((match-extract-vars (or . p) . x)
741      (match-extract-vars p . x))
742     ((match-extract-vars (not . p) . x)
743      (match-extract-vars p . x))
744     ;; A non-keyword pair, expand the CAR with a continuation to
745     ;; expand the CDR.
746     ((match-extract-vars (p q . r) k i v)
747      (match-check-ellipse
748       q
749       (match-extract-vars (p . r) k i v)
750       (match-extract-vars p (match-extract-vars-step (q . r) k i v) i ())))
751     ((match-extract-vars (p . q) k i v)
752      (match-extract-vars p (match-extract-vars-step q k i v) i ()))
753     ((match-extract-vars #(p ...) . x)
754      (match-extract-vars (p ...) . x))
755     ((match-extract-vars _ (k ...) i v)    (k ... v))
756     ((match-extract-vars ___ (k ...) i v)  (k ... v))
757     ((match-extract-vars *** (k ...) i v)  (k ... v))
758     ((match-extract-vars ..1 (k ...) i v)  (k ... v))
759     ;; This is the main part, the only place where we might add a new
760     ;; var if it's an unbound symbol.
761     ((match-extract-vars p (k ...) (i ...) v)
762      (let-syntax
763          ((new-sym?
764            (syntax-rules (i ...)
765              ((new-sym? p sk fk) sk)
766              ((new-sym? any sk fk) fk))))
767        (new-sym? random-sym-to-match
768                  (k ... ((p p-ls) . v))
769                  (k ... v))))
770     ))
771
772 ;; Stepper used in the above so it can expand the CAR and CDR
773 ;; separately.
774
775 (define-syntax match-extract-vars-step
776   (syntax-rules ()
777     ((_ p k i v ((v2 v2-ls) ...))
778      (match-extract-vars p k (v2 ... . i) ((v2 v2-ls) ... . v)))
779     ))
780
781 (define-syntax match-extract-quasiquote-vars
782   (syntax-rules (quasiquote unquote unquote-splicing)
783     ((match-extract-quasiquote-vars (quasiquote x) k i v d)
784      (match-extract-quasiquote-vars x k i v (#t . d)))
785     ((match-extract-quasiquote-vars (unquote-splicing x) k i v d)
786      (match-extract-quasiquote-vars (unquote x) k i v d))
787     ((match-extract-quasiquote-vars (unquote x) k i v (#t))
788      (match-extract-vars x k i v))
789     ((match-extract-quasiquote-vars (unquote x) k i v (#t . d))
790      (match-extract-quasiquote-vars x k i v d))
791     ((match-extract-quasiquote-vars (x . y) k i v (#t . d))
792      (match-extract-quasiquote-vars
793       x
794       (match-extract-quasiquote-vars-step y k i v d) i ()))
795     ((match-extract-quasiquote-vars #(x ...) k i v (#t . d))
796      (match-extract-quasiquote-vars (x ...) k i v d))
797     ((match-extract-quasiquote-vars x (k ...) i v (#t . d))
798      (k ... v))
799     ))
800
801 (define-syntax match-extract-quasiquote-vars-step
802   (syntax-rules ()
803     ((_ x k i v d ((v2 v2-ls) ...))
804      (match-extract-quasiquote-vars x k (v2 ... . i) ((v2 v2-ls) ... . v) d))
805     ))
806
807
808 ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
809 ;; Gimme some sugar baby.
810
811 ;;> Shortcut for @scheme{lambda} + @scheme{match}.  Creates a
812 ;;> procedure of one argument, and matches that argument against each
813 ;;> clause.
814
815 (define-syntax match-lambda
816   (syntax-rules ()
817     ((_ (pattern . body) ...) (lambda (expr) (match expr (pattern . body) ...)))))
818
819 ;;> Similar to @scheme{match-lambda}.  Creates a procedure of any
820 ;;> number of arguments, and matches the argument list against each
821 ;;> clause.
822
823 (define-syntax match-lambda*
824   (syntax-rules ()
825     ((_ (pattern . body) ...) (lambda expr (match expr (pattern . body) ...)))))
826
827 ;;> Matches each var to the corresponding expression, and evaluates
828 ;;> the body with all match variables in scope.  Raises an error if
829 ;;> any of the expressions fail to match.  Syntax analogous to named
830 ;;> let can also be used for recursive functions which match on their
831 ;;> arguments as in @scheme{match-lambda*}.
832
833 (define-syntax match-let
834   (syntax-rules ()
835     ((_ ((var value) ...) . body)
836      (match-let/helper let () () ((var value) ...) . body))
837     ((_ loop ((var init) ...) . body)
838      (match-named-let loop ((var init) ...) . body))))
839
840 ;;> Similar to @scheme{match-let}, but analogously to @scheme{letrec}
841 ;;> matches and binds the variables with all match variables in scope.
842
843 (define-syntax match-letrec
844   (syntax-rules ()
845     ((_ ((var value) ...) . body)
846      (match-let/helper letrec () () ((var value) ...) . body))))
847
848 (define-syntax match-let/helper
849   (syntax-rules ()
850     ((_ let ((var expr) ...) () () . body)
851      (let ((var expr) ...) . body))
852     ((_ let ((var expr) ...) ((pat tmp) ...) () . body)
853      (let ((var expr) ...)
854        (match-let* ((pat tmp) ...)
855          . body)))
856     ((_ let (v ...) (p ...) (((a . b) expr) . rest) . body)
857      (match-let/helper
858       let (v ... (tmp expr)) (p ... ((a . b) tmp)) rest . body))
859     ((_ let (v ...) (p ...) ((#(a ...) expr) . rest) . body)
860      (match-let/helper
861       let (v ... (tmp expr)) (p ... (#(a ...) tmp)) rest . body))
862     ((_ let (v ...) (p ...) ((a expr) . rest) . body)
863      (match-let/helper let (v ... (a expr)) (p ...) rest . body))))
864
865 (define-syntax match-named-let
866   (syntax-rules ()
867     ((_ loop ((pat expr var) ...) () . body)
868      (let loop ((var expr) ...)
869        (match-let ((pat var) ...)
870          . body)))
871     ((_ loop (v ...) ((pat expr) . rest) . body)
872      (match-named-let loop (v ... (pat expr tmp)) rest . body))))
873
874 ;;> @subsubsubsection{@rawcode{(match-let* ((var value) ...) body ...)}}
875
876 ;;> Similar to @scheme{match-let}, but analogously to @scheme{let*}
877 ;;> matches and binds the variables in sequence, with preceding match
878 ;;> variables in scope.
879
880 (define-syntax match-let*
881   (syntax-rules ()
882     ((_ () . body)
883      (begin . body))
884     ((_ ((pat expr) . rest) . body)
885      (match expr (pat (match-let* rest . body))))))
886
887
888 ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
889 ;; Otherwise COND-EXPANDed bits.
890
891 ;; This *should* work, but doesn't :(
892 ;;   (define-syntax match-check-ellipse
893 ;;     (syntax-rules (...)
894 ;;       ((_ ... sk fk) sk)
895 ;;       ((_ x sk fk) fk)))
896
897 ;; This is a little more complicated, and introduces a new let-syntax,
898 ;; but should work portably in any R[56]RS Scheme.  Taylor Campbell
899 ;; originally came up with the idea.
900 (define-syntax match-check-ellipse
901   (syntax-rules ()
902     ;; these two aren't necessary but provide fast-case failures
903     ((match-check-ellipse (a . b) success-k failure-k) failure-k)
904     ((match-check-ellipse #(a ...) success-k failure-k) failure-k)
905     ;; matching an atom
906     ((match-check-ellipse id success-k failure-k)
907      (let-syntax ((ellipse? (syntax-rules ()
908                               ;; iff `id' is `...' here then this will
909                               ;; match a list of any length
910                               ((ellipse? (foo id) sk fk) sk)
911                               ((ellipse? other sk fk) fk))))
912        ;; this list of three elements will only many the (foo id) list
913        ;; above if `id' is `...'
914        (ellipse? (a b c) success-k failure-k)))))
915
916 ;; This is portable but can be more efficient with non-portable
917 ;; extensions.  This trick was originally discovered by Oleg Kiselyov.
918
919 (define-syntax match-check-identifier
920   (syntax-rules ()
921     ;; fast-case failures, lists and vectors are not identifiers
922     ((_ (x . y) success-k failure-k) failure-k)
923     ((_ #(x ...) success-k failure-k) failure-k)
924     ;; x is an atom
925     ((_ x success-k failure-k)
926      (let-syntax
927          ((sym?
928            (syntax-rules ()
929              ;; if the symbol `abracadabra' matches x, then x is a
930              ;; symbol
931              ((sym? x sk fk) sk)
932              ;; otherwise x is a non-symbol datum
933              ((sym? y sk fk) fk))))
934        (sym? abracadabra success-k failure-k)))))