8. Sub: Subtyping
8.1. Concepts
8.1.1. A Motivating Example
Suppose we are writing a program involving two record types defined as follows:
Person = {name:String, age:Nat}
Student = {name:String, age:Nat, gpa:Nat}
Problem: In the pure STLC with records, the following term is not typable:
(λR:Person. (R.age)+1) {name="Pat",age=21,gpa=1}
This is a shame.
Idea: Introduce subtyping, formalizing the observation that "some types are better than others."
Safe substitution principle:
-
σis a subtype ofτ, writtenσ <: τ, if a value of typeσcan safely be used in any context where a value of typeτis expected.
8.1.2. Subtyping and Object-Oriented Languages
Subtyping plays a fundamental role in OO programming languages.
Roughly, an object can be thought of as a record of functions ("methods") and data values ("fields" or "instance variables").
-
Invoking a method
mof an objectoon some argumentsa₁..anconsists of projecting out themfield ofoand applying it toa₁..an.
The type of an object is a class (or an interface).
Classes are related by the subclass relation.
-
An object belonging to a subclass must provide all the methods and fields of one belonging to a superclass, plus possibly some more.
-
Thus a subclass object can be used anywhere a superclass object is expected.
-
Very handy for organizing large libraries
"Of course, real OO languages have lots of other features...
-
mutable fields
-
"private" and other visibility modifiers
-
method inheritance
-
static components
-
etc., etc.
We'll ignore all these and focus on core mechanisms.
8.1.3. The Subsumption Rule
τ₂ Our goal for this chapter is to add subtyping to the simply typed lambda-calculus (with some basic extensions). This involves two steps:
-
Defining a binary subtype relation between types.
-
Enriching the typing relation to take subtyping into account.
The second step is actually very simple. We add just a single rule to the typing relation: the so-called rule of subsumption:
Γ ⊢ t₁ ⦂ τ₁ τ₁ <: τ₂
-------------------------- (sub)
Γ ⊢ t₁ ⦂ τ₂
This rule says, intuitively, that it is OK to "forget" some of what we know about a term.
8.1.4. The Subtype Relation
The first step -- the definition of the relation σ <: τ -- is
where all the action is. Let's look at each of the clauses of its
definition.
8.1.4.1. Structural Rules
To start off, we impose two "structural rules" that are
independent of any particular type constructor: a rule of
transitivity, which says intuitively that, if σ is
better (richer, safer) than υ and υ is better than τ,
then σ is better than τ...
σ <: υ υ <: τ
---------------- (trans)
σ <: τ
... and a rule of reflexivity, since certainly any type τ is
as good as itself:
------ (refl)
τ <: τ
8.1.4.2. Products
Now we consider the individual type constructors, one by one, beginning with product types. We consider one pair to be a subtype of another if each of its components is.
σ₁ <: τ₁ σ₂ <: τ₂
-------------------- (prod)
σ₁ × σ₂ <: τ₁ × τ₂
Suppose we have functions F and G with these types:
F : C → Student
G : (C→Person) → D
Is it safe to allow the application G F?
Yes.
So we want:
C→Student <: C→Person
I.e., arrow is covariant in its right-hand argument.
Now suppose we have:
F : Person → C
G : (Student→C) → D
Is it safe to allow the application G F?
Again yes.
So we want:
Person → C <: Student → C
I.e., arrow is contravariant in its left-hand argument.
Putting these together...
τ₁ <: σ₁ σ₂ <: τ₂
-------------------- (arrow)
σ₁ → σ₂ <: τ₁ → τ₂
Suppose we have σ <: τ and υ <: δ. Which of the following
subtyping assertions is false?
(A) σ×υ <: τ×δ
(B) τ→υ <: σ→υ
(C) (σ→υ) → (σ×δ) <: (σ→υ) → (τ×υ)
(D) (τ×υ) → δ <: (σ×υ) → δ
(E) σ→υ <: σ→δ
Suppose again that we have σ <: τ and υ <: δ. Which of the
following is incorrect?
(A) (τ→τ)×υ <: (σ→τ)×δ
(B) τ→υ <: σ→δ
(C) (σ→υ) → (σ→δ) <: (τ→υ) → (τ→δ)
(D) (σ→δ) → δ <: (τ→υ) → δ
(E) σ → (δ→υ) <: σ → (υ→υ)
8.1.4.3. Records
What about subtyping for record types?
The basic intuition is that it is always safe to use a "bigger"
record in place of a "smaller" one. That is, given a record type,
adding extra fields will always result in a subtype. If some code
is expecting a record with fields x and y, it is perfectly safe
for it to receive a record with fields x, y, and z; the z
field will simply be ignored. For example,
{name:String, age:Nat, gpa:Nat} <: {name:String, age:Nat}
{name:String, age:Nat} <: {name:String}
{name:String} <: {}
This is known as "width subtyping" for records.
We can also create a subtype of a record type by replacing the type
of one of its fields with a subtype. If some code is expecting a
record with a field x of type τ, it will be happy with a record
having a field x of type σ as long as σ is a subtype of
τ. For example,
{x:Student} <: {x:Person}
This is known as "depth subtyping".
Finally, although the fields of a record type are written in a particular order, the order does not really matter. For example,
{name:String,age:Nat} <: {age:Nat,name:String}
This is known as "permutation subtyping".
We could formalize these requirements in a single subtyping rule for records as follows:
∀ jₖ in j₁..jₙ,
∃ iₚ in i₁..iₘ, such that
jₖ=iₚ and σₚ <: τₖ
---------------------------------- (rcd)
{i₁:σ₁...iₘ:σₘ} <: {j₁:τ₁...jₙ:τₙ}
That is, the record on the left should have all the field labels of the one on the right (and possibly more), while the types of the common fields should be in the subtype relation.
However, this rule is rather heavy and hard to read, so it is often
decomposed into three simpler rules, which can be combined using
trans to achieve all the same effects.
First, adding fields to the end of a record type gives a subtype:
n > m
--------------------------------- (rcdWidth)
{i₁:τ₁...iₙ:τₙ} <: {i₁:τ₁...iₘ:τₘ}
We can use rcdWidth to drop later fields of a multi-field
record while keeping earlier fields, showing for example that
{age:Nat,name:String} <: {age:Nat}.
Second, subtyping can be applied inside the components of a compound record type:
σ₁ <: τ₁ ... σₙ <: τₙ
---------------------------------- (rcdDepth)
{i₁:σ₁...iₙ:σₙ} <: {i₁:τ₁...iₙ:τₙ}
For example, we can use rcdDepth and rcdWidth together to
show that {y:Student, x:Nat} <: {y:Person}.
Third, subtyping can reorder fields. For example, we
want {name:String, gpa:Nat, age:Nat} <: Person, but we
haven't quite achieved this yet: using just rcdDepth and
rcdWidth we can only drop fields from the end of a record
type. So we add:
{i₁:σ₁...iₙ:σₙ} is a permutation of {j₁:τ₁...jₙ:τₙ}
--------------------------------------------------- (rcdPerm)
{i₁:σ₁...iₙ:σₙ} <: {j₁:τ₁...jₙ:τₙ}
It is worth noting that full-blown language designs may choose not to adopt all of these subtyping rules. For example, in Java:
-
Each class member (field or method) can be assigned a single index, adding new indices "on the right" as more members are added in subclasses (i.e., no permutation for classes).
-
A class may implement multiple interfaces -- so-called "multiple inheritance" of interfaces (i.e., permutation is allowed for interfaces).
-
In early versions of Java, a subclass could not change the argument or result types of a method of its superclass (i.e., no depth subtyping or no arrow subtyping, depending how you look at it).
8.1.4.4. ⊤
Finally, it is convenient to give the subtype relation a maximum
element -- a type that lies above every other type and is
inhabited by all (well-typed) values. We do this by adding to the
language one new type constant, called ⊤ (pronounced "⊤" and written ⊤),
together with a subtyping rule that places it above every other type in the
subtype relation:
-------- (⊤)
σ <: ⊤
The ⊤ type is an analog of the Object type in Java and C#.
8.1.4.5. Summary
In summary, we form the STLC with subtyping by starting with the pure STLC (over some set of base types) and then...
-
adding a base type
⊤, -
adding the rule of subsumption
Γ ⊢ t₁ ⦂ τ₁ τ₁ <: τ₂
-------------------------------- (sub)
Γ ⊢ t₁ ⦂ τ₂
to the typing relation, and
-
defining a subtype relation as follows:
σ <: υ υ <: τ
---------------- (trans)
σ <: τ
------ (refl)
τ <: τ
-------- (⊤)
σ <: ⊤
σ₁ <: τ₁ σ₂ <: τ₂
-------------------- (prod)
σ₁ × σ₂ <: τ₁ × τ₂
τ₁ <: σ₁ σ₂ <: τ₂
-------------------- (arrow)
σ₁ → σ₂ <: τ₁ → τ₂
n > m
--------------------------------- (rcdWidth)
{i₁:τ₁...iₙ:τₙ} <: {i₁:τ₁...iₘ:τₘ}
σ₁ <: τ₁ ... σₙ <: τₙ
---------------------------------- (rcdDepth)
{i₁:σ₁...iₙ:σₙ} <: {i₁:τ₁...iₙ:τₙ}
{i₁:σ₁...iₙ:σₙ} is a permutation of {j₁:τ₁...jₙ:τₙ}
--------------------------------------------------- (rcdPerm)
{i₁:σ₁...iₙ:σₙ} <: {j₁:τ₁...jₙ:τₙ}
Suppose we have σ <: τ and υ <: δ. Which of the following
subtyping assertions is false?
(A) σ×υ <: ⊤
(B) {i₁:σ,i₂:τ}→υ <: {i₁:σ,i₂:τ,i₃:δ}→υ
(C) (σ→τ) → (⊤ → ⊤) <: (σ→τ) → ⊤
(D) (⊤ → ⊤) → δ <: ⊤ → δ
(E) σ → {i₁:υ,i₂:δ} <: σ → {i₂:δ,i₁:υ}
How about these?
(A) {i₁:⊤} <: ⊤
(B) ⊤ → (⊤ → ⊤) <: ⊤ → ⊤
(C) {i₁:τ} → {i₁:τ} <: {i₁:τ,i₂:σ} → ⊤
(D) {i₁:τ,i₂:δ,i₃:δ} <: {i₁:σ,i₂:υ} × {i₃:δ}
(E) ⊤ → {i₁:υ,i₂:δ} <: {i₁:σ} → {i₂:δ,i₁:δ}
8.1.5. Exercises
What is the smallest type τ that makes the following
assertion true?
X:A ⊢ (λP:(A×τ). (P.snd) (P.fst)) (X, λZ:A. Z) ⦂ A
(A) ⊤
(B) A
(C) ⊤→⊤
(D) ⊤→A
(E) A→A
(F) A→⊤
What is the largest type τ that makes the following
assertion true?
X:A ⊢ (λP:(A×τ). (P.snd) (P.fst)) (X, λZ:A. Z) ⦂ A
(A) ⊤
(B) A
(C) ⊤→⊤
(D) ⊤→A
(E) A→A
(F) A→⊤
"The type Bool has no proper subtypes." (I.e., the only
type smaller than Bool is Bool itself.)
(A) True
(B) False
"Suppose σ, τ₁, and τ₂ are types with σ <: τ₁ → τ₂. Then
σ itself is an arrow type -- i.e., σ = σ₁ → σ₂ for some σ₁
and σ₂ -- with τ₁ <: σ₁ and σ₂ <: τ₂."
(A) True
(B) False
8.2. Formal Definitions
namespace StlcSub
open scoped MyGetElem
Most of the definitions needed to formalize what we've discussed
above -- in particular, the syntax and operational semantics of
the language -- are identical to what we saw in the last chapter.
We just need to extend the typing relation with the subsumption
rule and add a new inductive definition for the subtyping
relation. Let's first do the identical bits.
8.2.1. Core Definitions
8.2.1.1. Syntax
Omitting records, to avoid dealing with "..." stuff.
inductive Ty : Type where
| top : Ty
| bool : Ty
| base : String → Ty
| arrow : Ty → Ty → Ty
| unit : Ty
| prod : Ty → Ty → Ty
inductive Tm : Type where
| var : String → Tm
| app : Tm → Tm → Tm
| abs : String → Ty → Tm → Tm
| tru : Tm
| fls : Tm
| ite : Tm → Tm → Tm → Tm
| unit : Tm
| pair : Tm → Tm → Tm
| fst : Tm → Tm
| snd : Tm → Tm
This language uses the shared <{ ... }> notation from Stlc.
Capital Latin identifiers in term positions are Tm variables. In
type positions, Bool and Unit name the distinguished types above, while
other capital Latin identifiers, such as A, Int, or String, name
base types in Ty. Lowercase and Greek identifiers refer directly to
in-scope Lean variables, while arbitrary Lean expressions require ~
antiquotation.
Notation
scoped syntax:50 stlcTy:51 " × " stlcTy:50 : stlcTy
scoped syntax:max " ⊤ " : stlcTy
scoped syntax:50 "if " stlcTm:51 " then " stlcTm:50 " else " stlcTm:50 : stlcTm
scoped syntax:max " ( " stlcTm:60 " , " stlcTm:60 " ) " : stlcTm
namespace Elab
open StlcCommon
open Lean Meta Elab Term
def language : Language where
tyType := ``Ty
tmType := ``Tm
arrowCtor := ``Ty.arrow
varCtor := ``Tm.var
appCtor := ``Tm.app
absCtor := ``Tm.abs
-- defined later
subst := `StlcSub.subst
hasType := `StlcSub.HasType
def subTyHandler : TyElabHandler :=
fun recur k T => do
match T with
| `(stlcTy| ⊤) => do
return mkConst ``Ty.top
| `(stlcTy| Bool) => do
return mkConst ``Ty.bool
| `(stlcTy| Unit) => do
return mkConst ``Ty.unit
| `(stlcTy| $T₁:stlcTy × $T₂:stlcTy) => do
let T₁ ← recur T₁
let T₂ ← recur T₂
return mkApp2 (mkConst ``Ty.prod) T₁ T₂
| _ => k T
/--
Make unresolved type identifiers "base types".
This must run after `commonTyHandler`
so a Lean variable `τ : Ty` is implicitly antiquoted first.
-/
def baseTyHandler : TyElabHandler :=
fun _recur k T => do
match T with
| `(stlcTy| $id:ident) => do
match classifyIdent? id with
| some (.object, name) =>
return mkApp (mkConst ``Ty.base) (mkStrLit name)
| _ => k T
| _ => k T
def tyHandlers : TyElabHandler :=
subTyHandler.orElse ((commonTyHandler language).orElse baseTyHandler)
partial def elabTy : TyElab := tyHandlers elabTy <| unsupportedTy language
def subTmHandler : TmElabHandler :=
fun recur k Γ free t => do
match t with
| `(stlcTm| true) =>
return (mkConst ``Tm.tru, free)
| `(stlcTm| false) =>
return (mkConst ``Tm.fls, free)
| `(stlcTm| Bool) =>
throwError "`Bool` is not a valid term."
| `(stlcTm| Unit) =>
throwError "`Unit` is not a valid term."
| `(stlcTm| if $c:stlcTm then $t:stlcTm else $e:stlcTm) => do
let (c, free) ← recur Γ free c
let (t, free) ← recur Γ free t
let (e, free) ← recur Γ free e
return (mkApp3 (mkConst ``Tm.ite) c t e, free)
| `(stlcTm| unit) =>
return (mkConst ``Tm.unit, free)
| `(stlcTm| ($t₁:stlcTm, $t₂:stlcTm)) => do
let (t₁, free) ← recur Γ free t₁
let (t₂, free) ← recur Γ free t₂
return (mkApp2 (mkConst ``Tm.pair) t₁ t₂, free)
| `(stlcTm| fst $t:stlcTm) => do
let (t, free) ← recur Γ free t
return (mkApp (mkConst ``Tm.fst) t, free)
| `(stlcTm| snd $t:stlcTm) => do
let (t, free) ← recur Γ free t
return (mkApp (mkConst ``Tm.snd) t, free)
| _ => k Γ free t
def tmHandlers : TmElabHandler := subTmHandler.orElse (commonTmHandler language elabTy)
partial def elabTm : TmElab := tmHandlers elabTm unsupportedTm
def elabCtx : CtxElab :=
elabCtxCommon language elabTy
@[scoped term_elab StlcCommon.bracket]
def elabBracket : TermElab :=
fun stx expectedType? => do
let `(<{ $q:stlcQuoted }>) := stx
| throwUnsupportedSyntax
elabQuoted language elabTy elabTm elabCtx q expectedType?
end Elab
open scoped Elab
namespace Delab
open StlcCommon Elab Delab
open Lean PrettyPrinter Delaborator
@[app_unexpander Ty.top]
private def Ty.unexpandTop : Unexpander
| _ => `(<{ ⊤ }>)
@[app_unexpander Ty.bool]
private def Ty.unexpandBool : Unexpander
| stx => do
let Bool := mkObjectIdentFrom stx "Bool"
let T ← `(stlcTy| $Bool:ident)
`(<{ $T:stlcTy }>)
@[app_unexpander Ty.unit]
private def Ty.unexpandUnit : Unexpander
| stx => do
let Unit := mkObjectIdentFrom stx "Unit"
let T ← `(stlcTy| $Unit:ident)
`(<{ $T:stlcTy }>)
@[app_unexpander Ty.arrow]
private def Ty.unexpandArrow : Unexpander := Delab.unexpandArrow
@[app_unexpander Ty.prod]
private def Ty.unexpandProd : Unexpander
| `($_ $T₁ $T₂) => do
let T₁' := getTy T₁
let T₂' := getTy T₂
`(<{ $T₁':stlcTy × $T₂':stlcTy }>)
| _ => throw ()
private def reservedTyNames : String → Bool
| "Bool" | "Unit" => true
| _ => false
@[app_unexpander Ty.base]
private def Ty.unexpandBase : Unexpander
| stx@`($_ $s:str) => do
let name := s.getString
let id := mkObjectIdentFrom stx name
match classifyIdent? id, reservedTyNames name with
| some (.object, _), false =>
let T ← `(stlcTy| $id:ident)
`(<{ $T:stlcTy }>)
| _, _ => throw ()
| _ => throw ()
private def reservedTmNames : String → Bool
| "true" | "false" | "Bool"
| "Unit" | "unit" | "fst"
| "snd" => true
| _ => false
@[app_unexpander Tm.var]
private def Tm.unexpandVar : Unexpander :=
Delab.unexpandVar reservedTmNames ``Tm.var
@[app_delab Tm.var]
private def Tm.delabVar : Delab := Delab.delabVar ``Tm.var
@[app_unexpander Tm.app]
private def Tm.unexpandApp : Unexpander := Delab.unexpandApp
@[app_unexpander Tm.abs]
private def Tm.unexpandAbs : Unexpander := Delab.unexpandAbs
@[app_unexpander Tm.tru]
private def Tm.unexpandTru : Unexpander
| stx => do
let tru := mkObjectIdentFrom stx "true"
let t ← `(stlcTm| $tru:ident)
`(<{ $t:stlcTm }>)
@[app_unexpander Tm.fls]
private def Tm.unexpandFls : Unexpander
| stx => do
let fls := mkObjectIdentFrom stx "false"
let t ← `(stlcTm| $fls:ident)
`(<{ $t:stlcTm }>)
@[app_unexpander Tm.ite]
private def Tm.unexpandIte : Unexpander
| `($_ $c $t $e) => do
let c' := getTm c
let t' := getTm t
let e' := getTm e
`(<{if $c':stlcTm then $t':stlcTm else $e':stlcTm }>)
| _ => throw ()
@[app_unexpander Tm.unit]
private def Tm.unexpandUnit : Unexpander
| stx => do
let unit := mkObjectIdentFrom stx "unit"
let t ← `(stlcTm| $unit:ident)
`(<{ $t:stlcTm }>)
@[app_unexpander Tm.pair]
private def Tm.unexpandPair : Unexpander
| `($_ $t₁ $t₂) => do
let t₁' := getTm t₁
let t₂' := getTm t₂
`(<{ ($t₁':stlcTm, $t₂':stlcTm) }>)
| _ => throw ()
@[app_unexpander Tm.fst]
private def Tm.unexpandFst : Unexpander
| stx@`($_ $t) => do
let fst := mkObjectIdentFrom stx "fst"
let t' := getTm t
`(<{ $fst:ident $t':stlcTm }>)
| _ => throw ()
@[app_unexpander Tm.snd]
private def Tm.unexpandSnd : Unexpander
| stx@`($_ $t) => do
let snd := mkObjectIdentFrom stx "snd"
let t' := getTm t
`(<{ $snd:ident $t':stlcTm }>)
| _ => throw ()
end Delab
Checks that the extended grammar parses the way it should.
8.2.2. Substitution
The definition of substitution remains exactly the same as for the pure STLC.
def subst (x : String) (s : Tm) (t : Tm) : Tm :=
match t with
-- pure STLC
| .var y =>
if x = y then s else t
| .abs y τ t₁ =>
if x = y then t else <{ λ y : τ . [x := s] t₁ }>
| .app t₁ t₂ =>
<{ ([x := s] t₁) ([x := s] t₂) }>
-- unit
| .unit => <{ unit }>
-- bools
| .tru => <{ true }>
| .fls => <{ false }>
| .ite t₁ t₂ t₃ =>
<{ if [x := s] t₁ then [x := s] t₂ else [x := s] t₃ }>
-- Complete the following cases when you do the `products` exercise later
| .pair t₁ t₂ =>
sorry
| .fst t =>
sorry
| .snd t =>
sorry
Notation encoding
open Lean PrettyPrinter in
@[app_unexpander subst]
def unexpandSubst : Unexpander := StlcCommon.Delab.unexpandSubst
8.2.3. Reduction
Likewise the definitions of IsValue and Step.
inductive Tm.IsValue : Tm → Prop where
| abs (x : String) (τ₂ : Ty) (t₁ : Tm) :
IsValue <{λ x : τ₂ . t₁}>
| tru :
IsValue <{true}>
| fls :
IsValue <{false}>
| unit :
IsValue <{unit}>
-- Fill in more rules when you do the `products` exercise later
-- FILL IN HERE
attribute [StlcSubEval] Tm.IsValue.abs Tm.IsValue.tru Tm.IsValue.fls Tm.IsValue.unit
section
set_option hygiene false in
local notation:40 t:41 " ⟶ " t':41 => Step t t'
inductive Step : Tm → Tm → Prop where
-- pure STLC
| appAbs (x : String) (τ₂ : Ty) (t₁ v₂ : Tm) :
v₂.IsValue →
<{(λ x : τ₂ . t₁) v₂}> ⟶ <{ [x := v₂] t₁ }>
| app₁ (t₁ t₁' t₂ : Tm) :
t₁ ⟶ t₁' →
<{t₁ t₂}> ⟶ <{t₁' t₂}>
| app₂ (v₁ t₂ t₂' : Tm) :
v₁.IsValue →
t₂ ⟶ t₂' →
<{v₁ t₂}> ⟶ <{v₁ t₂'}>
-- booleans
| ifStep (t₁ t₁' t₂ t₃ : Tm) (h : t₁ ⟶ t₁') :
<{ if t₁ then t₂ else t₃ }> ⟶ <{ if t₁' then t₂ else t₃ }>
| ifTrue (t₂ t₃ : Tm) :
<{ if true then t₂ else t₃ }> ⟶ t₂
| ifFalse (t₂ t₃ : Tm) :
<{ if false then t₂ else t₃ }> ⟶ t₃
-- Fill in more rules when you do the `products` exercise later
-- FILL IN HERE
end
scoped notation:40 t:41 " ⟶ " t':41 => Step t t'
scoped notation:40 t:41 " ⟶* " t':41 => Multi Step t t'
-- Be sure to add your constructors for pairs to this list later
attribute [StlcSubEval] Step.appAbs Step.app₁ Step.app₂
Step.ifStep Step.ifTrue Step.ifFalse
-- FILL IN HERE
8.2.4. Subtyping
section
set_option hygiene false in
local notation:40 τ:41 " <: " τ':41 => Subtype τ τ'
inductive Subtype : Ty → Ty → Prop where
| refl {τ : Ty} :
τ <: τ
| trans {σ υ τ: Ty}
(h₁ : σ <: υ)
(h₂ : υ <: τ) :
σ <: τ
| top {σ : Ty} :
σ <: <{ ⊤ }>
| arrow { σ₁ σ₂ τ₁ τ₂ : Ty}
(h₁ : τ₁ <: σ₁)
(h₂ : σ₂ <: τ₂) :
<{ σ₁ → σ₂ }> <: <{ τ₁ → τ₂ }>
-- Fill in more rules when you do the `products` exercise later
-- FILL IN HERE
end
scoped notation:40 τ:41 " <: " τ':41 => Subtype τ τ'
attribute [StlcSubTyping] Subtype.refl Subtype.trans Subtype.top Subtype.arrow
-- FILL IN HERE
Note that we don't need any special rules for base types (Bool
and Base): they are automatically subtypes of themselves (by
refl) and ⊤ (by top), and that's all we want.
8.2.5. Typing
The only change to the typing relation is the addition of the rule
of subsumption, sub.
abbrev Context := PartialMap String Ty
inductive HasType : Context → Tm → Ty → Prop where
-- pure STLC
| var (Γ : Context) (x : String) (τ₁ : Ty) (h : Γ[x] = some τ₁) :
<{ Γ ⊢ ~(Tm.var x) ⦂ τ₁ }>
| abs (Γ : Context) (x : String) (τ₁ τ₂ : Ty) (t₁ : Tm)
(h : <{ x ↦ τ₂ ; Γ ⊢ t₁ ⦂ τ₁ }>) :
<{ Γ ⊢ λ x : τ₂ . t₁ ⦂ τ₂ → τ₁ }>
| app (Γ : Context) (τ₁ τ₂ : Ty) (t₁ t₂ : Tm)
(h₁ : <{ Γ ⊢ t₁ ⦂ τ₂ → τ₁ }>) (h₂ : <{ Γ ⊢ t₂ ⦂ τ₂ }>) :
<{ Γ ⊢ t₁ t₂ ⦂ τ₁ }>
-- booleans
| tru (Γ : Context) :
<{ Γ ⊢ true ⦂ Bool }>
| fls (Γ : Context) :
<{ Γ ⊢ false ⦂ Bool }>
| ite (Γ : Context) (t₁ t₂ t₃ : Tm) (τ : Ty)
(h₁ : <{ Γ ⊢ t₁ ⦂ Bool }>) (h₂ : <{ Γ ⊢ t₂ ⦂ τ }>)
(h₃ : <{ Γ ⊢ t₃ ⦂ τ }>) :
<{ Γ ⊢ if t₁ then t₂ else t₃ ⦂ τ }>
-- unit
| unit (Γ : Context) :
<{ Γ ⊢ unit ⦂ Unit }>
-- subsumption
| sub (Γ : Context) (t₁ : Tm) (τ₁ τ₂ : Ty)
(ht : <{ Γ ⊢ t₁ ⦂ τ₁ }>)
(hs : τ₁ <: τ₂) :
<{ Γ ⊢ t₁ ⦂ τ₂ }>
-- Fill in more rules when you do the `products` exercise later
-- FILL IN HERE
-- Make sure to add your constructors here
attribute [StlcSubTyping] HasType.var HasType.abs HasType.app
HasType.ite HasType.tru HasType.fls HasType.unit
-- FILL IN HERE
Notation encoding
open Lean PrettyPrinter in
@[app_unexpander HasType]
def HasType.unexpand : Unexpander := StlcCommon.Delab.unexpandHasType
We deliberately exclude HasType.sub from the list of constructors with the
StlcSubTyping. apply_rules using StlcSubTyping will search for derivations
without using the subtyping rule; if you want to make use of it in a derivation you will
need to do so yourself.
8.3. Properties
We want the same properties as always: progress + preservation.
-
Statements of these theorems don't need to change, compared to pure STLC
-
But proofs are a bit more involved, to account for the additional flexibility in the typing relation
8.3.1. Inversion Lemmas for Subtyping
Before we look at the properties of the typing relation, we need to establish a couple of critical structural properties of the subtype relation:
-
Boolis the only subtype ofBool, and -
every subtype of an arrow type is itself an arrow type.
Formally:
8.3.2. Canonical Forms
The proof of progress uses facts of the form "every value belonging to an arrow type is an abstraction."
In the pure STLC, such facts are "immediate from the
definition" (formally, they follow directly by inversion).
With subtyping, they require real proofs by induction...
theorem canonical_forms_of_arrow_types {Γ : Context} {t : Tm} {τ₁ τ₂ : Ty}
(ht : <{ Γ ⊢ t ⦂ τ₁ → τ₂ }>)
(hv : t.IsValue) :
∃ x σ₁ t₂, t = <{λ x : σ₁ . t₂}> := Γ:Contextt:Tmτ₁:Tyτ₂:Tyht:<{ Γ ⊢ t ⦂ τ₁ → τ₂ }>hv:t.IsValue⊢ ∃ x σ₁ t₂, t = <{ λ ~x : σ₁ . t₂ }>
All goals completed! 🐙
Similarly, the canonical forms of type Bool are the constants
tru and fls
theorem canonical_forms_of_bool {Γ : Context} {t : Tm}
(ht : <{ Γ ⊢ t ⦂ Bool }>)
(hv : t.IsValue) :
t = Tm.tru ∨ t = Tm.fls := Γ:Contextt:Tmht:<{ Γ ⊢ t ⦂ Bool }>hv:t.IsValue⊢ t = <{ true }> ∨ t = <{ false }>
Γ:Contextt:Tmhv:t.IsValueτ:Tyheq:<{ Bool }> = τht:<{ Γ ⊢ t ⦂ τ }>⊢ t = <{ true }> ∨ t = <{ false }>
induction ht with (Γ:Contextt:Tmτ:TyΓ✝:Contextt✝:Tmτ₁✝:Tyhv:<{ snd t✝ }>.IsValueh✝:<{ Γ✝ ⊢ t✝ ⦂ τ₁✝ × Bool }>h_ih✝:t✝.IsValue → <{ Bool }> = <{ τ₁✝ × Bool }> → t✝ = <{ true }> ∨ t✝ = <{ false }>⊢ <{ snd t✝ }> = <{ true }> ∨ <{ snd t✝ }> = <{ false }>; first | All goals completed! 🐙 | try All goals completed! 🐙)
Γ✝:Contextt:Tmτ:TyΓ:Contextt₁:Tmτ₁:Tyht:<{ Γ ⊢ t₁ ⦂ τ₁ }>ih:t₁.IsValue → <{ Bool }> = τ₁ → t₁ = <{ true }> ∨ t₁ = <{ false }>hv:t₁.IsValuehs:τ₁ <: <{ Bool }>⊢ t₁ = <{ true }> ∨ t₁ = <{ false }>
Γ✝:Contextt:Tmτ:TyΓ:Contextt₁:Tmτ₁:Tyht:<{ Γ ⊢ t₁ ⦂ τ₁ }>ih:t₁.IsValue → <{ Bool }> = τ₁ → t₁ = <{ true }> ∨ t₁ = <{ false }>hv:t₁.IsValuehs:τ₁ = <{ Bool }>⊢ t₁ = <{ true }> ∨ t₁ = <{ false }>; Γ✝:Contextt:Tmτ:TyΓ:Contextt₁:Tmhv:t₁.IsValueht:<{ Γ ⊢ t₁ ⦂ Bool }>ih:t₁.IsValue → <{ Bool }> = <{ Bool }> → t₁ = <{ true }> ∨ t₁ = <{ false }>⊢ t₁ = <{ true }> ∨ t₁ = <{ false }>
All goals completed! 🐙
8.3.3. Progress
Formally:
theorem progress (t : Tm) (τ : Ty) (h : <{ ∅ ⊢ t ⦂ τ }>) :
t.IsValue ∨ ∃ t', t ⟶ t' := t:Tmτ:Tyh:<{ ∅ ⊢ t ⦂ τ }>⊢ t.IsValue ∨ ∃ t', t ⟶ t'
t:Tmτ:TyΓ:Contextheq:∅ = Γh:<{ Γ ⊢ t ⦂ τ }>⊢ t.IsValue ∨ ∃ t', t ⟶ t'
induction h with (t:Tmτ:TyΓ:Contextt✝:Tmτ₁✝:Tyτ₂✝:Tyh✝:<{ ∅ ⊢ t✝ ⦂ τ₁✝ × τ₂✝ }>h_ih✝:∅ = ∅ → t✝.IsValue ∨ ∃ t', t✝ ⟶ t'⊢ <{ snd t✝ }>.IsValue ∨ ∃ t', <{ snd t✝ }> ⟶ t'; first
| t:Tmτ:TyΓ:Contextt✝:Tmτ₁✝:Tyτ₂✝:Tyh✝:<{ ∅ ⊢ t✝ ⦂ τ₁✝ × τ₂✝ }>h_ih✝:∅ = ∅ → t✝.IsValue ∨ ∃ t', t✝ ⟶ t'⊢ <{ snd t✝ }>.IsValue ∨ ∃ t', <{ snd t✝ }> ⟶ t'
-- discharge cases where `t` is obviously a value
| try (t:Tmτ:TyΓ:Contextt✝:Tmτ₁✝:Tyτ₂✝:Tyh✝:<{ ∅ ⊢ t✝ ⦂ τ₁✝ × τ₂✝ }>h_ih✝:∅ = ∅ → t✝.IsValue ∨ ∃ t', t✝ ⟶ t'⊢ <{ snd t✝ }>.IsValue; t:Tmτ:TyΓ:Contextt✝:Tmτ₁✝:Tyτ₂✝:Tyh✝:<{ ∅ ⊢ t✝ ⦂ τ₁✝ × τ₂✝ }>h_ih✝:∅ = ∅ → t✝.IsValue ∨ ∃ t', t✝ ⟶ t'⊢ <{ snd t✝ }>.IsValue; All goals completed! 🐙)
)
t:Tmτ:TyΓ:Contextτ₁:Tyτ₂:Tyt₁:Tmt₂:Tmh₁:<{ ∅ ⊢ t₁ ⦂ τ₂ → τ₁ }>h₂:<{ ∅ ⊢ t₂ ⦂ τ₂ }>ih₁:∅ = ∅ → t₁.IsValue ∨ ∃ t', t₁ ⟶ t'ih₂:∅ = ∅ → t₂.IsValue ∨ ∃ t', t₂ ⟶ t'⊢ <{ t₁ t₂ }>.IsValue ∨ ∃ t', <{ t₁ t₂ }> ⟶ t'
t:Tmτ:TyΓ:Contextτ₁:Tyτ₂:Tyt₁:Tmt₂:Tmh₁:<{ ∅ ⊢ t₁ ⦂ τ₂ → τ₁ }>h₂:<{ ∅ ⊢ t₂ ⦂ τ₂ }>ih₁:∅ = ∅ → t₁.IsValue ∨ ∃ t', t₁ ⟶ t'ih₂:∅ = ∅ → t₂.IsValue ∨ ∃ t', t₂ ⟶ t'⊢ ∃ t', <{ t₁ t₂ }> ⟶ t'; cases ih₁ rfl with
-- t₁ is a value
t:Tmτ:TyΓ:Contextτ₁:Tyτ₂:Tyt₁:Tmt₂:Tmh₁:<{ ∅ ⊢ t₁ ⦂ τ₂ → τ₁ }>h₂:<{ ∅ ⊢ t₂ ⦂ τ₂ }>ih₁:∅ = ∅ → t₁.IsValue ∨ ∃ t', t₁ ⟶ t'ih₂:∅ = ∅ → t₂.IsValue ∨ ∃ t', t₂ ⟶ t'ht₁:t₁.IsValue⊢ ∃ t', <{ t₁ t₂ }> ⟶ t'
cases ih₂ rfl with
-- t₂ is a value
t:Tmτ:TyΓ:Contextτ₁:Tyτ₂:Tyt₁:Tmt₂:Tmh₁:<{ ∅ ⊢ t₁ ⦂ τ₂ → τ₁ }>h₂:<{ ∅ ⊢ t₂ ⦂ τ₂ }>ih₁:∅ = ∅ → t₁.IsValue ∨ ∃ t', t₁ ⟶ t'ih₂:∅ = ∅ → t₂.IsValue ∨ ∃ t', t₂ ⟶ t'ht₁:t₁.IsValueht₂:t₂.IsValue⊢ ∃ t', <{ t₁ t₂ }> ⟶ t'
t:Tmτ:TyΓ:Contextτ₁:Tyτ₂:Tyt₁:Tmt₂:Tmh₂:<{ ∅ ⊢ t₂ ⦂ τ₂ }>ih₁:∅ = ∅ → t₁.IsValue ∨ ∃ t', t₁ ⟶ t'ih₂:∅ = ∅ → t₂.IsValue ∨ ∃ t', t₂ ⟶ t'ht₁:t₁.IsValueht₂:t₂.IsValueh₁:t₁.IsValue → ∃ x σ₁ t₂, t₁ = <{ λ ~x : σ₁ . t₂ }>⊢ ∃ t', <{ t₁ t₂ }> ⟶ t'
t:Tmτ:TyΓ:Contextτ₁:Tyτ₂:Tyt₁:Tmt₂:Tmh₂:<{ ∅ ⊢ t₂ ⦂ τ₂ }>ih₁:∅ = ∅ → t₁.IsValue ∨ ∃ t', t₁ ⟶ t'ih₂:∅ = ∅ → t₂.IsValue ∨ ∃ t', t₂ ⟶ t'ht₁:t₁.IsValueht₂:t₂.IsValueh₁:t₁.IsValue → ∃ x σ₁ t₂, t₁ = <{ λ ~x : σ₁ . t₂ }>x:Stringσ:Tyv:Tmhv:t₁ = <{ λ ~x : σ . v }>⊢ ∃ t', <{ t₁ t₂ }> ⟶ t'
t:Tmτ:TyΓ:Contextτ₁:Tyτ₂:Tyt₁:Tmt₂:Tmh₂:<{ ∅ ⊢ t₂ ⦂ τ₂ }>ih₁:∅ = ∅ → t₁.IsValue ∨ ∃ t', t₁ ⟶ t'ih₂:∅ = ∅ → t₂.IsValue ∨ ∃ t', t₂ ⟶ t'ht₁:t₁.IsValueht₂:t₂.IsValueh₁:t₁.IsValue → ∃ x σ₁ t₂, t₁ = <{ λ ~x : σ₁ . t₂ }>x:Stringσ:Tyv:Tmhv:t₁ = <{ λ ~x : σ . v }>⊢ <{ t₁ t₂ }> ⟶ <{ [~x := t₂] v }>; t:Tmτ:TyΓ:Contextτ₁:Tyτ₂:Tyt₁:Tmt₂:Tmh₂:<{ ∅ ⊢ t₂ ⦂ τ₂ }>ih₁:∅ = ∅ → t₁.IsValue ∨ ∃ t', t₁ ⟶ t'ih₂:∅ = ∅ → t₂.IsValue ∨ ∃ t', t₂ ⟶ t'ht₁:t₁.IsValueht₂:t₂.IsValueh₁:t₁.IsValue → ∃ x σ₁ t₂, t₁ = <{ λ ~x : σ₁ . t₂ }>x:Stringσ:Tyv:Tmhv:t₁ = <{ λ ~x : σ . v }>⊢ <{ (λ ~x : σ . v) t₂ }> ⟶ <{ [~x := t₂] v }>
All goals completed! 🐙
-- t₂ is not a value
t:Tmτ:TyΓ:Contextτ₁:Tyτ₂:Tyt₁:Tmt₂:Tmh₁:<{ ∅ ⊢ t₁ ⦂ τ₂ → τ₁ }>h₂:<{ ∅ ⊢ t₂ ⦂ τ₂ }>ih₁:∅ = ∅ → t₁.IsValue ∨ ∃ t', t₁ ⟶ t'ih₂:∅ = ∅ → t₂.IsValue ∨ ∃ t', t₂ ⟶ t'ht₁:t₁.IsValueht₂:∃ t', t₂ ⟶ t'⊢ ∃ t', <{ t₁ t₂ }> ⟶ t'
t:Tmτ:TyΓ:Contextτ₁:Tyτ₂:Tyt₁:Tmt₂:Tmh₁:<{ ∅ ⊢ t₁ ⦂ τ₂ → τ₁ }>h₂:<{ ∅ ⊢ t₂ ⦂ τ₂ }>ih₁:∅ = ∅ → t₁.IsValue ∨ ∃ t', t₁ ⟶ t'ih₂:∅ = ∅ → t₂.IsValue ∨ ∃ t', t₂ ⟶ t'ht₁:t₁.IsValuet₂':Tmht₂:t₂ ⟶ t₂'⊢ ∃ t', <{ t₁ t₂ }> ⟶ t'
t:Tmτ:TyΓ:Contextτ₁:Tyτ₂:Tyt₁:Tmt₂:Tmh₁:<{ ∅ ⊢ t₁ ⦂ τ₂ → τ₁ }>h₂:<{ ∅ ⊢ t₂ ⦂ τ₂ }>ih₁:∅ = ∅ → t₁.IsValue ∨ ∃ t', t₁ ⟶ t'ih₂:∅ = ∅ → t₂.IsValue ∨ ∃ t', t₂ ⟶ t'ht₁:t₁.IsValuet₂':Tmht₂:t₂ ⟶ t₂'⊢ <{ t₁ t₂ }> ⟶ <{ t₁ t₂' }>; All goals completed! 🐙
-- t₁ is not a value
t:Tmτ:TyΓ:Contextτ₁:Tyτ₂:Tyt₁:Tmt₂:Tmh₁:<{ ∅ ⊢ t₁ ⦂ τ₂ → τ₁ }>h₂:<{ ∅ ⊢ t₂ ⦂ τ₂ }>ih₁:∅ = ∅ → t₁.IsValue ∨ ∃ t', t₁ ⟶ t'ih₂:∅ = ∅ → t₂.IsValue ∨ ∃ t', t₂ ⟶ t'ht₁:∃ t', t₁ ⟶ t'⊢ ∃ t', <{ t₁ t₂ }> ⟶ t'
t:Tmτ:TyΓ:Contextτ₁:Tyτ₂:Tyt₁:Tmt₂:Tmh₁:<{ ∅ ⊢ t₁ ⦂ τ₂ → τ₁ }>h₂:<{ ∅ ⊢ t₂ ⦂ τ₂ }>ih₁:∅ = ∅ → t₁.IsValue ∨ ∃ t', t₁ ⟶ t'ih₂:∅ = ∅ → t₂.IsValue ∨ ∃ t', t₂ ⟶ t't₁':Tmht₁:t₁ ⟶ t₁'⊢ ∃ t', <{ t₁ t₂ }> ⟶ t'
t:Tmτ:TyΓ:Contextτ₁:Tyτ₂:Tyt₁:Tmt₂:Tmh₁:<{ ∅ ⊢ t₁ ⦂ τ₂ → τ₁ }>h₂:<{ ∅ ⊢ t₂ ⦂ τ₂ }>ih₁:∅ = ∅ → t₁.IsValue ∨ ∃ t', t₁ ⟶ t'ih₂:∅ = ∅ → t₂.IsValue ∨ ∃ t', t₂ ⟶ t't₁':Tmht₁:t₁ ⟶ t₁'⊢ <{ t₁ t₂ }> ⟶ <{ t₁' t₂ }>; All goals completed! 🐙
t:Tmτ✝:TyΓ:Contextt₁:Tmt₂:Tmt₃:Tmτ:Tyh₁:<{ ∅ ⊢ t₁ ⦂ Bool }>h₂:<{ ∅ ⊢ t₂ ⦂ τ }>h₃:<{ ∅ ⊢ t₃ ⦂ τ }>ih₁:∅ = ∅ → t₁.IsValue ∨ ∃ t', t₁ ⟶ t'ih₂:∅ = ∅ → t₂.IsValue ∨ ∃ t', t₂ ⟶ t'ih₃:∅ = ∅ → t₃.IsValue ∨ ∃ t', t₃ ⟶ t'⊢ <{ if t₁ then t₂ else t₃ }>.IsValue ∨ ∃ t', <{ if t₁ then t₂ else t₃ }> ⟶ t'
t:Tmτ✝:TyΓ:Contextt₁:Tmt₂:Tmt₃:Tmτ:Tyh₁:<{ ∅ ⊢ t₁ ⦂ Bool }>h₂:<{ ∅ ⊢ t₂ ⦂ τ }>h₃:<{ ∅ ⊢ t₃ ⦂ τ }>ih₁:∅ = ∅ → t₁.IsValue ∨ ∃ t', t₁ ⟶ t'ih₂:∅ = ∅ → t₂.IsValue ∨ ∃ t', t₂ ⟶ t'ih₃:∅ = ∅ → t₃.IsValue ∨ ∃ t', t₃ ⟶ t'⊢ ∃ t', <{ if t₁ then t₂ else t₃ }> ⟶ t'; cases ih₁ rfl with
-- t₁ is a value
t:Tmτ✝:TyΓ:Contextt₁:Tmt₂:Tmt₃:Tmτ:Tyh₁:<{ ∅ ⊢ t₁ ⦂ Bool }>h₂:<{ ∅ ⊢ t₂ ⦂ τ }>h₃:<{ ∅ ⊢ t₃ ⦂ τ }>ih₁:∅ = ∅ → t₁.IsValue ∨ ∃ t', t₁ ⟶ t'ih₂:∅ = ∅ → t₂.IsValue ∨ ∃ t', t₂ ⟶ t'ih₃:∅ = ∅ → t₃.IsValue ∨ ∃ t', t₃ ⟶ t'ht₁:t₁.IsValue⊢ ∃ t', <{ if t₁ then t₂ else t₃ }> ⟶ t'
t:Tmτ✝:TyΓ:Contextt₁:Tmt₂:Tmt₃:Tmτ:Tyh₂:<{ ∅ ⊢ t₂ ⦂ τ }>h₃:<{ ∅ ⊢ t₃ ⦂ τ }>ih₁:∅ = ∅ → t₁.IsValue ∨ ∃ t', t₁ ⟶ t'ih₂:∅ = ∅ → t₂.IsValue ∨ ∃ t', t₂ ⟶ t'ih₃:∅ = ∅ → t₃.IsValue ∨ ∃ t', t₃ ⟶ t'ht₁:t₁.IsValueh₁:t₁.IsValue → t₁ = <{ true }> ∨ t₁ = <{ false }>⊢ ∃ t', <{ if t₁ then t₂ else t₃ }> ⟶ t'
t:Tmτ✝:TyΓ:Contextt₁:Tmt₂:Tmt₃:Tmτ:Tyh₂:<{ ∅ ⊢ t₂ ⦂ τ }>h₃:<{ ∅ ⊢ t₃ ⦂ τ }>ih₁:∅ = ∅ → t₁.IsValue ∨ ∃ t', t₁ ⟶ t'ih₂:∅ = ∅ → t₂.IsValue ∨ ∃ t', t₂ ⟶ t'ih₃:∅ = ∅ → t₃.IsValue ∨ ∃ t', t₃ ⟶ t'ht₁:t₁.IsValueh₁✝:t₁.IsValue → t₁ = <{ true }> ∨ t₁ = <{ false }>h₁:t₁ = <{ true }>⊢ ∃ t', <{ if t₁ then t₂ else t₃ }> ⟶ t't:Tmτ✝:TyΓ:Contextt₁:Tmt₂:Tmt₃:Tmτ:Tyh₂:<{ ∅ ⊢ t₂ ⦂ τ }>h₃:<{ ∅ ⊢ t₃ ⦂ τ }>ih₁:∅ = ∅ → t₁.IsValue ∨ ∃ t', t₁ ⟶ t'ih₂:∅ = ∅ → t₂.IsValue ∨ ∃ t', t₂ ⟶ t'ih₃:∅ = ∅ → t₃.IsValue ∨ ∃ t', t₃ ⟶ t'ht₁:t₁.IsValueh₁✝:t₁.IsValue → t₁ = <{ true }> ∨ t₁ = <{ false }>h₁:t₁ = <{ false }>⊢ ∃ t', <{ if t₁ then t₂ else t₃ }> ⟶ t' t:Tmτ✝:TyΓ:Contextt₁:Tmt₂:Tmt₃:Tmτ:Tyh₂:<{ ∅ ⊢ t₂ ⦂ τ }>h₃:<{ ∅ ⊢ t₃ ⦂ τ }>ih₁:∅ = ∅ → t₁.IsValue ∨ ∃ t', t₁ ⟶ t'ih₂:∅ = ∅ → t₂.IsValue ∨ ∃ t', t₂ ⟶ t'ih₃:∅ = ∅ → t₃.IsValue ∨ ∃ t', t₃ ⟶ t'ht₁:t₁.IsValueh₁✝:t₁.IsValue → t₁ = <{ true }> ∨ t₁ = <{ false }>h₁:t₁ = <{ true }>⊢ ∃ t', <{ if t₁ then t₂ else t₃ }> ⟶ t't:Tmτ✝:TyΓ:Contextt₁:Tmt₂:Tmt₃:Tmτ:Tyh₂:<{ ∅ ⊢ t₂ ⦂ τ }>h₃:<{ ∅ ⊢ t₃ ⦂ τ }>ih₁:∅ = ∅ → t₁.IsValue ∨ ∃ t', t₁ ⟶ t'ih₂:∅ = ∅ → t₂.IsValue ∨ ∃ t', t₂ ⟶ t'ih₃:∅ = ∅ → t₃.IsValue ∨ ∃ t', t₃ ⟶ t'ht₁:t₁.IsValueh₁✝:t₁.IsValue → t₁ = <{ true }> ∨ t₁ = <{ false }>h₁:t₁ = <{ false }>⊢ ∃ t', <{ if t₁ then t₂ else t₃ }> ⟶ t' t:Tmτ✝:TyΓ:Contextt₂:Tmt₃:Tmτ:Tyh₂:<{ ∅ ⊢ t₂ ⦂ τ }>h₃:<{ ∅ ⊢ t₃ ⦂ τ }>ih₂:∅ = ∅ → t₂.IsValue ∨ ∃ t', t₂ ⟶ t'ih₃:∅ = ∅ → t₃.IsValue ∨ ∃ t', t₃ ⟶ t'ih₁:∅ = ∅ → <{ false }>.IsValue ∨ ∃ t', <{ false }> ⟶ t'ht₁:<{ false }>.IsValueh₁:<{ false }>.IsValue → <{ false }> = <{ true }> ∨ <{ false }> = <{ false }>⊢ ∃ t', <{ if false then t₂ else t₃ }> ⟶ t'
t:Tmτ✝:TyΓ:Contextt₂:Tmt₃:Tmτ:Tyh₂:<{ ∅ ⊢ t₂ ⦂ τ }>h₃:<{ ∅ ⊢ t₃ ⦂ τ }>ih₂:∅ = ∅ → t₂.IsValue ∨ ∃ t', t₂ ⟶ t'ih₃:∅ = ∅ → t₃.IsValue ∨ ∃ t', t₃ ⟶ t'ih₁:∅ = ∅ → <{ true }>.IsValue ∨ ∃ t', <{ true }> ⟶ t'ht₁:<{ true }>.IsValueh₁:<{ true }>.IsValue → <{ true }> = <{ true }> ∨ <{ true }> = <{ false }>⊢ ∃ t', <{ if true then t₂ else t₃ }> ⟶ t' t:Tmτ✝:TyΓ:Contextt₂:Tmt₃:Tmτ:Tyh₂:<{ ∅ ⊢ t₂ ⦂ τ }>h₃:<{ ∅ ⊢ t₃ ⦂ τ }>ih₂:∅ = ∅ → t₂.IsValue ∨ ∃ t', t₂ ⟶ t'ih₃:∅ = ∅ → t₃.IsValue ∨ ∃ t', t₃ ⟶ t'ih₁:∅ = ∅ → <{ true }>.IsValue ∨ ∃ t', <{ true }> ⟶ t'ht₁:<{ true }>.IsValueh₁:<{ true }>.IsValue → <{ true }> = <{ true }> ∨ <{ true }> = <{ false }>⊢ <{ if true then t₂ else t₃ }> ⟶ t₂; All goals completed! 🐙
t:Tmτ✝:TyΓ:Contextt₂:Tmt₃:Tmτ:Tyh₂:<{ ∅ ⊢ t₂ ⦂ τ }>h₃:<{ ∅ ⊢ t₃ ⦂ τ }>ih₂:∅ = ∅ → t₂.IsValue ∨ ∃ t', t₂ ⟶ t'ih₃:∅ = ∅ → t₃.IsValue ∨ ∃ t', t₃ ⟶ t'ih₁:∅ = ∅ → <{ false }>.IsValue ∨ ∃ t', <{ false }> ⟶ t'ht₁:<{ false }>.IsValueh₁:<{ false }>.IsValue → <{ false }> = <{ true }> ∨ <{ false }> = <{ false }>⊢ ∃ t', <{ if false then t₂ else t₃ }> ⟶ t' t:Tmτ✝:TyΓ:Contextt₂:Tmt₃:Tmτ:Tyh₂:<{ ∅ ⊢ t₂ ⦂ τ }>h₃:<{ ∅ ⊢ t₃ ⦂ τ }>ih₂:∅ = ∅ → t₂.IsValue ∨ ∃ t', t₂ ⟶ t'ih₃:∅ = ∅ → t₃.IsValue ∨ ∃ t', t₃ ⟶ t'ih₁:∅ = ∅ → <{ false }>.IsValue ∨ ∃ t', <{ false }> ⟶ t'ht₁:<{ false }>.IsValueh₁:<{ false }>.IsValue → <{ false }> = <{ true }> ∨ <{ false }> = <{ false }>⊢ <{ if false then t₂ else t₃ }> ⟶ t₃; All goals completed! 🐙
-- t₁ is not a value
t:Tmτ✝:TyΓ:Contextt₁:Tmt₂:Tmt₃:Tmτ:Tyh₁:<{ ∅ ⊢ t₁ ⦂ Bool }>h₂:<{ ∅ ⊢ t₂ ⦂ τ }>h₃:<{ ∅ ⊢ t₃ ⦂ τ }>ih₁:∅ = ∅ → t₁.IsValue ∨ ∃ t', t₁ ⟶ t'ih₂:∅ = ∅ → t₂.IsValue ∨ ∃ t', t₂ ⟶ t'ih₃:∅ = ∅ → t₃.IsValue ∨ ∃ t', t₃ ⟶ t'ht₁:∃ t', t₁ ⟶ t'⊢ ∃ t', <{ if t₁ then t₂ else t₃ }> ⟶ t'
t:Tmτ✝:TyΓ:Contextt₁:Tmt₂:Tmt₃:Tmτ:Tyh₁:<{ ∅ ⊢ t₁ ⦂ Bool }>h₂:<{ ∅ ⊢ t₂ ⦂ τ }>h₃:<{ ∅ ⊢ t₃ ⦂ τ }>ih₁:∅ = ∅ → t₁.IsValue ∨ ∃ t', t₁ ⟶ t'ih₂:∅ = ∅ → t₂.IsValue ∨ ∃ t', t₂ ⟶ t'ih₃:∅ = ∅ → t₃.IsValue ∨ ∃ t', t₃ ⟶ t't₁':Tmht₁:t₁ ⟶ t₁'⊢ ∃ t', <{ if t₁ then t₂ else t₃ }> ⟶ t'
t:Tmτ✝:TyΓ:Contextt₁:Tmt₂:Tmt₃:Tmτ:Tyh₁:<{ ∅ ⊢ t₁ ⦂ Bool }>h₂:<{ ∅ ⊢ t₂ ⦂ τ }>h₃:<{ ∅ ⊢ t₃ ⦂ τ }>ih₁:∅ = ∅ → t₁.IsValue ∨ ∃ t', t₁ ⟶ t'ih₂:∅ = ∅ → t₂.IsValue ∨ ∃ t', t₂ ⟶ t'ih₃:∅ = ∅ → t₃.IsValue ∨ ∃ t', t₃ ⟶ t't₁':Tmht₁:t₁ ⟶ t₁'⊢ <{ if t₁ then t₂ else t₃ }> ⟶ <{ if t₁' then t₂ else t₃ }>; All goals completed! 🐙
t:Tmτ:TyΓ:Contextt₁:Tmτ₁:Tyτ₂:Tyhs:τ₁ <: τ₂ht:<{ ∅ ⊢ t₁ ⦂ τ₁ }>ih:∅ = ∅ → t₁.IsValue ∨ ∃ t', t₁ ⟶ t'⊢ t₁.IsValue ∨ ∃ t', t₁ ⟶ t' t:Tmτ:TyΓ:Contextt₁:Tmτ₁:Tyτ₂:Tyhs:τ₁ <: τ₂ht:<{ ∅ ⊢ t₁ ⦂ τ₁ }>ih:∅ = ∅ → t₁.IsValue ∨ ∃ t', t₁ ⟶ t'⊢ ∅ = ∅; All goals completed! 🐙
-- Fill in products here later
-- FILL IN HERE
8.3.4. Inversion Lemmas for Typing
We also need to prove an inversion lemma corresponding to a structural fact about the typing relation that is "obvious from the definition" in pure STLC.
Lemma: If Γ ⊢ λ x : σ₁ . t₂ ⦂ τ, then there is a type σ₂
such that x ↦ σ₁ ; Γ ⊢ t₂ ⦂ σ₂ and σ₁ → σ₂ <: τ.
Proof: Let Γ, x, σ₁, t₂ and τ be given as
described. Proceed by induction on the derivation of Γ ⊢ λ x : σ₁ . t₂ ⦂ τ.
The cases for var and app are vacuous
as those rules cannot be used to give a type to a syntactic
abstraction.
-
If the last step of the derivation is a use of
absthen there is a typeτ₁₂such thatτ = σ₁ → τ₁₂andx ↦ σ₁; Γ ⊢ t₂ ⦂ τ₁₂. Pickingτ₁₂forσ₂gives us what we need, sinceσ₁ → τ₁₂ <: σ₁ → τ₁₂follows fromrfl. -
If the last step of the derivation is a use of
subthen there is a typeσsuch thatσ <: τandΓ ⊢ λx : σ₁, t₂ ⦂ σ. The IH for the typing subderivation tells us that there is some typeσ₂withσ₁ → σ₂ <: σandx↦σ₁; Γ ⊢ t₂ ⦂ σ₂. Picking typeσ₂gives us what we need, sinceσ₁ → σ₂ <: τthen follows bytrans.
Formally:
theorem typing_inversion_abs {Γ : Context} {x : String} {σ₁ : Ty} {t₂ : Tm} {τ : Ty}
(h : <{ Γ ⊢ λ x : σ₁ . t₂ ⦂ τ }>) :
∃ σ₂, <{ σ₁ → σ₂ }> <: τ ∧ <{ x ↦ σ₁ ; Γ ⊢ t₂ ⦂ σ₂ }> := Γ:Contextx:Stringσ₁:Tyt₂:Tmτ:Tyh:<{ Γ ⊢ λ ~x : σ₁ . t₂ ⦂ τ }>⊢ ∃ σ₂, <{ σ₁ → σ₂ }> <: τ ∧ <{ ~(x →ₚ σ₁ ; Γ) ⊢ t₂ ⦂ σ₂ }>
Γ:Contextx:Stringσ₁:Tyt₂:Tmτ:Tyt:Tmheq:<{ λ ~x : σ₁ . t₂ }> = th:<{ Γ ⊢ t ⦂ τ }>⊢ ∃ σ₂, <{ σ₁ → σ₂ }> <: τ ∧ <{ ~(x →ₚ σ₁ ; Γ) ⊢ t₂ ⦂ σ₂ }>
induction h with (Γ:Contextx:Stringσ₁:Tyt₂:Tmτ:Tyt:TmΓ✝:Contextt✝:Tmτ₁✝:Tyτ₂✝:Tyh✝:<{ Γ✝ ⊢ t✝ ⦂ τ₁✝ × τ₂✝ }>h_ih✝:<{ λ ~x : σ₁ . t₂ }> = t✝ → ∃ σ₂, <{ σ₁ → σ₂ }> <: <{ τ₁✝ × τ₂✝ }> ∧ <{ ~(x →ₚ σ₁ ; Γ✝) ⊢ t₂ ⦂ σ₂ }>heq:<{ λ ~x : σ₁ . t₂ }> = <{ snd t✝ }>⊢ ∃ σ₂, <{ σ₁ → σ₂ }> <: τ₂✝ ∧ <{ ~(x →ₚ σ₁ ; Γ✝) ⊢ t₂ ⦂ σ₂ }>; try All goals completed! 🐙)
Γ✝:Contextx✝:Stringσ₁:Tyt₂:Tmτ:Tyt:TmΓ:Contextx:Stringτ₁:Tyτ₂:Tyt₁:Tmh:<{ ~(x →ₚ τ₂ ; Γ) ⊢ t₁ ⦂ τ₁ }>i:<{ λ ~x✝ : σ₁ . t₂ }> = t₁ → ∃ σ₂, <{ σ₁ → σ₂ }> <: τ₁ ∧ <{ ~(x✝ →ₚ σ₁ ; x →ₚ τ₂ ; Γ) ⊢ t₂ ⦂ σ₂ }>heq:<{ λ ~x✝ : σ₁ . t₂ }> = <{ λ ~x : τ₂ . t₁ }>⊢ ∃ σ₂, <{ σ₁ → σ₂ }> <: <{ τ₂ → τ₁ }> ∧ <{ ~(x✝ →ₚ σ₁ ; Γ) ⊢ t₂ ⦂ σ₂ }>
Γ✝:Contextx:Stringσ₁:Tyt₂:Tmτ:Tyt:TmΓ:Contextτ₁:Tyh:<{ ~(x →ₚ σ₁ ; Γ) ⊢ t₂ ⦂ τ₁ }>i:<{ λ ~x : σ₁ . t₂ }> = t₂ → ∃ σ₂, <{ σ₁ → σ₂ }> <: τ₁ ∧ <{ ~(x →ₚ σ₁ ; x →ₚ σ₁ ; Γ) ⊢ t₂ ⦂ σ₂ }>⊢ ∃ σ₂, <{ σ₁ → σ₂ }> <: <{ σ₁ → τ₁ }> ∧ <{ ~(x →ₚ σ₁ ; Γ) ⊢ t₂ ⦂ σ₂ }>; Γ✝:Contextx:Stringσ₁:Tyt₂:Tmτ:Tyt:TmΓ:Contextτ₁:Tyh:<{ ~(x →ₚ σ₁ ; Γ) ⊢ t₂ ⦂ τ₁ }>i:<{ λ ~x : σ₁ . t₂ }> = t₂ → ∃ σ₂, <{ σ₁ → σ₂ }> <: τ₁ ∧ <{ ~(x →ₚ σ₁ ; x →ₚ σ₁ ; Γ) ⊢ t₂ ⦂ σ₂ }>⊢ <{ σ₁ → τ₁ }> <: <{ σ₁ → τ₁ }> ∧ <{ ~(x →ₚ σ₁ ; Γ) ⊢ t₂ ⦂ τ₁ }>; All goals completed! 🐙
Γ✝:Contextx:Stringσ₁:Tyt₂:Tmτ:Tyt:TmΓ:Contextτ₁:Tyτ₂:Tyhs:τ₁ <: τ₂ht:<{ Γ ⊢ λ ~x : σ₁ . t₂ ⦂ τ₁ }>ih:<{ λ ~x : σ₁ . t₂ }> = <{ λ ~x : σ₁ . t₂ }> → ∃ σ₂, <{ σ₁ → σ₂ }> <: τ₁ ∧ <{ ~(x →ₚ σ₁ ; Γ) ⊢ t₂ ⦂ σ₂ }>⊢ ∃ σ₂, <{ σ₁ → σ₂ }> <: τ₂ ∧ <{ ~(x →ₚ σ₁ ; Γ) ⊢ t₂ ⦂ σ₂ }>
Γ✝:Contextx:Stringσ₁:Tyt₂:Tmτ:Tyt:TmΓ:Contextτ₁:Tyτ₂:Tyhs:τ₁ <: τ₂ht:<{ Γ ⊢ λ ~x : σ₁ . t₂ ⦂ τ₁ }>ih:<{ λ ~x : σ₁ . t₂ }> = <{ λ ~x : σ₁ . t₂ }> → ∃ σ₂, <{ σ₁ → σ₂ }> <: τ₁ ∧ <{ ~(x →ₚ σ₁ ; Γ) ⊢ t₂ ⦂ σ₂ }>σ₂:Tyhs':<{ σ₁ → σ₂ }> <: τ₁ht':<{ ~(x →ₚ σ₁ ; Γ) ⊢ t₂ ⦂ σ₂ }>⊢ ∃ σ₂, <{ σ₁ → σ₂ }> <: τ₂ ∧ <{ ~(x →ₚ σ₁ ; Γ) ⊢ t₂ ⦂ σ₂ }>
Γ✝:Contextx:Stringσ₁:Tyt₂:Tmτ:Tyt:TmΓ:Contextτ₁:Tyτ₂:Tyhs:τ₁ <: τ₂ht:<{ Γ ⊢ λ ~x : σ₁ . t₂ ⦂ τ₁ }>ih:<{ λ ~x : σ₁ . t₂ }> = <{ λ ~x : σ₁ . t₂ }> → ∃ σ₂, <{ σ₁ → σ₂ }> <: τ₁ ∧ <{ ~(x →ₚ σ₁ ; Γ) ⊢ t₂ ⦂ σ₂ }>σ₂:Tyhs':<{ σ₁ → σ₂ }> <: τ₁ht':<{ ~(x →ₚ σ₁ ; Γ) ⊢ t₂ ⦂ σ₂ }>⊢ <{ σ₁ → σ₂ }> <: τ₂ ∧ <{ ~(x →ₚ σ₁ ; Γ) ⊢ t₂ ⦂ σ₂ }>; All goals completed! 🐙
Similarly:
theorem typing_inversion_unit (Γ : Context) (τ : Ty)
(h : <{ Γ ⊢ unit ⦂ τ }>) :
<{ Unit }> <: τ := Γ:Contextτ:Tyh:<{ Γ ⊢ unit ⦂ τ }>⊢ <{ Unit }> <: τ
Γ:Contextτ:Tyt:Tmheq:<{ unit }> = th:<{ Γ ⊢ t ⦂ τ }>⊢ <{ Unit }> <: τ
induction h with (Γ:Contextτ:Tyt:TmΓ✝:Contextt✝:Tmτ₁✝:Tyτ₂✝:Tyh✝:<{ Γ✝ ⊢ t✝ ⦂ τ₁✝ × τ₂✝ }>h_ih✝:<{ unit }> = t✝ → <{ Unit }> <: <{ τ₁✝ × τ₂✝ }>heq:<{ unit }> = <{ snd t✝ }>⊢ <{ Unit }> <: τ₂✝; try All goals completed! 🐙)
Γ:Contextτ:Tyt:TmΓ✝:Contextheq:<{ unit }> = <{ unit }>⊢ <{ Unit }> <: <{ Unit }> Γ:Contextτ:Tyt:TmΓ✝:Context⊢ <{ Unit }> <: <{ Unit }>; All goals completed! 🐙
Γ✝:Contextτ:Tyt:TmΓ:Contextτ₁:Tyτ₂:Tyhs:τ₁ <: τ₂ht:<{ Γ ⊢ unit ⦂ τ₁ }>ih:<{ unit }> = <{ unit }> → <{ Unit }> <: τ₁⊢ <{ Unit }> <: τ₂
Γ✝:Contextτ:Tyt:TmΓ:Contextτ₁:Tyτ₂:Tyhs:τ₁ <: τ₂ht:<{ Γ ⊢ unit ⦂ τ₁ }>ih:<{ Unit }> <: τ₁⊢ <{ Unit }> <: τ₂
All goals completed! 🐙
-- Add your lemmas for products here when you get to that exercise
-- FILL IN HEREThe inversion lemmas for typing and for subtyping between arrow types can be packaged up as a useful "combination lemma" telling us exactly what we'll actually require below.
theorem abs_arrow {x : String} {t₂ : Tm} {σ₁ τ₁ τ₂ : Ty}
(h : <{ ∅ ⊢ λ x : σ₁ . t₂ ⦂ τ₁ → τ₂ }> ) :
τ₁ <: σ₁ ∧ <{ x ↦ σ₁ ; ∅ ⊢ t₂ ⦂ τ₂ }> := x:Stringt₂:Tmσ₁:Tyτ₁:Tyτ₂:Tyh:<{ ∅ ⊢ λ ~x : σ₁ . t₂ ⦂ τ₁ → τ₂ }>⊢ τ₁ <: σ₁ ∧ <{ ~(x →ₚ σ₁) ⊢ t₂ ⦂ τ₂ }>
x:Stringt₂:Tmσ₁:Tyτ₁:Tyτ₂:Tyh:<{ ∅ ⊢ λ ~x : σ₁ . t₂ ⦂ τ₁ → τ₂ }>σ₂:Tyhs:<{ σ₁ → σ₂ }> <: <{ τ₁ → τ₂ }>ht:<{ ~(x →ₚ σ₁) ⊢ t₂ ⦂ σ₂ }>⊢ τ₁ <: σ₁ ∧ <{ ~(x →ₚ σ₁) ⊢ t₂ ⦂ τ₂ }>; x:Stringt₂:Tmσ₁:Tyτ₁:Tyτ₂:Tyσ₂:Tyhs:<{ σ₁ → σ₂ }> <: <{ τ₁ → τ₂ }>ht:<{ ~(x →ₚ σ₁) ⊢ t₂ ⦂ σ₂ }>⊢ τ₁ <: σ₁ ∧ <{ ~(x →ₚ σ₁) ⊢ t₂ ⦂ τ₂ }>
x:Stringt₂:Tmσ₁:Tyτ₁:Tyτ₂:Tyσ₂:Tyhs:<{ σ₁ → σ₂ }> <: <{ τ₁ → τ₂ }>ht:<{ ~(x →ₚ σ₁) ⊢ t₂ ⦂ σ₂ }>w✝¹:Tyw✝:Tyheq:<{ σ₁ → σ₂ }> = <{ w✝¹ → w✝ }>hs₁:τ₁ <: w✝¹hs₂:w✝ <: τ₂⊢ τ₁ <: σ₁ ∧ <{ ~(x →ₚ σ₁) ⊢ t₂ ⦂ τ₂ }>; x:Stringt₂:Tmσ₁:Tyτ₁:Tyτ₂:Tyσ₂:Tyht:<{ ~(x →ₚ σ₁) ⊢ t₂ ⦂ σ₂ }>w✝¹:Tyw✝:Tyheq:<{ σ₁ → σ₂ }> = <{ w✝¹ → w✝ }>hs₁:τ₁ <: w✝¹hs₂:w✝ <: τ₂⊢ τ₁ <: σ₁ ∧ <{ ~(x →ₚ σ₁) ⊢ t₂ ⦂ τ₂ }>
x:Stringt₂:Tmσ₁:Tyτ₁:Tyτ₂:Tyσ₂:Tyht:<{ ~(x →ₚ σ₁) ⊢ t₂ ⦂ σ₂ }>hs₁:τ₁ <: σ₁hs₂:σ₂ <: τ₂⊢ τ₁ <: σ₁ ∧ <{ ~(x →ₚ σ₁) ⊢ t₂ ⦂ τ₂ }>; x:Stringt₂:Tmσ₁:Tyτ₁:Tyτ₂:Tyσ₂:Tyht:<{ ~(x →ₚ σ₁) ⊢ t₂ ⦂ σ₂ }>hs₁:τ₁ <: σ₁hs₂:σ₂ <: τ₂⊢ τ₁ <: σ₁x:Stringt₂:Tmσ₁:Tyτ₁:Tyτ₂:Tyσ₂:Tyht:<{ ~(x →ₚ σ₁) ⊢ t₂ ⦂ σ₂ }>hs₁:τ₁ <: σ₁hs₂:σ₂ <: τ₂⊢ <{ ~(x →ₚ σ₁) ⊢ t₂ ⦂ τ₂ }>
x:Stringt₂:Tmσ₁:Tyτ₁:Tyτ₂:Tyσ₂:Tyht:<{ ~(x →ₚ σ₁) ⊢ t₂ ⦂ σ₂ }>hs₁:τ₁ <: σ₁hs₂:σ₂ <: τ₂⊢ τ₁ <: σ₁ All goals completed! 🐙
x:Stringt₂:Tmσ₁:Tyτ₁:Tyτ₂:Tyσ₂:Tyht:<{ ~(x →ₚ σ₁) ⊢ t₂ ⦂ σ₂ }>hs₁:τ₁ <: σ₁hs₂:σ₂ <: τ₂⊢ <{ ~(x →ₚ σ₁) ⊢ t₂ ⦂ τ₂ }> x:Stringt₂:Tmσ₁:Tyτ₁:Tyτ₂:Tyσ₂:Tyht:<{ ~(x →ₚ σ₁) ⊢ t₂ ⦂ σ₂ }>hs₁:τ₁ <: σ₁hs₂:σ₂ <: τ₂⊢ <{ ~(x →ₚ σ₁) ⊢ t₂ ⦂ ~?refl.right.τ₁ }>x:Stringt₂:Tmσ₁:Tyτ₁:Tyτ₂:Tyσ₂:Tyht:<{ ~(x →ₚ σ₁) ⊢ t₂ ⦂ σ₂ }>hs₁:τ₁ <: σ₁hs₂:σ₂ <: τ₂⊢ ?refl.right.τ₁ <: τ₂x:Stringt₂:Tmσ₁:Tyτ₁:Tyτ₂:Tyσ₂:Tyht:<{ ~(x →ₚ σ₁) ⊢ t₂ ⦂ σ₂ }>hs₁:τ₁ <: σ₁hs₂:σ₂ <: τ₂⊢ Ty x:Stringt₂:Tmσ₁:Tyτ₁:Tyτ₂:Tyσ₂:Tyht:<{ ~(x →ₚ σ₁) ⊢ t₂ ⦂ σ₂ }>hs₁:τ₁ <: σ₁hs₂:σ₂ <: τ₂⊢ <{ ~(x →ₚ σ₁) ⊢ t₂ ⦂ ~?refl.right.τ₁ }>x:Stringt₂:Tmσ₁:Tyτ₁:Tyτ₂:Tyσ₂:Tyht:<{ ~(x →ₚ σ₁) ⊢ t₂ ⦂ σ₂ }>hs₁:τ₁ <: σ₁hs₂:σ₂ <: τ₂⊢ ?refl.right.τ₁ <: τ₂x:Stringt₂:Tmσ₁:Tyτ₁:Tyτ₂:Tyσ₂:Tyht:<{ ~(x →ₚ σ₁) ⊢ t₂ ⦂ σ₂ }>hs₁:τ₁ <: σ₁hs₂:σ₂ <: τ₂⊢ Ty All goals completed! 🐙
8.3.5. Weakening
The weakening lemma is proved as in pure STLC, with the exception of the sub case,
which requires a manual use of the sub rule.
theorem weakening {Γ Γ' : Context} {t : Tm} {τ: Ty}
(hi : Γ ⊆ Γ')
(ht : <{ Γ ⊢ t ⦂ τ }>) :
<{ Γ' ⊢ t ⦂ τ }> := Γ:ContextΓ':Contextt:Tmτ:Tyhi:Γ ⊆ Γ'ht:<{ Γ ⊢ t ⦂ τ }>⊢ <{ Γ' ⊢ t ⦂ τ }>
induction ht generalizing Γ' with (try All goals completed! 🐙)
Γ✝:Contextt:Tmτ:TyΓ:Contextt₁:Tmτ₁:Tyτ₂:Tyht:<{ Γ ⊢ t₁ ⦂ τ₁ }>hs:τ₁ <: τ₂ih:∀ {Γ' : Context}, Γ ⊆ Γ' → <{ Γ' ⊢ t₁ ⦂ τ₁ }>Γ':Contexthi:Γ ⊆ Γ'⊢ <{ Γ' ⊢ t₁ ⦂ τ₂ }>
Γ✝:Contextt:Tmτ:TyΓ:Contextt₁:Tmτ₁:Tyτ₂:Tyht:<{ Γ ⊢ t₁ ⦂ τ₁ }>hs:τ₁ <: τ₂ih:∀ {Γ' : Context}, Γ ⊆ Γ' → <{ Γ' ⊢ t₁ ⦂ τ₁ }>Γ':Contexthi:Γ ⊆ Γ'⊢ <{ Γ' ⊢ t₁ ⦂ ~?sub.τ₁ }>Γ✝:Contextt:Tmτ:TyΓ:Contextt₁:Tmτ₁:Tyτ₂:Tyht:<{ Γ ⊢ t₁ ⦂ τ₁ }>hs:τ₁ <: τ₂ih:∀ {Γ' : Context}, Γ ⊆ Γ' → <{ Γ' ⊢ t₁ ⦂ τ₁ }>Γ':Contexthi:Γ ⊆ Γ'⊢ ?sub.τ₁ <: τ₂Γ✝:Contextt:Tmτ:TyΓ:Contextt₁:Tmτ₁:Tyτ₂:Tyht:<{ Γ ⊢ t₁ ⦂ τ₁ }>hs:τ₁ <: τ₂ih:∀ {Γ' : Context}, Γ ⊆ Γ' → <{ Γ' ⊢ t₁ ⦂ τ₁ }>Γ':Contexthi:Γ ⊆ Γ'⊢ Ty Γ✝:Contextt:Tmτ:TyΓ:Contextt₁:Tmτ₁:Tyτ₂:Tyht:<{ Γ ⊢ t₁ ⦂ τ₁ }>hs:τ₁ <: τ₂ih:∀ {Γ' : Context}, Γ ⊆ Γ' → <{ Γ' ⊢ t₁ ⦂ τ₁ }>Γ':Contexthi:Γ ⊆ Γ'⊢ <{ Γ' ⊢ t₁ ⦂ ~?sub.τ₁ }>Γ✝:Contextt:Tmτ:TyΓ:Contextt₁:Tmτ₁:Tyτ₂:Tyht:<{ Γ ⊢ t₁ ⦂ τ₁ }>hs:τ₁ <: τ₂ih:∀ {Γ' : Context}, Γ ⊆ Γ' → <{ Γ' ⊢ t₁ ⦂ τ₁ }>Γ':Contexthi:Γ ⊆ Γ'⊢ ?sub.τ₁ <: τ₂Γ✝:Contextt:Tmτ:TyΓ:Contextt₁:Tmτ₁:Tyτ₂:Tyht:<{ Γ ⊢ t₁ ⦂ τ₁ }>hs:τ₁ <: τ₂ih:∀ {Γ' : Context}, Γ ⊆ Γ' → <{ Γ' ⊢ t₁ ⦂ τ₁ }>Γ':Contexthi:Γ ⊆ Γ'⊢ Ty All goals completed! 🐙
theorem weakening_empty {Γ : Context} {t : Tm} {τ: Ty}
(ht :<{ ∅ ⊢ t ⦂ τ }>) :
<{ Γ ⊢ t ⦂ τ }> := Γ:Contextt:Tmτ:Tyht:<{ ∅ ⊢ t ⦂ τ }>⊢ <{ Γ ⊢ t ⦂ τ }>
Γ:Contextt:Tmτ:Tyht:<{ ∅ ⊢ t ⦂ τ }>⊢ ∅ ⊆ Γ
Γ:Contextt:Tmτ:Tyht:<{ ∅ ⊢ t ⦂ τ }>a✝:Stringb✝:Tyh:∅[a✝] = some b✝⊢ Γ[a✝] = some b✝
Γ:Contextt:Tmτ:Tyht:<{ ∅ ⊢ t ⦂ τ }>a✝:Stringb✝:Tyh:none = some b✝⊢ Γ[a✝] = some b✝
contradiction All goals completed! 🐙
8.3.6. Substitution
The substitution lemma is stated exactly as in pure STLC.
The proof is also the same except that here it is easier to use induction on typing derivations rather than on terms.
theorem substitution_preserves_typing {Γ : Context} {x : String} {τ₁ : Ty} {t v : Tm} {τ : Ty}
(ht : <{ x ↦ τ₁ ; Γ ⊢ t ⦂ τ }>)
(hv : <{ ∅ ⊢ v ⦂ τ₁ }>) :
<{ Γ ⊢ [x := v] t ⦂ τ }> := by Γ:Contextx:Stringτ₁:Tyt:Tmv:Tmτ:Tyht:<{ ~(x →ₚ τ₁ ; Γ) ⊢ t ⦂ τ }>hv:<{ ∅ ⊢ v ⦂ τ₁ }>⊢ <{ Γ ⊢ [~x := v] t ⦂ τ }>
generalize heq : x →ₚ τ₁ ; Γ = Γ' at ht Γ:Contextx:Stringτ₁:Tyt:Tmv:Tmτ:Tyhv:<{ ∅ ⊢ v ⦂ τ₁ }>Γ':PartialMap String Tyheq:x →ₚ τ₁ ; Γ = Γ'ht:<{ Γ' ⊢ t ⦂ τ }>⊢ <{ Γ ⊢ [~x := v] t ⦂ τ }>
induction ht generalizing x Γ with (
subst_vars snd τ₁:Tyt:Tmv:Tmτ:Tyhv:<{ ∅ ⊢ v ⦂ τ₁ }>Γ':PartialMap String Tyt✝:Tmτ₁✝:Tyτ₂✝:TyΓ:Contextx:Stringh✝:<{ ~(x →ₚ τ₁ ; Γ) ⊢ t✝ ⦂ τ₁✝ × τ₂✝ }>h_ih✝:∀ {Γ_1 : Context} {x_1 : String}, x_1 →ₚ τ₁ ; Γ_1 = x →ₚ τ₁ ; Γ → <{ Γ_1 ⊢ [~x_1 := v] t✝ ⦂ τ₁✝ × τ₂✝ }>⊢ <{ Γ ⊢ [~x := v] (snd t✝) ⦂ τ₂✝ }>; try rw [subst var τ₁:Tyt:Tmv:Tmτ:Tyhv:<{ ∅ ⊢ v ⦂ τ₁ }>Γ':PartialMap String Tyy:Stringσ:TyΓ:Contextx:Stringh:(x →ₚ τ₁ ; Γ)[y] = some σ⊢ <{ Γ ⊢ ~(if x = y then v else StlcSub.Tm.var y) ⦂ σ }>] fst τ₁:Tyt:Tmv:Tmτ:Tyhv:<{ ∅ ⊢ v ⦂ τ₁ }>Γ':PartialMap String Tyt✝:Tmτ₁✝:Tyτ₂✝:TyΓ:Contextx:Stringh✝:<{ ~(x →ₚ τ₁ ; Γ) ⊢ t✝ ⦂ τ₁✝ × τ₂✝ }>h_ih✝:∀ {Γ_1 : Context} {x_1 : String}, x_1 →ₚ τ₁ ; Γ_1 = x →ₚ τ₁ ; Γ → <{ Γ_1 ⊢ [~x_1 := v] t✝ ⦂ τ₁✝ × τ₂✝ }>⊢ <{ Γ ⊢ fst [~x := v] t✝ ⦂ τ₁✝ }> snd τ₁:Tyt:Tmv:Tmτ:Tyhv:<{ ∅ ⊢ v ⦂ τ₁ }>Γ':PartialMap String Tyt✝:Tmτ₁✝:Tyτ₂✝:TyΓ:Contextx:Stringh✝:<{ ~(x →ₚ τ₁ ; Γ) ⊢ t✝ ⦂ τ₁✝ × τ₂✝ }>h_ih✝:∀ {Γ_1 : Context} {x_1 : String}, x_1 →ₚ τ₁ ; Γ_1 = x →ₚ τ₁ ; Γ → <{ Γ_1 ⊢ [~x_1 := v] t✝ ⦂ τ₁✝ × τ₂✝ }>⊢ <{ Γ ⊢ snd [~x := v] t✝ ⦂ τ₂✝ }>; try (apply_rules using StlcSubTyping All goals completed! 🐙; done))
| var Γ y σ h => var τ₁:Tyt:Tmv:Tmτ:Tyhv:<{ ∅ ⊢ v ⦂ τ₁ }>Γ':PartialMap String Tyy:Stringσ:TyΓ:Contextx:Stringh:(x →ₚ τ₁ ; Γ)[y] = some σ⊢ <{ Γ ⊢ ~(if x = y then v else StlcSub.Tm.var y) ⦂ σ }>
by_cases h₁ : x = y pos τ₁:Tyt:Tmv:Tmτ:Tyhv:<{ ∅ ⊢ v ⦂ τ₁ }>Γ':PartialMap String Tyy:Stringσ:TyΓ:Contextx:Stringh:(x →ₚ τ₁ ; Γ)[y] = some σh₁:x = y⊢ <{ Γ ⊢ ~(if x = y then v else StlcSub.Tm.var y) ⦂ σ }>neg τ₁:Tyt:Tmv:Tmτ:Tyhv:<{ ∅ ⊢ v ⦂ τ₁ }>Γ':PartialMap String Tyy:Stringσ:TyΓ:Contextx:Stringh:(x →ₚ τ₁ ; Γ)[y] = some σh₁:¬x = y⊢ <{ Γ ⊢ ~(if x = y then v else StlcSub.Tm.var y) ⦂ σ }>
· pos τ₁:Tyt:Tmv:Tmτ:Tyhv:<{ ∅ ⊢ v ⦂ τ₁ }>Γ':PartialMap String Tyy:Stringσ:TyΓ:Contextx:Stringh:(x →ₚ τ₁ ; Γ)[y] = some σh₁:x = y⊢ <{ Γ ⊢ ~(if x = y then v else StlcSub.Tm.var y) ⦂ σ }> subst h₁ pos τ₁:Tyt:Tmv:Tmτ:Tyhv:<{ ∅ ⊢ v ⦂ τ₁ }>Γ':PartialMap String Tyσ:TyΓ:Contextx:Stringh:(x →ₚ τ₁ ; Γ)[x] = some σ⊢ <{ Γ ⊢ ~(if x = x then v else StlcSub.Tm.var x) ⦂ σ }>; simp at h pos τ₁:Tyt:Tmv:Tmτ:Tyhv:<{ ∅ ⊢ v ⦂ τ₁ }>Γ':PartialMap String Tyσ:TyΓ:Contextx:Stringh:τ₁ = σ⊢ <{ Γ ⊢ ~(if x = x then v else StlcSub.Tm.var x) ⦂ σ }>; subst h pos τ₁:Tyt:Tmv:Tmτ:Tyhv:<{ ∅ ⊢ v ⦂ τ₁ }>Γ':PartialMap String TyΓ:Contextx:String⊢ <{ Γ ⊢ ~(if x = x then v else StlcSub.Tm.var x) ⦂ τ₁ }>;
apply weakening_empty at hv pos τ₁:Tyt:Tmv:Tmτ:Tyhv✝:<{ ∅ ⊢ v ⦂ τ₁ }>Γ':PartialMap String TyΓ:Contextx:Stringhv:<{ ~?Γ ⊢ v ⦂ τ₁ }>⊢ <{ Γ ⊢ ~(if x = x then v else StlcSub.Tm.var x) ⦂ τ₁ }>Γ τ₁:Tyt:Tmv:Tmτ:Tyhv:<{ ∅ ⊢ v ⦂ τ₁ }>Γ':PartialMap String TyΓ:Contextx:String⊢ Context
simp pos τ₁:Tyt:Tmv:Tmτ:Tyhv✝:<{ ∅ ⊢ v ⦂ τ₁ }>Γ':PartialMap String TyΓ:Contextx:Stringhv:<{ ~?Γ ⊢ v ⦂ τ₁ }>⊢ <{ Γ ⊢ v ⦂ τ₁ }>Γ τ₁:Tyt:Tmv:Tmτ:Tyhv:<{ ∅ ⊢ v ⦂ τ₁ }>Γ':PartialMap String TyΓ:Contextx:String⊢ Context; assumption All goals completed! 🐙
· neg τ₁:Tyt:Tmv:Tmτ:Tyhv:<{ ∅ ⊢ v ⦂ τ₁ }>Γ':PartialMap String Tyy:Stringσ:TyΓ:Contextx:Stringh:(x →ₚ τ₁ ; Γ)[y] = some σh₁:¬x = y⊢ <{ Γ ⊢ ~(if x = y then v else StlcSub.Tm.var y) ⦂ σ }> rw [PartialMap.update_neq neg τ₁:Tyt:Tmv:Tmτ:Tyhv:<{ ∅ ⊢ v ⦂ τ₁ }>Γ':PartialMap String Tyy:Stringσ:TyΓ:Contextx:Stringh:Γ[y] = some σh₁:¬x = y⊢ <{ Γ ⊢ ~(if x = y then v else StlcSub.Tm.var y) ⦂ σ }>neg.h τ₁:Tyt:Tmv:Tmτ:Tyhv:<{ ∅ ⊢ v ⦂ τ₁ }>Γ':PartialMap String Tyy:Stringσ:TyΓ:Contextx:Stringh:(x →ₚ τ₁ ; Γ)[y] = some σh₁:¬x = y⊢ x ≠ y] at h neg τ₁:Tyt:Tmv:Tmτ:Tyhv:<{ ∅ ⊢ v ⦂ τ₁ }>Γ':PartialMap String Tyy:Stringσ:TyΓ:Contextx:Stringh:Γ[y] = some σh₁:¬x = y⊢ <{ Γ ⊢ ~(if x = y then v else StlcSub.Tm.var y) ⦂ σ }>neg.h τ₁:Tyt:Tmv:Tmτ:Tyhv:<{ ∅ ⊢ v ⦂ τ₁ }>Γ':PartialMap String Tyy:Stringσ:TyΓ:Contextx:Stringh:(x →ₚ τ₁ ; Γ)[y] = some σh₁:¬x = y⊢ x ≠ y <;> neg τ₁:Tyt:Tmv:Tmτ:Tyhv:<{ ∅ ⊢ v ⦂ τ₁ }>Γ':PartialMap String Tyy:Stringσ:TyΓ:Contextx:Stringh:Γ[y] = some σh₁:¬x = y⊢ <{ Γ ⊢ ~(if x = y then v else StlcSub.Tm.var y) ⦂ σ }>neg.h τ₁:Tyt:Tmv:Tmτ:Tyhv:<{ ∅ ⊢ v ⦂ τ₁ }>Γ':PartialMap String Tyy:Stringσ:TyΓ:Contextx:Stringh:(x →ₚ τ₁ ; Γ)[y] = some σh₁:¬x = y⊢ x ≠ y simp_all All goals completed! 🐙
apply_rules using StlcSubTyping All goals completed! 🐙
| abs _ y _ _ _ h ih => abs τ₁:Tyt:Tmv:Tmτ:Tyhv:<{ ∅ ⊢ v ⦂ τ₁ }>Γ':PartialMap String Tyy:Stringτ₁✝:Tyτ₂✝:Tyt₁✝:TmΓ:Contextx:Stringh:<{ ~(y →ₚ τ₂✝ ; x →ₚ τ₁ ; Γ) ⊢ t₁✝ ⦂ τ₁✝ }>ih:∀ {Γ_1 : Context} {x_1 : String}, x_1 →ₚ τ₁ ; Γ_1 = y →ₚ τ₂✝ ; x →ₚ τ₁ ; Γ → <{ Γ_1 ⊢ [~x_1 := v] t₁✝ ⦂ τ₁✝ }>⊢ <{ Γ ⊢ ~(if x = y then <{ λ ~y : τ₂✝ . t₁✝ }> else <{ λ ~y : τ₂✝ . [~x := v] t₁✝ }>) ⦂ τ₂✝ → τ₁✝ }>
by_cases h₁ : x = y pos τ₁:Tyt:Tmv:Tmτ:Tyhv:<{ ∅ ⊢ v ⦂ τ₁ }>Γ':PartialMap String Tyy:Stringτ₁✝:Tyτ₂✝:Tyt₁✝:TmΓ:Contextx:Stringh:<{ ~(y →ₚ τ₂✝ ; x →ₚ τ₁ ; Γ) ⊢ t₁✝ ⦂ τ₁✝ }>ih:∀ {Γ_1 : Context} {x_1 : String}, x_1 →ₚ τ₁ ; Γ_1 = y →ₚ τ₂✝ ; x →ₚ τ₁ ; Γ → <{ Γ_1 ⊢ [~x_1 := v] t₁✝ ⦂ τ₁✝ }>h₁:x = y⊢ <{ Γ ⊢ ~(if x = y then <{ λ ~y : τ₂✝ . t₁✝ }> else <{ λ ~y : τ₂✝ . [~x := v] t₁✝ }>) ⦂ τ₂✝ → τ₁✝ }>neg τ₁:Tyt:Tmv:Tmτ:Tyhv:<{ ∅ ⊢ v ⦂ τ₁ }>Γ':PartialMap String Tyy:Stringτ₁✝:Tyτ₂✝:Tyt₁✝:TmΓ:Contextx:Stringh:<{ ~(y →ₚ τ₂✝ ; x →ₚ τ₁ ; Γ) ⊢ t₁✝ ⦂ τ₁✝ }>ih:∀ {Γ_1 : Context} {x_1 : String}, x_1 →ₚ τ₁ ; Γ_1 = y →ₚ τ₂✝ ; x →ₚ τ₁ ; Γ → <{ Γ_1 ⊢ [~x_1 := v] t₁✝ ⦂ τ₁✝ }>h₁:¬x = y⊢ <{ Γ ⊢ ~(if x = y then <{ λ ~y : τ₂✝ . t₁✝ }> else <{ λ ~y : τ₂✝ . [~x := v] t₁✝ }>) ⦂ τ₂✝ → τ₁✝ }>
· pos τ₁:Tyt:Tmv:Tmτ:Tyhv:<{ ∅ ⊢ v ⦂ τ₁ }>Γ':PartialMap String Tyy:Stringτ₁✝:Tyτ₂✝:Tyt₁✝:TmΓ:Contextx:Stringh:<{ ~(y →ₚ τ₂✝ ; x →ₚ τ₁ ; Γ) ⊢ t₁✝ ⦂ τ₁✝ }>ih:∀ {Γ_1 : Context} {x_1 : String}, x_1 →ₚ τ₁ ; Γ_1 = y →ₚ τ₂✝ ; x →ₚ τ₁ ; Γ → <{ Γ_1 ⊢ [~x_1 := v] t₁✝ ⦂ τ₁✝ }>h₁:x = y⊢ <{ Γ ⊢ ~(if x = y then <{ λ ~y : τ₂✝ . t₁✝ }> else <{ λ ~y : τ₂✝ . [~x := v] t₁✝ }>) ⦂ τ₂✝ → τ₁✝ }> simp_all [PartialMap.update_shadow] pos τ₁:Tyt:Tmv:Tmτ:Tyhv:<{ ∅ ⊢ v ⦂ τ₁ }>Γ':PartialMap String Tyy:Stringτ₁✝:Tyτ₂✝:Tyt₁✝:TmΓ:Contextx:Stringh:<{ ~(y →ₚ τ₂✝ ; Γ) ⊢ t₁✝ ⦂ τ₁✝ }>ih:∀ {Γ_1 : Context} {x : String}, x →ₚ τ₁ ; Γ_1 = y →ₚ τ₂✝ ; Γ → <{ Γ_1 ⊢ [~x := v] t₁✝ ⦂ τ₁✝ }>h₁:x = y⊢ <{ Γ ⊢ λ ~y : τ₂✝ . t₁✝ ⦂ τ₂✝ → τ₁✝ }>; apply_rules using StlcSubTyping All goals completed! 🐙
· neg τ₁:Tyt:Tmv:Tmτ:Tyhv:<{ ∅ ⊢ v ⦂ τ₁ }>Γ':PartialMap String Tyy:Stringτ₁✝:Tyτ₂✝:Tyt₁✝:TmΓ:Contextx:Stringh:<{ ~(y →ₚ τ₂✝ ; x →ₚ τ₁ ; Γ) ⊢ t₁✝ ⦂ τ₁✝ }>ih:∀ {Γ_1 : Context} {x_1 : String}, x_1 →ₚ τ₁ ; Γ_1 = y →ₚ τ₂✝ ; x →ₚ τ₁ ; Γ → <{ Γ_1 ⊢ [~x_1 := v] t₁✝ ⦂ τ₁✝ }>h₁:¬x = y⊢ <{ Γ ⊢ ~(if x = y then <{ λ ~y : τ₂✝ . t₁✝ }> else <{ λ ~y : τ₂✝ . [~x := v] t₁✝ }>) ⦂ τ₂✝ → τ₁✝ }> simp_all neg τ₁:Tyt:Tmv:Tmτ:Tyhv:<{ ∅ ⊢ v ⦂ τ₁ }>Γ':PartialMap String Tyy:Stringτ₁✝:Tyτ₂✝:Tyt₁✝:TmΓ:Contextx:Stringh:<{ ~(y →ₚ τ₂✝ ; x →ₚ τ₁ ; Γ) ⊢ t₁✝ ⦂ τ₁✝ }>ih:∀ {Γ_1 : Context} {x_1 : String}, x_1 →ₚ τ₁ ; Γ_1 = y →ₚ τ₂✝ ; x →ₚ τ₁ ; Γ → <{ Γ_1 ⊢ [~x_1 := v] t₁✝ ⦂ τ₁✝ }>h₁:¬x = y⊢ <{ Γ ⊢ λ ~y : τ₂✝ . [~x := v] t₁✝ ⦂ τ₂✝ → τ₁✝ }>; constructor neg τ₁:Tyt:Tmv:Tmτ:Tyhv:<{ ∅ ⊢ v ⦂ τ₁ }>Γ':PartialMap String Tyy:Stringτ₁✝:Tyτ₂✝:Tyt₁✝:TmΓ:Contextx:Stringh:<{ ~(y →ₚ τ₂✝ ; x →ₚ τ₁ ; Γ) ⊢ t₁✝ ⦂ τ₁✝ }>ih:∀ {Γ_1 : Context} {x_1 : String}, x_1 →ₚ τ₁ ; Γ_1 = y →ₚ τ₂✝ ; x →ₚ τ₁ ; Γ → <{ Γ_1 ⊢ [~x_1 := v] t₁✝ ⦂ τ₁✝ }>h₁:¬x = y⊢ <{ ~(y →ₚ τ₂✝ ; Γ) ⊢ [~x := v] t₁✝ ⦂ τ₁✝ }>; apply ih neg τ₁:Tyt:Tmv:Tmτ:Tyhv:<{ ∅ ⊢ v ⦂ τ₁ }>Γ':PartialMap String Tyy:Stringτ₁✝:Tyτ₂✝:Tyt₁✝:TmΓ:Contextx:Stringh:<{ ~(y →ₚ τ₂✝ ; x →ₚ τ₁ ; Γ) ⊢ t₁✝ ⦂ τ₁✝ }>ih:∀ {Γ_1 : Context} {x_1 : String}, x_1 →ₚ τ₁ ; Γ_1 = y →ₚ τ₂✝ ; x →ₚ τ₁ ; Γ → <{ Γ_1 ⊢ [~x_1 := v] t₁✝ ⦂ τ₁✝ }>h₁:¬x = y⊢ x →ₚ τ₁ ; y →ₚ τ₂✝ ; Γ = y →ₚ τ₂✝ ; x →ₚ τ₁ ; Γ; rw [PartialMap.update_permute neg τ₁:Tyt:Tmv:Tmτ:Tyhv:<{ ∅ ⊢ v ⦂ τ₁ }>Γ':PartialMap String Tyy:Stringτ₁✝:Tyτ₂✝:Tyt₁✝:TmΓ:Contextx:Stringh:<{ ~(y →ₚ τ₂✝ ; x →ₚ τ₁ ; Γ) ⊢ t₁✝ ⦂ τ₁✝ }>ih:∀ {Γ_1 : Context} {x_1 : String}, x_1 →ₚ τ₁ ; Γ_1 = y →ₚ τ₂✝ ; x →ₚ τ₁ ; Γ → <{ Γ_1 ⊢ [~x_1 := v] t₁✝ ⦂ τ₁✝ }>h₁:¬x = y⊢ y →ₚ τ₂✝ ; x →ₚ τ₁ ; Γ = y →ₚ τ₂✝ ; x →ₚ τ₁ ; Γneg τ₁:Tyt:Tmv:Tmτ:Tyhv:<{ ∅ ⊢ v ⦂ τ₁ }>Γ':PartialMap String Tyy:Stringτ₁✝:Tyτ₂✝:Tyt₁✝:TmΓ:Contextx:Stringh:<{ ~(y →ₚ τ₂✝ ; x →ₚ τ₁ ; Γ) ⊢ t₁✝ ⦂ τ₁✝ }>ih:∀ {Γ_1 : Context} {x_1 : String}, x_1 →ₚ τ₁ ; Γ_1 = y →ₚ τ₂✝ ; x →ₚ τ₁ ; Γ → <{ Γ_1 ⊢ [~x_1 := v] t₁✝ ⦂ τ₁✝ }>h₁:¬x = y⊢ x ≠ y] neg τ₁:Tyt:Tmv:Tmτ:Tyhv:<{ ∅ ⊢ v ⦂ τ₁ }>Γ':PartialMap String Tyy:Stringτ₁✝:Tyτ₂✝:Tyt₁✝:TmΓ:Contextx:Stringh:<{ ~(y →ₚ τ₂✝ ; x →ₚ τ₁ ; Γ) ⊢ t₁✝ ⦂ τ₁✝ }>ih:∀ {Γ_1 : Context} {x_1 : String}, x_1 →ₚ τ₁ ; Γ_1 = y →ₚ τ₂✝ ; x →ₚ τ₁ ; Γ → <{ Γ_1 ⊢ [~x_1 := v] t₁✝ ⦂ τ₁✝ }>h₁:¬x = y⊢ x ≠ y; lia All goals completed! 🐙
| sub Γ t₁ τ₁ τ₂ ht hs ih => sub τ₁✝:Tyt:Tmv:Tmτ:Tyhv:<{ ∅ ⊢ v ⦂ τ₁ }>Γ':PartialMap String Tyt₁:Tmτ₁:Tyτ₂:Tyhs:τ₁ <: τ₂Γ:Contextx:Stringht:<{ ~(x →ₚ τ₁✝ ; Γ) ⊢ t₁ ⦂ τ₁ }>ih:∀ {Γ_1 : Context} {x_1 : String}, x_1 →ₚ τ₁✝ ; Γ_1 = x →ₚ τ₁✝ ; Γ → <{ Γ_1 ⊢ [~x_1 := v] t₁ ⦂ τ₁ }>⊢ <{ Γ ⊢ [~x := v] t₁ ⦂ τ₂ }>
apply HasType.sub sub.ht τ₁✝:Tyt:Tmv:Tmτ:Tyhv:<{ ∅ ⊢ v ⦂ τ₁ }>Γ':PartialMap String Tyt₁:Tmτ₁:Tyτ₂:Tyhs:τ₁ <: τ₂Γ:Contextx:Stringht:<{ ~(x →ₚ τ₁✝ ; Γ) ⊢ t₁ ⦂ τ₁ }>ih:∀ {Γ_1 : Context} {x_1 : String}, x_1 →ₚ τ₁✝ ; Γ_1 = x →ₚ τ₁✝ ; Γ → <{ Γ_1 ⊢ [~x_1 := v] t₁ ⦂ τ₁ }>⊢ <{ Γ ⊢ [~x := v] t₁ ⦂ ~?sub.τ₁ }>sub.hs τ₁✝:Tyt:Tmv:Tmτ:Tyhv:<{ ∅ ⊢ v ⦂ τ₁ }>Γ':PartialMap String Tyt₁:Tmτ₁:Tyτ₂:Tyhs:τ₁ <: τ₂Γ:Contextx:Stringht:<{ ~(x →ₚ τ₁✝ ; Γ) ⊢ t₁ ⦂ τ₁ }>ih:∀ {Γ_1 : Context} {x_1 : String}, x_1 →ₚ τ₁✝ ; Γ_1 = x →ₚ τ₁✝ ; Γ → <{ Γ_1 ⊢ [~x_1 := v] t₁ ⦂ τ₁ }>⊢ ?sub.τ₁ <: τ₂sub.τ₁ τ₁✝:Tyt:Tmv:Tmτ:Tyhv:<{ ∅ ⊢ v ⦂ τ₁ }>Γ':PartialMap String Tyt₁:Tmτ₁:Tyτ₂:Tyhs:τ₁ <: τ₂Γ:Contextx:Stringht:<{ ~(x →ₚ τ₁✝ ; Γ) ⊢ t₁ ⦂ τ₁ }>ih:∀ {Γ_1 : Context} {x_1 : String}, x_1 →ₚ τ₁✝ ; Γ_1 = x →ₚ τ₁✝ ; Γ → <{ Γ_1 ⊢ [~x_1 := v] t₁ ⦂ τ₁ }>⊢ Ty <;> sub.ht τ₁✝:Tyt:Tmv:Tmτ:Tyhv:<{ ∅ ⊢ v ⦂ τ₁ }>Γ':PartialMap String Tyt₁:Tmτ₁:Tyτ₂:Tyhs:τ₁ <: τ₂Γ:Contextx:Stringht:<{ ~(x →ₚ τ₁✝ ; Γ) ⊢ t₁ ⦂ τ₁ }>ih:∀ {Γ_1 : Context} {x_1 : String}, x_1 →ₚ τ₁✝ ; Γ_1 = x →ₚ τ₁✝ ; Γ → <{ Γ_1 ⊢ [~x_1 := v] t₁ ⦂ τ₁ }>⊢ <{ Γ ⊢ [~x := v] t₁ ⦂ ~?sub.τ₁ }>sub.hs τ₁✝:Tyt:Tmv:Tmτ:Tyhv:<{ ∅ ⊢ v ⦂ τ₁ }>Γ':PartialMap String Tyt₁:Tmτ₁:Tyτ₂:Tyhs:τ₁ <: τ₂Γ:Contextx:Stringht:<{ ~(x →ₚ τ₁✝ ; Γ) ⊢ t₁ ⦂ τ₁ }>ih:∀ {Γ_1 : Context} {x_1 : String}, x_1 →ₚ τ₁✝ ; Γ_1 = x →ₚ τ₁✝ ; Γ → <{ Γ_1 ⊢ [~x_1 := v] t₁ ⦂ τ₁ }>⊢ ?sub.τ₁ <: τ₂sub.τ₁ τ₁✝:Tyt:Tmv:Tmτ:Tyhv:<{ ∅ ⊢ v ⦂ τ₁ }>Γ':PartialMap String Tyt₁:Tmτ₁:Tyτ₂:Tyhs:τ₁ <: τ₂Γ:Contextx:Stringht:<{ ~(x →ₚ τ₁✝ ; Γ) ⊢ t₁ ⦂ τ₁ }>ih:∀ {Γ_1 : Context} {x_1 : String}, x_1 →ₚ τ₁✝ ; Γ_1 = x →ₚ τ₁✝ ; Γ → <{ Γ_1 ⊢ [~x_1 := v] t₁ ⦂ τ₁ }>⊢ Ty solve_by_elim using StlcSubTyping All goals completed! 🐙
8.3.7. Preservation
The proof of preservation now proceeds pretty much as in earlier chapters, using the substitution lemma at the appropriate point and the inversion lemma from above to extract structural information from typing assumptions.
Theorem (Preservation): If t, t' are terms and τ is a type
such that ∅ ⊢ t ⦂ τ and t ⟶ t', then ∅ ⊢ t' ⦂ τ.
Proof: Let t and τ be given such that ∅ ⊢ t ⦂ τ.
We proceed by induction on the structure of this typing
derivation. The abs, unit, tru, and fls cases
are vacuous because abstractions and constants don't step. Case
var is vacuous as well, since the context is empty.
-
If the final step of the derivation is by
app, then there are termst₁andt₂and typesτ₁andτ₂such thatt = t₁ t₂,τ = τ₂,∅ ⊢ t₁ ⦂ τ₁ → τ₂, and∅ ⊢ t₂ ⦂ τ₁.By the definition of the step relation, there are three ways
t₁ t₂can step. Casesapp₁'andapp₂follow immediately by the induction hypotheses for the typing subderivations and a use ofapp.Suppose instead
t₁ t₂steps byappAbs. Thent₁ = λ x:σ . t₁₂for some typeσand termt₁₂, andt' = [x:=t₂] t₁₂.By lemma
abs_arrow, we haveτ₁ <: σandx ↦ σ ; ∅ ⊢ t₁₂ ⦂ τ₂. It then follows by the substitution lemma (substitution_preserves_typing) that∅ ⊢ [x:=t₂] t₁₂ ⦂ τ₂as desired. -
If the final step of the derivation uses rule
if, then there are termst₁,t₂, andt₃such thatt = if t₁ then t₂ else t₃, with∅ ⊢ t₁ ⦂ Booland with∅ ⊢ t₂ ⦂ τand∅ ⊢ t₃ ⦂ τ. Moreover, by the induction hypothesis, ift₁steps tot₁'then∅ ⊢ t₁' : Bool. There are three cases to consider, depending on which rule was used to showt ⟶ t'.-
If
t ⟶ t'by ruleif, thent' = if t₁' then t₂ else t₃witht₁ ⟶ t₁'. By the induction hypothesis,∅ ⊢ t₁' ⦂ Bool, and so∅ ⊢ t' ⦂ τbyif. -
If
t ⟶ t'by ruleifTrueorifFalse, then eithert' = t₂ort' = t₃, and∅ ⊢ t' ⦂ τfollows by assumption.
-
-
If the final step of the derivation is by
sub, then there is a typeσsuch thatσ <: τand∅ ⊢ t ⦂ σ. The result is immediate by the induction hypothesis for the typing subderivation and an application ofsub.
Qed.
theorem preservation {t t' : Tm} {τ : Ty}
(ht : <{ ∅ ⊢ t ⦂ τ }>)
(hs : t ⟶ t') :
<{ ∅ ⊢ t' ⦂ τ }> := by t:Tmt':Tmτ:Tyht:<{ ∅ ⊢ t ⦂ τ }>hs:t ⟶ t'⊢ <{ ∅ ⊢ t' ⦂ τ }>
generalize heq : (∅ : Context) = Γ at ht t:Tmt':Tmτ:Tyhs:t ⟶ t'Γ:Contextheq:∅ = Γht:<{ Γ ⊢ t ⦂ τ }>⊢ <{ Γ ⊢ t' ⦂ τ }>
induction ht generalizing t' with (subst_vars snd t:Tmτ:TyΓ:Contextt✝:Tmτ₁✝:Tyτ₂✝:Tyt':Tmhs:<{ snd t✝ }> ⟶ t'h✝:<{ ∅ ⊢ t✝ ⦂ τ₁✝ × τ₂✝ }>h_ih✝:∀ {t' : Tm}, t✝ ⟶ t' → ∅ = ∅ → <{ ∅ ⊢ t' ⦂ τ₁✝ × τ₂✝ }>⊢ <{ ∅ ⊢ t' ⦂ τ₂✝ }>; first
-- discharge the goals where `t` doesn't step
| inversion hs snd₁ t:Tmτ:TyΓ:Contextt✝:Tmτ₁✝:Tyτ₂✝:Tyh✝:<{ ∅ ⊢ t✝ ⦂ τ₁✝ × τ₂✝ }>h_ih✝:∀ {t' : Tm}, t✝ ⟶ t' → ∅ = ∅ → <{ ∅ ⊢ t' ⦂ τ₁✝ × τ₂✝ }>t'✝:Tma✝:t✝ ⟶ t'✝⊢ <{ ∅ ⊢ snd t'✝ ⦂ τ₂✝ }>sndPair t:Tmτ:TyΓ:Contextτ₁✝:Tyτ₂✝:Tyt':Tmv₁✝:Tma✝¹:v₁✝.IsValuea✝:t'.IsValueh✝:<{ ∅ ⊢ ( v₁✝ , t' ) ⦂ τ₁✝ × τ₂✝ }>h_ih✝:∀ {t'_1 : Tm}, <{ ( v₁✝ , t' ) }> ⟶ t'_1 → ∅ = ∅ → <{ ∅ ⊢ t'_1 ⦂ τ₁✝ × τ₂✝ }>⊢ <{ ∅ ⊢ t' ⦂ τ₂✝ }> <;> snd₁ t:Tmτ:TyΓ:Contextt✝:Tmτ₁✝:Tyτ₂✝:Tyh✝:<{ ∅ ⊢ t✝ ⦂ τ₁✝ × τ₂✝ }>h_ih✝:∀ {t' : Tm}, t✝ ⟶ t' → ∅ = ∅ → <{ ∅ ⊢ t' ⦂ τ₁✝ × τ₂✝ }>t'✝:Tma✝:t✝ ⟶ t'✝⊢ <{ ∅ ⊢ snd t'✝ ⦂ τ₂✝ }>sndPair t:Tmτ:TyΓ:Contextτ₁✝:Tyτ₂✝:Tyt':Tmv₁✝:Tma✝¹:v₁✝.IsValuea✝:t'.IsValueh✝:<{ ∅ ⊢ ( v₁✝ , t' ) ⦂ τ₁✝ × τ₂✝ }>h_ih✝:∀ {t'_1 : Tm}, <{ ( v₁✝ , t' ) }> ⟶ t'_1 → ∅ = ∅ → <{ ∅ ⊢ t'_1 ⦂ τ₁✝ × τ₂✝ }>⊢ <{ ∅ ⊢ t' ⦂ τ₂✝ }> constructor sndPair.ht t:Tmτ:TyΓ:Contextτ₁✝:Tyτ₂✝:Tyt':Tmv₁✝:Tma✝¹:v₁✝.IsValuea✝:t'.IsValueh✝:<{ ∅ ⊢ ( v₁✝ , t' ) ⦂ τ₁✝ × τ₂✝ }>h_ih✝:∀ {t'_1 : Tm}, <{ ( v₁✝ , t' ) }> ⟶ t'_1 → ∅ = ∅ → <{ ∅ ⊢ t'_1 ⦂ τ₁✝ × τ₂✝ }>⊢ <{ ∅ ⊢ t' ⦂ ~?sndPair.τ₁ }>sndPair.hs t:Tmτ:TyΓ:Contextτ₁✝:Tyτ₂✝:Tyt':Tmv₁✝:Tma✝¹:v₁✝.IsValuea✝:t'.IsValueh✝:<{ ∅ ⊢ ( v₁✝ , t' ) ⦂ τ₁✝ × τ₂✝ }>h_ih✝:∀ {t'_1 : Tm}, <{ ( v₁✝ , t' ) }> ⟶ t'_1 → ∅ = ∅ → <{ ∅ ⊢ t'_1 ⦂ τ₁✝ × τ₂✝ }>⊢ ?sndPair.τ₁ <: τ₂✝sndPair.τ₁ t:Tmτ:TyΓ:Contextτ₁✝:Tyτ₂✝:Tyt':Tmv₁✝:Tma✝¹:v₁✝.IsValuea✝:t'.IsValueh✝:<{ ∅ ⊢ ( v₁✝ , t' ) ⦂ τ₁✝ × τ₂✝ }>h_ih✝:∀ {t'_1 : Tm}, <{ ( v₁✝ , t' ) }> ⟶ t'_1 → ∅ = ∅ → <{ ∅ ⊢ t'_1 ⦂ τ₁✝ × τ₂✝ }>⊢ Ty <;> snd₁.ht t:Tmτ:TyΓ:Contextt✝:Tmτ₁✝:Tyτ₂✝:Tyh✝:<{ ∅ ⊢ t✝ ⦂ τ₁✝ × τ₂✝ }>h_ih✝:∀ {t' : Tm}, t✝ ⟶ t' → ∅ = ∅ → <{ ∅ ⊢ t' ⦂ τ₁✝ × τ₂✝ }>t'✝:Tma✝:t✝ ⟶ t'✝⊢ <{ ∅ ⊢ snd t'✝ ⦂ ~?snd₁.τ₁ }>snd₁.hs t:Tmτ:TyΓ:Contextt✝:Tmτ₁✝:Tyτ₂✝:Tyh✝:<{ ∅ ⊢ t✝ ⦂ τ₁✝ × τ₂✝ }>h_ih✝:∀ {t' : Tm}, t✝ ⟶ t' → ∅ = ∅ → <{ ∅ ⊢ t' ⦂ τ₁✝ × τ₂✝ }>t'✝:Tma✝:t✝ ⟶ t'✝⊢ ?snd₁.τ₁ <: τ₂✝snd₁.τ₁ t:Tmτ:TyΓ:Contextt✝:Tmτ₁✝:Tyτ₂✝:Tyh✝:<{ ∅ ⊢ t✝ ⦂ τ₁✝ × τ₂✝ }>h_ih✝:∀ {t' : Tm}, t✝ ⟶ t' → ∅ = ∅ → <{ ∅ ⊢ t' ⦂ τ₁✝ × τ₂✝ }>t'✝:Tma✝:t✝ ⟶ t'✝⊢ TysndPair.ht t:Tmτ:TyΓ:Contextτ₁✝:Tyτ₂✝:Tyt':Tmv₁✝:Tma✝¹:v₁✝.IsValuea✝:t'.IsValueh✝:<{ ∅ ⊢ ( v₁✝ , t' ) ⦂ τ₁✝ × τ₂✝ }>h_ih✝:∀ {t'_1 : Tm}, <{ ( v₁✝ , t' ) }> ⟶ t'_1 → ∅ = ∅ → <{ ∅ ⊢ t'_1 ⦂ τ₁✝ × τ₂✝ }>⊢ <{ ∅ ⊢ t' ⦂ ~?sndPair.τ₁ }>sndPair.hs t:Tmτ:TyΓ:Contextτ₁✝:Tyτ₂✝:Tyt':Tmv₁✝:Tma✝¹:v₁✝.IsValuea✝:t'.IsValueh✝:<{ ∅ ⊢ ( v₁✝ , t' ) ⦂ τ₁✝ × τ₂✝ }>h_ih✝:∀ {t'_1 : Tm}, <{ ( v₁✝ , t' ) }> ⟶ t'_1 → ∅ = ∅ → <{ ∅ ⊢ t'_1 ⦂ τ₁✝ × τ₂✝ }>⊢ ?sndPair.τ₁ <: τ₂✝sndPair.τ₁ t:Tmτ:TyΓ:Contextτ₁✝:Tyτ₂✝:Tyt':Tmv₁✝:Tma✝¹:v₁✝.IsValuea✝:t'.IsValueh✝:<{ ∅ ⊢ ( v₁✝ , t' ) ⦂ τ₁✝ × τ₂✝ }>h_ih✝:∀ {t'_1 : Tm}, <{ ( v₁✝ , t' ) }> ⟶ t'_1 → ∅ = ∅ → <{ ∅ ⊢ t'_1 ⦂ τ₁✝ × τ₂✝ }>⊢ Ty simp_all sndPair.τ₁ t:Tmτ:TyΓ:Contextτ₁✝:Tyτ₂✝:Tyt':Tmv₁✝:Tma✝¹:v₁✝.IsValuea✝:t'.IsValueh✝:<{ ∅ ⊢ ( v₁✝ , t' ) ⦂ τ₁✝ × τ₂✝ }>h_ih✝:∀ {t'_1 : Tm}, <{ ( v₁✝ , t' ) }> ⟶ t'_1 → <{ ∅ ⊢ t'_1 ⦂ τ₁✝ × τ₂✝ }>⊢ Ty; done All goals completed! 🐙
| try (inversion hs snd₁ t:Tmτ:TyΓ:Contextt✝:Tmτ₁✝:Tyτ₂✝:Tyh✝:<{ ∅ ⊢ t✝ ⦂ τ₁✝ × τ₂✝ }>h_ih✝:∀ {t' : Tm}, t✝ ⟶ t' → ∅ = ∅ → <{ ∅ ⊢ t' ⦂ τ₁✝ × τ₂✝ }>t'✝:Tma✝:t✝ ⟶ t'✝⊢ <{ ∅ ⊢ snd t'✝ ⦂ τ₂✝ }>sndPair t:Tmτ:TyΓ:Contextτ₁✝:Tyτ₂✝:Tyt':Tmv₁✝:Tma✝¹:v₁✝.IsValuea✝:t'.IsValueh✝:<{ ∅ ⊢ ( v₁✝ , t' ) ⦂ τ₁✝ × τ₂✝ }>h_ih✝:∀ {t'_1 : Tm}, <{ ( v₁✝ , t' ) }> ⟶ t'_1 → ∅ = ∅ → <{ ∅ ⊢ t'_1 ⦂ τ₁✝ × τ₂✝ }>⊢ <{ ∅ ⊢ t' ⦂ τ₂✝ }>; apply_rules using StlcSubTyping sndPair t:Tmτ:TyΓ:Contextτ₁✝:Tyτ₂✝:Tyt':Tmv₁✝:Tma✝¹:v₁✝.IsValuea✝:t'.IsValueh✝:<{ ∅ ⊢ ( v₁✝ , t' ) ⦂ τ₁✝ × τ₂✝ }>h_ih✝:∀ {t'_1 : Tm}, <{ ( v₁✝ , t' ) }> ⟶ t'_1 → ∅ = ∅ → <{ ∅ ⊢ t'_1 ⦂ τ₁✝ × τ₂✝ }>⊢ <{ ∅ ⊢ t' ⦂ τ₂✝ }>; done All goals completed! 🐙))
| app Γ τ₁' τ₂' t₁' t₂ h₁ h₂ ih₁ ih₂ => app t:Tmτ:TyΓ:Contextτ₁':Tyτ₂':Tyt₁':Tmt₂:Tmt':Tmhs:<{ t₁' t₂ }> ⟶ t'h₁:<{ ∅ ⊢ t₁' ⦂ τ₂' → τ₁' }>h₂:<{ ∅ ⊢ t₂ ⦂ τ₂' }>ih₁:∀ {t' : Tm}, t₁' ⟶ t' → ∅ = ∅ → <{ ∅ ⊢ t' ⦂ τ₂' → τ₁' }>ih₂:∀ {t' : Tm}, t₂ ⟶ t' → ∅ = ∅ → <{ ∅ ⊢ t' ⦂ τ₂' }>⊢ <{ ∅ ⊢ t' ⦂ τ₁' }>
inversion hs with (try (constructor app₂.h₁ t:Tmτ:TyΓ:Contextτ₁':Tyτ₂':Tyt₁':Tmt₂:Tmh₁:<{ ∅ ⊢ t₁' ⦂ τ₂' → τ₁' }>h₂:<{ ∅ ⊢ t₂ ⦂ τ₂' }>ih₁:∀ {t' : Tm}, t₁' ⟶ t' → ∅ = ∅ → <{ ∅ ⊢ t' ⦂ τ₂' → τ₁' }>ih₂:∀ {t' : Tm}, t₂ ⟶ t' → ∅ = ∅ → <{ ∅ ⊢ t' ⦂ τ₂' }>t₂'✝:Tma✝¹:t₁'.IsValuea✝:t₂ ⟶ t₂'✝⊢ <{ ∅ ⊢ t₁' ⦂ ~?app₂.τ₂ → τ₁' }>app₂.h₂ t:Tmτ:TyΓ:Contextτ₁':Tyτ₂':Tyt₁':Tmt₂:Tmh₁:<{ ∅ ⊢ t₁' ⦂ τ₂' → τ₁' }>h₂:<{ ∅ ⊢ t₂ ⦂ τ₂' }>ih₁:∀ {t' : Tm}, t₁' ⟶ t' → ∅ = ∅ → <{ ∅ ⊢ t' ⦂ τ₂' → τ₁' }>ih₂:∀ {t' : Tm}, t₂ ⟶ t' → ∅ = ∅ → <{ ∅ ⊢ t' ⦂ τ₂' }>t₂'✝:Tma✝¹:t₁'.IsValuea✝:t₂ ⟶ t₂'✝⊢ <{ ∅ ⊢ t₂'✝ ⦂ ~?app₂.τ₂ }>app₂.τ₂ t:Tmτ:TyΓ:Contextτ₁':Tyτ₂':Tyt₁':Tmt₂:Tmh₁:<{ ∅ ⊢ t₁' ⦂ τ₂' → τ₁' }>h₂:<{ ∅ ⊢ t₂ ⦂ τ₂' }>ih₁:∀ {t' : Tm}, t₁' ⟶ t' → ∅ = ∅ → <{ ∅ ⊢ t' ⦂ τ₂' → τ₁' }>ih₂:∀ {t' : Tm}, t₂ ⟶ t' → ∅ = ∅ → <{ ∅ ⊢ t' ⦂ τ₂' }>t₂'✝:Tma✝¹:t₁'.IsValuea✝:t₂ ⟶ t₂'✝⊢ Ty <;> app₂.h₁ t:Tmτ:TyΓ:Contextτ₁':Tyτ₂':Tyt₁':Tmt₂:Tmh₁:<{ ∅ ⊢ t₁' ⦂ τ₂' → τ₁' }>h₂:<{ ∅ ⊢ t₂ ⦂ τ₂' }>ih₁:∀ {t' : Tm}, t₁' ⟶ t' → ∅ = ∅ → <{ ∅ ⊢ t' ⦂ τ₂' → τ₁' }>ih₂:∀ {t' : Tm}, t₂ ⟶ t' → ∅ = ∅ → <{ ∅ ⊢ t' ⦂ τ₂' }>t₂'✝:Tma✝¹:t₁'.IsValuea✝:t₂ ⟶ t₂'✝⊢ <{ ∅ ⊢ t₁' ⦂ ~?app₂.τ₂ → τ₁' }>app₂.h₂ t:Tmτ:TyΓ:Contextτ₁':Tyτ₂':Tyt₁':Tmt₂:Tmh₁:<{ ∅ ⊢ t₁' ⦂ τ₂' → τ₁' }>h₂:<{ ∅ ⊢ t₂ ⦂ τ₂' }>ih₁:∀ {t' : Tm}, t₁' ⟶ t' → ∅ = ∅ → <{ ∅ ⊢ t' ⦂ τ₂' → τ₁' }>ih₂:∀ {t' : Tm}, t₂ ⟶ t' → ∅ = ∅ → <{ ∅ ⊢ t' ⦂ τ₂' }>t₂'✝:Tma✝¹:t₁'.IsValuea✝:t₂ ⟶ t₂'✝⊢ <{ ∅ ⊢ t₂'✝ ⦂ ~?app₂.τ₂ }>app₂.τ₂ t:Tmτ:TyΓ:Contextτ₁':Tyτ₂':Tyt₁':Tmt₂:Tmh₁:<{ ∅ ⊢ t₁' ⦂ τ₂' → τ₁' }>h₂:<{ ∅ ⊢ t₂ ⦂ τ₂' }>ih₁:∀ {t' : Tm}, t₁' ⟶ t' → ∅ = ∅ → <{ ∅ ⊢ t' ⦂ τ₂' → τ₁' }>ih₂:∀ {t' : Tm}, t₂ ⟶ t' → ∅ = ∅ → <{ ∅ ⊢ t' ⦂ τ₂' }>t₂'✝:Tma✝¹:t₁'.IsValuea✝:t₂ ⟶ t₂'✝⊢ Ty apply_rules All goals completed! 🐙; done))
| appAbs _ τ₂ t₁ h => appAbs t:Tmτ:TyΓ:Contextτ₁':Tyτ₂':Tyt₂:Tmh₂:<{ ∅ ⊢ t₂ ⦂ τ₂' }>ih₂:∀ {t' : Tm}, t₂ ⟶ t' → ∅ = ∅ → <{ ∅ ⊢ t' ⦂ τ₂' }>x✝:Stringτ₂:Tyt₁:Tmh₁:<{ ∅ ⊢ λ ~x✝ : τ₂ . t₁ ⦂ τ₂' → τ₁' }>ih₁:∀ {t' : Tm}, <{ λ ~x✝ : τ₂ . t₁ }> ⟶ t' → ∅ = ∅ → <{ ∅ ⊢ t' ⦂ τ₂' → τ₁' }>h:t₂.IsValue⊢ <{ ∅ ⊢ [~x✝ := t₂] t₁ ⦂ τ₁' }>
obtain ⟨h₁, h₂⟩ := abs_arrow h₁ appAbs t:Tmτ:TyΓ:Contextτ₁':Tyτ₂':Tyt₂:Tmh₂✝:<{ ∅ ⊢ t₂ ⦂ τ₂' }>ih₂:∀ {t' : Tm}, t₂ ⟶ t' → ∅ = ∅ → <{ ∅ ⊢ t' ⦂ τ₂' }>x✝:Stringτ₂:Tyt₁:Tmh₁✝:<{ ∅ ⊢ λ ~x✝ : τ₂ . t₁ ⦂ τ₂' → τ₁' }>ih₁:∀ {t' : Tm}, <{ λ ~x✝ : τ₂ . t₁ }> ⟶ t' → ∅ = ∅ → <{ ∅ ⊢ t' ⦂ τ₂' → τ₁' }>h:t₂.IsValueh₁:τ₂' <: τ₂h₂:<{ ~(x✝ →ₚ τ₂) ⊢ t₁ ⦂ τ₁' }>⊢ <{ ∅ ⊢ [~x✝ := t₂] t₁ ⦂ τ₁' }>
apply substitution_preserves_typing (τ₁:=τ₂) appAbs.ht t:Tmτ:TyΓ:Contextτ₁':Tyτ₂':Tyt₂:Tmh₂✝:<{ ∅ ⊢ t₂ ⦂ τ₂' }>ih₂:∀ {t' : Tm}, t₂ ⟶ t' → ∅ = ∅ → <{ ∅ ⊢ t' ⦂ τ₂' }>x✝:Stringτ₂:Tyt₁:Tmh₁✝:<{ ∅ ⊢ λ ~x✝ : τ₂ . t₁ ⦂ τ₂' → τ₁' }>ih₁:∀ {t' : Tm}, <{ λ ~x✝ : τ₂ . t₁ }> ⟶ t' → ∅ = ∅ → <{ ∅ ⊢ t' ⦂ τ₂' → τ₁' }>h:t₂.IsValueh₁:τ₂' <: τ₂h₂:<{ ~(x✝ →ₚ τ₂) ⊢ t₁ ⦂ τ₁' }>⊢ <{ ~(x✝ →ₚ τ₂) ⊢ t₁ ⦂ τ₁' }>appAbs.hv t:Tmτ:TyΓ:Contextτ₁':Tyτ₂':Tyt₂:Tmh₂✝:<{ ∅ ⊢ t₂ ⦂ τ₂' }>ih₂:∀ {t' : Tm}, t₂ ⟶ t' → ∅ = ∅ → <{ ∅ ⊢ t' ⦂ τ₂' }>x✝:Stringτ₂:Tyt₁:Tmh₁✝:<{ ∅ ⊢ λ ~x✝ : τ₂ . t₁ ⦂ τ₂' → τ₁' }>ih₁:∀ {t' : Tm}, <{ λ ~x✝ : τ₂ . t₁ }> ⟶ t' → ∅ = ∅ → <{ ∅ ⊢ t' ⦂ τ₂' → τ₁' }>h:t₂.IsValueh₁:τ₂' <: τ₂h₂:<{ ~(x✝ →ₚ τ₂) ⊢ t₁ ⦂ τ₁' }>⊢ <{ ∅ ⊢ t₂ ⦂ τ₂ }>
· appAbs.ht t:Tmτ:TyΓ:Contextτ₁':Tyτ₂':Tyt₂:Tmh₂✝:<{ ∅ ⊢ t₂ ⦂ τ₂' }>ih₂:∀ {t' : Tm}, t₂ ⟶ t' → ∅ = ∅ → <{ ∅ ⊢ t' ⦂ τ₂' }>x✝:Stringτ₂:Tyt₁:Tmh₁✝:<{ ∅ ⊢ λ ~x✝ : τ₂ . t₁ ⦂ τ₂' → τ₁' }>ih₁:∀ {t' : Tm}, <{ λ ~x✝ : τ₂ . t₁ }> ⟶ t' → ∅ = ∅ → <{ ∅ ⊢ t' ⦂ τ₂' → τ₁' }>h:t₂.IsValueh₁:τ₂' <: τ₂h₂:<{ ~(x✝ →ₚ τ₂) ⊢ t₁ ⦂ τ₁' }>⊢ <{ ~(x✝ →ₚ τ₂) ⊢ t₁ ⦂ τ₁' }> assumption All goals completed! 🐙
· appAbs.hv t:Tmτ:TyΓ:Contextτ₁':Tyτ₂':Tyt₂:Tmh₂✝:<{ ∅ ⊢ t₂ ⦂ τ₂' }>ih₂:∀ {t' : Tm}, t₂ ⟶ t' → ∅ = ∅ → <{ ∅ ⊢ t' ⦂ τ₂' }>x✝:Stringτ₂:Tyt₁:Tmh₁✝:<{ ∅ ⊢ λ ~x✝ : τ₂ . t₁ ⦂ τ₂' → τ₁' }>ih₁:∀ {t' : Tm}, <{ λ ~x✝ : τ₂ . t₁ }> ⟶ t' → ∅ = ∅ → <{ ∅ ⊢ t' ⦂ τ₂' → τ₁' }>h:t₂.IsValueh₁:τ₂' <: τ₂h₂:<{ ~(x✝ →ₚ τ₂) ⊢ t₁ ⦂ τ₁' }>⊢ <{ ∅ ⊢ t₂ ⦂ τ₂ }> apply HasType.sub appAbs.hv.ht t:Tmτ:TyΓ:Contextτ₁':Tyτ₂':Tyt₂:Tmh₂✝:<{ ∅ ⊢ t₂ ⦂ τ₂' }>ih₂:∀ {t' : Tm}, t₂ ⟶ t' → ∅ = ∅ → <{ ∅ ⊢ t' ⦂ τ₂' }>x✝:Stringτ₂:Tyt₁:Tmh₁✝:<{ ∅ ⊢ λ ~x✝ : τ₂ . t₁ ⦂ τ₂' → τ₁' }>ih₁:∀ {t' : Tm}, <{ λ ~x✝ : τ₂ . t₁ }> ⟶ t' → ∅ = ∅ → <{ ∅ ⊢ t' ⦂ τ₂' → τ₁' }>h:t₂.IsValueh₁:τ₂' <: τ₂h₂:<{ ~(x✝ →ₚ τ₂) ⊢ t₁ ⦂ τ₁' }>⊢ <{ ∅ ⊢ t₂ ⦂ ~?appAbs.hv.τ₁ }>appAbs.hv.hs t:Tmτ:TyΓ:Contextτ₁':Tyτ₂':Tyt₂:Tmh₂✝:<{ ∅ ⊢ t₂ ⦂ τ₂' }>ih₂:∀ {t' : Tm}, t₂ ⟶ t' → ∅ = ∅ → <{ ∅ ⊢ t' ⦂ τ₂' }>x✝:Stringτ₂:Tyt₁:Tmh₁✝:<{ ∅ ⊢ λ ~x✝ : τ₂ . t₁ ⦂ τ₂' → τ₁' }>ih₁:∀ {t' : Tm}, <{ λ ~x✝ : τ₂ . t₁ }> ⟶ t' → ∅ = ∅ → <{ ∅ ⊢ t' ⦂ τ₂' → τ₁' }>h:t₂.IsValueh₁:τ₂' <: τ₂h₂:<{ ~(x✝ →ₚ τ₂) ⊢ t₁ ⦂ τ₁' }>⊢ ?appAbs.hv.τ₁ <: τ₂appAbs.hv.τ₁ t:Tmτ:TyΓ:Contextτ₁':Tyτ₂':Tyt₂:Tmh₂✝:<{ ∅ ⊢ t₂ ⦂ τ₂' }>ih₂:∀ {t' : Tm}, t₂ ⟶ t' → ∅ = ∅ → <{ ∅ ⊢ t' ⦂ τ₂' }>x✝:Stringτ₂:Tyt₁:Tmh₁✝:<{ ∅ ⊢ λ ~x✝ : τ₂ . t₁ ⦂ τ₂' → τ₁' }>ih₁:∀ {t' : Tm}, <{ λ ~x✝ : τ₂ . t₁ }> ⟶ t' → ∅ = ∅ → <{ ∅ ⊢ t' ⦂ τ₂' → τ₁' }>h:t₂.IsValueh₁:τ₂' <: τ₂h₂:<{ ~(x✝ →ₚ τ₂) ⊢ t₁ ⦂ τ₁' }>⊢ Ty <;> appAbs.hv.ht t:Tmτ:TyΓ:Contextτ₁':Tyτ₂':Tyt₂:Tmh₂✝:<{ ∅ ⊢ t₂ ⦂ τ₂' }>ih₂:∀ {t' : Tm}, t₂ ⟶ t' → ∅ = ∅ → <{ ∅ ⊢ t' ⦂ τ₂' }>x✝:Stringτ₂:Tyt₁:Tmh₁✝:<{ ∅ ⊢ λ ~x✝ : τ₂ . t₁ ⦂ τ₂' → τ₁' }>ih₁:∀ {t' : Tm}, <{ λ ~x✝ : τ₂ . t₁ }> ⟶ t' → ∅ = ∅ → <{ ∅ ⊢ t' ⦂ τ₂' → τ₁' }>h:t₂.IsValueh₁:τ₂' <: τ₂h₂:<{ ~(x✝ →ₚ τ₂) ⊢ t₁ ⦂ τ₁' }>⊢ <{ ∅ ⊢ t₂ ⦂ ~?appAbs.hv.τ₁ }>appAbs.hv.hs t:Tmτ:TyΓ:Contextτ₁':Tyτ₂':Tyt₂:Tmh₂✝:<{ ∅ ⊢ t₂ ⦂ τ₂' }>ih₂:∀ {t' : Tm}, t₂ ⟶ t' → ∅ = ∅ → <{ ∅ ⊢ t' ⦂ τ₂' }>x✝:Stringτ₂:Tyt₁:Tmh₁✝:<{ ∅ ⊢ λ ~x✝ : τ₂ . t₁ ⦂ τ₂' → τ₁' }>ih₁:∀ {t' : Tm}, <{ λ ~x✝ : τ₂ . t₁ }> ⟶ t' → ∅ = ∅ → <{ ∅ ⊢ t' ⦂ τ₂' → τ₁' }>h:t₂.IsValueh₁:τ₂' <: τ₂h₂:<{ ~(x✝ →ₚ τ₂) ⊢ t₁ ⦂ τ₁' }>⊢ ?appAbs.hv.τ₁ <: τ₂appAbs.hv.τ₁ t:Tmτ:TyΓ:Contextτ₁':Tyτ₂':Tyt₂:Tmh₂✝:<{ ∅ ⊢ t₂ ⦂ τ₂' }>ih₂:∀ {t' : Tm}, t₂ ⟶ t' → ∅ = ∅ → <{ ∅ ⊢ t' ⦂ τ₂' }>x✝:Stringτ₂:Tyt₁:Tmh₁✝:<{ ∅ ⊢ λ ~x✝ : τ₂ . t₁ ⦂ τ₂' → τ₁' }>ih₁:∀ {t' : Tm}, <{ λ ~x✝ : τ₂ . t₁ }> ⟶ t' → ∅ = ∅ → <{ ∅ ⊢ t' ⦂ τ₂' → τ₁' }>h:t₂.IsValueh₁:τ₂' <: τ₂h₂:<{ ~(x✝ →ₚ τ₂) ⊢ t₁ ⦂ τ₁' }>⊢ Ty apply_rules using StlcSubTyping All goals completed! 🐙
| ite Γ t₁ t₂ t₃ τ h₁ h₂ h₃ ih₁ ih₂ ih₃ => ite t:Tmτ✝:TyΓ:Contextt₁:Tmt₂:Tmt₃:Tmτ:Tyt':Tmhs:<{ if t₁ then t₂ else t₃ }> ⟶ t'h₁:<{ ∅ ⊢ t₁ ⦂ Bool }>h₂:<{ ∅ ⊢ t₂ ⦂ τ }>h₃:<{ ∅ ⊢ t₃ ⦂ τ }>ih₁:∀ {t' : Tm}, t₁ ⟶ t' → ∅ = ∅ → <{ ∅ ⊢ t' ⦂ Bool }>ih₂:∀ {t' : Tm}, t₂ ⟶ t' → ∅ = ∅ → <{ ∅ ⊢ t' ⦂ τ }>ih₃:∀ {t' : Tm}, t₃ ⟶ t' → ∅ = ∅ → <{ ∅ ⊢ t' ⦂ τ }>⊢ <{ ∅ ⊢ t' ⦂ τ }>
inversion hs with (try (constructor ifFalse.ht t:Tmτ✝:TyΓ:Contextt₂:Tmt₃:Tmτ:Tyh₂:<{ ∅ ⊢ t₂ ⦂ τ }>h₃:<{ ∅ ⊢ t₃ ⦂ τ }>ih₂:∀ {t' : Tm}, t₂ ⟶ t' → ∅ = ∅ → <{ ∅ ⊢ t' ⦂ τ }>ih₃:∀ {t' : Tm}, t₃ ⟶ t' → ∅ = ∅ → <{ ∅ ⊢ t' ⦂ τ }>h₁:<{ ∅ ⊢ false ⦂ Bool }>ih₁:∀ {t' : Tm}, <{ false }> ⟶ t' → ∅ = ∅ → <{ ∅ ⊢ t' ⦂ Bool }>⊢ <{ ∅ ⊢ t₃ ⦂ ~?ifFalse.τ₁ }>ifFalse.hs t:Tmτ✝:TyΓ:Contextt₂:Tmt₃:Tmτ:Tyh₂:<{ ∅ ⊢ t₂ ⦂ τ }>h₃:<{ ∅ ⊢ t₃ ⦂ τ }>ih₂:∀ {t' : Tm}, t₂ ⟶ t' → ∅ = ∅ → <{ ∅ ⊢ t' ⦂ τ }>ih₃:∀ {t' : Tm}, t₃ ⟶ t' → ∅ = ∅ → <{ ∅ ⊢ t' ⦂ τ }>h₁:<{ ∅ ⊢ false ⦂ Bool }>ih₁:∀ {t' : Tm}, <{ false }> ⟶ t' → ∅ = ∅ → <{ ∅ ⊢ t' ⦂ Bool }>⊢ ?ifFalse.τ₁ <: τifFalse.τ₁ t:Tmτ✝:TyΓ:Contextt₂:Tmt₃:Tmτ:Tyh₂:<{ ∅ ⊢ t₂ ⦂ τ }>h₃:<{ ∅ ⊢ t₃ ⦂ τ }>ih₂:∀ {t' : Tm}, t₂ ⟶ t' → ∅ = ∅ → <{ ∅ ⊢ t' ⦂ τ }>ih₃:∀ {t' : Tm}, t₃ ⟶ t' → ∅ = ∅ → <{ ∅ ⊢ t' ⦂ τ }>h₁:<{ ∅ ⊢ false ⦂ Bool }>ih₁:∀ {t' : Tm}, <{ false }> ⟶ t' → ∅ = ∅ → <{ ∅ ⊢ t' ⦂ Bool }>⊢ Ty <;> ifFalse.ht t:Tmτ✝:TyΓ:Contextt₂:Tmt₃:Tmτ:Tyh₂:<{ ∅ ⊢ t₂ ⦂ τ }>h₃:<{ ∅ ⊢ t₃ ⦂ τ }>ih₂:∀ {t' : Tm}, t₂ ⟶ t' → ∅ = ∅ → <{ ∅ ⊢ t' ⦂ τ }>ih₃:∀ {t' : Tm}, t₃ ⟶ t' → ∅ = ∅ → <{ ∅ ⊢ t' ⦂ τ }>h₁:<{ ∅ ⊢ false ⦂ Bool }>ih₁:∀ {t' : Tm}, <{ false }> ⟶ t' → ∅ = ∅ → <{ ∅ ⊢ t' ⦂ Bool }>⊢ <{ ∅ ⊢ t₃ ⦂ ~?ifFalse.τ₁ }>ifFalse.hs t:Tmτ✝:TyΓ:Contextt₂:Tmt₃:Tmτ:Tyh₂:<{ ∅ ⊢ t₂ ⦂ τ }>h₃:<{ ∅ ⊢ t₃ ⦂ τ }>ih₂:∀ {t' : Tm}, t₂ ⟶ t' → ∅ = ∅ → <{ ∅ ⊢ t' ⦂ τ }>ih₃:∀ {t' : Tm}, t₃ ⟶ t' → ∅ = ∅ → <{ ∅ ⊢ t' ⦂ τ }>h₁:<{ ∅ ⊢ false ⦂ Bool }>ih₁:∀ {t' : Tm}, <{ false }> ⟶ t' → ∅ = ∅ → <{ ∅ ⊢ t' ⦂ Bool }>⊢ ?ifFalse.τ₁ <: τifFalse.τ₁ t:Tmτ✝:TyΓ:Contextt₂:Tmt₃:Tmτ:Tyh₂:<{ ∅ ⊢ t₂ ⦂ τ }>h₃:<{ ∅ ⊢ t₃ ⦂ τ }>ih₂:∀ {t' : Tm}, t₂ ⟶ t' → ∅ = ∅ → <{ ∅ ⊢ t' ⦂ τ }>ih₃:∀ {t' : Tm}, t₃ ⟶ t' → ∅ = ∅ → <{ ∅ ⊢ t' ⦂ τ }>h₁:<{ ∅ ⊢ false ⦂ Bool }>ih₁:∀ {t' : Tm}, <{ false }> ⟶ t' → ∅ = ∅ → <{ ∅ ⊢ t' ⦂ Bool }>⊢ Ty solve_by_elim using StlcSubEval All goals completed! 🐙))
| sub Γ t₁ τ₁ τ₂ ht hs ih => sub t:Tmτ:TyΓ:Contextt₁:Tmτ₁:Tyτ₂:Tyhs✝:τ₁ <: τ₂t':Tmhs:t₁ ⟶ t'ht:<{ ∅ ⊢ t₁ ⦂ τ₁ }>ih:∀ {t' : Tm}, t₁ ⟶ t' → ∅ = ∅ → <{ ∅ ⊢ t' ⦂ τ₁ }>⊢ <{ ∅ ⊢ t' ⦂ τ₂ }>
apply HasType.sub sub.ht t:Tmτ:TyΓ:Contextt₁:Tmτ₁:Tyτ₂:Tyhs✝:τ₁ <: τ₂t':Tmhs:t₁ ⟶ t'ht:<{ ∅ ⊢ t₁ ⦂ τ₁ }>ih:∀ {t' : Tm}, t₁ ⟶ t' → ∅ = ∅ → <{ ∅ ⊢ t' ⦂ τ₁ }>⊢ <{ ∅ ⊢ t' ⦂ ~?sub.τ₁ }>sub.hs t:Tmτ:TyΓ:Contextt₁:Tmτ₁:Tyτ₂:Tyhs✝:τ₁ <: τ₂t':Tmhs:t₁ ⟶ t'ht:<{ ∅ ⊢ t₁ ⦂ τ₁ }>ih:∀ {t' : Tm}, t₁ ⟶ t' → ∅ = ∅ → <{ ∅ ⊢ t' ⦂ τ₁ }>⊢ ?sub.τ₁ <: τ₂sub.τ₁ t:Tmτ:TyΓ:Contextt₁:Tmτ₁:Tyτ₂:Tyhs✝:τ₁ <: τ₂t':Tmhs:t₁ ⟶ t'ht:<{ ∅ ⊢ t₁ ⦂ τ₁ }>ih:∀ {t' : Tm}, t₁ ⟶ t' → ∅ = ∅ → <{ ∅ ⊢ t' ⦂ τ₁ }>⊢ Ty <;> sub.ht t:Tmτ:TyΓ:Contextt₁:Tmτ₁:Tyτ₂:Tyhs✝:τ₁ <: τ₂t':Tmhs:t₁ ⟶ t'ht:<{ ∅ ⊢ t₁ ⦂ τ₁ }>ih:∀ {t' : Tm}, t₁ ⟶ t' → ∅ = ∅ → <{ ∅ ⊢ t' ⦂ τ₁ }>⊢ <{ ∅ ⊢ t' ⦂ ~?sub.τ₁ }>sub.hs t:Tmτ:TyΓ:Contextt₁:Tmτ₁:Tyτ₂:Tyhs✝:τ₁ <: τ₂t':Tmhs:t₁ ⟶ t'ht:<{ ∅ ⊢ t₁ ⦂ τ₁ }>ih:∀ {t' : Tm}, t₁ ⟶ t' → ∅ = ∅ → <{ ∅ ⊢ t' ⦂ τ₁ }>⊢ ?sub.τ₁ <: τ₂sub.τ₁ t:Tmτ:TyΓ:Contextt₁:Tmτ₁:Tyτ₂:Tyhs✝:τ₁ <: τ₂t':Tmhs:t₁ ⟶ t'ht:<{ ∅ ⊢ t₁ ⦂ τ₁ }>ih:∀ {t' : Tm}, t₁ ⟶ t' → ∅ = ∅ → <{ ∅ ⊢ t' ⦂ τ₁ }>⊢ Ty solve_by_elim using StlcSubTyping All goals completed! 🐙
-- FILL IN HERE
8.3.7.1. Exercise: Adding Products
8.3.8. Formalized "Thought Exercises"
end StlcSub