montrepol / README-project.md
SNAPKITTYWEST's picture
montrepol: exact mathematics in Haskell, with proofs and a certifying solver
5316c4e verified
|
Raw History Blame Contribute Delete
10.9 kB
# montrepol
Exact mathematics in Haskell, with every claim tied to a test that can fail.
This repository consolidates the parts of five earlier repositories that held
real mathematics, and drops the rest. It depends on nothing but GHC: no
Hackage packages, no Rust, no Python. The test harness, pseudorandom generator,
TOML reader and every algorithm are written here.
```
cabal build all # GHC 9.10.1, cabal 3.12
cabal test all # 182 checks across 6 packages
cabal run mp-gate # rules R1-R6 over the model, the sources and the build
cabal run mp-gate -- mutants # planted defects in code, proofs and refinements; each must be caught
agda --no-libraries -i formal formal/Everything.agda # Agda 2.6.3, --safe, no stdlib
```
## Packages
| Package | What it is | Checked against |
| --- | --- | --- |
| `mp-check` | Test harness: SplitMix64, generators, properties, ID-tagged tests | An independent C SplitMix64; a planted false property |
| `mp-linalg` | Semirings, matrices with dimensions in the type, naive and Strassen products, Bareiss determinant, rank, inverse, participation ratio | Leibniz expansion, the definition of the product, Floyd–Warshall |
| `mp-lie` | Root systems A–G, simple roots, Cartan matrices, Weyl group orders by orbit–stabilizer | The classification tables (Bourbaki, Humphreys) |
| `mp-seq` | Berlekamp–Massey over any field, LFSRs, periods | Brute-force minimality; Massey's 2L theorem |
| `mp-analytic` | Sieve, von Mangoldt, Chebyshev ψ, exact Bernoulli numbers, ζ by Euler–Maclaurin, Riemann–Siegel θ, Hardy Z, zeros, the explicit formula | Trial division, OEIS, lcm(1..x), von Staudt–Clausen, closed forms of ζ, Odlyzko's table |
| `mp-hcalc` | Hcalc: a certifying SMT core. DPLL SAT with resolution refutations, Fourier–Motzkin linear arithmetic over ℚ with Farkas certificates, and DPLL(T) over both | Brute-force truth tables, grids of rational points, and independent certificate checkers that must reject forged certificates |
| `mp-lambda` | The simply typed λ-calculus, and refinement types `{v:Int \| φ}` over it whose verification conditions Hcalc decides | Progress, preservation and substitution on random terms; accepted programs are run and their postconditions checked |
| `mp-gate` | The gate: R1–R6 over the model, sources, proofs, the Liquid layer and the build; mutant replay | Its own planted defects (GT-01..GT-10) |
## Hcalc and refinement types
Hcalc is an SMT solver written here, for quantifier-free linear rational
arithmetic with propositional structure. It is small and slow, and it does not
ask to be trusted: every answer carries a certificate.
| Answer | Certificate | Checked by |
| --- | --- | --- |
| SAT | a model | evaluating the formula directly, ignoring the encoding |
| UNSAT (propositional) | a tree-resolution refutation read off the DPLL search | replaying the resolution steps |
| UNSAT (arithmetic) | Farkas multipliers for every learned theory lemma | summing the constraints and checking the contradiction |
The checker trusts the Tseitin encoding and the reading of terms as linear
expressions; HC-07 tests the encoding against truth tables.
`mp-lambda`'s refinement checker sends each subtyping obligation to Hcalc and
accepts it only when the certificate checks. Hcalc decides over ℚ, and a
statement valid over ℚ is valid over ℤ, so acceptance is sound for integer
programs. The converse fails: `x < y ⟹ x + 1 ≤ y` holds over ℤ but is rejected,
with a non-integral counter-model (LM-10).
## Liquid Haskell
`liquid/` is a separate build that compiles core modules a second time with
the Liquid Haskell plugin and Z3. The refinements live in the core sources as
`{-@ … @-}` comments, which GHC ignores, so the core build is unchanged and
still depends on nothing outside GHC. `liquid/` is the one place allowed to use
Hackage and an external solver. The gate enforces that the exemption runs one
way only: the root build may not include `liquid/`, and no core package may
depend on it.
Liquid Haskell checks `MP.Lambda.Simple` as it is in the core:
- `size` is at least 1.
- `typeOf`, `shift`, `subst` and `step` terminate.
- `evaluate` terminates because its fuel decreases.
- Every pattern match in the module is total.
GHC checks none of these. This is the `refined` level: it trusts Liquid
Haskell 0.9.10.1.2 and Z3 4.8.12, a larger trusted base than Agda's kernel,
and it is kept apart from `proved` for that reason.
```
cd liquid && cabal update && cabal build all # needs z3 on PATH
```
## Dex
`dex/` holds [Dex](https://github.com/google-research/dex-lang) code: integer
matrices typed by their index sets, the same seven Strassen products, and the
exact Kish comparison. Each check is compared with a hand-computed value or
an independent computation. The files are quines: Dex runs them, and the
output must equal the file, so every `>` line is an assertion. Checks are
tagged `# check DX-01` and registered like any other ID.
Dex's last commit (January 2024) needs LLVM 12, GHC 8.10.7 and a pinned
`llvm-hs`. Ubuntu 24.04 does not package LLVM 12, so `dex/build.sh` installs
Ubuntu 22.04's packages of it, fetches Dex and `llvm-hs` by git at pinned
commits, and builds them into `dex/.toolchain`.
```
./dex/build.sh && ./dex/check.sh
```
## Proofs
`formal/` holds Agda proofs, checked under `--safe --without-K` with no
standard library: equality, naturals, vectors and the algebra are defined
there from nothing.
| Ledger key | What is proved | Where |
| --- | --- | --- |
| `strassen-identities` | Strassen's seven products give the four entries of the 2×2 product, in any abelian group with a two-sided distributive product: no associativity, commutativity or unit assumed. Matrices over a ring are such a structure (standard, not proved here), so this covers blocks | `formal/Montrepol/Strassen.agda` |
| `abelian-solver-sound` | The abelian-group normaliser the Strassen proof uses is sound in every model, so its `refl` steps are trustworthy | `formal/Montrepol/Solver.agda` |
| `kish-lower-bound` | Σ wᵢ² ≤ (Σ wᵢ)² for all natural weights, so k_eff ≥ 1 | `formal/Montrepol/Kish.agda` |
What is *not* proved is recorded too. That `MP.Matrix.strassenSq` uses exactly
these products is checked by reading and by the LA-03 tests, not mechanically.
The Kish upper bound (Cauchy–Schwarz) is tested, not proved.
[`CONFORMANCE.md`](CONFORMANCE.md) lists all 39 conformance IDs and the ledger's
untested claims, by package and honesty level. It is generated from [`model/`](model/), never edited.
## Where it came from
| Repository | Kept | Dropped, and why |
| --- | --- | --- |
| `matmul` | The claim discipline: levels, register, generated conformance, the rules | All of the Rust. There was no matrix multiplication in it; it was an empty template. `mp-linalg` is the matmul. |
| `prism-ciris` | The integer kernel's ideas, done correctly: exact Kish k_eff and participation ratio (`mp-linalg`), GF(2) recurrences done properly with Berlekamp–Massey (`mp-seq`), E8 (`mp-lie`) | The ethics, governance and "atlas" prose, the 188 vocabulary files and the `.lex.tex` "proofs": 200 of 223 theorems had no parameters, 196 were `decide` on constants, and no CI step ran Lean. See below for the two defects found in its kernel. |
| `prime-router` | ψ(x), the projection of ψ(x) − x onto zeta zeros, now as the explicit formula with measured error (`mp-analytic`); its zero table, as an oracle | "Hypersphere brain", Λ − π, "hyperbolic deficit", GloVe, the Ollama server. The table file was named `100k` and held 512 rows. |
| `cluster` | Not yet | 22k lines of infrastructure rendering. Porting it means byte-for-byte golden tests against its `generated/`, and it only means something with the hardware. |
| `jsonschema` | Not yet | A fork of an actively maintained upstream. A Haskell validator is a large, separate piece of work, with the official JSON-Schema-Test-Suite as its oracle. |
### Defects found in the prism-ciris kernel
Both were reproduced by compiling the original functions on their own before
anything here was written:
1. `check_integer_kish_keff` used saturating `u64` arithmetic and was described
as overflow-free. For weights `[2^32, 2^32]`, whose effective size is exactly
2, it accepted `min_keff = 3` and `min_keff = 1000`. Here the comparison is
over unbounded integers (LA-08), and a mutant that reintroduces 64-bit
saturation is caught.
2. `evaluate_gram_ratchet`'s comment said `tr(G)^2 >= 2 ||G||_F^2`, but for a
2×2 positive semi-definite matrix that holds only when `G` is a multiple of
the identity, since `(l1 + l2)^2 <= 2 (l1^2 + l2^2)`. The code checked
`4 tr^2 >= 7 ||G||_F^2` instead. Here the participation ratio
`tr(G)^2 / tr(G^2)` is shown to lie in `[1, 2]` and to equal 2 exactly for
scalar matrices (LA-10).
## How claims work
Every claim has one of five levels, and the gate fails if they blur:
- **`some-true`**: reproduced from a cited authority. Not established here.
- **`build`**: constructed here and checked by a test against an oracle.
Evidence, not proof.
- **`open`**: measured and reported. Never asserted.
- **`proved`**: machine-checked by Agda under `--safe`. The ledger names the
file and the lemmas; the gate checks they exist, that the file is `--safe`
with no escape hatches, and that `formal/Everything.agda` imports it so CI
checks it.
- **`refined`**: checked by Liquid Haskell, trusting it and Z3. The ledger
names a core source and functions; the gate checks each has a spec and that
the liquid build compiles the module.
Asserting words ("proves", "guarantees", "establishes", ...) may not appear in
a `build` or `open` claim, and the gate checks that. Property tests over random
inputs are evidence; they are not proofs, and this repository calls a claim
proved only when Agda has checked it.
[`AGENTS.md`](AGENTS.md) defines the rules. [`VERIFICATION.md`](VERIFICATION.md)
says what each gate discharges and records the defects planted to show it can
fail.
## Toolchain
GHC 9.10.1 and cabal 3.12.1.0, installed with `ghcup`. `libgmp` is needed to
link. Agda 2.6.3 (Ubuntu 24.04's `agda-bin`) for the proofs; run it under a
UTF-8 locale, since its messages print the proofs' Unicode. `cabal.project` sets `active-repositories: :none`: a dependency from
outside the compiler cannot even be resolved, and the build needs no network.
## Licence
GNU Affero General Public License v3.0 or later ([`LICENSE`](LICENSE)). Parts
adapted from the UOR Foundation's template keep their MIT / Apache-2.0 notices;
see [`NOTICE`](NOTICE). Every Haskell source carries
`SPDX-License-Identifier: AGPL-3.0-or-later` on its first line (`.cabal` files
on their second, after `cabal-version`), and the gate fails a file that does
not (R6).