TS Student source diff

Switch volume / audience

LF/Typeclasses.lean

15811581 
15821582 end Reflection
15831583 
1584--- Source revision: 2ca0e09, committed 2026-10-23 15:44 UTC
1584+-- 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

20412041     )
20422042     | var => contradiction
20432043     | app Γ τ₁ τ₂ t₁ t₂ h₁ h₂ ih₁ ih₂ =>
2044-      right; cases ih₁ rfl
2044+      right; cases ih₁ (by rfl)
20452045       -- t₁ is a value
20462046       case _ ht₁ =>
2047-        cases ih₂ rfl
2047+        cases ih₂ (by rfl)
20482048         -- t₂ is a value
20492049         case _ ht₂ =>
20502050           apply canonical_forms_fun at h₁
20602060         obtain ⟨t₁', ht₁⟩ := ht₁
20612061         exists <{t₁' t₂}>; apply_rules using ExtStlcEval
20622062     | succ Γ t₁ h ih =>
2063-      right; cases ih rfl
2063+      right; cases ih (by rfl)
20642064       -- t₁ is a value
20652065       case _ ht₁ =>
20662066         apply canonical_forms_nat at h
20712071         obtain ⟨t₁', ht₁⟩ := ht₁
20722072         exists <{succ t₁'}>; apply_rules using ExtStlcEval
20732073     | pred Γ t₁ h ih =>
2074-      right; cases ih rfl
2074+      right; cases ih (by rfl)
20752075        -- t₁ is a value
20762076       case _ ht₁ =>
20772077         apply canonical_forms_nat at h
20812081         obtain ⟨t₁', ht₁⟩ := ht₁
20822082         exists <{pred t₁'}>; apply_rules using ExtStlcEval
20832083     | mult Γ t₁ t₂ h₁ h₂ ih₁ ih₂ =>
2084-      right; cases ih₁ rfl
2084+      right; cases ih₁ (by rfl)
20852085       -- t₁ is a value
20862086       case _ ht₁ =>
2087-        cases ih₂ rfl
2087+        cases ih₂ (by rfl)
20882088         -- t₂ is a value
20892089         case _ ht₂ =>
20902090           apply canonical_forms_nat at h₁
21022102         obtain ⟨t₁', ht₁⟩ := ht₁
21032103         exists <{t₁' * t₂}>; apply_rules using ExtStlcEval
21042104     | ite0 Γ t₁ t₂ t₃ τ h₁ h₂ h₃ ih₁ ih₂ ih₃ =>
2105-      right; cases ih₁ rfl
2105+      right; cases ih₁ (by rfl)
21062106       -- t₁ is a value
21072107       case _ ht₁ =>
21082108         apply canonical_forms_nat at h₁
21152115         obtain ⟨t₁', ht₁⟩ := ht₁
21162116         exists <{if0 t₁' then t₂ else t₃}>; apply_rules using ExtStlcEval
21172117     | sumInl Γ t₁ τ₁ τ₂ h ih =>
2118-      cases ih rfl
2118+      cases ih (by rfl)
21192119       -- t₁ is a value
21202120       case _ ht₁ =>
21212121         left; apply_rules using ExtStlcEval
21242124         obtain ⟨t₁', ht₁⟩ := ht₁
21252125         right; exists <{inl τ₂ t₁'}>; apply_rules using ExtStlcEval
21262126     | sumInr Γ t₂ τ₁ τ₂ h ih =>
2127-      cases ih rfl
2127+      cases ih (by rfl)
21282128       -- t₁ is a value
21292129       case _ ht₁ =>
21302130         left; apply_rules using ExtStlcEval
21332133         obtain ⟨t₂', ht₁⟩ := ht₁
21342134         right; exists <{inr τ₁ t₂'}>; apply_rules using ExtStlcEval
21352135     | sumCase Γ x₁ x₂ τ₁ τ₂ τ₃ t t₁ t₂ h₁ h₂ h₃ ih₁ ih₂ ih₃ =>
2136-      right; cases ih₁ rfl
2136+      right; cases ih₁ (by rfl)
21372137       -- t₁ is a value
21382138       case _ ht =>
21392139         apply canonical_forms_sum at h₁
21452145         obtain ⟨t', ht⟩ := ht
21462146         exists <{case t' of inl x₁ => t₁ | inr x₂ => t₂}>; apply_rules using ExtStlcEval
21472147     | listCons Γ t₁ t₂ τ₁ h₁ h₂ ih₁ ih₂ =>
2148-      cases ih₁ rfl
2148+      cases ih₁ (by rfl)
21492149       -- t₁ is a value
21502150       case _ ht₁ =>
2151-        cases ih₂ rfl
2151+        cases ih₂ (by rfl)
21522152         -- t₂ is a value
21532153         case _ ht₂ =>
21542154           left; apply_rules using ExtStlcEval
21612161         obtain ⟨t₁', ht₁⟩ := ht₁
21622162         right; exists <{t₁' :: t₂}>; apply_rules using ExtStlcEval
21632163     | listCase Γ t₁ t₂ t₃ x₁ x₂ τ₁ τ₂ h₁ h₂ h₃ ih₁ ih₂ ih₃ =>
2164-        right; cases ih₁ rfl
2164+        right; cases ih₁ (by rfl)
21652165         -- t₁ is a value
21662166         case _ ht =>
21672167           apply canonical_forms_list at h₁
22562256 
22572257 end StlcExtended
22582258 
2259--- Source revision: 2ca0e09, committed 2026-10-23 15:44 UTC
2259+-- 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 
69156 --  was supported, in part, by the National Science Foundation under the
70157 --  NSF Expeditions grant 1521523, *The Science of Deep Specification*.
71158 
72--- Source revision: 2ca0e09, committed 2026-10-23 15:44 UTC
159+-- 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+--  ### Null References
706+
707+--  There is one final significant difference between our references and
708+--  C-style mutable variables: in C-like languages, variables holding
709+--  pointers into the heap may sometimes have the value `NULL`.
710+--  Dereferencing such a "null pointer" is an error, and results either in
711+--  a clean exception (Java and C#) or in arbitrary and possibly insecure
712+--  behavior (C and relatives like C++). Null pointers cause significant
713+--  trouble in C-like languages: the fact that any pointer might be null
714+--  means that any dereference operation in the program can potentially
715+--  fail.
716+--
717+--  Even in ML-like languages, there are sometimes situations where we may
718+--  or may not have a valid pointer in our hands. Fortunately, there is no
719+--  need to extend the basic mechanisms of references to represent such
720+--  situations: the sum types introduced in the MoreStlc chapter already
721+--  give us what we need.
722+--
723+--  First, we can use sums to build an analog of the `option` types
724+--  introduced in the Lists chapter of *Logical Foundations*. Define
725+--  `Option τ` to be an abbreviation for `Unit + τ`.
726+--
727+--  Then a "nullable reference to a `τ`" is simply an element of the type
728+--  `Option (Ref τ)`.
729+
730+--  ### Garbage Collection
731+
732+--  A last issue that we should mention before we move on with formalizing
733+--  references is storage *de*-allocation. We have not provided any
734+--  primitives for freeing reference cells when they are no longer needed.
735+--  Instead, like many modern languages (including OCaml, Haskell, Java,
736+--  etc.), we rely on the run-time system to perform *garbage collection*,
737+--  automatically identifying and reusing cells that can no longer be
738+--  reached by the program.
739+--
740+--  This is *not* just a question of taste in language design: it is
741+--  extremely difficult to achieve type safety in the presence of an
742+--  explicit deallocation operation.
743+--
744+--  One reason for this is the familiar *dangling reference* problem: we
745+--  allocate a cell holding a number, save a reference to it in some data
746+--  structure, use it for a while, then deallocate it and allocate a new
747+--  cell holding a boolean, possibly reusing the same storage. Now we can
748+--  have two names for the same storage cell — one with type `Ref Nat` and
749+--  the other with type `Ref Bool`.
750+
751+--  ### Exercise (2 stars): type_safety_violation (Manually graded) ⭐⭐
752+
753+--  Show how this can lead to a violation of type safety.
754+
755+--  ## Operational Semantics
756+
757+--  ### Locations
758+
759+--  The most subtle aspect of the treatment of references appears when we
760+--  consider how to formalize their operational behavior. One way to see
761+--  why is to ask, "What should be the *values* of type `Ref τ`?" The
762+--  crucial observation that we need to take into account is that reducing
763+--  a `ref` operator should *do* something — namely, allocate some storage
764+--  — and the result of the operation should be a reference to this
765+--  storage.
766+--
767+--  What, then, is a reference?
768+--
769+--  The run-time store in most programming-language implementations is
770+--  essentially just a big array of bytes. The run-time system keeps track
771+--  of which parts of this array are currently in use. When we need to
772+--  allocate a new reference cell, we allocate a large enough segment from
773+--  the free region of the store (4 bytes for integer cells, 8 bytes for
774+--  cells storing `Float`s, etc.), record somewhere that it is being used,
775+--  and return the index (typically, a 32- or 64-bit integer) of the start
776+--  of the newly allocated region. These indices are references.
777+--
778+--  For present purposes, there is no need to be quite so concrete. We can
779+--  think of the store as an array of *values*, rather than an array of
780+--  bytes, abstracting away from the different sizes of the run-time
781+--  representations of different values. A reference, then, is simply an
782+--  index into the store. (If we like, we can even abstract away from the
783+--  fact that these indices are numbers, but for purposes of formalization
784+--  in Lean it is convenient to use numbers.) We use the word *location*
785+--  instead of *reference* or *pointer* to emphasize this abstract quality.
786+--
787+--  Treating locations abstractly in this way will prevent us from modeling
788+--  the *pointer arithmetic* found in low-level languages such as C. This
789+--  limitation is intentional. While pointer arithmetic is occasionally
790+--  very useful, especially for implementing low-level services such as
791+--  garbage collectors, it cannot be tracked by most type systems: knowing
792+--  that location `n` in the store contains a `Float` doesn't tell us
793+--  anything useful about the type of location `n+4`. In C, pointer
794+--  arithmetic is a notorious source of type-safety violations.
795+
796+--  ### Stores
797+
798+--  Recall that, in the small-step operational semantics for Imp, the step
799+--  relation needed to carry along an auxiliary state in addition to the
800+--  program being executed. In the same way, once we have added reference
801+--  cells to the STLC, our step relation must carry along a store to keep
802+--  track of the contents of reference cells.
803+--
804+--  We could re-use the same functional representation we used for states
805+--  in Imp, but for carrying out the proofs in this chapter it is actually
806+--  more convenient to represent a store simply as a *list* of values. (The
807+--  reason we didn't use this representation before is that, in Imp, a
808+--  program could modify any location at any time, so states had to be
809+--  ready to map *any* variable to a value. However, in the STLC with
810+--  references, the only way to create a reference cell is with `ref t₁`,
811+--  which puts the value of `t₁` in a new reference cell and reduces to the
812+--  location of the newly created reference cell. When reducing such an
813+--  expression, we can just add a new reference cell to the end of the list
814+--  representing the store.)
815+
816+abbrev Store := List Tm
817+
818+--  We use `ρ[n]` to retrieve the value of the reference cell at location
819+--  `n` in the store `ρ`. Note that we must give a default value to `nth`
820+--  in case we try looking up an index which is too large. (In fact, we
821+--  never actually do this, but *proving* that we don't will require a bit
822+--  of work.)
823+
824+open scoped MyGetElem
825+instance : MyGetElem Store Nat Tm where
826+  getElem ρ n := ρ.getD n <{unit}>
827+
828+@[simp]
829+theorem Store_get_succ_tl (hd : Tm) (tl : Store) (n : Nat) :
830+  (hd :: tl)[n + 1] = tl[n] := by rfl
831+
832+@[simp]
833+theorem Store_get_zero_hd (hd : Tm) (tl : Store) :
834+  (hd :: tl)[0] = hd := by rfl
835+
836+--  To update the store, we use the `List.set` function, which replaces the
837+--  contents of a cell at a particular index.
838+--
839+--      def List.set : (l : List α) → (n : Nat) → (a : α) → List α
840+--        | cons _ as, 0,          b => cons b as
841+--        | cons a as, Nat.succ n, b => cons a (set as n b)
842+--        | nil,       _,          _ => nil
843+--
844+--  As might be expected, we will also need some technical lemmas; they are
845+--  straightforward to prove.
846+
847+theorem Store_get_set_eq (ρ : Store) (l : Nat) (x : Tm)
848+  (h : l < ρ.length) :
849+  (ρ.set l x)[l] = x := by
850+  induction ρ generalizing l with
851+  | nil => simp_all
852+  | cons hd tl ih => cases l <;> simp_all
853+
854+theorem Store_get_set_neq (l₁ l₂ : Nat) (t : Tm) (ρ : Store) :
855+  l₁ ≠ l₂ ->
856+  (ρ.set l₂ t)[l₁] = ρ[l₁] := by
857+  induction ρ generalizing l₁ l₂ with
858+  | nil => simp
859+  | cons hd tl ih => cases l₁ <;> cases l₂ <;> simp_all
860+
861+--  ### Reduction
862+
863+--  Next, we need to extend the operational semantics to take stores into
864+--  account. Since the result of reducing an expression will in general
865+--  depend on the contents of the store in which it is reduced, the
866+--  evaluation rules should take not just a term but also a store as
867+--  argument. Furthermore, since the reduction of a term can cause side
868+--  effects on the store, and these may affect the reduction of other terms
869+--  in the future, the reduction rules need to return a new store. Thus,
870+--  the shape of the single-step reduction relation needs to change from
871+--  `t ⟶ t'` to `t / ρ ⟶ t' / ρ'`, where `ρ` and `ρ'` are the starting and
872+--  ending states of the store.
873+--
874+--  To carry through this change, we first need to augment all of our
875+--  existing reduction rules with stores:
876+--
877+--                  value v₂
878+--      ---------------------------------- (appAbs)
879+--      (λx:τ₂,t₁) v₂ / ρ ⟶ [x:=v₂]t₁ / ρ
880+--
881+--                 t₁ / ρ ⟶ t₁' / ρ'
882+--      --------------------------------   (app₁)
883+--              t₁ t₂ / ρ ⟶ t₁' t₂ / ρ'
884+--
885+--                 value v₁
886+--                 t₂ / ρ ⟶ t₂' / ρ'
887+--      --------------------------------   (app₂)
888+--              v₁ t₂ / ρ ⟶ v₁ t₂' / ρ'
889+--
890+--  Note that the first rule here returns the store unchanged, since
891+--  function application, in itself, has no side effects. The other two
892+--  rules simply propagate side effects from premise to conclusion.
893+--
894+--  Now, the result of reducing a `ref` expression will be a fresh
895+--  location; this is why we included locations in the syntax of terms and
896+--  in the set of values. It is crucial to note that making this extension
897+--  to the syntax of terms does not mean that we intend *programmers* to
898+--  write terms involving explicit, concrete locations: such terms will
899+--  arise only as intermediate results during reduction. This may seem odd,
900+--  but it follows naturally from our design decision to represent the
901+--  result of every reduction step by a modified *term*. If we had chosen a
902+--  more "machine-like" model, e.g., with an explicit stack to contain
903+--  values of bound identifiers, then the idea of adding locations to the
904+--  set of allowed values might seem more obvious.
905+--
906+--  In terms of this expanded syntax, we can state reduction rules for the
907+--  new constructs that manipulate locations and the store. First, to
908+--  reduce a dereferencing expression `!t₁`, we must first reduce `t₁`
909+--  until it becomes a value:
910+--
911+--       t₁ / ρ ⟶ t₁' / ρ'
912+--      -------------------- (deref)
913+--      !t₁ / ρ ⟶ !t₁' / ρ'
914+--
915+--  Once `t₁` has finished reducing, we should have an expression of the
916+--  form `!l`, where `l` is some location. (A term that attempts to
917+--  dereference any other sort of value, such as a function or `unit`, is
918+--  erroneous, as is a term that tries to dereference a location that is
919+--  larger than the size ρ.length of the currently allocated store; the
920+--  reduction rules simply get stuck in this case. The type-safety
921+--  properties established below assure us that well-typed terms will never
922+--  misbehave in this way.)
923+--
924+--           l < ρ.length
925+--      ------------------------ (derefLoc)
926+--      !(loc l) / ρ ⟶ ρ[l] / ρ
927+--
928+--  Next, to reduce an assignment expression `t₁:=t₂`, we must first reduce
929+--  `t₁` until it becomes a value (a location), and then reduce `t₂` until
930+--  it becomes a value (of any sort):
931+--
932+--            t₁ / ρ ⟶ t₁' / ρ'
933+--      ------------------------------ (assign₁)
934+--      t₁ := t₂ / ρ ⟶ t₁' := t₂ / ρ'
935+--
936+--            t₂ / ρ ⟶ t₂' / ρ'
937+--      ------------------------------ (assign₂)
938+--      v₁ := t₂ / ρ ⟶ v₁ := t₂' / ρ'
939+--
940+--  Once we have finished with `t₁` and `t₂`, we have an expression of the
941+--  form `l:=v`, which we execute by updating the store to make location
942+--  `l` contain `v`:
943+--
944+--               l < ρ.length
945+--      -------------------------------- (assign)
946+--      loc l := v / ρ ⟶ unit / [l:=v]ρ
947+--
948+--  The notation `[l:=v]ρ` means "the store that maps `l` to `v` and maps
949+--  all other locations to the same thing as `ρ`". Note that the term
950+--  resulting from this reduction step is just `unit`; the interesting
951+--  result is the updated store.
952+--
953+--  Finally, to reduce an expression of the form `ref t₁`, we first reduce
954+--  `t₁` until it becomes a value:
955+--
956+--          t₁ / ρ ⟶ t₁' / ρ'
957+--      -------------------------- (ref)
958+--      ref t₁ / ρ ⟶ ref t₁' / ρ'
959+--
960+--  Then, to reduce the `ref` itself, we choose a fresh location at the end
961+--  of the current store — i.e., location `ρ.length` — and yield a new
962+--  store that extends `ρ` with the new value `v`.
963+--
964+--      -------------------------------- (refValue)
965+--      ref v / ρ ⟶ loc ρ.length / ρ, v
966+--
967+--  The value resulting from this step is the newly allocated location
968+--  itself. (Formally, `ρ, v` means `ρ.concat v` — i.e., to add a new
969+--  reference cell to the store, we append it to the end.)
970+--
971+--  Note that these reduction rules do not perform any kind of garbage
972+--  collection: we simply allow the store to keep growing without bound as
973+--  reduction proceeds. This does not affect the correctness of the results
974+--  of reduction (after all, the definition of "garbage" is precisely parts
975+--  of the store that are no longer reachable and so cannot play any
976+--  further role in reduction), but it means that a naive implementation of
977+--  our evaluator might run out of memory where a more sophisticated
978+--  evaluator would be able to continue by reusing locations whose contents
979+--  have become garbage.
980+--
981+--  Here are the rules again, formally:
982+
983+section
984+set_option hygiene false in
985+local notation:40
986+  t:71 " / " ρ:41 " ⟶ " t':71 " / " ρ':41 =>
987+  Step (t, ρ) (t', ρ')
988+
989+inductive Step : Tm × Store → Tm × Store → Prop where
990+  -- pure STLC
991+  | appAbs {x : String} {τ₂ : Ty} {t₁ v₂ : Tm} {ρ : Store}
992+      (h : v₂.IsValue) :
993+      <{(λ x : τ₂ . t₁) v₂}> / ρ ⟶
994+      <{ [x := v₂] t₁ }> / ρ
995+  | app₁ {t₁ t₁' t₂ : Tm} {ρ ρ' : Store}
996+      (h : t₁ / ρ ⟶ t₁' / ρ') :
997+      <{t₁ t₂}> / ρ ⟶ <{t₁' t₂}> / ρ'
998+  | app₂ {v₁ t₂ t₂' : Tm} {ρ ρ' : Store}
999+      (h₁ : v₁.IsValue)
1000+      (h₂ : t₂ / ρ ⟶ t₂' / ρ') :
1001+      <{v₁ t₂}> / ρ ⟶ <{v₁ t₂'}> / ρ'
1002+  -- numbers
1003+  | succNat {n : Nat} {ρ : Store} :
1004+      <{ succ ~(Tm.const n) }> / ρ ⟶ Tm.const (n + 1) / ρ
1005+  | succ {t₁ t₁' : Tm} {ρ ρ' : Store}
1006+      (h : t₁ / ρ ⟶ t₁' / ρ') :
1007+      <{ succ t₁ }> / ρ ⟶ <{ succ t₁' }> / ρ'
1008+  | predConst {n : Nat} {ρ : Store} :
1009+      <{ pred ~(Tm.const n) }> / ρ ⟶ Tm.const (n - 1) / ρ
1010+  | pred {t₁ t₁' : Tm} {ρ ρ' : Store}
1011+      (h : t₁ / ρ ⟶ t₁' / ρ') :
1012+      <{ pred t₁ }> / ρ ⟶ <{ pred t₁' }> / ρ'
1013+  | multConst {n₁ n₂ : Nat} {ρ : Store} :
1014+      <{ ~(Tm.const n₁) * ~(Tm.const n₂) }> / ρ ⟶
1015+      Tm.const (n₁ * n₂) / ρ
1016+  | mult₁ {t₁ t₁' t₂ : Tm} {ρ ρ' : Store}
1017+      (h : t₁ / ρ ⟶ t₁' / ρ') :
1018+      <{ t₁ * t₂ }> / ρ ⟶ <{ t₁' * t₂ }> / ρ'
1019+  | mult₂ {v₁ t₂ t₂' : Tm} {ρ ρ' : Store}
1020+      (h₁ : v₁.IsValue)
1021+      (h₂ : t₂ / ρ ⟶ t₂' / ρ') :
1022+      <{ v₁ * t₂ }> / ρ ⟶ <{ v₁ * t₂' }> / ρ'
1023+  | if0Step {t₁ t₁' t₂ t₃ : Tm} {ρ ρ' : Store}
1024+      (h : t₁ / ρ ⟶ t₁' / ρ') :
1025+      <{ if0 t₁ then t₂ else t₃ }> / ρ ⟶
1026+      <{ if0 t₁' then t₂ else t₃ }> / ρ'
1027+  | if0Zero {t₂ t₃ : Tm} {ρ : Store} :
1028+      <{ if0 0 then t₂ else t₃ }> / ρ ⟶ t₂ / ρ
1029+  | if0Nonzero {n : Nat} {t₂ t₃ : Tm} {ρ : Store} :
1030+      <{ if0 ~(Tm.const (n + 1)) then t₂ else t₃ }> / ρ ⟶
1031+      t₃ / ρ
1032+  -- references
1033+  | refValue {v : Tm} {ρ : Store}
1034+      (h : v.IsValue) :
1035+      <{ ref v }> / ρ ⟶ Tm.loc ρ.length / ρ.concat v
1036+  | ref_ {t₁ t₁' : Tm} {ρ ρ' : Store}
1037+      (h : t₁ / ρ ⟶ t₁' / ρ') :
1038+      <{ ref t₁ }> / ρ ⟶ <{ ref t₁' }> / ρ'
1039+  | derefLoc {l : Nat} {ρ : Store}
1040+      (h : l < ρ.length) :
1041+      <{ !~(Tm.loc l) }> / ρ ⟶ ρ[l] / ρ
1042+  | deref {t₁ t₁' : Tm} {ρ ρ' : Store}
1043+      (h : t₁ / ρ ⟶ t₁' / ρ') :
1044+      <{ !t₁ }> / ρ ⟶ <{ !t₁' }> / ρ'
1045+  | assign {v : Tm} {l : Nat} {ρ : Store}
1046+      (h₁ : v.IsValue)
1047+      (h₂ : l < ρ.length) :
1048+      <{ ~(Tm.loc l) := v }> / ρ ⟶ <{ unit }> / ρ.set l v
1049+  | assign₁ {t₁ t₁' t₂ : Tm} {ρ ρ' : Store}
1050+      (h : t₁ / ρ ⟶ t₁' / ρ') :
1051+      <{ t₁ := t₂ }> / ρ ⟶ <{ t₁' := t₂ }> / ρ'
1052+  | assign₂ {v₁ t₂ t₂' : Tm} {ρ ρ' : Store}
1053+      (h₁ : v₁.IsValue)
1054+      (h₂ : t₂ / ρ ⟶ t₂' / ρ') :
1055+      <{ v₁ := t₂ }> / ρ ⟶ <{ v₁ := t₂' }> / ρ'
1056+end
1057+
1058+scoped notation:40
1059+  t:71 " / " ρ:41 " ⟶ " t':71 " / " ρ':41 =>
1060+  Step (t, ρ) (t', ρ')
1061+scoped notation:40
1062+  t:71 " / " ρ:41 " ⟶* " t':71 " / " ρ':41 =>
1063+  Multi Step (t, ρ) (t', ρ')
1064+
1065+attribute [StlcRefEval] Step.appAbs Step.app₁ Step.app₂
1066+    Step.succ Step.succNat Step.pred Step.predConst
1067+    Step.multConst Step.mult₁ Step.mult₂
1068+    Step.if0Step Step.if0Zero Step.if0Nonzero
1069+    Step.refValue Step.ref_ Step.derefLoc Step.deref Step.assign
1070+    Step.assign₁ Step.assign₂
1071+
1072+--  ## Typing
1073+
1074+--  The contexts assigning types to free variables are exactly the same as
1075+--  for the STLC: partial maps from identifiers to types.
1076+
1077+abbrev Context := PartialMap String Ty
1078+
1079+--  ### Store typings
1080+
1081+--  Having extended our syntax and reduction rules to accommodate
1082+--  references, our last job is to write down typing rules for the new
1083+--  constructs (and, of course, to check that these rules are sound!).
1084+--
1085+--  Naturally, the key question is, "What is the type of a location?"
1086+--
1087+--  First of all, notice that this question doesn't arise when typechecking
1088+--  terms that programmers actually write. Concrete location constants
1089+--  arise only in terms that are the intermediate results of reduction;
1090+--  they are not in the language that programmers write. So we only need to
1091+--  determine the type of a location when we're in the middle of a
1092+--  reduction sequence, e.g., trying to apply the progress or preservation
1093+--  lemmas. Thus, even though we normally think of typing as a *static*
1094+--  program property, it makes sense for the typing of locations to depend
1095+--  on the *dynamic* progress of the program too.
1096+--
1097+--  As a first try, note that when we reduce a term containing concrete
1098+--  locations, the type of the result depends on the contents of the store
1099+--  that we start with. For example, if we reduce the term `!(loc 1)` in
1100+--  the store `unit, unit`, the result is `unit`; if we reduce the same
1101+--  term in the store `unit, λX:Unit.X`, the result is `λX:Unit.X`. With
1102+--  respect to the former store, the location `1` has type `Unit`, and with
1103+--  respect to the latter it has type `Unit→Unit`. This observation leads
1104+--  us immediately to a first attempt at a typing rule for locations:
1105+--
1106+--       Γ ⊢ ρ[l] : τ₁
1107+--      ------------------
1108+--      Γ ⊢ loc l : Ref τ₁
1109+--
1110+--  But where does `ρ` come from?
1111+--
1112+--  That is, to find the type of a location `l`, we look up the current
1113+--  contents of `l` in the store and calculate the type `τ₁` of the
1114+--  contents. The type of the location is then `Ref τ₁`.
1115+--
1116+--  Having begun in this way, we need to go a little further to reach a
1117+--  consistent state. In effect, by making the type of a term depend on the
1118+--  store, we have changed the typing relation from a three-place relation
1119+--  (between contexts, terms, and types) to a four-place relation (between
1120+--  contexts, *stores*, terms, and types). Since the store is, intuitively,
1121+--  part of the context in which we calculate the type of a term, let's
1122+--  write this four-place relation with the store to the left of the
1123+--  turnstile: `Γ; ρ ⊢ t : τ`. Our rule for typing references now has the
1124+--  form
1125+--
1126+--       Γ; ρ ⊢ ρ[l] : τ₁
1127+--      ---------------------
1128+--      Γ; ρ ⊢ loc l : Ref τ₁
1129+--
1130+--  and all the rest of the typing rules in the system are extended
1131+--  similarly with stores. (The other rules do not need to do anything
1132+--  interesting with their stores — just pass them from premise to
1133+--  conclusion.)
1134+--
1135+--  However, this rule will not quite do. For one thing, typechecking is
1136+--  rather inefficient, since calculating the type of a location `l`
1137+--  involves calculating the type of the current contents `v` of `l`. If
1138+--  `l` appears many times in a term `τ`, we will re-calculate the type of
1139+--  `v` many times in the course of constructing a typing derivation for
1140+--  `τ`. Worse, if `v` itself contains locations, then we will have to
1141+--  recalculate *their* types each time they appear. Worse yet, the
1142+--  proposed typing rule for locations may not allow us to derive anything
1143+--  at all if the store contains a *cycle*. For example, there is no finite
1144+--  typing derivation for the location `0` with respect to this store:
1145+
1146+--  λX:Nat. (!(loc 1)) X, λX:Nat. (!(loc 0)) X
1147+
1148+--  ### Exercise (3 stars): cyclic_store ⭐⭐⭐
1149+
1150+--  Can you find a term whose reduction will create this particular cyclic
1151+--  store?
1152+
1153+theorem cyclic_store:
1154+  ∃ t,
1155+    t / [] ⟶*
1156+    <{ unit }> / (<{ λX:Nat. (!(loc 1)) X }> :: <{ λX:Nat. (!(loc 0)) X }> :: []) := by
1157+  sorry
1158+
1159+--  (End of exercise)
1160+
1161+--  These problems arise from the fact that our proposed typing rule for
1162+--  locations requires us to recalculate the type of a location every time
1163+--  we mention it in a term. But this, intuitively, should not be
1164+--  necessary. After all, when a location is first created, we know the
1165+--  type of the initial value that we are storing into it. Suppose we are
1166+--  willing to enforce the invariant that the type of the value contained
1167+--  in a given location *never changes*; that is, although we may later
1168+--  store other values into this location, those other values will always
1169+--  have the same type as the initial one. In other words, we always have
1170+--  in mind a single, definite type for every location in the store, which
1171+--  is fixed when the location is allocated. Then these intended types can
1172+--  be collected together as a *store typing* — a finite function mapping
1173+--  locations to types.
1174+--
1175+--  As with the other type systems we've seen, this conservative typing
1176+--  restriction on allowed updates means that we will rule out as ill-typed
1177+--  some programs that could reduce perfectly well without getting stuck.
1178+--
1179+--  Just as we did for stores, we will represent a store type simply as a
1180+--  list of types: the type at index `i` records the type of the values
1181+--  that we expect to be stored in cell `i`.
1182+
1183+abbrev StoreTy := List Ty
1184+
1185+open scoped MyGetElem
1186+instance : MyGetElem StoreTy Nat Ty where
1187+  getElem δ n := δ.getD n <{Unit}>
1188+
1189+@[simp]
1190+theorem StoreTy_get_succ_tl (hd : Ty) (tl : StoreTy) (n : Nat) :
1191+  (hd :: tl)[n + 1] = tl[n] := by rfl
1192+@[simp]
1193+theorem StoreTy_get_zero_hd (hd : Ty) (tl : StoreTy) :
1194+  (hd :: tl)[0] = hd := by rfl
1195+
1196+--  Suppose we are given a store typing `δ` describing the store `ρ` in
1197+--  which some term `τ` will be reduced. Then we can use `δ` to calculate
1198+--  the type of the result of `τ` without ever looking directly at `ρ`. For
1199+--  example, if `δ` is `Unit, Unit→Unit`, then we can immediately infer
1200+--  that `!(loc 1)` has type `Unit→Unit`. More generally, the typing rule
1201+--  for locations can be reformulated in terms of store typings like this:
1202+--
1203+--           l < δ.length
1204+--      -----------------------
1205+--      Γ; δ ⊢ loc l : Ref δ[l]
1206+--
1207+--  That is, as long as `l` is a valid location, we can compute the type of
1208+--  `l` just by looking it up in `δ`. Typing is again a four-place
1209+--  relation, but it is parameterized on a store *typing* rather than a
1210+--  concrete store. The rest of the typing rules are analogously augmented
1211+--  with store typings.
1212+
1213+--  ### The Typing Relation
1214+
1215+--  We can now formalize the typing relation for the STLC with references.
1216+--  Here, again, are the rules we're adding to the base STLC (with numbers
1217+--  and `Unit`):
1218+--
1219+--           l < δ.length
1220+--      -----------------------  (loc)
1221+--      Γ; δ ⊢ loc l : Ref δ[l]
1222+--
1223+--          Γ; δ ⊢ t₁ : τ₁
1224+--      ----------------------   (ref)
1225+--      Γ; δ ⊢ ref t₁ : Ref τ₁
1226+--
1227+--        Γ; δ ⊢ t₁ : Ref τ₁
1228+--        ------------------     (deref)
1229+--        Γ; δ ⊢ !t₁ : τ₁
1230+--
1231+--        Γ; δ ⊢ t₁ : Ref τ₂
1232+--          Γ; δ ⊢ t₂ : τ₂
1233+--      ----------------------   (assign)
1234+--      Γ; δ ⊢ t₁ := t₂ : Unit
1235+
1236+inductive HasType (δ : StoreTy) : Context → Tm → Ty → Prop where
1237+  -- pure STLC
1238+  | var {Γ : Context} {x : String} {τ₁ : Ty}
1239+      (h : Γ[x] = some τ₁) :
1240+      <{ Γ / δ ⊢ ~(Tm.var x) ⦂ τ₁ }>
1241+  | abs {Γ : Context} {x : String} {τ₁ τ₂ : Ty} {t₁ : Tm}
1242+      (h : <{ x ↦ τ₂ ; Γ / δ ⊢ t₁ ⦂ τ₁ }>) :
1243+      <{ Γ / δ ⊢ λ x : τ₂ . t₁ ⦂ τ₂ → τ₁ }>
1244+  | app {Γ : Context} {τ₁ τ₂ : Ty} {t₁ t₂ : Tm}
1245+      (h₁ : <{ Γ / δ ⊢ t₁ ⦂ τ₂ → τ₁ }>)
1246+      (h₂ : <{ Γ / δ ⊢ t₂ ⦂ τ₂ }>) :
1247+      <{ Γ / δ ⊢ t₁ t₂ ⦂ τ₁ }>
1248+  -- numbers
1249+  | const {Γ : Context} {n : Nat} :
1250+      <{ Γ / δ ⊢ ~(Tm.const n) ⦂ Nat }>
1251+  | succ {Γ : Context} {t₁ : Tm}
1252+      (h : <{ Γ / δ ⊢ t₁ ⦂ Nat }>) :
1253+      <{ Γ / δ ⊢ succ t₁ ⦂ Nat }>
1254+  | pred {Γ : Context} {t₁ : Tm}
1255+      (h : <{ Γ / δ ⊢ t₁ ⦂ Nat }>) :
1256+      <{ Γ / δ ⊢ pred t₁ ⦂ Nat }>
1257+  | mult {Γ : Context} {t₁ t₂ : Tm}
1258+      (h₁ : <{ Γ / δ ⊢ t₁ ⦂ Nat }>)
1259+      (h₂ : <{ Γ / δ ⊢ t₂ ⦂ Nat }>) :
1260+      <{ Γ / δ ⊢ t₁ * t₂ ⦂ Nat }>
1261+  | ite0 {Γ : Context} {t₁ t₂ t₃ : Tm} {τ : Ty}
1262+      (h₁ : <{ Γ / δ ⊢ t₁ ⦂ Nat }>)
1263+      (h₂ : <{ Γ / δ ⊢ t₂ ⦂ τ }>)
1264+      (h₃ : <{ Γ / δ ⊢ t₃ ⦂ τ }>) :
1265+      <{ Γ / δ ⊢ if0 t₁ then t₂ else t₃ ⦂ τ }>
1266+  -- unit
1267+  | unit {Γ : Context} :
1268+      <{ Γ / δ ⊢ unit ⦂ Unit }>
1269+  -- references
1270+  | loc_ {Γ : Context} {l : Nat}
1271+      (h : l < δ.length) :
1272+      <{ Γ / δ ⊢ ~(Tm.loc l) ⦂ Ref ~(δ[l]) }>
1273+  | ref_ {Γ : Context} {t₁ : Tm} {τ₁ : Ty}
1274+      (h : <{ Γ / δ ⊢ t₁ ⦂ τ₁ }>) :
1275+      <{ Γ / δ ⊢ ref t₁ ⦂ Ref τ₁ }>
1276+  | deref {Γ : Context} {t₁ : Tm} {τ₁ : Ty}
1277+      (h : <{ Γ / δ ⊢ t₁ ⦂ Ref τ₁ }>) :
1278+      <{ Γ / δ ⊢ !t₁ ⦂ τ₁ }>
1279+  | assign {Γ : Context} {t₁ t₂ : Tm} {τ₂ : Ty}
1280+      (h₁ : <{ Γ / δ ⊢ t₁ ⦂ Ref τ₂ }>)
1281+      (h₂ : <{ Γ / δ ⊢ t₂ ⦂ τ₂ }>) :
1282+      <{ Γ / δ ⊢ t₁ := t₂ ⦂ Unit }>
1283+
1284+attribute [StlcRefTyping] HasType.var HasType.abs HasType.app
1285+    HasType.const HasType.succ HasType.pred HasType.mult
1286+    HasType.ite0 HasType.unit
1287+    HasType.loc_ HasType.ref_ HasType.deref HasType.assign
1288+
1289+--  THE FOLLOWING DETAILS CAN BE SKIPPED (Notation encoding)
1290+open Lean PrettyPrinter StlcCommon.Delab in
1291+@[app_unexpander HasType]
1292+def HasType.unexpand : Unexpander
1293+  | `($_ $δ $Γ $t $T) => do
1294+      let Γ' ← unexpandCtx Γ
1295+      `(<{ $Γ':stlcCtx / $δ ⊢ $(getTm t):stlcTm ⦂ $(getTy T):stlcTy }>)
1296+  | _ => throw ()
1297+--  END DETAILS
1298+
1299+--  Of course, these typing rules will accurately predict the results of
1300+--  reduction only if the concrete store used during reduction actually
1301+--  conforms to the store typing that we assume for purposes of
1302+--  typechecking. This proviso exactly parallels the situation with free
1303+--  variables in the basic STLC: the substitution lemma promises that, if
1304+--  `Γ / δ ⊢ t : T`, then we can replace the free variables in `τ` with
1305+--  values of the types listed in `Γ` to obtain a closed term of type `τ`,
1306+--  which, by the type preservation theorem will reduce to a final result
1307+--  of type `τ` if it yields any result at all. We will see below how to
1308+--  formalize an analogous intuition for stores and store typings.
1309+--
1310+--  However, for purposes of typechecking the terms that programmers
1311+--  actually write, we do not need to do anything tricky to guess what
1312+--  store typing we should use. Concrete locations arise only in terms that
1313+--  are the intermediate results of reduction; they are not in the language
1314+--  that programmers write. Thus, we can simply typecheck the programmer's
1315+--  terms with respect to the *empty* store typing. As reduction proceeds
1316+--  and new locations are created, we will always be able to see how to
1317+--  extend the store typing by looking at the type of the initial values
1318+--  being placed in newly allocated cells; this intuition is formalized in
1319+--  the statement of the type preservation theorem below.
1320+
1321+--  ## Properties
1322+
1323+--  Our final task is to check that standard type safety properties
1324+--  continue to hold for the STLC with references. The progress theorem
1325+--  ("well-typed terms are not stuck") can be stated and proved almost as
1326+--  for the STLC; we just need to add a few straightforward cases to the
1327+--  proof to deal with the new constructs. The preservation theorem is a
1328+--  bit more interesting, so let's look at it first.
1329+
1330+--  ### Well-Typed Stores
1331+
1332+--  Since we have extended both the reduction relation (with initial and
1333+--  final stores) and the typing relation (with a store typing), we need to
1334+--  change the statement of preservation to include these parameters. But
1335+--  clearly we cannot just add stores and store typings without saying
1336+--  anything about how they are related — i.e., this is wrong:
1337+
1338+sf_expect_failure_in
1339+  theorem preservation_wrong (δ : StoreTy) (τ : Ty) (t t' : Tm) (ρ ρ' : Store) :
1340+      <{ ∅ / δ ⊢ t ⦂ τ }> →
1341+      t / ρ ⟶ t' / ρ' →
1342+      <{ ∅ / δ ⊢ t' ⦂ τ }> := by
1343+
1344+--  If we typecheck with respect to some set of assumptions about the types
1345+--  of the values in the store and then reduce with respect to a store that
1346+--  violates these assumptions, the result will be disaster. We say that a
1347+--  store `ρ` is *well typed* with respect to a store typing `δ` if the
1348+--  term at each location `l` in `ρ` has the type at location `l` in `δ`.
1349+--  Since only closed terms ever get stored in locations (why?), it
1350+--  suffices to type them in the empty context. The following definition of
1351+--  `StoreWellTyped` formalizes this:
1352+
1353+def StoreWellTyped (δ:StoreTy) (ρ:Store) :=
1354+  δ.length = ρ.length ∧
1355+  (∀ (l : Nat), l < ρ.length → <{ ∅ / δ ⊢ ~(ρ[l]) ⦂ ~(δ[l]) }>)
1356+
1357+--  Informally, we will write `δ ⊢ ρ` for `StoreWellTyped δ ρ`.
1358+
1359+scoped notation:40 δ:41 " ⊢ " ρ:41 => StoreWellTyped δ ρ
1360+
1361+--  Intuitively, a store `ρ` is consistent with a store typing `δ` if every
1362+--  value in the store has the type predicted by the store typing. The only
1363+--  subtle point is the fact that, when typing the values in the store, we
1364+--  supply the very same store typing to the typing relation. This allows
1365+--  us to type circular stores like the one we saw above.
1366+
1367+--  ### Exercise (3 stars): store_not_unique ⭐⭐⭐
1368+
1369+--  Can you find a store `ρ`, and two different store typings `δ₁` and `δ₂`
1370+--  such that both `δ₁ ⊢ ρ` and `δ₂ ⊢ ρ`?
1371+
1372+theorem store_not_unique:
1373+  exists ρ, exists δ₁, exists δ₂,
1374+    δ₁ ⊢ ρ ∧ δ₂ ⊢ ρ ∧ δ₁ ≠ δ₂ := by
1375+  sorry
1376+
1377+--  (End of exercise)
1378+
1379+--  We can now state something closer to the desired preservation property:
1380+
1381+sf_expect_failure_in
1382+  theorem preservation_less_wrong (δ : StoreTy) (τ : Ty) (t t' : Tm) (ρ ρ' : Store) :
1383+    <{ ∅ / δ ⊢ t ⦂ τ }> →
1384+    t / ρ ⟶ t' / ρ' →
1385+    δ ⊢ ρ →
1386+    <{ ∅ / δ ⊢ t' ⦂ τ }> := by
1387+
1388+--  This statement is fine for all of the reduction rules except the
1389+--  allocation rule `refValue`. The problem is that this rule yields a
1390+--  store with a larger domain than the initial store, which falsifies the
1391+--  conclusion of the above statement: if `ρ'` includes a binding for a
1392+--  fresh location `l`, then `l` cannot be in the domain of `δ`, and it
1393+--  will not be the case that `t'` (which definitely mentions `l`) is
1394+--  typable under `δ`.
1395+
1396+--  ### Extending Store Typings
1397+
1398+--  Evidently, since the store can increase in size during reduction, we
1399+--  need to allow the store *typing* to grow during reduction as well. This
1400+--  motivates the following definition. We say that the store type `δ'`
1401+--  *extends* `δ` if `δ'` is just `δ` with some new types added to the end.
1402+
1403+inductive Extends : StoreTy → StoreTy → Prop where
1404+  | nil (δ' : StoreTy) : Extends δ' []
1405+  | cons (τ : Ty) {δ' δ : StoreTy} (h : Extends δ' δ) :
1406+      Extends (τ::δ') (τ::δ)
1407+
1408+attribute [StlcRefTyping] Extends.nil Extends.cons
1409+
1410+--  For example, the store typing `[Nat]` with a single location of type
1411+--  `Nat` extends the empty store typing.
1412+--
1413+--  We'll need a few technical lemmas about extended contexts. First,
1414+--  looking up a type in an extended store typing yields the same result as
1415+--  in the original:
1416+
1417+theorem extends_lookup {l : Nat} {δ δ' : StoreTy}
1418+  (h₁ : l < δ.length)
1419+  (h₂ : Extends δ' δ) :
1420+  δ'[l] = δ[l] := by
1421+
1422+    induction δ generalizing l δ' with
1423+    | nil => simp_all
1424+    | cons hd tl ih =>
1425+      cases δ' with
1426+      | nil => inversion h₂
1427+      | cons hd' tl' =>
1428+        inversion h₂
1429+        cases l with
1430+        | zero => rfl
1431+        | succ l =>
1432+          simp only [StoreTy_get_succ_tl]; apply ih
1433+          · simp_all
1434+          · assumption
1435+
1436+--  Next, if `δ'` extends `δ`, the length of `δ'` is at least that of `δ`.
1437+
1438+theorem length_extends {l : Nat} {δ δ' : StoreTy}
1439+  (h₁ : l < δ.length)
1440+  (h₂ : Extends δ' δ) :
1441+  l < δ'.length := by
1442+    induction h₂ generalizing l with
1443+    | nil => simp_all
1444+    | cons τ h ih =>
1445+        simp only [List.length_cons]
1446+        cases l with
1447+        | zero => lia
1448+        | succ l' =>
1449+          apply Nat.succ_lt_succ; apply ih
1450+          simp_all
1451+
1452+--  Finally, `δ ++ δ'` extends `δ`, and `Extends` is reflexive.
1453+
1454+theorem extends_app (δ δ' : StoreTy) : Extends (δ ++ δ') δ := by
1455+  induction δ generalizing δ' <;> apply_rules using StlcRefTyping
1456+
1457+theorem extends_refl (δ : StoreTy) : Extends δ δ := by
1458+  induction δ <;> apply_rules using StlcRefTyping
1459+
1460+--  ### Preservation, Finally
1461+
1462+--  We can now give the final, correct statement of the type preservation
1463+--  property:
1464+
1465+def preservation_theorem {δ : StoreTy} {t t' : Tm} {τ : Ty} {ρ ρ' : Store} :=
1466+  (hTy : <{ ∅ / δ ⊢ t ⦂ τ }>) →
1467+  (hStoreTy : δ ⊢ ρ) →
1468+  (hEval : t / ρ ⟶ t' / ρ') →
1469+    ∃ δ', Extends δ' δ ∧ (<{ ∅ / δ' ⊢ t' ⦂ τ }>) ∧ (δ' ⊢ ρ')
1470+
1471+--  Note that the preservation theorem merely asserts that there is *some*
1472+--  store typing `δ'` extending `δ` (i.e., agreeing with `δ` on the values
1473+--  of all the old locations) such that the new term `t'` is well typed
1474+--  with respect to `δ'`; it does not tell us exactly what `δ'` is. It is
1475+--  intuitively clear, of course, that `δ'` is either `δ` or else exactly
1476+--  `δ ++ [τ₁]`, where `τ₁` is the type of the value `v₁` in the extended
1477+--  store `ρ ++ [v₁]`, but stating this explicitly would complicate the
1478+--  statement of the theorem without making it any more useful: the weaker
1479+--  version above is already in the right form (because its conclusion
1480+--  implies its hypothesis) to "turn the crank" repeatedly and conclude
1481+--  that every *sequence* of reduction steps preserves well-typedness.
1482+--  Combining this with the progress property, we obtain the usual
1483+--  guarantee that "well-typed programs never go wrong."
1484+--
1485+--  In order to prove this, we'll need a few lemmas, as usual.
1486+
1487+--  #### Substitution Lemma
1488+
1489+--  First, we need an easy extension of the standard substitution lemma,
1490+--  along with the same machinery about context invariance that we used in
1491+--  the proof of the substitution lemma for the STLC.
1492+
1493+theorem weakening {Γ Γ' : Context} {δ : StoreTy} {t : Tm} {τ: Ty}
1494+    (hi : Γ ⊆ Γ')
1495+    (ht : <{ Γ / δ ⊢ t ⦂ τ }>) :
1496+     <{ Γ' / δ ⊢ t ⦂ τ }> := by
1497+  induction ht generalizing Γ' with (apply_rules [PartialMap.update_subset] using StlcRefTyping)
1498+
1499+theorem weakening_empty {Γ : Context} {δ : StoreTy} {t : Tm} {τ: Ty}
1500+    (ht :<{ ∅ / δ ⊢ t ⦂ τ }>) :
1501+    <{ Γ / δ ⊢ t ⦂ τ }> := by
1502+  apply weakening _ ht
1503+  intro _ _ h
1504+  rw [PartialMap.getElem_empty] at h
1505+  contradiction
1506+
1507+theorem substitution_preserves_typing (Γ : Context) (δ : StoreTy) (x : String)
1508+    (τ₁ : Ty) (t v : Tm) (τ : Ty)
1509+    (ht : <{ x ↦ τ₁ ; Γ / δ⊢ t ⦂ τ }>)
1510+    (hv : <{ ∅ / δ ⊢ v ⦂ τ₁ }>) :
1511+    <{ Γ / δ ⊢ [x := v] t ⦂ τ }> := by
1512+  induction t generalizing Γ τ with (
1513+    rw [subst]; try (inversion ht; apply_rules using StlcRefTyping; done))
1514+    | var y =>
1515+        inversion ht with | _ h =>
1516+        by_cases h₁ : x = y
1517+        · subst h₁; simp at h; subst h;
1518+          apply weakening_empty at hv
1519+          simp; assumption
1520+        · rw [PartialMap.update_neq] at h <;> simp_all
1521+          apply_rules using StlcRefTyping
1522+    | abs y _ _ ih =>
1523+        inversion ht with | _ h =>
1524+        by_cases h₁ : x = y
1525+        · simp_all [PartialMap.update_shadow]; apply_rules using StlcRefTyping
1526+        · rw [PartialMap.update_permute] at h
1527+          · simp_all; apply_rules using StlcRefTyping
1528+          · lia
1529+
1530+--  #### Assignment Preserves Store Typing
1531+
1532+--  Next, we must show that replacing the contents of a cell in the store
1533+--  with a new value of appropriate type does not change the overall type
1534+--  of the store. (This is needed for the `assign` rule.)
1535+
1536+theorem assign_pres_store_typing {δ : StoreTy} {ρ : Store} {l : Nat} {t : Tm}
1537+  (hLen : l < ρ.length)
1538+  (hStoreTy : δ ⊢ ρ)
1539+  (hTy : <{ ∅ / δ ⊢ t ⦂ ~(δ[l]) }>) :
1540+  δ ⊢ ρ.set l t := by
1541+    have ⟨h₁, h₂⟩ := hStoreTy
1542+    constructor
1543+    · simp_all [List.length_set]
1544+    · intro l' hLen'
1545+      by_cases h₁ : l' = l
1546+      · subst_vars
1547+        rw [Store_get_set_eq] <;> assumption
1548+      · rw [Store_get_set_neq] <;> try assumption
1549+        apply h₂
1550+        simp_all [List.length_set]
1551+
1552+--  #### Weakening for Stores
1553+
1554+--  Finally, we need a lemma on store typings, stating that, if a store
1555+--  typing is extended with a new location, the extended one still allows
1556+--  us to assign the same types to the same terms as the original.
1557+
1558+theorem store_weakening {Γ : Context} {δ δ' : StoreTy} {t : Tm} {τ : Ty}
1559+  (hExt : Extends δ' δ)
1560+  (hTy : <{ Γ / δ ⊢ t ⦂ τ }>) :
1561+  <{ Γ / δ' ⊢ t ⦂ τ }> := by
1562+    induction hTy with (try (apply_rules using StlcRefTyping; done))
1563+    | loc_ h =>
1564+        rw [←extends_lookup] <;> try assumption
1565+        apply HasType.loc_
1566+        apply length_extends <;> assumption
1567+
1568+--  We can use the `store_weakening` lemma to prove that if a store is well
1569+--  typed with respect to a store typing, then the store extended with a
1570+--  new term `τ` will still be well typed with respect to the store typing
1571+--  extended with `τ`'s type.
1572+
1573+theorem store_well_typed_app {δ : StoreTy} {ρ : Store} {t₁ : Tm} {τ₁ : Ty}
1574+  (hStoreTy : δ ⊢ ρ)
1575+  (hTy : <{ ∅ / δ ⊢ t₁ ⦂ τ₁ }>) :
1576+  (δ.concat τ₁) ⊢ (ρ.concat t₁) := by
1577+    have ⟨h₁, h₂⟩ := hStoreTy
1578+    simp_all only [List.concat_eq_append]
1579+    constructor
1580+    · simp_all
1581+    · simp_all only [List.length_append, List.length_cons, List.length_nil, Nat.zero_add]
1582+      intro l hl
1583+      inversion hl with
1584+      | refl =>
1585+          apply store_weakening <;> try assumption
1586+          apply extends_app
1587+          simp_all [MyGetElem.getElem]
1588+      | step hl =>
1589+          apply store_weakening <;> try assumption
1590+          · apply extends_app
1591+          · have hl' : l < ρ.length := by lia
1592+            simp_all [MyGetElem.getElem, List.getElem?_append_left]
1593+
1594+--  #### Preservation!
1595+
1596+--  Now that we've got everything set up right, the proof of preservation
1597+--  is actually quite straightforward:
1598+
1599+theorem preservation {δ : StoreTy} {t t' : Tm} {τ : Ty} {ρ ρ' : Store}
1600+  (hTy : <{ ∅ / δ ⊢ t ⦂ τ }>)
1601+  (hStoreTy : δ ⊢ ρ)
1602+  (hEval : t / ρ ⟶ t' / ρ') :
1603+    ∃ δ', Extends δ' δ ∧ (<{ ∅ / δ' ⊢ t' ⦂ τ }>) ∧ (δ' ⊢ ρ') := by
1604+
1605+    generalize heq : (∅ : Context) = Γ at hTy
1606+    -- discharge the goals where `t` doesn't step
1607+    induction hTy generalizing t' with (subst_vars; try (inversion hEval; done))
1608+    | app h₁ h₂ ih₁ ih₂ =>
1609+      inversion hEval with
1610+      | appAbs =>
1611+        inversion h₁ with | abs h =>
1612+        exists δ; constructor
1613+        apply extends_refl; constructor
1614+        apply_rules [substitution_preserves_typing, extends_refl] using StlcRefTyping
1615+        assumption
1616+      | app₁ hs =>
1617+        have ⟨δ', hExt, hTy', hStoreTy'⟩ := ih₁ hs rfl
1618+        exists δ'; constructor
1619+        assumption; constructor
1620+        solve_by_elim [store_weakening] using StlcRefTyping
1621+        assumption
1622+      | app₂ _ hs =>
1623+        have ⟨δ', hExt, hTy', hStoreTy'⟩ := ih₂ hs rfl
1624+        exists δ'; constructor
1625+        assumption; constructor
1626+        solve_by_elim [store_weakening] using StlcRefTyping
1627+        assumption
1628+    | succ _ ih =>
1629+      inversion hEval with
1630+      | succNat =>
1631+        exists δ; constructor
1632+        apply extends_refl; constructor
1633+        constructor
1634+        assumption
1635+      | succ hs =>
1636+        have ⟨δ', hExt, hTy', hStoreTy'⟩ := ih hs rfl
1637+        exists δ'; constructor
1638+        assumption; constructor
1639+        solve_by_elim [store_weakening] using StlcRefTyping
1640+        assumption
1641+    | pred _ ih =>
1642+      inversion hEval with
1643+      | predConst =>
1644+        exists δ; constructor
1645+        apply extends_refl; constructor
1646+        constructor
1647+        assumption
1648+      | pred hs =>
1649+        have ⟨δ', hExt, hTy', hStoreTy'⟩ := ih hs rfl
1650+        exists δ'; constructor
1651+        assumption; constructor
1652+        solve_by_elim [store_weakening] using StlcRefTyping
1653+        assumption
1654+    | mult h₁ h₂ ih₁ ih₂ =>
1655+      inversion hEval with
1656+      | multConst =>
1657+        exists δ; constructor
1658+        apply extends_refl; constructor
1659+        constructor
1660+        assumption
1661+      | mult₁ hs =>
1662+        have ⟨δ', hExt, hTy', hStoreTy'⟩ := ih₁ hs rfl
1663+        exists δ'; constructor
1664+        assumption; constructor
1665+        solve_by_elim [store_weakening] using StlcRefTyping
1666+        assumption
1667+      | mult₂ _ hs =>
1668+        have ⟨δ', hExt, hTy', hStoreTy'⟩ := ih₂ hs rfl
1669+        exists δ'; constructor
1670+        assumption; constructor
1671+        solve_by_elim [store_weakening] using StlcRefTyping
1672+        assumption
1673+    | ite0 _ h₂ h₃ ih₁ _ _ =>
1674+      inversion hEval with
1675+      | if0Step hs =>
1676+        have ⟨δ', hExt, hTy', hStoreTy'⟩ := ih₁ hs rfl
1677+        exists δ'; constructor
1678+        assumption; constructor
1679+        constructor <;> solve_by_elim [store_weakening] using StlcRefTyping
1680+        assumption
1681+      | if0Zero =>
1682+        exists δ; constructor
1683+        apply extends_refl; constructor <;> assumption
1684+      | if0Nonzero =>
1685+        exists δ; constructor
1686+        apply extends_refl; constructor <;> assumption
1687+    | @ref_ _ _ τ₁ h ih =>
1688+      inversion hEval with
1689+      | refValue =>
1690+        exists δ.concat τ₁; constructor
1691+        · rw [List.concat_eq_append]; apply extends_app
1692+        · constructor
1693+          · have h : <{Ref τ₁}> = <{Ref ~((δ.concat τ₁)[ρ.length])}> := by
1694+              simp_all [StoreWellTyped, MyGetElem.getElem]
1695+            rw [h]
1696+            constructor
1697+            simp [StoreWellTyped] at hStoreTy ⊢; lia
1698+          · apply store_well_typed_app <;> assumption
1699+      | ref_ hs =>
1700+        have ⟨δ', hExt, hTy', hStoreTy'⟩ := ih hs rfl
1701+        exists δ'; constructor
1702+        assumption; constructor
1703+        solve_by_elim [store_weakening] using StlcRefTyping
1704+        assumption
1705+    | deref h ih =>
1706+      inversion hEval with
1707+      | derefLoc hl =>
1708+        inversion h
1709+        exists δ; constructor
1710+        apply extends_refl; constructor
1711+        have ⟨h₁, h₂⟩ := hStoreTy
1712+        apply h₂ <;> assumption
1713+        assumption
1714+      | deref 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+    | assign h₁ h₂ ih₁ ih₂ =>
1721+      inversion hEval with
1722+      | assign _ hl =>
1723+        inversion h₁
1724+        exists δ; constructor
1725+        apply extends_refl; constructor
1726+        constructor
1727+        apply assign_pres_store_typing <;> assumption
1728+      | assign₁ hs =>
1729+        have ⟨δ', hExt, hTy', hStoreTy'⟩ := ih₁ hs rfl
1730+        exists δ'; constructor
1731+        assumption; constructor
1732+        solve_by_elim [store_weakening] using StlcRefTyping
1733+        assumption
1734+      | assign₂ _ hs =>
1735+        have ⟨δ', hExt, hTy', hStoreTy'⟩ := ih₂ hs rfl
1736+        exists δ'; constructor
1737+        assumption; constructor
1738+        solve_by_elim [store_weakening] using StlcRefTyping
1739+        assumption
1740+
1741+--  This proof is pretty long, and many of the cases repeat themselves.
1742+--  With judicious use of automation, we can make it much shorter:
1743+
1744+theorem preservation_shorter {δ : StoreTy} {t t' : Tm} {τ : Ty} {ρ ρ' : Store}
1745+  (hTy : <{ ∅ / δ ⊢ t ⦂ τ }>)
1746+  (hStoreTy : δ ⊢ ρ)
1747+  (hEval : t / ρ ⟶ t' / ρ') :
1748+    ∃ δ', Extends δ' δ ∧ (<{ ∅ / δ' ⊢ t' ⦂ τ }>) ∧ (δ' ⊢ ρ') := by
1749+
1750+      generalize heq : (∅ : Context) = Γ at hTy
1751+      induction hTy generalizing t' with (
1752+        subst_vars <;>
1753+        -- discharge the goals where `t` doesn't step
1754+        inversion hEval <;>
1755+        -- handle the congruence cases where the store typing grows,
1756+        -- but in an uninteresting way
1757+        (try
1758+          -- we want to apply our inductive hypotheses, but we can't name
1759+          -- them in our automation. Instead, we restate the result that
1760+          -- we want and use `solve_by_elim` to figure out how to prove
1761+          -- this result using the unnamed `ih`
1762+          obtain ⟨δ', hExt, hTy', hStoreTy'⟩ : ∃ δ', Extends δ' δ ∧ _ ∧ (δ' ⊢ ρ') := by
1763+            solve_by_elim
1764+          exists δ'; constructor
1765+          assumption; constructor
1766+          constructor <;> solve_by_elim [store_weakening] using StlcRefTyping
1767+          assumption) <;>
1768+        -- handle the cases where the store doesn't grow
1769+        (try
1770+          exists δ; constructor
1771+          apply extends_refl; constructor
1772+          solve_by_elim using StlcRefTyping
1773+          assumption))
1774+    | app h₁ h₂ ih₁ ih₂ =>
1775+      inversion h₁
1776+      exists δ; constructor
1777+      apply extends_refl; constructor
1778+      apply_rules [substitution_preserves_typing] using StlcRefTyping
1779+      assumption
1780+    | @ref_ _ _ τ₁ =>
1781+      exists δ.concat τ₁; constructor
1782+      · rw [List.concat_eq_append]; apply extends_app
1783+      · constructor
1784+        · have h : <{Ref τ₁}> = <{Ref ~((δ.concat τ₁)[ρ.length])}> := by
1785+            simp_all [StoreWellTyped, MyGetElem.getElem]
1786+          rw [h]
1787+          constructor
1788+          simp [StoreWellTyped] at hStoreTy ⊢; lia
1789+        · apply store_well_typed_app <;> assumption
1790+    | deref h =>
1791+      inversion h
1792+      exists δ; constructor
1793+      apply extends_refl; constructor
1794+      have ⟨_, h₂⟩ := hStoreTy; apply h₂; assumption
1795+      assumption
1796+    | assign h₁ =>
1797+      inversion h₁
1798+      exists δ; constructor
1799+      apply extends_refl; constructor
1800+      constructor
1801+      apply assign_pres_store_typing <;> assumption
1802+
1803+--  This shorter proof only handles the interesting cases (`app`, `deref`,
1804+--  `assign`, and `ref`) manually, and solves all the mechanical ones
1805+--  automatically.
1806+
1807+--  ### Exercise (3 stars): preservation_informal (Manually graded) ⭐⭐⭐
1808+
1809+--  Write a careful informal proof of the preservation theorem,
1810+--  concentrating on the `app`, `deref`, `assign`, and `ref` cases.
1811+
1812+--  ### Progress
1813+
1814+--  As we've said, progress for this system is pretty easy to prove; the
1815+--  proof is very similar to the proof of progress for the STLC, with a few
1816+--  new cases for the new syntactic constructs.
1817+
1818+theorem progress (δ : StoreTy) (t : Tm) (τ : Ty) (ρ : Store)
1819+  (hTy : <{ ∅ / δ ⊢ t ⦂ τ }>)
1820+  (hStoreTy : δ ⊢ ρ) :
1821+  (t.IsValue ∨ ∃ t' ρ', t / ρ ⟶ t' / ρ') := by
1822+    have ⟨hLen, _⟩ := hStoreTy
1823+    generalize heq : (∅ : Context) = Γ at hTy
1824+    induction hTy with (subst_vars; first
1825+      | contradiction
1826+      -- discharge cases where `t` is obviously a value
1827+      | try (left; constructor; done))
1828+    | app h₁ _ ih₁ ih₂ =>
1829+      right; cases ih₁ (by rfl) with
1830+      -- t₁ is a value
1831+      | inl hv₁ =>
1832+        cases ih₂ (by rfl) with
1833+        -- t₂ is a value
1834+        | inl hv₂ =>
1835+          cases hv₁ <;> try contradiction
1836+          apply Exists.intro; apply Exists.intro; solve_by_elim using StlcRefEval
1837+        -- t₂ steps
1838+        | inr hs₂ =>
1839+          have ⟨t₂', ρ', hs₂⟩ := hs₂
1840+          apply Exists.intro; apply Exists.intro; solve_by_elim using StlcRefEval
1841+      -- t₁ steps
1842+      | inr hs₁ =>
1843+        have ⟨t₁', ρ', hs₁⟩ := hs₁
1844+        apply Exists.intro; apply Exists.intro; solve_by_elim using StlcRefEval
1845+    | succ h ih
1846+    | pred h ih =>
1847+      -- these two cases are the same
1848+      right; cases ih (by rfl) with
1849+      -- t₁ is a value
1850+      | inl hv =>
1851+        cases hv <;> try contradiction
1852+        apply Exists.intro; apply Exists.intro; solve_by_elim using StlcRefEval
1853+      -- t₁ steps
1854+      | inr hs =>
1855+        have ⟨t₁', ρ', hs⟩ := hs
1856+        apply Exists.intro; apply Exists.intro; solve_by_elim using StlcRefEval
1857+    | mult h₁ h₂ ih₁ ih₂ =>
1858+      right; cases ih₁ (by rfl) with
1859+      -- t₁ is a value
1860+      | inl hv₁ =>
1861+        cases ih₂ (by rfl) with
1862+        -- t₂ is a value
1863+        | inl hv₂ =>
1864+          cases hv₁ <;> try contradiction
1865+          cases hv₂ <;> try contradiction
1866+          apply Exists.intro; apply Exists.intro; solve_by_elim using StlcRefEval
1867+        -- t₂ steps
1868+        | inr hs₂ =>
1869+          have ⟨t₂', ρ', hs₂⟩ := hs₂
1870+          apply Exists.intro; apply Exists.intro; solve_by_elim using StlcRefEval
1871+      -- t₁ steps
1872+      | inr hs₁ =>
1873+        have ⟨t₁', ρ', hs₁⟩ := hs₁
1874+        apply Exists.intro; apply Exists.intro; solve_by_elim using StlcRefEval
1875+    | ite0 h₁ _ _ ih₁ _ _ =>
1876+      right; cases ih₁ (by rfl) with
1877+      -- t₁ is a value
1878+      | inl hv₁ =>
1879+        cases hv₁ with (try contradiction)
1880+        | nat n =>
1881+          cases n <;> (apply Exists.intro; apply Exists.intro; solve_by_elim using StlcRefEval)
1882+      -- t₁ steps
1883+      | inr hs₁ =>
1884+        have ⟨t₁', ρ', hs₁⟩ := hs₁
1885+        apply Exists.intro; apply Exists.intro; solve_by_elim using StlcRefEval
1886+    | ref_ _ ih =>
1887+      right; cases ih (by rfl) with
1888+      -- t₁ is a value
1889+      | inl hv =>
1890+        apply Exists.intro; apply Exists.intro; solve_by_elim using StlcRefEval
1891+      -- t₁ steps
1892+      | inr hs =>
1893+        have ⟨t₁', ρ', hs⟩ := hs
1894+        apply Exists.intro; apply Exists.intro; solve_by_elim using StlcRefEval
1895+    | deref h ih =>
1896+      right; cases ih (by rfl) with
1897+      -- t₁ is a value; its typing tells us `l < δ.length`
1898+      | inl hv =>
1899+        cases hv with (inversion h)
1900+        | loc_ l => exists ρ[l], ρ; apply Step.derefLoc; lia
1901+      -- t₁ steps
1902+      | inr hs =>
1903+        have ⟨t₁', ρ', hs⟩ := hs
1904+        apply Exists.intro; apply Exists.intro; solve_by_elim using StlcRefEval
1905+    | @assign _ _ t₂ _ h₁ _ ih₁ ih₂ =>
1906+      right; cases ih₁ (by rfl) with
1907+      -- t₁ is a value
1908+      | inl hv₁ =>
1909+        cases ih₂ (by rfl) with
1910+        -- t₂ is a value
1911+        | inl hv₂ =>
1912+          cases hv₁ with (inversion h₁)
1913+          | loc_ l => exists <{ unit }>, ρ.set l t₂; apply Step.assign hv₂; lia
1914+        -- t₂ steps
1915+        | inr hs₂ =>
1916+          have ⟨_, _, _⟩ := hs₂
1917+          apply Exists.intro; apply Exists.intro; solve_by_elim using StlcRefEval
1918+      -- t₁ steps
1919+      | inr hs₁ =>
1920+        have ⟨t₁', ρ', hs₁⟩ := hs₁
1921+        apply Exists.intro; apply Exists.intro; solve_by_elim using StlcRefEval
1922+
1923+--  Like the earlier preservation proof, many of these cases are
1924+--  repetitive. Once again we can make the proof more concise using
1925+--  automation:
1926+
1927+theorem progress_shorter (δ : StoreTy) (t : Tm) (τ : Ty) (ρ : Store)
1928+  (hTy : <{ ∅ / δ ⊢ t ⦂ τ }>)
1929+  (hStoreTy : δ ⊢ ρ) :
1930+  (t.IsValue ∨ ∃ t' ρ', t / ρ ⟶ t' / ρ') := by
1931+    have ⟨hLen, _⟩ := hStoreTy
1932+    generalize heq : (∅ : Context) = Γ at hTy
1933+    induction hTy with (
1934+      subst_vars; first
1935+      | contradiction
1936+      -- discharge cases where `t` is obviously a value
1937+      | (left; constructor; done)
1938+      -- otherwise, `t` steps
1939+      | (right
1940+         -- we use the same trick as in the preservation proof
1941+         -- to get around our unnamed `ih`
1942+         (obtain hv | ⟨t', ρ', hs⟩ : Tm.IsValue _ ∨ ∃ t' ρ', _ / ρ ⟶ t' / ρ' := by
1943+           solve_by_elim) <;>
1944+         -- handle simple cases where `t`'s type gives us
1945+         -- one possible value
1946+         try
1947+           (try (cases hv <;> try contradiction)) <;>
1948+           (apply Exists.intro; apply Exists.intro; solve_by_elim using StlcRefEval)))
1949+    | app h₁ _ _ ih₂ =>
1950+      cases hv <;> inversion h₁
1951+      obtain hv₂ | ⟨t₂', ρ', hs₂⟩ := ih₂ (by rfl) <;>
1952+      (apply Exists.intro; apply Exists.intro; solve_by_elim using StlcRefEval)
1953+    | mult h₁ h₂ _ ih₂ =>
1954+      cases hv <;> try contradiction
1955+      cases ih₂ (by rfl) with
1956+      | inl hv₂ =>
1957+        cases hv₂ <;> try contradiction
1958+        apply Exists.intro; apply Exists.intro; solve_by_elim using StlcRefEval
1959+      | inr hs₂ =>
1960+        have ⟨t₂', ρ', hs₂⟩ := hs₂
1961+        apply Exists.intro; apply Exists.intro; solve_by_elim using StlcRefEval
1962+    | ite0 h₁ =>
1963+      cases hv with (inversion h₁)
1964+      | nat n =>
1965+        cases n <;>
1966+        (apply Exists.intro; apply Exists.intro; solve_by_elim using StlcRefEval)
1967+    | deref h =>
1968+      cases hv <;> inversion h
1969+      apply Exists.intro; apply Exists.intro; apply Step.derefLoc; lia
1970+    | assign h₁ _ _ ih₂ =>
1971+      cases hv <;> inversion h₁
1972+      cases ih₂ (by rfl) with
1973+      | inl hv₂ =>
1974+        apply Exists.intro; apply Exists.intro; apply Step.assign hv₂; lia
1975+      | inr hs₂ =>
1976+        have ⟨t₂', ρ', hs₂⟩ := hs₂
1977+        apply Exists.intro; apply Exists.intro; solve_by_elim using StlcRefEval
1978+
1979+--  ## References and Nontermination
1980+
1981+--  An important fact about the STLC is that it is *normalizing* — that is,
1982+--  every well-typed term can be reduced to a value in a finite number of
1983+--  steps.
1984+--
1985+--  What about STLC + references? Surprisingly, adding references causes us
1986+--  to lose the normalization property: there exist well-typed terms in the
1987+--  STLC + references which can continue to reduce forever, without ever
1988+--  reaching a normal form!
1989+--
1990+--  How can we construct such a term? The main idea is to make a function
1991+--  which calls itself. We first make a function which calls another
1992+--  function stored in a reference cell; the trick is that we then smuggle
1993+--  in a reference to itself!
1994+--
1995+--         (λR: Ref (Unit → Unit),
1996+--              R := (λx:Unit,(!R) unit); (!R) unit)
1997+--      (ref (λX:Unit.unit))
1998+--
1999+--  First, `ref (λX:Unit.unit)` creates a reference to a cell of type
2000+--  `Unit → Unit`. We then pass this reference as the argument to a
2001+--  function which binds it to the name `R`, and assigns to it the function
2002+--  `λX:Unit.(!R) unit` — that is, the function which ignores its argument
2003+--  and calls the function stored in `R` on the argument `unit`; but of
2004+--  course, that function is itself! To start the divergent loop, we
2005+--  execute the function stored in the cell by evaluating `(!r) unit`.
2006+--
2007+--  Here is the divergent term in Lean:
2008+
2009+namespace RefsAndNontermination
2010+
2011+def loop_fun := <{ λX : Unit. (!R) unit }>
2012+
2013+def loop :=
2014+  <{ (λR : Ref (Unit → Unit). (( R := (λX : Unit. (!R) unit) );  ( (! R) unit ) ))
2015+     (ref (λX : Unit. unit)) }>
2016+
2017+--  This term is well typed:
2018+
2019+theorem loop_typeable : ∃ τ, <{ ∅ / [] ⊢ loop ⦂ τ }> := by
2020+  apply Exists.intro
2021+  apply_rules using StlcRefTyping
2022+
2023+--  To show formally that the term diverges, we first define the
2024+--  `step_closure` of the single-step reduction relation, written `⟶+`.
2025+--  This is just like the reflexive step closure of single-step reduction
2026+--  (which we're been writing `⟶*`), except that it is not reflexive:
2027+--  `t ⟶+ t'` means that `τ` can reach `t'` by *one or more* steps of
2028+--  reduction.
2029+
2030+inductive StepClosure {X:Type} (R: Relation X) : X → X → Prop :=
2031+  | one {x y : X} (h₁ : R x y) : StepClosure R x y
2032+  | step {x y z : X} (h₁ : R x y) (h₂ : StepClosure R y z) : StepClosure R x z
2033+
2034+scoped notation:40
2035+  t:71 " / " ρ:41 " ⟶+ " t':71 " / " ρ':41 =>
2036+  StepClosure Step (t, ρ) (t', ρ')
2037+
2038+--  Now, we can show that the expression `loop` reduces to the expression
2039+--  `!(loc 0) unit` and the size-one store `[R:=(loc 0)] loop_fun`.
2040+--
2041+--  As a convenience, we introduce a slight variant of the `normalize`
2042+--  tactic, called `reduce`, which tries solving the goal with `Multi.refl`
2043+--  at each step, instead of waiting until the goal can't be reduced any
2044+--  more. Of course, the whole point is that `loop` doesn't normalize, so
2045+--  the old `normalize` tactic would just go into an infinite loop reducing
2046+--  it forever!
2047+
2048+syntax "reduce" " using " ident,+ : tactic
2049+
2050+macro_rules
2051+  | `(tactic| reduce using $xs,*) =>
2052+    `(tactic|
2053+      repeat
2054+        (apply Multi.step
2055+         · solve_by_elim (maxDepth := 15) (constructor := false) [Nat.le.refl, Nat.le.step] using $xs,*
2056+         try apply Multi.refl))
2057+
2058+--  Next, we use `reduce` to show that `loop` steps to `!(loc 0) unit`,
2059+--  starting from the ∅ store.
2060+
2061+theorem loop_steps_to_loop_fun :
2062+  loop / [] ⟶*  <{ (! (loc 0)) unit }> / [<{ [R := loc 0] loop_fun }>] := by
2063+    reduce using StlcRefEval
2064+
2065+--  Finally, we show that the latter expression reduces in two steps to
2066+--  itself!
2067+
2068+theorem loop_fun_step_self :
2069+  <{ (! (loc 0)) unit }> / [<{ [R := loc 0] loop_fun }>] ⟶+
2070+  <{ (! (loc 0)) unit }> / [<{ [R := loc 0] loop_fun }>] := by
2071+    apply StepClosure.step; solve_by_elim using StlcRefEval
2072+    apply StepClosure.one; solve_by_elim using StlcRefEval
2073+
2074+--  ### Exercise (4 stars): factorial_ref ⭐⭐⭐⭐
2075+
2076+--  Use the above ideas to implement a factorial function in STLC with
2077+--  references. (There is no need to prove formally that it really behaves
2078+--  like the factorial. Just uncomment the example below to make sure it
2079+--  gives the correct result when applied to the argument `4`.)
2080+
2081+def factorial : Tm :=
2082+  sorry
2083+
2084+theorem factorial_type : <{ ∅ / [] ⊢ factorial ⦂ (Nat → Nat) }> := by
2085+  sorry
2086+
2087+--  If your definition is correct, you should be able to finish the example
2088+--  below; the proof should be fully automatic using the `reduce` tactic,
2089+--  once the witness is supplied.
2090+
2091+theorem factorial_4 : ∃ (ρ : Store), <{ factorial 4 }> / [] ⟶* .const 24 / ρ := by
2092+  sorry
2093+
2094+--  (End of exercise)
2095+
2096+end RefsAndNontermination
2097+
2098+--  ## Additional Exercises
2099+
2100+--  ### Exercise (5 stars): garbage_collector (Optional) ⭐⭐⭐⭐⭐
2101+
2102+--  Challenge problem: modify our formalization to include an account of
2103+--  garbage collection, and prove that it satisfies whatever nice
2104+--  properties you can think to prove about it.
2105+
2106+--  (End of exercise)
2107+
2108+end STLCRef
2109+
2110+-- Source revision: a06e066, committed 2026-10-27 16:51 UTC

TS/Slang.lean

653653 --  switch between points of view at will — exactly what we did above in
654654 --  `Slang.Aexp.evalR_iff_eval` and `Slang.Bexp.evalR_iff_eval`.
655655 
656--- Source revision: 2ca0e09, committed 2026-10-23 15:44 UTC
656+-- Source revision: a06e066, committed 2026-10-27 16:51 UTC

TS/Smallstep.lean

231231 --  reviewing that chapter may be useful if the treatment here feels too
232232 --  terse.)
233233 --
234---  A *binary relation* on a type `X` is a family of propositions
235---  parameterized by two elements of `X` — i.e., a proposition about pairs
236---  of elements of `X`.
237-
238-def Relation (X : Type) := X → X → Prop
234+--  A *binary relation* on a type `α` is a family of propositions
235+--  parameterized by two elements of `α` — i.e., a proposition about pairs
236+--  of elements of `α`. The type of a binary relation on a type `α` is
237+--  `α → α → Prop`.
238+
239+def Relation (α : Type) := α → α → Prop
239240 
240241 --  Our main examples of such relations in this chapter will be the
241242 --  single-step reduction relation, `⟶`, and its multi-step variant, `⟶*`,
267268 --
268269 --  Formally,
269270 
270-def Deterministic {X : Type} (R : Relation X) : Prop :=
271-  ∀ x y₁ y₂ : X, R x y₁ → R x y₂ → y₁ = y₂
271+def Deterministic {α : Type} (R : Relation α) : Prop :=
272+  ∀ x y₁ y₂ : α, R x y₁ → R x y₂ → y₁ = y₂
272273 
273274 namespace SimpleArith2
274275 
277278   induction h₁ generalizing y₂ with
278279   | plus n₁ n₂ =>
279280       intro h₂
280-      cases h₂ <;> first | rfl | cases ‹SimpleArith1.Step (.c _) _›
281+      cases h₂ <;> try contradiction
282+      rfl
281283   | plusLeft t₁ t₁' t₂ hs ih =>
282284       intro h₂
283-      cases h₂ <;> first | cases ‹SimpleArith1.Step (.c _) _› | rw [ih _ ‹SimpleArith1.Step t₁ _›]
285+      cases h₂ <;> try contradiction
286+      case plusLeft.plusLeft h => rw [ih _ h]
284287   | plusRight n₁ t₂ t₂' hs ih =>
285288       intro h₂
286-      cases h₂ <;> first | cases ‹SimpleArith1.Step (.c _) _› | rw [ih _ ‹SimpleArith1.Step t₂ _›]
289+      cases h₂ <;> try contradiction
290+      case plusRight.plusRight h => rw [ih _ h]
287291 
288292 end SimpleArith2
289293 
413417 
414418 theorem strong_progress (t : Tm) : IsValue t ∨ ∃ t', t ⟶ t' := by
415419   induction t with
416-  | c n => left; exact .const n
420+  | c n => left; constructor
417421   | p t₁ t₂ ih₁ ih₂ =>
418422       right
419423       cases ih₁ with
423427               cases hv₁ with
424428               | const n₁ =>
425429                   cases hv₂ with
426-                  | const n₂ => exact ⟨.c (n₁ + n₂), .plus n₁ n₂⟩
430+                  | const n₂ =>
431+                      exists .c (n₁ + n₂)
432+                      apply Step.plus
427433           | inr h₂ =>
428434               obtain ⟨t₂', ht₂⟩ := h₂
429-              exact ⟨.p t₁ t₂', .plusRight t₁ t₂ t₂' hv₁ ht₂⟩
435+              exists .p t₁ t₂'
436+              apply Step.plusRight
437+              · exact hv₁
438+              · exact ht₂
430439       | inr h₁ =>
431440           obtain ⟨t₁', ht₁⟩ := h₁
432-          exact ⟨.p t₁' t₂, .plusLeft t₁ t₁' t₂ ht₁⟩
441+          exists .p t₁' t₂
442+          apply Step.plusLeft
443+          exact ht₁
433444 
434445 --  This important property is called *strong progress*, because every term
435446 --  either is a value or can "make progress" by stepping to some other
441452 --  that do *not* make progress in this sense. Let's give a name to "terms
442453 --  that cannot make progress." We'll call them *normal forms*.
443454 
444-def IsNormalForm {X : Type} (R : Relation X) (t : X) : Prop :=
455+def IsNormalForm {α : Type} (R : Relation α) (t : α) : Prop :=
445456   ¬ ∃ t', R t t'
446457 
447458 --  Note that this definition specifies what it is to be a normal form for
448---  an *arbitrary* relation `R` over an arbitrary type `X`, not just for
459+--  an *arbitrary* relation `R` over an arbitrary type `α`, not just for
449460 --  the particular single-step reduction relation over terms that we are
450461 --  interested in at the moment. We'll re-use the same terminology for
451462 --  talking about other relations later in the course.
465476     (h : IsNormalForm Step t) : IsValue t := by
466477   cases strong_progress t with
467478   | inl hv => exact hv
468-  | inr hstep => exact absurd hstep h
479+  | inr hstep => contradiction
469480 
470481 theorem nf_same_as_value (t : Tm) :
471482     IsNormalForm Step t ↔ IsValue t := by
472-  exact ⟨nf_is_value t, value_is_nf t⟩
483+  constructor
484+  · apply nf_is_value
485+  · apply value_is_nf
473486 
474487 --  Why is this interesting? Because `IsValue` is a *syntactic* concept —
475488 --  it is defined by looking at the way a term is written — while
527540 
528541 theorem value_not_same_as_normal_form :
529542     ∃ v, IsValue v ∧ ¬ IsNormalForm Step v := by
530-  apply Exists.intro (.p (.c 0) (.c 0))
531-  apply And.intro (.funny _ 0)
532-  sorry
543+  exists .p (.c 0) (.c 0)
544+  constructor
545+  · apply IsValue.funny
546+  · sorry
533547 
534548 --  (End of exercise)
535549 
570584 
571585 theorem value_not_same_as_normal_form :
572586     ∃ v, IsValue v ∧ ¬ IsNormalForm Step v := by
573-  apply Exists.intro (.c 5)
574-  apply And.intro (.const 5)
575-  sorry
587+  exists .c 5
588+  constructor
589+  · apply IsValue.const
590+  · sorry
576591 
577592 end Temp2
578593 
609624 
610625 theorem value_not_same_as_normal_form :
611626     ∃ t, ¬ IsValue t ∧ IsNormalForm Step t := by
612-  apply Exists.intro (.p (.c 1) (.p (.c 1) (.c 2)))
613-  apply And.intro
627+  exists .p (.c 1) (.p (.c 1) (.c 2))
628+  constructor
614629   · sorry
615630   · sorry
616631 
635650 --  define a new relation `Multi R`, called the *multi-step closure of
636651 --  `R`*, as follows.
637652 
638-inductive Multi {X : Type} (R : Relation X) : X → X → Prop where
639-  | refl (x : X) : Multi R x x
640-  | step (x y z : X) (h₁ : R x y) (h₂ : Multi R y z) : Multi R x z
653+inductive Multi {α : Type} (R : Relation α) : α → α → Prop where
654+  | refl (x : α) : Multi R x x
655+  | step (x y z : α) (h₁ : R x y) (h₂ : Multi R y z) : Multi R x z
641656 
642657 --  The effect of this definition is that `Multi R` relates two elements
643658 --  `x` and `y` if
686701 --  case of multi-step executions. (It is this fact that justifies the word
687702 --  "closure" in "multi-step closure of `R`.")
688703 
689-theorem multi_single {X : Type} (R : Relation X) (x y : X)
704+theorem multi_single {α : Type} (R : Relation α) (x y : α)
690705     (h : R x y) : Multi R x y := by
691-  exact .step x y y h (.refl y)
706+  apply Multi.step (y := y)
707+  · exact h
708+  · rfl
692709 
693710 --  Third, `Multi R` is *transitive*.
694711 
695-theorem multi_trans {X : Type} (R : Relation X) (x y z : X)
712+theorem multi_trans {α : Type} (R : Relation α) (x y z : α)
696713     (g : Multi R x y) (h : Multi R y z) : Multi R x z := by
697714   induction g with
698715   | refl a => exact h
699-  | step a b c h₁ h₂ ih => exact .step a b z h₁ (ih h)
716+  | step a b c h₁ h₂ ih =>
717+      apply Multi.step (y := b)
718+      · exact h₁
719+      · exact ih h
700720 
701721 --  In particular, for the `Multi Step` relation on terms, if `t₁ ⟶* t₂`
702722 --  and `t₂ ⟶* t₃`, then `t₁ ⟶* t₃`.
719739     (.p (.p (.c 0) (.c 3)) (.p (.c 2) (.c 4)))
720740       ⟶* .c ((0 + 3) + (2 + 4)) := by
721741   apply Multi.step (y := .p (.c (0 + 3)) (.p (.c 2) (.c 4)))
722-  · exact .plusLeft _ _ _ (.plus 0 3)
742+  · apply Step.plusLeft
743+    apply Step.plus
723744   apply Multi.step (y := .p (.c (0 + 3)) (.c (2 + 4)))
724-  · exact .plusRight _ _ _ (.const _) (.plus 2 4)
725-  · exact multi_single _ _ _ (.plus (0 + 3) (2 + 4))
745+  · apply Step.plusRight
746+    · apply IsValue.const
747+    · apply Step.plus
748+  · apply multi_single
749+    apply Step.plus
726750 
727751 --  ### Exercise (1 star): test_multistep_2 (Optional) ⭐
728752 
753777 --  If `t` reduces to `t'` in zero or more steps and `t'` is a normal form,
754778 --  we say that "`t'` is *a normal form of* `t`."
755779 
756-def IsNormalFormOf {X : Type} (R : Relation X) (t t' : X) : Prop :=
780+def IsNormalFormOf {α : Type} (R : Relation α) (t t' : α) : Prop :=
757781   Multi R t t' ∧ IsNormalForm R t'
758782 
759783 --  We have already seen that, for our language, single-step reduction is
782806 --  `IsNormalFormOf` is a *total* function. We say the `Step` relation is
783807 --  *normalizing*. To prove it, we need a couple of congruence lemmas.
784808 
785-def Normalizing {X : Type} (R : Relation X) : Prop :=
809+def Normalizing {α : Type} (R : Relation α) : Prop :=
786810   ∀ t, ∃ t', IsNormalFormOf R t t'
787811 
788812 theorem multistep_congr_1 (t₁ t₁' t₂ : Tm) (h : t₁ ⟶* t₁') :
789813     (.p t₁ t₂) ⟶* (.p t₁' t₂) := by
790814   induction h with
791815   | refl x => exact .refl _
792-  | step x y z h₁ h₂ ih => exact .step _ (.p y t₂) _ (.plusLeft x y t₂ h₁) ih
816+  | step x y z h₁ h₂ ih =>
817+      apply Multi.step (y := .p y t₂)
818+      · apply Step.plusLeft
819+        exact h₁
820+      · exact ih
793821 
794822 --  ### Exercise (2 stars): multistep_congr_2 ⭐⭐
795823 
823851 theorem step_normalizing : Normalizing Step := by
824852   intro t
825853   induction t with
826-  | c n => exact ⟨.c n, .refl _, (nf_same_as_value _).mpr (.const n)⟩
854+  | c n =>
855+      exists .c n
856+      constructor
857+      · apply Multi.refl
858+      · apply (nf_same_as_value _).mpr
859+        apply IsValue.const
827860   | p t₁ t₂ ih₁ ih₂ =>
828861       obtain ⟨t₁', hs₁, hnf₁⟩ := ih₁
829862       obtain ⟨t₂', hs₂, hnf₂⟩ := ih₂
830863       obtain ⟨n₁⟩ := (nf_same_as_value _).mp hnf₁
831864       obtain ⟨n₂⟩ := (nf_same_as_value _).mp hnf₂
832-      apply Exists.intro (.c (n₁ + n₂))
833-      apply And.intro _ ((nf_same_as_value _).mpr (.const _))
834-      apply multi_trans _ _ _ _ (multistep_congr_1 t₁ (.c n₁) t₂ hs₁)
835-      apply multi_trans _ _ _ _ (multistep_congr_2 (.c n₁) t₂ (.c n₂) (.const n₁) hs₂)
836-      exact multi_single _ _ _ (.plus n₁ n₂)
865+      exists .c (n₁ + n₂)
866+      constructor
867+      · apply multi_trans _ _ _ _ (multistep_congr_1 t₁ (.c n₁) t₂ hs₁)
868+        apply multi_trans _ _ _ _ (multistep_congr_2 (.c n₁) t₂ (.c n₂) (.const n₁) hs₂)
869+        apply multi_single
870+        apply Step.plus
871+      · apply (nf_same_as_value _).mpr
872+        apply IsValue.const
837873 
838874 --  ### Equivalence of Big-Step and Small-Step
839875 
10091045 example :
10101046     (Aexp.plus (.num 3) (.plus (.num 2) (.num 1)))
10111047       ⟶a (.plus (.num 3) (.num 3)) := by
1012-  exact .plusRight (.num 3) (.plus 2 1)
1048+  apply AStep.plusRight
1049+  · apply IsAValue.num
1050+  · apply AStep.plus
10131051 
10141052 --  ### Exercise (2 stars): strong_progress_arith ⭐⭐
10151053 
11171155 example :
11181156     (Bexp.le (.plus (.num 1) (.num 1)) (.num 3))
11191157       ⟶b (.le (.num 2) (.num 3)) := by
1120-  exact .leLeft (.plus 1 1)
1158+  apply BStep.leLeft
1159+  apply AStep.plus
11211160 
11221161 --   ----------------------------------------
11231162 
12051244 theorem anstep_not_deterministic : ¬ Deterministic ANStep := by
12061245   intro hd
12071246   have s₁ : ANStep (.plus (.plus (.num 1) (.num 1)) (.plus (.num 2) (.num 2)))
1208-      (.plus (.num 2) (.plus (.num 2) (.num 2))) :=
1209-    .plusLeft (.plus 1 1)
1247+      (.plus (.num 2) (.plus (.num 2) (.num 2))) := by
1248+    exact .plusLeft (.plus 1 1)
12101249   have s₂ : ANStep (.plus (.plus (.num 1) (.num 1)) (.plus (.num 2) (.num 2)))
1211-      (.plus (.plus (.num 1) (.num 1)) (.num 4)) :=
1212-    .plusRight (.plus 2 2)
1250+      (.plus (.plus (.num 1) (.num 1)) (.num 4)) := by
1251+    exact .plusRight (.plus 2 2)
12131252   have heq := hd _ _ _ s₁ s₂
12141253   simp at heq
12151254 
12591298     (h : Multi AStep a a') : Multi ANStep a a' := by
12601299   induction h with
12611300   | refl x => exact .refl x
1262-  | step x y z h₁ _ ih => exact .step x y z (astep_imp_anstep x y h₁) ih
1301+  | step x y z h₁ _ ih =>
1302+      apply Multi.step (y := y)
1303+      · apply astep_imp_anstep
1304+        exact h₁
1305+      · exact ih
12631306 
12641307 --  ### Exercise (3 stars): astep_anstep_agree ⭐⭐⭐
12651308 
14461489     exists e', (.p (.c 3) (.p (.c 2) (.c 1))) ⟶* e' ∧ IsValue e' := by
14471490   sorry
14481491 
1449--- Source revision: 2ca0e09, committed 2026-10-23 15:44 UTC
1492+-- Source revision: a06e066, committed 2026-10-27 16:51 UTC

TS/Stlc.lean

567567   simp [subst, h]
568568 
569569 @[simp] theorem subst_app :
570-    <{ [x := s] (t₁ t₂) }> = <{ ([x := s] t₁) ([x := s] t₂) }> := rfl
571-
572-@[simp] theorem subst_tru : <{ [x := s] true }> = <{ true }> := rfl
573-
574-@[simp] theorem subst_fls : <{ [x := s] false }> = <{ false }> := rfl
570+    <{ [x := s] (t₁ t₂) }> = <{ ([x := s] t₁) ([x := s] t₂) }> := by rfl
571+
572+@[simp] theorem subst_tru : <{ [x := s] true }> = <{ true }> := by rfl
573+
574+@[simp] theorem subst_fls : <{ [x := s] false }> = <{ false }> := by rfl
575575 
576576 @[simp] theorem subst_ite :
577577     <{ [x := s] (if t₁ then t₂ else t₃) }> =
578-      <{ if [x := s] t₁ then [x := s] t₂ else [x := s] t₃ }> := rfl
578+      <{ if [x := s] t₁ then [x := s] t₂ else [x := s] t₃ }> := by rfl
579579 
580580 --   ----------------------------------------
581581 
11761176 
11771177 end Stlc
11781178 
1179--- Source revision: 2ca0e09, committed 2026-10-23 15:44 UTC
1179+-- Source revision: a06e066, committed 2026-10-27 16:51 UTC

TS/StlcProp.lean

9696     -- `t = t₁ t₂`.  Proceed by cases on whether `t₁` is a value or steps.
9797     subst hΓ
9898     right
99-    cases ih₁ rfl with
99+    cases ih₁ (by rfl) with
100100     | inl hv₁ =>
101-      cases ih₂ rfl with
101+      cases ih₂ (by rfl) with
102102       | inl hv₂ =>
103103         obtain ⟨x, u, rfl⟩ := canonical_forms_fun t₁ _ _ h₁ hv₁
104104         exists <{ [x := t₂] u }>
115115   | ite Γ t₁ t₂ t₃ τ₁ h₁ h₂ h₃ ih₁ ih₂ ih₃ =>
116116     subst hΓ
117117     right
118-    cases ih₁ rfl with
118+    cases ih₁ (by rfl) with
119119     | inl hv₁ =>
120120       cases canonical_forms_bool t₁ h₁ hv₁ with
121121       | inl he =>
11951195 
11961196 end StlcArith
11971197 
1198--- Source revision: 2ca0e09, committed 2026-10-23 15:44 UTC
1198+-- Source revision: a06e066, committed 2026-10-27 16:51 UTC

TS/Sub.lean

13711371   induction ht with (subst_vars; first | trivial | try lia)
13721372   | sub Γ t₁ τ₁ τ₂ ht hs ih =>
13731373     apply sub_inversion_bool at hs; subst_vars
1374-    exact ih hv rfl
1374+    apply ih hv
1375+    rfl
13751376 
13761377 --  When you do the `products` exercise, add your canonical forms lemma for
13771378 --  products here:
14321433     | try (left; constructor; done)
14331434   )
14341435   | app Γ τ₁ τ₂ t₁ t₂ h₁ h₂ ih₁ ih₂ =>
1435-      right; cases ih₁ rfl with
1436+      right; cases ih₁ (by rfl) with
14361437       -- t₁ is a value
14371438       | inl ht₁ =>
1438-        cases ih₂ rfl with
1439+        cases ih₂ (by rfl) with
14391440         -- t₂ is a value
14401441         | inl ht₂ =>
14411442           apply canonical_forms_of_arrow_types at h₁
14511452         obtain ⟨t₁', ht₁⟩ := ht₁
14521453         exists <{t₁' t₂}>; apply_rules using StlcSubEval
14531454   | ite Γ t₁ t₂ t₃ τ h₁ h₂ h₃ ih₁ ih₂ ih₃ =>
1454-    right; cases ih₁ rfl with
1455+    right; cases ih₁ (by rfl) with
14551456     -- t₁ is a value
14561457     | inl ht₁ =>
14571458       apply canonical_forms_of_bool at h₁
15121513   | abs Γ x τ₁ τ₂ t₁ h i =>
15131514       inversion heq; exists τ₁; solve_by_elim using StlcSubTyping
15141515   | sub Γ t₁ τ₁ τ₂ ht hs ih =>
1515-      obtain ⟨σ₂, hs', ht'⟩ := ih rfl
1516+      obtain ⟨σ₂, hs', ht'⟩ := ih (by rfl)
15161517       exists σ₂; solve_by_elim using StlcSubTyping
15171518 
15181519 --  ### Exercise (3 stars): typing_inversion_var (Optional) ⭐⭐⭐
15401541   induction h with (subst_vars; try contradiction)
15411542   | unit => inversion heq; solve_by_elim using StlcSubTyping
15421543   | sub Γ t₁ τ₁ τ₂ ht hs ih =>
1543-      specialize ih rfl
1544+      specialize ih (by rfl)
15441545       solve_by_elim using StlcSubTyping
15451546 
15461547 --  -- Add your lemmas for products here when you get to that exercise
19271928 
19281929 end StlcSub
19291930 
1930--- Source revision: 2ca0e09, committed 2026-10-23 15:44 UTC
1931+-- Source revision: a06e066, committed 2026-10-27 16:51 UTC

TS/Types.lean

956956 --  for nonterminating programs? Why might we prefer the small-step
957957 --  semantics for stating preservation and progress?
958958 
959--- Source revision: 2ca0e09, committed 2026-10-23 15:44 UTC
959+-- 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