A Coq library for representing and reasoning about recursive, effectful, and non-terminating programs using interaction trees.
Interaction Trees is a Coq library for representing and reasoning about recursive, effectful, and potentially non-terminating programs. It provides a coinductive data structure called interaction trees that can model programs with side effects (like I/O, state, or exceptions) within the pure setting of Coq, enabling formal verification of impure computations.
Researchers and developers working on formal verification, programming language semantics, or verified software in Coq, particularly those needing to model and reason about effectful or non-terminating programs.
It offers a principled, compositional framework for embedding impure programs in Coq with strong equational reasoning support, unlike ad-hoc approaches, and integrates with Coq's proof machinery for rigorous verification.
A Library for Representing Recursive and Impure Programs in Coq
Open-Awesome is built by the community, for the community. Submit a project, suggest an awesome list, or help improve the catalog on GitHub.
Enables representation of side-effecting programs like I/O and state within Coq's pure logic, using coinductive trees as demonstrated in the core ITree.ITree module.
Provides theorems and tools for proving program equivalence through bisimulation, facilitating rigorous correctness proofs as highlighted in ITree.ITreeFacts.
Supports defining custom event types and handlers, allowing flexible modeling of various computational effects, shown in the Events module and tutorials.
Includes detailed tutorials and example files like ReadmeExample.v, helping users learn and apply the library effectively, as noted in the README.
Relies on axioms such as UIP and excluded middle, which can compromise constructiveness and may not align with axiom-free Coq developments, as admitted in Axioms.v.
Requires installation of external Coq libraries like coq-paco and coq-ext-lib, adding to setup complexity and potential version compatibility issues.
Demands expertise in coinduction, bisimulation, and Coq proof techniques, making it inaccessible for those new to formal methods or semantics.