Lune

OOPSLA2026Top-tier venue

Commuting Conversions and Join Points for Call-by-Push-Value

Jonathan Chan, Madi Gudin, Annabel Levy, Stephanie Weirich

Abstract

Levy's call-by-push-value (CBPV) is a language that subsumes both call-by-name and call-by-value lambda calculi by syntactically distinguishing values from computations and explicitly specifying execution order. This low-level handling of computation suspension and resumption makes CBPV suitable as a compiler intermediate representation (IR), while its substitution evaluation semantics affords compositional reasoning about programs. In particular, βη -equivalences in CBPV have been used to justify compiler optimizations in low-level IRs. However, these equivalences do not validate commuting conversions , which are key transformations in compiler passes such as A-normalization. Such transformations syntactically rearrange computations without affecting evaluation order, and can reveal new opportunities for inlining. In this work, we identify the commuting conversions of CBPV, define a commuting conversion normal form (CCNF) for CBPV, present a single-pass transformation into CCNF based on A-normalization, and prove that well-typed, translated programs evaluate to the same result. To avoid the usual code duplication issues that also arise with A-normal form, we adapt the explicit join point constructs by Maurer et al. [2017] . Our results are all mechanized in Lean 4.

Ask Lune

Know this paper in minutes, not an afternoon.

Lune can read every page of it and the top-tier papers that cite it, and gives you its claims, its evidence and its limits, each one cited to the paper it comes from. No skimming, no AI slop.

Questions to start from

Lune can draw on

the full paper · related work

Get the answer

Free to start. No credit card required.

Lineage

Builds onCited byLeft to right by year; the more cited, the higher.

Builds on1

  1. A Low-Level Look at A-Normal FormWilliam J. BowmanOOPSLA 2024 · 4 citations

Related papers

  1. Abstract Operational Methods for Call-by-Push-ValueSergey Goncharov, Stelios Tsampas, Henning UrbatPOPL 2025 · 3 citations
  2. A Lazy, Concurrent Convertibility CheckerNathanaëlle Courant, Xavier LeroyPOPL 2026
  3. Effects and Coeffects in Call-by-Push-ValueCassia Torczon, Emmanuel Suárez Acevedo, Shubh Agrawal, Joey Velez-Ginorio et al.OOPSLA 2024 · 5 citations
  4. Genericity Through StratificationVictor Arrial, Giulio Guerrieri, Delia KesnerLICS 2024 · 1 citation
  5. Algorithmic Conversion with Surjective Pairing: A Syntactic and Untyped ApproachYiyun Liu, Stephanie WeirichPOPL 2026
Dusk over the sea between two cliffs drawn in fine vertical lines