Modular Typechecking for Hierarchically
Extensible Datatypes and Functions
ACM Transactions on Programming Languages and Systems (TOPLAS), 26(5):836-889, September 2004.
An earlier version of this paper appeared in the
2002 International Conference on Functional Programming (ICFP 2002),
Pittsburgh, PA, October 4-6, 2002.
An even earlier version of this paper appeared in the Ninth
International
Workshop on Foundations of
Object-Oriented Languages (FOOL 9),
Portland, Oregon, January 19, 2002.
Todd Millstein,
Colin Bleckner, and
Craig Chambers
One promising approach for adding object-oriented (OO) facilities to
functional languages like ML is to generalize the
existing datatype and function constructs to be hierarchical and
extensible, so that datatype variants simulate classes and function
cases simulate methods.
This approach allows existing datatypes to be
easily
extended with both new operations and new variants, resolving a
long-standing conflict between the functional and OO styles. However,
previous designs based on this approach have been forced to give up
modular typechecking, requiring whole-program checks to ensure
type safety.
We describe Extensible ML (EML), an ML-like
language that supports hierarchical, extensible datatypes and functions
while preserving purely modular typechecking. To achieve this result,
EML's type system imposes
a few requirements on datatype and function extensibility, but EML
is still able to express both traditional functional and OO idioms.
We have formalized a core version of EML and proven the
associated
type system sound,
and we have developed a prototype interpreter for the language.
[journal PDF |
conference PDF]