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