Abstract

Magnus Myreen and Thomas Tuerk are going to practice their TPHOLS talks. So, there will be two 20 minute talks.

Magnus Myreen: Verified LISP implementations on ARM , x86 and PowerPC

This paper reports on a case study, which we believe is the first to produce a formally verified end-to-end implementation of a functional programming language running on commercial processors. Interpreters for the core of McCarthy’s LISP 1 .5 were implemented in ARM , x86 and PowerPC machine code, and proved to correctly parse, evaluate and print LISP s-expressions. The proof of evaluation required working on top of verified implementations of memory allocation and garbage collection. All proofs are mechanised in the HOL4 theorem prover.

Thomas Tuerk A Formalisation of Smallfoot in HOL

I’m building a framework based on Abstract Separation Logic in HOL . Furthermore, I use this framework to build a tool called Holfoot that is similar to Smallfoot. In this talk I will give a high level presentation of the framework and especially Holfoot.

Smallfoot is one of the oldest and best documented separation logic tools. It is able to automatically prove specifications about programs written in a simple, low-level imperative language. This programming language is designed to be similar to C. It contains pointers, local and global variables, dynamic memory allocation/deallocation, conditional execution, while-loops and recursive procedures with call-by-value and call-by-reference arguments. Moreover, there is support for parallism.

Holfoot is able to parse Smallfoot-specifications and verify them automatically inside HOL . While Smallfoot-specifications only talk about the shape of data-structures in memory, my tool is able to reason about their data-content as well. However, proofs of fully-functional specification usually need user interaction.