[R6RS] Enumerations proposal pre-draft

[William D Clinger]

> > I don't see how the speed of run-time type checking would be
> > faster with specialized enumeration values than with symbols.
>
> Presumably, you have to go through the list of valid symbols to check
> that a given symbol is a member.  With a separate type, you just have
> to check the tag.

It depends on what you mean by "run-time type checking".
Here are the four things I think you could mean:

    enumeration type: run-time type checking is just as
        fast with either proposal
    enumeration set type: run-time type checking is just
        as fast with either proposal
    enumeration value: checking whether something is a
        symbol will probably be a little faster than
        checking whether something is a specialized
        enumeration value, because the latter is likely
        to involve two checks: (1) Is it a record?
        (2) Is it the right kind of record?
    checking whether some enumeration value belongs
        to some enumeration type: this is essentially
        the same as computing the index of an enumeration
        type, which is discussed below; the short answer
        is no, you do not have to go through the list of
        valid symbols to check that a given symbol is a
        member; you would use exactly the same machinery
        compilers already use for case dispatch on symbols
        (with specialized enumeration types, that machinery
        would have to be duplicated in the implementation
        of your proposed <name-constructor>, and would
        probably not be duplicated as well)

> >> - The mapping to integers is much faster than with symbols.  This
> >>   could also be exploited to produce very fast code for a case
> >>   distinction, via tables or binary search.  (This may also be
> >>   possible for symbols, but I don't see how.)
> >
> > Faster, yes, but not much faster.
>
> That depends on the size of the universe, no?

Not very much.  With both proposals, the construction of an
enumeration set by enumerating its values takes time proportional
to the number of elements in the set.  It is also influenced
by the size of the universe, but not by very much because
hash tables usually have O(1) amortized cost and binary
search is O(lg n), where n is the size of the universe.

I will measure this cost for universes of various sizes, and
will report the results in a future message.

> > The speed of set operations is the same with symbols as with
> > specialized enumeration values.
>
> Don't you lose a bit at least at construction time, through the
> overhead in converting to an integer?

The only place where there is any difference at all is in
the construction of an enumeration set by enumerating its
values, which we were talking about above.  This usually
gets done only once, when the set computation is set up
(no pun intended) and usually accounts for an insignificant
fraction of the set computation.

Will