Logical Frameworks as a Basis for Verification Tools:

A Case Study

Ina Kraan and Peter Baumann

inak,[email protected]

Institut fur Informatik der Universitat Zurich

Winterthurerstrasse 190, 8057 Zurich, Schweiz

May 12, 1995

Abstract

Wide-spread acceptance and use of formal methods in software development hinges on the availability of powerful tools. Tools must be both reliable and offer real assistance to the user. Logical frameworks are a suitable medium to build such tools, since they provide a means to show the faithfulness and adequacy of the implementation, and at the same time provide the flexibility needed to build sufficiently automated tools. We present Z-in-Isabelle, a deep semantic embedding of the specification language Z and a deductive system for Z in the generic theorem prover Isabelle. Z is based on Zermelo-Fraenkel set theory and first-order predicate logic, extended by a notion of schemas. Isabelle supports a fragment of higher-order predicate logic, in which object logics such as Z can be encoded as theories. We illustrate the use of Z-in-Isabelle with a data refinement proof. We assess to what extent such proofs need to and can be automated to make implementations in logical frameworks such as Z-in-Isabelle viable tools for reasoning about specifications.
Keywords: Verification, proof tools, formal methods, logical frameworks.

1 Introduction

Wide-spread acceptance and use of formal methods in software development depends on the availability of suitable tools. Since applying formal methods usually involves some kind of proof, tools for formal methods are primarily proof tools. To be useful, they must therefore both be reliable and offer real assistance to the user. We believe that logical frameworks are a suitable medium to build such tools, since they provide a means to show the faithfulness and adequacy of the implementation, and at the same time provide the flexibility needed to build intelligent tools which automate large parts of the proofs involved in the application of formal methods, which tend to be large and to involve many repetitive and tedious steps.

We have implemented the specification language Z and a deductive system for Z in the generic theorem proving tool Isabelle. The implementation is based on Z and its deductive system as defined in the draft Z standard [Brien & Nicholls 92]. It is a deep embedding of Z, i.e., both the syntax and a deductive system are formalized within Isabelle's meta-logic.