Abstract

In my last ARG Lunch talk I presented a formalisation of Abstract Separation Logic in HOL . Based on this formalisation, I build a formalisation of a tool similar to Smallfoot. This talk will present this tool and its formalisation.

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.

My tool 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.

The talk will consist of 3 parts. First, I will shortly present the theoretical background and give an overview over the Smallfoot formalisation. Then I will give a demonstration on how a fully-functional-specification of mergesort can be proved using the tool. After this, there will be time for questions and people that are not interested in HOL implementation details will be able to leave. Finally, I plan to give an overview over some general HOL infrastructure that I developed for this tool. This part of the talk will require some knowledge of HOL and might only be of interest to HOL -users. In particular, I will present consequence conversions (/src/bool/ConseqConv) and the quantifier instantiation-heuristics library (/src/quantHeuristics).