We gratefully acknowledge support from
the Simons Foundation and member institutions.
Full-text links:

Download:

Current browse context:

cs.PL

Change to browse by:

cs

References & Citations

DBLP - CS Bibliography

Bookmark

(what is this?)
CiteULike logo BibSonomy logo Mendeley logo del.icio.us logo Digg logo Reddit logo

Computer Science > Programming Languages

Title: Lean4Lean: Towards a formalized metatheory for the Lean theorem prover

Abstract: In this paper we present a new "external verifier" for the Lean theorem prover, written in Lean itself. This is the first complete verifier for Lean 4 other than the reference implementation in C++ used by Lean itself, and our new verifier is competitive with the original, running between 20% and 50% slower and usable to verify all of Lean's mathlib library, forming an additional step in Lean's aim to self-host the full elaborator and compiler. Moreover, because the verifier is written in a language which admits formal verification, it is possible to state and prove properties about the kernel itself, and we report on some initial steps taken in this direction to formalize the Lean type theory abstractly and show that the kernel correctly implements this theory, to eliminate the possibility of implementation bugs in the kernel and increase the trustworthiness of proofs conducted in it. This work is still ongoing but we plan to use this project to help justify any future changes to the kernel and type theory and ensure unsoundness does not sneak in through either the abstract theory or implementation bugs.
Comments: 17 pages, submitted to ITP 2024
Subjects: Programming Languages (cs.PL)
ACM classes: F.4.1; G.4; D.2.4
Cite as: arXiv:2403.14064 [cs.PL]
  (or arXiv:2403.14064v1 [cs.PL] for this version)

Submission history

From: Mario Carneiro [view email]
[v1] Thu, 21 Mar 2024 01:22:52 GMT (96kb,D)

Link back to: arXiv, form interface, contact.