# mit-pdos/perennial architecture

> Architecture diagram of the GitHub repository mit-pdos/perennial, generated by GitDiagram from its file tree, README and a sample of source files (last updated 2025-03-31). It is an AI-made overview: check details against the source.

- Interactive diagram: https://gitdiagram.com/mit-pdos/perennial
- Repository: https://github.com/mit-pdos/perennial

## Overview

##### 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.

## Diagram (Mermaid)

```mermaid
flowchart TD

    %% Verification & Proof Infrastructure
    subgraph "Verification & Proof Infrastructure"
        ProgLogic("Program Logic"):::proof
        ProgProof("Program Proof"):::proof
    end

    %% GooseLang Core & Libraries
    subgraph "GooseLang Core & Libraries"
        GooseCore("GooseLang Core"):::implementation
        Interpreter("Interpreter"):::implementation
    end

    %% Helpers & Infrastructure Modules
    subgraph "Helpers & Infrastructure Modules"
        Helpers("Helpers"):::helpers
        Algebra("Algebra"):::helpers
    end

    %% External Dependencies
    subgraph "External Dependencies"
        ExDeps("External Dependencies"):::external
    end

    %% Build & Compilation Support
    subgraph "Build & Compilation Support"
        Makefile("Makefile"):::build
        COQC("coqc.py"):::build
    end

    %% Relationships
    %% Helpers and Algebra support GooseLang Core and Verification layers
    Helpers -->|"supports"| GooseCore
    Algebra -->|"supports"| GooseCore

    Helpers -->|"supports"| ProgLogic
    Helpers -->|"supports"| ProgProof
    Algebra -->|"supports"| ProgLogic
    Algebra -->|"supports"| ProgProof

    %% External Dependencies provide foundational support
    ExDeps -->|"provides"| GooseCore
    ExDeps -->|"supports"| ProgLogic
    ExDeps -->|"supports"| ProgProof

    %% GooseLang Core interactions
    GooseCore -->|"executes"| Interpreter
    GooseCore -->|"defines"| ProgLogic
    GooseCore -->|"verifies"| ProgProof

    %% Verification layers dependency
    ProgLogic -->|"builds_upon"| ProgProof

    %% Build tools compile key components
    Makefile -->|"compiles"| GooseCore
    Makefile -->|"compiles"| ProgLogic
    Makefile -->|"compiles"| ProgProof

    COQC -->|"compiles"| GooseCore
    COQC -->|"compiles"| ProgLogic
    COQC -->|"compiles"| ProgProof

    %% Styles
    classDef proof fill:#B3E5FC,stroke:#0288D1,stroke-width:2px;
    classDef implementation fill:#C8E6C9,stroke:#388E3C,stroke-width:2px;
    classDef helpers fill:#FFF9C4,stroke:#FBC02D,stroke-width:2px;
    classDef external fill:#FFCDD2,stroke:#D32F2F,stroke-width:2px;
    classDef build fill:#D1C4E9,stroke:#7B1FA2,stroke-width:2px;

    %% Click Events
    click ProgLogic "https://github.com/mit-pdos/perennial/tree/master/src/program_logic"
    click ProgProof "https://github.com/mit-pdos/perennial/tree/master/src/program_proof"
    click GooseCore "https://github.com/mit-pdos/perennial/tree/master/src/goose_lang"
    click Interpreter "https://github.com/mit-pdos/perennial/tree/master/src/goose_lang/interpreter"
    click Helpers "https://github.com/mit-pdos/perennial/tree/master/src/Helpers"
    click Algebra "https://github.com/mit-pdos/perennial/tree/master/src/algebra"
    click ExDeps "https://github.com/mit-pdos/perennial/tree/master/external"
    click Makefile "https://github.com/mit-pdos/perennial/tree/master/Makefile"
    click COQC "https://github.com/mit-pdos/perennial/blob/master/etc/coqc.py"
```
