HL Teacher (solutions) source diff

Switch volume / audience

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