Proceedings of the ACM on Programming Languages · 2019 · 14 citations · 12 references
ComputingComputer ScienceAlgorithmsFormal MethodsProgramming LanguagesData-flow AnalysisEquivalence CheckingFunctional ProgrammingRecursion TheoryType CheckingType SystemsContextual EquivalenceDecidabilityDecidability ProblemsHorn Clause LogicHorn Clause SolvingReachabilityReachability AnalysisRecursion
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 set of 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.
12
Sequent calculi for induction and infinite descent
J G. Brotherston, Alex Simpson · Journal of Logic and Computation · 2010 · 126 citations · Full text
Automating regression verification
Dennis Felsing, Sarah Grebing, Vladimir Klebanov et al. · 2014 · 119 citations
Environmental Bisimulations for Higher-Order Languages
Davide Sangiorgi, Naoki Kobayashi, Eijiro Sumii · 2007 · 89 citations