((section 2 "Outdated egg!" (p "This is an egg for CHICKEN 4, the unsupported old release.  You're almost certainly looking for " (int-link "/eggref/5/matchable" "the CHICKEN 5 version of this egg") ", if it exists.") (p "If it does not exist, there may be equivalent functionality provided by another egg; have a look at the " (link "https://wiki.call-cc.org/chicken-projects/egg-index-5.html" "egg index") ". Otherwise, please consider porting this egg to the current version of CHICKEN.") (tags "egg")) (section 2 "matchable" (p "This extension implements Andrew Wright's pattern matching macros.") (toc) (section 3 "Overview" (p "Pattern matching allows complicated control decisions based on data structure to be expressed in a concise manner.  Pattern matching is found in several modern languages, notably Standard ML, Haskell and Miranda.") (p "This wiki page is based on Andrew Wright's paper " (link "http://download.plt-scheme.org/doc/103p1/pdf/match.pdf" "Pattern Matching for Scheme") ".")) (section 3 "Interface" (def (sig (syntax "(match exp (pat body …) …)" (id match))) (p "The basic form of pattern matching expression, where " (tt "exp") " is an expression, " (tt "pat") " is a pattern, and " (tt "body") " is one or more expressions (like the body of a lambda-expression). The " (tt "match") " form matches its first subexpression against a sequence of patterns, and branches to the " (tt "body") " corresponding to the first pattern successfully matched.") (p "For example, the following code defines the usual " (tt "map") " function:") (highlight scheme "(define map\n  (lambda (f l)\n    (match l\n      [() '()]\n      [(x . y) (cons (f x) (map f y))] )))") (p "The first pattern " (tt "()") " matches the empty list.  The second pattern " (tt "(x . y)") " matches a pair, binding " (tt "x") " to the first component of the pair and " (tt "y") " to the second component of the pair.")) (def (sig (syntax "(match-lambda  (pat body …) …)" (id match-lambda)) (syntax "(match-lambda* (pat body …) …)" (id match-lambda*))) (p "The " (tt "match-lambda") " and " (tt "match-lambda*") " forms are convenient combinations of " (tt "match") " and " (tt "lambda") ", and can be explained as follows:") (highlight scheme "(match-lambda  (pat body …) …)\n  --> (lambda (x) (match x (pat body …) …))\n\n(match-lambda* (pat body …) …)\n  --> (lambda x   (match x (pat body) …))") (p "where " (tt "x") " is a unique variable.") (p "The " (tt "match-lambda") " form is convenient when defining a single argument function that immediately destructures its argument. The " (tt "match-lambda*") " form constructs a function that accepts any number of arguments; the patterns of " (tt "match-lambda*") " should be lists.") (p "For example, the " (tt "map") " procedure can be written as:") (highlight scheme "(define map\n  (match-lambda*\n    [(_ ()) '()]\n    [(f (x . y)) (cons (f x) (map f y))] ))")) (def (sig (syntax "(match-let [var] ((pat exp) …) body …)" (id match-let)) (syntax "(match-let*      ((pat exp) …) body …)" (id match-let*)) (syntax "(match-letrec    ((pat exp) …) body …)" (id match-letrec))) (p "The " (tt "match-let") ", " (tt "match-let*") " and " (tt "match-letrec") " forms generalize Scheme's " (tt "let") ", " (tt "let*") ", " (tt "letrec") ", and " (tt "define") " expressions to allow patterns in the binding position rather than just variables. For example, the following expression:") (highlight scheme "(match-let (((x y z) (list 1 2 3)))\n            ((a b c) (list 4 5 6)))\n  body …)") (p "binds " (tt "x") " to 1, " (tt "y") " to 2, " (tt "z") " to 3, " (tt "a") " to 4, " (tt "b") " to 5, and " (tt "c") " to 6 in " (tt "body …") ".  These forms are convenient for destructuring the result of a function that returns multiple values as a list or vector.  As usual for " (tt "letrec") ", pattern variables bound by " (tt "match-letrec") " should not be used in computing the bound value.") (p "Analogously to named " (tt "let") ", " (tt "match-let") " accepts an optional loop variable " (tt "var") " before the binding list, turning " (tt "match-let") " into a general looping construct."))) (section 3 "Pattern Matching Expressions" (p "The complete syntax of the pattern matching expressions follows:") (pre "exp ::= (match exp clause …)\n     |  (match-lambda clause …)\n     |  (match-lambda* clause …)\n     |  (match-let ([pat exp] …) body)\n     |  (match-let* ([pat exp] …) body)\n     |  (match-letrec ([pat exp] …) body)\n     |  (match-let var ([pat exp] …) body)") (pre "clause ::= [pat body]\n     |  [pat (=> identifier) body]") (pre "pat ::= identifier           matches anything, and binds identifier as a variable\n     |  _                    anything\n     |  ()                   itself (the empty list)\n     |  #t                   itself\n     |  #f                   itself\n     |  string               an `equal?' string\n     |  number               an `equal?' number\n     |  character            an `equal?' character\n     |  's-expression        an `equal?' s-expression\n     |  (pat-1 … pat-n)    a proper list of n elements\n     |  (pat-1 … pat-n . pat-n+1)  \n                             a list of n or more elements\n     |  (pat-1 … pat-n pat-n+1 ...)  \n                             a proper list of n+k or more elements [1]\n     |  #(pat-1 … pat-n)   a vector of n elements\n     |  #(pat-1 … pat-n pat-n+1 ...)  \n                             a vector of n+k or more elements\n     |  ($ struct pat-1 … pat-n)  \n                             a structure\n     |  (= field pat)        a field of a structure\n     |  (and pat-1 … pat-n)  \n                             if all of pat-1 through pat-n match\n     |  (or pat-1 … pat-n) \n                             if any of pat-1 through pat-n match\n     |  (not pat-1 … pat-n)\n                             if none of pat-1 through pat-n match\n     |  (? predicate pat-1 … pat-n)  \n                             if predicate true and pat-1 through pat-n all match\n     |  (set! identifier)    anything, and binds identifier as a setter\n     |  (get! identifier)    anything, and binds identifier as a getter\n     |  (pat-1 *** pat-2)    a tree pattern\n     |  `qp                  a quasipattern") (pre "qp ::= ()                    itself (the empty list)\n    |  #t                    itself\n    |  #f                    itself\n    |  string                an `equal?' string\n    |  number                an `equal?' number\n    |  character             an `equal?' character\n    |  symbol                an `equal?' symbol\n    |  (qp-1 … qp-n)       a proper list of n elements\n    |  (qp-1 … qp-n . qp-n+1)  \n                             a list of n or more elements\n    |  (qp-1 … qp-n qp-n+1 ...)  \n                             a proper list of n+k or more elements\n    |  #(qp-1 … qp-n)      a vector of n elements\n    |  #(qp-1 … qp-n qp-n+1 ...)  \n                             a vector of n+k or more elements\n    |  ,pat                  a pattern\n    |  ,@pat                 a pattern, spliced") (section 4 "Optional \"=>\" failure procedure syntax" (p "The " (tt "match") ", " (tt "match-lambda") ", and " (tt "match-lambda*") " forms allow the optional syntax " (tt "(=> identifier)") " between the pattern and the body of a clause.  When the pattern match for such a clause succeeds, the " (tt "identifier") " is bound to a " (i "failure procedure") " of zero arguments within the " (tt "body") ".  If this procedure is invoked, it jumps back to the pattern matching expression, and resumes the matching process as if the pattern had failed to match.  The " (tt "body") " must not mutate the object being matched, otherwise unpredictable behavior may result."))) (section 3 "Patterns" (dl (dt (tt "identifier")) (dd "matches anything, and binds a variable of this name to the matching value in the " (tt "body") ".  Excludes the reserved names " (tt "? , = _ ... and or not set! get!") ".") (dt (tt "_")) (dd "matches anything, without binding any variables.") (dt (tt "()") ", " (tt "#t") ", " (tt "#f") ", " (tt "string") ", " (tt "number") ", " (tt "character") ", '" (tt "s-expression")) (dd "These constant patterns match themselves, i.e., the corresponding value must be " (tt "equal?") " to the pattern.") (dt (tt "(pat-1 … pat-n)")) (dd "matches a proper list of " (tt "n") " elements that match " (tt "pat-1") " through " (tt "pat-n") ".") (dt (tt "(pat-1 … pat-n . pat-n+1)")) (dd "matches a (possibly improper) list of at least " (tt "n") " elements that ends in something matching " (tt "pat-n+1") ".") (dt (tt "(pat-1 … pat-n pat-n+1 ...)")) (dd "matches a proper list of " (tt "n") " or more elements, where each element of the tail matches " (tt "pat-n+1") ".  Each pattern variable in " (tt "pat-n+1") " is bound to a list of the matching values.  For example, the expression:")) (highlight scheme "(match '(let ([x 1][y 2]) z)\n  [('let ((binding values) ...) exp)  body ...])") (p "binds " (tt "binding") " to the list " (tt "'(x y)") ", " (tt "values") " to the list " (tt "'(1 2)") ", and " (tt "exp") " to " (tt "'z") " in the body of the " (tt "match") "-expression. For the special case where " (tt "pat-n+1") " is a pattern variable, the list bound to that variable may share with the matched value.") (dl (dt (tt "(pat-1 … pat-n pat-n+1 ___)")) (dd "This pattern means the same thing as the previous pattern.") (dt (tt "#(pat-1 … pat-n)")) (dd "matches a vector of length " (tt "n") ", whose elements match " (tt "pat-1") " through " (tt "pat-n") ".") (dt (tt "#(pat-1 … pat-n pat-n+1 ...)")) (dd "matches a vector of length " (tt "n") " or more, where each element beyond " (tt "n") " matches " (tt "pat-n+1") ".") (dt (tt "($ struct pat-1 … pat-n)")) (dd "matches a structure declared with " (tt "define-record") " or " (tt "define-record-type") ".") (dt (tt "(= field pat)")) (dd "is intended for selecting a field from a structure.  " (i "field") " may be any expression; it is applied to the value being matched, and the result of this application is matched against " (tt "pat") ".") (dt (tt "(and pat-1 … pat-n)")) (dd "matches if all of the subpatterns match. At least one subpattern must be present. This pattern is often used as " (tt "(and x pat)") " to bind " (tt "x") " to to the entire value that matches " (tt "pat") " (cf. " (i "as-patterns") " in ML or Haskell).") (dt (tt "(or pat-1 … pat-n)")) (dd "matches if any of the subpatterns match. At least one subpattern must be present. All subpatterns must bind the same set of pattern variables.") (dt (tt "(not pat-1 … pat-n)")) (dd "matches if none of the subpatterns match. At least one subpattern must be present. The subpatterns may not bind any pattern variables.") (dt (tt "(? predicate pat-1 … pat-n)")) (dd "In this pattern, " (tt "predicate") " must be an expression evaluating to a single argument function. This pattern matches if " (tt "predicate") " applied to the corresponding value is true, and the subpatterns " (tt "pat-1 ... pat-n") " all match. The " (tt "predicate") " should not have side effects, as the code generated by the pattern matcher may invoke predicates repeatedly in any order. The " (tt "predicate") " expression is bound in the same scope as the match expression, i.e., free variables in " (tt "predicate") " are not bound by pattern variables.") (dt (tt "(set! identifier)")) (dd "matches anything, and binds " (tt "identifier") " to a procedure of one argument that mutates the corresponding field of the matching value. This pattern must be nested within a pair, vector, box, or structure pattern. For example, the expression:")) (highlight scheme "(define x (list 1 (list 2 3)))\n(match x [(_ (_ (set! setit)))  (setit 4)])") (p "mutates the " (tt "cadadr") " of " (tt "x") " to 4, so that " (tt "x") " is " (tt "'(1 (2 4))") ".") (dl (dt (tt "(get! identifier)")) (dd "matches anything, and binds " (tt "identifier") " to a procedure of zero arguments that accesses the corresponding field of the matching value.  This pattern is the complement to " (tt "set!") ". As with " (tt "set!") ", this pattern must be nested within a pair, vector, box, or structure pattern.") (dt (tt "`qp")) (dd "Quasiquote introduces a quasipattern, in which identifiers are considered to be symbolic constants.  Like Scheme's quasiquote for data, " (tt "unquote") " (,) and " (tt "unquote-splicing") " (,@) escape back to normal patterns."))) (section 3 "Record Structures Pattern" (p "The " (tt "$") " pattern handles native record structures and " (link "http://srfi.schemers.org/srfi-9/srfi-9.html" "SRFI-9") " records transparently.")) (section 3 "Tree Pattern" (p "Here we allow patterns of the form") (pre " (x *** y)") (p "to represent the pattern y located somewhere in a tree where the path from the current object to y can be seen as a list of the form (X …).  Y can immediately match the current object in which case the path is the empty list.  In a sense it's a 2-dimensional version of the ... pattern.") (p "As a common case the pattern (_ *** y) can be used to search for Y anywhere in a tree, regardless of the path used."))) (section 2 "Examples" (p "You can find examples in:") (ul (li "the original " (link "http://download.plt-scheme.org/doc/103p1/pdf/match.pdf" "paper") " by Andrew Wright,") (li "introductory article " (link "http://ceaude.twoticketsplease.de/articles/an-introduction-to-lispy-pattern-matching.html" "An Introduction To Lispy Pattern Matching") " by Moritz Heidkamp."))) (section 2 "About this extension" (section 3 "Author" (p (int-link "/users/alex-shinn" "Alex Shinn"))) (section 3 "License" (p "Public domain")) (section 3 "History" (dl (dt "2.7") (dd "removed " (tt "match-define") " from documentation which is not provided by this egg (thanks to Juergen Lorenz for pointing this out)") (dt "2.6") (dd "better implementation of some internal forms for E/R macros") (dt "2.5") (dd "removed " (tt "-host") " option from setup script") (dt "2.4") (dd "fixing bug where (a ...) matched non-lists") (dt "2.3") (dd "allowing `...' with any backend, removing redundant check in vector patterns") (dt "2.2") (dd "uses srfi-46, if available (as it is in alexpander)") (dt "2.1") (dd "fixing quasiquote patterns") (dt "2.0") (dd "allowing ellipse patterns in other than the final position of a list") (dt "1.41") (dd "added syntax-error macro & specialized for Chicken [Kon Lovett]") (dt "1.3") (dd "updated to change in " (int-link "/eggref/3/syntactic-closures" "syntactic-closures") " 0.91") (dt "1.2") (dd "bugfix, now all tests pass with " (int-link "/eggref/3/syntactic-closures" "syntactic-closures")) (dt "1.1") (dd "works now with " (int-link "/eggref/3/syntactic-closures" "syntactic-closures")) (dt "1.0") (dd "initial release")))))