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 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 lists all 39 conformance IDs and the ledger's untested claims, by package and honesty level. It is generated from 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 defines the rules. 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). Parts adapted from the UOR Foundation's template keep their MIT / Apache-2.0 notices; see 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).