A Formal Equational Theory for Call-By-Push-Value
Authors: Christine Rizkallah, Dmitri Garbuzov and Steve Zdancewic
Paper Information
Title: | A Formal Equational Theory for Call-By-Push-Value |
Authors: | Christine Rizkallah, Dmitri Garbuzov and Steve Zdancewic |
Proceedings: | ITP Papers |
Editors: | Jeremy Avigad and Assia Mahboubi |
Keywords: | verification, optimizations, normal form bisimulation, equational theory, untyped call by value lambda calculus, call by push value, contextual equivalence, observational equivalence |
Abstract: | ABSTRACT. Establishing that two programs are contextually equivalent is hard, yet essential for reasoning about semantics preserving program transformations such as compiler optimizations. We adapt Lassen's normal form bisimulations technique to establish the soundness of equational theories for both an untyped call-by-value lambda calculus and a variant of Levy's call-by-push-value language. We demonstrate that our equational theory significantly simplifies the verification of optimizations. |
Pages: | 19 |
Talk: | Jul 09 17:30 (Session 51C) |
Paper: |