A machine-checked model for a Java-like language, virtual machine, and compiler
Gerwin Klein, Tobias Nipkow · ACM Transactions on Programming Languages and Systems · 2006
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 the realism of the language and the tractability and clarity of its 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 initialisation 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, that is, a data flow analyser for the JVM, a correctness proof of the bytecode verifier with respect to the type system, and 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.
Cited by 246 works. doi:10.1145/1146809.1146811 Open-access PDF
Authors
References
- Java Virtual Machine Specification
- A unified approach to global program optimization
- Advanced Compiler Design and Implementation
- Isabelle/HOL: A Proof Assistant for Higher-Order Logic
- A Syntactic Approach to Type Soundness
- Featherweight Java
- A type system for Java bytecode subroutines
- Proceedings DARPA Information Survivability Conference and Exposition. DISCEX'00
- Javalight is type-safe---definitely
- Proving Java Type Soundness