Greg Morrisett

The outcomes for my portion of the summer school are as follows:  A student who attends the lectures and does the homework will:

1. Learn how to write and reason about imperative ADTs and programs in the context of Coq.
2. Learn about and be able to apply the ideas behind separation logic for reasoning about pointers.
3. Learn about an approach to tactic-based theorem proving in Coq that leads to smaller and more maintainable proof scripts.
4. Build a certified type inference engine.

The primary goal is to teach you about the integration of Hoare-style program logics and type systems, or Hoare Type Theory (HTT).  HTT makes it possible to write and reason about imperative, higher-order programs and their computational effects.  We can embed HTT into Coq by providing only a very few new primitives.  On top of this basic framework, we can define refined versions of HTT that simplify proofs of programs.  In particular, we will build a separation-based interface for assembling and reasoning about references and state, and show how this style of interface supports modular reasoning about imperative, abstract data types.  

We will also discuss a technique for constructing proofs in Coq that I call "Chlipala-style" after Adam Chlipala.  A Chlipala-style proof is assembled from a collection of re-usable tactics.  The tactics are written to be insensitive to as many changes as possible.  In particular, the tactics are written to use Ltac's pattern matching to find suitable hypotheses instead of a specific name.  Although writing proofs in this style does not come naturally (to me), Adam has convinced me that the resulting proof scripts are easier to maintain than the brute-force approach that I was used to.  

Along the way, we'll study how to build a unification-based type-inference engine and prove its correctness.  We'll first consider a purely functional version of unification, based on a JFP article of Connor McBride, which uses dependent types in a crucial way to ensure termination.  Then using the ideas behind HTT, we'll build an imperative version which you can extract to efficient ML code.  


  • Powerpoint and PDF for the first lecture on type inference.
  • The Coq Doc material for type inference can be found here and the original Coq source can be found here.
  • Coqdoc and Coq code for the lecture on Hoare Type Theory.
  • Powerpoint and PDF for the lecture on Hoare Type Theory.