SyTeCi: Automating Contextual Equivalence for Higher-Order Programs with References
We propose a framework to study contextual equivalence of programs written in a call-by-value functional language with local integer references. It reduces the problem of contextual equivalence to the problem of non-reachability in a transition system of memory configurations. This reduction is complete for recursion-free programs.
Restricting to programs that do not allocate references inside the body of functions, we encode this non-reachability problem as a constrained Horn clause that can then be checked for satisfiability automatically. Restricting furthermore to a language with finite data-types, we also get a new decidability result for contextual equivalence at any type.
Thu 23 JanDisplayed time zone: Saskatchewan, Central America change
10:30 - 11:35
|Binders by Day, Labels by Night: Effect Instances via Lexically Scoped Handlers|
Dariusz Biernacki University of Wrocław, Maciej Piróg University of Wrocław, Piotr Polesiuk University of Wrocław, Filip Sieczkowski University of WrocławLink to publication DOI Media Attached
|The Fire Triangle: How to Mix Substitution, Dependent Elimination, and Effects|
Research PapersLink to publication DOI Media Attached
|SyTeCi: Automating Contextual Equivalence for Higher-Order Programs with References|
Guilhem Jaber LS2N, Université de NantesLink to publication DOI Media Attached