ΠΣ: Dependent Types without the Sugar

ΠΣ: Dependent Types without the Sugar
Thorsten Altenkirch, Nils Anders Danielsson, Andres Löh and Nicolas Oury
In the proceedings of Functional and Logic Programming, 10th International Symposium, FLOPS 2010. The original publication is available at www.springerlink.com. [pdf, implementation]

Abstract

The recent success of languages like Agda and Coq demonstrates the potential of using dependent types for programming. These systems rely on many high-level features like datatype definitions, pattern matching and implicit arguments to facilitate the use of the languages. However, these features complicate the metatheoretical study and are a potential source of bugs.

To address these issues we introduce ΠΣ, a dependently typed core language. It is small enough for metatheoretical study and the type checker is small enough to be formally verified. In this language there is only one mechanism for recursion—used for types, functions and infinite objects—and an explicit mechanism to control unfolding, based on lifted types. Furthermore structural equality is used consistently for values and types; this is achieved by a new notion of α-equality for recursive definitions. We show, by translating several high-level constructions, that ΠΣ is suitable as a core language for dependently typed programming.