How tz18/ecctoecca works
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)