1 Enumerated and finite types
define-enumerated-type
define-finite-type
2 Sets over Enumerated types
define-enum-set-type
enum-set->list
enum-set-member?
enum-set=?
enum-set-union
enum-set-intersection
enum-set-negation

Finite Types: Enumerated and finite types and sets

David Van Horn <dvanhorn@ccs.neu.edu>

This package provides an implementation of the finite-types and enum-sets interfaces from Scheme 48.

Report a bug.

1 Enumerated and finite types

 (require (planet dvanhorn/finite-types/finite-types))

(define-enumerated-type dispatcher type predicate instance-vector name-accessor index-accessor (instance-name ...))

This defines a new record type, to which type is bound, with as many instances as there are instance-names. Predicate is defined to be the record type’s predicate. Instance-vector is defined to be a vector containing the instances of the type in the same order as the instance-name list. Dispatcher is defined to be a macro of the form (dispatcher instance-name ); it evaluates to the instance with the given name, which is resolved at macro-expansion time. Name-accessor and index-accessor are defined to be unary procedures that return the symbolic name and index into the instance vector, respectively, of the new record type instances.

Examples:

  > (define-enumerated-type colour :colour
      colour?
      colours
      colour-name
      colour-index
      (black white purple maroon))
  > (colour-name (vector-ref colours 0))

  black

  > (colour-name (colour white))

  white

  > (colour-index (colour purple))

  2

(define-finite-type dispatcher type (field-tag ...) predicate instance-vector name-accessor index-accessor (field-tag accessor [modifier]) ... ((instance-name field-value ...) ...))

This is like define-enumerated-type, but the instances can also have added fields beyond the name and the accessor. The first list of field tags lists the fields that each instance is constructed with, and each instance is constructed by applying the unnamed constructor to the initial field values listed. Fields not listed in the first field tag list must be assigned later.

Examples:

  > (define-finite-type colour :colour
      (red green blue)
      colour?
      colours
      colour-name
      colour-index
      (red colour-red)
      (green colour-green)
      (blue colour-blue)
      ((black 0 0 0)
       (white 255 255 255)
       (purple 160 32 240)
       (maroon 176 48 96)))
  > (colour-name (colour black))

  black

  > (colour-name (vector-ref colours 1))

  white

  > (colour-index (colour purple))

  2

  > (colour-red (colour maroon))

  176

2 Sets over Enumerated types

 (require (planet dvanhorn/finite-types/enum-sets))

(define-enum-set-type set-syntax type predicate list->x-set element-syntax element-predicate element-vector element-index)
This defines set-syntax to be a syntax for constructing sets, type to be an object that represents the type of enumerated sets, predicate to be a predicate for those sets, and list->x-set to be a procedure that converts a list of elements into a set of the new type.

The element-syntax must name a macro for constructing set elements from names (akin to the dispatcher argument to the define-enumerated-type & define-finite-type forms). The element-predicate must be a predicate for the element type, element-vector a vector of all values of the element type, and element-index a procedure that returns the index of an element within element-vector.

(enum-set->list enum-set)  list?
  enum-set : enum-set?
Returns a list of elements within enum-set.

(enum-set-member? enum-set element)  boolean?
  enum-set : enum-set?
  element : any/c
Tests whether element is a member of enum-set.

(enum-set=? enum-set-a enum-set-b)  boolean?
  enum-set-a : enum-set?
  enum-set-b : enum-set?
Tests whether two enumerated sets are equal, i.e. contain all the same elements.

(enum-set-union enum-set-a enum-set-b)  enum-set?
  enum-set-a : enum-set?
  enum-set-b : enum-set?
(enum-set-intersection enum-set-a    
  enum-set-b)  enum-set?
  enum-set-a : enum-set?
  enum-set-b : enum-set?
(enum-set-negation enum-set)  enum-set?
  enum-set : enum-set?
Standard set algebra operations on enumerated sets.

It is an error to pass an element that does not satisfy enum-setted sets of different types to enum-set=? or the enumerated set algebra operators.

Examples:

  > (define-enumerated-type colour :colour
      colour?
      colours
      colour-name
      colour-index
      (red blue green))
  > (define-enum-set-type colour-set :colour-set
      colour-set?
      list->colour-set
      colour colour? colours colour-index)
  > (map colour-name (enum-set->list (colour-set red blue)))

  (blue red)

  > (map colour-name (enum-set->list (enum-set-negation (colour-set))))

  (green blue red)

  > (enum-set-member? (colour-set red blue) (colour blue))

  #t

Much of this documentation is derived from Taylor Campbell’s "The Nearly Complete Scheme48 1.3 Reference Manual", which is "Copyright (C) 2004, 2005, 2006 Taylor Campbell. All rights reserved" and in turn states the relevant section was "derived from work copyrighted (C) 1993-2005 by Richard Kelsey, Jonathan Rees, and Mike Sperber."