7.2

## Algebraic structures for untyped Racket

This package provides #lang algebraic/racket/base which extends #lang racket/base with free-form, lexically scoped algebraic data structures along with complementary function and macro abstractions with a uniform and compact destructuring syntax.

### 1Overview

#lang algebraic/racket/base synthesizes and specializes the functionality of struct, match-lambda, and syntax-parser to streamline the funtional programming experience in vanilla Racket in two key areas:

Consistent syntax

The destructuring syntax for algebraic data and most other data is the same across all function- and macro-producing forms.

Convenient defaults

Algebraic data constructors are like type tags. When applied to an argument list, they produce an instancea list, or ordered sequence, of unnamed fields with the constructor at its head. They are easy to print and easy to parse, like prefab structs. The main difference is that algebraic constructors are lexically scoped and have a natural ordering.

#### Data

The data form defines a variety of procedures and syntax transformers for working with named products and sums.

A product identifies a family of structures comprising an ordered set of fields, and a sum identifies a list of products.

 > (data Peano (Succ Zero))

In this example, Peano is a sum comprising the products Succ and Zero.

Each product name is bound to a constructor, a function that creates instances of the named product. An instance is a concrete expression of the product as a tagged tuple of run-time values or expansion-time syntax fragments.

 > (Succ Zero) (Succ Zero) > (instance? (Succ Zero)) #t

Equality is decided structurally for constructors and their instances.

 > (equal? Succ Succ) #t > (equal? (Succ Zero) (Succ Zero)) #t > (equal? (Succ Zero) (Succ (Succ Zero))) #f

The data form also defines several membership predicates.

 > (Succ? Succ) #t > ((sum Peano?) Succ) #t > ((sum Peano?) (sum Peano)) #t

To prevent name clashes in types like Unit, sum bindings are defined in their own namespace. The sum form merely adds the appropriate scope to an identifier.

#### Functions

A function is a procedure that either deconstructs or rejects a fully-evaluated argument or argument list. Functions are created with the single-argument φ (or phi) and function forms, or their multi-argument variants φ* (or phi*) and function*.

The φ (phi) form creates a function of exactly one argument with exactly one clause.

 > (define inc (φ a (Succ a))) > (define dec (φ (Succ b) b)) > (function? inc) #t > (inc Zero) (Succ Zero) > (dec (Succ (Succ Zero))) (Succ Zero)

The φ* (phi*) form creates a function of any number of arguments with exactly one clause.

 > (define cmp (φ* (a b) ((cond [(number? a) <] [(char? a) char
> (cmp 1 2)

#t

> (cmp #\y #\x)

#f

The function form creates a function of exactly one argument with one or more clauses.

 > (define peano (function [0 Zero] [n (Succ (peano (- n 1)))]))
 > (define num (function [Zero 0] [(Succ p) (+ 1 (num p))]))
> (peano 3)

(Succ (Succ (Succ Zero)))

> (num (Succ (Succ (Succ Zero))))

3

The function* form creates a function of any number of arguments with one or more clauses.

 > (define add (function* [(a Zero) a] [(a (Succ b)) (Succ (add a b))]))
> (num (add (peano 3) (peano 2)))

5

Functions created by function* can have clauses with no arguments, and the number of arguments for each clause can vary.

 > (define num-args (function* [() 0] [(_ . rest) (+ 1 (apply num-args rest))]))
> (num-args)

0

> (num-args - -)

2

> (num-args - - - - -)

5

#### Macros

A macro is a syntax transformer that either deconstructs or rejects an argument or argument list at expansion time. Macros are created with the single-argument μ (or mu) and macro forms, or the multi-argument variants μ* (or mu*) and macro*.

The μ (mu) form creates a macro of exactly one argument with exactly one clause.

 > (define-syntax infix (μ (a op b) (op a b))) > (infix (5 - 3)) 2

The μ* (mu*) form creates a macro of any number of arguments with exactly one clause.

 > (define-syntax --> (μ* (p q) (or (not p) q))) > (for*/list ([p '(#t #f)] [q '(#t #f)]) (--> p q)) '(#t #f #t #t)

The macro form creates a macro of exactly one argument with one or more clauses.

 > (define-syntax bin (macro [#f 0] [_ 1])) > (bin #f) 0 > (bin (values #f)) 1

The macro* form creates a macro of any number of arguments with one or more clauses.

> (define-syntax and2 (macro* [(a b) ((function [#f #f] [_ b]) a)]))
 > (define-syntax and* (macro* [() #t] [(a b) (and2 a b)] [(a bs ...) (and2 a (and* bs ...))]))
> (and* 2 #f 0)

#f

> (and* 2 1 0)

0

Macros are designed to simplify mundane meta-programming tasks. The following example is a run-time implementation of the “power” function from [Taha2004]:

 > (define f-power (function* [(0 _) 1] [(n x) (* x (f-power (- n 1) x))]))
> (map (curry f-power 3) '(0 1 2 3 4 5 6))

'(0 1 8 27 64 125 216)

With unsyntax and the var form, applications of the power function can be unrolled at expansion time.

 > (define-syntax m-power (macro* [(0 _) 1] [(1 x) x] [(n:nat x) (* x (m-power #,(- (var n) 1) x))]))
> (define-syntax m-power3 (μ y (m-power 3 y)))
> (map (φ x (m-power3 x)) '(0 1 2 3 4 5 6))

'(0 1 8 27 64 125 216)

With quote and local-expand, the generated code can be exposed.

 > (define-syntax q-power (macro* [(0 _) 1] [(1 x) x] [(n:nat x) '#,(local-expand #`(* x (q-power #,(- (var n) 1) x)) 'expression null)]))
> (q-power 3 2)

'(#%app * '2 '(#%app * '2 '2))

### 2Tutorial: Interpreters

A core use case for algebraic is fast and cheap interpreter development. With the right tooling, throw-away interpreters can be an easy way to explore and validate language design choices quickly.

As it happens, Haskell is already pretty good at this. Algebraic data types and functional destructuring syntax make interpreters easy to read and write, and its type system keeps track of pervasive breaking changes for you. algebraic addresses the untyped half of this equation—algebraic data structures (ADTs sans type constraints) with destructuring syntax.

In this tutorial, we will build a tower of interpreters based on the models originally used to design algebraic itself:

1. A core model based on the untyped λ-calculus,

2. An extended syntax that compiles down to core constructs, and

3. A hosted variant that borrows additional constructs from the implementing platform.

#### The Core Model

 #lang algebraic/model/core package: algebraic

The core model started as a pure untyped λ-calculus, and it took a while to get everything right. Each time a construct was added or removed, everything else had to be re-tested. Without automation, exploration at this level of detail was easier on paper. Whereas this tutorial begins with a presumably viable model and proceeds directly to a robust solution, a realistic process will converge over many iterations of design, development, and testing until all three are in agreement.

##### Syntax

The core defines three syntactic categories: terms, values, and patterns.

A term is a concrete expression of the calculus.

A value is a term that reduces to a normal form according to the evaluation semantics. When a term eventually reduces to a particular value, we say the term evaluates to that value.

Non-value terms either diverge or get stuck. Some divergent terms are useful as infinite loops, but all stuck terms indicate an error.

A pattern is a predicate form that produces a set of variable bindings when matched against a compatible term.

 t ⩴ t t application | t;t sequence | φp.t function clause | μp.t macro clause | x variable | δ constructor | ◊ unit
 p ⩴ t t application | t;t sequence | _ wildcard | x variable | δ constructor | ◊ unit
 v ⩴ φp.t;· function | μp.t;· macro | δ constructor | δ (v;·) instance | ◊ unit

There are seven kinds of terms and six kinds of patterns.

An application (t t) is a pair of juxtaposed sub-terms. Nested applications are always parenthesized.

 (A ◊)

A sequence (t;t) is a pair of sub-terms separated by a semicolon in the model and prefixed by a dollar sign (\$) in code. Sequences combine multiple terms into a single unit. They are used for holding the non-tag elements of a tagged list.

 (A (\$ ◊ ◊))

A function clausep.t) is a λ-abstraction with the formal parameter generalized to a pattern, and a macro clausep.t) is a generalized λ-abstraction.

 (φ x x) (μ a a)

A uniform sequence (t;·) is a right-hand nesting of sequences in which every left-hand side is the same kind of term and every right-hand side, exept perhaps the last, is the same kind of uniform sequence. Uniform sequences combine multiple abstractions into a single unit.

A functionp.t;·) is a function clause or a uniform sequence of them, and a macro (μp.t;·) is one or more macro clauses in sequence.

 (\$ (φ x x) (\$ (φ y y) (φ z z))) (\$ (μ a a) (\$ (μ b b) (μ c c)))

A variable (x) is a name that may be bound to a term in the body of a function clause or macro clause. We say a variable not bound by an abstraction is free. All free variables are stuck.

A constructor (δ) is a name that identifies a data type. Constructors evaluate to themselves.

For convenience, constructors names begin with an uppercase letter and variable names begin with a lowercase letter.

An instance (δ (v;·)) is a constructor applied to a value or sequence of values.

 (A ◊) (B (\$ ◊ ◊))

Finally, the unit (◊) value denotes the presence of a value, as a convenient notation for when the actual value is irrelevant.

Abstract Syntax

According to the formal syntax, we need seven kinds of terms and six kinds of patterns.

 #lang algebraic/racket/base (data Term (TApp TSeq TFun TMac TVar TCon TUni) Patt (PApp PSeq PWil PVar PCon PUni))

Abstract syntax drives the interpreter, but it makes a poor surface syntax. We might have to cross-check the code and the model several times, so it would be convenient to have a surface syntax that resembles the formal syntax.

The Parser

The parser’s job is to map s-expressions onto the members of Term. Some terms have a pattern, and patterns are parsed by different rules than terms. Although constructor arities are not encoded in the data declaration, we can anticipate the following:

• Applications, sequences, and the abstractions take two arguments.

• Variables and constructors take one argument.

• Wildcards and units take no arguments.

We can also assume applications and sequences are structurally recursive. With all of this in mind, the parser looks like this:

 #lang algebraic/racket/base (define (parse t) (define term (function [(  t1 t2) (TApp (term t1) (term t2))] [(\$ t1 t2) (TSeq (term t1) (term t2))] [('φ p1 t2) ... (TFun ...) ...] [('μ p1 t2) ... (TMac ...) ...] [x #:if (con-name? x) (TCon x)] [x #:if (var-name? x) (TVar x)] [◊ TUni])) (define patt (function [(  p1 p2) (PApp (patt p1) (patt p2))] [(\$ p1 p2) (PSeq (patt p1) (patt p2))] [x #:if (con-name? x) (PCon x)] [x #:if (var-name? x) (PVar x)] ['_ PWil] [◊ PUni])) (term t))

The parse function is defined as a pair of s-expression parser combinators: term and patt. The term combinator translates terms in the formal syntax onto Term, while patt maps patterns in the formal syntax onto Patt. Parsing always starts and ends with a single term.

In the patterns of these functions, some symbols are quoted and others are not. The Greek symbols are quoted because φ and μ are lowercase characters and we don’t want them to behave like variables. _ is quoted because an unquoted underscore is a wildcard pattern for the enclosing function form. Quoting is optional for \$ and because neither is an uppercase or lowercase character.

For symbols other than _ and , we need a way to detect constructor and variable names. Inspecting the characters of a symbol’s name is too low level for s-expression parsing, so we’ll put that logic into helper predicates. The con-name? predicate checks if the first character of a symbol’s name is uppercase, and var-name? checks if it is lowercase.

But what about the abstraction parsers? Structural recursion is an option, but it turns out we can save some trouble in the interpreter if we do a little extra work here in the parser.

The following term is a standard illustration of unintended variable capture.

 ((φ x (φ y (x y))) y)

Substituting y for x naively would produce a function clause wherein the free outer y is indistinguishable from the bound inner y:

 (φ y (y y))

Unintended variable capture is a well-known problem with multiple solutions. Our goal is to produce correct and compact code, so we’ll take a straight-forward approach and make all bound variable names unique as they are parsed. This is equivalent to rewriting the original s-expression so every bound variable gets a unique index:

 ((φ x1 (φ y2 (x1 y2))) y)

Reducing this term does not lead to the unintended capture of y.

 (φ y2 (y y2))

We’ll name this rewriting function α-rename-clause. It takes two arguments—a Patt and a Termand returns two values: a copy of the Patt with all of its variables renamed, and a copy of the Term with its variables renamed as they were in the Patt. The definition of α-rename-clause will be given later; for now, we’ll just use it to finish the parser.

The abstraction parsers also need to pass multiple return values to a constructor. To keep our parsing rules compact, we’ll define our first macro. The values-> macro is a simple syntactic patch for call-with-values that merely rearranges the arguments and reduces the number of parentheses, admitting a more applicative style.

 #lang algebraic/racket/base (define (parse t) (define term (function [(  t1 t2) (TApp (term t1) (term t2))] [(\$ t1 t2) (TSeq (term t1) (term t2))] [('φ p1 t2) (values-> TFun (α-rename-clause (patt p1) (term t2)))] [('μ p1 t2) (values-> TMac (α-rename-clause (patt p1) (term t2)))] [x #:if (con-name? x) (TCon x)] [x #:if (var-name? x) (TVar x)] [◊ TUni])) (define patt (function [(  p1 p2) (PApp (patt p1) (patt p2))] [(\$ p1 p2) (PSeq (patt p1) (patt p2))] [x #:if (con-name? x) (PCon x)] [x #:if (var-name? x) (PVar x)] ['_ PWil] [◊ PUni])) (term t)) (define-syntax values-> (μ* (f xs-expr) (call-with-values (λ () xs-expr) f))) (define (con-name? x) (and (symbol? x) (char-lower-case? (first-char x)))) (define (var-name? x) (and (symbol? x) (char-upper-case? (first-char x)))) (define (first-char x) (string-ref (symbol->string s) 0))

The Printer

The printer’s job is to translate the members of Term back into s-expressions. The printer has the same structure as the parser, but the roles of the pattern and body are swapped.

 #lang algebraic/racket/base (define (show t) (define term (function [(TApp t1 t2) `(  ,(term t1) ,(term t2))] [(TSeq t1 t2) `(\$ ,(term t1) ,(term t2))] [(TMac p1 t2) `(μ ,(patt p1) ,(term t2))] [(TFun p1 t2) `(φ ,(patt p1) ,(term t2))] [(TVar x1) (α-restore x1)] [(TCon δ1) δ1] [TUni '◊])) (define patt (function [(PApp p1 p2) `(  ,(patt p1) ,(patt p2))] [(PSeq p1 p2) `(\$ ,(patt p1) ,(patt p2))] [(PVar x1) (α-restore x1)] [(PCon δ1) δ1] [PWil '_] [PUni '◊])) (term t))

The show function is also defined as a pair of term/patt combinators. This time, each function pattern deconstructs a member of Term or Patt and produces a term or pattern in the formal syntax as an s-expression. A helper named α-restore is introduced pre-emptively to undo whatever α-reduce-clause does to variable names.

Values

A value is a term that evaluates to itself trivially. Values are the subset of terms that constitute a valid computational result. To recognize them, we’ll need a series of predicates on the members of Term.

The over-arching goal is to produce a value? predicate that checks whether a Term is a value. Values include:

• functions,

• macros,

• constructors,

• instances of a constructor, and

• the unit value.

We’ll also need to recognize three kinds of uniform sequence: functions, macros, and instance data. Since these predicate all share the same internal structure, we’ll create our second macro, define-uniform-seq-pred. It takes two arguments—an identifier and a predicate—and binds the identifier to a new predicate that recognizes uniform sequences of terms that satisfy the given predicate.

 #lang algebraic/racket/base (define-syntax define-uniform-seq-pred (μ* (name? kind?) (define name? (function [(TSeq t1 t2) #:if (kind? t1) (name? t2)] [t (kind? t)])))) (define-uniform-seq-pred fun? TFun?) (define-uniform-seq-pred mac? TMac?) (define-uniform-seq-pred dat? value?) (define ins? (function [(TApp (TCon _) t) (dat? t)] [_ #f])) (define value? (or/c fun? mac? TCon? ins? TUni?))

The fun?, mac?, and dat? predicates recognize a uniform sequence of function clauses, macro clauses, and instance data, respectively; and the ins? predicate recognizes an instance as a constructor applied to instance data.

##### Evaluation Semantics

The top-level evaluator is a parse-interpret-show macro named algebraic. It uses a function named interpret to evaluate a term to its normal form, which in turn calls a step function that returns either a term representing the next step of the computation, or #f if the term is stuck.

 #lang algebraic/racket/base (define-syntax algebraic (μ t (show (interpret (parse 't))))) (define interpret (function [v #:if (value? v) v] [t ;; (writeln (show t)) (interpret (or (step t) (error 'interpret "stuck at ~v" (show t))))]))

 t1 ↝ t1'

t1 t2  t1' t2

APP1

 p11×t2=σ σ(t12)=t12'

p11.t12) t2  t12'

APPM

 v1≁μp.t;· t2 ↝ t2'

v1 t2  v1 t2'

APP2

 p11×v2=σ σ(t12)=t12'

p11.t12) v2  t12'

APPF

Applications (t t) reduce quasi-eagerly, starting on the left. If the left side reduces to a macro, the macro is applied to the un-reduced right side. If the left side reduces to a function or constructor, evaluation continues on the right.

Function clauses (φp.t) attempt to match a single argument value to a pattern p. If the match succeeds, any variables bound by the pattern are substituted into the body term t. If the match fails, the application is stuck.

 > ((φ x x) (φ y y)) '(φ y y)

A macro clausep.t) attempts to match a single argument term to a pattern. The only semantic difference between function clauses and macro clauses is that macro clauses do not reduce their argument before attempthing the match.

 > ((μ (fx fy) (fy fx)) ((φ x x) (φ y y))) '(φ x x)

 t1 ↝ t1'

t1;t2  t1';t2

SEQ1

 t2 ↝ t2'

v1;t2  v1;t2'

SEQ2

Sequences always reduce eagerly from left to right. The semicolon is special to Racket, so we’ll prefix sequenced pairs with a dollar sign instead.

 > (\$ ((φ x x) (φ y y)) (φ z z)) '(\$ (φ y y) (φ z z))

 (φp11.t12) v2 ↝ t12'

p11.t12;v13) v2  t12'

FUN1

 p11×v2 undefined

p11.t12;v13) v2  v13 v2

FUN2

 (μp11.t12) t2 ↝ t12'

p11.t12;v13) t2  t12'

MAC1

 p11×t2 undefined

p11.t12;v13) t2  v13 v2

MAC2

Functions and macros attempt to match their inputs to each clause in the sequence, taking the body of the first succesful match as its result. If every clause fails, the term is stuck.

 > ((\$ (φ ◊ ◊) (φ x (φ z x))) (φ y y)) '(φ z (φ y y)) > ((\$ (φ ◊ ◊) (φ x (φ z x))) ◊) '◊

Applying a constructor to a sequence produces an instance of the constructor, and the existing inferences rules already cover this case.

 > (A (\$ B (\$ (φ x x) (φ y y)))) '(A (\$ B (\$ (φ x x) (φ y y))))

### 3API Reference

 #lang algebraic/racket/base package: algebraic

#### 3.1Sums and Products

syntax

(data sum-decl ...+)

 sum-decl = sum-id (product-id ...)
Creates a new sum on a list of products and binds variables related to them.

A sum with n products defines 3+3n names:

• for each sum-id:
• a transformer binding that encapsulates information about the sum declaration.

• a sum structure that can be printed to retrieve its definition.

• sum-id?, for each sum-id; a predicate that returns #t for the sum bound to sum-id, its constructors or their instances, and #f for any other value.

• for each product-id:

• product-id?, for each product-id; a predicate that returns #t for the constructor bound to product-id or its instances and #f for any other value.

Example:
 > (data Unit (Unit)) > (Unit? Unit) #t > (Unit? (Unit)) #t > ((sum Unit?) Unit) #t > ((sum Unit?) (sum Unit)) #t

 syntax(sum id)
Adds the sum scope to id.

To prevent clashes between sums and products with the same name, sum bindings are defined in their own namespace. This form adds a scope to id that represents the sum namespace.

Example:
 > (data Either (Left Right)) > (Either? Left) Either?: undefined; cannot reference an identifier before its definition in module: 'program > ((sum Either?) Left) #t > ((sum Either?) Either) Either: undefined; cannot reference an identifier before its definition in module: 'program > ((sum Either?) (sum Either)) #t

 procedure(data-less-than? Π1 Π2) → boolean? Π1 : product? Π2 : product?
Returns #t if the arguments are in the defined order.

Examples:
> (data ABC (A B C))
> (values (data-less-than? A C) (data-less-than? C A))
 #t #f

 > (data XYZ (X Y Z)) > (sort (list Z Y X) data-less-than?) '(X Y Z)

 procedure(sum? v) → boolean? v : any/c
Returns #t if v is a sum.

 procedure(product? v) → boolean? v : any/c
Returns #t if v is a constructor.

 procedure v : any/c
Returns #t if v is an instance.

#### 3.2Functions

 syntax(φ patt maybe-if ... body ...+)

syntax

(phi patt body ...+)

patt = literal
| wildcard-id
| variable-id
| product-id
| (product-id patt ...)
| (product-id patt ... . patt)
| reference-id
| (patt #:if cond-expr)
| (patt #:as patt)
| regexp
| (regexp patt ...+)
| (regexp patt ... . patt)
| symbol
| (patt ...)
| (patt ... . patt)
| (struct-id ([field patt] ...))
| (struct-id patt ...)
| `fqp
| (void)
| #(patt)
| #&patt
| #hash([key . patt] ...)

literal = boolean
| character
| number
| string
| bytes
| 'datum

fqp = literal
| id
| ()
| (fqp . fqp)
| ,patt

maybe-if =
| #:if
| cond-expr
Creates a function of one argument with one clause.

Optional #:if cond-exprs specify that the pattern should only match if the cond-exprs produce true values. cond-expr is in the scope of all of the variables bound in patt.

Example:
> (data SZ (S Z))
 > (let ([f (function [(S x y) #:if (not x) #:if (not y) 0] [(S x y) #:if (not (and x y)) (or x y)] [(S x y) #:if x #:if y (+ x y)])]) (map f (list (S 1 2) (S #f 2) (S 1 #f) (S #f #f))))

'(3 2 1 0)

A patt has one of the following forms:

 literal

A Racket literal value: #t, #f, character, number, string, bytes, or (quote datum).

Matches an equal? constant.

Example:
 > ((φ "one" 1) "one") 1

 wildcard-id

An identifier whose name begins with an underscore “_”.

Matches anything, without binding any identifiers.

Example:
 > ((φ _ 1) 0) 1 > ((φ _x _x) 0) __x: undefined; cannot reference an identifier before its definition in module: 'program

 variable-id

An identifier whose name begins with a lowercase character.

Matches anything, and binds the identifier to the matching value in the bodys. If a variable binding is used multiple times within a pattern, the corresponding matches must be the same according to match-equality-test.

Example:
 > ((φ x x) 1) 1 > ((φ (S x x) x) (S 2 2)) 2 > ((φ (S x x) x) (S 3 4)) φ: no matching clause for (S 3 4)

 product-id

Matches a constructor named product-id.

Example:
 > ((φ S 1) S) 1

 (product-id patt ...) (product-id patt ... . patt)
Matches an instance of the product bound to product-id with fields that match patts.

Example:
 > ((φ (S x . xs) (list x xs)) (S 1 2 3)) '(1 (2 3))

 reference-id

A bound identifier that is not a wildcard-id, variable-id, or constructor-id.

Matches the bound value.

Example:
 > ((φ + 'Plus) +) 'Plus > ((φ + 'Plus) -) φ: no matching clause for #

 (patt #:if cond-expr)

Matches patt if cond-expr produces a true value. cond-expr is in the scope of all of the variables bound in patt.

Example:
 > ((φ (n #:if (> n 0)) '+++) 5) '+++ > ((φ (n #:if (> n 0)) '+++) -3) φ: no matching clause for -3

 (patt #:as alias-patt)

Matches patt if alias-patt also matches the same value.

Example:
 > ((φ ((S x) #:as y) (list x y)) (S 1)) '(1 (S 1))

 regexp (regexp patt ...+) (regexp patt ... . patt)
Matches regexp (a regexp value or byte-regexp-value) to a portion of its argument (a string, byte string, path, or input port) with regexp-match.

Example:
 > (values ((φ #rx"x+y+" 1) "--xxyy++") ((φ #rx"a+b+" 2) (open-input-string "--aabb++")))
 1 2

If any patts are given, they are matched against the results. If one or more capturing groups is present, the initial “whole-match” element of the result list is dropped before attempting to match patts.

Example:
 > (values ((φ (#rx"x+y+" xy) xy) "--xxyy++") ((φ (#rx"(a+)(b+)" as bs) (list as bs)) "--aabb++"))
 "xxyy" '("aa" "bb")
> ((φ (#rx"(a+)(b+)" as bs cs) 'OK) "--aabb++")

φ: no matching clause for "--aabb++"

 symbol

An unquoted datum literal that is not a wildcard-id, variable-id, or product-id.

Matches a symbol.

Example:
 > ((φ \$ 1) '\$) 1 > ((φ \$ 1) \$) \$: undefined; cannot reference an identifier before its definition in module: 'program

 (patt ...) (patt ... . patt)
Matches patts against the elements of a list.

Example:
 > ((φ (a b c) (+ a b c)) '(1 2 3)) 6

If the pattern contains a delimited ., the final patt is matched against the argument’s tail.

Example:
 > ((φ (a . b) (list a b)) '(1)) '(1 ())

 (struct-id ([field patt] ...)) (struct-id patt ..)
Matches an instance of a structure type named struct-id, where each field in the instance matches the corresponding patt.

Example:
 > (struct F (a b c)) > ((φ (F x y z) (+ x y z)) (F 1 2 3)) 6

If fields are present, any field of struct-id may be omitted, and such fields can occur in any order.

Example:
> (struct tree (val left right))
 > ((φ (tree [val a] [left (tree [right #f] [val b] [left #f])] [right #f]) (list a b)) (tree 0 (tree 1 #f #f) #f))

'(0 1)

 > ((φ (tree a (tree b #f #f) #f) (list a b)) (tree 0 (tree 1 #f #f) #f))

'(0 1)

 `fqp

Introduces a quasiquoted pattern, wherein all identifiers match symbols and unquote escapes back to normal patterns.

Example:
 > ((φ `(x y . ,(S a b)) (+ a b)) (list* 'x 'y (S 1 2)))

3

 (void)

Matches a void value.

 #(patt ...)

Matches patts against the elements of a vector.

Example:
 > ((φ #(a b c) (+ a b c)) (vector 1 2 3)) 6

 #&patt

Matches patt against the element of a box.

Example:
 > ((φ #&x x) (box 1)) 1

 #hash([key . patt] ...)

Matches against a hash table’s key-value pairs, where key is a bare identifier or a literal. Any key-value pair of the hash table may be omitted, and such pairs can occur in any order.

Example:
 > ((φ #hash((x . a) ("y" . b)) (list a b)) (hash "y" 1 #t 2 'x 3))

'(3 1)

 syntax(function [patt maybe-if ... body ...+] ...+)
Creates a function of one argument with at least one clause. When multiple clauses are given, they are attempted in the order specified.

Example:
 > (define fib (function [(n #:if (< n 2)) 1] [n (+ (fib (- n 1)) (fib (- n 2)))]))
> (map fib '(0 1 2 3 4 5 6))

'(1 1 2 3 5 8 13)

 syntax(φ* formals maybe-if ... body ...+)

syntax

(phi* formals maybe-if ... body ...+)

 formals = (patt ...) | (patt ...+ . rest-patt) | rest-patt
Creates a function of any number of arguments with one clause. The formals determine the number of arguments.

A formals has one of the following forms:

 (patt ...)

The function accepts as many argument values as the number of patts. Each patt is associated with an argument value by position.

Example:
 > (define fact (function* [(n) (fact n 1)] [(0 a) a] [(n a) (fact (- n 1) (* a n))]))
> (map fact '(0 1 2 3 4 5 6))

'(1 1 2 6 24 120 720)

 (patt ...+ . rest-patt)

The function accepts at least as many arguments as the number of patts. When the function is applied, the patts are associated with argument values by position, and all leftover arguments are placed into a list that is associated to rest-id.

Example:
 > ((function* [(x y . zs) (list x y zs)]) 1 2 3 4) '(1 2 (3 4))

 rest-patt

The function accepts any number of arguments and places them into a list that is associated with rest-patt.

Example:
 > ((function* [xs (reverse xs)]) 1 2 3 4) '(4 3 2 1)

 syntax(function* [formals maybe-if ... body ...+] ...+)
Creates a function of any number of arguments with one or more clauses. When multiple clauses are given, they are attempted in the order specified.

 procedure v : any/c
Returns #t if v is a function.

#### 3.3Macros

 syntax(μ macro-patt body ...+)

syntax

(mu macro-patt directive ... body ...+)

 macro-patt = literal | wildcard-id | variable-id | id-literal | (struct-id macro-patt ...) | `mqp | (macro-patt ...) | (macro-patt ...+ . macro-patt) | (macro-patt ooo . macro-patt) mqp = ,macro-patt | (mqp . mqp) | datum ooo = ... | ...+ directive = #:with macro-patt stx-expr | #:if condition-expr
Creates a macro of one argument with one clause.

A macro-patt is a literal or wildcard-id as defined for φ, or one of the following forms:

 variable-id

An identifier whose name begins with a lowercase character.

Matches anything, and binds the pattern variable to the matching sub-term in the bodys. If the identifier is of the form id:syntax-class-id, it behaves like an annotated pattern variable with the implicit class inserted. Otherwise, the pattern variable matches anything.

Example:
 > (define-syntax m (μ x:id (identifier? #'x))) > (m a) #t > (m 3) eval:99.0: m: expected identifier at: 3 in: (m 3) parsing context: while parsing macro argument term: 3 location: eval:99.0

 id-literal

An identifier that is not a wildcard-id or variable-id.

Matches an identifier literal.

Example:
 > (define-syntax m (μ ++ "plus plus")) > (m ++) "plus plus" > (m --) eval:102.0: m: expected the literal symbol `++' at: -- in: (m --) parsing context: while parsing macro argument term: -- location: eval:102.0

 (struct-id macro-patt ...)

Matches a sequence of terms, where the first element struct-id names a structure type and subsequent elements match the corresponding macro-patt.

Example:
 > (struct F (a b c)) > (define-syntax m (μ (F x y z) (+ x y z))) > (m (F 1 2 3)) 6

 `mqp

Introduces a quasiquoted macro pattern, in which identifiers match symbols and unquote escapes back to normal macro patterns.

Example:
 > (define-syntax m (μ `x 1)) > (m x) 1 > (m y) eval:108.0: m: expected the literal symbol `x' at: y in: (m y) parsing context: while parsing macro argument term: y location: eval:108.0

 (macro-patt ...)

Matches a parenthesized sequence of macro-patts.

Example:
> (define-syntax m (μ (a b) (b a)))
> (values (m (0 S)) (instance? (m (0 S))))
 (S 0) #t

 (macro-patt ...+ . macro-patt)

Matches a term with a list head and a tail separated by a delimited ..

Example:
 > (define-syntax m (μ (x y . z) (list x y z))) > (m (1 2 . 3)) '(1 2 3)

 (head-macro-patt ooo . tail-macro-pat)

Matches any term that can be decomposed into a list head matching some number of repetitions of head-macro-patt followed by a list tail matching tail-macro-patt.

Example:
 > (define-syntax m (macro* [(x ... (y ...) z ...+) (list* x ... y ... z ...)]))
 > (values (m 1 2 (3 4) 5 6) (m (3 4) 5 6))
 '(1 2 3 4 5 . 6) '(3 4 5 . 6)
> (m 1 2 (3 4))

eval:115.0: m: expected more terms

at: ()

within: (m 1 2 (3 4))

in: (m 1 2 (3 4))

The following pattern directives may appear in a macro clause:

 #:with macro-patt expr

Evaluates expr in the context of all pattern bindings and matches it against macro-patt. The expr is implicitly quasisyntaxed, so unsyntax and unsyntax-splicing escape to an expression within the transformer environment.

Example:
 > (define-syntax m (macro [x #:with (a) #,(list 10) #:with b 1 (+ x a b)]))
> (m 100)

111

 #:if condition-expr

Evaluates the condition-expr in the context of all previous attribute bindings. If the value is #f, the match fails.

Example:
 > (define-syntax m-fib (macro [n:nat #:if (< (var n) 2) 1] [n:nat (+ (m-fib #,(- (var n) 1)) (m-fib #,(- (var n) 2)))]))
 > (values (m-fib 0) (m-fib 1) (m-fib 2) (m-fib 3) (m-fib 4) (m-fib 5) (m-fib 6))
 1 1 2 3 5 8 13
> (let ([a 7]) (m-fib a))

eval:120.0: m-fib: expected exact-nonnegative-integer

at: a

in: (m-fib a)

parsing context:

while parsing macro argument

term: a

location: eval:120.0

 syntax(macro [macro-patt directive ... body ...+] ...+)
Creates a macro of one argument with one or more clauses. When multiple clauses are given, they are attempted in the order specified.

 syntax(μ* (macro-patt ...) directive ... body ...+)
 syntax(mu* (macro-patt ...) directive ... body ...+)
Creates a macro with any number of arguments and one clause.

 syntax(macro* [(macro-patt ...) directive ... body ...+] ...+)
Creates a macro with any number of arguments and at least one clause. When multiple clauses are given, they are attempted in the order specified.

 syntax(var id)
Returns the value bound to id in the transformer environment.

### Bibliography

 [Taha2004] Taha, Walid, “A gentle introduction to multi-stage programming,” In Domain-Specific Program Generation (pp 30-50). Springer, Berlin, Heidelberg, 2004.