Choice Trees: Representing Nondeterministic, Recursive, and Impure Programs in Coq

Abstract

This paper introduces Choice Trees (ctrees), a monad for modeling nondeterministic, recursive, and impure programs in Coq. Inspired by Xia et al.'s itrees, this novel data structure embeds computations into coinductive trees with three kind of nodes: external events, and two variants of nondeterministic branching. This apparent redundancy allows us to provide shallow embedding of denotational models with internal choice in the style of ccs, while recovering an inductive LTS view of the computation. CTrees inherit a vast collection of bisimulation and refinement tools, with respect to which we establish a rich equational theory. We connect ctrees to the itrees infrastructure by showing how a monad morphism embedding the former into the latter permits to use ctrees to implement nondeterministic effects. We demonstrate the utility of ctrees by using them to model concurrency semantics in two case studies: ccs and cooperative multithreading.

References in corpus (6)

• General Recursion via Coinductive Types
• Interaction Trees: Representing Recursive and Impure Programs in Coq
• Partiality, Revisited: The Partiality Monad as a Quotient Inductive-Inductive Type
• An Equational Theory for Weak Bisimulation via Generalized Parameterized Coinduction
• A Model of Cooperative Threads
• LAGC Semantics of Concurrent Programming Languages

Cited by in corpus (6)

• Fully Composable and Adequate Verified Compilation with Direct Refinements between Open Modules (Technical Report)
• A HAT Trick: Automatically Verifying Representation Invariants Using Symbolic Finite Automata
• Provably Fair Cooperative Scheduling
• Structural Temporal Logic for Mechanized Program Verification
• Memory Simulations, Security and Optimization in a Verified Compiler
• Denotation-based Compositional Compiler Verification