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