My main research interests include semantics, programming languages, type theory, distributed systems, automated reasoning.
A longer version of this paper appeared as INRIA technical report RR-4851.
Type abstraction is a key feature of ML-like languages for writing large programs. Marshalling is necessary for writing distributed programs, exchanging values via network byte-streams or persistent stores. In this report we combine the two, developing compile-time and run-time semantics for marshalling, that guarantee abstraction-safety between separately-built programs.
We obtain a namespace for abstract types that is global, i.e. meaningful between programs, by hashing module declarations. We examine the scenarios in which values of abstract types are communicated from one program to another, and ensure, by constructing hashes appropriately, that the dynamic and static notions of type equality mirror each other. We use singleton kinds to express abstraction in the static semantics; abstraction is tracked in the dynamic semantics by coloured brackets. These allow us to prove preservation, erasure, and coincidence results. We argue that our proposal is a good basis for extensions to existing ML-like languages, pragmatically straightforward for language users and for implementors.
It is rare to give a semantic definition of a full-scale programming language, despite the many potential benefits. Partly this is because the available metalanguages for expressing semantics &emdash; usually either LaTeX for informal mathematics, or the formal mathematics of a proof assistant &emdash; make it much harder than necessary to work with large definitions.
We present a metalanguage specifically designed for this problem, and
ott, that sanity-checks such definitions and compiles
them into proof assistant code for Coq, HOL, Isabelle, and (in
progress) Twelf, together with LaTeX code for production-quality
typesetting, and OCaml boilerplate. The main innovations are:
(1) metalanguage design to make definitions concise, and easy to read and edit;
(2) an expressive but intuitive metalanguage for specifying binding structures; and
(3) compilation to proof assistant code.
This has been tested in substantial case studies, including modular specifications of calculi from the TAPL text, a Lightweight Java with Java JSR 277/294 module system proposals, and a large fragment of OCaml (around 271 rules), with machine proofs of various soundness results. Our aim with this work is to enable a phase change: making it feasible to work routinely, without heroic effort, with rigorous semantic definitions of realistic languages.