match.upstream.scm 37 KB

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