POPL 2026 (series) / PADL 2026 (series) / PADL 2026: The 28th International Symposium on Practical Aspects of Declarative Languages /
A One-Pass CPS Transform with Simulation on the Nose
Danvy & Nielsen’s one-pass CPS transform has a straightforward definition, but clashes between the names of variables it introduces make it difficult to mechanically prove correct. Existing mechanical proofs either side-step the issue by using nameless representations, or rely on tedious $\alpha$-equivalence relations between target terms. This paper presents a new formulation of the transform using evaluation contexts that allows deterministic introduction of fresh names, eliminating the problem of naming clashes. We use our formulation to present a new and straightforward simulation proof of the correctness of the one-pass CPS transform, which we have mechanised in the HOL4 theorem prover.
Tue 13 JanDisplayed time zone: Brussels, Copenhagen, Madrid, Paris change
Tue 13 Jan
Displayed time zone: Brussels, Copenhagen, Madrid, Paris change
11:00 - 12:30 | |||
11:00 30mTalk | A Functional Logic Perspective on Indentation-Sensitive Parsing (Short Paper) PADL Steven Libby University of Portland | ||
11:30 30mTalk | A One-Pass CPS Transform with Simulation on the Nose PADL Pascal Y. Lasnier , Jeremy Yallop University of Cambridge, Magnus O. Myreen Chalmers University of Technology | ||
12:00 30mTalk | Determinacy Checking for Elpi: an Higher-Order Logic Programming Language with Cut PADL | ||