HAL will be down for maintenance from Friday, June 10 at 4pm through Monday, June 13 at 9am. More information
Skip to Main content Skip to Navigation
Conference papers

Mechanized verification of CPS transformations

Zaynah Dargaye 1, * Xavier Leroy 1
* Corresponding author
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.
Document type :
Conference papers
Complete list of metadata

Cited literature [24 references]  Display  Hide  Download

Contributor : Xavier Leroy Connect in order to contact the contributor
Submitted on : Saturday, June 21, 2008 - 11:48:16 AM
Last modification on : Thursday, February 3, 2022 - 11:16:44 AM
Long-term archiving on: : Friday, September 28, 2012 - 4:25:38 PM


Files produced by the author(s)




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. pp.211-225, ⟨10.1007/978-3-540-75560-9_17⟩. ⟨inria-00289541⟩



Record views


Files downloads