@node Enumerated/finite types and sets
@section Enumerated/finite types and sets

@i{(This section was derived from work copyrighted (C) 1993-2005 by
Richard Kelsey, Jonathan Rees, and Mike Sperber.)}

@stindex finite-types
@stindex enum-sets
@texonlyindent
The structure @code{finite-types} has two macros for defining
@dfn{finite} or @dfn{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
@code{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 @embedref{Boxed bitwise-integer masks,boxed bitwise-integer
mask library} and the enumerated set facility.

@subsection Enumerated/finite types

@deffn syntax define-enumerated-type
@lisp
(define-enumerated-type @var{dispatcher} @var{type}
  @var{predicate}
  @var{instance-vector}
  @var{name-accessor}
  @var{index-accessor}
  (@var{instance-name}
   @dots{}))@end lisp
This defines a new record type, to which @var{type} is bound, with as
many instances as there are @var{instance-name}s.  @var{Predicate} is
defined to be the record type's predicate.  @var{Instance-vector} is
defined to be a vector containing the instances of the type in the same
order as the @var{instance-name} list.  @var{Dispatcher} is defined to
be a macro of the form (@var{dispatcher} @var{instance-name}); it
evaluates to the instance with the given name, which is resolved at
macro-expansion time.  @var{Name-accessor} & @var{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,

@lisp
(define-enumerated-type colour :colour
  colour?
  colours
  colour-name
  colour-index
  (black white purple maroon))

(colour-name (vector-ref colours 0))    @result{} black
(colour-name (colour white))            @result{} white
(colour-index (colour purple))          @result{} 2@end lisp
@end deffn

@deffn syntax define-finite-type
@lisp
(define-finite-type @var{dispatcher} @var{type}
  (@var{field-tag} @dots{})
  @var{predicate}
  @var{instance-vector}
  @var{name-accessor}
  @var{index-accessor}
  (@var{field-tag} @var{accessor} [@var{modifier}])
  @dots{}
  ((@var{instance-name} @var{field-value} @dots{})
   @dots{}))@end lisp
This is like @code{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,

@lisp
(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))            @result{} black
(colour-name (vector-ref colours 1))    @result{} white
(colour-index (colour purple))          @result{} 2
(colour-red (colour maroon))            @result{} 176@end lisp
@end deffn

@subsection Sets over enumerated types

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

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

@deffn procedure enum-set->list enum-set @returns{} element list
@deffnx procedure enum-set-member? enum-set element @returns{} boolean
@deffnx procedure enum-set=? enum-set@suba{a} enum-set@suba{b} @returns{} boolean
@deffnx procedure enum-set-union enum-set@suba{a} enum-set@suba{b} @returns{} enum-set
@deffnx procedure enum-set-intersection enum-set@suba{a} enum-set@suba{b} @returns{} enum-set
@deffnx procedure enum-set-negation enum-set @returns{} enum-set
@code{Enum-set->list} returns a list of elements within @var{enum-set}.
@code{Enum-set-member?} tests whether @var{element} is a member of
@var{enum-set}.  @code{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 @var{enum-set}'s
predicate to @code{enum-set-member?} or to pass two enumerated sets of
different types to @code{enum-set=?} or the enumerated set algebra
operators.
@end deffn

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

@lisp
(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))
    @result{} (#@{Colour red@} #@{Colour blue@})
(enum-set->list (enum-set-negation (colour-set red blue)))
    @result{} (#@{Colour green@})
(enum-set-member? (colour-set red blue) (colour blue))
    @result{} #t@end lisp