Investigating Extension Polymorphism

This paper examines a polymorphism mechanism which allows abstraction over evolving types. Although inclusion polymorphism is often quoted as being such a mechanism, this holds only for record types, for which constructor the inclusion relation matches the way types evolve in a long-lived system. This paper formalises the idea of evolution in the type space by the notion of extension, based upon both intuition and observation of evolving systems in a persistent programming environment. Extension is proposed as a type abstraction mechanism to allow smooth evolution in statically typed systems, and programming language mechanisms are introduced which maintain soundness and static checking in the presence of this abstraction. Extension over some function types is related to the concept of type matching, but a more general treatment is given as our interest is in extension over the whole type system.