Coinductive big-step operational semantics

Abstract : Using a call-by-value functional language as an example, this article illustrates the use of coinductive definitions and proofs in big-step operational semantics, enabling it to describe diverging evaluations in addition to terminating evaluations. We formalize the connections between the coinductive big-step semantics and the standard small-step semantics, proving that both semantics are equivalent. We then study the use of coinductive big-step semantics in proofs of type soundness and proofs of semantic preservation for compilers. A methodological originality of this paper is that all results have been proved using the Coq proof assistant. We explain the proof-theoretic presentation of coinductive definitions and proofs offered by Coq, and show that it facilitates the discovery and the presentation of the results.
Type de document :
Article dans une revue
Information and Computation, Elsevier, 2009, 207 (2), pp.284-304. 〈10.1016/j.ic.2007.12.004〉
Liste complète des métadonnées

Littérature citée [40 références]  Voir  Masquer  Télécharger
Contributeur : Xavier Leroy <>
Soumis le : mardi 5 août 2008 - 09:38:11
Dernière modification le : vendredi 23 février 2018 - 15:29:08
Document(s) archivé(s) le : jeudi 3 juin 2010 - 17:48:36


Fichiers produits par l'(les) auteur(s)




Xavier Leroy, Hervé Grall. Coinductive big-step operational semantics. Information and Computation, Elsevier, 2009, 207 (2), pp.284-304. 〈10.1016/j.ic.2007.12.004〉. 〈inria-00309010〉



Consultations de la notice


Téléchargements de fichiers