FLOC 2018: FEDERATED LOGIC CONFERENCE 2018
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: