[R6RS] Enumerations proposal pre-draft

William D Clinger will at ccs.neu.edu
Sun Apr 23 11:19:30 EDT 2006

> - Having a new type allows for very fast dynamic type checking.
>   Moreover, I suspect that it at least simplifies compile-time
>   checking for compilers that already have the infrastructure for
>   tracking record types through their flow analyses, but not sets of
>   symbols.

I don't see how the speed of run-time type checking would be
faster with specialized enumeration values than with symbols.
Type checking on enumeration types and on sets of enumeration
types would be the same with either.  Checking that something
is a specialized enumeration value would probably be slower
than checking that something is a symbol.

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

The frequency of case dispatch on symbols in existing Scheme
programs already provides a strong incentive for implementors
to provide a fast mapping between symbols and integers, often
in the form of a hash code.  Larceny, for example, stores the
hash code of a symbol directly in the symbol structure, so it
can be fetched just as quickly as the integer index of your
proposal.  The cost of using symbols instead of a specialized
enumeration value would lie in the mapping from a symbol's
hash code to its index in a particular enumeration.  That
mapping would ordinarily be computed by a small hash table
that is embedded within the enumeration type and is created
when the enumeration type is created.  The space cost of this
hash table would be comparable to the space occupied by the
specialized enumeration values.

The advantage of using symbols is that you get structural
subtyping of enumeration set types for free.  In my opinion,
this increase in generality justifies the small increase in
run time for creating enumeration sets.

Note that specialized enumeration values also have run-time
costs for creating the specialized values and for passing
them around.

The speed of set operations is the same with symbols as with
specialized enumeration values.


More information about the R6RS mailing list