Tobias Nipkow
Technische Universität München
A Machine-Checked Model for a
Java-Like Language, Virtual Machine and Compiler
Abstract:
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 www.in.tum.de/~nipkow/pubs/Jinja/.
Principles
of Programming Seminars