Mechanized verification of CPS transformations

Zaynah Dargaye 1, * Xavier Leroy 1
* Auteur correspondant
Abstract : Transformation to continuation-passing style (CPS) is often performed by optimizing compilers for functional programming languages. As part of the development and proof of correctness of a compiler for the mini-ML functional language, we have mechanically verified the correctness of two CPS transformations for a call-by-value lambda-calculus with n-ary functions, recursive functions, data types and pattern-matching. The transformations generalize Plotkin's original call-by-value transformation and Danvy and Nielsen's optimized transformation, respectively. We used the Coq proof assistant to formalize the transformations and conduct and check the proofs. Originalities of this work include the use of big-step operational semantics to avoid difficulties with administrative redexes, and of two-sorted de Bruijn indices to avoid difficulties with alpha-conversion.
Type de document :
Communication dans un congrès
Logic for Programming, Artificial Intelligence and Reasoning, 14th Int. Conf. LPAR 2007, Oct 2007, Erevan, Armenia. Springer, 4790, pp.211-225, 2007, Lecture Notes in Artificial Intelligence. 〈10.1007/978-3-540-75560-9_17〉
Liste complète des métadonnées

Littérature citée [24 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/inria-00289541
Contributeur : Xavier Leroy <>
Soumis le : samedi 21 juin 2008 - 11:48:16
Dernière modification le : lundi 5 octobre 2015 - 16:58:39
Document(s) archivé(s) le : vendredi 28 septembre 2012 - 16:25:38

Fichier

cps-dargaye-leroy.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

Collections

Citation

Zaynah Dargaye, Xavier Leroy. Mechanized verification of CPS transformations. Logic for Programming, Artificial Intelligence and Reasoning, 14th Int. Conf. LPAR 2007, Oct 2007, Erevan, Armenia. Springer, 4790, pp.211-225, 2007, Lecture Notes in Artificial Intelligence. 〈10.1007/978-3-540-75560-9_17〉. 〈inria-00289541〉

Partager

Métriques

Consultations de
la notice

224

Téléchargements du document

156