Name
Abstract | ||
|---|---|---|
A commonly-used technique in dependently-typed programming is to encode invariants about a data structure into its type, thus ensuring that the data structure is correct by construction. Unfortunately, this often necessitates the embedding of explicit proof terms within the data structure, which are not part of the structure conceptually, but merely supplied to ensure that the data invariants are maintained. As the complexity of the specifications in the types increases, these additional terms tend to clutter definitions, reducing readability. We introduce a technique where these proof terms can be supplied later, by constructing the data structure within a proof delay applicative functor. We apply this technique to Trip, our new language for Hoare-logic verification of imperative programs embedded in Agda, where our applicative functor is used as the basis for a verification condition generator, turning the typed holes of Agda into a method for stepwise derivation of a program from its specification in the form of a Hoare triple.
|
Year | DOI | Venue |
|---|---|---|
2019 | 10.1145/3331554.3342605 | TyDe@ICFP |
Keywords | DocType | ISBN |
agda, applicative functor, hoare logic, imperative programming, types, verification conditions | Conference | 978-1-4503-6815-5 |
Citations | PageRank | References |
0 | 0.34 | 0 |
Authors | ||
1 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Liam O'Connor | 1 | 44 | 5.02 |