The shadchen Reference Manual

Table of Contents

Next: , Previous: , Up: (dir)   [Contents][Index]

The shadchen Reference Manual

This is the shadchen Reference Manual, generated automatically by Declt version 2.3 "Robert April" on Tue Feb 20 09:20:07 2018 GMT+0.


Next: , Previous: , Up: Top   [Contents][Index]

1 Introduction

Shadchen: A pattern matching library

shadchen: Noun
  matchmaker
from Yiddish

(note: there is an emacs lisp port of this library here) (note: if you are reading this README for the emacs version of the library, keep in mind that emacs symbols are case sensitive. Symbols are all lowercase in this library.)

I love pattern-matching, which I find to be a great way to combine destructuring data with type-checking when used in dynamic languages. If you aren't familiar with how pattern matching works, here is an example:

(defun second (lst)
 (match lst 
  ((cons _ (cons x rest)) x)))

MATCH introduces a pattern matching expression, which takes a value, in this case LST and a series of lists, whose first elements are descriptions of a data structure and whose subsequent elements are code to execute if the match succeeds. Pattern matching takes the description of the data and binds the variables that appear therein to the parts of the data structure they indicate. Above, we match _ to the car of a list, x to the car of that list's cdr, and rest to the cdr of that list.

If we don't pass in a list, the match fails. (Because of the behavior of CL's car and cdr, which return NIL on NIL, the form cons doesn't enforce a length requirement on the input list, and will return NIL for an empty list. This corresponds with the fact that in Common Lisp (car nil) is nil and (cdr nil) is nil.)

We might instead write:

(defun second-of-two (lst)
  (match lst
    ((list _ x) x)))

Which returns the second element of a list only when a two element list is passed in. MATCH can take multiple pattern/body sets, in which case patterns are tried in order until one pattern matches, and the result of evaluating the associated forms is returned. If no patterns match, an error is raised.

Built-in Patterns

Shadchen supports the following built-in patterns.

_

Matches anything, but no bindings are made.

<SYMBOL>

Matches anything, binding to that value in the body expressions.

<KEYwORD-LITERAL> 

Matches only when the value is the same keyword.

<NUMBER-LITERAL>

Matches only when the value is the same number.

<STRING-LITERAL>

Matches only when the value is string= is the same string.

(CONS <PATTERN1> <PATTERN2>)

Matches any CONS cell, or NIL, then matches <PATTERN1> and <PATTERN2>, executing the body in a context where their matches are bound. If the match value is NIL, then each PATTERN matches against NIL.

(LIST <P1> ... <PN>)

Matches a list of length N, then matches each pattern <PN> to the elements of that list.

(LIST-REST <P1> ... <PN> <REST-PATTERN)

Matches - to elements in at list, as in the LIST pattern. The final <REST-PATTERN> is matched against the rest of the list.

(QUOTE DATUM)

Only succeeds when DATUM is EQUALP to the match-value. Binds no values.

 (AND <P1> .. <PN>)

Tests all <PN> against the same value, succeeding only when all patterns match, and binding all variables in all patterns.

 (OR <P1> .. <PN>)

Tries each <PN> in turn, and succeeds if any <PN> succeeds. The body of the matched expression is then executed with that <PN>'s bindings. Each sub-pattern in an OR must bind an identical set of symbols or an error will be raised at compile time.

 (? PREDICATE <PATTERN>)

Succeeds when (FUNCALL PREDICATE MATCH-VALUE) is true and when <PATTERN> matches the value. Body has the bindings of <PATTERN>.

 (FUNCALL FUN <PATTERN>)

Applies FUN to the match value, then matches <PATTERN> against the result.

 (BQ EXPR)

Matches as if by BACKQUOTE. If EXPR is an atom, then this is equivalent to QUOTE. If EXPR is a list, each element is matches as in QUOTE, unless it is an (UQ <PATTERN>) form, in which case it is matched as a pattern. Eg:

(match (list 1 2 3)
  ((BQ (1 (UQ x) 2)) x)) 

Will succeed, binding X to 2.

(match (list 10 2 20)
   ((BQ (1 (UQ x) 2)) x))

Will fail, since 10 and 1 don't match.

(values <P1> ... <PN>)

Will match multiple values produced by a (values ...) form.

(let (n1 v1) (n2 v2) ... (nn vn))

Not a pattern matching pattern, per se. let always succeeds and produces a context where the bindings are active. This can be used to provide default alternatives, as in:

(defun non-nil (x) x)

(match (list 1) 
 ((cons hd (or (? #'non-nil tl)
               (let (tl '(2 3)))))
  (list hd tl)))

Will result in (1 (2 3)) but

(match (list 1 4) 
 ((cons hd (or (? #'non-nil tl)
               (let (tl '(2 3)))))
  (list hd tl)))

Will produce (1 (4)). Note that a similar functionality can be provided with funcall.

Extending shadchen

Users can define their own patterns using the defpattern form. For instance, the behavior of CONS, which matches the empty list, may not be desired. We can define a match which doesn't have this behavior as:

(defun non-nil (x) x)
(defpattern cons* (car cdr)
 `(? #'non-nil (cons ,car ,cdr)))

A pattern is a function which takes the arguments passed into the custom pattern, and expands them into a new pattern in the language of the built-in pattern-matching.

We can now say:

(match (cons 10 11)
 ((cons* a b) a)) 

Which will produce 10, but:

(match nil
 ((cons* a b) a))

Will raise a no-match error.

Judicious application of the matchers AND, FUNCALL, and ? allow the definition of arbitrary matchers without exposing the guts of the matching system.


Copyright 2012, Vincent Toups
This program is distributed under the terms of the GNU Lesser 
General Public License (see license.txt).

Next: , Previous: , Up: Top   [Contents][Index]

2 Systems

The main system appears first, followed by any subsystem dependency.


Previous: , Up: Systems   [Contents][Index]

2.1 shadchen

Maintainer

Vincent Toups

Author

Vincent Toups

Description

A pattern matching library.

Long Description

Shadchen (matchmaker) is a Racket-inspired pattern matching library.

Source

shadchen.asd (file)

Components

Next: , Previous: , Up: Top   [Contents][Index]

3 Files

Files are sorted by type and then listed depth-first from the systems components trees.


Previous: , Up: Files   [Contents][Index]

3.1 Lisp


Next: , Previous: , Up: Lisp files   [Contents][Index]

3.1.1 shadchen.asd

Location

shadchen.asd

Systems

shadchen (system)


Next: , Previous: , Up: Lisp files   [Contents][Index]

3.1.2 shadchen/package.lisp

Parent

shadchen (system)

Location

package.lisp

Packages

shadchen


Previous: , Up: Lisp files   [Contents][Index]

3.1.3 shadchen/shadchen.lisp

Dependency

package.lisp (file)

Parent

shadchen (system)

Location

shadchen.lisp

Exported Definitions
Internal Definitions

Next: , Previous: , Up: Top   [Contents][Index]

4 Packages

Packages are listed by definition order.


Previous: , Up: Packages   [Contents][Index]

4.1 shadchen

Source

package.lisp (file)

Nickname

s?

Use List

common-lisp

Exported Definitions
Internal Definitions

Next: , Previous: , Up: Top   [Contents][Index]

5 Definitions

Definitions are sorted by export status, category, package, and then by lexicographic order.


Next: , Previous: , Up: Definitions   [Contents][Index]

5.1 Exported definitions


Previous: , Up: Exported definitions   [Contents][Index]

5.1.1 Macros

Macro: defpattern NAME ARGS &body BODY
Package

shadchen

Source

shadchen.lisp (file)

Macro: defun-match NAME PATTERNS &body BODY
Package

shadchen

Source

shadchen.lisp (file)

Macro: defun-match- NAME PATTERNS &body BODY
Package

shadchen

Source

shadchen.lisp (file)

Macro: match VALUE &body FORMS

Attempt to match VALUE against each of the patterns in the CAR of FORMS. When a match is detected, its subsequent forms are executed as in a PROGN where the bindings implied by the match are in effect.

An error is thrown when no matches are found.

Package

shadchen

Source

shadchen.lisp (file)

Macro: match-lambda &body FORMS

Like MATCH except the VALUE is curried.

Package

shadchen

Source

shadchen.lisp (file)

Macro: match-let BINDINGS &body BODY

Just like let* but each symbol part of each binding can be a match expression of arbitrary complexity.

Package

shadchen

Source

shadchen.lisp (file)

Macro: match-let* BINDINGS &body BODY

Just like let* but each symbol part of each binding can be a match expression of arbitrary complexity.

Package

shadchen

Source

shadchen.lisp (file)

Macro: match-loop RECUR-POINT BINDINGS &body BODY

Like match-let but the binding form can be re-entered by calling
a local function indicated by ‘recur-point‘ with the same number of arguments as bindings expressions in BINDINGS.

Package

shadchen

Source

shadchen.lisp (file)


Previous: , Up: Definitions   [Contents][Index]

5.2 Internal definitions


Next: , Previous: , Up: Internal definitions   [Contents][Index]

5.2.1 Special variables

Special Variable: *extended-patterns*

Holds user declared patterns.

Package

shadchen

Source

shadchen.lisp (file)

Special Variable: *match-fail*
Package

shadchen

Source

shadchen.lisp (file)

Special Variable: *match-function-table*
Package

shadchen

Source

shadchen.lisp (file)


Next: , Previous: , Up: Internal definitions   [Contents][Index]

5.2.2 Macros

Macro: match-helper VALUE &body FORMS
Package

shadchen

Source

shadchen.lisp (file)

Macro: match1 MATCH-EXPRESSION MATCH-VALUE &body BODY
Package

shadchen

Source

shadchen.lisp (file)

Macro: named-let NAME BINDERS &body BODY
Package

shadchen

Source

shadchen.lisp (file)


Next: , Previous: , Up: Internal definitions   [Contents][Index]

5.2.3 Functions

Function: bq->regular-match BQ-EXPRESSION
Package

shadchen

Source

shadchen.lisp (file)

Function: calc-backquote-bindings EXPR

Calculate the bindings for a backquote expression.

Package

shadchen

Source

shadchen.lisp (file)

Function: calc-pattern-bindings EXPR

Given a shadchen pattern EXPR return a list of symbols bound by that expression.

Package

shadchen

Source

shadchen.lisp (file)

Function: calc-pattern-bindings-extended EXPR

Calculate the bound symbols of a user defined pattern.

Package

shadchen

Source

shadchen.lisp (file)

Function: calc-pattern-bindings-list EXPR &optional ACC
Package

shadchen

Source

shadchen.lisp (file)

Function: canonical-binding-list L
Package

shadchen

Source

shadchen.lisp (file)

Function: copy-match-fail-struct INSTANCE
Package

shadchen

Source

shadchen.lisp (file)

Function: equal-by-binding &rest PATTERNS
Package

shadchen

Source

shadchen.lisp (file)

Function: equal-by-binding2 P1 P2
Package

shadchen

Source

shadchen.lisp (file)

Function: extend-defun-match-table NAME LEXPR
Package

shadchen

Source

shadchen.lisp (file)

Function: extended-patternp PATTERN-HEAD

Return T if PATTERN-HEAD indicates a user provided pattern.

Package

shadchen

Source

shadchen.lisp (file)

Function: htbl-fetcher KEY
Package

shadchen

Source

shadchen.lisp (file)

Function: length=1 LST

Returns T when LST has one element.

Package

shadchen

Source

shadchen.lisp (file)

Function: make-match-fail-struct &key
Package

shadchen

Source

shadchen.lisp (file)

Function: mapcat F LST
Package

shadchen

Source

shadchen.lisp (file)

Function: match-?-expander MATCH-EXPRESSION MATCH-VALUE BODY
Package

shadchen

Source

shadchen.lisp (file)

Function: match-and-expander MATCH-EXPRESSION MATCH-VALUE BODY
Package

shadchen

Source

shadchen.lisp (file)

Function: match-and-expander* SUB-EXPRESSIONS MATCH-NAME BODY
Package

shadchen

Source

shadchen.lisp (file)

Function: match-backquote-expander MATCH-EXPRESSION MATCH-VALUE BODY
Package

shadchen

Source

shadchen.lisp (file)

Function: match-cons-expander MATCH-EXPRESSION MATCH-VALUE BODY
Package

shadchen

Source

shadchen.lisp (file)

Function: match-extended-pattern-expander MATCH-EXPRESSION MATCH-VALUE BODY
Package

shadchen

Source

shadchen.lisp (file)

Function: match-fail-struct-p OBJECT
Package

shadchen

Source

shadchen.lisp (file)

Function: match-funcall-expander MATCH-EXPRESSION MATCH-VALUE BODY
Package

shadchen

Source

shadchen.lisp (file)

Function: match-let-expander MATCH-EXPRESSION MATCH-VALUE BODY
Package

shadchen

Source

shadchen.lisp (file)

Function: match-list-expander MATCH-EXPRESSION MATCH-VALUE BODY
Package

shadchen

Source

shadchen.lisp (file)

Function: match-list-expander* SUB-EXPRESSIONS MATCH-VALUE BODY
Package

shadchen

Source

shadchen.lisp (file)

Function: match-literal-character MATCH-EXPRESSION MATCH-VALUE BODY
Package

shadchen

Source

shadchen.lisp (file)

Function: match-literal-keyword MATCH-EXPRESSION MATCH-VALUE BODY
Package

shadchen

Source

shadchen.lisp (file)

Function: match-literal-number MATCH-EXPRESSION MATCH-VALUE BODY
Package

shadchen

Source

shadchen.lisp (file)

Function: match-literal-string MATCH-EXPRESSION MATCH-VALUE BODY
Package

shadchen

Source

shadchen.lisp (file)

Function: match-must-match-expander MATCH-EXPR VAL-EXPR BODY
Package

shadchen

Source

shadchen.lisp (file)

Function: match-or-expander MATCH-EXPRESSION MATCH-VALUE BODY
Package

shadchen

Source

shadchen.lisp (file)

Function: match-or-expander-unsafe MATCH-EXPRESSION MATCH-VALUE BODY
Package

shadchen

Source

shadchen.lisp (file)

Function: match-quote-expander MATCH-EXPRESSION MATCH-VALUE BODY
Package

shadchen

Source

shadchen.lisp (file)

Function: match-values-expander MATCH-EXPRESSION MATCH-VALUE BODY
Package

shadchen

Source

shadchen.lisp (file)

Function: must-match-case MATCH-EXPR
Package

shadchen

Source

shadchen.lisp (file)

Function: non-keyword-symbol O
Package

shadchen

Source

shadchen.lisp (file)

Function: package-name* P
Package

shadchen

Source

shadchen.lisp (file)

Function: symbol< S1 S2
Package

shadchen

Source

shadchen.lisp (file)

Function: uq? E
Package

shadchen

Source

shadchen.lisp (file)


Previous: , Up: Internal definitions   [Contents][Index]

5.2.4 Structures

Structure: match-fail-struct ()
Package

shadchen

Source

shadchen.lisp (file)

Direct superclasses

structure-object (structure)


Previous: , Up: Top   [Contents][Index]

Appendix A Indexes


Next: , Previous: , Up: Indexes   [Contents][Index]

A.1 Concepts

Jump to:   F   L   S  
Index Entry  Section

F
File, Lisp, shadchen.asd: The shadchen<dot>asd file
File, Lisp, shadchen/package.lisp: The shadchen/package<dot>lisp file
File, Lisp, shadchen/shadchen.lisp: The shadchen/shadchen<dot>lisp file

L
Lisp File, shadchen.asd: The shadchen<dot>asd file
Lisp File, shadchen/package.lisp: The shadchen/package<dot>lisp file
Lisp File, shadchen/shadchen.lisp: The shadchen/shadchen<dot>lisp file

S
shadchen.asd: The shadchen<dot>asd file
shadchen/package.lisp: The shadchen/package<dot>lisp file
shadchen/shadchen.lisp: The shadchen/shadchen<dot>lisp file

Jump to:   F   L   S  

Next: , Previous: , Up: Indexes   [Contents][Index]

A.2 Functions

Jump to:   B   C   D   E   F   H   L   M   N   P   S   U  
Index Entry  Section

B
bq->regular-match: Internal functions

C
calc-backquote-bindings: Internal functions
calc-pattern-bindings: Internal functions
calc-pattern-bindings-extended: Internal functions
calc-pattern-bindings-list: Internal functions
canonical-binding-list: Internal functions
copy-match-fail-struct: Internal functions

D
defpattern: Exported macros
defun-match: Exported macros
defun-match-: Exported macros

E
equal-by-binding: Internal functions
equal-by-binding2: Internal functions
extend-defun-match-table: Internal functions
extended-patternp: Internal functions

F
Function, bq->regular-match: Internal functions
Function, calc-backquote-bindings: Internal functions
Function, calc-pattern-bindings: Internal functions
Function, calc-pattern-bindings-extended: Internal functions
Function, calc-pattern-bindings-list: Internal functions
Function, canonical-binding-list: Internal functions
Function, copy-match-fail-struct: Internal functions
Function, equal-by-binding: Internal functions
Function, equal-by-binding2: Internal functions
Function, extend-defun-match-table: Internal functions
Function, extended-patternp: Internal functions
Function, htbl-fetcher: Internal functions
Function, length=1: Internal functions
Function, make-match-fail-struct: Internal functions
Function, mapcat: Internal functions
Function, match-?-expander: Internal functions
Function, match-and-expander: Internal functions
Function, match-and-expander*: Internal functions
Function, match-backquote-expander: Internal functions
Function, match-cons-expander: Internal functions
Function, match-extended-pattern-expander: Internal functions
Function, match-fail-struct-p: Internal functions
Function, match-funcall-expander: Internal functions
Function, match-let-expander: Internal functions
Function, match-list-expander: Internal functions
Function, match-list-expander*: Internal functions
Function, match-literal-character: Internal functions
Function, match-literal-keyword: Internal functions
Function, match-literal-number: Internal functions
Function, match-literal-string: Internal functions
Function, match-must-match-expander: Internal functions
Function, match-or-expander: Internal functions
Function, match-or-expander-unsafe: Internal functions
Function, match-quote-expander: Internal functions
Function, match-values-expander: Internal functions
Function, must-match-case: Internal functions
Function, non-keyword-symbol: Internal functions
Function, package-name*: Internal functions
Function, symbol<: Internal functions
Function, uq?: Internal functions

H
htbl-fetcher: Internal functions

L
length=1: Internal functions

M
Macro, defpattern: Exported macros
Macro, defun-match: Exported macros
Macro, defun-match-: Exported macros
Macro, match: Exported macros
Macro, match-helper: Internal macros
Macro, match-lambda: Exported macros
Macro, match-let: Exported macros
Macro, match-let*: Exported macros
Macro, match-loop: Exported macros
Macro, match1: Internal macros
Macro, named-let: Internal macros
make-match-fail-struct: Internal functions
mapcat: Internal functions
match: Exported macros
match-?-expander: Internal functions
match-and-expander: Internal functions
match-and-expander*: Internal functions
match-backquote-expander: Internal functions
match-cons-expander: Internal functions
match-extended-pattern-expander: Internal functions
match-fail-struct-p: Internal functions
match-funcall-expander: Internal functions
match-helper: Internal macros
match-lambda: Exported macros
match-let: Exported macros
match-let*: Exported macros
match-let-expander: Internal functions
match-list-expander: Internal functions
match-list-expander*: Internal functions
match-literal-character: Internal functions
match-literal-keyword: Internal functions
match-literal-number: Internal functions
match-literal-string: Internal functions
match-loop: Exported macros
match-must-match-expander: Internal functions
match-or-expander: Internal functions
match-or-expander-unsafe: Internal functions
match-quote-expander: Internal functions
match-values-expander: Internal functions
match1: Internal macros
must-match-case: Internal functions

N
named-let: Internal macros
non-keyword-symbol: Internal functions

P
package-name*: Internal functions

S
symbol<: Internal functions

U
uq?: Internal functions

Jump to:   B   C   D   E   F   H   L   M   N   P   S   U  

Next: , Previous: , Up: Indexes   [Contents][Index]

A.3 Variables

Jump to:   *  
S  
Index Entry  Section

*
*extended-patterns*: Internal special variables
*match-fail*: Internal special variables
*match-function-table*: Internal special variables

S
Special Variable, *extended-patterns*: Internal special variables
Special Variable, *match-fail*: Internal special variables
Special Variable, *match-function-table*: Internal special variables

Jump to:   *  
S  

Previous: , Up: Indexes   [Contents][Index]

A.4 Data types

Jump to:   M   P   S  
Index Entry  Section

M
match-fail-struct: Internal structures

P
Package, shadchen: The shadchen package

S
shadchen: The shadchen system
shadchen: The shadchen package
Structure, match-fail-struct: Internal structures
System, shadchen: The shadchen system

Jump to:   M   P   S