Home > Research > Publications & Outputs > Type systems for the masses

Links

Text available via DOI:

View graph of relations

Type systems for the masses: deriving soundness proofs and efficient checkers

Research output: Contribution in Book/Report/Proceedings - With ISBN/ISSNConference contribution/Paperpeer-review

Published
Close
Publication date23/10/2015
Host publicationOnward! 2015 2015 ACM International Symposium on New Ideas, New Paradigms, and Reflections on Programming and Software (Onward!)
Place of PublicationNew York
PublisherACM
Pages137-150
Number of pages14
ISBN (print)9781450336888
<mark>Original language</mark>English

Abstract

The correct definition and implementation of non-trivial type systems is difficult and requires expert knowledge, which is not available to developers of domain-specific languages (DSLs) in practice. We propose Veritas, a workbench that simplifies the development of sound type systems. Veritas provides a single, high-level specification language for type systems, from which it automatically tries to derive soundness proofs and efficient and correct type-checking algorithms. For verification, Veritas combines off-the-shelf automated first-order theorem provers with automated proof strategies specific to type systems. For deriving efficient type checkers, Veritas provides a collection of optimization strategies whose applicability to a given type system is checked through verification on a case-by-case basis. We have developed a prototypical implementation of Veritas and used it to verify type soundness of the simply-typed lambda calculus and of parts of typed SQL. Our experience suggests that many of the individual verification steps can be automated and, in particular, that a high degree of automation is possible for type systems of DSLs.