Abstract

Refinement types enrich a language’s type system with logical predicates that circumscribe the set of values described by the type. These refinement predicates provide software developers a tunable knob with which to inform the type system about what invariants and correctness properties should be checked on their code, and give the type checker a way to enforce those properties at compile time. In this article, we distill the ideas developed in the substantial literature on refinement types into a unified tutorial that explains the key ingredients of modern refinement type systems. In particular, we show how to implement a refinement type checker via a progression of languages that incrementally add features to the language or type system.

Refinement Types: A Tutorial

Refinement types can be the vector that brings formal verification into mainstream software development. This happy outcome hinges upon the design and implementation of refinement type systems that can be retrofitted to existing languages, or co-designed with new ones.

In this book, the authors catalyze the development of such systems by distilling the ideas developed in the sprawling literature on the topic into a coherent and unified tutorial that explains the key ingredients of modern refinement type systems, by showing how to implement a refinement type checker.

Inspired by the nanopass framework for teaching compilation the authors show how to implement refinement types via a progression of languages that incrementally add features to the language or type system.

The readily accessible book provides the reader with an insightful introduction into Refinement Types using an innovative tutorial style that enables fast learning. Furthermore, the accompanying software implementation allows readers to work on practical real-world examples.