phm/nitrate: Scheme procedure-based pattern matcher - Codeberg.org

head| meta| @| charset| utf-8
 link| @| href| https://florida.moe/assets/treeside-simple.css
 rel| stylesheet
 type| text/css
nh1| nitrate — Combinator Based Pattern Matcher
{href `https://codeberg.org/phm/nitrate` Git repository (latest)}
Releases:
dl|
 dt| bleeding-edge
 dd| {href `https://codeberg.org/phm/nitrate` Git repository}
 dt| 2.0
 dd| {href `https://codeberg.org/phm/nitrate/src/tag/2.0` Git repository}
 dd| {href `https://florida.moe/nitrate/nitrate-2.0.html` manual}
 dd| {href `https://florida.moe/nitrate/nitrate-2.0.tgz` Release tarball}
 dt| 1.0
 dd| {href `https://codeberg.org/phm/nitrate/src/tag/1.0` Git repository}
 dd| {href `https://florida.moe/nitrate/nitrate-1.0.html` manual}
 dd| {href `https://florida.moe/nitrate/nitrate-1.0.tgz` Release tarball}
Nitrate is a combinator (procedure) based backtracking pattern
matcher. Being procedure based, as opposed to syntax based, the matcher
is extensible with any predicate or record type and its basic components
are composable and can represent recursive structure. Designed for
{R7RS}-small systems without fancy macro systems or optimizers.
This could also be called monadic
pattern matching or a parser-combinator library for Scheme values.
Nitrate has been tested to work on CHICKEN 5 and Chibi Scheme.
the-table-of-contents|
nh2| Why a Procedure-Based Pattern Matcher?
Scheme has no standard pattern matcher. A commonly used one is the
"Wright" pattern matcher, with a notable `syntax-rules` implementation
using CPS macros by Alex Shinn. Such patterns matchers are not extensible.
Some proposals for high-end, extensible pattern matchers include {SRFI
257} and {SRFI 262}.
These matchers are all at the syntax level and are very difficult to
implement. A static-typed language like Standard
ML or {href `https://www.haskell.org/` Haskell} requires a matcher as
a syntactic construct because it has no way to discriminate against sum types.
But Scheme is a latently typed language, so it does not have this issue.
Higher-order procedures should be able to do the same thing that pattern
matching syntax can, with the added benefit of easy extensibility.
This procedure-based pattern matcher is very composable. For instance,
the pattern {idref or~} could be defined as:
code| pre|
 (define {idref or~}
 (case-lambda
 (() {idref _~})
 ((x~) x~)
 ((x~ . spats) ({idref if~} x~ {idref _~} (apply {idref or~} spats)))))
This code almost looks like how one would write `or` in a call-by-name
version of Scheme. Since procedures are composed before matching, the
code that makes up the patterns passed to {idref or~} are not run until
then.
The composition is done over a finite list (the argument list), hence the
recursion is done at a meta-level to the matching. But with this system,
one can also write recursive patterns at the matching level. Consider the
following possible implementation of {idref member~}:
 code| pre|
 ({idref define-recpat} (member~ pat~)
 ({idref or~} ({idref cons~} pat~ {idref _~}) ({idref cons~} {idref _~} (member~ pat~))))
The macro {idref define-recpat} uses an eta-expansion trick to allow for
a composition of matching procedures to be recursive.
A procedure-based pattern matcher would have a uniform syntax for matching
any structured data. This may make the basic case of lists and vectors less
ergonomic than a specalized solution, but this could encourage people to
use abstract patterns instead of concrete ones.
One thing that a procedure-based pattern matcher can't do that a syntactic
pattern matcher can is to bind values to identifiers, because identifiers
are a syntactic construct. This has its upsides, though: a binding can
appear zero or more times, and the client code can extract values as
desired.
nh2| Design of the Matcher
The matcher is a depth-first, left-to-right traversal. Many {R7RS}-small
systems are not going to take much opportunity to optimize anyways by
re-arranging the evaulation order, so by fixing an evaluation order the
matcher can express things such as cuts.
The matcher threads an immutable map through the match. Its immutability
makes it easy to backtrack. The map is returned at the end of the match.
The matcher procedures either return the map, or `#f`.
The matcher also threads a dynamic state through the match, roughly
equivalent to `parameterize` but will always tail-call its pattern.
The default matcher is `call/cc` safe. That means that a matcher using
only the procedures here can be entered and exited multiple times. This
could be used, for instance, to match one branch, do some processing, and
cut back to try another match if something goes wrong in the client code.
nh3| Future Directions
One idea is to use identifiers ({R6RS}) instead of symbols. This would
make the patterns easier to read and help with possible scope and
hygiene issues. A more radical change would be to use {SRFI 247} style
syntactic monads.
Another possibility is to do a version of {SRFI 262} lowered to the
procedure level. SRFI 262 is designed to be compilable efficiently,
which suggests a route for optimizing compilers: given a pattern (i.e.
in a procedure), lift it such that it only needs to be evaluated once,
evaluate derived matching procedures into matching primitives (maybe
record types), optimize the primitives, and then output a matching
procedure with compiler hints to aggresively inline.
nh2| Examples
An example of a toy expander for the R4RS special forms is bundled in
the repository in the `examples` folder.
Match a list with specified atoms:
code| pre|
 (define (one-two-three-four lst)
 ({idref match} lst dict
 (({idref list~} 1 2 3 4) #t)
 ({idref _~} #f)))
 (one-two-three-four '(1 2 3 4)) ; => #t
 (one-two-three-four '#(1 2 3 4)) ; => #f
Match a list, mapping values to symbols:
code| pre|
 (define (simple lst)
 ({idref match} lst dict
 (({idref list~} 1 ({idref b~} 'second) 3) (car (dict-ref (dto) dict 'second)))
 ({idref _~} #f)))
 (simple '(1 100 3)) ; => 100
 (simple '(1 100 5~~ ; => #f
Match as many numbers at the head of a list as possible:
code| pre|
 (define (leading lst)
 ({idref match} lst dict
 (({idref not~} ({idref ?~} pair?)) (values '() '()))
 (({idref list*~} ({idref and~} ({idref ?~} number?) ({idref b~} 'n)) ({idref b~} 'rest))
 (values (dict-ref/default (dto) dict 'n '())
 (car (dict-ref (dto) dict 'rest))))))
 (leading '(1 2 3 4)) ; => (values '(1 2 3 4) '())
 (leading '(1 2 3 x y 5)) ;=> (values '(1 2 3) '(x y 5))
 (leading '(x 1 2)) ; => (values '() '(x 1 2))
 (leading 'abcd) ; => (values '() '())
Partition a list using a predicate:
code| pre|
 (define (partition predicate? lst)
 ({idref match} lst dict
 (({idref list*~} ({idref or~} ({idref and~} ({idref ?~} predicate?) ({idref b~} 'hit))
 ({idref b~} 'miss))
 '())
 (values (dict-ref/default (dto) dict 'hit '())
 (dict-ref/default (dto) dict 'miss '())))))
 (partition positive? '(1 2 3 -5 -6 7 8 -9))
 ; => (values '(1 2 3 7 8) '(-5 -6 -9))
nh2| API
nh3| High-Level Matching
feature|
 syntax| {name match} {non-terminal expression} {non-terminal identifier} {gstar ({non-terminal pattern} {non-terminal body})}
 Each {non-terminal pattern} must evaluate to something that can be
 passed to {idref mt}. This is generally a matching procedure.
 Matches {non-terminal expression} to each of the {non-terminal pattern}
 in turn. If a match results in a success, bind the resulting dictionary
 to {non-terminal identifier}, with all entries in left-to-right matching
 order, and tail-evaluate {non-terminal body} with {non-terminal identifier}
 in scope.
feature|
 syntax| {name match-pr} {non-terminal expression} ({non-terminal identifier{sub 1}} {non-terminal identifier{sub 2}}) {gstar ({non-terminal pattern} {non-terminal body})}
 Like {idref match}, except instead of binding the dictionary to an identifier:
 li| the identifier {non-terminal identifer{sub 1}} is bound to a procedure
 `(r x [d])`. It looks up the symbol `x` in the dictionary, returning
 the resulting list, or `d` (defaults to the empty list) if not found.
 li| the identifier {non-terminal identifier{sub 2}} is bound to a procedure
 `(r1 x [d])`. It looks up the symbol `x` in the dictionary, returning
 the first matched result, or `d` (defaults to `#f`) if not found.
feature|
 syntax| {name match-rev} {non-terminal expression} {non-terminal identifier} {gstar ({non-terminal pattern} {non-terminal body})}
 Like {idref match}, except that the dictionary is returned without
 transforming the order of the bound values.
nh3| Dictionaries
{index {l {e `dict`}} {ref `dict` argument parameter definition}}
All procedure arguments that start with {label `dict` `dict`} or are described as dictionaries must
be objects that are {code (dictionary? ({ref dto}) dict)} when
passed to the procedure.
nh4| dto
This object is the global, immutable {SRFI 225} DTO.
nh4| empty-dict
This object is the global, immutable dict corresponding to the {SRFI 225} DTO.
nh3| Shorthands
feature|
 syntax| {name define-recpat} {non-terminal define-head} {non-terminal body}
 Define an eta-expanded composition of matching procedures. This is useful
 to express recursive pattern matching that would normally cause a call-by-value
 evaulation order to loop forever.
 For example, consider the following matcher:
 code| pre|
 ({idref define-recpat} (member~ pat~)
 ({idref or~} ({idref cons~} pat~ {idref _~}) ({idref cons~} {idref _~} (member~ pat~))))
 If this was defined using `define`, then `(member~ pat~)` would loop
 forever as it will call `(member~ pat~)` again. The `define-recpat` version
 is equivalent to
 code| pre|
 (define (member~ pat~)
 (lambda (dict input)
 ({idref or~} ({idref cons~} pat~ {idref _~}) ({idref cons~} {idref _~} (member~ pat~)))))
 Hence the evaluation of `(member~ pat~)` stops at the `lambda`.
feature|
 syntax| {name matcher-wrapper} ({non-terminal predicate} {gplus {non-terminal accessor}})
 All the arguments to the macro must evaluate to procedures.
 Create a procedure that in turn creates matching procedures.
 The procedure takes the same number of arguments as {non-terminal
 accessor}s, which must be matching procedures.
 The procedure returns a matching procedure that fails if the passed
 value does not satisfy {non-terminal predicate}. Otherwise, it
 matches the first {non-terminal accessor} with the input dictionary,
 the second {non-terminal accessor} with the returned dictionary, and
 so on, returning the result of the final {non-terminal accessor}. The
 final {non-terminal accessor} is called in the tail-position.
nh3| Matching
{index {l {e `~`}} {ref `tilde` naming convention}}
{label `tilde` Identifers ending with `~` are either values that can be
passed to {idref `mt`}, or procedures that create values that can be
passed to {idref `mt`}.}
feature|
 procedure| name| mt
 args| pred| `tilde` mat~
 pred| `dict` dict
 pred| `dict` dyn
 name| input
 returns| name| {ref `dict` dict}/#f
 Matches {var mat~} against {var input}.
 li| If {var mat~} is a procedure, then tail-call
 the underlying procedure with {var dict} and {var input} as arguments.
 li| If the {var mat~} is `equal?` to {var input}, return the input dict.
 li| Otherwise, return false.
nh3| Unconditional Matchers
feature|
 procedure| name| b~
 args| name| symbol
 opt| name| procedure
 returns| name| procedure?
 Creates a matcher that unconditionally matches the passed value.
 
 The returned dictionary maps {var symbol} to a list where the head is
 `(procedure value)`,
 and {var value} is the passed value. If {var procedure} is not given,
 the default is the identity function.
 If the only variable bindings in the matche are made with this procedure,
 then the resulting dictionary will have the bindings of the match in
 reverse order.
feature|
 procedure| name| _~
 args| pred| `dict` dict
 name| input
 returns| pred| `dict` dict
 A matching procedure that always suceeds and returns the input
 dictionary.
feature|
 procedure| name| fail~
 args| pred| `dict` dict
 name| input
 A matching procedure that always fails.
nh3| Conditional Matchers
feature|
 procedure| name| if~
 args| name| test~
 name| consequent~
 name| alternative~
 returns| name| `procedure?`
 Try to match {var test~}. 
 
 If the match of {var test~} succeeds, try to match
 {var consequent~} in the tail-position with the returned dictionary.
 Otherwise try to match {var alternative~} in the tail-position with
 the input dictionary.
feature|
 procedure| name| if*~
 args| rep| name| test~
 name| consequent~
 An analogue of `cond`. Equivalent to:
 code| pre|
 ({idref if~} test{sub 1}~ consequent{sub 1}~
 ({idref if~} test{sub 2}~ consequent{sub 2}~
 ({idref if~} ... {idref fail~})))
feature|
 procedure| name| and~
 args| rep| pred| `tilde` pat~
 returns| name| `procedure?`
 Create a matching procedure that will try to match the first {var pat~},
 and then match the second {var pat~} with the same input and the
 dictionary of the first {var pat~}, and so on. If one fails, the entire
 match fails. The final {var pat~} is tail-called.
feature|
 procedure| name| or~
 args| rep| pred| `tilde` pat~
 returns| name| `procedure?`
 Create a matching procedure that tries each {var pat~} in sequence
 against the same input and dictionary. If a match fails, the next match
 is tested. If a match succeeds, return the dictionary from it. If no
 match succeeds, the match fails. The final {var pat~} is tail-called.
feature|
 procedure| name| not~
 args| pred| `tilde` pat~
 returns| name| `procedure?`
 Create a matching procedure that will fail if {var pat~} succeeds, and
 suceed with the input dictionary if {var pat~} fails.
feature|
 procedure| name| opt~
 args| pred| `tilde` pat~
 returns| name| `procedure?`
 Creating a matching procedure that matches {var pat~} against the input.
 If the match succeeds, return the value. Otherwise return the input
 dictionary.
 The maching procedure always succeeds.
feature|
 procedure| name| as-many~
 args| rep| pred| `tilde` pat~
 returns| name| `procedure?`
 Creates a matching procedure that attempts to match each {var pat~}
 against the input. The successful matches are merged from left to right.
 The maching procedure always succeeds.
nh3| Calling Scheme Procedures
feature|
 procedure| name| ?~
 args| name| procedure
 returns| name| `procedure?`
 Creates a matching procedure that will pass its input to {var procedure}.
 If {var procedure} returns false, the match fails. Otherwise return the
 input {ref `dict` dictionary} unchanged.
feature|
 procedure| name| inspect~
 args| name| predicate
 returns| name| `procedure?`
 Creates a matching procedure that calls {var predicate} with one argument,
 the input dictionary. If {var predicate} returns false, the match fails.
 Otherwise return the input {ref `dict` dictionary} unchanged.
feature|
 procedure| name| xfrm~
 args| name| procedure
 name| pat~
 returns| name| `procedure?`
 Creates a matching procedure that tail-calls {var pat~} with the output
 of calling {var procedure} on the input value.
nh3| Numbers
feature|
 procedure| name| =~
 args| name| x
 returns| name| `procedure?`
 Creates a matching procedure that will succeed only if the input is
 a number that is numerically equal to {var x}. The procedure will
 return an empty {ref `dict` dictionary} for a succesful match.
feature|
 procedure| name| =Reps~
 args| name| eps
 name| x
 returns| name| `procedure?`
 Creates a matching procedure that will succeed only if the input is
 a number that is less than {var eps} in distance from {var x}, measured
 by absolute value. The returned dictionary is the input dictionary.
feature|
 procedure| name| signmag~
 args| name| sign~
 name| mag~
 returns| name| `procedure?`
 Creates a matching procedure that will succeed if the input is a real
 number, and the sign (as `-1`, or `1`) matches {var sign~}, and
 the magnitude (as a non-negative real number) matches {var mag~}.
 Exact zero and inexact positive zero have a positive sign. Inexact
 negative zero, if it exists, has a negative sign.
feature|
 procedure| name| =eps~
 args| name| eps
 name| x
 returns| name| `procedure?`
 Like {idref =Reps~}, except that non-real values are supported and
 compared using magnitude.
feature|
 library| (nitrate complex)
 procedure| name| rect~
 args| name| real~
 name| imag~
 returns| name| `procedure?`
 Matches a complex number with real part {var real~} and imaginary part
 {var imag~}.
feature|
 library| (nitrate complex)
 procedure| name| polar~
 args| name| magnitude~
 name| angle~
 returns| name| `procedure?`
 Matches a complex number with magnitude {var magnitude~} and angle
 {var angle~}.
feature|
 library| (nitrate rational)
 procedure| name| rat~
 args| name| numerator~
 name| denominator~
 returns| name| `procedure?`
 Matches a rational number with numerator {var numerator~} and
 denominator {var denominator~}.
nh3| Lists and Pairs
feature|
 procedure| name| cons~
 args| pred| `tilde` car~
 pred| `tilde` cdr~
 returns| name| `procedure?`
 Creates a matching procedure that will succeed only if the input is a
 pair whose car matches {var car~} and whose cdr matches {var cdr~}.
 The matcher for {var cdr~} is tail-called.
feature|
 procedure| name| cons~*
 args| pred| `tilde` pat~{sub 1}
 rep| pred| `tilde` pat~{sub n}
 opt| pred| `tilde` tail~
 returns| name| `procedure?`
 Equivalent to
 code| pre|
 ({idref cons~} pat~{sub 1} ({idref cons~} pat~{sub 1} (... ({idref cons~} pat~{sub 1} tail~))))
feature|
 procedure| name| list~
 args| rep| pred| `tilde` pat~
 returns| name| `procedure?`
 Like {idref `cons~*`}, except the tail must be the empty list.
feature|
 procedure| name| list-tail~
 args| name| n
 pred| `tilde` pat~
 returns| name| `procedure?`
 Creates a matching procedure that matches the input if the input is
 a possibly improper list of at least {var n} elements, whose {var n}th cdr
 matches {var pat~}. The matching of {var pat~} occurs in tail-position.
feature|
 procedure| name| list-ref~
 args| name| n
 pred| `tilde` pat~
 returns| name| `procedure?`
 Equivalent to:
 code| pre|
 ({idref list-tail~} n (cons pat~ {idref _~}))
feature|
 procedure| name| member-tail~
 args| pred| `tilde` pat~
 returns| name| `procedure?`
 Creates a matching procedure that will match the first cdr of the
 possibly improper input list where some cdr of the list matches
 {var pat~}. If there is no such cdr, the match fails. Otherwise the
 dictionary returned is the one returned from {var pat~}.
feature|
 procedure| name| member~
 args| pred| `tilde` pat~
 returns| name| `procedure?`
 Equivalent to
 code| pre|
 ({idref member-tail~} ({idref cons~} pat~ {idref _~}))
feature|
 procedure| name| assoc~
 args| pred| `tilde` key~
 opt| pred| `tilde` val~
 returns| name| `procedure?`
 If {var val~} is absent, defaults to {idref _~}. Equivalent to
 code| pre|
 ({idref member~} ({idref cons~} key~ val~))
feature|
 procedure| name| list*~
 args| pred| `tilde` pat~
 pred| `tilde` tail~
 returns| name| `procedure?`
 Matchs {var pat~} greedily over the elements of the input list. Once
 {var pat~} fails, then try to match {var tail~} on the remaining list.
nh3| Vectors
feature|
 procedure| name| vector~
 args| rep| pred| `tilde` pat~
 returns| name| `procedure?`
 Return a matcher procedure that will succeed when the input is a vector
 that has the same number of elements as the arguments to this procedure.
 Each {var pat~} is matched to the corresponding element in the vector
 from left to right, passing the returned dictionaries alogn the way.
 The final {var pat~} is matched in tail-position. The match fails if any
 match fails.
feature|
 procedure| name| vector-ref~
 args| name| n
 pred| `tilde` pat~
 returns| name| `procedure?`
 Returns a matcher procedure that will succeed when the input is a vector
 with a length greater than {var n} and whose {var n}th element satisfies
 {var pat~}. The {var pat~} is matched in tail-position.
nh2| Version Changes
nh3| 1.0.0 to 2.0.0
The design of the library was simplified. The disjoint record
`matcher-procedure` was removed, along with all parameter objects. The
DTO is now global and hence much easier for a program to optimize without
having to do whole program analysis.
Matchers now return `#f` when they fail. There is no backtracking with
`call/cc` at all.
nh2| Copyright
© Peter McGoron 2026
Permission to use, copy, modify, and/or distribute this software for
any purpose with or without fee is hereby granted.
THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL
WARRANTIES WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES
OF MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE
FOR ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY
DAMAGES WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN
AN ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT
OF OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
nh2| Index
the-index|