Abstract
The advent of proof-carrying code has generated significant interest in reasoning about low-level languages. It is widely believed that low-level languages with jumps must be difficult to reason about because of being inherently non-modular. We argue that this is untrue. We take it seriously that, unlike statements of a high-level language, pieces of low-level code are multiple-entry and multiple-exit. And we define a piece of code as consisting of either a single labelled instruction or a finite union of pieces of code. Thus we obtain a compositional natural semantics and a matching Hoare logic for a basic low-level language with jumps. By their simplicity and intuitiveness, these are comparable to the standard natural semantics and Hoare logic of While. The Hoare logic is sound and complete wrt the semantics and allows for compilation of proofs of the Hoare logic of While.
| Original language | English |
|---|---|
| Pages (from-to) | 273-302 |
| Number of pages | 30 |
| Journal | Theoretical Computer Science |
| Volume | 373 |
| Issue number | 3 |
| DOIs | |
| Publication status | Published - 5 Apr 2007 |
Bibliographical note
Funding Information: We benefited from the constructive remarks and suggestions of our two referees. The first and second authors’ research activity was partially supported by the Estonian Science Foundation under grant No. 5567. Travel was supported by the EU FP5 IST project eVikings II.Other keywords
- Compilation of proofs
- Compositionality
- Hoare logics
- Low-level languages
- Natural semantics