hal-00585717, version 1
Decomposing Logical Relations with Forcing
Guilhem Jaber 1, 2Nicolas Tabareau 2
(23/03/2011)
Résumé : Logical relations have now the maturity to deal with program equivalence for realistic programming languages with features likes recursive types, higher-order references and first-class continuations. However, such advanced logical relations---which are defined with technical developments like step-indexing or heap abstractions using recursively defined worlds---can make a proof tedious. A lot of work has been done to hide step-indexing in proofs, using Gödel-Löb logic. But to date, step-indexes have still to appear explicitely in particular constructions, for instance when building recursive worlds in a stratified way. In this paper, we go one step further, proposing an extension of Abadi-Plotkin logic with forcing construction which enables to encapsulate reasoning about step-indexing or heap in different layers. Moreover, it gives a uniform and abstract management of step-indexing for recursive terms or types and for higher-order references.
- 1 : Ecole Normale Supérieure de Cachan (ENS Cachan)
- École normale supérieure de Cachan - ENS Cachan
- 2 : ASCOLA (INRIA - EMN)
- INRIA – Ecole des Mines de Nantes
- Domaine : Informatique/Logique en informatique
Informatique/Langage de programmation
- hal-00585717, version 1
- http://hal.archives-ouvertes.fr/hal-00585717
- oai:hal.archives-ouvertes.fr:hal-00585717
- Contributeur : Guilhem Jaber
- Soumis le : Mercredi 13 Avril 2011, 18:44:14
- Dernière modification le : Jeudi 14 Avril 2011, 09:12:18






Documents associés
Exporter