Enumerated/finite types and sets
================================

(This section was derived from work copyrighted © 1993--2005 by Richard Kelsey, Jonathan Rees, and Mike Sperber.)

The structure finite-types has two macros for defining finite or enumerated record types.  These are record types for which there is a fixed set of instances, all of which are created at the same time as the record type itself.  Also, the structure enum-sets has several utilities for building sets of the instances of those types, although it is generalized beyond the built-in enumerated/finite type device.  There is considerable overlap between the Boxed bitwise-integer masks,boxed bitwise-integer mask library and the enumerated set facility.

Enumerated/finite types
-----------------------

 -- syntax: define-enumerated-type

          (define-enumerated-type DISPATCHER TYPE
            PREDICATE
            INSTANCE-VECTOR
            NAME-ACCESSOR
            INDEX-ACCESSOR
            (INSTANCE-NAME
             ...)) lisp
          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 & INDEX-ACCESSOR are
          defined to be unary procedures that return the symbolic name & index
          into the instance vector, respectively, of the new record type's
          instances.

          For example,

               (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 lisp

 -- syntax: define-finite-type

          (define-finite-type DISPATCHER TYPE
            (FIELD-TAG ...)
            PREDICATE
            INSTANCE-VECTOR
            NAME-ACCESSOR
            INDEX-ACCESSOR
            (FIELD-TAG ACCESSOR [MODIFIER])
            ...
            ((INSTANCE-NAME FIELD-VALUE ...)
             ...)) lisp
          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.

          For example,

               (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 lisp

Sets over enumerated types
--------------------------

 -- syntax: define-enum-set-type

          (define-enum-set-type SET-SYNTAX TYPE
                                PREDICATE
                                LIST->X-SET
            ELEMENT-SYNTAX
            ELEMENT-PREDICATE
            ELEMENT-VECTOR
            ELEMENT-INDEX) lisp
          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.

          ELEMENT-SYNTAX must be the name of a macro for constructing set
          elements from names (akin to the DISPATCHER argument to the
          define-enumerated-type & define-finite-type forms).
          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.

 -- procedure: enum-set->list enum-set returns element list
 -- procedure: enum-set-member? enum-set element returns boolean
 -- procedure: enum-set=? enum-seta enum-setb returns boolean
 -- procedure: enum-set-union enum-seta enum-setb returns enum-set
 -- procedure: enum-set-intersection enum-seta enum-setb returns enum-set
 -- procedure: enum-set-negation enum-set returns enum-set
     Enum-set->list returns a list of elements within ENUM-SET. Enum-set-member? tests whether ELEMENT is a member of ENUM-SET.  Enum-set=? tests whether two enumerated sets are equal, ie contain all the same elements.  The other procedures perform standard set algebra operations on enumerated sets.  It is an error to pass an element that does not satisfy ENUM-SET's predicate to enum-set-member? or to pass two enumerated sets of different types to enum-set=? or the enumerated set algebra operators.

Here is a simple example of enumerated sets built atop the enumerated types described in the previous section:

     (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)

     (enum-set->list (colour-set red blue))
         => (#{Colour red} #{Colour blue})
     (enum-set->list (enum-set-negation (colour-set red blue)))
         => (#{Colour green})
     (enum-set-member? (colour-set red blue) (colour blue))
         => #t lisp