This paper explores a fundamental trade-off in the world of formal logic: the balance between the "trustworthiness" of a theorem prover and the "efficiency" of its proofs. By strategically expanding the core of a popular theorem prover, the author demonstrates significant gains in speed and storage without sacrificing the rigor required for formal verification.
TL;DR
By extending the "minimalist" kernel of the HOL Light theorem prover to include implication and universal quantification as primitives, the author created HOLALA, which reduces proof file sizes by roughly 35% and speeds up proof checking by 38%. This work provides a rare qualitative measurement of how kernel design directly impacts the practical costs of large-scale formal verification.
What Problem Does This Paper Address?
Interactive Theorem Provers (ITPs) are software tools used to verify complex mathematical proofs or the correctness of hardware and software. To ensure these tools don't have bugs themselves, they are usually built around a kernel—a tiny, trusted core of basic logic rules.
The "de Bruijn criterion" suggests that this kernel should be as small as possible so it can be easily audited. For example, the kernel of HOL Light is famously minimalist: it treats only "equality" ($=$) as a primitive symbol. Every other logical concept (like "and," "or," or "for all") must be defined in terms of equality.
However, this minimalism comes at a cost. When a proof is exported for checking by an independent tool (like Dedukti), every high-level step must be "unrolled" into dozens or hundreds of tiny kernel-level steps. For massive projects like the proof of the Kepler Conjecture, this leads to enormous proof files that are computationally expensive to verify. The author investigates whether slightly expanding the kernel can solve this "bloat" problem.
Methods
The author developed HOLALA, a modified version of HOL Light with an extended kernel.
- Kernel Expansion: Unlike the original HOL Light, which only views equality as primitive, HOLALA adds two more symbols to the trusted core: implication ($\rightarrow$) and universal quantification ($\forall$).
- New Inference Rules: To support these symbols, four new primitive inference rules were added to the kernel: Modus Ponens (MP), Discharge (DISCH), Generalization (GEN), and Specialization (SPEC).
- Toolchain Update: The author updated Holide (a translation tool) and Dedukti (a universal proof checker) to recognize these new primitives. This allowed the system to verify proofs generated by the new HOLALA kernel.
- Comparative Analysis: The author ran the standard HOL Light theory library through both the original system and HOLALA to compare file sizes, translation times, and proof-checking speeds.
Datasets
The evaluation used the (OpenTheory) HOL Light standard theory library. This is a comprehensive collection of formalized mathematics that serves as a standard benchmark in the Higher-Order Logic (HOL) community.
Key Insights and Ideas
- The "Minimalist Tax": The paper quantifies the overhead of extreme minimalism. In standard HOL Light, a simple "conjunction introduction" (proving $A \wedge B$ given $A$ and $B$) takes 55 inference steps because it has to be translated into equality logic. In HOLALA, this drops to 31 steps.
- Strategic Primitives: You don't need to make everything a primitive to see gains. By choosing $\rightarrow$ and $\forall$—symbols that many other logical connectives depend on—the author created a "shortcut" for a vast majority of proof steps. For instance, the disjunction introduction rule saw a massive reduction from 156 steps down to just 21.
- Efficiency vs. Reliability: While a larger kernel is technically harder to verify, the author argues that the trade-off is worth it. A 38% speedup in checking time makes independent verification of massive proofs much more feasible for researchers.
Key Results
The transition from a minimalist kernel (HOL Light) to an extended kernel (HOLALA) yielded impressive quantitative improvements:
- Proof File Size: The gzipped article files were reduced to 64.36% of their original size.
- Translation Time: The time taken to convert proofs for the checker improved by 41.81%.
- Proof Checking Time: The actual verification process in Dedukti became 38.04% faster.
- Dedukti File Size: The resulting files used by the proof checker were reduced to 64.92% of the original size.
Limitations and Future Work
- The Soundness Burden: Every line of code added to a kernel is a potential liability. The author acknowledges that larger kernels are harder to guarantee as "sound" (error-free).
- Loss of Original Definitions: By making $\forall$ and $\rightarrow$ primitive, users lose the original mathematical definitions used in HOL Light. To fix this, the author had to re-prove those definitions as theorems using the axiom of extensionality.
- Further Expansion: The author suggests that even greater gains could be achieved by adding more primitives, such as conjunction ($\wedge$), disjunction ($\vee$), and existential quantification ($\exists$). Future work could involve testing these "maximalist" kernels to find the point of diminishing returns.
Summary updated