TS Teacher (solutions) source diff

Switch volume / audience

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

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

21152115     )
21162116     | var => contradiction
21172117     | app Γ τ₁ τ₂ t₁ t₂ h₁ h₂ ih₁ ih₂ =>
2118-      right; cases ih₁ rfl
2118+      right; cases ih₁ (by rfl)
21192119       -- t₁ is a value
21202120       case _ ht₁ =>
2121-        cases ih₂ rfl
2121+        cases ih₂ (by rfl)
21222122         -- t₂ is a value
21232123         case _ ht₂ =>
21242124           apply canonical_forms_fun at h₁
21342134         obtain ⟨t₁', ht₁⟩ := ht₁
21352135         exists <{t₁' t₂}>; apply_rules using ExtStlcEval
21362136     | succ Γ t₁ h ih =>
2137-      right; cases ih rfl
2137+      right; cases ih (by rfl)
21382138       -- t₁ is a value
21392139       case _ ht₁ =>
21402140         apply canonical_forms_nat at h
21452145         obtain ⟨t₁', ht₁⟩ := ht₁
21462146         exists <{succ t₁'}>; apply_rules using ExtStlcEval
21472147     | pred Γ t₁ h ih =>
2148-      right; cases ih rfl
2148+      right; cases ih (by rfl)
21492149        -- t₁ is a value
21502150       case _ ht₁ =>
21512151         apply canonical_forms_nat at h
21552155         obtain ⟨t₁', ht₁⟩ := ht₁
21562156         exists <{pred t₁'}>; apply_rules using ExtStlcEval
21572157     | mult Γ t₁ t₂ h₁ h₂ ih₁ ih₂ =>
2158-      right; cases ih₁ rfl
2158+      right; cases ih₁ (by rfl)
21592159       -- t₁ is a value
21602160       case _ ht₁ =>
2161-        cases ih₂ rfl
2161+        cases ih₂ (by rfl)
21622162         -- t₂ is a value
21632163         case _ ht₂ =>
21642164           apply canonical_forms_nat at h₁
21762176         obtain ⟨t₁', ht₁⟩ := ht₁
21772177         exists <{t₁' * t₂}>; apply_rules using ExtStlcEval
21782178     | ite0 Γ t₁ t₂ t₃ τ h₁ h₂ h₃ ih₁ ih₂ ih₃ =>
2179-      right; cases ih₁ rfl
2179+      right; cases ih₁ (by rfl)
21802180       -- t₁ is a value
21812181       case _ ht₁ =>
21822182         apply canonical_forms_nat at h₁
21892189         obtain ⟨t₁', ht₁⟩ := ht₁
21902190         exists <{if0 t₁' then t₂ else t₃}>; apply_rules using ExtStlcEval
21912191     | sumInl Γ t₁ τ₁ τ₂ h ih =>
2192-      cases ih rfl
2192+      cases ih (by rfl)
21932193       -- t₁ is a value
21942194       case _ ht₁ =>
21952195         left; apply_rules using ExtStlcEval
21982198         obtain ⟨t₁', ht₁⟩ := ht₁
21992199         right; exists <{inl τ₂ t₁'}>; apply_rules using ExtStlcEval
22002200     | sumInr Γ t₂ τ₁ τ₂ h ih =>
2201-      cases ih rfl
2201+      cases ih (by rfl)
22022202       -- t₁ is a value
22032203       case _ ht₁ =>
22042204         left; apply_rules using ExtStlcEval
22072207         obtain ⟨t₂', ht₁⟩ := ht₁
22082208         right; exists <{inr τ₁ t₂'}>; apply_rules using ExtStlcEval
22092209     | sumCase Γ x₁ x₂ τ₁ τ₂ τ₃ t t₁ t₂ h₁ h₂ h₃ ih₁ ih₂ ih₃ =>
2210-      right; cases ih₁ rfl
2210+      right; cases ih₁ (by rfl)
22112211       -- t₁ is a value
22122212       case _ ht =>
22132213         apply canonical_forms_sum at h₁
22192219         obtain ⟨t', ht⟩ := ht
22202220         exists <{case t' of inl x₁ => t₁ | inr x₂ => t₂}>; apply_rules using ExtStlcEval
22212221     | listCons Γ t₁ t₂ τ₁ h₁ h₂ ih₁ ih₂ =>
2222-      cases ih₁ rfl
2222+      cases ih₁ (by rfl)
22232223       -- t₁ is a value
22242224       case _ ht₁ =>
2225-        cases ih₂ rfl
2225+        cases ih₂ (by rfl)
22262226         -- t₂ is a value
22272227         case _ ht₂ =>
22282228           left; apply_rules using ExtStlcEval
22352235         obtain ⟨t₁', ht₁⟩ := ht₁
22362236         right; exists <{t₁' :: t₂}>; apply_rules using ExtStlcEval
22372237     | listCase Γ t₁ t₂ t₃ x₁ x₂ τ₁ τ₂ h₁ h₂ h₃ ih₁ ih₂ ih₃ =>
2238-        right; cases ih₁ rfl
2238+        right; cases ih₁ (by rfl)
22392239         -- t₁ is a value
22402240         case _ ht =>
22412241           apply canonical_forms_list at h₁
22482248           exists <{case t' of nil => t₂ | x₁ :: x₂ => t₃}>; apply_rules using ExtStlcEval
22492249     -- complete the proof
22502250     | pair Γ t₁ t₂ τ₁ τ₂ h₁ h₂ ih₁ ih₂ =>
2251-      cases ih₁ rfl
2251+      cases ih₁ (by rfl)
22522252       -- t₁ is a value
22532253       case _ ht₁ =>
2254-        cases ih₂ rfl
2254+        cases ih₂ (by rfl)
22552255         -- t₂ is a value
22562256         case _ ht₂ =>
22572257           left; apply_rules using ExtStlcEval
22642264         obtain ⟨t₁', ht₁⟩ := ht₁
22652265         right; exists <{(t₁', t₂)}>; apply_rules using ExtStlcEval
22662266     | fst Γ t τ₁ τ₂ h ih =>
2267-      right; cases ih rfl
2267+      right; cases ih (by rfl)
22682268       -- t₁ is a value
22692269       case _ ht₁ =>
22702270         apply canonical_forms_prod at h
22752275         obtain ⟨t₁', ht₁⟩ := ht₁
22762276         exists <{fst t₁'}>; apply_rules using ExtStlcEval
22772277     | snd Γ t τ₁ τ₂ h ih =>
2278-      right; cases ih rfl
2278+      right; cases ih (by rfl)
22792279       -- t₁ is a value
22802280       case _ ht₁ =>
22812281         apply canonical_forms_prod at h
22862286         obtain ⟨t₁', ht₁⟩ := ht₁
22872287         exists <{snd t₁'}>; apply_rules using ExtStlcEval
22882288     | letIn Γ x t₁ t₂ τ₁ τ₂ h₁ h₂ ih₁ ih₂ =>
2289-      right; cases ih₁ rfl
2289+      right; cases ih₁ (by rfl)
22902290       -- t₁ is a value
22912291       case _ ht₁ =>
22922292         exists <{ [x := t₁] t₂ }>; apply_rules using ExtStlcEval
22952295         obtain ⟨t₁', ht₁⟩ := ht₁
22962296         exists <{let x = t₁' in t₂}>; apply_rules using ExtStlcEval
22972297     | fix Γ t₁ τ₁ h ih =>
2298-        right; cases ih rfl
2298+        right; cases ih (by rfl)
22992299         -- t₁ is a value
23002300         case _ ht₁ =>
23012301           apply canonical_forms_fun at h
24402440 
24412441 end StlcExtended
24422442 
2443--- Source revision: 2ca0e09, committed 2026-10-23 15:44 UTC
2443+-- 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 Lean formalization
6---  of type systems, covering the simply typed lambda calculus, progress
7---  and preservation theorems, and extensions such as subtyping and
8---  polymorphism. Please check back later!
5+--  ## Welcome
96 
10---  ## Recommended Citation Format
7+--  This is Type Systems, volume 3 of *Software Foundations in Lean*. It
8+--  develops *type systems*: static checks for establishing that *all*
9+--  programs in a given language are well behaved, in contrast to Hoare
10+--  Logic, which develops techniques for reasoning about the behavior of a
11+--  *specific* program. The two volumes can be read in either order, and
12+--  both build on the material in Logical Foundations.
13+
14+--  ## Overview
15+
16+--  To reason about a program, we represent it as a mathematical object
17+--  together with a mathematical function or relation for describing its
18+--  behavior. Our main approach to doing so is called *operational
19+--  semantics*, and it amounts to defining a kind of *abstract interpreter*
20+--  for the programs in a language. We present two styles of operational
21+--  semantics: the *big-step* style specifies a program's behavior by
22+--  relating it directly to its final value, while the *small-step* style
23+--  specifies a program's behavior as a series of computational steps. The
24+--  small-step approach is more involved, but also makes it possible to
25+--  reason about a program's evaluation in a more fine-grained manner.
26+--
27+--  After introducing operational semantics using a simple language of
28+--  arithmetic and boolean expressions (Slang), we turn to *types*, the
29+--  volume's central subject. A type is a static classification of what a
30+--  program computes, and a *type system* is a static reasoning system that
31+--  uses types to rule out whole categories of run-time errors before a
32+--  program is ever run. Working with a small language of numbers and
33+--  booleans, we define a type system for it and prove the two signature
34+--  theorems of type-system metatheory — *progress* (a well-typed term is
35+--  either a value or can take a step) and *preservation* (taking a step
36+--  preserves well-typedness) — which together guarantee that a well-typed
37+--  program can never "go wrong."
38+--
39+--  Finally, we turn our attention to the *simply typed lambda-calculus*
40+--  (STLC), a much richer language with a more interesting type system. We
41+--  start from a small untyped core and extend it with numbers, pairs,
42+--  sums, lists, and general recursion, proving progress and preservation
43+--  anew for the extended language. We then study *subtyping*, a mechanism
44+--  that lets a term of one type stand in for a term of another — motivated
45+--  by the way record types behave in object-oriented languages — and prove
46+--  progress and preservation once more for a language with subtyping. In
47+--  so doing, we work our way up to a fairly full featured programming
48+--  language.
49+
50+--  ## Practicalities
51+
52+--  This volume assumes you already have Lean and VS Code set up as
53+--  described in the Logical Foundations Preface, and that you are
54+--  comfortable with the basic mechanics of working through an SFL chapter.
55+--  The exercises here have the same "advanced"/"optional" markings, and
56+--  star ratings.
57+--
58+--  Briefly (see the Logical Foundations Preface for detail), to get
59+--  started:
60+--
61+--  If you are using this book as part of a class, your instructor will
62+--  have created a "student" release for you; download and unzip it, open
63+--  the resulting directory in VS Code, and open a `.lean` file (e.g.,
64+--  `TS/Slang.lean`) to get started.
65+--
66+--  If you are reading on your own, clone the
67+--  [SF-in-Lean](https://github.com/plclub/sf-in-lean) repository and run
68+--  `make
69+--  ts-student` from the root directory to build the student version
70+--  of this volume; it is written to `_out/ts/student/`, with an `html/`
71+--  directory and a `lean/` directory, exactly as described for Logical
72+--  Foundations. Run `make
73+--  student` instead if you want all three volumes
74+--  built together.
75+
76+--  ### Building on Your Own Copy of Logical Foundations
77+
78+--  This project includes a copy of the Logical Foundations files that
79+--  chapters in this volume depend on, in their own `LF/` directory, so you
80+--  do not need a separate Logical Foundations download to build or read
81+--  this volume. If you have already worked through Logical Foundations and
82+--  would rather this volume build on your own work, copy the whole `LF/`
83+--  directory from your Logical Foundations download over this project's
84+--  `LF/` directory, then rebuild.
85+--
86+--  Exercises in this volume use the same star ratings, and the same
87+--  "advanced"/"optional" markings, described in the Logical Foundations
88+--  Preface.
89+
90+--  ### Citation Format
1191 
1292 --  If you want to refer to this volume in your own writing, please do so
1393 --  as follows:
21101 --  publisher    =   "Electronic textbook",
22102 --  note         =   {Version 0.1.0, \URL<https://github.com/plclub/sf-in-lean>}
23103 --  }
104+
105+--  ## For Potential Contributors
106+
107+--  If you find things you'd like to help add or improve, your
108+--  contributions are welcome! To get started, clone the [SF-in-Lean git
109+--  repo](https://github.com/plclub/sf-in-lean) and have a look at
110+--  `ALPHA-TESTERS.md`.
24111 
25112 --  ### Credits
26113 
72159 --  Note to developers (Benjamin Pierce @bcpierce00):
73160 --      Other funding should be acknowledged here...
74161 
75--- Source revision: 2ca0e09, committed 2026-10-23 15:44 UTC
162+-- 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+--  Up to this point, we have considered a variety of *pure* language
10+--  features, including functional abstraction, basic types such as numbers
11+--  and booleans, and structured types such as records and variants. These
12+--  features form the backbone of most programming languages — including
13+--  purely functional languages such as Haskell and "mostly functional"
14+--  languages such as ML, as well as imperative languages such as C and
15+--  object-oriented languages such as Java, C#, and Scala.
16+--
17+--  Most practical languages also include various *impure* features that
18+--  cannot be described in the simple semantic framework we have used so
19+--  far. In particular, besides just yielding results, computation in these
20+--  languages may assign to mutable variables (reference cells, arrays,
21+--  mutable record fields, etc.); perform input and output to files,
22+--  displays, or network connections; make non-local transfers of control
23+--  via exceptions, jumps, or continuations; engage in inter-process
24+--  synchronization and communication; and so on. In the literature on
25+--  programming languages, such "side effects" of computation are
26+--  collectively referred to as *computational effects*.
27+--
28+--  In this chapter, we'll see how one sort of computational effect —
29+--  mutable references — can be added to the calculi we have studied. The
30+--  main extension will be dealing explicitly with a *store* (or *heap*)
31+--  and *pointers* that name store locations. This extension is fairly
32+--  straightforward to define; the most interesting part is the refinement
33+--  we need to make to the statement of the type preservation theorem.
34+
35+--  ## Definitions
36+
37+--  Pretty much every programming language provides some form of assignment
38+--  operation that changes the contents of a previously allocated piece of
39+--  storage. (Lean is a rare exception!)
40+--
41+--  In some languages — notably ML and its relatives — the mechanisms for
42+--  name binding and those for assignment are kept separate. We can have a
43+--  variable `x` whose *value* is the number `5`, or we can have a variable
44+--  `y` whose value is a *reference* (or *pointer*) to a mutable cell whose
45+--  current contents is `5`. These are different things, and the difference
46+--  is visible to the programmer. We can add `x` to another number, but not
47+--  assign to it. We can use `y` to assign a new value to the cell that it
48+--  points to (by writing `y:=84`), but we cannot use `y` directly as an
49+--  argument to an operation like `+`. Instead, we must explicitly
50+--  *dereference* it, writing `!y` to obtain its current contents.
51+--
52+--  In most other languages — in particular, in all members of the C
53+--  family, including Java — *every* variable name refers to a mutable
54+--  cell, and the operation of dereferencing a variable to obtain its
55+--  current contents is implicit.
56+--
57+--  For purposes of formal study, it is useful to keep these mechanisms
58+--  separate. The development in this chapter will closely follow ML's
59+--  model. Applying the lessons learned here to C-like languages is a
60+--  straightforward matter of collapsing some distinctions and rendering
61+--  some operations such as dereferencing implicit instead of explicit.
62+
63+--  ### Syntax
64+
65+--  In this chapter, we study adding mutable references to the simply-typed
66+--  lambda calculus with natural numbers.
67+
68+namespace STLCRef
69+
70+open scoped MyGetElem
71+
72+--  The basic operations on references are *allocation*, *dereferencing*,
73+--  and *assignment*.
74+--  - To allocate a reference, we use the `ref` operator, providing an
75+--    initial value for the new cell.
76+--
77+--    For example, `ref 5` creates a new cell containing the value `5` and
78+--    reduces to a reference to that cell.
79+--
80+--  - To read the current value of this cell, we use the dereferencing
81+--    operator `!`.
82+--
83+--    For example, `!(ref 5)` reduces to `5`.
84+--
85+--  - To change the value stored in a cell, we use the assignment operator.
86+--
87+--    If `r` is a reference, `r := 7` will store the value `7` in the cell
88+--    referenced by `r`.
89+
90+--  ### Types
91+
92+--  We start with the simply typed lambda calculus over the natural
93+--  numbers. Besides the base natural-number type and arrow types, we add
94+--  two more types to deal with references. First, we need the *unit type*,
95+--  which we will use as the result type of an assignment operation. We
96+--  then add *reference types*.
97+--
98+--  If `τ` is a type, then `Ref τ` is the type of references to cells
99+--  holding values of type `τ`.
100+
101+--  τ ::= Nat
102+--      | Unit
103+--      | τ → τ
104+--      | Ref τ
105+
106+inductive Ty : Type :=
107+  | nat : Ty
108+  | unit : Ty
109+  | arrow : Ty → Ty → Ty
110+  | ref : Ty → Ty
111+
112+--  ### Terms
113+
114+--  Besides the usual variables, abstractions, applications, terms related
115+--  to natural numbers, and `unit`, we need four more sorts of terms to
116+--  handle mutable references:
117+
118+--  t ::= ref t     (reference)
119+--      | ! t       (dereference)
120+--      | t := t    (assignment)
121+--      | l         (location)
122+
123+inductive Tm  : Type :=
124+  -- STLC with numbers:
125+  | var    : String → Tm
126+  | app    : Tm → Tm → Tm
127+  | abs    : String → Ty → Tm → Tm
128+  | const  : Nat → Tm
129+  | succ    : Tm → Tm
130+  | pred    : Tm → Tm
131+  | mult    : Tm → Tm → Tm
132+  | ite0  : Tm → Tm → Tm → Tm
133+  -- New terms:
134+  | unit   : Tm
135+  | ref    : Tm → Tm
136+  | deref  : Tm → Tm
137+  | assign : Tm → Tm → Tm
138+  | loc    : Nat → Tm
139+
140+--  THE FOLLOWING DETAILS CAN BE SKIPPED (Notation)
141+scoped syntax:max num : stlcTm
142+scoped syntax:60 stlcTm:60 " * " stlcTm:61 : stlcTm
143+scoped syntax:50 "if0 " stlcTm:51 " then " stlcTm:50 " else " stlcTm:50 : stlcTm
144+
145+scoped syntax:60 stlcTm:60 " := " stlcTm:61 : stlcTm
146+scoped syntax:60 "Ref " stlcTy:61 : stlcTy
147+scoped syntax:60 "ref " stlcTm:61 : stlcTm
148+scoped syntax:60 "loc " stlcTm:61 : stlcTm
149+scoped syntax:60 "!" stlcTm:61 : stlcTm
150+scoped syntax:55 stlcTm:56 " ; " stlcTm:55 : stlcTm
151+
152+scoped syntax stlcCtx " / " term:max " ⊢ " stlcTm " ⦂ " stlcTy : stlcQuoted
153+
154+abbrev Tm.tseq t₁ t₂ :=
155+  Tm.app (.abs "X" .unit t₂) t₁
156+
157+namespace Elab
158+
159+open StlcCommon
160+open Lean Meta Elab Term
161+
162+def language : Language where
163+  tyType := ``Ty
164+  tmType := ``Tm
165+  arrowCtor := ``Ty.arrow
166+  varCtor := ``Tm.var
167+  appCtor := ``Tm.app
168+  absCtor := ``Tm.abs
169+  -- defined later
170+  subst := `STLCRef.subst
171+  hasType := `STLCRef.HasType
172+
173+def extendedTyHandler : TyElabHandler :=
174+  fun recur k T => do
175+    match T with
176+    | `(stlcTy| Nat) =>
177+        return mkConst ``Ty.nat
178+    | `(stlcTy| Unit) =>
179+        return mkConst ``Ty.unit
180+    | `(stlcTy| Ref $τ:stlcTy) => do
181+        let τ ← recur τ
182+        return mkApp (mkConst ``Ty.ref) τ
183+    | _ => k T
184+
185+def tyHandlers : TyElabHandler :=
186+  extendedTyHandler.orElse (commonTyHandler language)
187+
188+partial def elabTy : TyElab :=
189+  tyHandlers elabTy <| unsupportedTy language
190+
191+def extendedTmHandler : TmElabHandler :=
192+  fun recur k Γ free t => do
193+    match t with
194+    | `(stlcTm| $n:num) => do
195+        return (mkApp (mkConst ``Tm.const) (mkNatLit n.getNat), free )
196+
197+    | `(stlcTm| Nat) => do
198+        throwError "`Nat` is not a valid term."
199+
200+    | `(stlcTm| succ $t:stlcTm) => do
201+        let (t, free) ← recur Γ free t
202+        return (mkApp (mkConst ``Tm.succ) t, free)
203+
204+    | `(stlcTm| pred $t:stlcTm) => do
205+        let (t, free) ← recur Γ free t
206+        return (mkApp (mkConst ``Tm.pred) t, free)
207+
208+    | `(stlcTm| $t₁:stlcTm * $t₂:stlcTm) => do
209+        let (t₁, free) ← recur Γ free t₁
210+        let (t₂, free) ← recur Γ free t₂
211+        return (mkApp2 (mkConst ``Tm.mult) t₁ t₂, free)
212+
213+    | `(stlcTm| if0 $c:stlcTm then $t:stlcTm else $e:stlcTm) => do
214+        let (c, free) ← recur Γ free c
215+        let (t, free) ← recur Γ free t
216+        let (e, free) ← recur Γ free e
217+        return (mkApp3 (mkConst ``Tm.ite0) c t e, free)
218+
219+    | `(stlcTm| Unit) => do
220+        throwError "`Unit` is not a valid term."
221+
222+    | `(stlcTm| unit) => do
223+        return (mkConst ``Tm.unit, free)
224+
225+    | `(stlcTm| ref $t:stlcTm) => do
226+        let (t, free) ← recur Γ free t
227+        return (mkApp (mkConst ``Tm.ref) t, free)
228+
229+    | `(stlcTm| !$t:stlcTm) => do
230+        let (t, free) ← recur Γ free t
231+        return (mkApp (mkConst ``Tm.deref) t, free)
232+
233+    | `(stlcTm| loc $n:num) => do
234+        return (mkApp (mkConst ``Tm.loc) (mkNatLit n.getNat), free )
235+
236+    | `(stlcTm| $t₁:stlcTm := $t₂:stlcTm) => do
237+        let (t₁, free) ← recur Γ free t₁
238+        let (t₂, free) ← recur Γ free t₂
239+        return (mkApp2 (mkConst ``Tm.assign) t₁ t₂, free)
240+
241+    | `(stlcTm| $t₁:stlcTm ; $t₂:stlcTm) => do
242+        let (t₁, free) ← recur Γ free t₁
243+        let (t₂, free) ← recur Γ free t₂
244+        return (mkApp2 (mkConst ``Tm.tseq) t₁ t₂, free)
245+
246+    | _ => k Γ free t
247+
248+def tmHandlers : TmElabHandler :=
249+  extendedTmHandler.orElse (commonTmHandler language elabTy)
250+
251+partial def elabTm : TmElab :=
252+  tmHandlers elabTm unsupportedTm
253+
254+def elabCtx : CtxElab := elabCtxCommon language elabTy
255+
256+-- `HasType` takes the store typing as an extra first argument,
257+-- so we build typing judgments here instead of in `elabQuoted`.
258+def mkHasType (δ Γ t T : Expr) : TermElabM Expr := do
259+  let some hasType ← resolveId? (mkIdent language.hasType)
260+    | throwError "unknown declaration `{language.hasType}`"
261+  return mkApp4 hasType δ Γ t T
262+
263+@[scoped term_elab StlcCommon.bracket]
264+def elabBracket : TermElab :=
265+  fun stx expectedType? => do
266+    match stx with
267+    | `(<{ $Γ:stlcCtx / $δ:term ⊢ $t:stlcTm ⦂ $T:stlcTy }>) => do
268+        let (Γ, scope) ← elabCtx Γ
269+        let (t, _) ← elabTm scope [] t
270+        let T ← elabTy T
271+        let δ ← elabTermEnsuringType δ (mkApp (mkConst ``List [levelZero]) (mkConst ``Ty))
272+        mkHasType δ Γ t T
273+    | `(<{ $_:stlcCtx ⊢ $_:stlcTm ⦂ $_:stlcTy }>) =>
274+        throwError "typing judgments need a store typing: write `Γ / δ ⊢ t ⦂ τ`"
275+    | `(<{ $q:stlcQuoted }>) =>
276+        elabQuoted language elabTy elabTm elabCtx q expectedType?
277+    | _ => throwUnsupportedSyntax
278+
279+end Elab
280+
281+open scoped Elab
282+
283+namespace Delab
284+
285+open StlcCommon Elab Delab
286+open Lean PrettyPrinter Delaborator
287+
288+@[app_unexpander Ty.nat]
289+private def Ty.unexpandNat : Unexpander
290+  | stx => do
291+    let Nat := mkObjectIdentFrom stx "Nat"
292+    let T ← `(stlcTy| $Nat:ident)
293+    `(<{ $T:stlcTy }>)
294+
295+@[app_unexpander Ty.unit]
296+private def Ty.unexpandUnit : Unexpander
297+  | stx => do
298+    let Unit := mkObjectIdentFrom stx "Unit"
299+    let T ← `(stlcTy| $Unit:ident)
300+    `(<{ $T:stlcTy }>)
301+
302+@[app_unexpander Ty.arrow]
303+private def Ty.unexpandArrow : Unexpander := Delab.unexpandArrow
304+
305+@[app_unexpander Ty.ref]
306+private def Ty.unexpandRef : Unexpander
307+  | `($_ $T) => do
308+      let T' := getTy T
309+      `(<{ Ref $T':stlcTy }>)
310+  | _ => throw ()
311+
312+private def reservedNames : String → Bool
313+  | "Nat" | "Unit" | "succ" | "pred"
314+  | "if0" | "ref" | "loc" | "Ref"
315+  | "unit" => true
316+  | _ => false
317+
318+@[app_unexpander Tm.var]
319+private def Tm.unexpandVar : Unexpander := Delab.unexpandVar reservedNames ``Tm.var
320+
321+@[app_delab Tm.var]
322+private def Tm.delabVar : Delab := Delab.delabVar ``Tm.var
323+
324+@[app_unexpander Tm.app]
325+private def Tm.unexpandApp : Unexpander := Delab.unexpandApp
326+
327+@[app_unexpander Tm.abs]
328+private def Tm.unexpandAbs : Unexpander := Delab.unexpandAbs
329+
330+@[app_unexpander Tm.const]
331+private def Tm.unexpandConst : Unexpander
332+  | `($_ $n:num) => `(<{ $n:num }>)
333+  | _ => throw ()
334+
335+@[app_unexpander Tm.succ]
336+private def Tm.unexpandSucc : Unexpander
337+  | stx@`($_ $t) => do
338+      let succ := mkObjectIdentFrom stx "succ"
339+      let t' := getTm t
340+      `(<{ $succ:ident $t':stlcTm }>)
341+  | _ => throw ()
342+
343+@[app_unexpander Tm.pred]
344+private def Tm.unexpandPred : Unexpander
345+  | stx@`($_ $t) => do
346+      let pred := mkObjectIdentFrom stx "pred"
347+      let t' := getTm t
348+      `(<{ $pred:ident $t':stlcTm }>)
349+  | _ => throw ()
350+
351+@[app_unexpander Tm.mult]
352+private def Tm.unexpandMult : Unexpander
353+  | `($_ $t₁ $t₂) => do
354+      let t₁' := getTm t₁
355+      let t₂' := getTm t₂
356+      `(<{ $t₁':stlcTm * $t₂':stlcTm }>)
357+  | _ => throw ()
358+
359+@[app_unexpander Tm.tseq]
360+private def Tm.unexpandTseq : Unexpander
361+  | `($_ $t₁ $t₂) => do
362+      let t₁' := getTm t₁
363+      let t₂' := getTm t₂
364+      `(<{ $t₁':stlcTm ; $t₂':stlcTm }>)
365+  | _ => throw ()
366+
367+@[app_unexpander Tm.ite0]
368+private def Tm.unexpandIte0 : Unexpander
369+  | `($_ $c $t $e) => do
370+      let c' := getTm c
371+      let t' := getTm t
372+      let e' := getTm e
373+      `(<{ if0 $c':stlcTm then $t':stlcTm else $e':stlcTm }>)
374+  | _ => throw ()
375+
376+@[app_unexpander Tm.unit]
377+private def Tm.unexpandUnit : Unexpander
378+  | stx => do
379+      let unit := mkObjectIdentFrom stx "unit"
380+      let t ← `(stlcTm| $unit:ident)
381+      `(<{ $t:stlcTm }>)
382+
383+@[app_unexpander Tm.assign]
384+private def Tm.unexpandAssign : Unexpander
385+  | `($_ $t₁ $t₂) => do
386+      let t₁' := getTm t₁
387+      let t₂' := getTm t₂
388+      `(<{ $t₁':stlcTm := $t₂':stlcTm }>)
389+  | _ => throw ()
390+
391+@[app_unexpander Tm.ref]
392+private def Tm.unexpandRef : Unexpander
393+  | `($_ $t₁) => do
394+      let t₁' := getTm t₁
395+      `(<{ ref $t₁':stlcTm }>)
396+  | _ => throw ()
397+
398+@[app_unexpander Tm.deref]
399+private def Tm.unexpandDeref : Unexpander
400+  | `($_ $t₁) => do
401+      let t₁' := getTm t₁
402+      `(<{ !$t₁':stlcTm }>)
403+  | _ => throw ()
404+
405+@[app_unexpander Tm.loc]
406+private def Tm.unexpandLoc : Unexpander
407+  | `($_ $n:num) => `(<{ loc $n:num }>)
408+  | _ => throw ()
409+
410+end Delab
411+--  END DETAILS
412+
413+--  Intuitively:
414+--  - `ref t` (formally, `ref t`) allocates a new reference cell with the
415+--    value `τ` and reduces to the location of the newly allocated cell;
416+--  - `!t` (formally, `deref t`) reduces to the contents of the cell
417+--    referenced by `τ`;
418+--  - `t₁ := t₂` (formally, `assign t₁ t₂`) assigns `t₂` to the cell
419+--    referenced by `t₁`; and
420+--  - `l` (formally, `loc l`) is a reference to the cell at location `l`.
421+--    We'll discuss locations later.
422+--
423+--  In informal examples, we'll also freely use the extensions of the STLC
424+--  developed in the MoreStlc chapter; however, to keep the proofs small,
425+--  we won't bother formalizing them again here. (It would be easy to do
426+--  so, since there are no very interesting interactions between those
427+--  features and references.)
428+
429+--  ### Typing (Preview)
430+
431+--  Informally, the typing rules for allocation, dereferencing, and
432+--  assignment look roughly like this:
433+--
434+--            Γ ⊢ t₁ ⦂ τ₁
435+--      ---------------------  (ref)
436+--        Γ ⊢ ref t₁ ⦂ Ref τ₁
437+--
438+--            Γ ⊢ t₁ ⦂ Ref τ₁
439+--      ---------------------  (deref)
440+--           Γ ⊢ !t₁ ⦂ τ₁
441+--
442+--            Γ ⊢ t₁ ⦂ Ref τ₂
443+--            Γ ⊢ t₂ ⦂ τ₂
444+--      ---------------------  (assign)
445+--      Γ ⊢ t₁ := t₂ ⦂ Unit
446+--
447+--  The rule for locations will require a bit more machinery, and this will
448+--  motivate some changes to the other rules; we'll come back to this
449+--  later.
450+
451+--  ### Values and Substitution
452+
453+--  Besides abstractions, numbers, and the unit value, we have one new type
454+--  of value: locations.
455+--
456+--  A location is a concrete pointer value — think of it like an address in
457+--  memory. Locations should never be written directly by programmers; they
458+--  are used to keep track of the intermediate states of programs involving
459+--  references. In particular, the result of a `ref` expression is a
460+--  location.
461+
462+inductive Tm.IsValue : Tm → Prop :=
463+  | abs : forall x τ₂ t₁,
464+      IsValue <{λx : τ₂. t₁}>
465+  | nat : forall (n : Nat),
466+      IsValue (.const n)
467+  | unit :
468+      IsValue <{ unit }>
469+  | loc_ : forall (l : Nat),
470+      IsValue (.loc l)
471+
472+attribute [StlcRefEval] Tm.IsValue.abs Tm.IsValue.nat Tm.IsValue.unit Tm.IsValue.loc_
473+
474+--  Extending substitution to handle the new syntax of terms is
475+--  straightforward: substituting into a pointer leaves it unchanged.
476+
477+def subst (x : String) (s : Tm) (t : Tm) : Tm :=
478+  match t with
479+  -- pure STLC
480+  | .var y =>
481+      if x = y then s else t
482+  | .abs y τ t₁ =>
483+      if x = y then t else <{ λ y : τ . [x := s] t₁ }>
484+  | .app t₁ t₂ =>
485+      <{ ([x := s] t₁) ([x := s] t₂) }>
486+  -- numbers
487+  | .const _ =>
488+      t
489+  | .succ t₁ =>
490+      <{ succ ([x := s] t₁) }>
491+  | .pred t₁ =>
492+      <{ pred ([x := s] t₁) }>
493+  | .mult t₁ t₂ =>
494+      <{ ([x := s] t₁) * ([x := s] t₂) }>
495+  | .ite0 t₁ t₂ t₃ =>
496+      <{
497+        if0 [x := s] t₁
498+        then [x := s] t₂
499+        else [x := s] t₃
500+      }>
501+  -- unit
502+  | .unit => <{ unit }>
503+  -- references
504+  | .ref t₁ =>  <{ ref ([x := s] t₁) }>
505+  | .deref t₁ =>  <{ !([x := s] t₁) }>
506+  | .loc n => .loc n
507+  | .assign t₁ t₂ =>
508+      <{ ([x := s] t₁) := ([x := s] t₂) }>
509+
510+--  THE FOLLOWING DETAILS CAN BE SKIPPED (Notation encoding)
511+open Lean PrettyPrinter in
512+@[app_unexpander subst]
513+def unexpandSubst : Unexpander := StlcCommon.Delab.unexpandSubst
514+--  END DETAILS
515+
516+--  ## Pragmatics
517+
518+--  ### Side Effects and Sequencing
519+
520+--  The fact that we've chosen the result of an assignment expression to be
521+--  the trivial value `unit` allows a nice abbreviation for *sequencing*.
522+--  For example, we can write
523+
524+--  R:=succ(!R); !R
525+
526+--  as an abbreviation for
527+
528+--  (λX:Unit, !R) (R:=succ(!R))
529+
530+--  This has the effect of reducing two expressions in order and returning
531+--  the value of the second. Restricting the type of the first expression
532+--  to `Unit` helps the typechecker to catch some silly errors by
533+--  permitting us to throw away the first value only if it is really
534+--  guaranteed to be trivial.
535+--
536+--  Notice that, if the second expression is also an assignment, then the
537+--  type of the whole sequence will be `Unit`, so we can validly place it
538+--  to the left of another `;` to build longer sequences of assignments:
539+
540+--  R:=succ(!R); R:=succ(!R); R:=succ(!R); R:=succ(!R); !R
541+
542+--  Formally, we introduce sequencing as a *derived form* `tseq` that
543+--  expands into an abstraction and an application.
544+
545+/-- info: <{ R := succ (!R) ; !R }> : Tm -/
546+#guard_msgs in
547+#check <{R := succ (!R); !R}>
548+
549+--  ### References and Aliasing
550+
551+--  It is important to bear in mind the difference between the *reference*
552+--  that is bound to some variable `r` and the *cell* in the store that is
553+--  pointed to by this reference.
554+--
555+--  If we make a copy of `r`, for example by binding its value to another
556+--  variable `s`, what gets copied is only the reference, not the contents
557+--  of the cell itself.
558+--
559+--  For example, after reducing
560+--
561+--      let R = ref 5 in
562+--      let S = R in
563+--      S := 82;
564+--      (!R)+1
565+--
566+--  the cell referenced by `R` will contain the value `82`, while the
567+--  result of the whole expression will be `83`. The references `R` and `S`
568+--  are said to be *aliases* for the same cell.
569+--
570+--  The possibility of aliasing can make programs with references quite
571+--  tricky to reason about. For example, the expression
572+--
573+--      R := 5; R := !S
574+--
575+--  assigns `5` to `R` and then immediately overwrites it with `S`'s
576+--  current value; this has exactly the same effect as the single
577+--  assignment
578+--
579+--      R := !S
580+--
581+--  *unless* we happen to do it in a context where `R` and `S` are aliases
582+--  for the same cell!
583+--
584+--      let R = ref 0 in
585+--      let S = R in
586+--      R := 5; R := !S
587+
588+--  ### Shared State
589+
590+--  Of course, aliasing is also a large part of what makes references
591+--  useful. In particular, it allows us to set up "implicit communication
592+--  channels" — shared state — between different parts of a program. For
593+--  example, suppose we define a reference cell and two functions that
594+--  manipulate its contents:
595+--
596+--      let C = ref 0 in
597+--      let Incc = λ_:Unit. (C := succ (!C); !C) in
598+--      let Decc = λ_:Unit. (C := pred (!C); !C) in
599+--        ...
600+--
601+--  Note that, since their argument types are `Unit`, the arguments to the
602+--  abstractions in the definitions of `Incc` and `Decc` are not providing
603+--  any useful information to the bodies of these functions (using the
604+--  wildcard `_` as the name of the bound variable is a reminder of this).
605+--  Instead, the purpose of these abstractions is to "slow down" the
606+--  execution of the function bodies. Since function abstractions are
607+--  values, the two `let`s are executed simply by binding these functions
608+--  to the names `Incc` and `Decc`, rather than by actually incrementing or
609+--  decrementing `C`. Later, each call to one of these functions results in
610+--  its body being executed once and performing the appropriate mutation on
611+--  `C`. Such functions are often called *thunks*.
612+--
613+--  In the context of these declarations, calling `Incc` results in changes
614+--  to `C` that can be observed by calling `Decc`. For example, if we
615+--  replace the `...` with `(Incc unit; Incc unit; Decc
616+--  unit)`, the result
617+--  of the whole program will be `1`.
618+
619+--  ### Objects
620+
621+--  We can go a step further and write a *function* that creates `C`,
622+--  `Incc`, and `Decc`, packages `Incc` and `Decc` together into a record,
623+--  and returns this record:
624+
625+--  Newcounter =
626+--    λ_:Unit.
627+--        let C = ref 0 in
628+--        let Incc = λ_:Unit. (C := succ (!C); !C) in
629+--        let Decc = λ_:Unit. (C := pred (!C); !C) in
630+--        {i=Incc, d=Decc}
631+
632+--  Now, each time we call `Newcounter`, we get a new record of functions
633+--  that share access to the same storage cell `C`. The caller of
634+--  `Newcounter` can't get at this storage cell directly, but can affect it
635+--  indirectly by calling the two functions. In other words, we've created
636+--  a simple form of *object*.
637+
638+--  let C₁ = newcounter unit in
639+--  let C₂ = newcounter unit in
640+--  // we've allocated two separate storage cells now!
641+--  let R₁ = C₁.i unit in
642+--  let R₂ = C₂.i unit in
643+--  R₂  // yields 1, not 2!
644+
645+--  ### Exercise (1 star): store_draw (Manually graded) ⭐
646+
647+--  Draw (on paper) the contents of the store at the point in execution
648+--  where the first two `let`s have finished and the third one is about to
649+--  begin.
650+
651+--  ### References to Compound Types
652+
653+--  A reference cell need not contain just a number: the primitives we've
654+--  defined above allow us to create references to values of any type,
655+--  including functions. For example, we can use references to functions to
656+--  give a(n inefficient) implementation of arrays of numbers as follows.
657+--
658+--  Write `NatArray` for the type `Ref (Nat→Nat)`.
659+--
660+--  Recall the `Equal` function from the MoreStlc chapter:
661+--
662+--      Equal =
663+--        fix
664+--          (λEq:Nat→Nat→Bool.
665+--              λM:Nat. λN:Nat.
666+--                if M=0 then iszero n
667+--                else if N=0 then false
668+--                else Eq (pred m) (pred n))
669+--
670+--  To build a new array, we allocate a reference cell and fill it with a
671+--  function that, when given an index, always returns `0`.
672+--
673+--      Newarray = λ_:Unit. ref (λN:Nat.0)
674+--
675+--  To look up an element of an array, we apply the function to the desired
676+--  index.
677+--
678+--      Lookup = λA:NatArray, λN:Nat. (!A) N
679+--
680+--  The interesting part of the encoding is the `Update` function. It takes
681+--  an array, an index, and a new value to be stored at that index, and it
682+--  does its job by creating (and storing in the reference) a new function
683+--  that, when it is asked for the value at this very index, returns the
684+--  new value that was given to `Update`, while on all other indices it
685+--  passes the lookup to the function that was previously stored in the
686+--  reference.
687+
688+--  Update = \A:NatArray, \M:Nat, \V:Nat,
689+--    let Oldf = !A in
690+--    A := (λN:Nat. if Equal M N then V else Oldf N);
691+
692+--  References to values containing other references can also be very
693+--  useful, allowing us to define data structures such as mutable lists and
694+--  trees.
695+
696+--  ### Exercise (2 stars): compact_update (Manually graded) ⭐⭐
697+
698+--  If we defined `Update` more compactly like this
699+--
700+--      Update = \A:NatArray, \M:Nat, \V:Nat,
701+--          A := (λN:Nat. if Equal M N then V else (!A) N);
702+--
703+--  would it behave the same?
704+
705+--  No: calls to `Lookup` with any index other than the one given to
706+--  `Update` will now diverge. The point is that we need to make sure we
707+--  look up the value stored in `A` *before* we overwrite it with the new
708+--  function. Otherwise, when we get around to doing the lookup, we will
709+--  find the new function, not the original one.
710+
711+--  ### Null References
712+
713+--  There is one final significant difference between our references and
714+--  C-style mutable variables: in C-like languages, variables holding
715+--  pointers into the heap may sometimes have the value `NULL`.
716+--  Dereferencing such a "null pointer" is an error, and results either in
717+--  a clean exception (Java and C#) or in arbitrary and possibly insecure
718+--  behavior (C and relatives like C++). Null pointers cause significant
719+--  trouble in C-like languages: the fact that any pointer might be null
720+--  means that any dereference operation in the program can potentially
721+--  fail.
722+--
723+--  Even in ML-like languages, there are sometimes situations where we may
724+--  or may not have a valid pointer in our hands. Fortunately, there is no
725+--  need to extend the basic mechanisms of references to represent such
726+--  situations: the sum types introduced in the MoreStlc chapter already
727+--  give us what we need.
728+--
729+--  First, we can use sums to build an analog of the `option` types
730+--  introduced in the Lists chapter of *Logical Foundations*. Define
731+--  `Option τ` to be an abbreviation for `Unit + τ`.
732+--
733+--  Then a "nullable reference to a `τ`" is simply an element of the type
734+--  `Option (Ref τ)`.
735+
736+--  ### Garbage Collection
737+
738+--  A last issue that we should mention before we move on with formalizing
739+--  references is storage *de*-allocation. We have not provided any
740+--  primitives for freeing reference cells when they are no longer needed.
741+--  Instead, like many modern languages (including OCaml, Haskell, Java,
742+--  etc.), we rely on the run-time system to perform *garbage collection*,
743+--  automatically identifying and reusing cells that can no longer be
744+--  reached by the program.
745+--
746+--  This is *not* just a question of taste in language design: it is
747+--  extremely difficult to achieve type safety in the presence of an
748+--  explicit deallocation operation.
749+--
750+--  One reason for this is the familiar *dangling reference* problem: we
751+--  allocate a cell holding a number, save a reference to it in some data
752+--  structure, use it for a while, then deallocate it and allocate a new
753+--  cell holding a boolean, possibly reusing the same storage. Now we can
754+--  have two names for the same storage cell — one with type `Ref Nat` and
755+--  the other with type `Ref Bool`.
756+
757+--  ### Exercise (2 stars): type_safety_violation (Manually graded) ⭐⭐
758+
759+--  Show how this can lead to a violation of type safety.
760+
761+--  Suppose the language provides a primitive `free` that takes a reference
762+--  cell as argument and releases its storage so that (say) the very next
763+--  allocation of a reference cell will obtain the same piece of memory.
764+--  Then the program
765+
766+--  let R = ref 0 in
767+--      let S = R in
768+--      free R;
769+--      let T = ref true in
770+--      T := false;
771+--      succ (!S)
772+
773+--  will reduce to the stuck term `succ false`. Note that aliasing plays a
774+--  crucial role here in setting up the problem, since it prevents us from
775+--  detecting invalid deallocations by simply making `free r` illegal if
776+--  the variable `R` appears free in the remainder of the expression.
777+--
778+--  This sort of example is easy to mimic in a language like C with manual
779+--  memory management (our `ref` constructor corresponds to C's `malloc`,
780+--  our `free` to a simplified version of C's `free`).
781+
782+--  ## Operational Semantics
783+
784+--  ### Locations
785+
786+--  The most subtle aspect of the treatment of references appears when we
787+--  consider how to formalize their operational behavior. One way to see
788+--  why is to ask, "What should be the *values* of type `Ref τ`?" The
789+--  crucial observation that we need to take into account is that reducing
790+--  a `ref` operator should *do* something — namely, allocate some storage
791+--  — and the result of the operation should be a reference to this
792+--  storage.
793+--
794+--  What, then, is a reference?
795+--
796+--  The run-time store in most programming-language implementations is
797+--  essentially just a big array of bytes. The run-time system keeps track
798+--  of which parts of this array are currently in use. When we need to
799+--  allocate a new reference cell, we allocate a large enough segment from
800+--  the free region of the store (4 bytes for integer cells, 8 bytes for
801+--  cells storing `Float`s, etc.), record somewhere that it is being used,
802+--  and return the index (typically, a 32- or 64-bit integer) of the start
803+--  of the newly allocated region. These indices are references.
804+--
805+--  For present purposes, there is no need to be quite so concrete. We can
806+--  think of the store as an array of *values*, rather than an array of
807+--  bytes, abstracting away from the different sizes of the run-time
808+--  representations of different values. A reference, then, is simply an
809+--  index into the store. (If we like, we can even abstract away from the
810+--  fact that these indices are numbers, but for purposes of formalization
811+--  in Lean it is convenient to use numbers.) We use the word *location*
812+--  instead of *reference* or *pointer* to emphasize this abstract quality.
813+--
814+--  Treating locations abstractly in this way will prevent us from modeling
815+--  the *pointer arithmetic* found in low-level languages such as C. This
816+--  limitation is intentional. While pointer arithmetic is occasionally
817+--  very useful, especially for implementing low-level services such as
818+--  garbage collectors, it cannot be tracked by most type systems: knowing
819+--  that location `n` in the store contains a `Float` doesn't tell us
820+--  anything useful about the type of location `n+4`. In C, pointer
821+--  arithmetic is a notorious source of type-safety violations.
822+
823+--  ### Stores
824+
825+--  Recall that, in the small-step operational semantics for Imp, the step
826+--  relation needed to carry along an auxiliary state in addition to the
827+--  program being executed. In the same way, once we have added reference
828+--  cells to the STLC, our step relation must carry along a store to keep
829+--  track of the contents of reference cells.
830+--
831+--  We could re-use the same functional representation we used for states
832+--  in Imp, but for carrying out the proofs in this chapter it is actually
833+--  more convenient to represent a store simply as a *list* of values. (The
834+--  reason we didn't use this representation before is that, in Imp, a
835+--  program could modify any location at any time, so states had to be
836+--  ready to map *any* variable to a value. However, in the STLC with
837+--  references, the only way to create a reference cell is with `ref t₁`,
838+--  which puts the value of `t₁` in a new reference cell and reduces to the
839+--  location of the newly created reference cell. When reducing such an
840+--  expression, we can just add a new reference cell to the end of the list
841+--  representing the store.)
842+
843+abbrev Store := List Tm
844+
845+--  We use `ρ[n]` to retrieve the value of the reference cell at location
846+--  `n` in the store `ρ`. Note that we must give a default value to `nth`
847+--  in case we try looking up an index which is too large. (In fact, we
848+--  never actually do this, but *proving* that we don't will require a bit
849+--  of work.)
850+
851+open scoped MyGetElem
852+instance : MyGetElem Store Nat Tm where
853+  getElem ρ n := ρ.getD n <{unit}>
854+
855+@[simp]
856+theorem Store_get_succ_tl (hd : Tm) (tl : Store) (n : Nat) :
857+  (hd :: tl)[n + 1] = tl[n] := by rfl
858+
859+@[simp]
860+theorem Store_get_zero_hd (hd : Tm) (tl : Store) :
861+  (hd :: tl)[0] = hd := by rfl
862+
863+--  To update the store, we use the `List.set` function, which replaces the
864+--  contents of a cell at a particular index.
865+--
866+--      def List.set : (l : List α) → (n : Nat) → (a : α) → List α
867+--        | cons _ as, 0,          b => cons b as
868+--        | cons a as, Nat.succ n, b => cons a (set as n b)
869+--        | nil,       _,          _ => nil
870+--
871+--  As might be expected, we will also need some technical lemmas; they are
872+--  straightforward to prove.
873+
874+theorem Store_get_set_eq (ρ : Store) (l : Nat) (x : Tm)
875+  (h : l < ρ.length) :
876+  (ρ.set l x)[l] = x := by
877+  induction ρ generalizing l with
878+  | nil => simp_all
879+  | cons hd tl ih => cases l <;> simp_all
880+
881+theorem Store_get_set_neq (l₁ l₂ : Nat) (t : Tm) (ρ : Store) :
882+  l₁ ≠ l₂ ->
883+  (ρ.set l₂ t)[l₁] = ρ[l₁] := by
884+  induction ρ generalizing l₁ l₂ with
885+  | nil => simp
886+  | cons hd tl ih => cases l₁ <;> cases l₂ <;> simp_all
887+
888+--  ### Reduction
889+
890+--  Next, we need to extend the operational semantics to take stores into
891+--  account. Since the result of reducing an expression will in general
892+--  depend on the contents of the store in which it is reduced, the
893+--  evaluation rules should take not just a term but also a store as
894+--  argument. Furthermore, since the reduction of a term can cause side
895+--  effects on the store, and these may affect the reduction of other terms
896+--  in the future, the reduction rules need to return a new store. Thus,
897+--  the shape of the single-step reduction relation needs to change from
898+--  `t ⟶ t'` to `t / ρ ⟶ t' / ρ'`, where `ρ` and `ρ'` are the starting and
899+--  ending states of the store.
900+--
901+--  To carry through this change, we first need to augment all of our
902+--  existing reduction rules with stores:
903+--
904+--                  value v₂
905+--      ---------------------------------- (appAbs)
906+--      (λx:τ₂,t₁) v₂ / ρ ⟶ [x:=v₂]t₁ / ρ
907+--
908+--                 t₁ / ρ ⟶ t₁' / ρ'
909+--      --------------------------------   (app₁)
910+--              t₁ t₂ / ρ ⟶ t₁' t₂ / ρ'
911+--
912+--                 value v₁
913+--                 t₂ / ρ ⟶ t₂' / ρ'
914+--      --------------------------------   (app₂)
915+--              v₁ t₂ / ρ ⟶ v₁ t₂' / ρ'
916+--
917+--  Note that the first rule here returns the store unchanged, since
918+--  function application, in itself, has no side effects. The other two
919+--  rules simply propagate side effects from premise to conclusion.
920+--
921+--  Now, the result of reducing a `ref` expression will be a fresh
922+--  location; this is why we included locations in the syntax of terms and
923+--  in the set of values. It is crucial to note that making this extension
924+--  to the syntax of terms does not mean that we intend *programmers* to
925+--  write terms involving explicit, concrete locations: such terms will
926+--  arise only as intermediate results during reduction. This may seem odd,
927+--  but it follows naturally from our design decision to represent the
928+--  result of every reduction step by a modified *term*. If we had chosen a
929+--  more "machine-like" model, e.g., with an explicit stack to contain
930+--  values of bound identifiers, then the idea of adding locations to the
931+--  set of allowed values might seem more obvious.
932+--
933+--  In terms of this expanded syntax, we can state reduction rules for the
934+--  new constructs that manipulate locations and the store. First, to
935+--  reduce a dereferencing expression `!t₁`, we must first reduce `t₁`
936+--  until it becomes a value:
937+--
938+--       t₁ / ρ ⟶ t₁' / ρ'
939+--      -------------------- (deref)
940+--      !t₁ / ρ ⟶ !t₁' / ρ'
941+--
942+--  Once `t₁` has finished reducing, we should have an expression of the
943+--  form `!l`, where `l` is some location. (A term that attempts to
944+--  dereference any other sort of value, such as a function or `unit`, is
945+--  erroneous, as is a term that tries to dereference a location that is
946+--  larger than the size ρ.length of the currently allocated store; the
947+--  reduction rules simply get stuck in this case. The type-safety
948+--  properties established below assure us that well-typed terms will never
949+--  misbehave in this way.)
950+--
951+--           l < ρ.length
952+--      ------------------------ (derefLoc)
953+--      !(loc l) / ρ ⟶ ρ[l] / ρ
954+--
955+--  Next, to reduce an assignment expression `t₁:=t₂`, we must first reduce
956+--  `t₁` until it becomes a value (a location), and then reduce `t₂` until
957+--  it becomes a value (of any sort):
958+--
959+--            t₁ / ρ ⟶ t₁' / ρ'
960+--      ------------------------------ (assign₁)
961+--      t₁ := t₂ / ρ ⟶ t₁' := t₂ / ρ'
962+--
963+--            t₂ / ρ ⟶ t₂' / ρ'
964+--      ------------------------------ (assign₂)
965+--      v₁ := t₂ / ρ ⟶ v₁ := t₂' / ρ'
966+--
967+--  Once we have finished with `t₁` and `t₂`, we have an expression of the
968+--  form `l:=v`, which we execute by updating the store to make location
969+--  `l` contain `v`:
970+--
971+--               l < ρ.length
972+--      -------------------------------- (assign)
973+--      loc l := v / ρ ⟶ unit / [l:=v]ρ
974+--
975+--  The notation `[l:=v]ρ` means "the store that maps `l` to `v` and maps
976+--  all other locations to the same thing as `ρ`". Note that the term
977+--  resulting from this reduction step is just `unit`; the interesting
978+--  result is the updated store.
979+--
980+--  Finally, to reduce an expression of the form `ref t₁`, we first reduce
981+--  `t₁` until it becomes a value:
982+--
983+--          t₁ / ρ ⟶ t₁' / ρ'
984+--      -------------------------- (ref)
985+--      ref t₁ / ρ ⟶ ref t₁' / ρ'
986+--
987+--  Then, to reduce the `ref` itself, we choose a fresh location at the end
988+--  of the current store — i.e., location `ρ.length` — and yield a new
989+--  store that extends `ρ` with the new value `v`.
990+--
991+--      -------------------------------- (refValue)
992+--      ref v / ρ ⟶ loc ρ.length / ρ, v
993+--
994+--  The value resulting from this step is the newly allocated location
995+--  itself. (Formally, `ρ, v` means `ρ.concat v` — i.e., to add a new
996+--  reference cell to the store, we append it to the end.)
997+--
998+--  Note that these reduction rules do not perform any kind of garbage
999+--  collection: we simply allow the store to keep growing without bound as
1000+--  reduction proceeds. This does not affect the correctness of the results
1001+--  of reduction (after all, the definition of "garbage" is precisely parts
1002+--  of the store that are no longer reachable and so cannot play any
1003+--  further role in reduction), but it means that a naive implementation of
1004+--  our evaluator might run out of memory where a more sophisticated
1005+--  evaluator would be able to continue by reusing locations whose contents
1006+--  have become garbage.
1007+--
1008+--  Here are the rules again, formally:
1009+
1010+section
1011+set_option hygiene false in
1012+local notation:40
1013+  t:71 " / " ρ:41 " ⟶ " t':71 " / " ρ':41 =>
1014+  Step (t, ρ) (t', ρ')
1015+
1016+inductive Step : Tm × Store → Tm × Store → Prop where
1017+  -- pure STLC
1018+  | appAbs {x : String} {τ₂ : Ty} {t₁ v₂ : Tm} {ρ : Store}
1019+      (h : v₂.IsValue) :
1020+      <{(λ x : τ₂ . t₁) v₂}> / ρ ⟶
1021+      <{ [x := v₂] t₁ }> / ρ
1022+  | app₁ {t₁ t₁' t₂ : Tm} {ρ ρ' : Store}
1023+      (h : t₁ / ρ ⟶ t₁' / ρ') :
1024+      <{t₁ t₂}> / ρ ⟶ <{t₁' t₂}> / ρ'
1025+  | app₂ {v₁ t₂ t₂' : Tm} {ρ ρ' : Store}
1026+      (h₁ : v₁.IsValue)
1027+      (h₂ : t₂ / ρ ⟶ t₂' / ρ') :
1028+      <{v₁ t₂}> / ρ ⟶ <{v₁ t₂'}> / ρ'
1029+  -- numbers
1030+  | succNat {n : Nat} {ρ : Store} :
1031+      <{ succ ~(Tm.const n) }> / ρ ⟶ Tm.const (n + 1) / ρ
1032+  | succ {t₁ t₁' : Tm} {ρ ρ' : Store}
1033+      (h : t₁ / ρ ⟶ t₁' / ρ') :
1034+      <{ succ t₁ }> / ρ ⟶ <{ succ t₁' }> / ρ'
1035+  | predConst {n : Nat} {ρ : Store} :
1036+      <{ pred ~(Tm.const n) }> / ρ ⟶ Tm.const (n - 1) / ρ
1037+  | pred {t₁ t₁' : Tm} {ρ ρ' : Store}
1038+      (h : t₁ / ρ ⟶ t₁' / ρ') :
1039+      <{ pred t₁ }> / ρ ⟶ <{ pred t₁' }> / ρ'
1040+  | multConst {n₁ n₂ : Nat} {ρ : Store} :
1041+      <{ ~(Tm.const n₁) * ~(Tm.const n₂) }> / ρ ⟶
1042+      Tm.const (n₁ * n₂) / ρ
1043+  | mult₁ {t₁ t₁' t₂ : Tm} {ρ ρ' : Store}
1044+      (h : t₁ / ρ ⟶ t₁' / ρ') :
1045+      <{ t₁ * t₂ }> / ρ ⟶ <{ t₁' * t₂ }> / ρ'
1046+  | mult₂ {v₁ t₂ t₂' : Tm} {ρ ρ' : Store}
1047+      (h₁ : v₁.IsValue)
1048+      (h₂ : t₂ / ρ ⟶ t₂' / ρ') :
1049+      <{ v₁ * t₂ }> / ρ ⟶ <{ v₁ * t₂' }> / ρ'
1050+  | if0Step {t₁ t₁' t₂ t₃ : Tm} {ρ ρ' : Store}
1051+      (h : t₁ / ρ ⟶ t₁' / ρ') :
1052+      <{ if0 t₁ then t₂ else t₃ }> / ρ ⟶
1053+      <{ if0 t₁' then t₂ else t₃ }> / ρ'
1054+  | if0Zero {t₂ t₃ : Tm} {ρ : Store} :
1055+      <{ if0 0 then t₂ else t₃ }> / ρ ⟶ t₂ / ρ
1056+  | if0Nonzero {n : Nat} {t₂ t₃ : Tm} {ρ : Store} :
1057+      <{ if0 ~(Tm.const (n + 1)) then t₂ else t₃ }> / ρ ⟶
1058+      t₃ / ρ
1059+  -- references
1060+  | refValue {v : Tm} {ρ : Store}
1061+      (h : v.IsValue) :
1062+      <{ ref v }> / ρ ⟶ Tm.loc ρ.length / ρ.concat v
1063+  | ref_ {t₁ t₁' : Tm} {ρ ρ' : Store}
1064+      (h : t₁ / ρ ⟶ t₁' / ρ') :
1065+      <{ ref t₁ }> / ρ ⟶ <{ ref t₁' }> / ρ'
1066+  | derefLoc {l : Nat} {ρ : Store}
1067+      (h : l < ρ.length) :
1068+      <{ !~(Tm.loc l) }> / ρ ⟶ ρ[l] / ρ
1069+  | deref {t₁ t₁' : Tm} {ρ ρ' : Store}
1070+      (h : t₁ / ρ ⟶ t₁' / ρ') :
1071+      <{ !t₁ }> / ρ ⟶ <{ !t₁' }> / ρ'
1072+  | assign {v : Tm} {l : Nat} {ρ : Store}
1073+      (h₁ : v.IsValue)
1074+      (h₂ : l < ρ.length) :
1075+      <{ ~(Tm.loc l) := v }> / ρ ⟶ <{ unit }> / ρ.set l v
1076+  | assign₁ {t₁ t₁' t₂ : Tm} {ρ ρ' : Store}
1077+      (h : t₁ / ρ ⟶ t₁' / ρ') :
1078+      <{ t₁ := t₂ }> / ρ ⟶ <{ t₁' := t₂ }> / ρ'
1079+  | assign₂ {v₁ t₂ t₂' : Tm} {ρ ρ' : Store}
1080+      (h₁ : v₁.IsValue)
1081+      (h₂ : t₂ / ρ ⟶ t₂' / ρ') :
1082+      <{ v₁ := t₂ }> / ρ ⟶ <{ v₁ := t₂' }> / ρ'
1083+end
1084+
1085+scoped notation:40
1086+  t:71 " / " ρ:41 " ⟶ " t':71 " / " ρ':41 =>
1087+  Step (t, ρ) (t', ρ')
1088+scoped notation:40
1089+  t:71 " / " ρ:41 " ⟶* " t':71 " / " ρ':41 =>
1090+  Multi Step (t, ρ) (t', ρ')
1091+
1092+attribute [StlcRefEval] Step.appAbs Step.app₁ Step.app₂
1093+    Step.succ Step.succNat Step.pred Step.predConst
1094+    Step.multConst Step.mult₁ Step.mult₂
1095+    Step.if0Step Step.if0Zero Step.if0Nonzero
1096+    Step.refValue Step.ref_ Step.derefLoc Step.deref Step.assign
1097+    Step.assign₁ Step.assign₂
1098+
1099+--  ## Typing
1100+
1101+--  The contexts assigning types to free variables are exactly the same as
1102+--  for the STLC: partial maps from identifiers to types.
1103+
1104+abbrev Context := PartialMap String Ty
1105+
1106+--  ### Store typings
1107+
1108+--  Having extended our syntax and reduction rules to accommodate
1109+--  references, our last job is to write down typing rules for the new
1110+--  constructs (and, of course, to check that these rules are sound!).
1111+--
1112+--  Naturally, the key question is, "What is the type of a location?"
1113+--
1114+--  First of all, notice that this question doesn't arise when typechecking
1115+--  terms that programmers actually write. Concrete location constants
1116+--  arise only in terms that are the intermediate results of reduction;
1117+--  they are not in the language that programmers write. So we only need to
1118+--  determine the type of a location when we're in the middle of a
1119+--  reduction sequence, e.g., trying to apply the progress or preservation
1120+--  lemmas. Thus, even though we normally think of typing as a *static*
1121+--  program property, it makes sense for the typing of locations to depend
1122+--  on the *dynamic* progress of the program too.
1123+--
1124+--  As a first try, note that when we reduce a term containing concrete
1125+--  locations, the type of the result depends on the contents of the store
1126+--  that we start with. For example, if we reduce the term `!(loc 1)` in
1127+--  the store `unit, unit`, the result is `unit`; if we reduce the same
1128+--  term in the store `unit, λX:Unit.X`, the result is `λX:Unit.X`. With
1129+--  respect to the former store, the location `1` has type `Unit`, and with
1130+--  respect to the latter it has type `Unit→Unit`. This observation leads
1131+--  us immediately to a first attempt at a typing rule for locations:
1132+--
1133+--       Γ ⊢ ρ[l] : τ₁
1134+--      ------------------
1135+--      Γ ⊢ loc l : Ref τ₁
1136+--
1137+--  But where does `ρ` come from?
1138+--
1139+--  That is, to find the type of a location `l`, we look up the current
1140+--  contents of `l` in the store and calculate the type `τ₁` of the
1141+--  contents. The type of the location is then `Ref τ₁`.
1142+--
1143+--  Having begun in this way, we need to go a little further to reach a
1144+--  consistent state. In effect, by making the type of a term depend on the
1145+--  store, we have changed the typing relation from a three-place relation
1146+--  (between contexts, terms, and types) to a four-place relation (between
1147+--  contexts, *stores*, terms, and types). Since the store is, intuitively,
1148+--  part of the context in which we calculate the type of a term, let's
1149+--  write this four-place relation with the store to the left of the
1150+--  turnstile: `Γ; ρ ⊢ t : τ`. Our rule for typing references now has the
1151+--  form
1152+--
1153+--       Γ; ρ ⊢ ρ[l] : τ₁
1154+--      ---------------------
1155+--      Γ; ρ ⊢ loc l : Ref τ₁
1156+--
1157+--  and all the rest of the typing rules in the system are extended
1158+--  similarly with stores. (The other rules do not need to do anything
1159+--  interesting with their stores — just pass them from premise to
1160+--  conclusion.)
1161+--
1162+--  However, this rule will not quite do. For one thing, typechecking is
1163+--  rather inefficient, since calculating the type of a location `l`
1164+--  involves calculating the type of the current contents `v` of `l`. If
1165+--  `l` appears many times in a term `τ`, we will re-calculate the type of
1166+--  `v` many times in the course of constructing a typing derivation for
1167+--  `τ`. Worse, if `v` itself contains locations, then we will have to
1168+--  recalculate *their* types each time they appear. Worse yet, the
1169+--  proposed typing rule for locations may not allow us to derive anything
1170+--  at all if the store contains a *cycle*. For example, there is no finite
1171+--  typing derivation for the location `0` with respect to this store:
1172+
1173+--  λX:Nat. (!(loc 1)) X, λX:Nat. (!(loc 0)) X
1174+
1175+--  ### Exercise (3 stars): cyclic_store ⭐⭐⭐
1176+
1177+--  Can you find a term whose reduction will create this particular cyclic
1178+--  store?
1179+
1180+theorem cyclic_store:
1181+  ∃ t,
1182+    t / [] ⟶*
1183+    <{ unit }> / (<{ λX:Nat. (!(loc 1)) X }> :: <{ λX:Nat. (!(loc 0)) X }> :: []) := by
1184+  exists <{
1185+    (λR₀ : Ref (Nat → Nat).
1186+      (λR₁ : Ref (Nat → Nat).
1187+        R₀ := (λX:Nat. (!R₁) X))
1188+      (ref (λX:Nat. (!R₀) X)))
1189+    (ref (λX:Nat. X)) }>
1190+  repeat
1191+    apply Multi.step
1192+    solve_by_elim using StlcRefEval
1193+  apply Multi.refl
1194+
1195+--  (End of exercise)
1196+
1197+--  These problems arise from the fact that our proposed typing rule for
1198+--  locations requires us to recalculate the type of a location every time
1199+--  we mention it in a term. But this, intuitively, should not be
1200+--  necessary. After all, when a location is first created, we know the
1201+--  type of the initial value that we are storing into it. Suppose we are
1202+--  willing to enforce the invariant that the type of the value contained
1203+--  in a given location *never changes*; that is, although we may later
1204+--  store other values into this location, those other values will always
1205+--  have the same type as the initial one. In other words, we always have
1206+--  in mind a single, definite type for every location in the store, which
1207+--  is fixed when the location is allocated. Then these intended types can
1208+--  be collected together as a *store typing* — a finite function mapping
1209+--  locations to types.
1210+--
1211+--  As with the other type systems we've seen, this conservative typing
1212+--  restriction on allowed updates means that we will rule out as ill-typed
1213+--  some programs that could reduce perfectly well without getting stuck.
1214+--
1215+--  Just as we did for stores, we will represent a store type simply as a
1216+--  list of types: the type at index `i` records the type of the values
1217+--  that we expect to be stored in cell `i`.
1218+
1219+abbrev StoreTy := List Ty
1220+
1221+open scoped MyGetElem
1222+instance : MyGetElem StoreTy Nat Ty where
1223+  getElem δ n := δ.getD n <{Unit}>
1224+
1225+@[simp]
1226+theorem StoreTy_get_succ_tl (hd : Ty) (tl : StoreTy) (n : Nat) :
1227+  (hd :: tl)[n + 1] = tl[n] := by rfl
1228+@[simp]
1229+theorem StoreTy_get_zero_hd (hd : Ty) (tl : StoreTy) :
1230+  (hd :: tl)[0] = hd := by rfl
1231+
1232+--  Suppose we are given a store typing `δ` describing the store `ρ` in
1233+--  which some term `τ` will be reduced. Then we can use `δ` to calculate
1234+--  the type of the result of `τ` without ever looking directly at `ρ`. For
1235+--  example, if `δ` is `Unit, Unit→Unit`, then we can immediately infer
1236+--  that `!(loc 1)` has type `Unit→Unit`. More generally, the typing rule
1237+--  for locations can be reformulated in terms of store typings like this:
1238+--
1239+--           l < δ.length
1240+--      -----------------------
1241+--      Γ; δ ⊢ loc l : Ref δ[l]
1242+--
1243+--  That is, as long as `l` is a valid location, we can compute the type of
1244+--  `l` just by looking it up in `δ`. Typing is again a four-place
1245+--  relation, but it is parameterized on a store *typing* rather than a
1246+--  concrete store. The rest of the typing rules are analogously augmented
1247+--  with store typings.
1248+
1249+--  ### The Typing Relation
1250+
1251+--  We can now formalize the typing relation for the STLC with references.
1252+--  Here, again, are the rules we're adding to the base STLC (with numbers
1253+--  and `Unit`):
1254+--
1255+--           l < δ.length
1256+--      -----------------------  (loc)
1257+--      Γ; δ ⊢ loc l : Ref δ[l]
1258+--
1259+--          Γ; δ ⊢ t₁ : τ₁
1260+--      ----------------------   (ref)
1261+--      Γ; δ ⊢ ref t₁ : Ref τ₁
1262+--
1263+--        Γ; δ ⊢ t₁ : Ref τ₁
1264+--        ------------------     (deref)
1265+--        Γ; δ ⊢ !t₁ : τ₁
1266+--
1267+--        Γ; δ ⊢ t₁ : Ref τ₂
1268+--          Γ; δ ⊢ t₂ : τ₂
1269+--      ----------------------   (assign)
1270+--      Γ; δ ⊢ t₁ := t₂ : Unit
1271+
1272+inductive HasType (δ : StoreTy) : Context → Tm → Ty → Prop where
1273+  -- pure STLC
1274+  | var {Γ : Context} {x : String} {τ₁ : Ty}
1275+      (h : Γ[x] = some τ₁) :
1276+      <{ Γ / δ ⊢ ~(Tm.var x) ⦂ τ₁ }>
1277+  | abs {Γ : Context} {x : String} {τ₁ τ₂ : Ty} {t₁ : Tm}
1278+      (h : <{ x ↦ τ₂ ; Γ / δ ⊢ t₁ ⦂ τ₁ }>) :
1279+      <{ Γ / δ ⊢ λ x : τ₂ . t₁ ⦂ τ₂ → τ₁ }>
1280+  | app {Γ : Context} {τ₁ τ₂ : Ty} {t₁ t₂ : Tm}
1281+      (h₁ : <{ Γ / δ ⊢ t₁ ⦂ τ₂ → τ₁ }>)
1282+      (h₂ : <{ Γ / δ ⊢ t₂ ⦂ τ₂ }>) :
1283+      <{ Γ / δ ⊢ t₁ t₂ ⦂ τ₁ }>
1284+  -- numbers
1285+  | const {Γ : Context} {n : Nat} :
1286+      <{ Γ / δ ⊢ ~(Tm.const n) ⦂ Nat }>
1287+  | succ {Γ : Context} {t₁ : Tm}
1288+      (h : <{ Γ / δ ⊢ t₁ ⦂ Nat }>) :
1289+      <{ Γ / δ ⊢ succ t₁ ⦂ Nat }>
1290+  | pred {Γ : Context} {t₁ : Tm}
1291+      (h : <{ Γ / δ ⊢ t₁ ⦂ Nat }>) :
1292+      <{ Γ / δ ⊢ pred t₁ ⦂ Nat }>
1293+  | mult {Γ : Context} {t₁ t₂ : Tm}
1294+      (h₁ : <{ Γ / δ ⊢ t₁ ⦂ Nat }>)
1295+      (h₂ : <{ Γ / δ ⊢ t₂ ⦂ Nat }>) :
1296+      <{ Γ / δ ⊢ t₁ * t₂ ⦂ Nat }>
1297+  | ite0 {Γ : Context} {t₁ t₂ t₃ : Tm} {τ : Ty}
1298+      (h₁ : <{ Γ / δ ⊢ t₁ ⦂ Nat }>)
1299+      (h₂ : <{ Γ / δ ⊢ t₂ ⦂ τ }>)
1300+      (h₃ : <{ Γ / δ ⊢ t₃ ⦂ τ }>) :
1301+      <{ Γ / δ ⊢ if0 t₁ then t₂ else t₃ ⦂ τ }>
1302+  -- unit
1303+  | unit {Γ : Context} :
1304+      <{ Γ / δ ⊢ unit ⦂ Unit }>
1305+  -- references
1306+  | loc_ {Γ : Context} {l : Nat}
1307+      (h : l < δ.length) :
1308+      <{ Γ / δ ⊢ ~(Tm.loc l) ⦂ Ref ~(δ[l]) }>
1309+  | ref_ {Γ : Context} {t₁ : Tm} {τ₁ : Ty}
1310+      (h : <{ Γ / δ ⊢ t₁ ⦂ τ₁ }>) :
1311+      <{ Γ / δ ⊢ ref t₁ ⦂ Ref τ₁ }>
1312+  | deref {Γ : Context} {t₁ : Tm} {τ₁ : Ty}
1313+      (h : <{ Γ / δ ⊢ t₁ ⦂ Ref τ₁ }>) :
1314+      <{ Γ / δ ⊢ !t₁ ⦂ τ₁ }>
1315+  | assign {Γ : Context} {t₁ t₂ : Tm} {τ₂ : Ty}
1316+      (h₁ : <{ Γ / δ ⊢ t₁ ⦂ Ref τ₂ }>)
1317+      (h₂ : <{ Γ / δ ⊢ t₂ ⦂ τ₂ }>) :
1318+      <{ Γ / δ ⊢ t₁ := t₂ ⦂ Unit }>
1319+
1320+attribute [StlcRefTyping] HasType.var HasType.abs HasType.app
1321+    HasType.const HasType.succ HasType.pred HasType.mult
1322+    HasType.ite0 HasType.unit
1323+    HasType.loc_ HasType.ref_ HasType.deref HasType.assign
1324+
1325+--  THE FOLLOWING DETAILS CAN BE SKIPPED (Notation encoding)
1326+open Lean PrettyPrinter StlcCommon.Delab in
1327+@[app_unexpander HasType]
1328+def HasType.unexpand : Unexpander
1329+  | `($_ $δ $Γ $t $T) => do
1330+      let Γ' ← unexpandCtx Γ
1331+      `(<{ $Γ':stlcCtx / $δ ⊢ $(getTm t):stlcTm ⦂ $(getTy T):stlcTy }>)
1332+  | _ => throw ()
1333+--  END DETAILS
1334+
1335+--  Of course, these typing rules will accurately predict the results of
1336+--  reduction only if the concrete store used during reduction actually
1337+--  conforms to the store typing that we assume for purposes of
1338+--  typechecking. This proviso exactly parallels the situation with free
1339+--  variables in the basic STLC: the substitution lemma promises that, if
1340+--  `Γ / δ ⊢ t : T`, then we can replace the free variables in `τ` with
1341+--  values of the types listed in `Γ` to obtain a closed term of type `τ`,
1342+--  which, by the type preservation theorem will reduce to a final result
1343+--  of type `τ` if it yields any result at all. We will see below how to
1344+--  formalize an analogous intuition for stores and store typings.
1345+--
1346+--  However, for purposes of typechecking the terms that programmers
1347+--  actually write, we do not need to do anything tricky to guess what
1348+--  store typing we should use. Concrete locations arise only in terms that
1349+--  are the intermediate results of reduction; they are not in the language
1350+--  that programmers write. Thus, we can simply typecheck the programmer's
1351+--  terms with respect to the *empty* store typing. As reduction proceeds
1352+--  and new locations are created, we will always be able to see how to
1353+--  extend the store typing by looking at the type of the initial values
1354+--  being placed in newly allocated cells; this intuition is formalized in
1355+--  the statement of the type preservation theorem below.
1356+
1357+--  ## Properties
1358+
1359+--  Our final task is to check that standard type safety properties
1360+--  continue to hold for the STLC with references. The progress theorem
1361+--  ("well-typed terms are not stuck") can be stated and proved almost as
1362+--  for the STLC; we just need to add a few straightforward cases to the
1363+--  proof to deal with the new constructs. The preservation theorem is a
1364+--  bit more interesting, so let's look at it first.
1365+
1366+--  ### Well-Typed Stores
1367+
1368+--  Since we have extended both the reduction relation (with initial and
1369+--  final stores) and the typing relation (with a store typing), we need to
1370+--  change the statement of preservation to include these parameters. But
1371+--  clearly we cannot just add stores and store typings without saying
1372+--  anything about how they are related — i.e., this is wrong:
1373+
1374+sf_expect_failure_in
1375+  theorem preservation_wrong (δ : StoreTy) (τ : Ty) (t t' : Tm) (ρ ρ' : Store) :
1376+      <{ ∅ / δ ⊢ t ⦂ τ }> →
1377+      t / ρ ⟶ t' / ρ' →
1378+      <{ ∅ / δ ⊢ t' ⦂ τ }> := by
1379+
1380+--  If we typecheck with respect to some set of assumptions about the types
1381+--  of the values in the store and then reduce with respect to a store that
1382+--  violates these assumptions, the result will be disaster. We say that a
1383+--  store `ρ` is *well typed* with respect to a store typing `δ` if the
1384+--  term at each location `l` in `ρ` has the type at location `l` in `δ`.
1385+--  Since only closed terms ever get stored in locations (why?), it
1386+--  suffices to type them in the empty context. The following definition of
1387+--  `StoreWellTyped` formalizes this:
1388+
1389+def StoreWellTyped (δ:StoreTy) (ρ:Store) :=
1390+  δ.length = ρ.length ∧
1391+  (∀ (l : Nat), l < ρ.length → <{ ∅ / δ ⊢ ~(ρ[l]) ⦂ ~(δ[l]) }>)
1392+
1393+--  Informally, we will write `δ ⊢ ρ` for `StoreWellTyped δ ρ`.
1394+
1395+scoped notation:40 δ:41 " ⊢ " ρ:41 => StoreWellTyped δ ρ
1396+
1397+--  Intuitively, a store `ρ` is consistent with a store typing `δ` if every
1398+--  value in the store has the type predicted by the store typing. The only
1399+--  subtle point is the fact that, when typing the values in the store, we
1400+--  supply the very same store typing to the typing relation. This allows
1401+--  us to type circular stores like the one we saw above.
1402+
1403+--  ### Exercise (3 stars): store_not_unique ⭐⭐⭐
1404+
1405+--  Can you find a store `ρ`, and two different store typings `δ₁` and `δ₂`
1406+--  such that both `δ₁ ⊢ ρ` and `δ₂ ⊢ ρ`?
1407+
1408+--  Let `ρ` be a store with a single location `0`, such that `ρ` =
1409+--  `λX:Unit. (!(loc 0))(X)`. Then `ρ` is well typed with respect to both
1410+--  of the following store typings: δ₁ = `Unit → Unit` δ₂ =
1411+--  `Unit → (Unit→Unit)`. In fact, it is well typed with respect to any
1412+--  store typing of the form δ = `Unit → τ` for any type `τ`.
1413+
1414+theorem store_not_unique:
1415+  exists ρ, exists δ₁, exists δ₂,
1416+    δ₁ ⊢ ρ ∧ δ₂ ⊢ ρ ∧ δ₁ ≠ δ₂ := by
1417+  exists (<{ λX:Unit. (!(loc 0)) X }> :: []);
1418+  exists (<{ Unit → Unit }> :: []);
1419+  exists (<{ Unit → Nat }> :: []);
1420+  constructor
1421+  · simp [StoreWellTyped]
1422+    apply_rules using StlcRefTyping
1423+    simp
1424+  · constructor
1425+    · simp [StoreWellTyped]
1426+      apply_rules using StlcRefTyping
1427+      simp
1428+    · simp
1429+
1430+--  (End of exercise)
1431+
1432+--  We can now state something closer to the desired preservation property:
1433+
1434+sf_expect_failure_in
1435+  theorem preservation_less_wrong (δ : StoreTy) (τ : Ty) (t t' : Tm) (ρ ρ' : Store) :
1436+    <{ ∅ / δ ⊢ t ⦂ τ }> →
1437+    t / ρ ⟶ t' / ρ' →
1438+    δ ⊢ ρ →
1439+    <{ ∅ / δ ⊢ t' ⦂ τ }> := by
1440+
1441+--  This statement is fine for all of the reduction rules except the
1442+--  allocation rule `refValue`. The problem is that this rule yields a
1443+--  store with a larger domain than the initial store, which falsifies the
1444+--  conclusion of the above statement: if `ρ'` includes a binding for a
1445+--  fresh location `l`, then `l` cannot be in the domain of `δ`, and it
1446+--  will not be the case that `t'` (which definitely mentions `l`) is
1447+--  typable under `δ`.
1448+
1449+--  ### Extending Store Typings
1450+
1451+--  Evidently, since the store can increase in size during reduction, we
1452+--  need to allow the store *typing* to grow during reduction as well. This
1453+--  motivates the following definition. We say that the store type `δ'`
1454+--  *extends* `δ` if `δ'` is just `δ` with some new types added to the end.
1455+
1456+inductive Extends : StoreTy → StoreTy → Prop where
1457+  | nil (δ' : StoreTy) : Extends δ' []
1458+  | cons (τ : Ty) {δ' δ : StoreTy} (h : Extends δ' δ) :
1459+      Extends (τ::δ') (τ::δ)
1460+
1461+attribute [StlcRefTyping] Extends.nil Extends.cons
1462+
1463+--  For example, the store typing `[Nat]` with a single location of type
1464+--  `Nat` extends the empty store typing.
1465+--
1466+--  We'll need a few technical lemmas about extended contexts. First,
1467+--  looking up a type in an extended store typing yields the same result as
1468+--  in the original:
1469+
1470+theorem extends_lookup {l : Nat} {δ δ' : StoreTy}
1471+  (h₁ : l < δ.length)
1472+  (h₂ : Extends δ' δ) :
1473+  δ'[l] = δ[l] := by
1474+
1475+    induction δ generalizing l δ' with
1476+    | nil => simp_all
1477+    | cons hd tl ih =>
1478+      cases δ' with
1479+      | nil => inversion h₂
1480+      | cons hd' tl' =>
1481+        inversion h₂
1482+        cases l with
1483+        | zero => rfl
1484+        | succ l =>
1485+          simp only [StoreTy_get_succ_tl]; apply ih
1486+          · simp_all
1487+          · assumption
1488+
1489+--  Next, if `δ'` extends `δ`, the length of `δ'` is at least that of `δ`.
1490+
1491+theorem length_extends {l : Nat} {δ δ' : StoreTy}
1492+  (h₁ : l < δ.length)
1493+  (h₂ : Extends δ' δ) :
1494+  l < δ'.length := by
1495+    induction h₂ generalizing l with
1496+    | nil => simp_all
1497+    | cons τ h ih =>
1498+        simp only [List.length_cons]
1499+        cases l with
1500+        | zero => lia
1501+        | succ l' =>
1502+          apply Nat.succ_lt_succ; apply ih
1503+          simp_all
1504+
1505+--  Finally, `δ ++ δ'` extends `δ`, and `Extends` is reflexive.
1506+
1507+theorem extends_app (δ δ' : StoreTy) : Extends (δ ++ δ') δ := by
1508+  induction δ generalizing δ' <;> apply_rules using StlcRefTyping
1509+
1510+theorem extends_refl (δ : StoreTy) : Extends δ δ := by
1511+  induction δ <;> apply_rules using StlcRefTyping
1512+
1513+--  ### Preservation, Finally
1514+
1515+--  We can now give the final, correct statement of the type preservation
1516+--  property:
1517+
1518+def preservation_theorem {δ : StoreTy} {t t' : Tm} {τ : Ty} {ρ ρ' : Store} :=
1519+  (hTy : <{ ∅ / δ ⊢ t ⦂ τ }>) →
1520+  (hStoreTy : δ ⊢ ρ) →
1521+  (hEval : t / ρ ⟶ t' / ρ') →
1522+    ∃ δ', Extends δ' δ ∧ (<{ ∅ / δ' ⊢ t' ⦂ τ }>) ∧ (δ' ⊢ ρ')
1523+
1524+--  Note that the preservation theorem merely asserts that there is *some*
1525+--  store typing `δ'` extending `δ` (i.e., agreeing with `δ` on the values
1526+--  of all the old locations) such that the new term `t'` is well typed
1527+--  with respect to `δ'`; it does not tell us exactly what `δ'` is. It is
1528+--  intuitively clear, of course, that `δ'` is either `δ` or else exactly
1529+--  `δ ++ [τ₁]`, where `τ₁` is the type of the value `v₁` in the extended
1530+--  store `ρ ++ [v₁]`, but stating this explicitly would complicate the
1531+--  statement of the theorem without making it any more useful: the weaker
1532+--  version above is already in the right form (because its conclusion
1533+--  implies its hypothesis) to "turn the crank" repeatedly and conclude
1534+--  that every *sequence* of reduction steps preserves well-typedness.
1535+--  Combining this with the progress property, we obtain the usual
1536+--  guarantee that "well-typed programs never go wrong."
1537+--
1538+--  In order to prove this, we'll need a few lemmas, as usual.
1539+
1540+--  #### Substitution Lemma
1541+
1542+--  First, we need an easy extension of the standard substitution lemma,
1543+--  along with the same machinery about context invariance that we used in
1544+--  the proof of the substitution lemma for the STLC.
1545+
1546+theorem weakening {Γ Γ' : Context} {δ : StoreTy} {t : Tm} {τ: Ty}
1547+    (hi : Γ ⊆ Γ')
1548+    (ht : <{ Γ / δ ⊢ t ⦂ τ }>) :
1549+     <{ Γ' / δ ⊢ t ⦂ τ }> := by
1550+  induction ht generalizing Γ' with (apply_rules [PartialMap.update_subset] using StlcRefTyping)
1551+
1552+theorem weakening_empty {Γ : Context} {δ : StoreTy} {t : Tm} {τ: Ty}
1553+    (ht :<{ ∅ / δ ⊢ t ⦂ τ }>) :
1554+    <{ Γ / δ ⊢ t ⦂ τ }> := by
1555+  apply weakening _ ht
1556+  intro _ _ h
1557+  rw [PartialMap.getElem_empty] at h
1558+  contradiction
1559+
1560+theorem substitution_preserves_typing (Γ : Context) (δ : StoreTy) (x : String)
1561+    (τ₁ : Ty) (t v : Tm) (τ : Ty)
1562+    (ht : <{ x ↦ τ₁ ; Γ / δ⊢ t ⦂ τ }>)
1563+    (hv : <{ ∅ / δ ⊢ v ⦂ τ₁ }>) :
1564+    <{ Γ / δ ⊢ [x := v] t ⦂ τ }> := by
1565+  induction t generalizing Γ τ with (
1566+    rw [subst]; try (inversion ht; apply_rules using StlcRefTyping; done))
1567+    | var y =>
1568+        inversion ht with | _ h =>
1569+        by_cases h₁ : x = y
1570+        · subst h₁; simp at h; subst h;
1571+          apply weakening_empty at hv
1572+          simp; assumption
1573+        · rw [PartialMap.update_neq] at h <;> simp_all
1574+          apply_rules using StlcRefTyping
1575+    | abs y _ _ ih =>
1576+        inversion ht with | _ h =>
1577+        by_cases h₁ : x = y
1578+        · simp_all [PartialMap.update_shadow]; apply_rules using StlcRefTyping
1579+        · rw [PartialMap.update_permute] at h
1580+          · simp_all; apply_rules using StlcRefTyping
1581+          · lia
1582+
1583+--  #### Assignment Preserves Store Typing
1584+
1585+--  Next, we must show that replacing the contents of a cell in the store
1586+--  with a new value of appropriate type does not change the overall type
1587+--  of the store. (This is needed for the `assign` rule.)
1588+
1589+theorem assign_pres_store_typing {δ : StoreTy} {ρ : Store} {l : Nat} {t : Tm}
1590+  (hLen : l < ρ.length)
1591+  (hStoreTy : δ ⊢ ρ)
1592+  (hTy : <{ ∅ / δ ⊢ t ⦂ ~(δ[l]) }>) :
1593+  δ ⊢ ρ.set l t := by
1594+    have ⟨h₁, h₂⟩ := hStoreTy
1595+    constructor
1596+    · simp_all [List.length_set]
1597+    · intro l' hLen'
1598+      by_cases h₁ : l' = l
1599+      · subst_vars
1600+        rw [Store_get_set_eq] <;> assumption
1601+      · rw [Store_get_set_neq] <;> try assumption
1602+        apply h₂
1603+        simp_all [List.length_set]
1604+
1605+--  #### Weakening for Stores
1606+
1607+--  Finally, we need a lemma on store typings, stating that, if a store
1608+--  typing is extended with a new location, the extended one still allows
1609+--  us to assign the same types to the same terms as the original.
1610+
1611+theorem store_weakening {Γ : Context} {δ δ' : StoreTy} {t : Tm} {τ : Ty}
1612+  (hExt : Extends δ' δ)
1613+  (hTy : <{ Γ / δ ⊢ t ⦂ τ }>) :
1614+  <{ Γ / δ' ⊢ t ⦂ τ }> := by
1615+    induction hTy with (try (apply_rules using StlcRefTyping; done))
1616+    | loc_ h =>
1617+        rw [←extends_lookup] <;> try assumption
1618+        apply HasType.loc_
1619+        apply length_extends <;> assumption
1620+
1621+--  We can use the `store_weakening` lemma to prove that if a store is well
1622+--  typed with respect to a store typing, then the store extended with a
1623+--  new term `τ` will still be well typed with respect to the store typing
1624+--  extended with `τ`'s type.
1625+
1626+theorem store_well_typed_app {δ : StoreTy} {ρ : Store} {t₁ : Tm} {τ₁ : Ty}
1627+  (hStoreTy : δ ⊢ ρ)
1628+  (hTy : <{ ∅ / δ ⊢ t₁ ⦂ τ₁ }>) :
1629+  (δ.concat τ₁) ⊢ (ρ.concat t₁) := by
1630+    have ⟨h₁, h₂⟩ := hStoreTy
1631+    simp_all only [List.concat_eq_append]
1632+    constructor
1633+    · simp_all
1634+    · simp_all only [List.length_append, List.length_cons, List.length_nil, Nat.zero_add]
1635+      intro l hl
1636+      inversion hl with
1637+      | refl =>
1638+          apply store_weakening <;> try assumption
1639+          apply extends_app
1640+          simp_all [MyGetElem.getElem]
1641+      | step hl =>
1642+          apply store_weakening <;> try assumption
1643+          · apply extends_app
1644+          · have hl' : l < ρ.length := by lia
1645+            simp_all [MyGetElem.getElem, List.getElem?_append_left]
1646+
1647+--  #### Preservation!
1648+
1649+--  Now that we've got everything set up right, the proof of preservation
1650+--  is actually quite straightforward:
1651+
1652+theorem preservation {δ : StoreTy} {t t' : Tm} {τ : Ty} {ρ ρ' : Store}
1653+  (hTy : <{ ∅ / δ ⊢ t ⦂ τ }>)
1654+  (hStoreTy : δ ⊢ ρ)
1655+  (hEval : t / ρ ⟶ t' / ρ') :
1656+    ∃ δ', Extends δ' δ ∧ (<{ ∅ / δ' ⊢ t' ⦂ τ }>) ∧ (δ' ⊢ ρ') := by
1657+
1658+    generalize heq : (∅ : Context) = Γ at hTy
1659+    -- discharge the goals where `t` doesn't step
1660+    induction hTy generalizing t' with (subst_vars; try (inversion hEval; done))
1661+    | app h₁ h₂ ih₁ ih₂ =>
1662+      inversion hEval with
1663+      | appAbs =>
1664+        inversion h₁ with | abs h =>
1665+        exists δ; constructor
1666+        apply extends_refl; constructor
1667+        apply_rules [substitution_preserves_typing, extends_refl] using StlcRefTyping
1668+        assumption
1669+      | app₁ hs =>
1670+        have ⟨δ', hExt, hTy', hStoreTy'⟩ := ih₁ hs rfl
1671+        exists δ'; constructor
1672+        assumption; constructor
1673+        solve_by_elim [store_weakening] using StlcRefTyping
1674+        assumption
1675+      | app₂ _ hs =>
1676+        have ⟨δ', hExt, hTy', hStoreTy'⟩ := ih₂ hs rfl
1677+        exists δ'; constructor
1678+        assumption; constructor
1679+        solve_by_elim [store_weakening] using StlcRefTyping
1680+        assumption
1681+    | succ _ ih =>
1682+      inversion hEval with
1683+      | succNat =>
1684+        exists δ; constructor
1685+        apply extends_refl; constructor
1686+        constructor
1687+        assumption
1688+      | succ hs =>
1689+        have ⟨δ', hExt, hTy', hStoreTy'⟩ := ih hs rfl
1690+        exists δ'; constructor
1691+        assumption; constructor
1692+        solve_by_elim [store_weakening] using StlcRefTyping
1693+        assumption
1694+    | pred _ ih =>
1695+      inversion hEval with
1696+      | predConst =>
1697+        exists δ; constructor
1698+        apply extends_refl; constructor
1699+        constructor
1700+        assumption
1701+      | pred hs =>
1702+        have ⟨δ', hExt, hTy', hStoreTy'⟩ := ih hs rfl
1703+        exists δ'; constructor
1704+        assumption; constructor
1705+        solve_by_elim [store_weakening] using StlcRefTyping
1706+        assumption
1707+    | mult h₁ h₂ ih₁ ih₂ =>
1708+      inversion hEval with
1709+      | multConst =>
1710+        exists δ; constructor
1711+        apply extends_refl; constructor
1712+        constructor
1713+        assumption
1714+      | mult₁ hs =>
1715+        have ⟨δ', hExt, hTy', hStoreTy'⟩ := ih₁ hs rfl
1716+        exists δ'; constructor
1717+        assumption; constructor
1718+        solve_by_elim [store_weakening] using StlcRefTyping
1719+        assumption
1720+      | mult₂ _ hs =>
1721+        have ⟨δ', hExt, hTy', hStoreTy'⟩ := ih₂ hs rfl
1722+        exists δ'; constructor
1723+        assumption; constructor
1724+        solve_by_elim [store_weakening] using StlcRefTyping
1725+        assumption
1726+    | ite0 _ h₂ h₃ ih₁ _ _ =>
1727+      inversion hEval with
1728+      | if0Step hs =>
1729+        have ⟨δ', hExt, hTy', hStoreTy'⟩ := ih₁ hs rfl
1730+        exists δ'; constructor
1731+        assumption; constructor
1732+        constructor <;> solve_by_elim [store_weakening] using StlcRefTyping
1733+        assumption
1734+      | if0Zero =>
1735+        exists δ; constructor
1736+        apply extends_refl; constructor <;> assumption
1737+      | if0Nonzero =>
1738+        exists δ; constructor
1739+        apply extends_refl; constructor <;> assumption
1740+    | @ref_ _ _ τ₁ h ih =>
1741+      inversion hEval with
1742+      | refValue =>
1743+        exists δ.concat τ₁; constructor
1744+        · rw [List.concat_eq_append]; apply extends_app
1745+        · constructor
1746+          · have h : <{Ref τ₁}> = <{Ref ~((δ.concat τ₁)[ρ.length])}> := by
1747+              simp_all [StoreWellTyped, MyGetElem.getElem]
1748+            rw [h]
1749+            constructor
1750+            simp [StoreWellTyped] at hStoreTy ⊢; lia
1751+          · apply store_well_typed_app <;> assumption
1752+      | ref_ hs =>
1753+        have ⟨δ', hExt, hTy', hStoreTy'⟩ := ih hs rfl
1754+        exists δ'; constructor
1755+        assumption; constructor
1756+        solve_by_elim [store_weakening] using StlcRefTyping
1757+        assumption
1758+    | deref h ih =>
1759+      inversion hEval with
1760+      | derefLoc hl =>
1761+        inversion h
1762+        exists δ; constructor
1763+        apply extends_refl; constructor
1764+        have ⟨h₁, h₂⟩ := hStoreTy
1765+        apply h₂ <;> assumption
1766+        assumption
1767+      | deref hs =>
1768+        have ⟨δ', hExt, hTy', hStoreTy'⟩ := ih hs rfl
1769+        exists δ'; constructor
1770+        assumption; constructor
1771+        solve_by_elim [store_weakening] using StlcRefTyping
1772+        assumption
1773+    | assign h₁ h₂ ih₁ ih₂ =>
1774+      inversion hEval with
1775+      | assign _ hl =>
1776+        inversion h₁
1777+        exists δ; constructor
1778+        apply extends_refl; constructor
1779+        constructor
1780+        apply assign_pres_store_typing <;> assumption
1781+      | assign₁ hs =>
1782+        have ⟨δ', hExt, hTy', hStoreTy'⟩ := ih₁ hs rfl
1783+        exists δ'; constructor
1784+        assumption; constructor
1785+        solve_by_elim [store_weakening] using StlcRefTyping
1786+        assumption
1787+      | assign₂ _ hs =>
1788+        have ⟨δ', hExt, hTy', hStoreTy'⟩ := ih₂ hs rfl
1789+        exists δ'; constructor
1790+        assumption; constructor
1791+        solve_by_elim [store_weakening] using StlcRefTyping
1792+        assumption
1793+
1794+--  This proof is pretty long, and many of the cases repeat themselves.
1795+--  With judicious use of automation, we can make it much shorter:
1796+
1797+theorem preservation_shorter {δ : StoreTy} {t t' : Tm} {τ : Ty} {ρ ρ' : Store}
1798+  (hTy : <{ ∅ / δ ⊢ t ⦂ τ }>)
1799+  (hStoreTy : δ ⊢ ρ)
1800+  (hEval : t / ρ ⟶ t' / ρ') :
1801+    ∃ δ', Extends δ' δ ∧ (<{ ∅ / δ' ⊢ t' ⦂ τ }>) ∧ (δ' ⊢ ρ') := by
1802+
1803+      generalize heq : (∅ : Context) = Γ at hTy
1804+      induction hTy generalizing t' with (
1805+        subst_vars <;>
1806+        -- discharge the goals where `t` doesn't step
1807+        inversion hEval <;>
1808+        -- handle the congruence cases where the store typing grows,
1809+        -- but in an uninteresting way
1810+        (try
1811+          -- we want to apply our inductive hypotheses, but we can't name
1812+          -- them in our automation. Instead, we restate the result that
1813+          -- we want and use `solve_by_elim` to figure out how to prove
1814+          -- this result using the unnamed `ih`
1815+          obtain ⟨δ', hExt, hTy', hStoreTy'⟩ : ∃ δ', Extends δ' δ ∧ _ ∧ (δ' ⊢ ρ') := by
1816+            solve_by_elim
1817+          exists δ'; constructor
1818+          assumption; constructor
1819+          constructor <;> solve_by_elim [store_weakening] using StlcRefTyping
1820+          assumption) <;>
1821+        -- handle the cases where the store doesn't grow
1822+        (try
1823+          exists δ; constructor
1824+          apply extends_refl; constructor
1825+          solve_by_elim using StlcRefTyping
1826+          assumption))
1827+    | app h₁ h₂ ih₁ ih₂ =>
1828+      inversion h₁
1829+      exists δ; constructor
1830+      apply extends_refl; constructor
1831+      apply_rules [substitution_preserves_typing] using StlcRefTyping
1832+      assumption
1833+    | @ref_ _ _ τ₁ =>
1834+      exists δ.concat τ₁; constructor
1835+      · rw [List.concat_eq_append]; apply extends_app
1836+      · constructor
1837+        · have h : <{Ref τ₁}> = <{Ref ~((δ.concat τ₁)[ρ.length])}> := by
1838+            simp_all [StoreWellTyped, MyGetElem.getElem]
1839+          rw [h]
1840+          constructor
1841+          simp [StoreWellTyped] at hStoreTy ⊢; lia
1842+        · apply store_well_typed_app <;> assumption
1843+    | deref h =>
1844+      inversion h
1845+      exists δ; constructor
1846+      apply extends_refl; constructor
1847+      have ⟨_, h₂⟩ := hStoreTy; apply h₂; assumption
1848+      assumption
1849+    | assign h₁ =>
1850+      inversion h₁
1851+      exists δ; constructor
1852+      apply extends_refl; constructor
1853+      constructor
1854+      apply assign_pres_store_typing <;> assumption
1855+
1856+--  This shorter proof only handles the interesting cases (`app`, `deref`,
1857+--  `assign`, and `ref`) manually, and solves all the mechanical ones
1858+--  automatically.
1859+
1860+--  ### Exercise (3 stars): preservation_informal (Manually graded) ⭐⭐⭐
1861+
1862+--  Write a careful informal proof of the preservation theorem,
1863+--  concentrating on the `app`, `deref`, `assign`, and `ref` cases.
1864+
1865+--  *Proof*: By induction on a derivation of `∅ / [] ⊢ t : τ`.
1866+--  - If the last rule in the derivation is `app`, then `t = t₁ t₂` for
1867+--    some `t₁` and `t₂` and `τ = τ₁₂`, with `∅ / δ ⊢ t₁ : τ₁₁ → τ₁₂` and
1868+--    `∅ / δ ⊢ t₂ : τ₁₁`. There are three cases to consider, one for each
1869+--    rule that could have been used to show that `t₁ t₂` takes a step to
1870+--    `t'`.
1871+--    - Suppose `t₁ t₂` takes a step by `app₁`, with `t₁` stepping to `t₁'`
1872+--      and new store `ρ'`. Then by the IH there is some store typing `δ'`
1873+--      such that `δ'` extends `δ`, `ρ'` is well typed with respect to
1874+--      `δ'`, and `∅ / δ' ⊢ t₁' : τ₁₁ → τ₁₂`. We also know
1875+--      `∅ / δ' ⊢ t₂ : τ₁₁` by the `store_weakening` lemma. Hence,
1876+--      `∅ / δ' ⊢ t₁' t₂` by `app`.
1877+--    - The `app₂` case is similar.
1878+--    - Suppose `t₁ t₂` takes a step by `appAbs`. Then `t₁ = λx:τ₁₁. t₁₂`
1879+--      and `t₁ t₂` steps to `[x:=t₂] t₁₂`; the desired result now follows
1880+--      from the substitution lemma, taking `δ' = δ`.
1881+--
1882+--  - If the last rule in the derivation is `ref`, then `t = ref t₁` for
1883+--    some `t₁` and `∅ / δ ⊢ t₁ : τ₁` for some `τ₁`, with `τ = Ref τ₁`.
1884+--    There are two cases to consider, one for each rule that could have
1885+--    been used to show that `ref t₁` takes a step to `t'`.
1886+--    - Suppose `ref t₁` takes a step by `ref`, with `t₁` stepping to `t₁'`
1887+--      and new store `ρ'`. Then by the IH there is some store typing `δ'`
1888+--      such that `δ'` extends `δ`, `ρ'` is well typed with respect to
1889+--      `δ'`, and `∅ / δ' ⊢ t₁' : τ₁`. Hence, `∅ / δ' ⊢ ref t₁' : Ref τ₁`
1890+--      by `ref`.
1891+--    - Suppose `ref t₁` takes a step by `refValue`. Then `t₁` is a value,
1892+--      `ρ' = ρ.concat t₁`, and `t'` is the length of `ρ` - i.e., the
1893+--      location of `t₁` in `ρ'`. If we choose `δ' = δ.concat τ₁`, we
1894+--      obtain
1895+--      - `δ'` extends `δ` by construction
1896+--      - `ρ'` is well typed with respect to `δ'` because `ρ` is well typed
1897+--        with respect to `δ` and the last element, `t₁`, has type `τ₁`
1898+--        under `δ`, hence also under `δ'` by the store weakening lemma
1899+--      - `∅ / δ' ⊢ l : Ref τ₁` by `loc` as required.
1900+--
1901+--  - If the last rule in the derivation is `deref`, then `t = !t₁` for
1902+--    some `t₁` and `∅ / δ ⊢ t₁ : Ref τ`. There are two cases to consider,
1903+--    one for each rule that could have been used to show that `!t₁` takes
1904+--    a step to `t'`.
1905+--    - Suppose `!t₁` takes a step by `deref`, with `t₁` stepping to `t₁'`
1906+--      and new store `ρ'`. Then by the IH there is some store typing `δ'`
1907+--      such that `δ'` extends `δ`, `ρ'` is well typed with respect to
1908+--      `δ'`, and `∅ / δ' ⊢ t₁' : Ref τ`. Hence, `∅ / δ' ⊢ !t₁' : τ` by
1909+--      `deref`.
1910+--    - Suppose `ref t₁` takes a step by `derefLoc`. Then `t₁` is some
1911+--      location `l` and `t'` is the contents of `ρ` at location `l`.
1912+--      Moreover, the typing rule used to derive `∅ / δ ⊢ l : Ref τ` must
1913+--      be `loc`, so the contents of `δ` at location `l` is `τ`. Now, since
1914+--      `ρ` is well typed with respect to `δ`, we know that
1915+--      `∅ / δ ⊢ t' : τ`, as required.
1916+--
1917+--  - If the last rule in the derivation is `assign`, then `t = t₁ := t₂`
1918+--    for some `t₁` and `t₂`, with `∅ / δ ⊢ t₁ : Ref τ₂` and
1919+--    `∅ / δ ⊢ t₂ : τ₂` for some `τ₂`; moreover, `τ = Unit`. There are now
1920+--    three cases to consider, one for each rule that could have been used
1921+--    to show that `t₁ := t₂` takes a step to `t'`.
1922+--    - The cases where `t₁ := t₂` takes a step by either `assign₁` or
1923+--      `assign₂` are similar to the congruence rule cases above.
1924+--
1925+--    - Suppose `t₁ := t₂` takes a step by `assign`. Then `t₁` is some
1926+--      location `l`, `t₂` is some value, `t'` is `unit`, and `ρ'` is
1927+--      formed from `ρ` by updating the contents of location `l` with `t₂`.
1928+--
1929+--      Moreover, the typing rule used to derive `∅ / δ ⊢ l : Ref τ₂` must
1930+--      be `loc`, so the contents of `δ` at location `l` is `τ₂`. Now,
1931+--      `∅ / δ ⊢ unit : Unit` by `unit`. Moreover, since `ρ` is well typed
1932+--      with respect to `δ` and we know `∅ / δ ⊢ t₂ : τ₂`, we know that
1933+--      `ρ'` is well typed with respect to `δ` by lemma
1934+--      `assign_pres_store_typing`. So we can take `δ' = δ` and finish this
1935+--      case.
1936+--
1937+--    - (Other cases elided...)
1938+--
1939+--  *QED*.
1940+
1941+--  ### Progress
1942+
1943+--  As we've said, progress for this system is pretty easy to prove; the
1944+--  proof is very similar to the proof of progress for the STLC, with a few
1945+--  new cases for the new syntactic constructs.
1946+
1947+theorem progress (δ : StoreTy) (t : Tm) (τ : Ty) (ρ : Store)
1948+  (hTy : <{ ∅ / δ ⊢ t ⦂ τ }>)
1949+  (hStoreTy : δ ⊢ ρ) :
1950+  (t.IsValue ∨ ∃ t' ρ', t / ρ ⟶ t' / ρ') := by
1951+    have ⟨hLen, _⟩ := hStoreTy
1952+    generalize heq : (∅ : Context) = Γ at hTy
1953+    induction hTy with (subst_vars; first
1954+      | contradiction
1955+      -- discharge cases where `t` is obviously a value
1956+      | try (left; constructor; done))
1957+    | app h₁ _ ih₁ ih₂ =>
1958+      right; cases ih₁ (by rfl) with
1959+      -- t₁ is a value
1960+      | inl hv₁ =>
1961+        cases ih₂ (by rfl) with
1962+        -- t₂ is a value
1963+        | inl hv₂ =>
1964+          cases hv₁ <;> try contradiction
1965+          apply Exists.intro; apply Exists.intro; solve_by_elim using StlcRefEval
1966+        -- t₂ steps
1967+        | inr hs₂ =>
1968+          have ⟨t₂', ρ', hs₂⟩ := hs₂
1969+          apply Exists.intro; apply Exists.intro; solve_by_elim using StlcRefEval
1970+      -- t₁ steps
1971+      | inr hs₁ =>
1972+        have ⟨t₁', ρ', hs₁⟩ := hs₁
1973+        apply Exists.intro; apply Exists.intro; solve_by_elim using StlcRefEval
1974+    | succ h ih
1975+    | pred h ih =>
1976+      -- these two cases are the same
1977+      right; cases ih (by rfl) with
1978+      -- t₁ is a value
1979+      | inl hv =>
1980+        cases hv <;> try contradiction
1981+        apply Exists.intro; apply Exists.intro; solve_by_elim using StlcRefEval
1982+      -- t₁ steps
1983+      | inr hs =>
1984+        have ⟨t₁', ρ', hs⟩ := hs
1985+        apply Exists.intro; apply Exists.intro; solve_by_elim using StlcRefEval
1986+    | mult h₁ h₂ ih₁ ih₂ =>
1987+      right; cases ih₁ (by rfl) with
1988+      -- t₁ is a value
1989+      | inl hv₁ =>
1990+        cases ih₂ (by rfl) with
1991+        -- t₂ is a value
1992+        | inl hv₂ =>
1993+          cases hv₁ <;> try contradiction
1994+          cases hv₂ <;> try contradiction
1995+          apply Exists.intro; apply Exists.intro; solve_by_elim using StlcRefEval
1996+        -- t₂ steps
1997+        | inr hs₂ =>
1998+          have ⟨t₂', ρ', hs₂⟩ := hs₂
1999+          apply Exists.intro; apply Exists.intro; solve_by_elim using StlcRefEval
2000+      -- t₁ steps
2001+      | inr hs₁ =>
2002+        have ⟨t₁', ρ', hs₁⟩ := hs₁
2003+        apply Exists.intro; apply Exists.intro; solve_by_elim using StlcRefEval
2004+    | ite0 h₁ _ _ ih₁ _ _ =>
2005+      right; cases ih₁ (by rfl) with
2006+      -- t₁ is a value
2007+      | inl hv₁ =>
2008+        cases hv₁ with (try contradiction)
2009+        | nat n =>
2010+          cases n <;> (apply Exists.intro; apply Exists.intro; solve_by_elim using StlcRefEval)
2011+      -- t₁ steps
2012+      | inr hs₁ =>
2013+        have ⟨t₁', ρ', hs₁⟩ := hs₁
2014+        apply Exists.intro; apply Exists.intro; solve_by_elim using StlcRefEval
2015+    | ref_ _ ih =>
2016+      right; cases ih (by rfl) with
2017+      -- t₁ is a value
2018+      | inl hv =>
2019+        apply Exists.intro; apply Exists.intro; solve_by_elim using StlcRefEval
2020+      -- t₁ steps
2021+      | inr hs =>
2022+        have ⟨t₁', ρ', hs⟩ := hs
2023+        apply Exists.intro; apply Exists.intro; solve_by_elim using StlcRefEval
2024+    | deref h ih =>
2025+      right; cases ih (by rfl) with
2026+      -- t₁ is a value; its typing tells us `l < δ.length`
2027+      | inl hv =>
2028+        cases hv with (inversion h)
2029+        | loc_ l => exists ρ[l], ρ; apply Step.derefLoc; lia
2030+      -- t₁ steps
2031+      | inr hs =>
2032+        have ⟨t₁', ρ', hs⟩ := hs
2033+        apply Exists.intro; apply Exists.intro; solve_by_elim using StlcRefEval
2034+    | @assign _ _ t₂ _ h₁ _ ih₁ ih₂ =>
2035+      right; cases ih₁ (by rfl) with
2036+      -- t₁ is a value
2037+      | inl hv₁ =>
2038+        cases ih₂ (by rfl) with
2039+        -- t₂ is a value
2040+        | inl hv₂ =>
2041+          cases hv₁ with (inversion h₁)
2042+          | loc_ l => exists <{ unit }>, ρ.set l t₂; apply Step.assign hv₂; lia
2043+        -- t₂ steps
2044+        | inr hs₂ =>
2045+          have ⟨_, _, _⟩ := hs₂
2046+          apply Exists.intro; apply Exists.intro; solve_by_elim using StlcRefEval
2047+      -- t₁ steps
2048+      | inr hs₁ =>
2049+        have ⟨t₁', ρ', hs₁⟩ := hs₁
2050+        apply Exists.intro; apply Exists.intro; solve_by_elim using StlcRefEval
2051+
2052+--  Like the earlier preservation proof, many of these cases are
2053+--  repetitive. Once again we can make the proof more concise using
2054+--  automation:
2055+
2056+theorem progress_shorter (δ : StoreTy) (t : Tm) (τ : Ty) (ρ : Store)
2057+  (hTy : <{ ∅ / δ ⊢ t ⦂ τ }>)
2058+  (hStoreTy : δ ⊢ ρ) :
2059+  (t.IsValue ∨ ∃ t' ρ', t / ρ ⟶ t' / ρ') := by
2060+    have ⟨hLen, _⟩ := hStoreTy
2061+    generalize heq : (∅ : Context) = Γ at hTy
2062+    induction hTy with (
2063+      subst_vars; first
2064+      | contradiction
2065+      -- discharge cases where `t` is obviously a value
2066+      | (left; constructor; done)
2067+      -- otherwise, `t` steps
2068+      | (right
2069+         -- we use the same trick as in the preservation proof
2070+         -- to get around our unnamed `ih`
2071+         (obtain hv | ⟨t', ρ', hs⟩ : Tm.IsValue _ ∨ ∃ t' ρ', _ / ρ ⟶ t' / ρ' := by
2072+           solve_by_elim) <;>
2073+         -- handle simple cases where `t`'s type gives us
2074+         -- one possible value
2075+         try
2076+           (try (cases hv <;> try contradiction)) <;>
2077+           (apply Exists.intro; apply Exists.intro; solve_by_elim using StlcRefEval)))
2078+    | app h₁ _ _ ih₂ =>
2079+      cases hv <;> inversion h₁
2080+      obtain hv₂ | ⟨t₂', ρ', hs₂⟩ := ih₂ (by rfl) <;>
2081+      (apply Exists.intro; apply Exists.intro; solve_by_elim using StlcRefEval)
2082+    | mult h₁ h₂ _ ih₂ =>
2083+      cases hv <;> try contradiction
2084+      cases ih₂ (by rfl) with
2085+      | inl hv₂ =>
2086+        cases hv₂ <;> try contradiction
2087+        apply Exists.intro; apply Exists.intro; solve_by_elim using StlcRefEval
2088+      | inr hs₂ =>
2089+        have ⟨t₂', ρ', hs₂⟩ := hs₂
2090+        apply Exists.intro; apply Exists.intro; solve_by_elim using StlcRefEval
2091+    | ite0 h₁ =>
2092+      cases hv with (inversion h₁)
2093+      | nat n =>
2094+        cases n <;>
2095+        (apply Exists.intro; apply Exists.intro; solve_by_elim using StlcRefEval)
2096+    | deref h =>
2097+      cases hv <;> inversion h
2098+      apply Exists.intro; apply Exists.intro; apply Step.derefLoc; lia
2099+    | assign h₁ _ _ ih₂ =>
2100+      cases hv <;> inversion h₁
2101+      cases ih₂ (by rfl) with
2102+      | inl hv₂ =>
2103+        apply Exists.intro; apply Exists.intro; apply Step.assign hv₂; lia
2104+      | inr hs₂ =>
2105+        have ⟨t₂', ρ', hs₂⟩ := hs₂
2106+        apply Exists.intro; apply Exists.intro; solve_by_elim using StlcRefEval
2107+
2108+--  ## References and Nontermination
2109+
2110+--  An important fact about the STLC is that it is *normalizing* — that is,
2111+--  every well-typed term can be reduced to a value in a finite number of
2112+--  steps.
2113+--
2114+--  What about STLC + references? Surprisingly, adding references causes us
2115+--  to lose the normalization property: there exist well-typed terms in the
2116+--  STLC + references which can continue to reduce forever, without ever
2117+--  reaching a normal form!
2118+--
2119+--  How can we construct such a term? The main idea is to make a function
2120+--  which calls itself. We first make a function which calls another
2121+--  function stored in a reference cell; the trick is that we then smuggle
2122+--  in a reference to itself!
2123+--
2124+--         (λR: Ref (Unit → Unit),
2125+--              R := (λx:Unit,(!R) unit); (!R) unit)
2126+--      (ref (λX:Unit.unit))
2127+--
2128+--  First, `ref (λX:Unit.unit)` creates a reference to a cell of type
2129+--  `Unit → Unit`. We then pass this reference as the argument to a
2130+--  function which binds it to the name `R`, and assigns to it the function
2131+--  `λX:Unit.(!R) unit` — that is, the function which ignores its argument
2132+--  and calls the function stored in `R` on the argument `unit`; but of
2133+--  course, that function is itself! To start the divergent loop, we
2134+--  execute the function stored in the cell by evaluating `(!r) unit`.
2135+--
2136+--  Here is the divergent term in Lean:
2137+
2138+namespace RefsAndNontermination
2139+
2140+def loop_fun := <{ λX : Unit. (!R) unit }>
2141+
2142+def loop :=
2143+  <{ (λR : Ref (Unit → Unit). (( R := (λX : Unit. (!R) unit) );  ( (! R) unit ) ))
2144+     (ref (λX : Unit. unit)) }>
2145+
2146+--  This term is well typed:
2147+
2148+theorem loop_typeable : ∃ τ, <{ ∅ / [] ⊢ loop ⦂ τ }> := by
2149+  apply Exists.intro
2150+  apply_rules using StlcRefTyping
2151+
2152+--  To show formally that the term diverges, we first define the
2153+--  `step_closure` of the single-step reduction relation, written `⟶+`.
2154+--  This is just like the reflexive step closure of single-step reduction
2155+--  (which we're been writing `⟶*`), except that it is not reflexive:
2156+--  `t ⟶+ t'` means that `τ` can reach `t'` by *one or more* steps of
2157+--  reduction.
2158+
2159+inductive StepClosure {X:Type} (R: Relation X) : X → X → Prop :=
2160+  | one {x y : X} (h₁ : R x y) : StepClosure R x y
2161+  | step {x y z : X} (h₁ : R x y) (h₂ : StepClosure R y z) : StepClosure R x z
2162+
2163+scoped notation:40
2164+  t:71 " / " ρ:41 " ⟶+ " t':71 " / " ρ':41 =>
2165+  StepClosure Step (t, ρ) (t', ρ')
2166+
2167+--  Now, we can show that the expression `loop` reduces to the expression
2168+--  `!(loc 0) unit` and the size-one store `[R:=(loc 0)] loop_fun`.
2169+--
2170+--  As a convenience, we introduce a slight variant of the `normalize`
2171+--  tactic, called `reduce`, which tries solving the goal with `Multi.refl`
2172+--  at each step, instead of waiting until the goal can't be reduced any
2173+--  more. Of course, the whole point is that `loop` doesn't normalize, so
2174+--  the old `normalize` tactic would just go into an infinite loop reducing
2175+--  it forever!
2176+
2177+syntax "reduce" " using " ident,+ : tactic
2178+
2179+macro_rules
2180+  | `(tactic| reduce using $xs,*) =>
2181+    `(tactic|
2182+      repeat
2183+        (apply Multi.step
2184+         · solve_by_elim (maxDepth := 15) (constructor := false) [Nat.le.refl, Nat.le.step] using $xs,*
2185+         try apply Multi.refl))
2186+
2187+--  Next, we use `reduce` to show that `loop` steps to `!(loc 0) unit`,
2188+--  starting from the ∅ store.
2189+
2190+theorem loop_steps_to_loop_fun :
2191+  loop / [] ⟶*  <{ (! (loc 0)) unit }> / [<{ [R := loc 0] loop_fun }>] := by
2192+    reduce using StlcRefEval
2193+
2194+--  Finally, we show that the latter expression reduces in two steps to
2195+--  itself!
2196+
2197+theorem loop_fun_step_self :
2198+  <{ (! (loc 0)) unit }> / [<{ [R := loc 0] loop_fun }>] ⟶+
2199+  <{ (! (loc 0)) unit }> / [<{ [R := loc 0] loop_fun }>] := by
2200+    apply StepClosure.step; solve_by_elim using StlcRefEval
2201+    apply StepClosure.one; solve_by_elim using StlcRefEval
2202+
2203+--  ### Exercise (4 stars): factorial_ref ⭐⭐⭐⭐
2204+
2205+--  Use the above ideas to implement a factorial function in STLC with
2206+--  references. (There is no need to prove formally that it really behaves
2207+--  like the factorial. Just uncomment the example below to make sure it
2208+--  gives the correct result when applied to the argument `4`.)
2209+
2210+def factorial : Tm :=
2211+  (
2212+    <{(λR : (Ref (Nat → Nat) ).
2213+            (R := (λX : Nat. if0 X then 1 else (X * ( (!R) (pred X) ) ))); !R  )
2214+      (ref (λX : Nat. X)) }>)
2215+
2216+theorem factorial_type : <{ ∅ / [] ⊢ factorial ⦂ (Nat → Nat) }> := by
2217+  apply_rules using StlcRefTyping
2218+
2219+--  If your definition is correct, you should be able to finish the example
2220+--  below; the proof should be fully automatic using the `reduce` tactic,
2221+--  once the witness is supplied.
2222+
2223+theorem factorial_4 : ∃ (ρ : Store), <{ factorial 4 }> / [] ⟶* .const 24 / ρ := by
2224+  exists [<{ λX : Nat. if0 X then 1 else (X * ((!(loc 0)) (pred X))) }>]
2225+  reduce using StlcRefEval
2226+
2227+--  (End of exercise)
2228+
2229+end RefsAndNontermination
2230+
2231+--  ## Additional Exercises
2232+
2233+--  ### Exercise (5 stars): garbage_collector (Optional) ⭐⭐⭐⭐⭐
2234+
2235+--  Challenge problem: modify our formalization to include an account of
2236+--  garbage collection, and prove that it satisfies whatever nice
2237+--  properties you can think to prove about it.
2238+
2239+--  (End of exercise)
2240+
2241+end STLCRef
2242+
2243+-- Source revision: a06e066, committed 2026-10-27 16:51 UTC

TS/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

TS/Smallstep.lean

55 import SFLCompat
66 
77 --  # Smallstep: Small-step Operational Semantics
8-
9---  Note to developers (Benjamin Pierce @bcpierce00):
10---      The `hiding lean` (above in the source file) should not be needed
11---      any more and should be removed from all files everywhere it exists.
128 
139 --  Note to developers (Michael Hicks @mwhicks1):
1410 --      This chapter adapts Smallstep to follow Slang, the initial part of
272268 --  reviewing that chapter may be useful if the treatment here feels too
273269 --  terse.)
274270 --
275---  A *binary relation* on a type `X` is a family of propositions
276---  parameterized by two elements of `X` — i.e., a proposition about pairs
277---  of elements of `X`.
271+--  A *binary relation* on a type `α` is a family of propositions
272+--  parameterized by two elements of `α` — i.e., a proposition about pairs
273+--  of elements of `α`. The type of a binary relation on a type `α` is
274+--  `α → α → Prop`.
278275 
279276 --  Note to developers (Michael Hicks @mwhicks1, before next release):
280277 --      Should we be getting this (and `Deterministic`, `Multi`, etc. if
281278 --      appropriate) from the Lean standard library? If not, should we
282279 --      match the concepts in CSLib, if they exists there?
283280 
284-def Relation (X : Type) := X → X → Prop
281+--  Note to developers (Roger Burtonpatel @rogerburtonpatel, before next release):
282+--      @mwhicks1 I looked into this and there is some existing infra, but
283+--      not much. Mathlib/CSlib have a few items (determinism though
284+--      Relator.RightUnique), but using their transitive closures actually
285+--      puts a step AFTER the multistep, which would change all the
286+--      inductions. We could certainly use a few of the notations for
287+--      stepping, and change `IsNormalForm` to their `Normal`.
288+--
289+--      I would say put both of these comments in a larger maybe-TODO and
290+--      delete them for now.
291+
292+def Relation (α : Type) := α → α → Prop
285293 
286294 --  Our main examples of such relations in this chapter will be the
287295 --  single-step reduction relation, `⟶`, and its multi-step variant, `⟶*`,
313321 --
314322 --  Formally,
315323 
316-def Deterministic {X : Type} (R : Relation X) : Prop :=
317-  ∀ x y₁ y₂ : X, R x y₁ → R x y₂ → y₁ = y₂
324+def Deterministic {α : Type} (R : Relation α) : Prop :=
325+  ∀ x y₁ y₂ : α, R x y₁ → R x y₂ → y₁ = y₂
318326 
319327 namespace SimpleArith2
320328 
323331   induction h₁ generalizing y₂ with
324332   | plus n₁ n₂ =>
325333       intro h₂
326-      cases h₂ <;> first | rfl | cases ‹SimpleArith1.Step (.c _) _›
334+      cases h₂ <;> try contradiction
335+      rfl
327336   | plusLeft t₁ t₁' t₂ hs ih =>
328337       intro h₂
329-      cases h₂ <;> first | cases ‹SimpleArith1.Step (.c _) _› | rw [ih _ ‹SimpleArith1.Step t₁ _›]
338+      cases h₂ <;> try contradiction
339+      case plusLeft.plusLeft h => rw [ih _ h]
330340   | plusRight n₁ t₂ t₂' hs ih =>
331341       intro h₂
332-      cases h₂ <;> first | cases ‹SimpleArith1.Step (.c _) _› | rw [ih _ ‹SimpleArith1.Step t₂ _›]
342+      cases h₂ <;> try contradiction
343+      case plusRight.plusRight h => rw [ih _ h]
333344 
334345 end SimpleArith2
335-
336---  Note to developers (Michael Hicks @mwhicks1):
337---      In the Rocq there is the development of a special tactic to make
338---      this proof simpler. Do we want that here?
339346 
340347 --  ### Values
341348 
436443   intro x y₁ y₂ h₁
437444   induction h₁ generalizing y₂ with
438445   | plus n₁ n₂ =>
439-      intro h₂; cases h₂ with
446+      intro h₂; cases h₂ with try contradiction
440447       | plus => rfl
441-      | plusLeft _ _ _ hs => cases hs
442-      | plusRight _ _ _ _ hs => cases hs
443448   | plusLeft t₁ t₁' t₂ hs ih =>
444-      intro h₂; cases h₂ with
445-      | plus => cases hs
449+      intro h₂; cases h₂ with try contradiction
446450       | plusLeft _ _ _ hs₂ => rw [ih _ hs₂]
447451       | plusRight _ _ _ hv hs₂ => cases hv; cases hs
448452   | plusRight v₁ t₂ t₂' hv hs ih =>
449-      intro h₂; cases h₂ with
450-      | plus => cases hs
453+      intro h₂; cases h₂ with try contradiction
451454       | plusLeft _ _ _ hs₂ => cases hv; cases hs₂
452455       | plusRight _ _ _ _ hs₂ => rw [ih _ hs₂]
453456 
479482 
480483 theorem strong_progress (t : Tm) : IsValue t ∨ ∃ t', t ⟶ t' := by
481484   induction t with
482-  | c n => left; exact .const n
485+  | c n => left; constructor
483486   | p t₁ t₂ ih₁ ih₂ =>
484487       right
485488       cases ih₁ with
489492               cases hv₁ with
490493               | const n₁ =>
491494                   cases hv₂ with
492-                  | const n₂ => exact ⟨.c (n₁ + n₂), .plus n₁ n₂⟩
495+                  | const n₂ =>
496+                      exists .c (n₁ + n₂)
497+                      apply Step.plus
493498           | inr h₂ =>
494499               obtain ⟨t₂', ht₂⟩ := h₂
495-              exact ⟨.p t₁ t₂', .plusRight t₁ t₂ t₂' hv₁ ht₂⟩
500+              exists .p t₁ t₂'
501+              apply Step.plusRight
502+              · exact hv₁
503+              · exact ht₂
496504       | inr h₁ =>
497505           obtain ⟨t₁', ht₁⟩ := h₁
498-          exact ⟨.p t₁' t₂, .plusLeft t₁ t₁' t₂ ht₁⟩
506+          exists .p t₁' t₂
507+          apply Step.plusLeft
508+          exact ht₁
499509 
500510 --  This important property is called *strong progress*, because every term
501511 --  either is a value or can "make progress" by stepping to some other
507517 --  that do *not* make progress in this sense. Let's give a name to "terms
508518 --  that cannot make progress." We'll call them *normal forms*.
509519 
510-def IsNormalForm {X : Type} (R : Relation X) (t : X) : Prop :=
520+def IsNormalForm {α : Type} (R : Relation α) (t : α) : Prop :=
511521   ¬ ∃ t', R t t'
512522 
513523 --  Note that this definition specifies what it is to be a normal form for
514---  an *arbitrary* relation `R` over an arbitrary type `X`, not just for
524+--  an *arbitrary* relation `R` over an arbitrary type `α`, not just for
515525 --  the particular single-step reduction relation over terms that we are
516526 --  interested in at the moment. We'll re-use the same terminology for
517527 --  talking about other relations later in the course.
531541     (h : IsNormalForm Step t) : IsValue t := by
532542   cases strong_progress t with
533543   | inl hv => exact hv
534-  | inr hstep => exact absurd hstep h
544+  | inr hstep => contradiction
535545 
536546 theorem nf_same_as_value (t : Tm) :
537547     IsNormalForm Step t ↔ IsValue t := by
538-  exact ⟨nf_is_value t, value_is_nf t⟩
539-
540---  Note to developers (Kihong Heo @KihongHeo):
541---      Tactic `absurd` is first introduced here. Do we want to explain it?
542-
543---  Note to developers (Daniel Sainati @dsainati1):
544---      I think some of these proofs were originally Claude-generated, so
545---      we probably want to redo them from scratch, in which case
546---      introducing absurd is likely not necessary.
548+  constructor
549+  · apply nf_is_value
550+  · apply value_is_nf
547551 
548552 --  Why is this interesting? Because `IsValue` is a *syntactic* concept —
549553 --  it is defined by looking at the way a term is written — while
601605 
602606 theorem value_not_same_as_normal_form :
603607     ∃ v, IsValue v ∧ ¬ IsNormalForm Step v := by
604-  apply Exists.intro (.p (.c 0) (.c 0))
605-  apply And.intro (.funny _ 0)
606-  intro h
607-  exact h ⟨.c (0 + 0), .plus 0 0⟩
608+  exists .p (.c 0) (.c 0)
609+  constructor
610+  · apply IsValue.funny
611+  · intro h
612+    apply h
613+    exists .c (0 + 0)
614+    apply Step.plus
608615 
609616 --  (End of exercise)
610617 
645652 
646653 theorem value_not_same_as_normal_form :
647654     ∃ v, IsValue v ∧ ¬ IsNormalForm Step v := by
648-  apply Exists.intro (.c 5)
649-  apply And.intro (.const 5)
650-  intro h
651-  exact h ⟨.p (.c 5) (.c 0), .funny 5⟩
655+  exists .c 5
656+  constructor
657+  · apply IsValue.const
658+  · intro h
659+    apply h
660+    exists .p (.c 5) (.c 0)
661+    apply Step.funny
652662 
653663 end Temp2
654664 
685695 
686696 theorem value_not_same_as_normal_form :
687697     ∃ t, ¬ IsValue t ∧ IsNormalForm Step t := by
688-  apply Exists.intro (.p (.c 1) (.p (.c 1) (.c 2)))
689-  apply And.intro
698+  exists .p (.c 1) (.p (.c 1) (.c 2))
699+  constructor
690700   · intro h; cases h
691701   · intro h
692702     obtain ⟨t', ht⟩ := h
714724 --  define a new relation `Multi R`, called the *multi-step closure of
715725 --  `R`*, as follows.
716726 
717-inductive Multi {X : Type} (R : Relation X) : X → X → Prop where
718-  | refl (x : X) : Multi R x x
719-  | step (x y z : X) (h₁ : R x y) (h₂ : Multi R y z) : Multi R x z
720-
721---  Note to developers (berberman):
722---      I would make some arguments implicit to provide a cleaner interface
723---      (FYI the [mathlib
724---      version](https://leanprover-community.github.io/mathlib4_docs/Mathlib/Logic/Relation.html#Relation.ReflTransGen))
727+inductive Multi {α : Type} (R : Relation α) : α → α → Prop where
728+  | refl (x : α) : Multi R x x
729+  | step (x y z : α) (h₁ : R x y) (h₂ : Multi R y z) : Multi R x z
725730 
726731 --  The effect of this definition is that `Multi R` relates two elements
727732 --  `x` and `y` if
770775 --  case of multi-step executions. (It is this fact that justifies the word
771776 --  "closure" in "multi-step closure of `R`.")
772777 
773-theorem multi_single {X : Type} (R : Relation X) (x y : X)
778+theorem multi_single {α : Type} (R : Relation α) (x y : α)
774779     (h : R x y) : Multi R x y := by
775-  exact .step x y y h (.refl y)
780+  apply Multi.step (y := y)
781+  · exact h
782+  · rfl
776783 
777784 --  Third, `Multi R` is *transitive*.
778785 
779-theorem multi_trans {X : Type} (R : Relation X) (x y z : X)
786+theorem multi_trans {α : Type} (R : Relation α) (x y z : α)
780787     (g : Multi R x y) (h : Multi R y z) : Multi R x z := by
781788   induction g with
782789   | refl a => exact h
783-  | step a b c h₁ h₂ ih => exact .step a b z h₁ (ih h)
790+  | step a b c h₁ h₂ ih =>
791+      apply Multi.step (y := b)
792+      · exact h₁
793+      · exact ih h
784794 
785795 --  In particular, for the `Multi Step` relation on terms, if `t₁ ⟶* t₂`
786796 --  and `t₂ ⟶* t₃`, then `t₁ ⟶* t₃`.
803813     (.p (.p (.c 0) (.c 3)) (.p (.c 2) (.c 4)))
804814       ⟶* .c ((0 + 3) + (2 + 4)) := by
805815   apply Multi.step (y := .p (.c (0 + 3)) (.p (.c 2) (.c 4)))
806-  · exact .plusLeft _ _ _ (.plus 0 3)
816+  · apply Step.plusLeft
817+    apply Step.plus
807818   apply Multi.step (y := .p (.c (0 + 3)) (.c (2 + 4)))
808-  · exact .plusRight _ _ _ (.const _) (.plus 2 4)
809-  · exact multi_single _ _ _ (.plus (0 + 3) (2 + 4))
819+  · apply Step.plusRight
820+    · apply IsValue.const
821+    · apply Step.plus
822+  · apply multi_single
823+    apply Step.plus
810824 
811825 --  ### Exercise (1 star): test_multistep_2 (Optional) ⭐
812826 
822836     (.p (.c 0) (.p (.c 2) (.p (.c 0) (.c 3))))
823837       ⟶* (.p (.c 0) (.c (2 + (0 + 3)))) := by
824838   apply Multi.step (y := .p (.c 0) (.p (.c 2) (.c (0 + 3))))
825-  · exact .plusRight _ _ _ (.const 0) (.plusRight _ _ _ (.const 2) (.plus 0 3))
826-  · exact multi_single _ _ _ (.plusRight _ _ _ (.const 0) (.plus 2 (0 + 3)))
839+  · apply Step.plusRight
840+    · apply IsValue.const
841+    · apply Step.plusRight
842+      · apply IsValue.const
843+      · apply Step.plus
844+  · apply multi_single
845+    apply Step.plusRight
846+    · apply IsValue.const
847+    · apply Step.plus
827848 
828849 --  ### Exercise (2 stars): test_multistep_rfl ⭐⭐
829850 
833854 theorem test_multistep_rfl :
834855     (.p (.p (.c 1) (.c 2)) (.c 4)) ⟶* .c ((1 + 2) + 4) := by
835856   apply Multi.step (y := .p (.c (1 + 2)) (.c 4))
836-  · exact .plusLeft _ _ _ (.plus 1 2)
857+  · apply Step.plusLeft
858+    apply Step.plus
837859   apply Multi.step (y := .c ((1 + 2) + 4))
838860   · exact .plus (1 + 2) 4
839861   · rfl
843865 --  If `t` reduces to `t'` in zero or more steps and `t'` is a normal form,
844866 --  we say that "`t'` is *a normal form of* `t`."
845867 
846-def IsNormalFormOf {X : Type} (R : Relation X) (t t' : X) : Prop :=
868+def IsNormalFormOf {α : Type} (R : Relation α) (t t' : α) : Prop :=
847869   Multi R t t' ∧ IsNormalForm R t'
848870 
849871 --  We have already seen that, for our language, single-step reduction is
866888   | refl a =>
867889       cases p₂₁ with
868890       | refl => rfl
869-      | step _ b _ h₁ _ => exact absurd ⟨b, h₁⟩ p₁₂
891+      | step _ b _ h₁ _ =>
892+        exfalso
893+        apply p₁₂
894+        exists b
870895   | step a b c h₁ h₂ ih =>
871896       cases p₂₁ with
872-      | refl => exact absurd ⟨b, h₁⟩ p₂₂
897+      | refl =>
898+        exfalso
899+        apply p₂₂
900+        exists b
873901       | step _ b' _ h₁' h₂' =>
874902           have hbb : b = b' := step_deterministic _ _ _ h₁ h₁'
875903           subst hbb
883911 --  `IsNormalFormOf` is a *total* function. We say the `Step` relation is
884912 --  *normalizing*. To prove it, we need a couple of congruence lemmas.
885913 
886-def Normalizing {X : Type} (R : Relation X) : Prop :=
914+def Normalizing {α : Type} (R : Relation α) : Prop :=
887915   ∀ t, ∃ t', IsNormalFormOf R t t'
888916 
889917 theorem multistep_congr_1 (t₁ t₁' t₂ : Tm) (h : t₁ ⟶* t₁') :
890918     (.p t₁ t₂) ⟶* (.p t₁' t₂) := by
891919   induction h with
892920   | refl x => exact .refl _
893-  | step x y z h₁ h₂ ih => exact .step _ (.p y t₂) _ (.plusLeft x y t₂ h₁) ih
921+  | step x y z h₁ h₂ ih =>
922+      apply Multi.step (y := .p y t₂)
923+      · apply Step.plusLeft
924+        exact h₁
925+      · exact ih
894926 
895927 --  ### Exercise (2 stars): multistep_congr_2 ⭐⭐
896928 
899931     (.p v₁ t₂) ⟶* (.p v₁ t₂') := by
900932   induction h with
901933   | refl x => exact .refl _
902-  | step x y z h₁ h₂ ih => exact .step _ (.p v₁ y) _ (.plusRight v₁ x y hv h₁) ih
934+  | step x y z h₁ h₂ ih =>
935+      apply Multi.step (y := .p v₁ y)
936+      · apply Step.plusRight
937+        · exact hv
938+        · exact h₁
939+      · exact ih
903940 
904941 --  (End of exercise)
905942 
926963 theorem step_normalizing : Normalizing Step := by
927964   intro t
928965   induction t with
929-  | c n => exact ⟨.c n, .refl _, (nf_same_as_value _).mpr (.const n)⟩
966+  | c n =>
967+      exists .c n
968+      constructor
969+      · apply Multi.refl
970+      · apply (nf_same_as_value _).mpr
971+        apply IsValue.const
930972   | p t₁ t₂ ih₁ ih₂ =>
931973       obtain ⟨t₁', hs₁, hnf₁⟩ := ih₁
932974       obtain ⟨t₂', hs₂, hnf₂⟩ := ih₂
933975       obtain ⟨n₁⟩ := (nf_same_as_value _).mp hnf₁
934976       obtain ⟨n₂⟩ := (nf_same_as_value _).mp hnf₂
935-      apply Exists.intro (.c (n₁ + n₂))
936-      apply And.intro _ ((nf_same_as_value _).mpr (.const _))
937-      apply multi_trans _ _ _ _ (multistep_congr_1 t₁ (.c n₁) t₂ hs₁)
938-      apply multi_trans _ _ _ _ (multistep_congr_2 (.c n₁) t₂ (.c n₂) (.const n₁) hs₂)
939-      exact multi_single _ _ _ (.plus n₁ n₂)
977+      exists .c (n₁ + n₂)
978+      constructor
979+      · apply multi_trans _ _ _ _ (multistep_congr_1 t₁ (.c n₁) t₂ hs₁)
980+        apply multi_trans _ _ _ _ (multistep_congr_2 (.c n₁) t₂ (.c n₂) (.const n₁) hs₂)
981+        apply multi_single
982+        apply Step.plus
983+      · apply (nf_same_as_value _).mpr
984+        apply IsValue.const
940985 
941986 --  ### Equivalence of Big-Step and Small-Step
942987 
9571002   | plus t₁ t₂ n₁ n₂ h₁ h₂ ih₁ ih₂ =>
9581003       apply multi_trans _ _ _ _ (multistep_congr_1 t₁ (.c n₁) t₂ ih₁)
9591004       apply multi_trans _ _ _ _ (multistep_congr_2 (.c n₁) t₂ (.c n₂) (.const n₁) ih₂)
960-      exact multi_single _ _ _ (.plus n₁ n₂)
1005+      apply multi_single
1006+      apply Step.plus
9611007 
9621008 --  The key ideas in the proof can be seen in the following picture:
9631009 
10261072   induction hs generalizing n with
10271073   | plus n₁ n₂ =>
10281074       cases he with
1029-      | const _ => exact .plus _ _ n₁ n₂ (.const n₁) (.const n₂)
1075+      | const _ =>
1076+          apply Eval.plus
1077+          · apply Eval.const
1078+          · apply Eval.const
10301079   | plusLeft t₁ t₁' t₂ h₁ ih =>
10311080       cases he with
1032-      | plus _ _ m₁ m₂ he₁ he₂ => exact .plus t₁ t₂ m₁ m₂ (ih m₁ he₁) he₂
1081+      | plus _ _ m₁ m₂ he₁ he₂ =>
1082+          apply Eval.plus
1083+          · apply ih
1084+            exact he₁
1085+          · exact he₂
10331086   | plusRight v₁ t₂ t₂' hv h₂ ih =>
10341087       cases he with
1035-      | plus _ _ m₁ m₂ he₁ he₂ => exact .plus v₁ t₂ m₁ m₂ he₁ (ih m₂ he₂)
1088+      | plus _ _ m₁ m₂ he₁ he₂ =>
1089+          apply Eval.plus
1090+          · exact he₁
1091+          · apply ih
1092+            exact he₂
10361093 
10371094 --  (End of exercise)
10381095 
10541111     induction hst with
10551112     | refl b => intro heq; subst heq; exact .const n
10561113     | step b c d h₁ h₂ ih => intro heq; exact eval_of_step b c n h₁ (ih heq)
1057-  exact ⟨n, rfl, H t (.c n) hs rfl⟩
1114+  exists n
1115+  constructor
1116+  · rfl
1117+  · apply H
1118+    · exact hs
1119+    · rfl
10581120 
10591121 --  ### Exercise (3 stars): interp_tm (Optional) ⭐⭐⭐
10601122 
10701132     subst hi
10711133     induction t with
10721134     | c n => exact .const n
1073-    | p t₁ t₂ ih₁ ih₂ => exact .plus t₁ t₂ _ _ ih₁ ih₂
1135+    | p t₁ t₂ ih₁ ih₂ =>
1136+        apply Eval.plus
1137+        · exact ih₁
1138+        · exact ih₂
10741139   · intro he
10751140     induction he with
10761141     | const n => rfl
11631228 example :
11641229     (Aexp.plus (.num 3) (.plus (.num 2) (.num 1)))
11651230       ⟶a (.plus (.num 3) (.num 3)) := by
1166-  exact .plusRight (.num 3) (.plus 2 1)
1231+  apply AStep.plusRight
1232+  · apply IsAValue.num
1233+  · apply AStep.plus
11671234 
11681235 --  ### Exercise (2 stars): strong_progress_arith ⭐⭐
11691236 
11741241 theorem strong_progress_arith (a : Aexp) :
11751242     IsAValue a ∨ ∃ a', a ⟶a a' := by
11761243   induction a with
1177-  | num n => exact .inl (.num n)
1244+  | num n =>
1245+      left
1246+      apply IsAValue.num
11781247   | plus a₁ a₂ ih₁ ih₂ =>
11791248       right
11801249       cases ih₁ with
11871256           | inr h₂ =>
11881257             obtain ⟨a₂', ha₂⟩ := h₂
11891258             exists .plus (.num n₁) a₂'
1190-            exact .plusRight (.num n₁) ha₂
1259+            apply AStep.plusRight
1260+            · apply IsAValue.num
1261+            · exact ha₂
11911262           | inl hv₂ => cases hv₂ with
11921263             | num n₂ =>
11931264               exists .num (n₁ + n₂)
12041275           | inr h₂ =>
12051276             obtain ⟨a₂', ha₂⟩ := h₂
12061277             exists .minus (.num n₁) a₂'
1207-            exact .minusRight (.num n₁) ha₂
1278+            apply AStep.minusRight
1279+            · apply IsAValue.num
1280+            · exact ha₂
12081281           | inl hv₂ => cases hv₂ with
12091282             | num n₂ =>
12101283               exists .num (n₁ - n₂)
12211294           | inr h₂ =>
12221295             obtain ⟨a₂', ha₂⟩ := h₂
12231296             exists .mult (.num n₁) a₂'
1224-            exact .multRight (.num n₁) ha₂
1297+            apply AStep.multRight
1298+            · apply IsAValue.num
1299+            · exact ha₂
12251300           | inl hv₂ => cases hv₂ with
12261301             | num n₂ =>
12271302               exists .num (n₁ * n₂)
13231398 example :
13241399     (Bexp.le (.plus (.num 1) (.num 1)) (.num 3))
13251400       ⟶b (.le (.num 2) (.num 3)) := by
1326-  exact .leLeft (.plus 1 1)
1401+  apply BStep.leLeft
1402+  apply AStep.plus
13271403 
13281404 --   ----------------------------------------
13291405 
15541630 theorem anstep_not_deterministic : ¬ Deterministic ANStep := by
15551631   intro hd
15561632   have s₁ : ANStep (.plus (.plus (.num 1) (.num 1)) (.plus (.num 2) (.num 2)))
1557-      (.plus (.num 2) (.plus (.num 2) (.num 2))) :=
1558-    .plusLeft (.plus 1 1)
1633+      (.plus (.num 2) (.plus (.num 2) (.num 2))) := by
1634+    exact .plusLeft (.plus 1 1)
15591635   have s₂ : ANStep (.plus (.plus (.num 1) (.num 1)) (.plus (.num 2) (.num 2)))
1560-      (.plus (.plus (.num 1) (.num 1)) (.num 4)) :=
1561-    .plusRight (.plus 2 2)
1636+      (.plus (.plus (.num 1) (.num 1)) (.num 4)) := by
1637+    exact .plusRight (.plus 2 2)
15621638   have heq := hd _ _ _ s₁ s₂
15631639   simp at heq
15641640 
16081684     (h : Multi AStep a a') : Multi ANStep a a' := by
16091685   induction h with
16101686   | refl x => exact .refl x
1611-  | step x y z h₁ _ ih => exact .step x y z (astep_imp_anstep x y h₁) ih
1687+  | step x y z h₁ _ ih =>
1688+      apply Multi.step (y := y)
1689+      · apply astep_imp_anstep
1690+        exact h₁
1691+      · exact ih
16121692 
16131693 --  ### Exercise (3 stars): astep_anstep_agree ⭐⭐⭐
16141694 
17101790     | num n =>
17111791         intro p stk
17121792         simp only [compile, Aexp.eval]
1713-        exact multi_single _ _ _ (StackStep.push p stk n)
1793+        apply multi_single
1794+        apply StackStep.push
17141795     | plus a₁ a₂ ih₁ ih₂ =>
17151796         intro p stk
17161797         simp only [compile, Aexp.eval, List.append_assoc]
1717-        exact multi_trans _ _ _ _ (ih₁ _ stk)
1718-          (multi_trans _ _ _ _ (ih₂ _ (a₁.eval :: stk))
1719-            (multi_single _ _ _ (StackStep.plus p stk a₂.eval a₁.eval)))
1798+        apply multi_trans _ _ _ _ (ih₁ _ stk)
1799+        apply multi_trans _ _ _ _ (ih₂ _ (a₁.eval :: stk))
1800+        apply multi_single
1801+        apply StackStep.plus
17201802     | minus a₁ a₂ ih₁ ih₂ =>
17211803         intro p stk
17221804         simp only [compile, Aexp.eval, List.append_assoc]
1723-        exact multi_trans _ _ _ _ (ih₁ _ stk)
1724-          (multi_trans _ _ _ _ (ih₂ _ (a₁.eval :: stk))
1725-            (multi_single _ _ _ (StackStep.minus p stk a₂.eval a₁.eval)))
1805+        apply multi_trans _ _ _ _ (ih₁ _ stk)
1806+        apply multi_trans _ _ _ _ (ih₂ _ (a₁.eval :: stk))
1807+        apply multi_single
1808+        apply StackStep.minus
17261809     | mult a₁ a₂ ih₁ ih₂ =>
17271810         intro p stk
17281811         simp only [compile, Aexp.eval, List.append_assoc]
1729-        exact multi_trans _ _ _ _ (ih₁ _ stk)
1730-          (multi_trans _ _ _ _ (ih₂ _ (a₁.eval :: stk))
1731-            (multi_single _ _ _ (StackStep.mult p stk a₂.eval a₁.eval)))
1812+        apply multi_trans _ _ _ _ (ih₁ _ stk)
1813+        apply multi_trans _ _ _ _ (ih₂ _ (a₁.eval :: stk))
1814+        apply multi_single
1815+        apply StackStep.mult
17321816   have hfin := gen a [] []
17331817   simp only [List.append_nil] at hfin
17341818   exact hfin
18291913   · normalize using SimpleArith
18301914   · constructor
18311915 
1832--- Source revision: 2ca0e09, committed 2026-10-23 15:44 UTC
1916+-- Source revision: a06e066, committed 2026-10-27 16:51 UTC

TS/Stlc.lean

575575   simp [subst, h]
576576 
577577 @[simp] theorem subst_app :
578-    <{ [x := s] (t₁ t₂) }> = <{ ([x := s] t₁) ([x := s] t₂) }> := rfl
579-
580-@[simp] theorem subst_tru : <{ [x := s] true }> = <{ true }> := rfl
581-
582-@[simp] theorem subst_fls : <{ [x := s] false }> = <{ false }> := rfl
578+    <{ [x := s] (t₁ t₂) }> = <{ ([x := s] t₁) ([x := s] t₂) }> := by rfl
579+
580+@[simp] theorem subst_tru : <{ [x := s] true }> = <{ true }> := by rfl
581+
582+@[simp] theorem subst_fls : <{ [x := s] false }> = <{ false }> := by rfl
583583 
584584 @[simp] theorem subst_ite :
585585     <{ [x := s] (if t₁ then t₂ else t₃) }> =
586-      <{ if [x := s] t₁ then [x := s] t₂ else [x := s] t₃ }> := rfl
586+      <{ if [x := s] t₁ then [x := s] t₂ else [x := s] t₃ }> := by rfl
587587 
588588 --   ----------------------------------------
589589 
12511251 
12521252 end Stlc
12531253 
1254--- Source revision: 2ca0e09, committed 2026-10-23 15:44 UTC
1254+-- Source revision: a06e066, committed 2026-10-27 16:51 UTC

TS/StlcProp.lean

101101     -- `t = t₁ t₂`.  Proceed by cases on whether `t₁` is a value or steps.
102102     subst hΓ
103103     right
104-    cases ih₁ rfl with
104+    cases ih₁ (by rfl) with
105105     | inl hv₁ =>
106-      cases ih₂ rfl with
106+      cases ih₂ (by rfl) with
107107       | inl hv₂ =>
108108         obtain ⟨x, u, rfl⟩ := canonical_forms_fun t₁ _ _ h₁ hv₁
109109         exists <{ [x := t₂] u }>
120120   | ite Γ t₁ t₂ t₃ τ₁ h₁ h₂ h₃ ih₁ ih₂ ih₃ =>
121121     subst hΓ
122122     right
123-    cases ih₁ rfl with
123+    cases ih₁ (by rfl) with
124124     | inl hv₁ =>
125125       cases canonical_forms_bool t₁ h₁ hv₁ with
126126       | inl he =>
14101410   simp [subst, h]
14111411 
14121412 @[simp] theorem subst_app :
1413-    <{ [x := s] (t₁ t₂) }> = <{ ([x := s] t₁) ([x := s] t₂) }> := rfl
1414-
1415-@[simp] theorem subst_const : <{ [x := s] ~(Tm.const n) }> = .const n := rfl
1413+    <{ [x := s] (t₁ t₂) }> = <{ ([x := s] t₁) ([x := s] t₂) }> := by rfl
1414+
1415+@[simp] theorem subst_const : <{ [x := s] ~(Tm.const n) }> = .const n := by rfl
14161416 
14171417 @[simp] theorem subst_succ :
1418-    <{ [x := s] (succ t₁) }> = <{ succ ([x := s] t₁) }> := rfl
1418+    <{ [x := s] (succ t₁) }> = <{ succ ([x := s] t₁) }> := by rfl
14191419 
14201420 @[simp] theorem subst_pred :
1421-    <{ [x := s] (pred t₁) }> = <{ pred ([x := s] t₁) }> := rfl
1421+    <{ [x := s] (pred t₁) }> = <{ pred ([x := s] t₁) }> := by rfl
14221422 
14231423 @[simp] theorem subst_mult :
1424-    <{ [x := s] (t₁ * t₂) }> = <{ ([x := s] t₁) * ([x := s] t₂) }> := rfl
1424+    <{ [x := s] (t₁ * t₂) }> = <{ ([x := s] t₁) * ([x := s] t₂) }> := by rfl
14251425 
14261426 @[simp] theorem subst_ite0 :
14271427     <{ [x := s] (if0 t₁ then t₂ else t₃) }> =
1428-      <{ if0 [x := s] t₁ then [x := s] t₂ else [x := s] t₃ }> := rfl
1428+      <{ if0 [x := s] t₁ then [x := s] t₂ else [x := s] t₃ }> := by rfl
14291429 end
14301430 
14311431 --  Next, the values.
18101810   | app Γ τ₁ τ₂ t₁ t₂ h₁ h₂ ih₁ ih₂ =>
18111811     right
18121812     subst hΓ
1813-    cases ih₁ rfl with
1813+    cases ih₁ (by rfl) with
18141814     | inl hv₁ =>
1815-      cases ih₂ rfl with
1815+      cases ih₂ (by rfl) with
18161816       | inl hv₂ =>
18171817         -- `t₁` is a value of arrow type, so it is an abstraction, not a number.
18181818         cases hv₁ with
18331833   | succ Γ t₁ h ih =>
18341834     right
18351835     subst hΓ
1836-    cases ih rfl with
1836+    cases ih (by rfl) with
18371837     | inl hv =>
18381838       cases hv with
18391839       | abs => cases h
18481848   | pred Γ t₁ h ih =>
18491849     right
18501850     subst hΓ
1851-    cases ih rfl with
1851+    cases ih (by rfl) with
18521852     | inl hv =>
18531853       cases hv with
18541854       | abs => cases h
18631863   | mult Γ t₁ t₂ h₁ h₂ ih₁ ih₂ =>
18641864     right
18651865     subst hΓ
1866-    cases ih₁ rfl with
1866+    cases ih₁ (by rfl) with
18671867     | inl hv₁ =>
1868-      cases ih₂ rfl with
1868+      cases ih₂ (by rfl) with
18691869       | inl hv₂ =>
18701870         cases hv₁ with
18711871         | abs => cases h₁
18871887   | ite0 Γ t₁ t₂ t₃ τ₀ h₁ h₂ h₃ ih₁ ih₂ ih₃ =>
18881888     right
18891889     subst hΓ
1890-    cases ih₁ rfl with
1890+    cases ih₁ (by rfl) with
18911891     | inl hv₁ =>
18921892       cases hv₁ with
18931893       | abs => cases h₁
19091909 
19101910 end StlcArith
19111911 
1912--- Source revision: 2ca0e09, committed 2026-10-23 15:44 UTC
1912+-- Source revision: a06e066, committed 2026-10-27 16:51 UTC

TS/Sub.lean

14631463   induction h with (subst_vars; try contradiction)
14641464   | refl => rfl
14651465   | trans h₁ h₂ ih₁ ih₂ =>
1466-      rw [ih₁]; apply ih₂ rfl
1467-      symm; apply ih₂ rfl
1466+      rw [ih₁]; apply ih₂ (by rfl)
1467+      symm; apply ih₂ (by rfl)
14681468 
14691469 --  ### Exercise (3 stars): sub_inversion_arrow ⭐⭐⭐
14701470 
14801480   | @arrow σ₁ σ₂ _ _ h₁ h₂ ih₁ ih₂ =>
14811481       inversion heq; exists σ₁, σ₂
14821482   | trans h₁ h₂ ih₁ ih₂ =>
1483-      obtain ⟨σ₁, σ₂, _, hs₁, hs₂⟩ := ih₂ rfl; clear ih₂; subst_vars
1484-      obtain ⟨σ₁', σ₂', _, hs₁', hs₂'⟩ := ih₁ rfl; subst_vars; clear ih₁
1483+      obtain ⟨σ₁, σ₂, _, hs₁, hs₂⟩ := ih₂ (by rfl); clear ih₂; subst_vars
1484+      obtain ⟨σ₁', σ₂', _, hs₁', hs₂'⟩ := ih₁ (by rfl); subst_vars; clear ih₁
14851485       exists σ₁', σ₂'; constructor; rfl; constructor
14861486       · exact Subtype.trans hs₁ hs₁'
14871487       · exact Subtype.trans hs₂' hs₂
15001500   induction h with (subst_vars; try contradiction)
15011501   | refl => rfl
15021502   | trans h₁ h₂ ih₁ ih₂ =>
1503-      rw [ih₁]; apply ih₂ rfl
1504-      symm; apply ih₂ rfl
1503+      rw [ih₁]; apply ih₂ (by rfl)
1504+      symm; apply ih₂ (by rfl)
15051505 
15061506 --  ### Exercise (2 stars): sub_inversion_base (Optional) ⭐⭐
15071507 
15101510   induction h with (subst_vars; try contradiction)
15111511   | refl => rfl
15121512   | trans h₁ h₂ ih₁ ih₂ =>
1513-      rw [ih₁]; apply ih₂ rfl
1514-      symm; apply ih₂ rfl
1513+      rw [ih₁]; apply ih₂ (by rfl)
1514+      symm; apply ih₂ (by rfl)
15151515 
15161516 --  ### Exercise (2 stars): sub_inversion_top (Optional) ⭐⭐
15171517 
15211521   | refl => rfl
15221522   | top => rfl
15231523   | trans h₁ h₂ ih₁ ih₂ =>
1524-      rw [ih₂]; apply ih₁ rfl
1525-      symm; apply ih₁ rfl
1524+      rw [ih₂]; apply ih₁ (by rfl)
1525+      symm; apply ih₁ (by rfl)
15261526 
15271527 --  (End of exercise)
15281528 
15391539   | @prod σ₁ σ₂ _ _ h₁ h₂ ih₁ ih₂ =>
15401540       inversion heq; exists σ₁, σ₂
15411541   | trans h₁ h₂ ih₁ ih₂ =>
1542-      obtain ⟨σ₁, σ₂, _, hs₁, hs₂⟩ := ih₂ rfl; clear ih₂; subst_vars
1543-      obtain ⟨σ₁', σ₂', _, hs₁', hs₂'⟩ := ih₁ rfl; subst_vars; clear ih₁
1542+      obtain ⟨σ₁, σ₂, _, hs₁, hs₂⟩ := ih₂ (by rfl); clear ih₂; subst_vars
1543+      obtain ⟨σ₁', σ₂', _, hs₁', hs₂'⟩ := ih₁ (by rfl); subst_vars; clear ih₁
15441544       exists σ₁', σ₂'; constructor; rfl; constructor
15451545       · exact Subtype.trans hs₁' hs₁
15461546       · exact Subtype.trans hs₂' hs₂
15811581   | abs Γ x τ₁ τ₂ t₁ h ih => inversion heq; exists x, τ₂, t₁
15821582   | sub Γ t₁ τ₁ τ₂ ht hs ih =>
15831583       obtain ⟨σ₁, σ₂, _, hs₁, hs₂⟩ := sub_inversion_arrow hs; subst_vars
1584-      exact ih hv rfl
1584+      apply ih hv
1585+      rfl
15851586 
15861587 --  (End of exercise)
15871588 
15971598   induction ht with (subst_vars; first | trivial | try lia)
15981599   | sub Γ t₁ τ₁ τ₂ ht hs ih =>
15991600     apply sub_inversion_bool at hs; subst_vars
1600-    exact ih hv rfl
1601+    apply ih hv
1602+    rfl
16011603 
16021604 --  When you do the `products` exercise, add your canonical forms lemma for
16031605 --  products here:
16111613     | pair Γ t₁ t₂ τ₁ τ₂ h ih => inversion heq; exists t₁, t₂
16121614     | sub Γ t₁ τ₁ τ₂ ht hs ih =>
16131615         obtain ⟨σ₁, σ₂, _, hs₁, hs₂⟩ := sub_inversion_prod hs; subst_vars
1614-        exact ih hv rfl
1616+        apply ih hv
1617+        rfl
16151618 
16161619 --  ### Progress
16171620 
16671670     | try (left; constructor; done)
16681671   )
16691672   | app Γ τ₁ τ₂ t₁ t₂ h₁ h₂ ih₁ ih₂ =>
1670-      right; cases ih₁ rfl with
1673+      right; cases ih₁ (by rfl) with
16711674       -- t₁ is a value
16721675       | inl ht₁ =>
1673-        cases ih₂ rfl with
1676+        cases ih₂ (by rfl) with
16741677         -- t₂ is a value
16751678         | inl ht₂ =>
16761679           apply canonical_forms_of_arrow_types at h₁
16861689         obtain ⟨t₁', ht₁⟩ := ht₁
16871690         exists <{t₁' t₂}>; apply_rules using StlcSubEval
16881691   | ite Γ t₁ t₂ t₃ τ h₁ h₂ h₃ ih₁ ih₂ ih₃ =>
1689-    right; cases ih₁ rfl with
1692+    right; cases ih₁ (by rfl) with
16901693     -- t₁ is a value
16911694     | inl ht₁ =>
16921695       apply canonical_forms_of_bool at h₁
17001703   | sub Γ t₁ τ₁ τ₂ ht hs ih => apply ih; rfl
17011704 -- Fill in products here later
17021705   | pair Γ t₁ t₂ τ₁ τ₂ h₁ h₂ ih₁ ih₂ =>
1703-      cases ih₁ rfl with
1706+      cases ih₁ (by rfl) with
17041707       -- t₁ is a value
17051708       | inl ht₁ =>
1706-        cases ih₂ rfl with
1709+        cases ih₂ (by rfl) with
17071710         -- t₂ is a value
17081711         | inl ht₂ =>
17091712           left; apply_rules using StlcSubEval
17161719         obtain ⟨t₁', ht₁⟩ := ht₁
17171720         right; exists <{(t₁', t₂)}>; apply_rules using StlcSubEval
17181721   | fst Γ t τ₁ τ₂ h ih =>
1719-      right; cases ih rfl with
1722+      right; cases ih (by rfl) with
17201723       -- t₁ is a value
17211724       | inl ht₁ =>
17221725         apply canonical_forms_of_product_types at h
17271730         obtain ⟨t₁', ht₁⟩ := ht₁
17281731         exists <{fst t₁'}>; apply_rules using StlcSubEval
17291732   | snd Γ t τ₁ τ₂ h ih =>
1730-      right; cases ih rfl with
1733+      right; cases ih (by rfl) with
17311734       -- t₁ is a value
17321735       | inl ht₁ =>
17331736         apply canonical_forms_of_product_types at h
17841787   | abs Γ x τ₁ τ₂ t₁ h i =>
17851788       inversion heq; exists τ₁; solve_by_elim using StlcSubTyping
17861789   | sub Γ t₁ τ₁ τ₂ ht hs ih =>
1787-      obtain ⟨σ₂, hs', ht'⟩ := ih rfl
1790+      obtain ⟨σ₂, hs', ht'⟩ := ih (by rfl)
17881791       exists σ₂; solve_by_elim using StlcSubTyping
17891792 
17901793 --  ### Exercise (3 stars): typing_inversion_var (Optional) ⭐⭐⭐
17971800   induction h with (subst_vars; try contradiction)
17981801   | var Γ y τ₁ h => inversion heq; solve_by_elim using StlcSubTyping
17991802   | sub Γ t₁ τ₁ τ₂ ht hs ih =>
1800-      obtain ⟨σ₂, hs', ht'⟩ := ih rfl
1803+      obtain ⟨σ₂, hs', ht'⟩ := ih (by rfl)
18011804       exists σ₂; solve_by_elim using StlcSubTyping
18021805 
18031806 --  ### Exercise (3 stars): typing_inversion_app (Optional) ⭐⭐⭐
18091812   induction h with (subst_vars; try contradiction)
18101813   | app => inversion heq; solve_by_elim using StlcSubTyping
18111814   | sub Γ t₁ τ₁ τ₂ ht hs ih =>
1812-      obtain ⟨σ₂, hs', ht'⟩ := ih rfl
1815+      obtain ⟨σ₂, hs', ht'⟩ := ih (by rfl)
18131816       exists σ₂; constructor <;> try assumption
18141817       apply HasType.sub _ _ _ _ hs'
18151818       solve_by_elim using StlcSubTyping
18241827   induction h with (subst_vars; try contradiction)
18251828   | unit => inversion heq; solve_by_elim using StlcSubTyping
18261829   | sub Γ t₁ τ₁ τ₂ ht hs ih =>
1827-      specialize ih rfl
1830+      specialize ih (by rfl)
18281831       solve_by_elim using StlcSubTyping
18291832 
18301833 --  -- Add your lemmas for products here when you get to that exercise
18381841     | pair Γ t₁ t₂ τ₁ τ₂ h₁ h₂ ih₁ ih₂ =>
18391842         inversion heq; exists τ₁, τ₂; solve_by_elim using StlcSubTyping
18401843     | sub Γ t₁ τ₁ τ₂ ht hs ih =>
1841-      obtain ⟨σ₁, σ₂, hs', ht₁, ht₂⟩ := ih rfl
1844+      obtain ⟨σ₁, σ₂, hs', ht₁, ht₂⟩ := ih (by rfl)
18421845       exists σ₁, σ₂; solve_by_elim (maxDepth := 10) using StlcSubTyping
18431846 
18441847 theorem typing_inversion_fst {Γ : Context} {t : Tm} {τ: Ty}
18511854     | fst Γ t τ₁ τ₂ h ih =>
18521855         inversion heq; exists τ₁, τ₂; solve_by_elim using StlcSubTyping
18531856     | sub Γ t₁ τ₁ τ₂ ht hs ih =>
1854-      obtain ⟨σ₁, σ₂, hs', ht'⟩ := ih rfl
1857+      obtain ⟨σ₁, σ₂, hs', ht'⟩ := ih (by rfl)
18551858       exists σ₁, σ₂; solve_by_elim using StlcSubTyping
18561859 
18571860 theorem typing_inversion_snd {Γ : Context} {t : Tm} {τ: Ty}
18641867   | snd Γ t τ₁ τ₂ h ih =>
18651868       inversion heq; exists τ₁, τ₂; solve_by_elim using StlcSubTyping
18661869   | sub Γ t₁ τ₁ τ₂ ht hs ih =>
1867-    obtain ⟨σ₁, σ₂, hs', ht'⟩ := ih rfl
1870+    obtain ⟨σ₁, σ₂, hs', ht'⟩ := ih (by rfl)
18681871     exists σ₁, σ₂; solve_by_elim using StlcSubTyping
18691872 
18701873 --  The inversion lemmas for typing and for subtyping between arrow types
23822385 
23832386 end StlcSub
23842387 
2385--- Source revision: 2ca0e09, committed 2026-10-23 15:44 UTC
2388+-- Source revision: a06e066, committed 2026-10-27 16:51 UTC

TS/Types.lean

13051305 --      throughout (and maybe in Smallstep and Imp?)... `dev` block headers
13061306 --      too, if we want to be really consistent.
13071307 
1308--- Source revision: 2ca0e09, committed 2026-10-23 15:44 UTC
1308+-- 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