Dependent Types for Low-Level Programming

In this paper, the authors describe the key principles of a dependent type system for low-level imperative languages. The major contributions of this work are a sound type system that combines dependent types and mutation for variables and for heap-allocated structures in a more flexible way than before and a technique for automatically inferring dependent types for local variables. They have applied these general principles to design Deputy, a dependent type system for C that allows the user to describe bounded pointers and tagged unions. Deputy has been used to annotate and check a number of real-world C programs.