What you have to trust¶
A proof is only worth as much as the reasons to believe it. This chapter asks what, exactly, you have to take on trust when the project says a property is proven, and how the project makes that list short.
Lean's checker¶
When you write a proof with tactics, the tactics don't decide whether it is
correct. They build a proof: a term, a value of the statement's type. Then
a small, separate program at the heart of Lean, the kernel, checks that
term against the statement. Tactics such as simp and omega are large and
clever, and could have bugs, but a bug in a tactic can only make it fail to
build a proof, or build one the kernel then rejects. It can't make a false
statement pass.
So the first thing you trust is the kernel: a program far smaller than the rest of Lean, and the same for everyone who uses it.
The second thing is that each statement says what you mean. Lean checks that the proof proves the statement; it can't check that the statement is the one you wanted. This is why every guarantee in the project has a plain-English headline beside its exact statement, and why the statements are worth reading for yourself.
sorry¶
sorry proves anything. It is there so you can leave a gap while you work
on the rest of a proof. Lean accepts it with a warning:
/-- warning: declaration uses `sorry` -/
#guard_msgs in
theorem wrong : 2 + 2 = 5 := by
sorry
/-- info: 'Learn.Engine.wrong' depends on axioms: [sorryAx] -/
#guard_msgs in
#print axioms wrong
/-- An argument that uses the wrong "fact" is accepted too. -/
theorem worse : 4 = 5 := by
rw [← wrong]
/-- info: 'Learn.Engine.worse' depends on axioms: [sorryAx] -/
#guard_msgs in
#print axioms worse
wrong is false, and Lean accepted it. Worse, worse uses it, and gets no
warning at all: the warning appears only where sorry is written, not in
everything that depends on it. A gap can hide two files away from the
theorem you're reading.
#print axioms finds it. It lists everything a theorem rests on without
proof, following every theorem it uses, all the way down. sorry shows up
as sorryAx, in wrong and in worse alike.
The project refuses gaps in two ways. make proofs first searches the
files under Proofs/ for the word sorry, and fails if it finds one:
That catches the obvious case, but a gap needn't be spelled sorry. The
tactic admit does the same thing:
/-- warning: declaration uses `sorry` -/
#guard_msgs in
theorem hidden : 2 + 2 = 5 := by
admit
/-- info: 'Learn.Engine.hidden' depends on axioms: [sorryAx] -/
#guard_msgs in
#print axioms hidden
So make proofs also asks Lean, for every theorem in every Proofs module,
what it rests on, as #print axioms does, and fails if anything is there
that shouldn't be. An admit in Proofs/ passes the search for sorry
and is stopped by this second check, which names the theorem and sorryAx.
Axioms¶
An axiom is a statement accepted without proof. You can declare one, and Lean will believe it:
axiom magic : 2 + 2 = 5
theorem byMagic : 2 + 2 = 5 := magic
/-- info: 'Learn.Engine.byMagic' depends on axioms: [magic] -/
#guard_msgs in
#print axioms byMagic
This is why the list from #print axioms matters: a theorem is only as
true as the axioms it rests on. Here are two of the project's guarantees:
/-- info: 'Proofs.Engine.rejected_action_changes_nothing' depends on axioms: [propext, Classical.choice] -/
#guard_msgs in
#print axioms Proofs.Engine.rejected_action_changes_nothing
/-- info: 'Proofs.Snap.whole_views_reveal_nothing_hidden' depends on axioms: [propext, Classical.choice, Quot.sound] -/
#guard_msgs in
#print axioms Proofs.Snap.whole_views_reveal_nothing_hidden
These three are Lean's standard axioms, which nearly all of mathematics in Lean rests on:
propext: two statements that imply each other are equal.Classical.choice: from a proof that something exists, you may pick one. Among other things it gives you that every statement is either true or false.Quot.sound: the rule for quotient types, from which Lean gets, among other things, that two functions giving equal results on every input are equal.
The project's proofs never mention them; they arrive through the library
lemmas that simp and the other tactics use. The project accepts exactly
these three, and no other.
decide and native_decide¶
You met decide in Snap: Lean works the statement out, and the kernel
checks the working. There is a faster tactic, native_decide, which
compiles the check to machine code and runs it. It is much faster on big
computations, but the kernel can't check machine code. It can only take the
compiled program's word for it:
theorem fiftyTwo : Games.Snap.deck.length = 52 := by decide
theorem fiftyTwoFast : Games.Snap.deck.length = 52 := by native_decide
/-- info: 'Learn.Engine.fiftyTwo' does not depend on any axioms -/
#guard_msgs in
#print axioms fiftyTwo
/-- info: 'Learn.Engine.fiftyTwoFast' depends on axioms: [fiftyTwoFast._native.native_decide.ax_1_1] -/
#guard_msgs in
#print axioms fiftyTwoFast
The decide proof rests on nothing at all. The native_decide proof rests
on a new axiom that Lean made for it, which says, in effect, "the compiled
program said so". That brings Lean's whole compiler into what you trust, so
the project doesn't use native_decide, and the axiom check in make
proofs would refuse it like any other.
The guarantees page¶
docs/GUARANTEES.md lists every guarantee in the project. Nobody writes it.
Tools/Guarantees.lean is a Lean program that loads the checked proofs and
writes the page from them: for each guarantee, its headline, its exact
statement, a link to its proof and the axioms it rests on.
The axioms it accepts:
/-- The axioms Lean's own kernel and standard library rest on. Anything else
(above all `sorryAx`) is flagged on the page. -/
def standardAxioms : List Name := [``propext, ``Classical.choice, ``Quot.sound]
and the check make proofs runs over every theorem in every Proofs
module, guarantee or not:
/-- Every theorem in every `Proofs` module, guarantee or bookkeeping, whose
proof depends on an axiom beyond the standard three: a `sorry` (`sorryAx`),
`native_decide` (which adds an axiom of its own for each use) or a declared
axiom. -/
def unsound (env : Environment) : MetaM (List (Name × List Name)) := do
let mut bad := []
for m in proofModules env do
let some idx := env.getModuleIdx? m | continue
let some md := env.header.moduleData[idx.toNat]? | continue
for info in md.constants do
unless info matches ConstantInfo.thmInfo _ do continue
let extra := (← collectAxioms info.name).toList.filter (!standardAxioms.contains ·)
unless extra.isEmpty do bad := (info.name, extra) :: bad
return bad
collectAxioms is what #print axioms uses. Any theorem with an axiom
outside the three is reported, and the program refuses to write the page.
To regenerate the page after changing a proof:
make proofs writes the page afresh and compares it with the committed
one, and fails if they differ, with docs/GUARANTEES.md is out of date: run
make guarantees. Change one headline in Proofs/Engine/Guarantees.lean
and you will see it. So the page can't fall behind the proofs, and a
proof's headline can't say one thing on the page and another in the code.
The proven code is the code that runs¶
A proof about step is worth having only if step is what decides your
game. In this project it is, because nothing is translated by hand.
Lean compiles every definition to C. After
you can open .lake/build/ir/Games/Snap/Rules.c and find Snap's step as
the C function lp_stichhalter_Games_Snap_step, compiled from the same
definition the proofs are about.
The hosts reach the engine through a handful of functions marked
@[export …] in Ffi/Export.lean, which gives each a fixed C name. Here is
the one that starts a table:
def newBytes (game config : ByteArray) : Except String AnySession := do
new (← utf8 "game" game) (← utf8 "config" config)
It takes raw bytes and lets Lean decode them, so no host code stands between what a client sent and what the engine reads. Every game is reached through one type with one case per game:
/-- Every registered game. Adding a game means adding a constructor here. -/
inductive AnySession where
| counter (s : Session Games.Counter.State)
| snap (s : Session Games.Snap.State)
| lol (s : Session Games.LoL.State)
| alba (s : Session Games.Alba.State)
deriving Inhabited
Each case holds a session of its own game, so these functions just pass
each request to that game's Session functions, the ones the proofs are
about. capi/sh.c wraps them in a plain C interface, and both hosts use
that:
- the Go server links the compiled C, through cgo, into one native program;
- the browser gets the very same C files, compiled to WebAssembly by
wasm/build.sh:
The engine imports nothing but Lean's Init and Std libraries, and does
no input or output, so the same code builds for both. The web tests also
check that the WebAssembly engine and the native one give the same answers.
What the proofs don't cover¶
The list of things you trust is short, but it isn't empty, and it is better to know it:
- The tools. Lean's kernel, its compiler from Lean to C, the C compiler, and Lean's runtime (which manages memory). The proofs are about the Lean definitions; the compiler is trusted to run them faithfully.
- The code around the engine.
capi/sh.c, the Go server and the browser page aren't proven. They can't change the rules, because they never decide anything, but they could fail to deliver what the engine says. -
The JSON text. The proofs are about
Jsonvalues. Turning a value into text and back is done byJson.renderand the parser inEngine/Json.lean, which are written aspartial def:partial def render : Json → String | null => "null" | bool true => "true" | bool false => "false" | num n => toString n | str s => escape s | arr xs => "[" ++ ",".intercalate (xs.toList.map render) ++ "]" | obj kvs => "{" ++ ",".intercalate (kvs.toList.map fun (k, v) => escape k ++ ":" ++ render v) ++ "}"partiallets a function call itself without Lean checking that it stops, at the price that proofs can't see inside it. So no proof says thatrenderwrites each value correctly. The tests check it instead. -Ffi/Export.leanitself, which has no proofs of its own. It is short, and each case only passes the request on, but that is a fact you check by reading, not one Lean has checked. - The statements. Above all: that each guarantee says what the rules of the game mean. Lean can't check that, and you can: read them.
Exercises¶
- Print the axioms of
Proofs.Engine.names_change_nothing_in_the_gameandProofs.Engine.only_admitted_events_are_shown, and compare them with whatdocs/GUARANTEES.mdsays. - Without
#print axioms, how could you tell thatworserests on a gap? - Add a theorem to
Proofs/Engine/Bookkeeping.leanwhose proof isadmit, and runmake proofs. Which of its two checks stops it? Then put the file back withgit restore Proofs/Engine/Bookkeeping.lean.
Solution
-
Lean prints these, and the page agrees:
/-- info: 'Proofs.Engine.names_change_nothing_in_the_game' depends on axioms: [propext, Classical.choice] -/ #guard_msgs in #print axioms Proofs.Engine.names_change_nothing_in_the_game /-- info: 'Proofs.Engine.only_admitted_events_are_shown' depends on axioms: [propext, Quot.sound] -/ #guard_msgs in #print axioms Proofs.Engine.only_admitted_events_are_shownThey differ from each other because they use different library lemmas, not because one is more trustworthy: both stay within the standard three.
-
You would have to read its proof, see that it uses
wrong, then readwrong's proof, and so on down. That is exactly the search#print axiomsdoes for you, and the reason the project runs it on every theorem rather than trusting the warnings. -
The search for the word
sorryfinds nothing, since the file saysadmit. Lean builds it with the warningdeclaration uses sorry, and then the axiom check fails:Unsound proofs: these theorems depend on non-standard axioms:, naming your theorem andsorryAx, thenproofs are unsound (see above).