Zaynah Dargaye and Xavier Leroy. Mechanized verification of CPS transformations. In LPAR 2007: Logic for Programming, Artificial Intelligence and Reasoning, number 4790 in LNAI, pages 211--225. Springer, 2007.

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 λ-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 α-conversion.

bib | DOI | Local copy | At publisher's site ] Back


This file was generated by bibtex2html 1.98.