Extensible Datatypes

We now explain how an @extensible datatype type differs from a datatype. The main difference is that later declarations may continue to add variants. Extensible datatypes are useful for allowing clients to extend data structures in unforeseen ways. For example:

  @extensible datatype Food;
  datatype Food { Banana; Grape; 
                  Pizza(list_t<datatype Food*>) };
  datatype Food { Candy; Broccoli };

After these declarations, Pizza(new List(new Broccoli, NULL)) is a well-typed expression.

If multiple declarations include the same variants, the variants must have the same declaration (the number of values, types for the values, and the same existential type variables).

Because different files may add different variants and Cyclone compiles files separately, no code can know (for sure) all the variants of an @extensible datatype. Hence all pattern-matches against a value of an @extensible datatype type must end with a case that matches everything, typically default.

There is one built-in @extensible datatype type: @extensible datatype exn is the type of exceptions. Therefore, you declare new exn constructors like this:

  datatype exn {BadFilename(string)};

The implementation of @extensible datatype types is very similar to that of datatype types, but variant tags cannot be represented as small integers because of separate compilation. Instead, these tags are represented as pointers to unique locations in static data.