(hamster mmatch) is an extensible modular pattern matcher for Scheme objects written in R6RS standard Scheme. Copyright (c) 2016, 2017, 2022 Tim Chadburn. Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.3 or any later version published by the Free Software Foundation; with no Invariant Sections, no Front-Cover Texts, and no Back-Cover Texts. A copy of the license is included in the file "fdl.txt" which is part of this package. Once mmatch.ss and misc-utils.ss are properly installed in your Scheme implementation's library directory, you can access this library by adding (hamster mmatch) to your import list. Contents -------- 2. Basic Usage Tutorial 3. Description of Architecture: The parts of (hamster mmatch) and how they fit together. 4. Pattern Matcher Utilities: The interface between the front-end "pattern matchers" and back-end "match- procedures". 5. Pattern Matcher Procedures: These are what the user calls when he wants to do some pattern matching. 6. Convenience Stuff: Shorthand and abbreviations, premade lists of match-procedures, and other useful stuff. 7. Supplied Match Procedures: Definitions of pattern matching syntax and functionality. a. Predicate Match Procedures b. Recursive Match Procedures 8. Methods for Wrapping Predicate Match Procedures: Predicate MPs need turning into recursives in order to be used. Here's how it's done. 9. Procedures for Building Match Procedures: Functions which are used to build match procedures but aren't MPs themselves. 2. Basic Usage Tutorial ----------------------- We can do some pattern matching with (hamster mmatch)'s standard set of functionality using the procedure smatch. It looks like this: (smatch pattern object) A pattern and object match if they are equal? to one another: (smatch 1 1) => #t (smatch 1 2) => #f (smatch "abc" "abc") => #t (smatch "abc" "def") => #f The pattern ? matches any object: (smatch '? 1) => #t (smatch '? "horse") => #t (smatch 1 '?) => #f Pairs and lists match if their contents match: (smatch '(1 2) '(1 2)) => #t (smatch '(? ?) '(1 2)) => #t (smatch '(1 2 3) '(1 2)) => #f (smatch '(2 2) '(1 2) => #f The pattern _ matches anything and returns its object, so that any pattern containing _ will return the object the _ matches if the match as a whole is true: (smatch '_ 1) => 1 (smatch '(1 _) '(1 2)) => 2 (smatch '(1 _) '(2 2)) => #f If we want to match multiple elements of a list, we can follow a pattern in the list with the symbol ... ; this will match any number of instances of the pattern before the ... , including zero. (smatch '(1 ...) '(1 1 1 1)) => #t (smatch '(1 ... 2) '(1 1 2)) => #t (smatch '(1 ... 2) '(2)) => #t (smatch '(? ...) '(1 2 3 4) => #t (smatch '(_ ? ...) '(1 2 3) => 1 (smatch '(_ ...) '(1 2 3) => (1 2 . 3) (smatch '(2 1 ...) '(1 1) => #f The variable stdtp is a list of symbols bound to the type predicates which exist in the R6RS standard. If we use one of these symbols as a pattern, it will match any object for which the type predicate would return #t. (smatch 'number? 1) => #t (smatch '(string? number?) '("pigeon" 8)) => #t (smatch '(number? string?) '("pigeon" 8)) => #f (smatch 'list? '(1 2 3)) => #t 3. Description of Architecture ------------------------------ (hamster mmatch) consists of two types of modular component: the match-procedures, each of which embodies a particular piece of pattern matching functionality and syntax, and the pattern matcher itself, which defines high-level behaviour and co-ordination. There are two types of match procedure: the two-argument "predicate" and the four-argument "recursive". The predicates are used where it is unnecessary for the particular procedure to call the pattern matcher recursively or manage its own method of returning values. The predicate match procedure takes (pattern object) as its arguments and returns a value whose truth states whether, according to the functionality the procedure represents, the two match or not. The recursive match procedure takes (rmatch pattern object . extra). rmatch is a procedure representing the pattern matcher which exists so that the pattern matcher's behaviour can be propagated through recursive calls; whenever a recursive wants to call the pattern matcher, it should call rmatch, not a particular pattern matcher. rmatch takes (pattern object). extra exists so that certain specialized match procedures can receive extra information from the user; most match procedures accept but ignore this extra information. All match procedures must return a true value if, according to the functionality the procedure represents, its pattern and object match, or #f if they don't. For a predicate match procedure, the exact value of the true value is unimportant; only the value's truth matters. For a recursive match procedure, whether a true value returned is #t or another true value makes quite a difference: #t merely indicates that the pattern and object match, while another true value indicates that that value is to be returned from the overall pattern match. Existing match procedures include mmatch-equal?, which returns true if pattern and object are equal? and #f otherwise; mmatch-pair, which returns true if both pattern and object are pairs, the car of pattern and the car of object match and the cdr of pattern and the cdr of object match, and #f otherwise; mmatch-?, which returns true if pattern is eq? to the symbol ?, and #f otherwise; mmatch-_, which returns object if pattern is eq? to the symbol _, and #f otherwise; mmatch-type-predicate, which returns true if pattern can be found in the list stdtp and the procedure it is bound to returns true when applied to object, and #f otherwise. As you can hopefully see, each match-procedure is not responsible for the whole match, but only its own little part, and when that part is not relevant to the pattern and object, the match procedure returns #f and plays no part in that particular match. Of course, match procedures also return #f when they are relevant but their functionality deems the pattern and object not to match. The pattern matching functionality to use in a particular match is defined by passing a list of match procedures to the pattern matcher. These embody the functionality that will be used. Most pattern matchers then pass this list of match procedures to call-match-procs which does the actual calling of the match procedures in the list and finds and returns an appropriate return value. See the description of call-match-procs below, in section 4, "Pattern Matcher Utilities", for exactly how it does this. The list of match procedures passed to (hamster mmatch) must all be recursives: predicates must be wrapped using mmatch-2argproc which manages the things that predicates don't bother to define themselves using a suitable standard framework. If the predicate returns true, #t is returned by the wrapper. Pattern matcher procedures generally consist entirely of a sub-procedure defined with named let called rmatch, taking (pattern object) as stated above. The pattern and object of the pattern matcher are passed to rmatch for its initial argument values. rmatch then passes itself as the rmatch argument to call-match-procs, call-match-proc, or whatever the pattern matcher uses to interface with the match-procedures. 4. Pattern Matcher Utilities ---------------------------- (call-match-proc proc arg ...) proc must be either #f or a procedure capable of being called with the args as its arguments. If proc is true, it will be called with the args as its arguments, and the result will be returned. If proc is false, #f is returned. This procedure is usually called like this: (call-match-proc mp rmatch pattern object) where mp is a recursive match procedure which will be called with (rmatch pattern object) as its arguments. (call-match-procs procs arg ...) procs must be a list, each element of which is either #f or a procedure capable of being called with the args as its arguments. Each procedure in the list will be called in order with the args as its arguments until one of these calls returns true, in which case that value is returned, or the end of the list is reached, in which case #f is returned. This procedure is usually called like this: (call-match-procs mpl rmatch pattern object) where mpl is a list of recursive match procedures, each of which will be called with (rmatch pattern object) as its arguments until one returns true or the end of the list is reached. 5. Pattern Matcher Procedures ----------------------------- (mmatch procs pattern object) mmatch does nothing but call call-match-procs (see immediately above). (double-mmatch procs pattern object) This calls call-match-procs, and if that returns #f, calls call-match-procs again with the pattern and object swapped round (so that the pattern is used as the object and the object is used as the pattern). E.g.: (double-mmatch stdmp '_ 1) => 1 (double-mmatch stdmp 2 '_) => 2 (double-mmatch stdmp '(? 4) '(3 _)) => 4 (priority-mmatch rightprocs wrongprocs pattern object) This is similar to double-mmatch in that the pattern and object can be swapped around if the initial match fails. priority-mmatch takes two lists of match procedures. rightprocs are the procedures which are applied when pattern and object are the right way round; wrongprocs are the procedures which are applied when the two are swapped. The two lists must be the same length; they can be padded with #f. priority-mmatch goes down the two lists at once; for each position, the procedure from rightprocs is called with the pattern and object the right way round, then if that fails, the wrongproc is called with the pattern and object swapped round. If either returns true, priority-mmatch returns that true value and calls no more match-procedures; if the end of the lists is reached, #f is returned. priority-mmatch keeps track of all the swaps so that it always knows which way round it is relative to the original call. 6. Convenience Stuff -------------------- stdmp stdmp is a list of match procedures representing a kind of "standard" functionality; if a match-proc is general-purpose and doesn't break anything, it goes in this list. nsmp Neutralized Standard Match Procedures: this is like stdmp, but with its return capabilities disabled. This is used with priority-mmatch as the "wrongprocs" when one only wishes returns to occur when the pattern and object are the right way round. stdtp STanDard Type Predicates: This is a list of symbols bound to the type predicates which exist in the R6RS standard. (smatch pattern object) Equivalent to (mmatch stdmp pattern object). (psmatch pattern) Returns a procedure of one argument, object, which will return (smatch pattern object). (rpsmatch object) Returns a procedure of one argument, pattern, which will return (smatch pattern object). (make-psmatch smatch) Returns a procedure of one argument, pattern, which itself returns a procedure of one argument, object, which will return (smatch pattern object). Note that smatch here refers to the argument to make-psmatch, not the above defined smatch. (make-rpsmatch smatch) Returns a procedure of one argument, object, which itself returns a procedure of one argument, pattern, which will return (smatch pattern object). (double-smatch pattern object) Equivalent to (double-mmatch stdmp pattern object). (priority-smatch pattern object) Equivalent to (priority-mmatch stdmp nsmp pattern object) . (double-psmatch pattern) Returns a procedure of one argument, object, which will return (double-smatch pattern object). (double-rpsmatch object) Returns a procedure of one argument, pattern, which will return (double-smatch pattern object). 7. Supplied Match Procedures ---------------------------- 7a. Predicate Match Procedures ------------------------------ For predicate match procedures, the name of the wrapped version is given, but the functionality of the predicate only is described. mmatch-? Returns #t if the pattern is ?, else #f. mmatch-equal? Identical to equal? mmatch-type-predicate If pattern is an element of stdtp, it is assumed to be a symbol bound to a valid type predicate and the procedure it is bound to is called with object as its only argument. Otherwise #f is returned. 7b. Recursive Match Procedures ------------------------------ mmatch-pair If both pattern and object are pairs, calls rmatch with the car of both pattern and object, and again with the cdr of both pattern and object. If either call returns #f, mmatch-pair returns #f. If both return #t, mmatch-pair returns #t. If one call returns #t and the other returns a different true value, the different true value is returned. If both return a non-#t true value, mmatch-pair conses them together, the result of the car call first, and returns the newly created pair. mmatch-return If pattern is (r pat), mmatch-return will call (rmatch pat object), and if this returns true, mmatch-return will return object. So, for instance, (smatch '(r ?) 1) will return 1. mmatch-return-neutralized If pattern is (r pat), mmatch-return-neutralized will call (rmatch pat object). In other words, it is the same as if the pattern were pat. No return is caused. mmatch-_ If pattern is the symbol _ , the object is returned unconditionally. E.g. (smatch '_ 1) returns 1, (smatch '(1 _) '(1 2)) returns 2, etc. mmatch-... If (cadr pattern) is ... , the first two elements of pattern match any number of instances of (car pattern), including zero. For instance, (smatch '(1 ...) '(1 1 1)) returns #t; (smatch '(1 ... 2 3) '(1 1 2 3)) returns #t; (smatch '(_ ...) '(4 3 2)) returns (4 3 . 2); (smatch '(stuff ...) '()) returns #t; (smatch '(1 2 3 ...) '(1 2 3)) returns #t. The system for returning values is similar to that of mmatch-pair; both use the `fall-through' procedure to calculate their return value (see section 9, Procedures for Building Match Procedures). mmatch-flip If the car of either pattern or object is / , the pattern and object are swapped around from that point onwards. If the / was in the pattern, the object it tried to match against becomes the first object in the new pattern, with the object after the / being the first object in the new object, and vice versa. E.g.: (smatch '(1 / ?) '(1 2)) returns #f; (smatch '(1 / 2) '(1 ?)) returns #t. (smatch '(1 2) '(1 / ?)) returns #t; (smatch '(2) '(/ _)) returns 2. 8. Methods for Wrapping Predicate Match Procedures -------------------------------------------------- (mmatch-2argproc extra? proc) This returns a procedure taking four arguments (rmatch pattern object . extra). The new procedure will call (proc pattern object). If that returns true, #t is returned. If that returns #f, #f is returned. extra? should be #f. (wrapmp extra? name proc) This is shorthand for and equivalent to (define name (mmatch-2argproc extra? proc)). 9. Procedures for Building Match Procedures ------------------------------------------- (fall-through car-result get-cdr-result) This provides a common return mechanism for match-procedures that match pairs, regardless of how they work out the results of the matches representing the car and cdr sides of the pair. car-result must be the result of the match representing the car side of the pair. get-cdr-result must be a procedure of no arguments which, when called, performs the match representing the cdr side of the pair and returns its result. get-cdr-result is not called if car-result is #f. After obtaining the cdr-result, fall-through then calculates the return value as described under mmatch-pair. (make-mmatch-return active?) This allows two versions of mmatch-return to exist, the normal version which returns its object if the match succeeds and the neutralized version which merely returns the result of the match. active? is a boolean value; if active? is true, the normal version is returned, else the neutralized version is. (make-mmatch-type-predicate import-specs tps) This allows versions of mmatch-type-predicate to be created with different lists of type predicates than the standard, stdtp. import-specs must be a list of import specifiers. The argument tps must be a list of symbols which are bound to type predicates within the environment described by import-specs.