[R6RS] Enumerations proposal pre-draft

[William D Clinger]

Here is yet another draft of the enumerations proposal.  Its
interface is pretty different from what Mike described in the
previous draft, but its semantics are pretty similar.

Highlights:

- Enumerated values are symbols.

- There is only one syntactic form, which is used to define
  a finite ordered (enumerated) universe of symbols.

- Like IRS Form 1040, there is both a long form and a short
  form of that form.  Each is simpler than the corresponding
  code of the previous draft of this proposal.

- The long form defines an enumerated universe of symbols, and
  defines a macro for constructing subsets of that universe,
  a procedure for constructing subsets of that universe, and a
  predicate for recognizing subsets of that universe.

- The short form does not define that macro, that constructor
  procedure, and that predicate.  There are, however, gloriously
  ad hoc ways to obtain the constructor procedure and predicate
  even if a programmer uses the short form.

- The representation of a set of symbols is not specified by
  this proposal.

Issues:

- Should the constructor procedure take an arbitrary number of
  symbols as arguments, or does it take a single list of symbols?

                                * * *

The long form:

(define-enumeration <type-name> ; Mike's symbol-checking macro (hehe)
  (<symbol> ...)                ; the symbols in this universe
  <index-of>                    ; maps a symbol to its index
  <constructor-syntax>          ; macro that constructs sets
  <constructor>                 ; procedure that constructs sets
  <predicate>)                  ; predicate that recognizes sets

where <type-name> is an identifier that will be bound to an
interesting macro; <symbol> ... are the symbols that form the
universe of the enumeration (in order); <index-of> is an
identifier that will be bound to a procedure that returns
a vector of <symbol> ... if passed no arguments, or returns
#f if passed a value that is not one of the <symbol> ...,
or returns a non-negative exact integer index if passed one
of the <symbol> ...; <constructor-syntax> is an identifier
that will be bound to a macro that, given any finite sequence
of the <symbol> ..., possibly with duplicates, expands into
an expression that evaluates to the set of those symbols;
<constructor> is an identifier that will be bound to a
procedure that, given any finite sequence of the <symbol> ...,
possibly with duplicates, returns the set of those symbols;
and <predicate> is an identifier that will be bound to a
predicate of one argument that returns true if and only if
its argument is a set whose universe is the universe defined
by this use of define-enumeration.

The short form:

(define-enumeration <type-name> ; Mike's symbol-checking macro (hehe)
  (<symbol> ...)                ; the symbols in this universe
  <index-of>)                   ; maps a symbol to its index

This is just a short form of the long form.  Deal with it.

With either form, the <type-name> macro has two distinct uses.

(<type-name> <symbol>) checks at macro-expansion time whether
<symbol> is in the universe associated with <type-name>.  If
it is, then (<type-name> <symbol>) is equivalent to '<symbol>.
If it isn't, then an exception must be raised at macro expansion
time, whatever that means.

Since the above use of <type-name> is pretty useless, we give
it a more important use: (<type-name>) returns the set of all
symbols that belong to the enumeration type, considered as a
subset of <type-name>.

Example:

(define-enumeration color
  (black white purple maroon)
  color-index)

(color black)                      => black
(color purpel)                     => <expansion-time error>
(color-index)                      => #(black white purple maroon)
(color-index 'black)               => 0
(color-index 'gold)                => #f
(color-index (color purple))       => 2
(color-index 'purple)              => 2
(enum-set->list (color))           => (black white purple maroon)


Other procedures:

Let enum-set range over the finite sets of symbols that can
be defined using the machinery above and below.  Then

(enum-set-universe enum-set) => enum-set
(enum-set-indexer enum-set) => procedure      ; the <index-of> procedure
(enum-set-constructor enum-set) => procedure  ; the <constructor>
(enum-set-predicate enum-set) => procedure    ; the <predicate>
(enum-set->list enum-set) => list of symbols
(enum-set-member? symbol enum-set) => boolean
(enum-set-subset? enum-set enum-set) => boolean
(enum-set=? enum-set enum-set) => boolean
(enum-set-union enum-set enum-set) => enum-set
(enum-set-intersection enum-set enum-set) => enum-set
(enum-set-difference enum-set enum-set)
(enum-set-complement enum-set) => enum-set
(enum-set-projection enum-set enum-set) => enum-set

`enum-set-universe' returns the set of all symbols that comprise
the universe of its argument; (enum-set-universe x) is equivalent
to (enum-set-complement (enum-set-difference x x)).

`enum-set-indexer' returns the <index-of> procedure associated
with the universe of its argument; when called with no arguments,
that procedure returns a vector of the symbols that comprise the
universe.

`enum-set-constructor' returns the <constructor> procedure
associated with the universe of its argument.

`enum-set-predicate' returns the unary <constructor> procedure
associated with the universe of its argument.

`enum-set->list' returns a list of the symbols that belong to
its argument, preferably in the same order as in the definition
of the enumeration type of its universe.

`enum-set-member?' returns true if and only if its first argument is
an element of its second argument.

`enum-set-subset?' returns true if and only if the universe of its
first argument is a subset of the universe of its second argument
(considered as sets of symbols) and every element of its first
argument is a member of its second.

`enum-set=?' returns true if and only if its first argument is a
subset of its second and vice versa, as determined by the
enum-set-subset? procedure.  This implies that the universes of
the two sets are equal as sets of symbols, but does not imply
that they are equal as enumeration types.

`enum-set-union' takes two enumeration sets that share the same
enumeration type as universe, and returns their union.

`enum-set-intersection' takes two enumeration sets that share the same
enumeration type as universe, and returns their intersection.

`enum-set-difference' takes two enumeration sets that share the same
enumeration type as universe, and returns their difference.

`enum-set-complement' takes an enumeration set and returns
its complement with respect to its universe.

`enum-set-projection' projects its first argument into the
universe of its second, dropping any elements of its first
argument that do not belong to the universe of its second.
(If its first argument is a subset of the universe of its
second, then no elements are dropped, and the injection is
returned.)


(enum-set=?
 (color)
 (enum-set-universe (color)))      => #t

((enum-set-indexer (color))
 'purple)                          => 2

(enum-set->list
 ((enum-set-constructor (color))
  'black 'purple))                 => (black purple)

((enum-set-predicate (color))
 (color))                          => #t

(enum-set-member? 'white
 ((enum-set-constructor (color))
  'white 'maroon))                 => #t

(enum-set-subset?
 (enum-set-complement (color))
 (color))                          => #t

(enum-set=?
 ((enum-set-constructor (color)) 'black 'maroon)
 (enum-set-complement
  ((enum-set-constructor (color))
   'white 'purple)))               => #t

(enum-set-subset?
 ((enum-set-constructor (color)) 'white)
 ((enum-set-constructor (other-color))
  'black 'white 'red 'green))      => #t

(enum-set=?
  ((enum-set-constructor (color))
   'black 'white)
  ((enum-set-constructor (other-color))
   'black 'white))                 => #t

(enum-set->list
 (enum-set-projection (other-color)
                      (color)))    => (black white purple maroon)

[end of proposal]