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~
             args| 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|