TS Student source diff
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