University of Sheffield

Anthony J H Simons, MA PhD

Senior Lecturer in Computer Science
University Computer Science Testing Group Space Tech Europe Industry

A Language with Class

The theory of classification exemplified in an object-oriented programming language

Anthony James Howard Simons

F-bounded polymorphism


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.

The Theory of Classification

The Brunel Object-Oriented Programming Language

The Poppy Object-Oriented Programming Language