A Machine-Checked Model for a Java-Like Language, Virtual Machine and Compiler

Gerwin Klein and Tobias Nipkow

We introduce Jinja, a Java-like programming language with a formal semantics designed to exhibit core features of the Java language architecture. Jinja is a compromise between realism of the language and tractability and clarity of the formal semantics. The following aspects are formalised: a big and a small step operational semantics for Jinja and a proof of their equivalence; a type system and a definite initialization analysis; a type safety proof of the small step semantics; a virtual machine (JVM), its operational semantics and its type system; a type safety proof for the JVM; a bytecode verifier, i.e. dataflow analyzer for the JVM; a correctness proof of the bytecode verifiers w.r.t. the type system; a compiler and a proof that it preseves semantics and well-typedness.

The emphasis of this work is not on particular language features but on providing a unified model of the source language, the virtual machine and the compiler. The whole development has been carried out in the theorem prover Isabelle/HOL.

Journal preprint (which is a slightly revised version of the technical report). Includes index!

Isabelle theories in the Archive of Formal Proofs

BibTeX:

@article{KleinN-TOPLAS,author={Gerwin Klein and Tobias Nipkow},
title={A Machine-Checked Model for a {Java}-Like Language, Virtual Machine and Compiler},
journal=TOPLAS,volume = {28}, number = {4}, year = {2006}, pages = {619--695},
doi = {http://doi.acm.org/10.1145/1146809.1146811}}
Tech report:
@techreport{KleinN04,
  author={Gerwin Klein and Tobias Nipkow},
  title={A Machine-Checked Model for a {Java}-Like Language, Virtual Machine and Compiler},
  number={0400001T.1},
  institution={National ICT Australia},
  address={Sydney},
  month=mar,
  year=2004
}