Tags:call by push value, contextual equivalence, equational theory, normal form bisimulation, observational equivalence, optimizations, untyped call by value lambda calculus and verification
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.