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.
Document type :
Journal articles
Complete list of metadatas

Cited literature [40 references]  Display  Hide  Download

https://hal.inria.fr/inria-00309010
Contributor : Xavier Leroy <>
Submitted on : Tuesday, August 5, 2008 - 9:38:11 AM
Last modification on : Tuesday, December 4, 2018 - 8:34:01 AM
Long-term archiving on : Thursday, June 3, 2010 - 5:48:36 PM

Files

leroy-grall.pdf
Files produced by the author(s)

Identifiers

Citation

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⟩

Share

Metrics

Record views

644

Files downloads

397