An Algorithmic Framework for Recursive Structural Types
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.