Commuting Conversions and Join Points for Call-by-Push-ValueDistinguished Paper
This program is tentative and subject to change.
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, $\beta\eta$-equivalences in CBPV have been used to justify compiler optimizations in low-level IRs. However, these equivalences do not validate \emph{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 \emph{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. Our results are all mechanized in Lean 4.
This program is tentative and subject to change.
Tue 6 OctDisplayed time zone: Pacific Time (US & Canada) change
10:30 - 12:00 | |||
10:30 18mTalk | Commuting Conversions and Join Points for Call-by-Push-ValueDistinguished Paper OOPSLA Jonathan Chan University of Pennsylvania, Madi Gudin Amherst College, Annabel Levy University of Maryland, Stephanie Weirich University of Pennsylvania Link to publication DOI | ||
10:48 18mTalk | Differential Execution with Lexical Tracing OOPSLA DOI | ||
11:06 18mTalk | MGQL: An Executable, Small-Step Semantics of GQL OOPSLA Aditya Thimmaiah University of Texas at Austin, Tong-Nong Lin University of Texas at Austin, Milos Gligoric University of Texas at Austin DOI Pre-print | ||
11:24 18mTalk | Towards Concise Binding Semantics of Late-Bound OOP Systems OOPSLA Joel Jakubovic Charles University DOI Pre-print | ||
11:42 18mTalk | Semantics for 2D Rasterization OOPSLA Bhargav Kulkarni University of Utah, Henry Whiting University of Utah, Pavel Panchekha University of Utah DOI Pre-print | ||