Ph.D. thesis  cap


Analyzing Java in Isabelle/HOL
-- Formalization, Type Safety and Hoare Logic --

Author: David von Oheimb
School: Technische Universität München
Year: 2001
Note: Available from http://ddvo.net/diss/
CR Classification: D.2.4, D.3.1, F.3.1
CR General Terms: Languages, Verification, Theory
Keywords: Java, formalization, operational semantics, type soundness, axiomatic semantics, Isabelle/HOL
Abstract: This thesis deals with machine-checking a large sublanguage of sequential Java, covering nearly all features, in particular the object-oriented ones. It shows that embedding such a language in a theorem prover and deducing practically important properties is meanwhile possible and explains in detail how this can be achieved.

We formalize the abstract syntax, and the static semantics including the type system and well-formedness conditions, as well as an operational (evaluation) semantics of the language. Based on these definitions, we can express soundness of the type system, an important design goal claimed to be reached by the designers of Java, and prove that type safety holds indeed. Moreover, we give an axiomatic semantics of partial correctness for both statements and (side-effecting) expressions. We prove the soundness of this semantics relative to the operational semantics, and even prove completeness. We further give a small but instructive application example.

A direct outcome of this work is the confirmation that the design and specification of Java (or at least the subset considered) is reasonable, yet some omissions in the language specification and possibilities for generalizing the design can be pointed out. The second main contribution is a sound and complete Hoare logic, where the soundness proof for our Hoare logic gives new insights into the role of type safety. To our knowledge, this logic is the first one for an object-oriented language that has been proved complete. By-products of this work are a new general technique for handling side-effecting expressions and their results, the discovery of the strongest possible rule of consequence, and a new rule for flexible handling of mutual recursion.

All definitions and proofs have been done fully formally with the interactive theorem prover Isabelle/HOL, representing one of its major applications. This approach guarantees not only rigorous definitions, but also gives maximal confidence in the results obtained. Thus this thesis demonstrates that machine-checking the design of an important non-trivial programming language and conducting meta-theory on it entirely within a theorem proving system has become a reality.


Available as [ps.gz] and [pdf] file. Official Electronic Publication
Overview Slides (in German) as [ps.gz] file.
Corresponding Isabelle sources
Pictures of PhD party

BibTeX-Entry:

@phdthesis{DvO-PhD, author = {Oheimb, David von}, title = {Analyzing {J}ava in {Isabelle/HOL}: \textit{Formalization, Type Safety and {H}oare Logic}}, school = {Technische Universit\"{a}t M\"{u}nchen}, year = 2001, CRClassification = {D.2.4, D.3.1, F.3.1}, CRGenTerms = {Languages, Verification, Theory}, keywords = {Java, formalization, operational semantics, type soundness, axiomatic semantics, Isabelle/HOL}, note = {\url{http://ddvo.net/diss/}}, abstract = { This thesis deals with machine-checking a large sublanguage of sequential Java, covering nearly all features, in particular the object-oriented ones. It shows that embedding such a language in a theorem prover and deducing practically important properties is meanwhile possible and explains in detail how this can be achieved. We formalize the abstract syntax, and the static semantics including the type system and well-formedness conditions, as well as an operational (evaluation) semantics of the language. Based on these definitions, we can express soundness of the type system, an important design goal claimed to be reached by the designers of Java, and prove that type safety holds indeed. Moreover, we give an axiomatic semantics of partial correctness for both statements and (side-effecting) expressions. We prove the soundness of this semantics relative to the operational semantics, and even prove completeness. We further give a small but instructive application example. A direct outcome of this work is the confirmation that the design and specification of Java (or at least the subset considered) is reasonable, yet some omissions in the language specification and possibilities for generalizing the design can be pointed out. The second main contribution is a sound and complete Hoare logic, where the soundness proof for our Hoare logic gives new insights into the role of type safety. To our knowledge, this logic is the first one for an object-oriented language that has been proved complete. By-products of this work are a new general technique for handling side-effecting expressions and their results, the discovery of the strongest possible rule of consequence, and a new rule for flexible handling of mutual recursion. All definitions and proofs have been done fully formally with the interactive theorem prover Isabelle/HOL, representing one of its major applications. This approach guarantees not only rigorous definitions, but also gives maximal confidence in the results obtained. Thus this thesis demonstrates that machine-checking the design of an important non-trivial programming language and conducting meta-theory on it entirely within a theorem proving system has become a reality. } }