
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
Widespread 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 ZinIsabelle, 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 ZermeloFraenkel set theory and firstorder predicate logic, extended by a notion of
schemas. Isabelle supports a fragment of higherorder predicate logic, in which object
logics such as Z can be encoded as theories. We illustrate the use of ZinIsabelle 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 ZinIsabelle viable
tools for reasoning about specifications.
Keywords: Verification, proof tools, formal methods, logical frameworks.
1 Introduction
Widespread 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 metalogic.