Concept:PatternMatchingPattern matching in SchemePattern matching is an essential idea in functional programming, with almost every functional language having some form of matching data against a certain set of requirements and shapes. Scheme is no exception. This pages gives an overview of pattern matching syntaxes proposed by SRFIs and included by some implementations. SRFI-200?, SRFI-201?, and SRFI-202?This family of SRFIs makes a review of many other pattern matching syntaxes and recommends a unified syntax working across most match syntaxes here: pat ::= identifier anything, and binds identifier
| _ anything
| () the empty list
| #t #t
| #f #f
| string a string
| number a number
| character a character
| 'sexp an s-expression
| 'symbol a symbol (special case of s-expr)
| `qp a quasi-pattern
qp ::= () the empty list
| #t #t
| #f #f
| string a string
| number a number
| character a character
| identifier a symbol
| (qp_1 ... qp_n) list of n elements
| (qp_1 ... qp_n . qp_{n+1}) list of n or more
of remainder must match qp_n+1
| ,pat a pattern
However, the prime SRFI in the series, SRFI-200, was withdrawn. This makes the whole family inherently non-portable. SRFI-204?Wright-Cartwright-Shinn matcher SRFI is probably the most influential and widely-implemented pattern-matching syntax. Despite being ultimately withdrawn. Provided forms are:
The syntax is pat : patvar ;; anything, and binds patvar
| _ ;; anything
| () ;; the empty list
| #t ;; #t
| #f ;; #f
| string ;; a string
| number ;; a number
| character ;; a character
| 'sexp ;; an s-expression
| 'symbol ;; a symbol (special case of s-expr)
| (pat1 ... patN) ;; list of n elements
| (pat1 ... patN . patN+1) ;; list of n or more
| (pat1 ... patN patN+1 ooo) ;; list of n or more, each element
;; of remainder must match patN+1
| (pat1 ... patN patN+1 ooo patN+2 ... patM)
;; list of m or more, every element between the
;; nth and the (m or more - n)th must match
;; patN+1.
| #(pat1 ... patN) ;; vector of n elements
| #(pat1 ... patN patN+1 ooo) ;; vector of n or more, each element
;; of remainder must match patN+1
| #(pat1 ... patN patN+1 ooo patN+2 ... patM)
;; vector of m or more, every element between the
;; nth and the (m or more - n)th must match
;; patN+1.
| ($ record-type pat1 ... patN) ;; a record (patK matches in slot
;; order) optional
| (struct struct-type pat1 ... patN) ;; ditto (*) optional
| (object struct-type (slot1 pat1) ...) ;; a record (using slot names) (*)
;; optional
| (= proc pat) ;; apply proc, match the result to pat
| (and pat ...) ;; if all of pats match
| (or pat ...) ;; if any of pats match
| (not pat ...) ;; if no pats match
| (? predicate pat ...) ;; if predicate true and all pats match
| (set! patvar) ;; anything, and binds setter
| (get! patvar) ;; anything, and binds getter
| (pat1 *** pat2) ;; tree subpattern (*)
| `qp ;; a quasi-pattern
(*) extended syntax not originally part of
Wright-Cartwright pattern matcher.
patvar : an identifier except _, quote, $, struct, @, object, =, and, or,
not, ?, set!, get!, quasiquote, ..., ___, **1, =.., *..
unquote, unquote-splicing.
ooo : ... ;; zero or more
| ___ ;; zero or more
| **1 ;; one or more
| =.. k ;; exactly k where k is an integer. (*)
;; Example: =.. 1, =.. 2 ...
| *.. k j ;; between k and j, where k and j are (*)
;; integers. Example: *.. 3 4, match 3
;; or 4 of a pattern *.. 1 5 match from
;; 1 to 5 of a pattern
(*) extended syntax not originally part of
Wright-Cartwright pattern matcher.
Note: a list can contain only one ellipsis pattern which includes the
patterns above, tail patterns, and unquote-splicing patterns.
qp : () ;; the empty list
| #t ;; #t
| #f ;; #f
| string ;; a string
| number ;; a number
| character ;; a character
| identifier ;; a symbol
| (qp_1 ... qp_n) ;; list of n elements
| (qp_1 ... qp_n . qp_{n+1}) ;; list of n or more
| (qp_1 ... qp_n qp_n+1 ooo) ;; list of n or more, each element
;; of remainder must match qp_n+1
| #(qp_1 ... qp_n) ;; vector of n elements
| #(qp_1 ... qp_n qp_n+1 ooo) ;; vector of n or more, each element
;; of remainder must match qp_n+1
| ,pat ;; a pattern
| ,@pat ;; a pattern
Alex Shinn's match.scm implements that standard (and some more!) in portable Scheme: https://synthcode.com/scheme/match.scm While his match-simple.scm implements a minimally useful subset of features in just 80 lines: https://synthcode.com/scheme/match-simple.scm pat : patvar
| _
| ()
| 'sexp
| (pat1 ... patN)
| (pat1 ... patN . patN+1)
| (pat1 ... patN patN+1 ___) ;; ___ is zero-or-more ellipsis
| #(pat1 ... patN)
| #(pat1 ... patN patN+1 ___)
| (and pat ...)
| (or pat ...)
| (not pat)
| (? predicate pat ...)
SRFI-239While SRFI-239 is much narrower in scope, only focusing on list destructuring, it is a kind of pattern matcher too.
The only provided form is (list-case ⟨expression⟩ ⟨list-case clause⟩ …) Where the possible clause shapes are [(⟨variable⟩ . ⟨variable⟩) ⟨body⟩]
[() ⟨body⟩]
[⟨variable⟩ ⟨body⟩]
While this is a pretty minimal syntax, it caters to a frequent pattern of destructuring pairs. Most of the other pattern matching syntaxes are majorly used to destructure lists, anyway. SRFI-241?Extends over SRFI-200 syntax, while also adding new SRFI-257?SRFI-257 suggest an extendable ⟨atomic datum⟩
_
⟨match pattern identifier⟩
(quote ⟨datum⟩)
(quasiquote ⟨match quasipattern⟩)
T[()] ⟹ (quote ())
T[⟨atomic datum⟩] ⟹ ⟨atomic datum⟩
T[(unquote ⟨mp⟩)] ⟹ ⟨mp⟩
T[((unquote-splicing ⟨mp⟩))] ⟹ ⟨mp⟩
T[((unquote-splicing ⟨mp⟩) . ⟨mqp⟩)] ⟹ (~append ⟨mp⟩ T[⟨mqp⟩])
T[(⟨mqp1⟩ . ⟨mqp2⟩)] ⟹ (~cons T[⟨mqp1⟩] T[⟨mqp2⟩])
T[#(⟨mqp⟩*)] ⟹ (~vector T[⟨mqp1⟩]*)
(~value ⟨expression⟩)
(~cons ⟨mpa⟩ ⟨mpd⟩)
(~list ⟨mp⟩ …)
(~append ⟨mp⟩ …)
(~append/ng ⟨mp⟩ …)
(~append/t ⟨datum⟩ ⟨mp1⟩ ⟨mp2⟩)
(~etc ⟨mp⟩)
(~etcse ⟨mp⟩)
(~vector ⟨mp⟩ …)
(~vector-append ⟨mp⟩ …)
(~vector-append/ng ⟨mp⟩ …)
(~string ⟨mp⟩ …)
(~string-append ⟨mp⟩ …)
(~string-append/ng ⟨mp⟩ …)
(~vector->list ⟨mp⟩)
(~string->list ⟨mp⟩)
(~list->vector ⟨mp⟩)
(~list->string ⟨mp⟩)
(~string->symbol ⟨mp⟩)
(~symbol->string ⟨mp⟩)
(~string->number ⟨mp⟩)
(~string->number ⟨mp⟩ ⟨rx⟩)
(~number->string ⟨mp⟩)
(~number->string ⟨mp⟩ ⟨rx⟩)
(~null? ⟨mp⟩ …)
(~pair? ⟨mp⟩ …)
(~list? ⟨mp⟩ …)
(~boolean? ⟨mp⟩ …)
(~number? ⟨mp⟩ …)
(~integer? ⟨mp⟩ …)
(~vector? ⟨mp⟩ …)
(~string? ⟨mp⟩ …)
(~symbol? ⟨mp⟩ …)
(~char? ⟨mp⟩ …)
(~and ⟨mp⟩ …)
(~or ⟨mp⟩ …)
(~not ⟨mp⟩)
(~cut! ⟨mp⟩)
(~list* ⟨mp⟩ … ⟨mpt⟩)
(~list-no-order ⟨mp⟩ …)
(~list-no-order* ⟨mp⟩ … ⟨mpt⟩)
(~= ⟨fn⟩ ⟨mp⟩)
(~? ⟨fn⟩ ⟨mp⟩ …)
(~prop ⟨fn⟩ => ⟨mp⟩ …)
(~prop ⟨fn⟩ (⟨arg⟩ …) => ⟨mp⟩ …)
(~test ⟨fn⟩)
(~test ⟨fn⟩ (⟨arg⟩ …))
(~test ⟨fn⟩ => ⟨mp⟩)
(~test ⟨fn⟩ (⟨arg⟩ …) => ⟨mp⟩)
(~iterate ⟨start⟩ ⟨head⟩ ⟨tail⟩ (⟨var⟩…) ⟨mp⟩)
(~if-id-member ⟨id⟩ ( ⟨literal-id⟩ …) ⟨mpt⟩ ⟨mpf⟩)
(~replace-specials ⟨new ...⟩ ⟨new _⟩ ⟨mp⟩)
SRFI-262?Withdrawn. Friedman-Hilsdale-Dybvig matcher Pat ::= (Pat ... . Pat)
| (Pat . Pat)
| ()
| #(Pat* Pat ... Pat*)
| #(Pat*)
| ,Id
| ,[Id*]
| ,[Cata -> Id*]
| Id
ChickenThe most prevalent library in Chicken ecosystem is https://wiki.call-cc.org/eggref/5/matchable The syntax and the provided forms are roughly these of Wright-Cartwright-Shinn GuileGuile provides Wright-Cartwright-Shinn forms and pattern syntax in https://doc.guix.gnu.org/guile/latest/en/html_node/Pattern-Matching.html ChibiSchemeChibi provides its own http://www.synthcode.com/scheme/chibi/lib/chibi/match.html The most notable extensions are the ability to use non-linear patterns -
patterns in which the same identifier occurs multiple times,
tail patterns after ellipsis, and the experimental tree patterns.
Bigloo and STklosImplementations provide two forms: <atom> the <atom>.
| (kwote <atom>) any expression eq? to <atom>.
| (and <pat1> ... <patn>) if all of <pati> match.
| (or <pat1> ... ...<patn>) if any of <pat1> through <patn> matches.
| (not <pat>) if <pat> doesn't match.
| (? <predicate>) if <predicate> is true.
| (<pat1> ... <patn>) a list of n elements. Here, ... is a
meta-character denoting a finite repetition
of patterns.
| <pat> ... a (possibly empty) repetition
of <pat> in a list.
| #(<pat> ... <patn>) a vector of n elements.
| #{<struct> <pat> ... } a structure.
| ?<id> anything, and binds id as a variable.
| ?- anything.
| ??- any (possibly empty) repetition of anything
in a list.
| ???- any end of list.
STklos also has a re-implementation of Alex Shinn's match-simple, but with a slightly extended grammar and ability to check two patterns for equality by repeating their variable name. It's available as pat : patvar
| _
| ()
| #t ;; #t
| #f ;; #f
| string ;; a string
| number ;; a number
| character ;; a character
| :keyword ;; a keyword symbol
| 'sexp
| (pat1 ... patN)
| (pat1 ... patN . patN+1)
| (pat1 ... patN patN+1 ___) ;; ___ is zero-or-more ellipsis
;; ___ is also available as ...
| #(pat1 ... patN)
| #(pat1 ... patN patN+1 ___)
| (and pat ...)
| (or pat ...)
| (not pat)
| (? predicate pat ...)
SkintThe only pattern matching implementation supported by Skint is SRFI-257?. GerbilThe syntax, as described in SRFI-200, is: (? test) ; predicate test with the `?` predicate constructor
(? test pattern) ; test and match a pattern
(? test => pattern) ; test and match a pattern on the value of the test
(? test :: proc => pattern) ; test and match with a filter
(and pattern ...) ; match all patterns
(or pattern ...) ; match any pattern
(not pattern) ; negated match
(cons pattern1 pattern2) ; destructure a pair like cons
(cons* pattern ... pattern-tail) ; destructure a list like cons*
[pattern ...] ;
(@list pattern ...) ; destructure a list like @list
(box pattern) ;
#&pattern ; destructure a box
(values pattern ...) ; destructure a values tuple
(vector pattern ...) ;
#(pattern ...) ; destructure a vector
(struct-id pattern ...) ; destructure a struct
(class-id (slot pattern) ...) ; destructure a class
(eq? val) ; match eq? to val
(eqv? val) ; match eqv? to val
(equal? val) ; match equal? to val
(quote expr) ; match eq?/eqv?/equal? to a quoted value
(quasiquote datum) ; destructure with quasiquote
(apply getf pattern) ; applicative destructuring
(match-macro arg ...) ; apply match macro expander
_ ; match any and ignore
id ; match any and bind to id
datum ; match eq?/eqv?/equal? to a datum
MoshMosh ships a "Pattern match library written by Alex Shinn" | About This SiteHome Alphabetical Indexa b c d e f g h i j k l m n o p q r s t u v w x y z other ConceptsConcept:CaseSensitivity Concept:DocumentationFormat Concept:ExtendedLambdaList Concept:FileSystem Concept:FindAndAnyInCollection Concept:ForeignInterface Concept:HashTable Concept:Module Concept:Networking Concept:ObjectSystem Concept:PatternMatching Concept:Process Concept:RegularExpression Concept:Type Concept:UserGroup Implementations
External Links |