HL Teacher (solutions) source diff
HL/Equiv.lean
1111 -- This chapter develops a notion of *behavioral equivalence* for Imp's
1212 -- expressions and commands.
1313 --
14--- To illustrate it use, we verify that program transformations such as
14+-- To illustrate its use, we verify that program transformations such as
1515 -- constant folding preserve behavior. Along the way we also see
1616 -- techniques for proving that two programs are *not* equivalent. Finally,
1717 -- we close with an extended look at what equivalence means once Imp is
794794 injection heq with beq ceq
795795 subst beq ceq
796796 rw [hb] at hb'
797- specialize ih2 rfl
797+ specialize ih2 (by rfl)
798798 apply Com.EvalR.whileTrue hb' _ ih2
799799 · rw [equiv_def] at hc
800800 exact hc.mp hc'
813813 injection heq with beq ceq
814814 subst beq ceq
815815 rw [← hb] at hb'
816- specialize ih2 rfl
816+ specialize ih2 (by rfl)
817817 apply Com.EvalR.whileTrue hb' _ ih2
818818 · rw [equiv_def] at hc
819819 exact hc.mpr hc'
21762176 bne_eq_false_iff_eq] at h'
21772177 rw [←h', TotalMap.update_same]
21782178 | whileTrue hb hc hloop ihc ihloop =>
2179- specialize ihloop rfl; subst_vars
2179+ specialize ihloop (by rfl); subst_vars
21802180 inversion hc
21812181 apply TotalMap.update_shadow
21822182
23212321 obtain ⟨st', h⟩ := hc
23222322 apply ha at h; exists st'
23232323
2324--- Source revision: 2ca0e09, committed 2026-10-23 15:44 UTC
2324+-- Source revision: a06e066, committed 2026-10-27 16:51 UTC
HL/Hoare.lean
13171317 exists aexp { X + 1 }
13181318 intro hc
13191319 rw [validHoareTriple_def] at hc
1320- have h := hc (st := ∅) (st' := {X ↦ 1}) (EvalR.asgn rfl) True.intro
1320+ have h := hc (st := ∅) (st' := {X ↦ 1}) (EvalR.asgn (by rfl)) True.intro
13211321 simp at h
13221322
13231323 -- If `a` itself mentions `X`, then the value of `a` may be different in
13661366 subst h hx
13671367 rw [TotalMap.update_eq, TotalMap.update_shadow,
13681368 TotalMap.update_same]
1369- exact ⟨hp, rfl⟩
1369+ constructor
1370+ · exact hp
1371+ · rfl
13701372
13711373 -- ### Exercise (2 stars): hoare_asgn_fwd_exists (Advanced, Optional) ⭐⭐
13721374
13931395 exists st[X]
13941396 rw [TotalMap.update_eq, TotalMap.update_shadow,
13951397 TotalMap.update_same]
1396- exact ⟨hpre, rfl⟩
1398+ constructor
1399+ · exact hpre
1400+ · rfl
13971401
13981402 -- ### Consequence
13991403
18541858 specialize h (aexp { X }) 2 (st := {X ↦ 2})
18551859 (st' := {Y ↦ 3, X ↦ 3, X ↦ 2}) ?_
18561860 · apply EvalR.seq
1857- · exact EvalR.asgn rfl
1858- · exact EvalR.asgn rfl
1859- simp +decide at h
1861+ · apply EvalR.asgn (by rfl)
1862+ · apply EvalR.asgn (by rfl)
1863+ assertion_auto
18601864
18611865 -- ### Conditionals
18621866
19471951 · exact hoare_asgn
19481952 · assertion_auto
19491953
1950--- We can even shorten it a little bit more. Wherever Lean expects a term
1951--- of some type, we may write `(by <tactics>)` in its place: the tactics
1952--- run immediately, and the proof they produce is spliced in as that term.
1953--- Here we use it to supply `hoare_consequence_pre`'s second argument, the
1954--- implication `P ↠ P'`, directly at the call site, instead of `apply`-ing
1954+-- We can even shorten it a little bit more. Recall that wherever Lean
1955+-- expects a term of some type, we may write `(by <tactics>)` in its
1956+-- place: the tactics run immediately, and the proof they produce is
1957+-- spliced in as that term. Here we use it to supply
1958+-- `hoare_consequence_pre`'s second argument, the implication `P ↠ P'`,
1959+-- directly at the call site, instead of `apply`-ing
19551960 -- `hoare_consequence_pre` and discharging that goal afterward with a
19561961 -- separate bullet.
19571962
23082313 | whileTrue hb hc hloop ih₁ ih₂ =>
23092314 injection heq with hbeq hceq
23102315 subst hbeq hceq
2311- exact ih₂ (hhoare hc ⟨hpre, hb⟩) rfl
2316+ apply ih₂ (hhoare hc ⟨hpre, hb⟩) (by rfl)
23122317 | skip | asgn | seq | ifTrue | ifFalse =>
23132318 contradiction
23142319
26942699 ∅ =[ ex1Repeat ]=> {Y ↦ 1, X ↦ 1} := by
26952700 apply Com.EvalR.repeatEnd
26962701 · apply Com.EvalR.seq
2697- · exact Com.EvalR.asgn rfl
2698- · exact Com.EvalR.asgn rfl
2702+ · apply Com.EvalR.asgn (by rfl)
2703+ · apply Com.EvalR.asgn (by rfl)
26992704 · rfl
27002705
27012706 -- Now state and prove a theorem, `hoare_repeat`, that expresses an
27172722 | repeatLoop hc hb hloop ih₁ ih₂ =>
27182723 injection heq with hceq hbeq
27192724 subst hceq hbeq
2720- apply ih₂ h₂ _ rfl
2725+ apply ih₂ h₂ _ (by rfl)
27212726 constructor
27222727 · exact h₁ hc hpre
27232728 · simp [hb]
28172822 | repeatLoop hc hb hloop ih₁ ih₂ =>
28182823 injection heq with hceq hbeq
28192824 subst hceq hbeq
2820- exact ih₂ (h hc hpre) rfl
2825+ apply ih₂ (h hc hpre)
2826+ rfl
28212827 | skip | asgn | seq | ifTrue | ifFalse | whileFalse | whileTrue =>
28222828 contradiction
28232829
32963302 · intro hC
32973303 rw [validHoareTriple_def] at hC
32983304 have h : ∅ =[ assert (false) ]=> Result.error :=
3299- Com.EvalR.assertFalse rfl
3305+ Com.EvalR.assertFalse (by rfl)
33003306 obtain ⟨st', h₁, h₂⟩ := hC h True.intro
33013307 contradiction
33023308
33173323 obtain ⟨st', h₁, h₂⟩ := hhoare h hpre
33183324 injection h₁ with hsteq
33193325 subst hsteq
3320- exact ⟨rfl, h₂⟩
3326+ constructor
3327+ · rfl
3328+ · exact h₂
33213329
33223330 -- Next, here are proofs for the old Hoare rules adapted to the new
33233331 -- semantics. You don't need to do anything with these.
33313339 | asgn n h =>
33323340 exists (x →ₜ n ; st)
33333341 subst h
3334- exact ⟨rfl, hQ⟩
3342+ exact ⟨by rfl, hQ⟩
33353343
33363344 theorem hoare_consequence_pre {P P' Q : Assertion} {c : Com}
33373345 (hhoare : {{ P' }} c {{ Q }}) (himp : P ↠ P') :
33753383 rw [validHoareTriple_def]
33763384 intro st r h hpre
33773385 inversion h
3378- exact ⟨st, rfl, hpre⟩
3386+ exists st
33793387
33803388 theorem hoare_if {P Q : Assertion} {b : Bexp} {c₁ c₂ : Com}
33813389 (htrue : {{ P ∧ b}} c₁ {{ Q }})
34013409 intro st r heval hpre
34023410 generalize heq : (imp { while (b) { c } }) = cmd at heval
34033411 induction heval generalizing P with
3404- | whileFalse hb =>
3412+ | @whileFalse _ st _ hb =>
34053413 injection heq with hbeq hceq
34063414 subst hbeq hceq
3407- exact ⟨_, rfl, hpre, by simp [hb]⟩
3415+ exists st
3416+ simp_all
34083417 | whileTrueNormal hb hc hloop ih₁ ih₂ =>
34093418 injection heq with hbeq hceq
34103419 subst hbeq hceq
3411- apply ih₂ hhoare _ rfl
3420+ apply ih₂ hhoare _ (by rfl)
34123421 obtain ⟨s₁, heq₁, hs₁⟩ := hhoare hc ⟨hpre, hb⟩
34133422 injection heq₁ with he
34143423 subst he
34383447 obtain ⟨hst, hb⟩ := hpre
34393448 exists st
34403449 inversion heval with
3441- | assertTrue hb' => exact ⟨rfl, hst⟩
3450+ | assertTrue hb' =>
3451+ exact ⟨by rfl, hst⟩
34423452 | assertFalse hb' => simp [hb'] at hb
34433453
34443454 /- Stating this in a backwards-direction friendly way. -/
34483458 intro st r heval hpre
34493459 exists st
34503460 inversion heval with
3451- | assume hb => exact ⟨rfl, hpre hb⟩
3461+ | assume hb =>
3462+ exact ⟨by rfl, hpre hb⟩
34523463
34533464 -- Use your rules to prove the following triple.
34543465
34683479
34693480 end HoareAssertAssume
34703481
3471--- Source revision: 2ca0e09, committed 2026-10-23 15:44 UTC
3482+-- Source revision: a06e066, committed 2026-10-27 16:51 UTC
HL/Hoare2.lean
33663366
33673367 end HimpHoare2
33683368
3369--- Source revision: 2ca0e09, committed 2026-10-23 15:44 UTC
3369+-- Source revision: a06e066, committed 2026-10-27 16:51 UTC
HL/Imp.lean
908908 ]=> {Z ↦ 4, X ↦ 2} := by
909909 -- To supply the intermediate state to the `seq` rule, which is
910910 -- sometimes necessary, we can write `EvalR.seq (st' := ...)`.
911+ -- We can also write `EvalR.asgn (by rfl)` to immediately close
912+ -- the subgoal generated by the lookup.
911913 apply EvalR.seq (st' := {X ↦ 2})
912- · exact EvalR.asgn rfl
914+ · apply EvalR.asgn (by rfl)
913915 · apply EvalR.ifFalse
914916 · rfl
915- · exact EvalR.asgn rfl
917+ · apply EvalR.asgn (by rfl)
916918
917919 -- Note to developers (Niklas Halonen @xhalo32):
918920 -- After `apply EvalR.seq (st' := {X ↦ 2})`, the infoview shows
923925 -- Since the total-map update notation (`→ₜ`) is difficult to type, we
924926 -- prefer to use the `{}`-notation with `KVPair`s.
925927 --
926--- In the above proof, using `EvalR.asgn rfl` is convenient because it
927--- computes the value of the right-hand side and can use it to determine
928--- `st'`.
929---
928+-- In the above proof, proving the premise of `EvalR.asgn` with `rfl` is
929+-- convenient because it computes the value of the right-hand side and can
930+-- use it to determine `st'`.
931+
930932 -- Here are some more examples. Note the use of `~` in the first, since
931933 -- `.num x` is a Lean term that we want to splice into Imp.
932934
936938 -- `simp` or `rfl`
937939 simp
938940
941+-- We can abbreviate this further using `apply EvalR.asgn (by rfl)`, which
942+-- automatically closes the `=` subproof with `rfl`.
943+
939944 example {x : Nat} : ∅ =[ X := ~(.num x) ]=> {X ↦ x} := by
940- exact EvalR.asgn rfl
945+ apply EvalR.asgn (by rfl)
941946
942947 example : ∅ =[ X := 2; Y := 3 ]=> {Y ↦ 3, X ↦ 2} := by
943948 apply EvalR.seq
944949 · -- `⊢ imp {X := 2}.EvalR ∅ ?st'`
945950 -- assigns the metavariable `?st'` to `{X ↦ 2}` (or equivalent)
946- exact EvalR.asgn rfl
951+ apply EvalR.asgn (by rfl)
947952 · simp only [Aexp.eval_num, evalR_eq]
948- exact EvalR.asgn rfl
953+ apply EvalR.asgn (by rfl)
949954
950955 -- This is a case where `rfl` is more powerful than `simp`, because it can
951956 -- assign the `?st'` metavariable. To demonstrate, here's a version with
977982 Z := 2
978983 ]=> {Z ↦ 2, Y ↦ 1, X ↦ 0} := by
979984 apply EvalR.seq (st' := {X ↦ 0})
980- · apply EvalR.asgn rfl
985+ · apply EvalR.asgn (by rfl)
981986 · -- Note: st' is not necessary
982987 apply EvalR.seq (st' := {Y ↦ 1, X ↦ 0})
983- · exact EvalR.asgn rfl
984- · exact EvalR.asgn rfl
988+ · apply EvalR.asgn (by rfl)
989+ · apply EvalR.asgn (by rfl)
985990
986991 -- (End of exercise)
987992
12111216 | whileFalse hb =>
12121217 injection heq with e₁ _
12131218 subst e₁; simp at hb
1214- exact key loop st st' contra rfl
1219+ apply key loop st st' contra (by rfl)
12151220
12161221 -- ### Exercise (3 stars): no_whiles_eqv ⭐⭐⭐
12171222
13811386 have hz : st[Z] ≠ 0 := by
13821387 intro hz
13831388 simp [hz] at hb
1384- exact ih₂ (factBody_preserves_invariant hinv hz hc) rfl
1389+ apply ih₂ (factBody_preserves_invariant hinv hz hc)
1390+ rfl
13851391 | skip | asgn | seq | ifTrue | ifFalse => simp [factLoop] at heq
13861392
13871393 -- Next, we show that, for any loop, if the loop terminates, then the
14741480 have hx : st[X] ≠ 0 := by
14751481 intro hx
14761482 simp [hx] at hb
1477- exact ih₂ (ss_body_preserves_invariant hinv hx hc) rfl
1483+ apply ih₂ (ss_body_preserves_invariant hinv hx hc)
1484+ rfl
14781485 | skip | asgn | seq | ifTrue | ifFalse => simp [subtract_slowly] at heq
14791486
14801487 theorem ss_correct {st st' : State} {n z : Nat}
20402047 -- Notation for `for` loops, but feel free to play with this too if you
20412048 -- like.)
20422049
2043--- Source revision: 2ca0e09, committed 2026-10-23 15:44 UTC
2050+-- Source revision: a06e066, committed 2026-10-27 16:51 UTC
HL/Preface.lean
166166 -- Note to developers (Benjamin Pierce @bcpierce00):
167167 -- Other funding should be acknowledged here...
168168
169--- Source revision: 2ca0e09, committed 2026-10-23 15:44 UTC
169+-- Source revision: a06e066, committed 2026-10-27 16:51 UTC
HL/Slang.lean
721721 -- switch between points of view at will — exactly what we did above in
722722 -- `Slang.Aexp.evalR_iff_eval` and `Slang.Bexp.evalR_iff_eval`.
723723
724--- Source revision: 2ca0e09, committed 2026-10-23 15:44 UTC
724+-- Source revision: a06e066, committed 2026-10-27 16:51 UTC
HL.lean
55 import HL.Hoare
66 import HL.Hoare2
77
8--- Source revision: 2ca0e09, committed 2026-10-23 15:44 UTC
8+-- Source revision: a06e066, committed 2026-10-27 16:51 UTC
LF/Typeclasses.lean
16131613
16141614 end Reflection
16151615
1616--- Source revision: 2ca0e09, committed 2026-10-23 15:44 UTC
1616+-- Source revision: a06e066, committed 2026-10-27 16:51 UTC
SFLCompat/Experiment.lean
146146 Example:
147147 ```lean
148148 sf_expect_failure_in
149- example : 1 = 2 := rfl
149+ example : 1 = 2 := by rfl
150150 ```
151151 -/
152152 def expectFailureTk := leading_parser
SFLCompat/Recall/Check.lean
460460
461461 def twice (f : Nat → Nat) (n : Nat) : Nat := f (f n)
462462
463-theorem twice_id : twice id 3 = 3 := rfl
463+theorem twice_id : twice id 3 = 3 := by rfl
464464
465465 sf_recall
466466 inductive Palette where
490490
491491 -- The statement form counts universe parameters: a placeholder universe
492492 -- becomes a parameter and matches, and a fixed universe is rejected.
493-theorem poly_refl.{u} : ∀ {α : Sort u} (a : α), a = a := fun _ => rfl
493+theorem poly_refl.{u} : ∀ {α : Sort u} (a : α), a = a := fun _ => by rfl
494494
495495 sf_recall statement poly_refl : ∀ {α : Sort _} (a : α), a = a
496496
SFLCompat/Recall/Source.lean
6363
6464 def twice (f : Nat → Nat) (n : Nat) : Nat := f (f n)
6565
66-theorem twice_id : twice id 3 = 3 := rfl
66+theorem twice_id : twice id 3 = 3 := by rfl
6767
6868 sf_recall_source
6969 inductive Palette where