Proceedings of the ACM on Programming Languages · 2019 · 129 citations · 44 references
ComputingComputer ScienceFormal MethodsProgramming LanguagesTheory Of ComputationAbstract Syntax TreesInterpreter DesignRecursion TheorySyntax-semantics InterfaceBisimulationCoqEquational ReasoningExtraction Of Executable CodeFormal VerificationOperational SemanticsStrong BisimulationWeak Bisimulation
Interaction trees (ITrees) are a general-purpose data structure for representing the behaviors of recursive programs that interact with their environments. A coinductive variant of “free monads,” ITrees are built out of uninterpreted events and their continuations. They support compositional construction of interpreters from event handlers , which give meaning to events by defining their semantics as monadic actions. ITrees are expressive enough to represent impure and potentially nonterminating, mutually recursive computations, while admitting a rich equational theory of equivalence up to weak bisimulation. In contrast to other approaches such as relationally specified operational semantics, ITrees are executable via code extraction, making them suitable for debugging, testing, and implementing software artifacts that are amenable to formal verification. We have implemented ITrees and their associated theory as a Coq library, mechanizing classic domain- and category-theoretic results about program semantics, iteration, monadic structures, and equational reasoning. Although the internals of the library rely heavily on coinductive proofs, the interface hides these details so that clients can use and reason about ITrees without explicit use of Coq’s coinduction tactics. To showcase the utility of our theory, we prove the termination-sensitive correctness of a compiler from a simple imperative source language to an assembly-like target whose meanings are given in an ITree-based denotational semantics. Unlike previous results using operational techniques, our bisimulation proof follows straightforwardly by structural induction and elementary rewriting via an equational theory of combinators for control-flow graphs.
44
A Structural Approach to Operational Semantics
Gordon Plotkin · 2004 · 2K citations
Notions of computation and monads
Eugenio Moggi · Information and Computation · 1991 · 1.7K citations
Gerwin Klein, Kevin Elphinstone, Gernot Heiser et al. · 2009 · 1.6K citations
Imperative functional programming
Simon Jones, Philip Wadler · 1993 · 1.2K citations · Full text
Formal verification of a realistic compiler
Xavier Leroy · Communications of the ACM · 2009 · 1.1K citations