Next: , Previous: Boxed bitwise-integer masks, Up: Libraries


6.2 Enumerated/finite types and sets

(This section was derived from work copyrighted (C) 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 mask library and the enumerated set facility.

6.2.1 Enumerated/finite types

— syntax: define-enumerated-type
          (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 & 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
— 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 ...)
             ...))

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

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

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 –> element list
— procedure: enum-set-member? enum-set element –> boolean
— procedure: enum-set=? enum-seta enum-setb –> boolean
— procedure: enum-set-union enum-seta enum-setb –> enum-set
— procedure: enum-set-intersection enum-seta enum-setb –> enum-set
— procedure: enum-set-negation enum-set –> 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, i.e. 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