Algebraic structure
data
with-data
meta-function
function
data-expand
7.0

Algebraic structure

Eric Griffis <[email protected]>

The algebraic collection is an experimental library for inducing and exploiting algebraic structure on Racket program fragments. Algebraic data constructors may be declared as data, operated on with functions, and instantiated with-data at run time.

> (data False True)
> (function not
    [(False) True]
    [(True) False])
> (with-data ([False 0] [True 1])
    (list True (not True) (not (not True))))

'(1 0 1)

Algebraic functions are evaluated at compile time, which enables them to operate on uninstantiated data.

> (function test
    [(False _ f) f]
    [(True  t _) t])
> (test (not True) #t #f)

#f

Attempting to evaluate an uninstantiated data constructor raises an exception at run time.

> False

eval:6:0: False: uninstantiated algebraic data

  in: False

In the absence of a formal type system, data constructors behave like tagged tuples of unspecified arity.

> (function n-args
    [(True) #f]
    [((True)) 0]
    [((True _)) 1]
    [((True _ _)) 2])
> (list
   (n-args (True 9 8))
   (n-args (True 7))
   (n-args (True))
   (n-args True))

'(2 1 0 #f)

 (require algebraic) package: algebraic

syntax

(data id ...+)

Binds an abstract data constructor to each id.

syntax

(with-data ([with-data-pattern expr] ...) body ...+)

 
with-data-pattern = id
  | (id data-pattern ...+)
     
data-pattern = _
  | param-id
  | racket-literal
  | id
  | (id data-pattern ...+)
Binds the ids in the bodies to syntax transformers that associate with-data-patterns with target exprs. Each term in the bodys matching the shape of a with-data-pattern is rewritten according to the corresponding target expr, in which any pattern variables are bound. The fully-rewritten bodys are then evaluated in order. The last body is in tail position with respect to the with-data form.

> (data None Some)
> (with-data ([None #f] [(Some x) x])
    (list (and (Some 1) (Some 2) (Some 3))
          (and None (Some 4) (Some 5))
          (or None None (Some 6))))

'(3 #f 6)

syntax

(meta-function id parse-option ... clause ...+)

 
clause = [(syntax-pattern ...) pattern-directive ... expr]
Binds id to a syntax-parser with clauses that associate syntax-pattern lists with target exprs. A syntax-pattern can be any valid syntax-parser pattern.

When a meta-function is applied to an argument list, it matches the arguments against each syntax-pattern list in order. When a match succeeds, the associated target expr, in which any pattern variables are bound, replaces the original meta-function application. Raises a syntax error if no match is found.

Any parse-options or pattern-directives are passed to syntax-parse unaltered.

> (begin-for-syntax
    (define-syntax-class positive-number
      (pattern a:number #:when (positive? (syntax->datum #'a)))))
> (meta-function calc
    #:literals (+ *)
    [((a + b)) (+ (calc a) (calc b))]
    [((a * b)) (* (calc a) (calc b))]
    [(a:positive-number) a])
> (calc 123)

123

> (calc (1 + 2))

3

> (calc ((1 + 2) * (3 + 4)))

21

> (calc 0)

eval:16.0: calc: expected positive-number

  at: 0

  in: (calc 0)

syntax

(function id parse-option ... clause ...+)

 
clause = [(function-pattern ...) expr]
     
function-pattern = wildcard
  | variable
  | identifier
  | literal-value
  | (function-pattern ...+)
     
wildcard = _ symbol-char*
     
variable = [a..z] symbol-char*
     
literal-value = #f
  | #t
  | char
  | number
  | string
  | bytes
  | (quote datum)
Binds id to a syntax-parser with clauses that associate function-pattern lists with target exprs. A function-pattern can be any syntax-parser pattern, with the following restrictions:

Variables match any term and bind to the data-expanded form of the match. Wildcards also match any term but expand nothing and create no bindings.

When a function is applied to an argument list, it data-expands the arguments and then matches the results against each function-pattern list in order. When a match succeeds, the associated target expr, in which any pattern variables are bound, is data-expanded and the result replaces the original function application. Raises a syntax error if no match is found.

Any parse-options are passed to syntax-parse unaltered.

> (data None Some)
> (function maybe
    [(n _   None)       n]
    [(_ f (Some x)) (f x)])
> (maybe #f add1 None)

#f

> (maybe #f add1 (Some 7))

8

procedure

(data-expand stx    
  context-v    
  stop-ids    
  [intdef-ctx])  syntax?
  stx : any/c
  context-v : (or/c 'expression 'top-level 'module 'module-begin list?)
  stop-ids : (or/c (listof identifier?) empty #f)
  intdef-ctx : 
(or/c internal-definition-context?
      (listof internal-definition-context?)
      #f)
 = '()
Equvalent to local-expand with the stop-ids appended to a list of all declared data constructors, when stop-ids is a list.