How mit-pdos/perennial works
Main components
• Verification & Proof Infrastructure – This comprises the core of Perennial. It includes:
• The “program_logic” directory (e.g., crash weakest preconditions, invariants, atomic updates) that implements the reasoning framework.
• The “program_proof” directory, which holds proofs for various systems (e.g., journals, transactions, WAL, etc.) as well as examples and tutorials.
• GooseLang & Libraries:
• The “goose_lang” directory provides the formal semantics for a Go-like language. Within it you see subdirectories for typing, various libraries (map, slice, lock, etc.), and an FFI layer for interfacing with external components (e.g., disk and journaling).
• This layer also contains an “interpreter” which is used to test or run sequences of Goose programs.
• Helper & Infrastructure Modules:
• “Helpers” and “algebra” directories provide supporting libraries for integer arithmetic, lists, tactics, and Iris-based ghost-state reasoning.
• External Dependencies:
• Managed through git submodules in “external/”, these include verified versions of dependencies (Iris, coqutil, goose output projects, etc.) frozen to specific versions.
• Build & Compilation Support:
• Scripts and Makefile (plus utilities like “coqc.py”) support compiling the whole system. Also, there is a separate “new/” directory showing experimental/updated code and further proof artifacts.
Relationships and interactions
• The GooseLang layer forms the core language over which concurrent and crash-recovery properties are modeled. It interacts with:
• The implementation libraries (typed_mem, struct, map, slice, etc.) which encapsulate low-level Go programming idioms.
• The proof layers: “program_logic” and “program_proof” use the semantics and properties established in GooseLang to verify systems (e.g., journaling, file systems, transaction systems).
• The “Helpers” and “algebra” modules provide common utilities used across both the implementation and proof components.
• External directories form the foundation to ensure consistency – they supply the verified output for Goose projects and other external libraries (like Iris) that underpin the logic.
• The build scripts and Makefile wrap the compilation of Coq files via “coqc.py” and interact with the “vos”/“vok” mechanism to allow fast incremental checking.
Important architectural patterns/design principles
• Separation of Concerns: There is a clear split between the “implementation” (GooseLang’s executable semantics and its libraries) and the “verification” components (program_logic, program_proof).
• Layered Architecture: The foundation is given by the lower-level helper libraries (e.g., in Helpers and algebra), upon which GooseLang builds a language model. This, in turn, underpins the high-level proofs and system verifications.
• Dependency Management: External dependencies are included as submodules and are frozen to specific versions, ensuring stability.
• Modularity & Extensibility: With separate directories for each verification target (wal, txn, append_log, nfs, etc.), the system is built modularly, allowing you to isolate components for separate verification concerns.
Relevant technologies and libraries
• The system is developed in Coq and uses its proof tactics, type system, and extraction facilities.
• Goose, a domain-specific language for a subset of Go, is used both as an interpreter and as a target language for verification.
• Iris (and its associated libraries like coqutil, stdpp) plays a significant role in ghost state, invariants, and concurrency reasoning.
• Additional tooling – Python scripts (e.g., coqc.py, update-goose.py) and Makefile – facilitate compilation and dependency management.
Specific elements
• Verification & Proof Infrastructure (program_logic, program_proof)
• GooseLang Core and its Libraries (typed_mem, map, slice, lock, etc.)
• Helpers/Algebra (support libraries)
• External Dependencies (submodules: Iris, coqutil, goose output modules)
• Build / Execution Environment (Makefile, coqc.py, vos/vok compilation strategy)
• Clear labels on each component.
• Dependency of program_proof on components in GooseLang and Helpers.
• Interactions between the interpreter and the GooseLang semantics.
• Updates flowing from external dependency management.