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;;> 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;; 2016/03/06 - fixing named match-let (thanks to Stefan Israelsson Tampe) 214;; 2015/05/09 - fixing bug in var extraction of quasiquote patterns 215;; 2014/11/24 - [OMITTED IN GUILE] adding Gauche's `@' pattern for named record field matching 216;; 2012/12/26 - wrapping match-let&co body in lexical closure 217;; 2012/11/28 - fixing typo s/vetor/vector in largely unused set! code 218;; 2012/05/23 - fixing combinatorial explosion of code in certain or patterns 219;; 2011/09/25 - fixing bug when directly matching an identifier repeated in 220;; the pattern (thanks to Stefan Israelsson Tampe) 221;; 2011/01/27 - fixing bug when matching tail patterns against improper lists 222;; 2010/09/26 - adding `..1' patterns (thanks to Ludovic Courtès) 223;; 2010/09/07 - fixing identifier extraction in some `...' and `***' patterns 224;; 2009/11/25 - adding `***' tree search patterns 225;; 2008/03/20 - fixing bug where (a ...) matched non-lists 226;; 2008/03/15 - removing redundant check in vector patterns 227;; 2008/03/06 - you can use `...' portably now (thanks to Taylor Campbell) 228;; 2007/09/04 - fixing quasiquote patterns 229;; 2007/07/21 - allowing ellipsis patterns in non-final list positions 230;; 2007/04/10 - fixing potential hygiene issue in match-check-ellipsis 231;; (thanks to Taylor Campbell) 232;; 2007/04/08 - clean up, commenting 233;; 2006/12/24 - bugfixes 234;; 2006/12/01 - non-linear patterns, shared variables in OR, get!/set! 235 236;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;; 237;; force compile-time syntax errors with useful messages 238 239(define-syntax match-syntax-error 240 (syntax-rules () 241 ((_) (match-syntax-error "invalid match-syntax-error usage")))) 242 243;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;; 244 245;;> @subsubsection{Syntax} 246 247;;> @subsubsubsection{@rawcode{(match expr (pattern . body) ...)@br{} 248;;> (match expr (pattern (=> failure) . body) ...)}} 249 250;;> The result of @var{expr} is matched against each @var{pattern} in 251;;> turn, according to the pattern rules described in the previous 252;;> section, until the the first @var{pattern} matches. When a match is 253;;> found, the corresponding @var{body}s are evaluated in order, 254;;> and the result of the last expression is returned as the result 255;;> of the entire @scheme{match}. If a @var{failure} is provided, 256;;> then it is bound to a procedure of no arguments which continues, 257;;> processing at the next @var{pattern}. If no @var{pattern} matches, 258;;> an error is signalled. 259 260;; The basic interface. MATCH just performs some basic syntax 261;; validation, binds the match expression to a temporary variable `v', 262;; and passes it on to MATCH-NEXT. It's a constant throughout the 263;; code below that the binding `v' is a direct variable reference, not 264;; an expression. 265 266(define-syntax match 267 (syntax-rules () 268 ((match) 269 (match-syntax-error "missing match expression")) 270 ((match atom) 271 (match-syntax-error "no match clauses")) 272 ((match (app ...) (pat . body) ...) 273 (let ((v (app ...))) 274 (match-next v ((app ...) (set! (app ...))) (pat . body) ...))) 275 ((match #(vec ...) (pat . body) ...) 276 (let ((v #(vec ...))) 277 (match-next v (v (set! v)) (pat . body) ...))) 278 ((match atom (pat . body) ...) 279 (let ((v atom)) 280 (match-next v (atom (set! atom)) (pat . body) ...))) 281 )) 282 283;; MATCH-NEXT passes each clause to MATCH-ONE in turn with its failure 284;; thunk, which is expanded by recursing MATCH-NEXT on the remaining 285;; clauses. `g+s' is a list of two elements, the get! and set! 286;; expressions respectively. 287 288(define-syntax match-next 289 (syntax-rules (=>) 290 ;; no more clauses, the match failed 291 ((match-next v g+s) 292 ;; Here we call error in non-tail context, so that the backtrace 293 ;; can show the source location of the failing match form. 294 (begin 295 (error 'match "no matching pattern" v) 296 #f)) 297 ;; named failure continuation 298 ((match-next v g+s (pat (=> failure) . body) . rest) 299 (let ((failure (lambda () (match-next v g+s . rest)))) 300 ;; match-one analyzes the pattern for us 301 (match-one v pat g+s (match-drop-ids (begin . body)) (failure) ()))) 302 ;; anonymous failure continuation, give it a dummy name 303 ((match-next v g+s (pat . body) . rest) 304 (match-next v g+s (pat (=> failure) . body) . rest)))) 305 306;; MATCH-ONE first checks for ellipsis patterns, otherwise passes on to 307;; MATCH-TWO. 308 309(define-syntax match-one 310 (syntax-rules () 311 ;; If it's a list of two or more values, check to see if the 312 ;; second one is an ellipsis and handle accordingly, otherwise go 313 ;; to MATCH-TWO. 314 ((match-one v (p q . r) g+s sk fk i) 315 (match-check-ellipsis 316 q 317 (match-extract-vars p (match-gen-ellipsis v p r g+s sk fk i) i ()) 318 (match-two v (p q . r) g+s sk fk i))) 319 ;; Go directly to MATCH-TWO. 320 ((match-one . x) 321 (match-two . x)))) 322 323;; This is the guts of the pattern matcher. We are passed a lot of 324;; information in the form: 325;; 326;; (match-two var pattern getter setter success-k fail-k (ids ...)) 327;; 328;; usually abbreviated 329;; 330;; (match-two v p g+s sk fk i) 331;; 332;; where VAR is the symbol name of the current variable we are 333;; matching, PATTERN is the current pattern, getter and setter are the 334;; corresponding accessors (e.g. CAR and SET-CAR! of the pair holding 335;; VAR), SUCCESS-K is the success continuation, FAIL-K is the failure 336;; continuation (which is just a thunk call and is thus safe to expand 337;; multiple times) and IDS are the list of identifiers bound in the 338;; pattern so far. 339 340(define-syntax match-two 341 (syntax-rules (_ ___ ..1 *** quote quasiquote ? $ = and or not set! get!) 342 ((match-two v () g+s (sk ...) fk i) 343 (if (null? v) (sk ... i) fk)) 344 ((match-two v (quote p) g+s (sk ...) fk i) 345 (if (equal? v 'p) (sk ... i) fk)) 346 ((match-two v (quasiquote p) . x) 347 (match-quasiquote v p . x)) 348 ((match-two v (and) g+s (sk ...) fk i) (sk ... i)) 349 ((match-two v (and p q ...) g+s sk fk i) 350 (match-one v p g+s (match-one v (and q ...) g+s sk fk) fk i)) 351 ((match-two v (or) g+s sk fk i) fk) 352 ((match-two v (or p) . x) 353 (match-one v p . x)) 354 ((match-two v (or p ...) g+s sk fk i) 355 (match-extract-vars (or p ...) (match-gen-or v (p ...) g+s sk fk i) i ())) 356 ((match-two v (not p) g+s (sk ...) fk i) 357 (match-one v p g+s (match-drop-ids fk) (sk ... i) i)) 358 ((match-two v (get! getter) (g s) (sk ...) fk i) 359 (let ((getter (lambda () g))) (sk ... i))) 360 ((match-two v (set! setter) (g (s ...)) (sk ...) fk i) 361 (let ((setter (lambda (x) (s ... x)))) (sk ... i))) 362 ((match-two v (? pred . p) g+s sk fk i) 363 (if (pred v) (match-one v (and . p) g+s sk fk i) fk)) 364 ((match-two v (= proc p) . x) 365 (let ((w (proc v))) (match-one w p . x))) 366 ((match-two v (p ___ . r) g+s sk fk i) 367 (match-extract-vars p (match-gen-ellipsis v p r g+s sk fk i) i ())) 368 ((match-two v (p) g+s sk fk i) 369 (if (and (pair? v) (null? (cdr v))) 370 (let ((w (car v))) 371 (match-one w p ((car v) (set-car! v)) sk fk i)) 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 (match-one w p ((car v) (set-car! v)) 389 (match-one x q ((cdr v) (set-cdr! v)) sk fk) 390 fk 391 i)) 392 fk)) 393 ((match-two v #(p ...) g+s . x) 394 (match-vector v 0 () (p ...) . x)) 395 ((match-two v _ g+s (sk ...) fk i) (sk ... i)) 396 ;; Not a pair or vector or special literal, test to see if it's a 397 ;; new symbol, in which case we just bind it, or if it's an 398 ;; already bound symbol or some other literal, in which case we 399 ;; compare it with EQUAL?. 400 ((match-two v x g+s (sk ...) fk (id ...)) 401 (let-syntax 402 ((new-sym? 403 (syntax-rules (id ...) 404 ((new-sym? x sk2 fk2) sk2) 405 ((new-sym? y sk2 fk2) fk2)))) 406 (new-sym? random-sym-to-match 407 (let ((x v)) (sk ... (id ... x))) 408 (if (equal? v x) (sk ... (id ...)) fk)))) 409 )) 410 411;; QUASIQUOTE patterns 412 413(define-syntax match-quasiquote 414 (syntax-rules (unquote unquote-splicing quasiquote) 415 ((_ v (unquote p) g+s sk fk i) 416 (match-one v p g+s sk fk i)) 417 ((_ v ((unquote-splicing p) . rest) g+s sk fk i) 418 (if (pair? v) 419 (match-one v 420 (p . tmp) 421 (match-quasiquote tmp rest g+s sk fk) 422 fk 423 i) 424 fk)) 425 ((_ v (quasiquote p) g+s sk fk i . depth) 426 (match-quasiquote v p g+s sk fk i #f . depth)) 427 ((_ v (unquote p) g+s sk fk i x . depth) 428 (match-quasiquote v p g+s sk fk i . depth)) 429 ((_ v (unquote-splicing p) g+s sk fk i x . depth) 430 (match-quasiquote v p g+s sk fk i . depth)) 431 ((_ v (p . q) g+s sk fk i . depth) 432 (if (pair? v) 433 (let ((w (car v)) (x (cdr v))) 434 (match-quasiquote 435 w p g+s 436 (match-quasiquote-step x q g+s sk fk depth) 437 fk i . depth)) 438 fk)) 439 ((_ v #(elt ...) g+s sk fk i . depth) 440 (if (vector? v) 441 (let ((ls (vector->list v))) 442 (match-quasiquote ls (elt ...) g+s sk fk i . depth)) 443 fk)) 444 ((_ v x g+s sk fk i . depth) 445 (match-one v 'x g+s sk fk i)))) 446 447(define-syntax match-quasiquote-step 448 (syntax-rules () 449 ((match-quasiquote-step x q g+s sk fk depth i) 450 (match-quasiquote x q g+s sk fk i . depth)))) 451 452;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;; 453;; Utilities 454 455;; Takes two values and just expands into the first. 456(define-syntax match-drop-ids 457 (syntax-rules () 458 ((_ expr ids ...) expr))) 459 460(define-syntax match-tuck-ids 461 (syntax-rules () 462 ((_ (letish args (expr ...)) ids ...) 463 (letish args (expr ... ids ...))))) 464 465(define-syntax match-drop-first-arg 466 (syntax-rules () 467 ((_ arg expr) expr))) 468 469;; To expand an OR group we try each clause in succession, passing the 470;; first that succeeds to the success continuation. On failure for 471;; any clause, we just try the next clause, finally resorting to the 472;; failure continuation fk if all clauses fail. The only trick is 473;; that we want to unify the identifiers, so that the success 474;; continuation can refer to a variable from any of the OR clauses. 475 476(define-syntax match-gen-or 477 (syntax-rules () 478 ((_ v p g+s (sk ...) fk (i ...) ((id id-ls) ...)) 479 (let ((sk2 (lambda (id ...) (sk ... (i ... id ...))))) 480 (match-gen-or-step v p g+s (match-drop-ids (sk2 id ...)) fk (i ...)))))) 481 482(define-syntax match-gen-or-step 483 (syntax-rules () 484 ((_ v () g+s sk fk . x) 485 ;; no OR clauses, call the failure continuation 486 fk) 487 ((_ v (p) . x) 488 ;; last (or only) OR clause, just expand normally 489 (match-one v p . x)) 490 ((_ v (p . q) g+s sk fk i) 491 ;; match one and try the remaining on failure 492 (let ((fk2 (lambda () (match-gen-or-step v q g+s sk fk i)))) 493 (match-one v p g+s sk (fk2) i))) 494 )) 495 496;; We match a pattern (p ...) by matching the pattern p in a loop on 497;; each element of the variable, accumulating the bound ids into lists. 498 499;; Look at the body of the simple case - it's just a named let loop, 500;; matching each element in turn to the same pattern. The only trick 501;; is that we want to keep track of the lists of each extracted id, so 502;; when the loop recurses we cons the ids onto their respective list 503;; variables, and on success we bind the ids (what the user input and 504;; expects to see in the success body) to the reversed accumulated 505;; list IDs. 506 507(define-syntax match-gen-ellipsis 508 (syntax-rules () 509 ((_ v p () g+s (sk ...) fk i ((id id-ls) ...)) 510 (match-check-identifier p 511 ;; simplest case equivalent to (p ...), just bind the list 512 (let ((p v)) 513 (if (list? p) 514 (sk ... i) 515 fk)) 516 ;; simple case, match all elements of the list 517 (let loop ((ls v) (id-ls '()) ...) 518 (cond 519 ((null? ls) 520 (let ((id (reverse id-ls)) ...) (sk ... i))) 521 ((pair? ls) 522 (let ((w (car ls))) 523 (match-one w p ((car ls) (set-car! ls)) 524 (match-drop-ids (loop (cdr ls) (cons id id-ls) ...)) 525 fk i))) 526 (else 527 fk))))) 528 ((_ v p r g+s (sk ...) fk i ((id id-ls) ...)) 529 ;; general case, trailing patterns to match, keep track of the 530 ;; remaining list length so we don't need any backtracking 531 (match-verify-no-ellipsis 532 r 533 (let* ((tail-len (length 'r)) 534 (ls v) 535 (len (and (list? ls) (length ls)))) 536 (if (or (not len) (< len tail-len)) 537 fk 538 (let loop ((ls ls) (n len) (id-ls '()) ...) 539 (cond 540 ((= n tail-len) 541 (let ((id (reverse id-ls)) ...) 542 (match-one ls r (#f #f) (sk ...) fk i))) 543 ((pair? ls) 544 (let ((w (car ls))) 545 (match-one w p ((car ls) (set-car! ls)) 546 (match-drop-ids 547 (loop (cdr ls) (- n 1) (cons id id-ls) ...)) 548 fk 549 i))) 550 (else 551 fk))))))))) 552 553;; This is just a safety check. Although unlike syntax-rules we allow 554;; trailing patterns after an ellipsis, we explicitly disable multiple 555;; ellipses at the same level. This is because in the general case 556;; such patterns are exponential in the number of ellipses, and we 557;; don't want to make it easy to construct very expensive operations 558;; with simple looking patterns. For example, it would be O(n^2) for 559;; patterns like (a ... b ...) because we must consider every trailing 560;; element for every possible break for the leading "a ...". 561 562(define-syntax match-verify-no-ellipsis 563 (syntax-rules () 564 ((_ (x . y) sk) 565 (match-check-ellipsis 566 x 567 (match-syntax-error 568 "multiple ellipsis patterns not allowed at same level") 569 (match-verify-no-ellipsis y sk))) 570 ((_ () sk) 571 sk) 572 ((_ x sk) 573 (match-syntax-error "dotted tail not allowed after ellipsis" x)))) 574 575;; To implement the tree search, we use two recursive procedures. TRY 576;; attempts to match Y once, and on success it calls the normal SK on 577;; the accumulated list ids as in MATCH-GEN-ELLIPSIS. On failure, we 578;; call NEXT which first checks if the current value is a list 579;; beginning with X, then calls TRY on each remaining element of the 580;; list. Since TRY will recursively call NEXT again on failure, this 581;; effects a full depth-first search. 582;; 583;; The failure continuation throughout is a jump to the next step in 584;; the tree search, initialized with the original failure continuation 585;; FK. 586 587(define-syntax match-gen-search 588 (syntax-rules () 589 ((match-gen-search v p q g+s sk fk i ((id id-ls) ...)) 590 (letrec ((try (lambda (w fail id-ls ...) 591 (match-one w q g+s 592 (match-tuck-ids 593 (let ((id (reverse id-ls)) ...) 594 sk)) 595 (next w fail id-ls ...) i))) 596 (next (lambda (w fail id-ls ...) 597 (if (not (pair? w)) 598 (fail) 599 (let ((u (car w))) 600 (match-one 601 u p ((car w) (set-car! w)) 602 (match-drop-ids 603 ;; accumulate the head variables from 604 ;; the p pattern, and loop over the tail 605 (let ((id-ls (cons id id-ls)) ...) 606 (let lp ((ls (cdr w))) 607 (if (pair? ls) 608 (try (car ls) 609 (lambda () (lp (cdr ls))) 610 id-ls ...) 611 (fail))))) 612 (fail) i)))))) 613 ;; the initial id-ls binding here is a dummy to get the right 614 ;; number of '()s 615 (let ((id-ls '()) ...) 616 (try v (lambda () fk) id-ls ...)))))) 617 618;; Vector patterns are just more of the same, with the slight 619;; exception that we pass around the current vector index being 620;; matched. 621 622(define-syntax match-vector 623 (syntax-rules (___) 624 ((_ v n pats (p q) . x) 625 (match-check-ellipsis q 626 (match-gen-vector-ellipsis v n pats p . x) 627 (match-vector-two v n pats (p q) . x))) 628 ((_ v n pats (p ___) sk fk i) 629 (match-gen-vector-ellipsis v n pats p sk fk i)) 630 ((_ . x) 631 (match-vector-two . x)))) 632 633;; Check the exact vector length, then check each element in turn. 634 635(define-syntax match-vector-two 636 (syntax-rules () 637 ((_ v n ((pat index) ...) () sk fk i) 638 (if (vector? v) 639 (let ((len (vector-length v))) 640 (if (= len n) 641 (match-vector-step v ((pat index) ...) sk fk i) 642 fk)) 643 fk)) 644 ((_ v n (pats ...) (p . q) . x) 645 (match-vector v (+ n 1) (pats ... (p n)) q . x)))) 646 647(define-syntax match-vector-step 648 (syntax-rules () 649 ((_ v () (sk ...) fk i) (sk ... i)) 650 ((_ v ((pat index) . rest) sk fk i) 651 (let ((w (vector-ref v index))) 652 (match-one w pat ((vector-ref v index) (vector-set! v index)) 653 (match-vector-step v rest sk fk) 654 fk i))))) 655 656;; With a vector ellipsis pattern we first check to see if the vector 657;; length is at least the required length. 658 659(define-syntax match-gen-vector-ellipsis 660 (syntax-rules () 661 ((_ v n ((pat index) ...) p sk fk i) 662 (if (vector? v) 663 (let ((len (vector-length v))) 664 (if (>= len n) 665 (match-vector-step v ((pat index) ...) 666 (match-vector-tail v p n len sk fk) 667 fk i) 668 fk)) 669 fk)))) 670 671(define-syntax match-vector-tail 672 (syntax-rules () 673 ((_ v p n len sk fk i) 674 (match-extract-vars p (match-vector-tail-two v p n len sk fk i) i ())))) 675 676(define-syntax match-vector-tail-two 677 (syntax-rules () 678 ((_ v p n len (sk ...) fk i ((id id-ls) ...)) 679 (let loop ((j n) (id-ls '()) ...) 680 (if (>= j len) 681 (let ((id (reverse id-ls)) ...) (sk ... i)) 682 (let ((w (vector-ref v j))) 683 (match-one w p ((vector-ref v j) (vector-set! v j)) 684 (match-drop-ids (loop (+ j 1) (cons id id-ls) ...)) 685 fk i))))))) 686 687(define-syntax match-record-refs 688 (syntax-rules () 689 ((_ v rec n (p . q) g+s sk fk i) 690 (let ((w (slot-ref rec v n))) 691 (match-one w p ((slot-ref rec v n) (slot-set! rec v n)) 692 (match-record-refs v rec (+ n 1) q g+s sk fk) fk i))) 693 ((_ v rec n () g+s (sk ...) fk i) 694 (sk ... i)))) 695 696;; Extract all identifiers in a pattern. A little more complicated 697;; than just looking for symbols, we need to ignore special keywords 698;; and non-pattern forms (such as the predicate expression in ? 699;; patterns), and also ignore previously bound identifiers. 700;; 701;; Calls the continuation with all new vars as a list of the form 702;; ((orig-var tmp-name) ...), where tmp-name can be used to uniquely 703;; pair with the original variable (e.g. it's used in the ellipsis 704;; generation for list variables). 705;; 706;; (match-extract-vars pattern continuation (ids ...) (new-vars ...)) 707 708(define-syntax match-extract-vars 709 (syntax-rules (_ ___ ..1 *** ? $ = quote quasiquote and or not get! set!) 710 ((match-extract-vars (? pred . p) . x) 711 (match-extract-vars p . x)) 712 ((match-extract-vars ($ rec . p) . x) 713 (match-extract-vars p . x)) 714 ((match-extract-vars (= proc p) . x) 715 (match-extract-vars p . x)) 716 ((match-extract-vars (quote x) (k ...) i v) 717 (k ... v)) 718 ((match-extract-vars (quasiquote x) k i v) 719 (match-extract-quasiquote-vars x k i v (#t))) 720 ((match-extract-vars (and . p) . x) 721 (match-extract-vars p . x)) 722 ((match-extract-vars (or . p) . x) 723 (match-extract-vars p . x)) 724 ((match-extract-vars (not . p) . x) 725 (match-extract-vars p . x)) 726 ;; A non-keyword pair, expand the CAR with a continuation to 727 ;; expand the CDR. 728 ((match-extract-vars (p q . r) k i v) 729 (match-check-ellipsis 730 q 731 (match-extract-vars (p . r) k i v) 732 (match-extract-vars p (match-extract-vars-step (q . r) k i v) i ()))) 733 ((match-extract-vars (p . q) k i v) 734 (match-extract-vars p (match-extract-vars-step q k i v) i ())) 735 ((match-extract-vars #(p ...) . x) 736 (match-extract-vars (p ...) . x)) 737 ((match-extract-vars _ (k ...) i v) (k ... v)) 738 ((match-extract-vars ___ (k ...) i v) (k ... v)) 739 ((match-extract-vars *** (k ...) i v) (k ... v)) 740 ((match-extract-vars ..1 (k ...) i v) (k ... v)) 741 ;; This is the main part, the only place where we might add a new 742 ;; var if it's an unbound symbol. 743 ((match-extract-vars p (k ...) (i ...) v) 744 (let-syntax 745 ((new-sym? 746 (syntax-rules (i ...) 747 ((new-sym? p sk fk) sk) 748 ((new-sym? any sk fk) fk)))) 749 (new-sym? random-sym-to-match 750 (k ... ((p p-ls) . v)) 751 (k ... v)))) 752 )) 753 754;; Stepper used in the above so it can expand the CAR and CDR 755;; separately. 756 757(define-syntax match-extract-vars-step 758 (syntax-rules () 759 ((_ p k i v ((v2 v2-ls) ...)) 760 (match-extract-vars p k (v2 ... . i) ((v2 v2-ls) ... . v))) 761 )) 762 763(define-syntax match-extract-quasiquote-vars 764 (syntax-rules (quasiquote unquote unquote-splicing) 765 ((match-extract-quasiquote-vars (quasiquote x) k i v d) 766 (match-extract-quasiquote-vars x k i v (#t . d))) 767 ((match-extract-quasiquote-vars (unquote-splicing x) k i v d) 768 (match-extract-quasiquote-vars (unquote x) k i v d)) 769 ((match-extract-quasiquote-vars (unquote x) k i v (#t)) 770 (match-extract-vars x k i v)) 771 ((match-extract-quasiquote-vars (unquote x) k i v (#t . d)) 772 (match-extract-quasiquote-vars x k i v d)) 773 ((match-extract-quasiquote-vars (x . y) k i v d) 774 (match-extract-quasiquote-vars 775 x 776 (match-extract-quasiquote-vars-step y k i v d) i () d)) 777 ((match-extract-quasiquote-vars #(x ...) k i v d) 778 (match-extract-quasiquote-vars (x ...) k i v d)) 779 ((match-extract-quasiquote-vars x (k ...) i v d) 780 (k ... v)) 781 )) 782 783(define-syntax match-extract-quasiquote-vars-step 784 (syntax-rules () 785 ((_ x k i v d ((v2 v2-ls) ...)) 786 (match-extract-quasiquote-vars x k (v2 ... . i) ((v2 v2-ls) ... . v) d)) 787 )) 788 789 790;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;; 791;; Gimme some sugar baby. 792 793;;> Shortcut for @scheme{lambda} + @scheme{match}. Creates a 794;;> procedure of one argument, and matches that argument against each 795;;> clause. 796 797(define-syntax match-lambda 798 (syntax-rules () 799 ((_ (pattern . body) ...) (lambda (expr) (match expr (pattern . body) ...))))) 800 801;;> Similar to @scheme{match-lambda}. Creates a procedure of any 802;;> number of arguments, and matches the argument list against each 803;;> clause. 804 805(define-syntax match-lambda* 806 (syntax-rules () 807 ((_ (pattern . body) ...) (lambda expr (match expr (pattern . body) ...))))) 808 809;;> Matches each var to the corresponding expression, and evaluates 810;;> the body with all match variables in scope. Raises an error if 811;;> any of the expressions fail to match. Syntax analogous to named 812;;> let can also be used for recursive functions which match on their 813;;> arguments as in @scheme{match-lambda*}. 814 815(define-syntax match-let 816 (syntax-rules () 817 ((_ ((var value) ...) . body) 818 (match-let/helper let () () ((var value) ...) . body)) 819 ((_ loop ((var init) ...) . body) 820 (match-named-let loop () ((var init) ...) . body)))) 821 822;;> Similar to @scheme{match-let}, but analogously to @scheme{letrec} 823;;> matches and binds the variables with all match variables in scope. 824 825(define-syntax match-letrec 826 (syntax-rules () 827 ((_ ((var value) ...) . body) 828 (match-let/helper letrec () () ((var value) ...) . body)))) 829 830(define-syntax match-let/helper 831 (syntax-rules () 832 ((_ let ((var expr) ...) () () . body) 833 (let ((var expr) ...) . body)) 834 ((_ let ((var expr) ...) ((pat tmp) ...) () . body) 835 (let ((var expr) ...) 836 (match-let* ((pat tmp) ...) 837 . body))) 838 ((_ let (v ...) (p ...) (((a . b) expr) . rest) . body) 839 (match-let/helper 840 let (v ... (tmp expr)) (p ... ((a . b) tmp)) rest . body)) 841 ((_ let (v ...) (p ...) ((#(a ...) expr) . rest) . body) 842 (match-let/helper 843 let (v ... (tmp expr)) (p ... (#(a ...) tmp)) rest . body)) 844 ((_ let (v ...) (p ...) ((a expr) . rest) . body) 845 (match-let/helper let (v ... (a expr)) (p ...) rest . body)))) 846 847(define-syntax match-named-let 848 (syntax-rules () 849 ((_ loop ((pat expr var) ...) () . body) 850 (let loop ((var expr) ...) 851 (match-let ((pat var) ...) 852 . body))) 853 ((_ loop (v ...) ((pat expr) . rest) . body) 854 (match-named-let loop (v ... (pat expr tmp)) rest . body)))) 855 856;;> @subsubsubsection{@rawcode{(match-let* ((var value) ...) body ...)}} 857 858;;> Similar to @scheme{match-let}, but analogously to @scheme{let*} 859;;> matches and binds the variables in sequence, with preceding match 860;;> variables in scope. 861 862(define-syntax match-let* 863 (syntax-rules () 864 ((_ () . body) 865 (let () . body)) 866 ((_ ((pat expr) . rest) . body) 867 (match expr (pat (match-let* rest . body)))))) 868 869 870;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;; 871;; Otherwise COND-EXPANDed bits. 872 873;; This *should* work, but doesn't :( 874;; (define-syntax match-check-ellipsis 875;; (syntax-rules (...) 876;; ((_ ... sk fk) sk) 877;; ((_ x sk fk) fk))) 878 879;; This is a little more complicated, and introduces a new let-syntax, 880;; but should work portably in any R[56]RS Scheme. Taylor Campbell 881;; originally came up with the idea. 882(define-syntax match-check-ellipsis 883 (syntax-rules () 884 ;; these two aren't necessary but provide fast-case failures 885 ((match-check-ellipsis (a . b) success-k failure-k) failure-k) 886 ((match-check-ellipsis #(a ...) success-k failure-k) failure-k) 887 ;; matching an atom 888 ((match-check-ellipsis id success-k failure-k) 889 (let-syntax ((ellipsis? (syntax-rules () 890 ;; iff `id' is `...' here then this will 891 ;; match a list of any length 892 ((ellipsis? (foo id) sk fk) sk) 893 ((ellipsis? other sk fk) fk)))) 894 ;; this list of three elements will only match the (foo id) list 895 ;; above if `id' is `...' 896 (ellipsis? (a b c) success-k failure-k))))) 897 898 899;; This is portable but can be more efficient with non-portable 900;; extensions. This trick was originally discovered by Oleg Kiselyov. 901 902(define-syntax match-check-identifier 903 (syntax-rules () 904 ;; fast-case failures, lists and vectors are not identifiers 905 ((_ (x . y) success-k failure-k) failure-k) 906 ((_ #(x ...) success-k failure-k) failure-k) 907 ;; x is an atom 908 ((_ x success-k failure-k) 909 (let-syntax 910 ((sym? 911 (syntax-rules () 912 ;; if the symbol `abracadabra' matches x, then x is a 913 ;; symbol 914 ((sym? x sk fk) sk) 915 ;; otherwise x is a non-symbol datum 916 ((sym? y sk fk) fk)))) 917 (sym? abracadabra success-k failure-k))))) 918