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