Enumerated and finite types and sets facility

_Enumerated and finite types and sets facility_

David Van Horn

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

_Enumerated and finite types_

(require (planet "" ("dvanhorn" "finite-types.plt" 1 1)))

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

For example, 

  (define-enumerated-type colour :colour 
    (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 notlisted in the first field tag
list must be assigned later.

For example, 

  (define-finite-type colour :colour 
    (red green blue) 
    (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

_Sets over Enumerated types_

(require (planet "" ("dvanhorn" "finite-types.plt" 1 1)))

> (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 proce- dure that
returns the index of an element within element-vector.

> (enum-set->list enum-set)

Returns a list of elements within enum-set.

> (enum-set-member? enum-set element)

Tests whether element is a member of enum-set.

> (enum-set=? enum-set-a enum-set-b)

Tests whether two enumerated sets are equal, i.e. contain all the same

> (enum-set-union enum-set-a enum-set-b)
> (enum-set-intersection enum-set-a enum-set-b)
> (enum-set-negation 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

An example:

  (define-enumerated-type colour :colour 
    (red blue green))

  (define-enum-set-type colour-set :colour-set 
    colour colour? colours colour-index) 

  (map colour-name (enum-set->list (colour-set red blue))) 
   => (red blue)

  (map colour-name (enum-set->list (enum-set-negation (colour-set))))
   => (red blue green)   ;; or some permutation

  (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."