# tz18/ecctoecca architecture

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

- Interactive diagram: https://gitdiagram.com/tz18/ecctoecca
- Repository: https://github.com/tz18/ecctoecca

## Overview

##### Project type and purpose
- This is a Coq-based mechanization of Luo’s Extended Calculus of Constructions (ECC) and its ANF-style variant (ECCA), along with a translator from ECC to ECCA, packaged as a set of Coq theories and proofs rather than a typical “application.”
- The README describes how to set up the OPAM/Coq environment and compile the entire mechanization via Makefile, and outlines the main formal components: ECC grammar, ECCA grammar, lemmas, translation, and proofs.

##### File structure
- Top‐level directories:
- common/                – shared definitions (universes, atoms, integration of shifted-names)
- ECC/                   – ECC grammar, reduction, typing, equivalence modules
- ECCA/                  – CC^AE (ANF variant) grammar, reduction, typing, continuations, lemmas
- translation/           – translator from ECC→ECCA and compositionality/preservation proofs
- shifted-names/         – a git submodule providing the Tyde19 shifted-names library
- materials/, outdated/  – supporting PDFs and legacy code (not part of the build pipeline)
- Configuration files: Makefile, CoqMakefile.conf, _CoqProject, and OPAM instructions in the README.
- Notice the dependencies: shifted-names → common → ECC → ECCA → translation.

##### README for additional insights
- It prescribes an OPAM-based toolchain (OCaml switch, Coq, Coq-Equations, CoqIDE).
- Build steps: submodule init/update followed by make.
- The README’s Table of Contents already outlines logical layers: common, ECC, ECCA, translation.

##### Components and interactions
a. Main components
- External Environment: OPAM / OCaml switch, Coq, CoqIDE, Coq-Equations
- Build System: Makefile, _CoqProject, CoqMakefile.conf
- Library Layer: shifted-names submodule
- Core Definitions: common/Atom.v (universes, atoms)
- ECC Layer: ECC.v (grammar, reduction, typing, equivalence)
- ECCA Layer: core.v, reduction.v, typing.v, continuations.v, equiv.v, key_lemmas.v
- Translation Layer: translator.v, compositionality.v, trans_preservation.v
- Documentation/Materials: materials/, proof‐desc PDFs (supporting reading, not compiled)
b. Relationships and interactions
- The “Build System” orchestrates Coq compilation of each directory in dependency order.
- shifted-names is imported by common; common is imported by ECC; ECC is imported by ECCA; ECCA is imported by translation.
- The translator module consumes ECC terms/environments and produces ECCA terms/environments; the compositionality and preservation proofs depend on both ECC and ECCA libraries.
- External tools (Coq, Coq-Equations) provide language features and proof machinery.
c. Architectural patterns
- Layered architecture: library → core definitions → source language (ECC) → target ANF language (ECCA) → translation/proofs.
- Pipeline pattern for translation: ECC grammar → translator → ECCA grammar → proof obligations.
- Make-driven build graph representing compile-time dependencies.
d. Key technologies/libraries
- Coq proof assistant (v8.13.2)
- Coq-Equations plugin
- OPAM for package management
- shifted-names library (Tyde19)
- Standard Makefile + CoqMakefile for dependency tracking

##### Elements
- Clear labels: e.g., “OPAM & Coq Environment,” “Makefile,” “shifted-names,” “common,” “ECC,” “ECCA,” “translation.”
- From OPAM/Coq → Build System → each directory
- From shifted-names → common → ECC → ECCA → translation
- From ECC modules → translator → ECCA modules
- Rectangles for Coq modules/directories
- Clouds for external tools (OPAM, CoqIDE)

## Diagram (Mermaid)

```mermaid
flowchart TD
    %% External Tools
    subgraph "External Environment"
        direction TB
        OPAMCoq["OPAM & Coq Environment"]:::external
    end

    %% Build System
    subgraph "Build System"
        direction TB
        Makefile["Makefile"]:::build
        CoqMakefile["CoqMakefile.conf"]:::build
        CoqProject["_CoqProject"]:::build
    end

    %% Library Layer
    Shifted["shifted-names"]:::library

    %% Core Definitions
    Atom["common/Atom.v"]:::core

    %% ECC Layer
    ECCv["ECC/ECC.v"]:::ecc

    %% ECCA Layer
    subgraph "ECCA Layer"
        direction TB
        Core["ECCA/core.v"]:::ecca
        Reduction["ECCA/reduction.v"]:::ecca
        Typing["ECCA/typing.v"]:::ecca
        Continuations["ECCA/continuations.v"]:::ecca
        Equiv["ECCA/equiv.v"]:::ecca
        KeyLemmas["ECCA/key_lemmas.v"]:::ecca
        CoreLemmas["ECCA/core_lemmas.v"]:::ecca
        CoreLemmasNames["ECCA/core_lemmas_names.v"]:::ecca
        EquivLemmas["ECCA/equiv_lemmas.v"]:::ecca
        ReductionLemmas["ECCA/reduction_lemmas.v"]:::ecca
        TypingLemmas["ECCA/typing_lemmas.v"]:::ecca
        ContinuationsLemmas["ECCA/continuations_lemmas.v"]:::ecca
        Practice["ECCA/practice.v"]:::docs
    end

    %% Translation Layer
    subgraph "Translation Layer"
        direction TB
        Translator["translation/translator.v"]:::trans
        Compositionality["translation/compositionality.v"]:::trans
        Preservation["translation/trans_preservation.v"]:::trans
    end

    %% Documentation
    subgraph "Documentation & Materials"
        direction TB
        Materials["materials"]:::docs
        Outdated["outdated"]:::docs
    end

    %% Dependencies
    OPAMCoq --> Makefile
    OPAMCoq --> CoqMakefile
    OPAMCoq --> CoqProject

    Makefile --> Shifted
    Makefile --> Atom
    Makefile --> ECCv
    Makefile --> Core
    Makefile --> Translator

    Shifted --> Atom
    Atom --> ECCv
    ECCv --> Core
    Core --> Reduction
    Reduction --> Typing
    Typing --> Continuations
    Continuations --> Equiv
    Equiv --> KeyLemmas
    KeyLemmas --> CoreLemmas
    CoreLemmas --> CoreLemmasNames
    CoreLemmasNames --> EquivLemmas
    EquivLemmas --> ReductionLemmas
    ReductionLemmas --> TypingLemmas
    TypingLemmas --> ContinuationsLemmas

    ECCv --> Translator
    Core --> Translator
    ECCv --> Compositionality
    Equiv --> Compositionality
    Translator --> Preservation
    TypingLemmas --> Preservation

    %% Click Events
    click Makefile "https://github.com/tz18/ecctoecca/tree/master/Makefile"
    click CoqMakefile "https://github.com/tz18/ecctoecca/blob/master/CoqMakefile.conf"
    click CoqProject "https://github.com/tz18/ecctoecca/tree/master/_CoqProject"
    click Shifted "https://github.com/tz18/ecctoecca/tree/master/shifted-names/"
    click Atom "https://github.com/tz18/ecctoecca/blob/master/common/Atom.v"
    click ECCv "https://github.com/tz18/ecctoecca/blob/master/ECC/ECC.v"
    click Core "https://github.com/tz18/ecctoecca/blob/master/ECCA/core.v"
    click Reduction "https://github.com/tz18/ecctoecca/blob/master/ECCA/reduction.v"
    click Typing "https://github.com/tz18/ecctoecca/blob/master/ECCA/typing.v"
    click Continuations "https://github.com/tz18/ecctoecca/blob/master/ECCA/continuations.v"
    click Equiv "https://github.com/tz18/ecctoecca/blob/master/ECCA/equiv.v"
    click KeyLemmas "https://github.com/tz18/ecctoecca/blob/master/ECCA/key_lemmas.v"
    click CoreLemmas "https://github.com/tz18/ecctoecca/blob/master/ECCA/core_lemmas.v"
    click CoreLemmasNames "https://github.com/tz18/ecctoecca/blob/master/ECCA/core_lemmas_names.v"
    click EquivLemmas "https://github.com/tz18/ecctoecca/blob/master/ECCA/equiv_lemmas.v"
    click ReductionLemmas "https://github.com/tz18/ecctoecca/blob/master/ECCA/reduction_lemmas.v"
    click TypingLemmas "https://github.com/tz18/ecctoecca/blob/master/ECCA/typing_lemmas.v"
    click ContinuationsLemmas "https://github.com/tz18/ecctoecca/blob/master/ECCA/continuations_lemmas.v"
    click Practice "https://github.com/tz18/ecctoecca/blob/master/ECCA/practice.v"
    click Translator "https://github.com/tz18/ecctoecca/blob/master/translation/translator.v"
    click Compositionality "https://github.com/tz18/ecctoecca/blob/master/translation/compositionality.v"
    click Preservation "https://github.com/tz18/ecctoecca/blob/master/translation/trans_preservation.v"
    click Materials "https://github.com/tz18/ecctoecca/tree/master/materials/"
    click Outdated "https://github.com/tz18/ecctoecca/tree/master/outdated/"

    %% Styles
    classDef external fill:#CCE5FF,stroke:#0077CC,stroke-width:2px;
    classDef build fill:#E8F0FE,stroke:#1967D2,stroke-width:2px;
    classDef library fill:#D0F0C0,stroke:#2E7D32,stroke-width:2px;
    classDef core fill:#B3E5FC,stroke:#0288D1,stroke-width:2px;
    classDef ecc fill:#C8E6C9,stroke:#388E3C,stroke-width:2px;
    classDef ecca fill:#FFE0B2,stroke:#F57C00,stroke-width:2px;
    classDef trans fill:#E1BEE7,stroke:#8E24AA,stroke-width:2px;
    classDef docs fill:#F5F5F5,stroke:#9E9E9E,stroke-width:2px;
```
