1 Algebraic Racket
#lang algebraic/racket/base | package: algebraic |
Algebraic Racket is an extension for #lang racket/base that provides free-form, lexically scoped algebraic data structures along with several forms for creating functions and macros with a uniform and compact destructuring syntax.
It streamlines the functional Racket programming experience in two key areas:
Consistent Syntax
The destructuring syntax for algebraic data and most other data is the same for all function and macro forms.
Transparent, Lexically Scoped Data
Algebraic data constructors are like type tags. When applied to an argument
list, they produce an instance—
1.1 Data
(require algebraic/data) | package: algebraic |
The bindings documented in this section are provided by the algebraic/data and algebraic/racket/base libraries.
The data form defines several procedures and syntax transformers for working with named product and sum data structurs.
A product identifies a family of structures comprising a list of fields, and a sum is a list of products.
> (data Peano (Zero Succ))
In this example, Peano is a sum of the products Zero and Succ.
Each product name is bound to a constructor function that creates instances of the named product. A product 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)
> (product-instance? (Succ Zero)) #t
Equality is decided structurally for products 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 sum and product names from clashing, the sum bindings are defined in their own namespace. Use the sum form to add the appropriate scope to an identifier.
syntax
(data sum-decl ...+)
sum-decl = sum-id (product-id ...)
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 products or their instances, and #f for any other value.
- for each product-id:
a transformer binding that encapsulates information about the product declaration.
a product constructor that takes any number of arguments and returns a new instance of the product.
product-id?, for each product-id; a predicate that returns #t for the product constructor bound to product-id or its instances and #f for any other value.
> (data Unit (Unit)) > (Unit? Unit) #t
> (Unit? (Unit)) #t
> ((sum Unit?) Unit) #t
> ((sum Unit?) (sum Unit)) #t
syntax
(sum 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.
> (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?
> (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
(data->list arg) → (listof any/c)
arg : any/c
If arg is an product instance, returns its constructor followed by its fields.
Any other arg is returned as a singleton list.
> (data ABC (A B C)) > (data->list (sum ABC)) '(A B C)
> (data->list (A 1 2 3)) '(A 1 2 3)
> (data->list 123) '(123)
procedure
(product-instance? v) → boolean?
v : any/c
1.2 Functions
(require algebraic/function) | package: algebraic |
The bindings documented in this section are provided by algebraic/function algebraic/racket/base.
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 the multi-argument variants φ* (or phi*) and function*.
The φ (phi) form creates a function of exactly one argument with exactly one clause.
> (data Peano (Zero Succ)) > (define inc (φ a (Succ a))) > (define dec (φ (Succ b) b)) > (function? inc) #t
> (values (inc Zero) (dec (Succ (Succ Zero))))
(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<?]) a b))) > (cmp 1 2) #t
> (cmp #\x #\y) #t
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
syntax
(φ patt fun-directive ... body ...+)
syntax
(phi patt fun-directive ... body ...+)
syntax
(function [patt fun-directive ... body ...+] ...+)
patt = literal-data | `qfp | wildcard-id | variable-id | #(patt ...) | #&patt | #hash([key . patt] ...) | product-id | (product-id patt ...) | (product-id patt ... . patt) | (patt #:as alias-patt) | (patt #:if condition-expr) | regexp | (regexp patt ...+) | (regexp patt ... . patt) | (struct-id [field-id patt] ...) | (struct-id patt ...) | (void) | (patt ...) | (patt ... . patt) literal-data = boolean | character | number | string | bytes qfp = ,patt | (qfp . qfp) | datum fun-directive = #:as alias-patt | #:if condition-expr | #:with consequent-patt premise-expr
If #:as alias-patts are specified, they must all match the original input for the overall match to succeed.
Optional #:if condition-exprs specify that the pattern should only match if the condition-exprs produce true values. condition-expr is in the scope of all of the variables bound in patt and any preceding #:as directives.
> (letrec ([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 1 1 1 1 1)
An optional #:with consequent-patt premise-expr evaluates the premise-expr in the context of all the variables of patt and the alias-patts, if any. If the result matches consequent-patt, the pattern’s variables are added to the environment of subsequent side conditions. If the #:with match fails, the overall match also fails.
Multiple #:with directives are evaluated independently from each other.
> ((φ (#rx"^([^ ]+) ([^ ]+) HTTP/([^\r\n]+)" method uri version) #:with #rx"^(?:GET|PUT|POST)$" method #:with (#rx"^(.+)\\?(.+)$" path params) uri #:with #rx"^[0-9]\\.[0-9]$" version (list method path params version)) "GET /r/s?q=123&p=4 HTTP/1.0\r\n\r\n") '("GET" "/r/s" "q=123&p=4" "1.0")
A patt has one of the following forms:
literal-data A Racket literal value: #t, #f, character, number, string, or bytes, or (quote datum).
Matches an equal? constant.
Example:
`qfp Introduces a quasiquoted function pattern, wherein all identifiers match symbols and unquote escapes back to normal patterns.
Example:
wildcard-id An identifier whose name begins with an underscore “_”.
Matches anything and makes no bindings.
Example:
variable-id An identifier that is not a wildcard-id, product-id, or struct-id.
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:
#(patt ...) Matches patts against the elements of a vector.
Example:
#&patt Matches patt against the contents of a box.
Example:
#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:
product-id Matches a product constructor named product-id.
Example:
(product-id patt ...)
(product-id patt ... . patt) Example:
(patt #:as alias-patt) Matches patt if alias-patt also matches the same value.
Example:
(patt #:if condition-expr) Matches patt if condition-expr produces a true value. condition-expr is in the scope of all of the variables bound in patt.
Example:
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:
(struct-id [field-id 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:If field-ids are present, any field of struct-id may be omitted, and such fields can occur in any order.
Example:
(void) Matches a void value.
(patt ...)
(patt ... . patt) Matches patts against the elements of a list.Example:If the pattern contains a delimited ., the final patt is matched against the argument’s tail.
Example:
syntax
(φ* formals fun-directive ... body ...+)
syntax
(phi* formals fun-directive ... body ...+)
syntax
(function* [formals fun-directive ... body ...+] ...+)
formals = (patt ...) | (patt ...+ . rest-patt) | rest-patt
A formals has one of the following forms:
(patt ...) The function accepts as many argument values as the number of patts. Each patt is matched against an argument value by position.
Example:
(patt ...+ . rest-patt) The function accepts at least as many arguments as the number of patts. When the function is applied, the patts are matched against argument values by position, and all leftover arguments are placed into a list that is matched against rest-patt.
Example:
rest-patt The function accepts any number of arguments and places them into a list that is matched against rest-patt.
Example:
1.3 Macros
(require algebraic/macro) | package: algebraic |
The bindings documented in this section are provided by the algebraic/macro and algebraic/racket/base libraries.
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 (1 - (infix ((infix (2 + (infix (3 / 4)))) * (infix (5 - 6)))))) 15/4
The μ* (mu*) form creates a macro of any number of arguments with exactly one clause.
> (define-syntax infi* (μ* (a op b) (op a b))) > (infi* 1 - (infi* (infi* 2 + (infi* 3 / 4)) * (infi* 5 - 6))) 15/4
The macro form creates a macro of exactly one argument with one or more clauses.
> (define-syntax infixr (macro [(a op b) (op (infixr a) (infixr b))] [a a])) > (infixr (1 - ((2 + (3 / 4)) * (5 - 6)))) 15/4
The macro* form creates a macro of any number of arguments with one or more clauses.
> (define-syntax infixr* (macro* [(a op b ...) (op (infixr* a) (infixr* b ...))] [((a ...)) (infixr* a ...)] [(a) a])) > (infixr* 1 - (2 + 3 / 4) * (5 - 6)) 15/4
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, we can expose the generated code.
> (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))
> (define-syntax juicy-cons (μ0 (println 'POW!) ::))
> (begin-for-syntax (println (syntax-local-value #'juicy-cons))) #<procedure>
> (juicy-cons 1 (juicy-cons 2 3))
'POW!
'POW!
'(1 2 . 3)
syntax
(μ parse-option ... mac-patt mac-directive ... body ...+)
syntax
(mu parse-option ... mac-patt mac-directive ... body ...+)
syntax
(macro parse-option ... [mac-patt mac-directive ... body ...+] ...+)
mac-patt = literal-data | `qmp | wildcard-id | variable-id | #(mac-patt ...) | #&mac-patt | (struct-id mac-patt ...) | (mac-patt #:as alias-mac-patt) | (mac-patt #:if condition-expr) | (mac-patt ooo . mac-patt) | (mac-patt ...) | (mac-patt ...+ . mac-patt) qmp = ,mac-patt | (qmp . qmp) | datum ooo = ... | ...+ mac-directive = #:do [defn-or-expr ...] | #:as alias-mac-patt | #:if condition-expr | #:with consequent-mac-patt premise-expr
Any parse-options are passed to syntax-parse unaltered. See syntax-parse for details.
A mac-patt is a literal-data or wildcard-id as defined for φ, or one of the following forms:
`qmp Introduces a quasiquoted macro pattern, in which identifiers match symbols and unquote escapes back to normal macro patterns.
Example:
> (define-syntax m (μ `(x ,y) y)) > (m (x #t)) #t
> (m (z #t)) eval:100:0: m: expected the literal symbol `x'
at: z
in: (m (z #t))
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 is an annotated pattern variable and only matches forms described by the syntax class bound to syntax-class-id. Otherwise, it matches anything.
Example:
> (define-syntax m (μ x:id (identifier? #'x))) > (m a) #t
> (m 3) eval:103:0: m: expected identifier
at: 3
in: (m 3)
#(mac-patt ...) Matches mac-patts against the elements of a vector.
Example:
> (let-syntax ([m (μ #(a b c) (+ a b c))]) (m #(1 2 3))) 6
#&mac-patt Matches mac-patt against the contents of a box.
Example:
> (let-syntax ([m (μ #&x x)]) (m #&1)) 1
(struct-id mac-patt ...) Matches a sequence of terms, where the first element struct-id names a structure type and subsequent elements match the corresponding mac-patt.
Example:
> (struct F (a b c)) > (define-syntax m (μ (F x y z) (+ x y z))) > (m (F 1 2 3)) 6
(mac-patt #:as alias-mac-patt) First matches mac-patt, then matches alias-mac-patt against the same argument. If either pattern fails, the match fails.
Example:
> (let-syntax ([calc (μ ((x + y) #:as z) `(z = ,(+ x y)))]) (calc (1 + 2))) '((1 + 2) = 3)
(mac-patt #:if condition-expr) First matches mac-patt, then evaluates the condition-expr in the context of all previous variable bindings. If the value is #f, the match fails.
Example:
> (define-syntax m (μ (x #:if (number? (var x))) (+ x 2))) > (m 1) 3
> (m #f) eval:112:0: m: condition failed: (number? (var x))
at: #f
in: (m #f)
(head-mac-patt ooo . tail-mac-pat) Matches any term that can be decomposed into a list head matching some number of repetitions of head-mac-patt followed by a list tail matching tail-mac-patt.
Example:
(mac-patt ...) Matches a parenthesized sequence of mac-patts.
Example:
> (data Ss (S)) > (define-syntax swap (μ (a b) (b a))) > (swap (0 S)) (S 0)
> (product-instance? (swap (0 S))) #t
(mac-patt ...+ . mac-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)
The following pattern directives may appear any number of times in a macro clause:
#:do [defn-or-expr ...] Evaluates a sequence of definitions and expressions in the scope of all previous variable bindings.
Example:
> (define-syntax plus (μ* args #:do [(define xs (syntax-e #'args))] (+ #,@xs))) > (plus 1 2 3) 6
#:as alias-mac-patt Matches the original argument list against alias-mac-patt.
Example:
> (let-syntax ([calc (μ* (x + y) #:as z `(,@'z = ,(+ x y)))]) (calc 1 + 2)) '(1 + 2 = 3)
#:if condition-expr Evaluates the condition-expr in the context of all previous variable bindings. If the value is #f, the match fails.
Example:
#:with consequent-mac-patt premise-expr Evaluates premise-expr in the context of all pattern bindings and matches the result against consequent-mac-patt. The premise-expr is implicitly quasisyntaxed, so unsyntax and unsyntax-splicing escape to an expression within the transformer environment.
Example:
> (let-syntax ([m (macro [x #:with (a) (list #'10) #:with b #'1 (+ x a b)])]) (m 100)) 111
syntax
(μ* parse-option ... mac-formals mac-directive ... body ...+)
syntax
(mu* parse-option ... mac-formals mac-directive ... body ...+)
syntax
(macro* parse-option ... [mac-formals mac-directive ... body ...+] ...+)
mac-formals = (mac-patt ...) | (mac-patt ...+ . rest-mac-patt) | rest-mac-patt
syntax
(μ-parser parse-option ... mac-patt mac-directive ... body ...+)
syntax
(mu-parser parse-option ... mac-patt mac-directive ... body ...+)
syntax
(μ*-parser parse-option ... mac-formals mac-directive ... body ...+)
syntax
(mu*-parser parse-option ... mac-formals mac-directive ... body ...+)
syntax
(macro-parser parse-option ... [mac-patt mac-directive ... body ...+] ...+)
syntax
(macro*-parser parse-option ... [mac-formals mac-directive ... body ...+] ...+)
> ((macro*-parser [(x y) (list #'x #'y)] [(x y . z) (list #'x #'y #'z)]) #'(1 2 3 4 5)) '(#<syntax:eval:130:0 1> #<syntax:eval:130:0 2> #<syntax:eval:130:0 (3 4 5)>)
syntax
(var id)
1.4 Syntactic Forms
(require algebraic/racket/base/forms) | package: algebraic |
This section describes alternative core Racket syntax forms with variable binding sites generalized to function patterns.
See φ* for a description of formals and fun-directives.
syntax
(case-λ [formals fun-directive ... body ...+] ...)
syntax
(case-lambda [formals fun-directive ... body ...+] ...)
See φ* for a description of formals and fun-directives.
> (let ([f (case-λ [() 10] [((X x)) x] [((X x) (Y y)) (list y x)] [r r])]) (list (f) (f (X 1)) (f (X 1) (Y 2)) (f 1 2 3))) '(10 1 (2 1) (1 2 3))
> (let ([(X x) (X 5)]) x) 5
> (let ([(X x) (X 5)]) (let ([(X x) (X 2)] [(Y y) (Y x)]) (list y x))) '(5 2)
The second form evaluates the init-exprs; the resulting values become arguments in an application of a function (λ (patt ...) body ...), where proc-id is bound within the bodys to the function itself.
syntax
(let* ([patt val-expr] ...) body ...+)
syntax
(letrec ([patt val-expr] ...) body ...+)
> (letrec ([(X is-even?) (X (φ n ((|| zero? (.. is-odd? sub1)) n)))] [(Y is-odd?) (Y (φ n ((&& (.. not zero?) (.. is-even? sub1)) n)))]) (is-odd? 11)) #t
syntax
(let-values ([(patt ...) val-expr] ...) body ...+)
> (let-values ([((X x) (Y y)) (id (X (quotient 10 3)) (Y (remainder 10 3)))]) (list y x)) '(1 3)
syntax
(let*-values ([(patt ...) val-expr] ...) body ...+)
> (let*-values ([((X x) (Y y)) (id (X (quotient 10 3)) (Y (remainder 10 3)))] [((Z z)) (Z (list y x))]) z) '(1 3)
syntax
(letrec-values ([(patt ...) val-expr] ...) body ...+)
> (letrec-values ([((X is-even?) (Y is-odd?)) (id (X (φ n ((|| zero? (.. is-odd? sub1)) n))) (Y (φ n ((|| (<< = 1) (.. is-even? sub1)) n))))]) (is-odd? 11)) #t
syntax
(case val-expr case-clause ...)
case-clause = [patt fun-directive ... then-body ...+] | [else then-body ...+]
For the selected case-clause, the results of the last then-body, which is in tail position with respect to the case form, are the results for the whole case form.
A case-clause that starts with else must be the last case-clause.
> (case (+ 7 5) [n #:if ((member-of 1 2 3) n) 'small] [n #:if ((member-of 10 11 12) n) 'big]) 'big
> (case (- 7 5) [n #:if ((member-of 1 2 3) n) 'small] [n #:if ((member-of 10 11 12) n) 'big]) 'small
> (case (string-append "do" "g") [s #:if ((member-of "cat" "dog" "mouse") s) "animal"] [else "mineral or vegetable"]) "animal"
> (case (list 'y 'x) [ℓ #:if ((member-of '(a b) '(x y)) ℓ) 'forwards] [ℓ #:if ((member-of '(b a) '(y x)) ℓ) 'backwards]) 'backwards
syntax
(case-values val-expr case-clause ...)
case-clause = [(patt ...) fun-directive ... then-body ...+] | [else then-body ...+]
> (case-values (id 1 2 3) [(a b c) (+ a b c)] [else -1]) 6
The second form binds id to a function.
> (define (X x) (X 10)) > x 10
> (define (f (X x)) (+ x 1)) > (f (X 10)) 11