An Algorithmic Framework for Recursive Structural Types

Date Added: Oct 2011
Format: PDF

Structural type systems provide an interesting alternative to the more common nominal typing scheme. Many existing languages employ structural types in some form, including Modula-3, Scala and various extensions proposed for Java. Previous work has addressed many aspects of structural types, such as efficient sub-typing algorithms. Unlike nominal type systems, implementing a (recursive) structural type system remains a significant challenge. This is because a large gap exists between the formalisation of a recursive structural type system, and its algorithmic realisation. In this paper, the authors aim to reduce this gap by providing a generic framework that succinctly captures the important algorithmic issues.