Course pages 2017–18

# Interactive Formal Verification

# Course texts

The primary course text is "Concrete Semantics" by T. Nipkow and G. Klein, and is freely available here. A stripped-down version of this book is supplied with the Isabelle distribution (click the "Documentation" button on the right, and then open "prog-prove" under the "Tutorials" heading), and is called "Programming and proving with Isabelle/HOL". Some material is common to both, but numbered differently. I will reference both.

The additional technical manuals also found under the "Tutorials" heading in the Isabelle documentation panel are also suggested reading for anybody who wishes to advance their usage of Isabelle. The older (but still relevant) Isabelle tutorial, found in the "Documentation" panel under the "Old tutorials" heading also handles some subjects in more detail than "Programming and proving with Isabelle/HOL".

Students are also encouraged to read through existing Isabelle formalisations to learn idioms and tricks from experienced Isabelle users. A good source of vetted Isabelle formalisations, covering a range of subjects in pure mathematics and computer science, is the Archive of Formal Proofs.

# Installing Isabelle

Isabelle should be installed on laboratory machines. However, if you wish to install Isabelle on your own machine, then (assuming a Linux install):

- Download the Isabelle2016-1 distribution from the Isabelle homepage (click here).
Move the tar file into a suitable location, and then execute
`tar xzf Isabelle2016-1_app.tar.gz`to unpack. Add the resulting`Isabelle2016-1/bin/`directory to your PATH (usually by editing`.bashrc`or some other similar file in your home directory). - Start Isabelle for the first time by executing
`Isabelle2016-1`from a terminal window. This will first build a PolyML heap for the HOL object logic which can take up to 15 minutes depending on the speed of your machine. This heap building will only happen on the first execution of Isabelle. One this process has finished, close the dialogue box and proceed to edit your theory files.

Distributions for Windows and MacOS are also available from the Isabelle homepage.

# Lectures

All lectures will be interactive and held in the computer labs. Each lecture has an associated Isabelle theory file, with the intention that students are sat at machines inspecting the contents of the file within Isabelle itself whilst I project the contents of my own screen, explaining what is going on. The ordering of, and time spent on, any one particular topic is therefore subject to change based on how well we progress.

Each lecture (other than the first, introductory lecture) also has a set of associated exercises which students are encouraged to complete during the lab sessions, as the course progresses. Lectures are only intended to push students in the right direction, and provide a decent footing for further learning. Mastering Isabelle will require considerable practice and hard work. Students are encouraged to do further reading and think up their own exercises in their own time.

Subject | Lecture theory | Lecture slides | Associated exercises | Suggested reading |
---|---|---|---|---|

Introduction to Isabelle | Click | Welcome | Install Isabelle2016-1 | Introduction and Section 2.1 of "Concrete semantics"
Introduction and Section 2.1 of "Programming and proving in Isabelle/HOL" L. Paulson: "The foundation of a generic theorem prover" SEP: Church's Type Theory |

Propositional Logic | Click | Unification and Meta vs. Object | Click | L. Paulson: "Natural deduction as higher-order resolution" |

Predicate Logic | Click | None | Click | Section 4.1 of "Concrete semantics"
Section 3.1 of "Programming and proving in Isabelle/HOL" |

Typed set theory | Click | None | Click | Section 4.2 of "Concrete semantics"
Section 3.2 of "Programming and proving in Isabelle/HOL" |

Recursive functions and datatypes | Click | None | Click | Section 2.3 of "Concrete semantics"
Section 2.3 of "Programming and proving in Isabelle/HOL" Tutorial on function definitions |

Structured proofs | Click | None | Click | Chapter 5 of "Concrete semantics"
Chapter 4 of "Programming and proving in Isabelle/HOL" M. Wenzel: "Isar, a Generic Interpretative Approach to Readable Formal Proof Documents" |

Structured proofs | Click | None | Click | Chapter 5 of "Concrete semantics"
Chapter 4 of "Programming and proving in Isabelle/HOL" M. Wenzel: "Isar, a Generic Interpretative Approach to Readable Formal Proof Documents" |

Inductive definitions | Click | None | Click | Chapter 3.5 of "Programming and proving in Isabelle/HOL" |

Advanced subjects, and miscellanea | Click | None | Click | Section 4.3 of "Concrete semantics"
Section 3.3 of "Programming and proving in Isabelle/HOL" Tutorial on code generation User's guide to Sledgehammer Tutorial on function definitions J. Meng, C. Quigley, L. Paulson: "Automation for interactive proof: first prototype" |

Case study: operational semantics and hardware verification | Click
Click |
None | None | Chapters 3, 7 and 9 of "Concrete Semantics"
R. Kumar, M. Myreen, M. Norrish, S. Owens: "CakeML, a verified implementation of ML" S. Blazy, Z. Dargaye, X. Leroy: "Formal verification of a C compiler front-end" T. Nipkow, D. von Oheimb: "Java Light is type-safe, definitely" Sections 3.3, 8.1 and 8.2 of "Concrete semantics" A. Camilleri, M. Gordon, T. Melham: "Hardware verification using higher-order logic" A. Fox, M. Myreen: "A trustworthy monadic formalization of the ARMv7 Instruction Set Architecture" S. Goel, W. Hunt, M. Kaufmann, S. Ghosh: "Simulation and formal verification of X86 machine-code programs that make system calls" |

# Lab-based practical sessions

Lab sessions will be held on 12th October, 19th October, 2nd November and 9th November. All lab sessions will be held in SW02 at 11am (i.e. immediately after that morning's lecture). Sessions will be supervised by Dr. Victor Gomes and Dr. Dominic Mulligan (for the first two), and are intended for students to practice Isabelle/HOL skills and ask questions.

# Errata

With thanks for Bradley Hardy, Sebastian Borgeaud-dit-Avocat, and Patrick Fernandes:

The exercise sheet for recursive functions and datatypes contained a mistaken in the definition of a rose tree. The sheet has been amended to remove the broken material.

The definition of continuity in the second assessment was changed.

# Other interactive proof assistants

Several other interactive theorem proving systems exist, and are in active use. Ideas are often shared between these systems, and it is often worth looking at work published using these systems for new ideas. The major conferences in the field are CADE, CAV, CPP, and ITP, where work carried out in all of the theorem provers below is presented.

Name | Homepage |
---|---|

ACL2 | Click |

Agda | Click |

Coq | Click |

HOL4 | Click |

HOL-Light | Click |

Lean | Click |

Matita | Click |

PVS | Click |