Tobias Nipkow
Technische Universität München

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


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 formalized:  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 emantics and its type system; a type safety proof for the JVM; a bytecode verifier, i.e. data flow analyzer for the JVM; a correctness proof of the bytecode verifier w.r.t. the type system; a compiler and a proof that it preserves 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 jointly with Gerwin Klein.

The talk will give a very high-level overview of these formalizations.   Full paper available at

Host:  Frank Pfenning
Appointments:  Jennifer Landefeld

Friday, October 28, 2005
3:30 p.m.
Wean Hall 8220

Principles of Programming Seminars