TS Terse source diff

Switch volume / audience

LF/Typeclasses.lean

17231723 
17241724 end Reflection
17251725 
1726--- Source revision: 2ca0e09, committed 2026-10-23 15:44 UTC
1726+-- 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

TS/AttributeDecls.lean

2020 -- MoreStlc.lean
2121 register_label_attr ExtStlcEval
2222 register_label_attr ExtStlcTyping
23+
24+-- References.lean
25+register_label_attr StlcRefEval
26+register_label_attr StlcRefTyping

TS/MoreStlc.lean

11731173 
11741174 end StlcExtended
11751175 
1176--- Source revision: 2ca0e09, committed 2026-10-23 15:44 UTC
1176+-- Source revision: a06e066, committed 2026-10-27 16:51 UTC

TS/Preface.lean

22 
33 --  # Preface
44 
5---  This volume is a work in progress. It will develop a
6---  Lean formalization of type systems, covering the simply
7---  typed lambda calculus, progress and preservation
8---  theorems, and extensions such as subtyping and
9---  polymorphism. Please check back later!
5+--  ## Welcome
106 
11---  ## Recommended Citation Format
7+--  This is Type Systems, volume 3 of *Software Foundations
8+--  in Lean*. It develops *type systems*: static checks for
9+--  establishing that *all* programs in a given language are
10+--  well behaved, in contrast to Hoare Logic, which develops
11+--  techniques for reasoning about the behavior of a
12+--  *specific* program. The two volumes can be read in
13+--  either order, and both build on the material in Logical
14+--  Foundations.
15+
16+--  ## Overview
17+
18+--  To reason about a program, we represent it as a
19+--  mathematical object together with a mathematical
20+--  function or relation for describing its behavior. Our
21+--  main approach to doing so is called *operational
22+--  semantics*, and it amounts to defining a kind of
23+--  *abstract interpreter* for the programs in a language.
24+--  We present two styles of operational semantics: the
25+--  *big-step* style specifies a program's behavior by
26+--  relating it directly to its final value, while the
27+--  *small-step* style specifies a program's behavior as a
28+--  series of computational steps. The small-step approach
29+--  is more involved, but also makes it possible to reason
30+--  about a program's evaluation in a more fine-grained
31+--  manner.
32+--
33+--  After introducing operational semantics using a simple
34+--  language of arithmetic and boolean expressions (Slang),
35+--  we turn to *types*, the volume's central subject. A type
36+--  is a static classification of what a program computes,
37+--  and a *type system* is a static reasoning system that
38+--  uses types to rule out whole categories of run-time
39+--  errors before a program is ever run. Working with a
40+--  small language of numbers and booleans, we define a type
41+--  system for it and prove the two signature theorems of
42+--  type-system metatheory — *progress* (a well-typed term
43+--  is either a value or can take a step) and *preservation*
44+--  (taking a step preserves well-typedness) — which
45+--  together guarantee that a well-typed program can never
46+--  "go wrong."
47+--
48+--  Finally, we turn our attention to the *simply typed
49+--  lambda-calculus* (STLC), a much richer language with a
50+--  more interesting type system. We start from a small
51+--  untyped core and extend it with numbers, pairs, sums,
52+--  lists, and general recursion, proving progress and
53+--  preservation anew for the extended language. We then
54+--  study *subtyping*, a mechanism that lets a term of one
55+--  type stand in for a term of another — motivated by the
56+--  way record types behave in object-oriented languages —
57+--  and prove progress and preservation once more for a
58+--  language with subtyping. In so doing, we work our way up
59+--  to a fairly full featured programming language.
60+
61+--  ## Practicalities
62+
63+--  This volume assumes you already have Lean and VS Code
64+--  set up as described in the Logical Foundations Preface,
65+--  and that you are comfortable with the basic mechanics of
66+--  working through an SFL chapter. The exercises here have
67+--  the same "advanced"/"optional" markings, and star
68+--  ratings.
69+--
70+--  Briefly (see the Logical Foundations Preface for
71+--  detail), to get started:
72+--
73+--  If you are using this book as part of a class, your
74+--  instructor will have created a "student" release for
75+--  you; download and unzip it, open the resulting directory
76+--  in VS Code, and open a `.lean` file (e.g.,
77+--  `TS/Slang.lean`) to get started.
78+--
79+--  If you are reading on your own, clone the
80+--  [SF-in-Lean](https://github.com/plclub/sf-in-lean)
81+--  repository and run `make
82+--  ts-student` from the root
83+--  directory to build the student version of this volume;
84+--  it is written to `_out/ts/student/`, with an `html/`
85+--  directory and a `lean/` directory, exactly as described
86+--  for Logical Foundations. Run `make
87+--  student` instead if
88+--  you want all three volumes built together.
89+
90+--  ### Building on Your Own Copy of Logical Foundations
91+
92+--  This project includes a copy of the Logical Foundations
93+--  files that chapters in this volume depend on, in their
94+--  own `LF/` directory, so you do not need a separate
95+--  Logical Foundations download to build or read this
96+--  volume. If you have already worked through Logical
97+--  Foundations and would rather this volume build on your
98+--  own work, copy the whole `LF/` directory from your
99+--  Logical Foundations download over this project's `LF/`
100+--  directory, then rebuild.
101+--
102+--  Exercises in this volume use the same star ratings, and
103+--  the same "advanced"/"optional" markings, described in
104+--  the Logical Foundations Preface.
105+
106+--  ### Citation Format
12107 
13108 --  If you want to refer to this volume in your own writing,
14109 --  please do so as follows:
22117 --  publisher    =   "Electronic textbook",
23118 --  note         =   {Version 0.1.0, \URL<https://github.com/plclub/sf-in-lean>}
24119 --  }
120+
121+--  ## For Potential Contributors
122+
123+--  If you find things you'd like to help add or improve,
124+--  your contributions are welcome! To get started, clone
125+--  the [SF-in-Lean git
126+--  repo](https://github.com/plclub/sf-in-lean) and have a
127+--  look at `ALPHA-TESTERS.md`.
25128 
26129 --  ### Credits
27130 
81184 --  National Science Foundation under the NSF Expeditions
82185 --  grant 1521523, *The Science of Deep Specification*.
83186 
84--- Source revision: 2ca0e09, committed 2026-10-23 15:44 UTC
187+-- Source revision: a06e066, committed 2026-10-27 16:51 UTC

TS/References.lean

1+import TS.Stlc
2+import TS.Smallstep
3+import LF.CustomTactics
4+
5+import SFLCompat
6+
7+--  # References: Typing Mutable References
8+
9+--  Most real languages include *impure* features
10+--  ("computational effects")...
11+--  - mutable pointer structures
12+--  - non-local control constructs (exceptions,
13+--    continuations, etc.)
14+--  - inter-process synchronization and communication
15+--  - etc.
16+--
17+--  Goal for this chapter: Formalize pointers.
18+
19+--  ## Definitions
20+
21+--  In most real-world programming languages, the mechanisms
22+--  of *name binding* and *storage allocation* are
23+--  (intentionally) confused: every name refers to a mutable
24+--  piece of storage.
25+--
26+--  Conceptually, it's cleaner to separate the two:
27+--  - use the mechanisms we already have for name binding
28+--    (abstraction, let);
29+--  - introduce new operations for allocating, changing, and
30+--    looking up the contents of references (pointers).
31+
32+--  ### Syntax
33+
34+namespace STLCRef
35+
36+open scoped MyGetElem
37+
38+--  The basic operations on references are *allocation*,
39+--  *dereferencing*, and *assignment*.
40+--  - To allocate a reference, we use the `ref` operator,
41+--    providing an initial value for the new cell.
42+--
43+--    For example, `ref 5` creates a new cell containing the
44+--    value `5` and reduces to a reference to that cell.
45+--
46+--  - To read the current value of this cell, we use the
47+--    dereferencing operator `!`.
48+--
49+--    For example, `!(ref 5)` reduces to `5`.
50+--
51+--  - To change the value stored in a cell, we use the
52+--    assignment operator.
53+--
54+--    If `r` is a reference, `r := 7` will store the value
55+--    `7` in the cell referenced by `r`.
56+
57+--  ### Types
58+
59+--  If `τ` is a type, then `Ref τ` is the type of references
60+--  to cells holding values of type `τ`.
61+
62+--  τ ::= Nat
63+--      | Unit
64+--      | τ → τ
65+--      | Ref τ
66+
67+inductive Ty : Type :=
68+  | nat : Ty
69+  | unit : Ty
70+  | arrow : Ty → Ty → Ty
71+  | ref : Ty → Ty
72+
73+--  ### Terms
74+
75+--  Besides the usual variables, abstractions, applications,
76+--  terms related to natural numbers, and `unit`, we need
77+--  four more sorts of terms to handle mutable references:
78+
79+--  t ::= ref t     (reference)
80+--      | ! t       (dereference)
81+--      | t := t    (assignment)
82+--      | l         (location)
83+
84+inductive Tm  : Type :=
85+  -- STLC with numbers:
86+  | var    : String → Tm
87+  | app    : Tm → Tm → Tm
88+  | abs    : String → Ty → Tm → Tm
89+  | const  : Nat → Tm
90+  | succ    : Tm → Tm
91+  | pred    : Tm → Tm
92+  | mult    : Tm → Tm → Tm
93+  | ite0  : Tm → Tm → Tm → Tm
94+  -- New terms:
95+  | unit   : Tm
96+  | ref    : Tm → Tm
97+  | deref  : Tm → Tm
98+  | assign : Tm → Tm → Tm
99+  | loc    : Nat → Tm
100+
101+--  THE FOLLOWING DETAILS CAN BE SKIPPED (Notation)
102+scoped syntax:max num : stlcTm
103+scoped syntax:60 stlcTm:60 " * " stlcTm:61 : stlcTm
104+scoped syntax:50 "if0 " stlcTm:51 " then " stlcTm:50 " else " stlcTm:50 : stlcTm
105+
106+scoped syntax:60 stlcTm:60 " := " stlcTm:61 : stlcTm
107+scoped syntax:60 "Ref " stlcTy:61 : stlcTy
108+scoped syntax:60 "ref " stlcTm:61 : stlcTm
109+scoped syntax:60 "loc " stlcTm:61 : stlcTm
110+scoped syntax:60 "!" stlcTm:61 : stlcTm
111+scoped syntax:55 stlcTm:56 " ; " stlcTm:55 : stlcTm
112+
113+scoped syntax stlcCtx " / " term:max " ⊢ " stlcTm " ⦂ " stlcTy : stlcQuoted
114+
115+abbrev Tm.tseq t₁ t₂ :=
116+  Tm.app (.abs "X" .unit t₂) t₁
117+
118+namespace Elab
119+
120+open StlcCommon
121+open Lean Meta Elab Term
122+
123+def language : Language where
124+  tyType := ``Ty
125+  tmType := ``Tm
126+  arrowCtor := ``Ty.arrow
127+  varCtor := ``Tm.var
128+  appCtor := ``Tm.app
129+  absCtor := ``Tm.abs
130+  -- defined later
131+  subst := `STLCRef.subst
132+  hasType := `STLCRef.HasType
133+
134+def extendedTyHandler : TyElabHandler :=
135+  fun recur k T => do
136+    match T with
137+    | `(stlcTy| Nat) =>
138+        return mkConst ``Ty.nat
139+    | `(stlcTy| Unit) =>
140+        return mkConst ``Ty.unit
141+    | `(stlcTy| Ref $τ:stlcTy) => do
142+        let τ ← recur τ
143+        return mkApp (mkConst ``Ty.ref) τ
144+    | _ => k T
145+
146+def tyHandlers : TyElabHandler :=
147+  extendedTyHandler.orElse (commonTyHandler language)
148+
149+partial def elabTy : TyElab :=
150+  tyHandlers elabTy <| unsupportedTy language
151+
152+def extendedTmHandler : TmElabHandler :=
153+  fun recur k Γ free t => do
154+    match t with
155+    | `(stlcTm| $n:num) => do
156+        return (mkApp (mkConst ``Tm.const) (mkNatLit n.getNat), free )
157+
158+    | `(stlcTm| Nat) => do
159+        throwError "`Nat` is not a valid term."
160+
161+    | `(stlcTm| succ $t:stlcTm) => do
162+        let (t, free) ← recur Γ free t
163+        return (mkApp (mkConst ``Tm.succ) t, free)
164+
165+    | `(stlcTm| pred $t:stlcTm) => do
166+        let (t, free) ← recur Γ free t
167+        return (mkApp (mkConst ``Tm.pred) t, free)
168+
169+    | `(stlcTm| $t₁:stlcTm * $t₂:stlcTm) => do
170+        let (t₁, free) ← recur Γ free t₁
171+        let (t₂, free) ← recur Γ free t₂
172+        return (mkApp2 (mkConst ``Tm.mult) t₁ t₂, free)
173+
174+    | `(stlcTm| if0 $c:stlcTm then $t:stlcTm else $e:stlcTm) => do
175+        let (c, free) ← recur Γ free c
176+        let (t, free) ← recur Γ free t
177+        let (e, free) ← recur Γ free e
178+        return (mkApp3 (mkConst ``Tm.ite0) c t e, free)
179+
180+    | `(stlcTm| Unit) => do
181+        throwError "`Unit` is not a valid term."
182+
183+    | `(stlcTm| unit) => do
184+        return (mkConst ``Tm.unit, free)
185+
186+    | `(stlcTm| ref $t:stlcTm) => do
187+        let (t, free) ← recur Γ free t
188+        return (mkApp (mkConst ``Tm.ref) t, free)
189+
190+    | `(stlcTm| !$t:stlcTm) => do
191+        let (t, free) ← recur Γ free t
192+        return (mkApp (mkConst ``Tm.deref) t, free)
193+
194+    | `(stlcTm| loc $n:num) => do
195+        return (mkApp (mkConst ``Tm.loc) (mkNatLit n.getNat), free )
196+
197+    | `(stlcTm| $t₁:stlcTm := $t₂:stlcTm) => do
198+        let (t₁, free) ← recur Γ free t₁
199+        let (t₂, free) ← recur Γ free t₂
200+        return (mkApp2 (mkConst ``Tm.assign) t₁ t₂, free)
201+
202+    | `(stlcTm| $t₁:stlcTm ; $t₂:stlcTm) => do
203+        let (t₁, free) ← recur Γ free t₁
204+        let (t₂, free) ← recur Γ free t₂
205+        return (mkApp2 (mkConst ``Tm.tseq) t₁ t₂, free)
206+
207+    | _ => k Γ free t
208+
209+def tmHandlers : TmElabHandler :=
210+  extendedTmHandler.orElse (commonTmHandler language elabTy)
211+
212+partial def elabTm : TmElab :=
213+  tmHandlers elabTm unsupportedTm
214+
215+def elabCtx : CtxElab := elabCtxCommon language elabTy
216+
217+-- `HasType` takes the store typing as an extra first argument,
218+-- so we build typing judgments here instead of in `elabQuoted`.
219+def mkHasType (δ Γ t T : Expr) : TermElabM Expr := do
220+  let some hasType ← resolveId? (mkIdent language.hasType)
221+    | throwError "unknown declaration `{language.hasType}`"
222+  return mkApp4 hasType δ Γ t T
223+
224+@[scoped term_elab StlcCommon.bracket]
225+def elabBracket : TermElab :=
226+  fun stx expectedType? => do
227+    match stx with
228+    | `(<{ $Γ:stlcCtx / $δ:term ⊢ $t:stlcTm ⦂ $T:stlcTy }>) => do
229+        let (Γ, scope) ← elabCtx Γ
230+        let (t, _) ← elabTm scope [] t
231+        let T ← elabTy T
232+        let δ ← elabTermEnsuringType δ (mkApp (mkConst ``List [levelZero]) (mkConst ``Ty))
233+        mkHasType δ Γ t T
234+    | `(<{ $_:stlcCtx ⊢ $_:stlcTm ⦂ $_:stlcTy }>) =>
235+        throwError "typing judgments need a store typing: write `Γ / δ ⊢ t ⦂ τ`"
236+    | `(<{ $q:stlcQuoted }>) =>
237+        elabQuoted language elabTy elabTm elabCtx q expectedType?
238+    | _ => throwUnsupportedSyntax
239+
240+end Elab
241+
242+open scoped Elab
243+
244+namespace Delab
245+
246+open StlcCommon Elab Delab
247+open Lean PrettyPrinter Delaborator
248+
249+@[app_unexpander Ty.nat]
250+private def Ty.unexpandNat : Unexpander
251+  | stx => do
252+    let Nat := mkObjectIdentFrom stx "Nat"
253+    let T ← `(stlcTy| $Nat:ident)
254+    `(<{ $T:stlcTy }>)
255+
256+@[app_unexpander Ty.unit]
257+private def Ty.unexpandUnit : Unexpander
258+  | stx => do
259+    let Unit := mkObjectIdentFrom stx "Unit"
260+    let T ← `(stlcTy| $Unit:ident)
261+    `(<{ $T:stlcTy }>)
262+
263+@[app_unexpander Ty.arrow]
264+private def Ty.unexpandArrow : Unexpander := Delab.unexpandArrow
265+
266+@[app_unexpander Ty.ref]
267+private def Ty.unexpandRef : Unexpander
268+  | `($_ $T) => do
269+      let T' := getTy T
270+      `(<{ Ref $T':stlcTy }>)
271+  | _ => throw ()
272+
273+private def reservedNames : String → Bool
274+  | "Nat" | "Unit" | "succ" | "pred"
275+  | "if0" | "ref" | "loc" | "Ref"
276+  | "unit" => true
277+  | _ => false
278+
279+@[app_unexpander Tm.var]
280+private def Tm.unexpandVar : Unexpander := Delab.unexpandVar reservedNames ``Tm.var
281+
282+@[app_delab Tm.var]
283+private def Tm.delabVar : Delab := Delab.delabVar ``Tm.var
284+
285+@[app_unexpander Tm.app]
286+private def Tm.unexpandApp : Unexpander := Delab.unexpandApp
287+
288+@[app_unexpander Tm.abs]
289+private def Tm.unexpandAbs : Unexpander := Delab.unexpandAbs
290+
291+@[app_unexpander Tm.const]
292+private def Tm.unexpandConst : Unexpander
293+  | `($_ $n:num) => `(<{ $n:num }>)
294+  | _ => throw ()
295+
296+@[app_unexpander Tm.succ]
297+private def Tm.unexpandSucc : Unexpander
298+  | stx@`($_ $t) => do
299+      let succ := mkObjectIdentFrom stx "succ"
300+      let t' := getTm t
301+      `(<{ $succ:ident $t':stlcTm }>)
302+  | _ => throw ()
303+
304+@[app_unexpander Tm.pred]
305+private def Tm.unexpandPred : Unexpander
306+  | stx@`($_ $t) => do
307+      let pred := mkObjectIdentFrom stx "pred"
308+      let t' := getTm t
309+      `(<{ $pred:ident $t':stlcTm }>)
310+  | _ => throw ()
311+
312+@[app_unexpander Tm.mult]
313+private def Tm.unexpandMult : Unexpander
314+  | `($_ $t₁ $t₂) => do
315+      let t₁' := getTm t₁
316+      let t₂' := getTm t₂
317+      `(<{ $t₁':stlcTm * $t₂':stlcTm }>)
318+  | _ => throw ()
319+
320+@[app_unexpander Tm.tseq]
321+private def Tm.unexpandTseq : Unexpander
322+  | `($_ $t₁ $t₂) => do
323+      let t₁' := getTm t₁
324+      let t₂' := getTm t₂
325+      `(<{ $t₁':stlcTm ; $t₂':stlcTm }>)
326+  | _ => throw ()
327+
328+@[app_unexpander Tm.ite0]
329+private def Tm.unexpandIte0 : Unexpander
330+  | `($_ $c $t $e) => do
331+      let c' := getTm c
332+      let t' := getTm t
333+      let e' := getTm e
334+      `(<{ if0 $c':stlcTm then $t':stlcTm else $e':stlcTm }>)
335+  | _ => throw ()
336+
337+@[app_unexpander Tm.unit]
338+private def Tm.unexpandUnit : Unexpander
339+  | stx => do
340+      let unit := mkObjectIdentFrom stx "unit"
341+      let t ← `(stlcTm| $unit:ident)
342+      `(<{ $t:stlcTm }>)
343+
344+@[app_unexpander Tm.assign]
345+private def Tm.unexpandAssign : Unexpander
346+  | `($_ $t₁ $t₂) => do
347+      let t₁' := getTm t₁
348+      let t₂' := getTm t₂
349+      `(<{ $t₁':stlcTm := $t₂':stlcTm }>)
350+  | _ => throw ()
351+
352+@[app_unexpander Tm.ref]
353+private def Tm.unexpandRef : Unexpander
354+  | `($_ $t₁) => do
355+      let t₁' := getTm t₁
356+      `(<{ ref $t₁':stlcTm }>)
357+  | _ => throw ()
358+
359+@[app_unexpander Tm.deref]
360+private def Tm.unexpandDeref : Unexpander
361+  | `($_ $t₁) => do
362+      let t₁' := getTm t₁
363+      `(<{ !$t₁':stlcTm }>)
364+  | _ => throw ()
365+
366+@[app_unexpander Tm.loc]
367+private def Tm.unexpandLoc : Unexpander
368+  | `($_ $n:num) => `(<{ loc $n:num }>)
369+  | _ => throw ()
370+
371+end Delab
372+--  END DETAILS
373+
374+--  ### Typing (Preview)
375+
376+--  Informally, the typing rules for allocation,
377+--  dereferencing, and assignment look roughly like this:
378+--
379+--            Γ ⊢ t₁ ⦂ τ₁
380+--      ---------------------  (ref)
381+--        Γ ⊢ ref t₁ ⦂ Ref τ₁
382+--
383+--            Γ ⊢ t₁ ⦂ Ref τ₁
384+--      ---------------------  (deref)
385+--           Γ ⊢ !t₁ ⦂ τ₁
386+--
387+--            Γ ⊢ t₁ ⦂ Ref τ₂
388+--            Γ ⊢ t₂ ⦂ τ₂
389+--      ---------------------  (assign)
390+--      Γ ⊢ t₁ := t₂ ⦂ Unit
391+--
392+--  The rule for locations will require a bit more
393+--  machinery, and this will motivate some changes to the
394+--  other rules; we'll come back to this later.
395+
396+--  ### Values and Substitution
397+
398+--  Besides abstractions, numbers, and the unit value, we
399+--  have one new type of value: locations.
400+--
401+--  A location is a concrete pointer value — think of it
402+--  like an address in memory. Locations should never be
403+--  written directly by programmers; they are used to keep
404+--  track of the intermediate states of programs involving
405+--  references. In particular, the result of a `ref`
406+--  expression is a location.
407+
408+inductive Tm.IsValue : Tm → Prop :=
409+  | abs : forall x τ₂ t₁,
410+      IsValue <{λx : τ₂. t₁}>
411+  | nat : forall (n : Nat),
412+      IsValue (.const n)
413+  | unit :
414+      IsValue <{ unit }>
415+  | loc_ : forall (l : Nat),
416+      IsValue (.loc l)
417+
418+attribute [StlcRefEval] Tm.IsValue.abs Tm.IsValue.nat Tm.IsValue.unit Tm.IsValue.loc_
419+
420+--  Extending substitution to handle the new syntax of terms
421+--  is straightforward: substituting into a pointer leaves
422+--  it unchanged.
423+
424+def subst (x : String) (s : Tm) (t : Tm) : Tm :=
425+  match t with
426+  -- pure STLC
427+  | .var y =>
428+      if x = y then s else t
429+  | .abs y τ t₁ =>
430+      if x = y then t else <{ λ y : τ . [x := s] t₁ }>
431+  | .app t₁ t₂ =>
432+      <{ ([x := s] t₁) ([x := s] t₂) }>
433+  -- numbers
434+  | .const _ =>
435+      t
436+  | .succ t₁ =>
437+      <{ succ ([x := s] t₁) }>
438+  | .pred t₁ =>
439+      <{ pred ([x := s] t₁) }>
440+  | .mult t₁ t₂ =>
441+      <{ ([x := s] t₁) * ([x := s] t₂) }>
442+  | .ite0 t₁ t₂ t₃ =>
443+      <{
444+        if0 [x := s] t₁
445+        then [x := s] t₂
446+        else [x := s] t₃
447+      }>
448+  -- unit
449+  | .unit => <{ unit }>
450+  -- references
451+  | .ref t₁ =>  <{ ref ([x := s] t₁) }>
452+  | .deref t₁ =>  <{ !([x := s] t₁) }>
453+  | .loc n => .loc n
454+  | .assign t₁ t₂ =>
455+      <{ ([x := s] t₁) := ([x := s] t₂) }>
456+
457+--  THE FOLLOWING DETAILS CAN BE SKIPPED (Notation encoding)
458+open Lean PrettyPrinter in
459+@[app_unexpander subst]
460+def unexpandSubst : Unexpander := StlcCommon.Delab.unexpandSubst
461+--  END DETAILS
462+
463+--  ## Pragmatics
464+
465+--  ### Side Effects and Sequencing
466+
467+--  We can write (for example)
468+
469+--  R := succ (!R); !R
470+
471+--  as an abbreviation for
472+
473+--  (λX:Unit. !R) (r := succ(!R)).
474+
475+/-- info: <{ R := succ (!R) ; !R }> : Tm -/
476+#guard_msgs in
477+#check <{R := succ (!R); !R}>
478+
479+--  ### References and Aliasing
480+
481+--  It is important to bear in mind the difference between
482+--  the *reference* that is bound to some variable `r` and
483+--  the *cell* in the store that is pointed to by this
484+--  reference.
485+--
486+--  If we make a copy of `r`, for example by binding its
487+--  value to another variable `s`, what gets copied is only
488+--  the reference, not the contents of the cell itself.
489+--
490+--  For example, after reducing
491+--
492+--      let R = ref 5 in
493+--      let S = R in
494+--      S := 82;
495+--      (!R)+1
496+--
497+--  the cell referenced by `R` will contain the value `82`,
498+--  while the result of the whole expression will be `83`.
499+--  The references `R` and `S` are said to be *aliases* for
500+--  the same cell.
501+--
502+--  The possibility of aliasing can make programs with
503+--  references quite tricky to reason about. For example,
504+--  the expression
505+--
506+--      R := 5; R := !S
507+--
508+--  assigns `5` to `R` and then immediately overwrites it
509+--  with `S`'s current value; this has exactly the same
510+--  effect as the single assignment
511+--
512+--      R := !S
513+--
514+--  *unless* we happen to do it in a context where `R` and
515+--  `S` are aliases for the same cell!
516+--
517+--      let R = ref 0 in
518+--      let S = R in
519+--      R := 5; R := !S
520+
521+--  ### Shared State
522+
523+--  Of course, aliasing is also a large part of what makes
524+--  references useful. In particular, it allows us to set up
525+--  "implicit communication channels" — shared state —
526+--  between different parts of a program. For example,
527+--  suppose we define a reference cell and two functions
528+--  that manipulate its contents:
529+--
530+--      let C = ref 0 in
531+--      let Incc = λ_:Unit. (C := succ (!C); !C) in
532+--      let Decc = λ_:Unit. (C := pred (!C); !C) in
533+--        ...
534+--
535+--  The `Unit`-abstractions ("thunks") are used here to
536+--  prevent reduction until later.
537+
538+--  ### Objects
539+
540+--  We can go a step further and write a *function* that
541+--  creates `C`, `Incc`, and `Decc`, packages `Incc` and
542+--  `Decc` together into a record, and returns this record:
543+
544+--  Newcounter =
545+--    λ_:Unit.
546+--        let C = ref 0 in
547+--        let Incc = λ_:Unit. (C := succ (!C); !C) in
548+--        let Decc = λ_:Unit. (C := pred (!C); !C) in
549+--        {i=Incc, d=Decc}
550+
551+--  Now, each time we call `Newcounter`, we get a new record
552+--  of functions that share access to the same storage cell
553+--  `C`. The caller of `Newcounter` can't get at this
554+--  storage cell directly, but can affect it indirectly by
555+--  calling the two functions. In other words, we've created
556+--  a simple form of *object*.
557+
558+--  let C₁ = newcounter unit in
559+--  let C₂ = newcounter unit in
560+--  // we've allocated two separate storage cells now!
561+--  let R₁ = C₁.i unit in
562+--  let R₂ = C₂.i unit in
563+--  R₂  // yields 1, not 2!
564+
565+--  ### References to Compound Types
566+
567+--  A reference cell need not contain just a number: the
568+--  primitives we've defined above allow us to create
569+--  references to values of any type, including functions.
570+--  For example, we can use references to functions to give
571+--  a(n inefficient) implementation of arrays of numbers as
572+--  follows.
573+--
574+--  Write `NatArray` for the type `Ref (Nat→Nat)`.
575+--
576+--  To build a new array, we allocate a reference cell and
577+--  fill it with a function that, when given an index,
578+--  always returns `0`.
579+--
580+--      Newarray = λ_:Unit. ref (λN:Nat.0)
581+--
582+--  To look up an element of an array, we apply the function
583+--  to the desired index.
584+--
585+--      Lookup = λA:NatArray, λN:Nat. (!A) N
586+--
587+--  The interesting part of the encoding is the `Update`
588+--  function. It takes an array, an index, and a new value
589+--  to be stored at that index, and it does its job by
590+--  creating (and storing in the reference) a new function
591+--  that, when it is asked for the value at this very index,
592+--  returns the new value that was given to `Update`, while
593+--  on all other indices it passes the lookup to the
594+--  function that was previously stored in the reference.
595+
596+--  Update = \A:NatArray, \M:Nat, \V:Nat,
597+--    let Oldf = !A in
598+--    A := (λN:Nat. if Equal M N then V else Oldf N);
599+
600+--  References to values containing other references can
601+--  also be very useful, allowing us to define data
602+--  structures such as mutable lists and trees.
603+
604+--  ### Null References
605+
606+--  One more difference between our references and C-style
607+--  mutable variables: *null pointers*.
608+--  - In C, a pointer variable can contain either a valid
609+--    pointer into the heap or the special value `NULL`.
610+--  - A source of many errors and much tricky reasoning:
611+--    - (any pointer may potentially be "not there")
612+--    - but occasionally useful
613+--  - Nullable pointers are easy to implement using
614+--    references plus options (which can be built out of
615+--    disjoint sum types):
616+--
617+--      Option τ       =  Unit + τ
618+--      NullableRef τ  =  Ref (Option τ)
619+
620+--  ### Garbage Collection
621+
622+--  A last issue that we should mention before we move on
623+--  with formalizing references is storage *de*-allocation.
624+--  We have not provided any primitives for freeing
625+--  reference cells when they are no longer needed. Instead,
626+--  like many modern languages (including OCaml, Haskell,
627+--  Java, etc.), we rely on the run-time system to perform
628+--  *garbage collection*, automatically identifying and
629+--  reusing cells that can no longer be reached by the
630+--  program.
631+--
632+--  This is *not* just a question of taste in language
633+--  design: it is extremely difficult to achieve type safety
634+--  in the presence of an explicit deallocation operation.
635+--
636+--  One reason for this is the familiar *dangling reference*
637+--  problem: we allocate a cell holding a number, save a
638+--  reference to it in some data structure, use it for a
639+--  while, then deallocate it and allocate a new cell
640+--  holding a boolean, possibly reusing the same storage.
641+--  Now we can have two names for the same storage cell —
642+--  one with type `Ref Nat` and the other with type
643+--  `Ref Bool`.
644+
645+--  ## Operational Semantics
646+
647+--  ### Locations
648+
649+--  A reference names a location in the *store* (a.k.a.
650+--  heap).
651+--
652+--  What is the store?
653+--  - Concretely: An array of 8-bit bytes, indexed by 32-bit
654+--    integers.
655+--  - More abstractly: a list or array of values
656+--  - Even more abstractly: a partial function from
657+--    locations to values.
658+--
659+--  We'll choose the middle way here: A store is a list of
660+--  values, and a location is a natural-number index into
661+--  this list.
662+
663+--  ### Stores
664+
665+--  A store is just a *list* of values. (This more concrete
666+--  representation will be more convenient for proofs than
667+--  the functional representation we used in Imp.) We will
668+--  use the Greek letter ρ to represent stores.
669+
670+abbrev Store := List Tm
671+
672+--  We use `ρ[n]` to retrieve the value of the reference
673+--  cell at location `n` in the store `ρ`. Note that we must
674+--  give a default value to `nth` in case we try looking up
675+--  an index which is too large. (In fact, we never actually
676+--  do this, but *proving* that we don't will require a bit
677+--  of work.)
678+
679+open scoped MyGetElem
680+instance : MyGetElem Store Nat Tm where
681+  getElem ρ n := ρ.getD n <{unit}>
682+
683+@[simp]
684+theorem Store_get_succ_tl (hd : Tm) (tl : Store) (n : Nat) :
685+  (hd :: tl)[n + 1] = tl[n] := by rfl
686+
687+@[simp]
688+theorem Store_get_zero_hd (hd : Tm) (tl : Store) :
689+  (hd :: tl)[0] = hd := by rfl
690+
691+--  To update the store, we use the `List.set` function,
692+--  which replaces the contents of a cell at a particular
693+--  index.
694+--
695+--      def List.set : (l : List α) → (n : Nat) → (a : α) → List α
696+--        | cons _ as, 0,          b => cons b as
697+--        | cons a as, Nat.succ n, b => cons a (set as n b)
698+--        | nil,       _,          _ => nil
699+--
700+--  As might be expected, we will also need some technical
701+--  lemmas; they are straightforward to prove.
702+
703+theorem Store_get_set_eq (ρ : Store) (l : Nat) (x : Tm)
704+  (h : l < ρ.length) :
705+  (ρ.set l x)[l] = x := by
706+  induction ρ generalizing l with
707+  | nil => simp_all
708+  | cons hd tl ih => cases l <;> simp_all
709+
710+theorem Store_get_set_neq (l₁ l₂ : Nat) (t : Tm) (ρ : Store) :
711+  l₁ ≠ l₂ ->
712+  (ρ.set l₂ t)[l₁] = ρ[l₁] := by
713+  induction ρ generalizing l₁ l₂ with
714+  | nil => simp
715+  | cons hd tl ih => cases l₁ <;> cases l₂ <;> simp_all
716+
717+--  ### Reduction
718+
719+--  First, we augment existing reduction rules with stores:
720+--
721+--                  v₂.IsValue
722+--      ------------------------------------ (appAbs)
723+--      (λx:τ₂. t₁) v₂ / ρ ⟶ [x:=v₂] t₁ / ρ
724+--
725+--                  t₁ / ρ ⟶ t₁' / ρ'
726+--      ---------------------------------    (app₁)
727+--               t₁ t₂ / ρ ⟶ t₁' t₂ / ρ'
728+--
729+--                 v₁.IsValue
730+--                  t₂ / ρ ⟶ t₂' / ρ'
731+--      ---------------------------------    (app₂)
732+--               v₁ t₂ / ρ ⟶ v₁ t₂' / ρ'
733+--
734+--  Now we can give the rules for the new constructs:
735+--
736+--      ------------------------------------    (refValue)
737+--           ref v / ρ ⟶ loc ρ.length / ρ,v
738+--
739+--              t₁ / ρ ⟶ t₁' / ρ'
740+--      ------------------------------          (ref)
741+--          ref t₁ / ρ ⟶ ref t₁' / ρ'
742+--
743+--            l < ρ.length
744+--      --------------------------              (derefLoc)
745+--        !(loc l) / ρ ⟶ ρ[l] / ρ
746+--
747+--              t₁ / ρ ⟶ t₁' / ρ'
748+--      ---------------------------             (deref)
749+--             !t₁ / ρ ⟶ !t₁' / ρ'
750+--
751+--                   l < ρ.length
752+--      --------------------------------------- (assign)
753+--      loc l := v / ρ ⟶ unit / List.set ρ l v
754+--
755+--              t₁ / ρ ⟶ t₁' / ρ'
756+--      --------------------------------        (assign₁)
757+--        t₁ := t₂ / ρ ⟶ t₁' := t₂ / ρ'
758+--
759+--              t₂ / ρ ⟶ t₂' / ρ'
760+--      --------------------------------        (assign₂)
761+--        v₁ := t₂ / ρ ⟶ v₁ := t₂' / ρ'
762+
763+section
764+set_option hygiene false in
765+local notation:40
766+  t:71 " / " ρ:41 " ⟶ " t':71 " / " ρ':41 =>
767+  Step (t, ρ) (t', ρ')
768+
769+inductive Step : Tm × Store → Tm × Store → Prop where
770+  -- pure STLC
771+  | appAbs {x : String} {τ₂ : Ty} {t₁ v₂ : Tm} {ρ : Store}
772+      (h : v₂.IsValue) :
773+      <{(λ x : τ₂ . t₁) v₂}> / ρ ⟶
774+      <{ [x := v₂] t₁ }> / ρ
775+  | app₁ {t₁ t₁' t₂ : Tm} {ρ ρ' : Store}
776+      (h : t₁ / ρ ⟶ t₁' / ρ') :
777+      <{t₁ t₂}> / ρ ⟶ <{t₁' t₂}> / ρ'
778+  | app₂ {v₁ t₂ t₂' : Tm} {ρ ρ' : Store}
779+      (h₁ : v₁.IsValue)
780+      (h₂ : t₂ / ρ ⟶ t₂' / ρ') :
781+      <{v₁ t₂}> / ρ ⟶ <{v₁ t₂'}> / ρ'
782+  -- numbers
783+  | succNat {n : Nat} {ρ : Store} :
784+      <{ succ ~(Tm.const n) }> / ρ ⟶ Tm.const (n + 1) / ρ
785+  | succ {t₁ t₁' : Tm} {ρ ρ' : Store}
786+      (h : t₁ / ρ ⟶ t₁' / ρ') :
787+      <{ succ t₁ }> / ρ ⟶ <{ succ t₁' }> / ρ'
788+  | predConst {n : Nat} {ρ : Store} :
789+      <{ pred ~(Tm.const n) }> / ρ ⟶ Tm.const (n - 1) / ρ
790+  | pred {t₁ t₁' : Tm} {ρ ρ' : Store}
791+      (h : t₁ / ρ ⟶ t₁' / ρ') :
792+      <{ pred t₁ }> / ρ ⟶ <{ pred t₁' }> / ρ'
793+  | multConst {n₁ n₂ : Nat} {ρ : Store} :
794+      <{ ~(Tm.const n₁) * ~(Tm.const n₂) }> / ρ ⟶
795+      Tm.const (n₁ * n₂) / ρ
796+  | mult₁ {t₁ t₁' t₂ : Tm} {ρ ρ' : Store}
797+      (h : t₁ / ρ ⟶ t₁' / ρ') :
798+      <{ t₁ * t₂ }> / ρ ⟶ <{ t₁' * t₂ }> / ρ'
799+  | mult₂ {v₁ t₂ t₂' : Tm} {ρ ρ' : Store}
800+      (h₁ : v₁.IsValue)
801+      (h₂ : t₂ / ρ ⟶ t₂' / ρ') :
802+      <{ v₁ * t₂ }> / ρ ⟶ <{ v₁ * t₂' }> / ρ'
803+  | if0Step {t₁ t₁' t₂ t₃ : Tm} {ρ ρ' : Store}
804+      (h : t₁ / ρ ⟶ t₁' / ρ') :
805+      <{ if0 t₁ then t₂ else t₃ }> / ρ ⟶
806+      <{ if0 t₁' then t₂ else t₃ }> / ρ'
807+  | if0Zero {t₂ t₃ : Tm} {ρ : Store} :
808+      <{ if0 0 then t₂ else t₃ }> / ρ ⟶ t₂ / ρ
809+  | if0Nonzero {n : Nat} {t₂ t₃ : Tm} {ρ : Store} :
810+      <{ if0 ~(Tm.const (n + 1)) then t₂ else t₃ }> / ρ ⟶
811+      t₃ / ρ
812+  -- references
813+  | refValue {v : Tm} {ρ : Store}
814+      (h : v.IsValue) :
815+      <{ ref v }> / ρ ⟶ Tm.loc ρ.length / ρ.concat v
816+  | ref_ {t₁ t₁' : Tm} {ρ ρ' : Store}
817+      (h : t₁ / ρ ⟶ t₁' / ρ') :
818+      <{ ref t₁ }> / ρ ⟶ <{ ref t₁' }> / ρ'
819+  | derefLoc {l : Nat} {ρ : Store}
820+      (h : l < ρ.length) :
821+      <{ !~(Tm.loc l) }> / ρ ⟶ ρ[l] / ρ
822+  | deref {t₁ t₁' : Tm} {ρ ρ' : Store}
823+      (h : t₁ / ρ ⟶ t₁' / ρ') :
824+      <{ !t₁ }> / ρ ⟶ <{ !t₁' }> / ρ'
825+  | assign {v : Tm} {l : Nat} {ρ : Store}
826+      (h₁ : v.IsValue)
827+      (h₂ : l < ρ.length) :
828+      <{ ~(Tm.loc l) := v }> / ρ ⟶ <{ unit }> / ρ.set l v
829+  | assign₁ {t₁ t₁' t₂ : Tm} {ρ ρ' : Store}
830+      (h : t₁ / ρ ⟶ t₁' / ρ') :
831+      <{ t₁ := t₂ }> / ρ ⟶ <{ t₁' := t₂ }> / ρ'
832+  | assign₂ {v₁ t₂ t₂' : Tm} {ρ ρ' : Store}
833+      (h₁ : v₁.IsValue)
834+      (h₂ : t₂ / ρ ⟶ t₂' / ρ') :
835+      <{ v₁ := t₂ }> / ρ ⟶ <{ v₁ := t₂' }> / ρ'
836+end
837+
838+scoped notation:40
839+  t:71 " / " ρ:41 " ⟶ " t':71 " / " ρ':41 =>
840+  Step (t, ρ) (t', ρ')
841+scoped notation:40
842+  t:71 " / " ρ:41 " ⟶* " t':71 " / " ρ':41 =>
843+  Multi Step (t, ρ) (t', ρ')
844+
845+attribute [StlcRefEval] Step.appAbs Step.app₁ Step.app₂
846+    Step.succ Step.succNat Step.pred Step.predConst
847+    Step.multConst Step.mult₁ Step.mult₂
848+    Step.if0Step Step.if0Zero Step.if0Nonzero
849+    Step.refValue Step.ref_ Step.derefLoc Step.deref Step.assign
850+    Step.assign₁ Step.assign₂
851+
852+--  ## Typing
853+
854+--  The contexts assigning types to free variables are
855+--  exactly the same as for the STLC: partial maps from
856+--  identifiers to types.
857+
858+abbrev Context := PartialMap String Ty
859+
860+--  ### Store typings
861+
862+--  Naturally, the key question is, "What is the type of a
863+--  location?"
864+--
865+--  As a first try, observe that the type of a location is
866+--  connected to the contents of the store `ρ`.
867+--
868+--       Γ ⊢ ρ[l] : τ₁
869+--      ------------------
870+--      Γ ⊢ loc l : Ref τ₁
871+--
872+--  But where does `ρ` come from?
873+--
874+--  We could try adding `ρ` to the judgment: `Γ; ρ ⊢ t : τ`,
875+--  which gives us this rule:
876+--
877+--       Γ; ρ ⊢ ρ[l] : τ₁
878+--      ---------------------
879+--      Γ; ρ ⊢ loc l : Ref τ₁
880+--
881+--  But that means the *whole* store `ρ`, including all
882+--  dynamically created values, is needed *during
883+--  typechecking*. This does not seem like something we
884+--  want.
885+--
886+--  Worse yet, it doesn't work at all for *cyclic* stores.
887+--
888+--  For example, what is the type of location `0` in the
889+--  following store?
890+
891+--  λX:Nat. (!(loc 1)) X, λX:Nat. (!(loc 0)) X
892+
893+--  Instead, we establish an *invariant* that the type of
894+--  value stored in a location never changes.
895+--
896+--  This *static* representation of the store contents is
897+--  called a *store typing*:
898+
899+abbrev StoreTy := List Ty
900+
901+--  Here we represent locations as indices into a *list* of
902+--  types so the type at index `i` is the type of the values
903+--  stored in cell `i`.
904+
905+open scoped MyGetElem
906+instance : MyGetElem StoreTy Nat Ty where
907+  getElem δ n := δ.getD n <{Unit}>
908+
909+@[simp]
910+theorem StoreTy_get_succ_tl (hd : Ty) (tl : StoreTy) (n : Nat) :
911+  (hd :: tl)[n + 1] = tl[n] := by rfl
912+@[simp]
913+theorem StoreTy_get_zero_hd (hd : Ty) (tl : StoreTy) :
914+  (hd :: tl)[0] = hd := by rfl
915+
916+--  We can use the store typing `δ` to give a type to any
917+--  location `l` like this:
918+--
919+--           l < δ.length
920+--      -----------------------
921+--      Γ; δ ⊢ loc l : Ref δ[l]
922+--
923+--  That is, as long as `l` is a valid location, we can
924+--  compute the type of `l` just by looking it up in `δ`.
925+--  Typing is again a four-place relation, but it is
926+--  parameterized on a store *typing* rather than a concrete
927+--  store. The rest of the typing rules are analogously
928+--  augmented with store typings.
929+
930+--  ### The Typing Relation
931+
932+--           l < δ.length
933+--      -----------------------  (loc)
934+--      Γ; δ ⊢ loc l : Ref δ[l]
935+--
936+--          Γ; δ ⊢ t₁ : τ₁
937+--      ----------------------   (ref)
938+--      Γ; δ ⊢ ref t₁ : Ref τ₁
939+--
940+--        Γ; δ ⊢ t₁ : Ref τ₁
941+--        ------------------     (deref)
942+--        Γ; δ ⊢ !t₁ : τ₁
943+--
944+--        Γ; δ ⊢ t₁ : Ref τ₂
945+--          Γ; δ ⊢ t₂ : τ₂
946+--      ----------------------   (assign)
947+--      Γ; δ ⊢ t₁ := t₂ : Unit
948+
949+inductive HasType (δ : StoreTy) : Context → Tm → Ty → Prop where
950+  -- pure STLC
951+  | var {Γ : Context} {x : String} {τ₁ : Ty}
952+      (h : Γ[x] = some τ₁) :
953+      <{ Γ / δ ⊢ ~(Tm.var x) ⦂ τ₁ }>
954+  | abs {Γ : Context} {x : String} {τ₁ τ₂ : Ty} {t₁ : Tm}
955+      (h : <{ x ↦ τ₂ ; Γ / δ ⊢ t₁ ⦂ τ₁ }>) :
956+      <{ Γ / δ ⊢ λ x : τ₂ . t₁ ⦂ τ₂ → τ₁ }>
957+  | app {Γ : Context} {τ₁ τ₂ : Ty} {t₁ t₂ : Tm}
958+      (h₁ : <{ Γ / δ ⊢ t₁ ⦂ τ₂ → τ₁ }>)
959+      (h₂ : <{ Γ / δ ⊢ t₂ ⦂ τ₂ }>) :
960+      <{ Γ / δ ⊢ t₁ t₂ ⦂ τ₁ }>
961+  -- numbers
962+  | const {Γ : Context} {n : Nat} :
963+      <{ Γ / δ ⊢ ~(Tm.const n) ⦂ Nat }>
964+  | succ {Γ : Context} {t₁ : Tm}
965+      (h : <{ Γ / δ ⊢ t₁ ⦂ Nat }>) :
966+      <{ Γ / δ ⊢ succ t₁ ⦂ Nat }>
967+  | pred {Γ : Context} {t₁ : Tm}
968+      (h : <{ Γ / δ ⊢ t₁ ⦂ Nat }>) :
969+      <{ Γ / δ ⊢ pred t₁ ⦂ Nat }>
970+  | mult {Γ : Context} {t₁ t₂ : Tm}
971+      (h₁ : <{ Γ / δ ⊢ t₁ ⦂ Nat }>)
972+      (h₂ : <{ Γ / δ ⊢ t₂ ⦂ Nat }>) :
973+      <{ Γ / δ ⊢ t₁ * t₂ ⦂ Nat }>
974+  | ite0 {Γ : Context} {t₁ t₂ t₃ : Tm} {τ : Ty}
975+      (h₁ : <{ Γ / δ ⊢ t₁ ⦂ Nat }>)
976+      (h₂ : <{ Γ / δ ⊢ t₂ ⦂ τ }>)
977+      (h₃ : <{ Γ / δ ⊢ t₃ ⦂ τ }>) :
978+      <{ Γ / δ ⊢ if0 t₁ then t₂ else t₃ ⦂ τ }>
979+  -- unit
980+  | unit {Γ : Context} :
981+      <{ Γ / δ ⊢ unit ⦂ Unit }>
982+  -- references
983+  | loc_ {Γ : Context} {l : Nat}
984+      (h : l < δ.length) :
985+      <{ Γ / δ ⊢ ~(Tm.loc l) ⦂ Ref ~(δ[l]) }>
986+  | ref_ {Γ : Context} {t₁ : Tm} {τ₁ : Ty}
987+      (h : <{ Γ / δ ⊢ t₁ ⦂ τ₁ }>) :
988+      <{ Γ / δ ⊢ ref t₁ ⦂ Ref τ₁ }>
989+  | deref {Γ : Context} {t₁ : Tm} {τ₁ : Ty}
990+      (h : <{ Γ / δ ⊢ t₁ ⦂ Ref τ₁ }>) :
991+      <{ Γ / δ ⊢ !t₁ ⦂ τ₁ }>
992+  | assign {Γ : Context} {t₁ t₂ : Tm} {τ₂ : Ty}
993+      (h₁ : <{ Γ / δ ⊢ t₁ ⦂ Ref τ₂ }>)
994+      (h₂ : <{ Γ / δ ⊢ t₂ ⦂ τ₂ }>) :
995+      <{ Γ / δ ⊢ t₁ := t₂ ⦂ Unit }>
996+
997+attribute [StlcRefTyping] HasType.var HasType.abs HasType.app
998+    HasType.const HasType.succ HasType.pred HasType.mult
999+    HasType.ite0 HasType.unit
1000+    HasType.loc_ HasType.ref_ HasType.deref HasType.assign
1001+
1002+--  THE FOLLOWING DETAILS CAN BE SKIPPED (Notation encoding)
1003+open Lean PrettyPrinter StlcCommon.Delab in
1004+@[app_unexpander HasType]
1005+def HasType.unexpand : Unexpander
1006+  | `($_ $δ $Γ $t $T) => do
1007+      let Γ' ← unexpandCtx Γ
1008+      `(<{ $Γ':stlcCtx / $δ ⊢ $(getTm t):stlcTm ⦂ $(getTy T):stlcTy }>)
1009+  | _ => throw ()
1010+--  END DETAILS
1011+
1012+--  ## Properties
1013+
1014+--  Standard theorems...
1015+--  - Progress — pretty much same as always
1016+--  - Preservation — needs to be stated more carefully!
1017+
1018+--  ### Well-Typed Stores
1019+
1020+--  The evaluation and typing relations take more parameters
1021+--  now, so at a minimum we have to add these to the
1022+--  statement of preservation...
1023+
1024+sf_expect_failure_in
1025+  theorem preservation_wrong (δ : StoreTy) (τ : Ty) (t t' : Tm) (ρ ρ' : Store) :
1026+      <{ ∅ / δ ⊢ t ⦂ τ }> →
1027+      t / ρ ⟶ t' / ρ' →
1028+      <{ ∅ / δ ⊢ t' ⦂ τ }> := by
1029+
1030+--  Obviously wrong: no relation between assumed store
1031+--  typing and provided store!
1032+--
1033+--  We need a way of saying "this store satisfies the
1034+--  assumptions of that store typing"...
1035+
1036+def StoreWellTyped (δ:StoreTy) (ρ:Store) :=
1037+  δ.length = ρ.length ∧
1038+  (∀ (l : Nat), l < ρ.length → <{ ∅ / δ ⊢ ~(ρ[l]) ⦂ ~(δ[l]) }>)
1039+
1040+--  Informally, we will write `δ ⊢ ρ` for
1041+--  `StoreWellTyped δ ρ`.
1042+
1043+scoped notation:40 δ:41 " ⊢ " ρ:41 => StoreWellTyped δ ρ
1044+
1045+--  Intuitively, a store `ρ` is consistent with a store
1046+--  typing `δ` if every value in the store has the type
1047+--  predicted by the store typing. The only subtle point is
1048+--  the fact that, when typing the values in the store, we
1049+--  supply the very same store typing to the typing
1050+--  relation. This allows us to type circular stores like
1051+--  the one we saw above.
1052+--
1053+--  We can now state something closer to the desired
1054+--  preservation property:
1055+
1056+sf_expect_failure_in
1057+  theorem preservation_less_wrong (δ : StoreTy) (τ : Ty) (t t' : Tm) (ρ ρ' : Store) :
1058+    <{ ∅ / δ ⊢ t ⦂ τ }> →
1059+    t / ρ ⟶ t' / ρ' →
1060+    δ ⊢ ρ →
1061+    <{ ∅ / δ ⊢ t' ⦂ τ }> := by
1062+
1063+--  This works... for all but *one* of the reduction rules!
1064+--  (Which?)
1065+--
1066+--  The `refValue` rule is the problem
1067+--
1068+--      -------------------------- (refValue)
1069+--      ref v / ρ ⟶ loc |ρ| / ρ,v
1070+--
1071+--  It allocates a fresh location `l` and adds it to the
1072+--  store, but the store typing `δ` doesn't know about `l`,
1073+--  so `t'` won't be typeable under `δ`.
1074+--
1075+--  For example, the term `ref 5` is typeable in the ∅
1076+--  context and ∅ store typing, but it steps to `loc 0`,
1077+--  which is not typeable with an ∅ store typing.
1078+
1079+--  ### Extending Store Typings
1080+
1081+--  Intuition: Since the store can grow during reduction, we
1082+--  need to let the store *typing* grow too...
1083+
1084+inductive Extends : StoreTy → StoreTy → Prop where
1085+  | nil (δ' : StoreTy) : Extends δ' []
1086+  | cons (τ : Ty) {δ' δ : StoreTy} (h : Extends δ' δ) :
1087+      Extends (τ::δ') (τ::δ)
1088+
1089+attribute [StlcRefTyping] Extends.nil Extends.cons
1090+
1091+--  For example, the store typing `[Nat]` with a single
1092+--  location of type `Nat` extends the empty store typing.
1093+--
1094+--  We'll need a few technical lemmas about extended
1095+--  contexts. First, looking up a type in an extended store
1096+--  typing yields the same result as in the original:
1097+
1098+theorem extends_lookup {l : Nat} {δ δ' : StoreTy}
1099+  (h₁ : l < δ.length)
1100+  (h₂ : Extends δ' δ) :
1101+  δ'[l] = δ[l] := by
1102+
1103+    induction δ generalizing l δ' with
1104+    | nil => simp_all
1105+    | cons hd tl ih =>
1106+      cases δ' with
1107+      | nil => inversion h₂
1108+      | cons hd' tl' =>
1109+        inversion h₂
1110+        cases l with
1111+        | zero => rfl
1112+        | succ l =>
1113+          simp only [StoreTy_get_succ_tl]; apply ih
1114+          · simp_all
1115+          · assumption
1116+
1117+--  Next, if `δ'` extends `δ`, the length of `δ'` is at
1118+--  least that of `δ`.
1119+
1120+theorem length_extends {l : Nat} {δ δ' : StoreTy}
1121+  (h₁ : l < δ.length)
1122+  (h₂ : Extends δ' δ) :
1123+  l < δ'.length := by
1124+    induction h₂ generalizing l with
1125+    | nil => simp_all
1126+    | cons τ h ih =>
1127+        simp only [List.length_cons]
1128+        cases l with
1129+        | zero => lia
1130+        | succ l' =>
1131+          apply Nat.succ_lt_succ; apply ih
1132+          simp_all
1133+
1134+--  Finally, `δ ++ δ'` extends `δ`, and `Extends` is
1135+--  reflexive.
1136+
1137+theorem extends_app (δ δ' : StoreTy) : Extends (δ ++ δ') δ := by
1138+  induction δ generalizing δ' <;> apply_rules using StlcRefTyping
1139+
1140+theorem extends_refl (δ : StoreTy) : Extends δ δ := by
1141+  induction δ <;> apply_rules using StlcRefTyping
1142+
1143+--  ### Preservation, Finally
1144+
1145+--  We can now give the final, correct statement of the type
1146+--  preservation property:
1147+
1148+def preservation_theorem {δ : StoreTy} {t t' : Tm} {τ : Ty} {ρ ρ' : Store} :=
1149+  (hTy : <{ ∅ / δ ⊢ t ⦂ τ }>) →
1150+  (hStoreTy : δ ⊢ ρ) →
1151+  (hEval : t / ρ ⟶ t' / ρ') →
1152+    ∃ δ', Extends δ' δ ∧ (<{ ∅ / δ' ⊢ t' ⦂ τ }>) ∧ (δ' ⊢ ρ')
1153+
1154+--  This gives us just what we need to "turn the crank" when
1155+--  applying the theorem to multi-step reduction sequences.
1156+
1157+--  #### Substitution Lemma
1158+
1159+--  To prove preservation, we need to re-develop the rest of
1160+--  the machinery that we saw for the pure STLC (plus a
1161+--  couple of new things about store typings and
1162+--  extension)...
1163+
1164+theorem weakening {Γ Γ' : Context} {δ : StoreTy} {t : Tm} {τ: Ty}
1165+    (hi : Γ ⊆ Γ')
1166+    (ht : <{ Γ / δ ⊢ t ⦂ τ }>) :
1167+     <{ Γ' / δ ⊢ t ⦂ τ }> := by
1168+  induction ht generalizing Γ' with (apply_rules [PartialMap.update_subset] using StlcRefTyping)
1169+
1170+theorem weakening_empty {Γ : Context} {δ : StoreTy} {t : Tm} {τ: Ty}
1171+    (ht :<{ ∅ / δ ⊢ t ⦂ τ }>) :
1172+    <{ Γ / δ ⊢ t ⦂ τ }> := by
1173+  apply weakening _ ht
1174+  intro _ _ h
1175+  rw [PartialMap.getElem_empty] at h
1176+  contradiction
1177+
1178+theorem substitution_preserves_typing (Γ : Context) (δ : StoreTy) (x : String)
1179+    (τ₁ : Ty) (t v : Tm) (τ : Ty)
1180+    (ht : <{ x ↦ τ₁ ; Γ / δ⊢ t ⦂ τ }>)
1181+    (hv : <{ ∅ / δ ⊢ v ⦂ τ₁ }>) :
1182+    <{ Γ / δ ⊢ [x := v] t ⦂ τ }> := by
1183+  induction t generalizing Γ τ with (
1184+    rw [subst]; try (inversion ht; apply_rules using StlcRefTyping; done))
1185+    | var y =>
1186+        inversion ht with | _ h =>
1187+        by_cases h₁ : x = y
1188+        · subst h₁; simp at h; subst h;
1189+          apply weakening_empty at hv
1190+          simp; assumption
1191+        · rw [PartialMap.update_neq] at h <;> simp_all
1192+          apply_rules using StlcRefTyping
1193+    | abs y _ _ ih =>
1194+        inversion ht with | _ h =>
1195+        by_cases h₁ : x = y
1196+        · simp_all [PartialMap.update_shadow]; apply_rules using StlcRefTyping
1197+        · rw [PartialMap.update_permute] at h
1198+          · simp_all; apply_rules using StlcRefTyping
1199+          · lia
1200+
1201+--  #### Assignment Preserves Store Typing
1202+
1203+--  Next, we must show that replacing the contents of a cell
1204+--  in the store with a new value of appropriate type does
1205+--  not change the overall type of the store. (This is
1206+--  needed for the `assign` rule.)
1207+
1208+theorem assign_pres_store_typing {δ : StoreTy} {ρ : Store} {l : Nat} {t : Tm}
1209+  (hLen : l < ρ.length)
1210+  (hStoreTy : δ ⊢ ρ)
1211+  (hTy : <{ ∅ / δ ⊢ t ⦂ ~(δ[l]) }>) :
1212+  δ ⊢ ρ.set l t := by
1213+    have ⟨h₁, h₂⟩ := hStoreTy
1214+    constructor
1215+    · simp_all [List.length_set]
1216+    · intro l' hLen'
1217+      by_cases h₁ : l' = l
1218+      · subst_vars
1219+        rw [Store_get_set_eq] <;> assumption
1220+      · rw [Store_get_set_neq] <;> try assumption
1221+        apply h₂
1222+        simp_all [List.length_set]
1223+
1224+--  #### Weakening for Stores
1225+
1226+--  Finally, we need a lemma on store typings, stating that,
1227+--  if a store typing is extended with a new location, the
1228+--  extended one still allows us to assign the same types to
1229+--  the same terms as the original.
1230+
1231+theorem store_weakening {Γ : Context} {δ δ' : StoreTy} {t : Tm} {τ : Ty}
1232+  (hExt : Extends δ' δ)
1233+  (hTy : <{ Γ / δ ⊢ t ⦂ τ }>) :
1234+  <{ Γ / δ' ⊢ t ⦂ τ }> := by
1235+    induction hTy with (try (apply_rules using StlcRefTyping; done))
1236+    | loc_ h =>
1237+        rw [←extends_lookup] <;> try assumption
1238+        apply HasType.loc_
1239+        apply length_extends <;> assumption
1240+
1241+--  We can use the `store_weakening` lemma to prove that if
1242+--  a store is well typed with respect to a store typing,
1243+--  then the store extended with a new term `τ` will still
1244+--  be well typed with respect to the store typing extended
1245+--  with `τ`'s type.
1246+
1247+theorem store_well_typed_app {δ : StoreTy} {ρ : Store} {t₁ : Tm} {τ₁ : Ty}
1248+  (hStoreTy : δ ⊢ ρ)
1249+  (hTy : <{ ∅ / δ ⊢ t₁ ⦂ τ₁ }>) :
1250+  (δ.concat τ₁) ⊢ (ρ.concat t₁) := by
1251+    have ⟨h₁, h₂⟩ := hStoreTy
1252+    simp_all only [List.concat_eq_append]
1253+    constructor
1254+    · simp_all
1255+    · simp_all only [List.length_append, List.length_cons, List.length_nil, Nat.zero_add]
1256+      intro l hl
1257+      inversion hl with
1258+      | refl =>
1259+          apply store_weakening <;> try assumption
1260+          apply extends_app
1261+          simp_all [MyGetElem.getElem]
1262+      | step hl =>
1263+          apply store_weakening <;> try assumption
1264+          · apply extends_app
1265+          · have hl' : l < ρ.length := by lia
1266+            simp_all [MyGetElem.getElem, List.getElem?_append_left]
1267+
1268+--  #### Preservation!
1269+
1270+--  Now that we've got everything set up right, the proof of
1271+--  preservation is actually quite straightforward:
1272+
1273+theorem preservation {δ : StoreTy} {t t' : Tm} {τ : Ty} {ρ ρ' : Store}
1274+  (hTy : <{ ∅ / δ ⊢ t ⦂ τ }>)
1275+  (hStoreTy : δ ⊢ ρ)
1276+  (hEval : t / ρ ⟶ t' / ρ') :
1277+    ∃ δ', Extends δ' δ ∧ (<{ ∅ / δ' ⊢ t' ⦂ τ }>) ∧ (δ' ⊢ ρ') := by
1278+
1279+    generalize heq : (∅ : Context) = Γ at hTy
1280+    -- discharge the goals where `t` doesn't step
1281+    induction hTy generalizing t' with (subst_vars; try (inversion hEval; done))
1282+    | app h₁ h₂ ih₁ ih₂ =>
1283+      inversion hEval with
1284+      | appAbs =>
1285+        inversion h₁ with | abs h =>
1286+        exists δ; constructor
1287+        apply extends_refl; constructor
1288+        apply_rules [substitution_preserves_typing, extends_refl] using StlcRefTyping
1289+        assumption
1290+      | app₁ hs =>
1291+        have ⟨δ', hExt, hTy', hStoreTy'⟩ := ih₁ hs rfl
1292+        exists δ'; constructor
1293+        assumption; constructor
1294+        solve_by_elim [store_weakening] using StlcRefTyping
1295+        assumption
1296+      | app₂ _ hs =>
1297+        have ⟨δ', hExt, hTy', hStoreTy'⟩ := ih₂ hs rfl
1298+        exists δ'; constructor
1299+        assumption; constructor
1300+        solve_by_elim [store_weakening] using StlcRefTyping
1301+        assumption
1302+    | succ _ ih =>
1303+      inversion hEval with
1304+      | succNat =>
1305+        exists δ; constructor
1306+        apply extends_refl; constructor
1307+        constructor
1308+        assumption
1309+      | succ hs =>
1310+        have ⟨δ', hExt, hTy', hStoreTy'⟩ := ih hs rfl
1311+        exists δ'; constructor
1312+        assumption; constructor
1313+        solve_by_elim [store_weakening] using StlcRefTyping
1314+        assumption
1315+    | pred _ ih =>
1316+      inversion hEval with
1317+      | predConst =>
1318+        exists δ; constructor
1319+        apply extends_refl; constructor
1320+        constructor
1321+        assumption
1322+      | pred hs =>
1323+        have ⟨δ', hExt, hTy', hStoreTy'⟩ := ih hs rfl
1324+        exists δ'; constructor
1325+        assumption; constructor
1326+        solve_by_elim [store_weakening] using StlcRefTyping
1327+        assumption
1328+    | mult h₁ h₂ ih₁ ih₂ =>
1329+      inversion hEval with
1330+      | multConst =>
1331+        exists δ; constructor
1332+        apply extends_refl; constructor
1333+        constructor
1334+        assumption
1335+      | mult₁ hs =>
1336+        have ⟨δ', hExt, hTy', hStoreTy'⟩ := ih₁ hs rfl
1337+        exists δ'; constructor
1338+        assumption; constructor
1339+        solve_by_elim [store_weakening] using StlcRefTyping
1340+        assumption
1341+      | mult₂ _ hs =>
1342+        have ⟨δ', hExt, hTy', hStoreTy'⟩ := ih₂ hs rfl
1343+        exists δ'; constructor
1344+        assumption; constructor
1345+        solve_by_elim [store_weakening] using StlcRefTyping
1346+        assumption
1347+    | ite0 _ h₂ h₃ ih₁ _ _ =>
1348+      inversion hEval with
1349+      | if0Step hs =>
1350+        have ⟨δ', hExt, hTy', hStoreTy'⟩ := ih₁ hs rfl
1351+        exists δ'; constructor
1352+        assumption; constructor
1353+        constructor <;> solve_by_elim [store_weakening] using StlcRefTyping
1354+        assumption
1355+      | if0Zero =>
1356+        exists δ; constructor
1357+        apply extends_refl; constructor <;> assumption
1358+      | if0Nonzero =>
1359+        exists δ; constructor
1360+        apply extends_refl; constructor <;> assumption
1361+    | @ref_ _ _ τ₁ h ih =>
1362+      inversion hEval with
1363+      | refValue =>
1364+        exists δ.concat τ₁; constructor
1365+        · rw [List.concat_eq_append]; apply extends_app
1366+        · constructor
1367+          · have h : <{Ref τ₁}> = <{Ref ~((δ.concat τ₁)[ρ.length])}> := by
1368+              simp_all [StoreWellTyped, MyGetElem.getElem]
1369+            rw [h]
1370+            constructor
1371+            simp [StoreWellTyped] at hStoreTy ⊢; lia
1372+          · apply store_well_typed_app <;> assumption
1373+      | ref_ hs =>
1374+        have ⟨δ', hExt, hTy', hStoreTy'⟩ := ih hs rfl
1375+        exists δ'; constructor
1376+        assumption; constructor
1377+        solve_by_elim [store_weakening] using StlcRefTyping
1378+        assumption
1379+    | deref h ih =>
1380+      inversion hEval with
1381+      | derefLoc hl =>
1382+        inversion h
1383+        exists δ; constructor
1384+        apply extends_refl; constructor
1385+        have ⟨h₁, h₂⟩ := hStoreTy
1386+        apply h₂ <;> assumption
1387+        assumption
1388+      | deref hs =>
1389+        have ⟨δ', hExt, hTy', hStoreTy'⟩ := ih hs rfl
1390+        exists δ'; constructor
1391+        assumption; constructor
1392+        solve_by_elim [store_weakening] using StlcRefTyping
1393+        assumption
1394+    | assign h₁ h₂ ih₁ ih₂ =>
1395+      inversion hEval with
1396+      | assign _ hl =>
1397+        inversion h₁
1398+        exists δ; constructor
1399+        apply extends_refl; constructor
1400+        constructor
1401+        apply assign_pres_store_typing <;> assumption
1402+      | assign₁ hs =>
1403+        have ⟨δ', hExt, hTy', hStoreTy'⟩ := ih₁ hs rfl
1404+        exists δ'; constructor
1405+        assumption; constructor
1406+        solve_by_elim [store_weakening] using StlcRefTyping
1407+        assumption
1408+      | assign₂ _ hs =>
1409+        have ⟨δ', hExt, hTy', hStoreTy'⟩ := ih₂ hs rfl
1410+        exists δ'; constructor
1411+        assumption; constructor
1412+        solve_by_elim [store_weakening] using StlcRefTyping
1413+        assumption
1414+
1415+--  ### Progress
1416+
1417+--  As we've said, progress for this system is pretty easy
1418+--  to prove; the proof is very similar to the proof of
1419+--  progress for the STLC, with a few new cases for the new
1420+--  syntactic constructs.
1421+
1422+theorem progress (δ : StoreTy) (t : Tm) (τ : Ty) (ρ : Store)
1423+  (hTy : <{ ∅ / δ ⊢ t ⦂ τ }>)
1424+  (hStoreTy : δ ⊢ ρ) :
1425+  (t.IsValue ∨ ∃ t' ρ', t / ρ ⟶ t' / ρ') := by
1426+    have ⟨hLen, _⟩ := hStoreTy
1427+    generalize heq : (∅ : Context) = Γ at hTy
1428+    induction hTy with (subst_vars; first
1429+      | contradiction
1430+      -- discharge cases where `t` is obviously a value
1431+      | try (left; constructor; done))
1432+    | app h₁ _ ih₁ ih₂ =>
1433+      right; cases ih₁ (by rfl) with
1434+      -- t₁ is a value
1435+      | inl hv₁ =>
1436+        cases ih₂ (by rfl) with
1437+        -- t₂ is a value
1438+        | inl hv₂ =>
1439+          cases hv₁ <;> try contradiction
1440+          apply Exists.intro; apply Exists.intro; solve_by_elim using StlcRefEval
1441+        -- t₂ steps
1442+        | inr hs₂ =>
1443+          have ⟨t₂', ρ', hs₂⟩ := hs₂
1444+          apply Exists.intro; apply Exists.intro; solve_by_elim using StlcRefEval
1445+      -- t₁ steps
1446+      | inr hs₁ =>
1447+        have ⟨t₁', ρ', hs₁⟩ := hs₁
1448+        apply Exists.intro; apply Exists.intro; solve_by_elim using StlcRefEval
1449+    | succ h ih
1450+    | pred h ih =>
1451+      -- these two cases are the same
1452+      right; cases ih (by rfl) with
1453+      -- t₁ is a value
1454+      | inl hv =>
1455+        cases hv <;> try contradiction
1456+        apply Exists.intro; apply Exists.intro; solve_by_elim using StlcRefEval
1457+      -- t₁ steps
1458+      | inr hs =>
1459+        have ⟨t₁', ρ', hs⟩ := hs
1460+        apply Exists.intro; apply Exists.intro; solve_by_elim using StlcRefEval
1461+    | mult h₁ h₂ ih₁ ih₂ =>
1462+      right; cases ih₁ (by rfl) with
1463+      -- t₁ is a value
1464+      | inl hv₁ =>
1465+        cases ih₂ (by rfl) with
1466+        -- t₂ is a value
1467+        | inl hv₂ =>
1468+          cases hv₁ <;> try contradiction
1469+          cases hv₂ <;> try contradiction
1470+          apply Exists.intro; apply Exists.intro; solve_by_elim using StlcRefEval
1471+        -- t₂ steps
1472+        | inr hs₂ =>
1473+          have ⟨t₂', ρ', hs₂⟩ := hs₂
1474+          apply Exists.intro; apply Exists.intro; solve_by_elim using StlcRefEval
1475+      -- t₁ steps
1476+      | inr hs₁ =>
1477+        have ⟨t₁', ρ', hs₁⟩ := hs₁
1478+        apply Exists.intro; apply Exists.intro; solve_by_elim using StlcRefEval
1479+    | ite0 h₁ _ _ ih₁ _ _ =>
1480+      right; cases ih₁ (by rfl) with
1481+      -- t₁ is a value
1482+      | inl hv₁ =>
1483+        cases hv₁ with (try contradiction)
1484+        | nat n =>
1485+          cases n <;> (apply Exists.intro; apply Exists.intro; solve_by_elim using StlcRefEval)
1486+      -- t₁ steps
1487+      | inr hs₁ =>
1488+        have ⟨t₁', ρ', hs₁⟩ := hs₁
1489+        apply Exists.intro; apply Exists.intro; solve_by_elim using StlcRefEval
1490+    | ref_ _ ih =>
1491+      right; cases ih (by rfl) with
1492+      -- t₁ is a value
1493+      | inl hv =>
1494+        apply Exists.intro; apply Exists.intro; solve_by_elim using StlcRefEval
1495+      -- t₁ steps
1496+      | inr hs =>
1497+        have ⟨t₁', ρ', hs⟩ := hs
1498+        apply Exists.intro; apply Exists.intro; solve_by_elim using StlcRefEval
1499+    | deref h ih =>
1500+      right; cases ih (by rfl) with
1501+      -- t₁ is a value; its typing tells us `l < δ.length`
1502+      | inl hv =>
1503+        cases hv with (inversion h)
1504+        | loc_ l => exists ρ[l], ρ; apply Step.derefLoc; lia
1505+      -- t₁ steps
1506+      | inr hs =>
1507+        have ⟨t₁', ρ', hs⟩ := hs
1508+        apply Exists.intro; apply Exists.intro; solve_by_elim using StlcRefEval
1509+    | @assign _ _ t₂ _ h₁ _ ih₁ ih₂ =>
1510+      right; cases ih₁ (by rfl) with
1511+      -- t₁ is a value
1512+      | inl hv₁ =>
1513+        cases ih₂ (by rfl) with
1514+        -- t₂ is a value
1515+        | inl hv₂ =>
1516+          cases hv₁ with (inversion h₁)
1517+          | loc_ l => exists <{ unit }>, ρ.set l t₂; apply Step.assign hv₂; lia
1518+        -- t₂ steps
1519+        | inr hs₂ =>
1520+          have ⟨_, _, _⟩ := hs₂
1521+          apply Exists.intro; apply Exists.intro; solve_by_elim using StlcRefEval
1522+      -- t₁ steps
1523+      | inr hs₁ =>
1524+        have ⟨t₁', ρ', hs₁⟩ := hs₁
1525+        apply Exists.intro; apply Exists.intro; solve_by_elim using StlcRefEval
1526+
1527+--  ## References and Nontermination
1528+
1529+--  An important fact about the STLC is that it is
1530+--  *normalizing* — that is, every well-typed term can be
1531+--  reduced to a value in a finite number of steps.
1532+--
1533+--  What about STLC + references? Surprisingly, adding
1534+--  references causes us to lose the normalization property:
1535+--  there exist well-typed terms in the STLC + references
1536+--  which can continue to reduce forever, without ever
1537+--  reaching a normal form!
1538+--
1539+--  How can we construct such a term? The main idea is to
1540+--  make a function which calls itself. We first make a
1541+--  function which calls another function stored in a
1542+--  reference cell; the trick is that we then smuggle in a
1543+--  reference to itself!
1544+--
1545+--         (λR: Ref (Unit → Unit),
1546+--              R := (λx:Unit,(!R) unit); (!R) unit)
1547+--      (ref (λX:Unit.unit))
1548+
1549+namespace RefsAndNontermination
1550+
1551+def loop_fun := <{ λX : Unit. (!R) unit }>
1552+
1553+def loop :=
1554+  <{ (λR : Ref (Unit → Unit). (( R := (λX : Unit. (!R) unit) );  ( (! R) unit ) ))
1555+     (ref (λX : Unit. unit)) }>
1556+
1557+--  This term is well typed:
1558+
1559+theorem loop_typeable : ∃ τ, <{ ∅ / [] ⊢ loop ⦂ τ }> := by
1560+  apply Exists.intro
1561+  apply_rules using StlcRefTyping
1562+
1563+--  To show formally that the term diverges, we first define
1564+--  the `step_closure` of the single-step reduction
1565+--  relation, written `⟶+`. This is just like the reflexive
1566+--  step closure of single-step reduction (which we're been
1567+--  writing `⟶*`), except that it is not reflexive:
1568+--  `t ⟶+ t'` means that `τ` can reach `t'` by *one or more*
1569+--  steps of reduction.
1570+
1571+inductive StepClosure {X:Type} (R: Relation X) : X → X → Prop :=
1572+  | one {x y : X} (h₁ : R x y) : StepClosure R x y
1573+  | step {x y z : X} (h₁ : R x y) (h₂ : StepClosure R y z) : StepClosure R x z
1574+
1575+scoped notation:40
1576+  t:71 " / " ρ:41 " ⟶+ " t':71 " / " ρ':41 =>
1577+  StepClosure Step (t, ρ) (t', ρ')
1578+
1579+--  Now, we can show that the expression `loop` reduces to
1580+--  the expression `!(loc 0) unit` and the size-one store
1581+--  `[R:=(loc 0)] loop_fun`.
1582+--
1583+--  As a convenience, we introduce a slight variant of the
1584+--  `normalize` tactic, called `reduce`, which tries solving
1585+--  the goal with `Multi.refl` at each step, instead of
1586+--  waiting until the goal can't be reduced any more. Of
1587+--  course, the whole point is that `loop` doesn't
1588+--  normalize, so the old `normalize` tactic would just go
1589+--  into an infinite loop reducing it forever!
1590+
1591+syntax "reduce" " using " ident,+ : tactic
1592+
1593+macro_rules
1594+  | `(tactic| reduce using $xs,*) =>
1595+    `(tactic|
1596+      repeat
1597+        (apply Multi.step
1598+         · solve_by_elim (maxDepth := 15) (constructor := false) [Nat.le.refl, Nat.le.step] using $xs,*
1599+         try apply Multi.refl))
1600+
1601+--  Next, we use `reduce` to show that `loop` steps to
1602+--  `!(loc 0) unit`, starting from the ∅ store.
1603+
1604+theorem loop_steps_to_loop_fun :
1605+  loop / [] ⟶*  <{ (! (loc 0)) unit }> / [<{ [R := loc 0] loop_fun }>] := by
1606+    reduce using StlcRefEval
1607+
1608+--  Finally, we show that the latter expression reduces in
1609+--  two steps to itself!
1610+
1611+theorem loop_fun_step_self :
1612+  <{ (! (loc 0)) unit }> / [<{ [R := loc 0] loop_fun }>] ⟶+
1613+  <{ (! (loc 0)) unit }> / [<{ [R := loc 0] loop_fun }>] := by
1614+    apply StepClosure.step; solve_by_elim using StlcRefEval
1615+    apply StepClosure.one; solve_by_elim using StlcRefEval
1616+
1617+end RefsAndNontermination
1618+
1619+end STLCRef
1620+
1621+-- Source revision: a06e066, committed 2026-10-27 16:51 UTC

TS/Slang.lean

398398 --  Functional: computation. Relational: expressive. Best:
399399 --  both, proved equivalent.
400400 
401--- Source revision: 2ca0e09, committed 2026-10-23 15:44 UTC
401+-- Source revision: a06e066, committed 2026-10-27 16:51 UTC

TS/Smallstep.lean

144144 
145145 --  ## Relations
146146 
147---  The step relation `⟶` is an example of a relation on
148---  `Tm`.
149-
150-def Relation (X : Type) := X → X → Prop
147+--  The step relation `⟶` is an example of a binary relation
148+--  on `Tm`.
149+
150+def Relation (α : Type) := α → α → Prop
151151 
152152 --  One simple property a relation may have is being
153153 --  *deterministic*: like Slang's big-step evaluation, each
177177 --
178178 --  Formally,
179179 
180-def Deterministic {X : Type} (R : Relation X) : Prop :=
181-  ∀ x y₁ y₂ : X, R x y₁ → R x y₂ → y₁ = y₂
180+def Deterministic {α : Type} (R : Relation α) : Prop :=
181+  ∀ x y₁ y₂ : α, R x y₁ → R x y₂ → y₁ = y₂
182182 
183183 namespace SimpleArith2
184184 
187187   induction h₁ generalizing y₂ with
188188   | plus n₁ n₂ =>
189189       intro h₂
190-      cases h₂ <;> first | rfl | cases ‹SimpleArith1.Step (.c _) _›
190+      cases h₂ <;> try contradiction
191+      rfl
191192   | plusLeft t₁ t₁' t₂ hs ih =>
192193       intro h₂
193-      cases h₂ <;> first | cases ‹SimpleArith1.Step (.c _) _› | rw [ih _ ‹SimpleArith1.Step t₁ _›]
194+      cases h₂ <;> try contradiction
195+      case plusLeft.plusLeft h => rw [ih _ h]
194196   | plusRight n₁ t₂ t₂' hs ih =>
195197       intro h₂
196-      cases h₂ <;> first | cases ‹SimpleArith1.Step (.c _) _› | rw [ih _ ‹SimpleArith1.Step t₂ _›]
198+      cases h₂ <;> try contradiction
199+      case plusRight.plusRight h => rw [ih _ h]
197200 
198201 end SimpleArith2
199202 
224227 
225228 theorem strong_progress (t : Tm) : IsValue t ∨ ∃ t', t ⟶ t' := by
226229   induction t with
227-  | c n => left; exact .const n
230+  | c n => left; constructor
228231   | p t₁ t₂ ih₁ ih₂ =>
229232       right
230233       cases ih₁ with
234237               cases hv₁ with
235238               | const n₁ =>
236239                   cases hv₂ with
237-                  | const n₂ => exact ⟨.c (n₁ + n₂), .plus n₁ n₂⟩
240+                  | const n₂ =>
241+                      exists .c (n₁ + n₂)
242+                      apply Step.plus
238243           | inr h₂ =>
239244               obtain ⟨t₂', ht₂⟩ := h₂
240-              exact ⟨.p t₁ t₂', .plusRight t₁ t₂ t₂' hv₁ ht₂⟩
245+              exists .p t₁ t₂'
246+              apply Step.plusRight
247+              · exact hv₁
248+              · exact ht₂
241249       | inr h₁ =>
242250           obtain ⟨t₁', ht₁⟩ := h₁
243-          exact ⟨.p t₁' t₂, .plusLeft t₁ t₁' t₂ ht₁⟩
244-
245-def IsNormalForm {X : Type} (R : Relation X) (t : X) : Prop :=
251+          exists .p t₁' t₂
252+          apply Step.plusLeft
253+          exact ht₁
254+
255+def IsNormalForm {α : Type} (R : Relation α) (t : α) : Prop :=
246256   ¬ ∃ t', R t t'
247257 
248258 --  We can use this terminology to generalize the
261271     (h : IsNormalForm Step t) : IsValue t := by
262272   cases strong_progress t with
263273   | inl hv => exact hv
264-  | inr hstep => exact absurd hstep h
274+  | inr hstep => contradiction
265275 
266276 theorem nf_same_as_value (t : Tm) :
267277     IsNormalForm Step t ↔ IsValue t := by
268-  exact ⟨nf_is_value t, value_is_nf t⟩
278+  constructor
279+  · apply nf_is_value
280+  · apply value_is_nf
269281 
270282 --  Why is this interesting? Because `IsValue` is a
271283 --  *syntactic* concept — it is defined by looking at the
327339 
328340 theorem value_not_same_as_normal_form :
329341     ∃ v, IsValue v ∧ ¬ IsNormalForm Step v := by
330-  apply Exists.intro (.p (.c 0) (.c 0))
331-  apply And.intro (.funny _ 0)
332-  sorry
342+  exists .p (.c 0) (.c 0)
343+  constructor
344+  · apply IsValue.funny
345+  · sorry
333346 
334347 --  (End of exercise)
335348 
371384 
372385 theorem value_not_same_as_normal_form :
373386     ∃ v, IsValue v ∧ ¬ IsNormalForm Step v := by
374-  apply Exists.intro (.c 5)
375-  apply And.intro (.const 5)
376-  sorry
387+  exists .c 5
388+  constructor
389+  · apply IsValue.const
390+  · sorry
377391 
378392 end Temp2
379393 
412426 
413427 theorem value_not_same_as_normal_form :
414428     ∃ t, ¬ IsValue t ∧ IsNormalForm Step t := by
415-  apply Exists.intro (.p (.c 1) (.p (.c 1) (.c 2)))
416-  apply And.intro
429+  exists .p (.c 1) (.p (.c 1) (.c 2))
430+  constructor
417431   · sorry
418432   · sorry
419433 
421435 
422436 --  ## Multi-Step Reduction
423437 
424-inductive Multi {X : Type} (R : Relation X) : X → X → Prop where
425-  | refl (x : X) : Multi R x x
426-  | step (x y z : X) (h₁ : R x y) (h₂ : Multi R y z) : Multi R x z
438+inductive Multi {α : Type} (R : Relation α) : α → α → Prop where
439+  | refl (x : α) : Multi R x x
440+  | step (x y z : α) (h₁ : R x y) (h₂ : Multi R y z) : Multi R x z
427441 
428442 --  We write `⟶*` for the `Multi Step` relation on terms
429443 
440454   · exact .plus 1 2
441455   · rfl
442456 
443-theorem multi_single {X : Type} (R : Relation X) (x y : X)
457+theorem multi_single {α : Type} (R : Relation α) (x y : α)
444458     (h : R x y) : Multi R x y := by
445-  exact .step x y y h (.refl y)
446-
447-theorem multi_trans {X : Type} (R : Relation X) (x y z : X)
459+  apply Multi.step (y := y)
460+  · exact h
461+  · rfl
462+
463+theorem multi_trans {α : Type} (R : Relation α) (x y z : α)
448464     (g : Multi R x y) (h : Multi R y z) : Multi R x z := by
449465   induction g with
450466   | refl a => exact h
451-  | step a b c h₁ h₂ ih => exact .step a b z h₁ (ih h)
467+  | step a b c h₁ h₂ ih =>
468+      apply Multi.step (y := b)
469+      · exact h₁
470+      · exact ih h
452471 
453472 --   ----------------------------------------
454473 
468487     (.p (.p (.c 0) (.c 3)) (.p (.c 2) (.c 4)))
469488       ⟶* .c ((0 + 3) + (2 + 4)) := by
470489   apply Multi.step (y := .p (.c (0 + 3)) (.p (.c 2) (.c 4)))
471-  · exact .plusLeft _ _ _ (.plus 0 3)
490+  · apply Step.plusLeft
491+    apply Step.plus
472492   apply Multi.step (y := .p (.c (0 + 3)) (.c (2 + 4)))
473-  · exact .plusRight _ _ _ (.const _) (.plus 2 4)
474-  · exact multi_single _ _ _ (.plus (0 + 3) (2 + 4))
493+  · apply Step.plusRight
494+    · apply IsValue.const
495+    · apply Step.plus
496+  · apply multi_single
497+    apply Step.plus
475498 
476499 --  ### Normal Forms Again
477500 
479502 --  a normal form, we say that "`t'` is *a normal form of*
480503 --  `t`."
481504 
482-def IsNormalFormOf {X : Type} (R : Relation X) (t t' : X) : Prop :=
505+def IsNormalFormOf {α : Type} (R : Relation α) (t t' : α) : Prop :=
483506   Multi R t t' ∧ IsNormalForm R t'
484507 
485508 --  When `R` is deterministic (as for our language's
501524 --  a normal form in a finite number of steps. Determinism
502525 --  guarantees that normal form is unique. unique.
503526 
504-def Normalizing {X : Type} (R : Relation X) : Prop :=
527+def Normalizing {α : Type} (R : Relation α) : Prop :=
505528   ∀ t, ∃ t', IsNormalFormOf R t t'
506529 
507530 theorem multistep_congr_1 (t₁ t₁' t₂ : Tm) (h : t₁ ⟶* t₁') :
508531     (.p t₁ t₂) ⟶* (.p t₁' t₂) := by
509532   induction h with
510533   | refl x => exact .refl _
511-  | step x y z h₁ h₂ ih => exact .step _ (.p y t₂) _ (.plusLeft x y t₂ h₁) ih
534+  | step x y z h₁ h₂ ih =>
535+      apply Multi.step (y := .p y t₂)
536+      · apply Step.plusLeft
537+        exact h₁
538+      · exact ih
512539 
513540 --  ### Exercise (2 stars): multistep_congr_2 ⭐⭐
514541 
522549 theorem step_normalizing : Normalizing Step := by
523550   intro t
524551   induction t with
525-  | c n => exact ⟨.c n, .refl _, (nf_same_as_value _).mpr (.const n)⟩
552+  | c n =>
553+      exists .c n
554+      constructor
555+      · apply Multi.refl
556+      · apply (nf_same_as_value _).mpr
557+        apply IsValue.const
526558   | p t₁ t₂ ih₁ ih₂ =>
527559       obtain ⟨t₁', hs₁, hnf₁⟩ := ih₁
528560       obtain ⟨t₂', hs₂, hnf₂⟩ := ih₂
529561       obtain ⟨n₁⟩ := (nf_same_as_value _).mp hnf₁
530562       obtain ⟨n₂⟩ := (nf_same_as_value _).mp hnf₂
531-      apply Exists.intro (.c (n₁ + n₂))
532-      apply And.intro _ ((nf_same_as_value _).mpr (.const _))
533-      apply multi_trans _ _ _ _ (multistep_congr_1 t₁ (.c n₁) t₂ hs₁)
534-      apply multi_trans _ _ _ _ (multistep_congr_2 (.c n₁) t₂ (.c n₂) (.const n₁) hs₂)
535-      exact multi_single _ _ _ (.plus n₁ n₂)
563+      exists .c (n₁ + n₂)
564+      constructor
565+      · apply multi_trans _ _ _ _ (multistep_congr_1 t₁ (.c n₁) t₂ hs₁)
566+        apply multi_trans _ _ _ _ (multistep_congr_2 (.c n₁) t₂ (.c n₂) (.const n₁) hs₂)
567+        apply multi_single
568+        apply Step.plus
569+      · apply (nf_same_as_value _).mpr
570+        apply IsValue.const
536571 
537572 --  ### Equivalence of Big-Step and Small-Step
538573 
670705 example :
671706     (Aexp.plus (.num 3) (.plus (.num 2) (.num 1)))
672707       ⟶a (.plus (.num 3) (.num 3)) := by
673-  exact .plusRight (.num 3) (.plus 2 1)
708+  apply AStep.plusRight
709+  · apply IsAValue.num
710+  · apply AStep.plus
674711 
675712 --  ### Boolean Expressions
676713 
734771 example :
735772     (Bexp.le (.plus (.num 1) (.num 1)) (.num 3))
736773       ⟶b (.le (.num 2) (.num 3)) := by
737-  exact .leLeft (.plus 1 1)
774+  apply BStep.leLeft
775+  apply AStep.plus
738776 
739777 --   ----------------------------------------
740778 
792830 theorem anstep_not_deterministic : ¬ Deterministic ANStep := by
793831   intro hd
794832   have s₁ : ANStep (.plus (.plus (.num 1) (.num 1)) (.plus (.num 2) (.num 2)))
795-      (.plus (.num 2) (.plus (.num 2) (.num 2))) :=
796-    .plusLeft (.plus 1 1)
833+      (.plus (.num 2) (.plus (.num 2) (.num 2))) := by
834+    exact .plusLeft (.plus 1 1)
797835   have s₂ : ANStep (.plus (.plus (.num 1) (.num 1)) (.plus (.num 2) (.num 2)))
798-      (.plus (.plus (.num 1) (.num 1)) (.num 4)) :=
799-    .plusRight (.plus 2 2)
836+      (.plus (.plus (.num 1) (.num 1)) (.num 4)) := by
837+    exact .plusRight (.plus 2 2)
800838   have heq := hd _ _ _ s₁ s₂
801839   simp at heq
802840 
838876     (h : Multi AStep a a') : Multi ANStep a a' := by
839877   induction h with
840878   | refl x => exact .refl x
841-  | step x y z h₁ _ ih => exact .step x y z (astep_imp_anstep x y h₁) ih
879+  | step x y z h₁ _ ih =>
880+      apply Multi.step (y := y)
881+      · apply astep_imp_anstep
882+        exact h₁
883+      · exact ih
842884 
843885 --  ### A Small-Step Stack Machine
844886 
9731015 example : (.p (.c 3) (.p (.c 3) (.c 4))) ⟶* (.c 10) := by
9741016   normalize using SimpleArith
9751017 
976--- Source revision: 2ca0e09, committed 2026-10-23 15:44 UTC
1018+-- Source revision: a06e066, committed 2026-10-27 16:51 UTC

TS/Stlc.lean

525525   simp [subst, h]
526526 
527527 @[simp] theorem subst_app :
528-    <{ [x := s] (t₁ t₂) }> = <{ ([x := s] t₁) ([x := s] t₂) }> := rfl
529-
530-@[simp] theorem subst_tru : <{ [x := s] true }> = <{ true }> := rfl
531-
532-@[simp] theorem subst_fls : <{ [x := s] false }> = <{ false }> := rfl
528+    <{ [x := s] (t₁ t₂) }> = <{ ([x := s] t₁) ([x := s] t₂) }> := by rfl
529+
530+@[simp] theorem subst_tru : <{ [x := s] true }> = <{ true }> := by rfl
531+
532+@[simp] theorem subst_fls : <{ [x := s] false }> = <{ false }> := by rfl
533533 
534534 @[simp] theorem subst_ite :
535535     <{ [x := s] (if t₁ then t₂ else t₃) }> =
536-      <{ if [x := s] t₁ then [x := s] t₂ else [x := s] t₃ }> := rfl
536+      <{ if [x := s] t₁ then [x := s] t₂ else [x := s] t₃ }> := by rfl
537537 
538538 --   ----------------------------------------
539539 
10311031 
10321032 end Stlc
10331033 
1034--- Source revision: 2ca0e09, committed 2026-10-23 15:44 UTC
1034+-- Source revision: a06e066, committed 2026-10-27 16:51 UTC

TS/StlcProp.lean

140140     -- `t = t₁ t₂`.  Proceed by cases on whether `t₁` is a value or steps.
141141     subst hΓ
142142     right
143-    cases ih₁ rfl with
143+    cases ih₁ (by rfl) with
144144     | inl hv₁ =>
145-      cases ih₂ rfl with
145+      cases ih₂ (by rfl) with
146146       | inl hv₂ =>
147147         obtain ⟨x, u, rfl⟩ := canonical_forms_fun t₁ _ _ h₁ hv₁
148148         exists <{ [x := t₂] u }>
159159   | ite Γ t₁ t₂ t₃ τ₁ h₁ h₂ h₃ ih₁ ih₂ ih₃ =>
160160     subst hΓ
161161     right
162-    cases ih₁ rfl with
162+    cases ih₁ (by rfl) with
163163     | inl hv₁ =>
164164       cases canonical_forms_bool t₁ h₁ hv₁ with
165165       | inl he =>
582582 
583583 end StlcArith
584584 
585--- Source revision: 2ca0e09, committed 2026-10-23 15:44 UTC
585+-- Source revision: a06e066, committed 2026-10-27 16:51 UTC

TS/Sub.lean

994994   induction ht with (subst_vars; first | trivial | try lia)
995995   | sub Γ t₁ τ₁ τ₂ ht hs ih =>
996996     apply sub_inversion_bool at hs; subst_vars
997-    exact ih hv rfl
997+    apply ih hv
998+    rfl
998999 
9991000 --  ### Progress
10001001 
10091010     | try (left; constructor; done)
10101011   )
10111012   | app Γ τ₁ τ₂ t₁ t₂ h₁ h₂ ih₁ ih₂ =>
1012-      right; cases ih₁ rfl with
1013+      right; cases ih₁ (by rfl) with
10131014       -- t₁ is a value
10141015       | inl ht₁ =>
1015-        cases ih₂ rfl with
1016+        cases ih₂ (by rfl) with
10161017         -- t₂ is a value
10171018         | inl ht₂ =>
10181019           apply canonical_forms_of_arrow_types at h₁
10281029         obtain ⟨t₁', ht₁⟩ := ht₁
10291030         exists <{t₁' t₂}>; apply_rules using StlcSubEval
10301031   | ite Γ t₁ t₂ t₃ τ h₁ h₂ h₃ ih₁ ih₂ ih₃ =>
1031-    right; cases ih₁ rfl with
1032+    right; cases ih₁ (by rfl) with
10321033     -- t₁ is a value
10331034     | inl ht₁ =>
10341035       apply canonical_forms_of_bool at h₁
10821083   | abs Γ x τ₁ τ₂ t₁ h i =>
10831084       inversion heq; exists τ₁; solve_by_elim using StlcSubTyping
10841085   | sub Γ t₁ τ₁ τ₂ ht hs ih =>
1085-      obtain ⟨σ₂, hs', ht'⟩ := ih rfl
1086+      obtain ⟨σ₂, hs', ht'⟩ := ih (by rfl)
10861087       exists σ₂; solve_by_elim using StlcSubTyping
10871088 
10881089 --  Similarly:
10951096   induction h with (subst_vars; try contradiction)
10961097   | unit => inversion heq; solve_by_elim using StlcSubTyping
10971098   | sub Γ t₁ τ₁ τ₂ ht hs ih =>
1098-      specialize ih rfl
1099+      specialize ih (by rfl)
10991100       solve_by_elim using StlcSubTyping
11001101 
11011102 --  -- Add your lemmas for products here when you get to
12541255 
12551256 end StlcSub
12561257 
1257--- Source revision: 2ca0e09, committed 2026-10-23 15:44 UTC
1258+-- Source revision: a06e066, committed 2026-10-27 16:51 UTC

TS/Types.lean

681681 --  breaks. (These are graded manually; there is no Lean
682682 --  code to complete.)
683683 
684--- Source revision: 2ca0e09, committed 2026-10-23 15:44 UTC
684+-- Source revision: a06e066, committed 2026-10-27 16:51 UTC

TS.lean

66 import TS.StlcProp
77 import TS.MoreStlc
88 import TS.Sub
9+import TS.References
910 
10--- Source revision: 2ca0e09, committed 2026-10-23 15:44 UTC
11+-- Source revision: a06e066, committed 2026-10-27 16:51 UTC