Trustworthy Systems

Interactive proof: Applications to semantics

Authors

Gerwin Klein

NICTA

UNSW

Abstract

Building on a previous lecture in the summer school, the introduction to interactive proof, this lecture demonstrates a specific application of interactive proof assistants: the semantics of programming languages. In particular, I show how to formalise a small imperative programming language in the theorem prover Isabelle/HOL, how to define its semantics in different variations, and how to prove properties about the language in the theorem prover. The emphasis of the lecture is not on formalising a complex language deeply, but to teach formalisation techniques and proof strategies using simple examples. To this purpose, we cover big- and small step semantics, typing and type safety, as well as a small machine language with compiler and compiler correctness proof.

BibTeX Entry

  @inbook{Klein_12,
    author           = {Klein, Gerwin},
    booktitle        = {Software Safety and Security: Tools for Analysis and Verification},
    isbn             = {978-1-61499-027-7},
    keywords         = {isabelle, semantics},
    month            = apr,
    pages            = {85--125},
    paperurl         = {https://trustworthy.systems/publications/nicta_full_text/5371.pdf},
    publisher        = {IOS Press},
    series           = {NATO Science for Peace and Security Series},
    title            = {Interactive Proof: Applications to Semantics},
    year             = {2012}
  }

Download