A Language with Class

Abstract

Object-oriented programming languages have developed in advance of a formal theory of classification and, as a result, their treatment of class is muddled and ill-founded. The operational behaviour of such languages is often described incorrectly using a terminology of types which strictly does not apply. The type systems of languages affected by such misunderstandings are incorrect; furthermore, they may contain redundant mechanisms for handling type polymorphism as a result of the central ambiguity surrounding the notion of class.

To counter this confusion, a mathematical theory of classification is developed, which encompasses other approaches to type abstraction, such as "type constructors", "generic parameters", "classes", "inheritance" and "polymorphism". The theory extends earlier work on F-bounded polymorphism by providing second- and higher-order typed record combination for objects modelled as records of functions. The theory captures notions such as multiple and mixin inheritance and correctly classifies types with internal polymorphism. Recursive structures having both homogeneous and heterogeneous internal polymorphism are supported.

To demonstrate that theoretical purity does not mitigate against practical concerns, the theory is exemplified in a programming language called Brunel. An innovation in Brunel is the treatment of all forms of polymorphism using a single parametric mechanism; polymorphism is resolved either statically at compile-time or dynamically at run-time, by an optimising compiler. F-bounded types, type constructors and simple types are all handled within the same framework, demonstrating that the mathematical notion of class is fundamental to all forms of type abstraction.