< Module walkthrough:let.
< Prove walkthrough:host:typeOf_unique.
Subgoal 4:
Variables: Ctx TyA TyB Ty1 T2 T1 X
IH : forall Ctx T TyA TyB, typeOf Ctx T TyA * -> typeOf Ctx T TyB -> TyA = TyB
TyA : typeOf Ctx (let X T1 T2) TyA @
TyB : typeOf Ctx (let X T1 T2) TyB
TyA1 : typeOf Ctx T1 Ty1 *
TyA2 : typeOf ((X, Ty1)::Ctx) T2 TyA *
============================
TyA = TyB
< TyB: case TyB.
Subgoal 4:
Variables: Ctx TyA TyB Ty1 T2 T1 X Ty2
IH : forall Ctx T TyA TyB, typeOf Ctx T TyA * -> typeOf Ctx T TyB -> TyA = TyB
TyA : typeOf Ctx (let X T1 T2) TyA @
TyA1 : typeOf Ctx T1 Ty1 *
TyA2 : typeOf ((X, Ty1)::Ctx) T2 TyA *
TyB : typeOf Ctx T1 Ty2
TyB1 : typeOf ((X, Ty2)::Ctx) T2 TyB
============================
TyA = TyB
< apply IH to TyA1 TyB.
Subgoal 4:
Variables: Ctx TyA TyB T2 T1 X Ty2
IH : forall Ctx T TyA TyB, typeOf Ctx T TyA * -> typeOf Ctx T TyB -> TyA = TyB
TyA : typeOf Ctx (let X T1 T2) TyA @
TyA1 : typeOf Ctx T1 Ty2 *
TyA2 : typeOf ((X, Ty2)::Ctx) T2 TyA *
TyB : typeOf Ctx T1 Ty2
TyB1 : typeOf ((X, Ty2)::Ctx) T2 TyB
============================
TyA = TyB
< apply IH to TyA2 TyB1.
Subgoal 4:
Variables: Ctx TyB T2 T1 X Ty2
IH : forall Ctx T TyA TyB, typeOf Ctx T TyA * -> typeOf Ctx T TyB -> TyA = TyB
TyA : typeOf Ctx (let X T1 T2) TyB @
TyA1 : typeOf Ctx T1 Ty2 *
TyA2 : typeOf ((X, Ty2)::Ctx) T2 TyB *
TyB : typeOf Ctx T1 Ty2
TyB1 : typeOf ((X, Ty2)::Ctx) T2 TyB
============================
TyB = TyB
< search.
Proof completed.
< Prove walkthrough:host:ty_lookup.
Subgoal 4:
Variables: Ctx1 Ctx2 Ty Ty1 T2 T1 X
IH : forall Ctx1 Ctx2 T Ty,
typeOf Ctx1 T Ty * -> (forall X XTy,
lookup Ctx1 X XTy -> lookup Ctx2 X XTy) -> typeOf Ctx2 T Ty
Ty : typeOf Ctx1 (let X T1 T2) Ty @
L : forall X XTy, lookup Ctx1 X XTy -> lookup Ctx2 X XTy
Ty1 : typeOf Ctx1 T1 Ty1 *
Ty2 : typeOf ((X, Ty1)::Ctx1) T2 Ty *
============================
typeOf Ctx2 (let X T1 T2) Ty
< apply IH to Ty1 L.
Subgoal 4:
Variables: Ctx1 Ctx2 Ty Ty1 T2 T1 X
IH : forall Ctx1 Ctx2 T Ty,
typeOf Ctx1 T Ty * -> (forall X XTy,
lookup Ctx1 X XTy -> lookup Ctx2 X XTy) -> typeOf Ctx2 T Ty
Ty : typeOf Ctx1 (let X T1 T2) Ty @
L : forall X XTy, lookup Ctx1 X XTy -> lookup Ctx2 X XTy
Ty1 : typeOf Ctx1 T1 Ty1 *
Ty2 : typeOf ((X, Ty1)::Ctx1) T2 Ty *
H1 : typeOf Ctx2 T1 Ty1
============================
typeOf Ctx2 (let X T1 T2) Ty
< apply IH to Ty2 _ with
Ctx2 = (X, Ty1)::Ctx2.
Subgoal 4.1:
Variables: Ctx1 Ctx2 Ty Ty1 T2 T1 X
IH : forall Ctx1 Ctx2 T Ty,
typeOf Ctx1 T Ty * -> (forall X XTy,
lookup Ctx1 X XTy -> lookup Ctx2 X XTy) -> typeOf Ctx2 T Ty
Ty : typeOf Ctx1 (let X T1 T2) Ty @
L : forall X XTy, lookup Ctx1 X XTy -> lookup Ctx2 X XTy
Ty1 : typeOf Ctx1 T1 Ty1 *
Ty2 : typeOf ((X, Ty1)::Ctx1) T2 Ty *
H1 : typeOf Ctx2 T1 Ty1
============================
forall X1 XTy, lookup ((X, Ty1)::Ctx1) X1 XTy -> lookup ((X, Ty1)::Ctx2) X1 XTy
< intros Lkp.
Subgoal 4.1:
Variables: Ctx1 Ctx2 Ty Ty1 T2 T1 X X1 XTy
IH : forall Ctx1 Ctx2 T Ty,
typeOf Ctx1 T Ty * -> (forall X XTy,
lookup Ctx1 X XTy -> lookup Ctx2 X XTy) -> typeOf Ctx2 T Ty
Ty : typeOf Ctx1 (let X T1 T2) Ty @
L : forall X XTy, lookup Ctx1 X XTy -> lookup Ctx2 X XTy
Ty1 : typeOf Ctx1 T1 Ty1 *
Ty2 : typeOf ((X, Ty1)::Ctx1) T2 Ty *
H1 : typeOf Ctx2 T1 Ty1
Lkp : lookup ((X, Ty1)::Ctx1) X1 XTy
============================
lookup ((X, Ty1)::Ctx2) X1 XTy
< Lkp: case Lkp.
Subgoal 4.1.1:
Variables: Ctx1 Ctx2 Ty T2 T1 X1 XTy
IH : forall Ctx1 Ctx2 T Ty,
typeOf Ctx1 T Ty * -> (forall X XTy,
lookup Ctx1 X XTy -> lookup Ctx2 X XTy) -> typeOf Ctx2 T Ty
Ty : typeOf Ctx1 (let X1 T1 T2) Ty @
L : forall X XTy, lookup Ctx1 X XTy -> lookup Ctx2 X XTy
Ty1 : typeOf Ctx1 T1 XTy *
Ty2 : typeOf ((X1, XTy)::Ctx1) T2 Ty *
H1 : typeOf Ctx2 T1 XTy
============================
lookup ((X1, XTy)::Ctx2) X1 XTy
< search.
Subgoal 4.1.2:
Variables: Ctx1 Ctx2 Ty Ty1 T2 T1 X X1 XTy
IH : forall Ctx1 Ctx2 T Ty,
typeOf Ctx1 T Ty * -> (forall X XTy,
lookup Ctx1 X XTy -> lookup Ctx2 X XTy) -> typeOf Ctx2 T Ty
Ty : typeOf Ctx1 (let X T1 T2) Ty @
L : forall X XTy, lookup Ctx1 X XTy -> lookup Ctx2 X XTy
Ty1 : typeOf Ctx1 T1 Ty1 *
Ty2 : typeOf ((X, Ty1)::Ctx1) T2 Ty *
H1 : typeOf Ctx2 T1 Ty1
Lkp : X = X1 -> false
Lkp1 : lookup Ctx1 X1 XTy
============================
lookup ((X, Ty1)::Ctx2) X1 XTy
< apply L to Lkp1.
Subgoal 4.1.2:
Variables: Ctx1 Ctx2 Ty Ty1 T2 T1 X X1 XTy
IH : forall Ctx1 Ctx2 T Ty,
typeOf Ctx1 T Ty * -> (forall X XTy,
lookup Ctx1 X XTy -> lookup Ctx2 X XTy) -> typeOf Ctx2 T Ty
Ty : typeOf Ctx1 (let X T1 T2) Ty @
L : forall X XTy, lookup Ctx1 X XTy -> lookup Ctx2 X XTy
Ty1 : typeOf Ctx1 T1 Ty1 *
Ty2 : typeOf ((X, Ty1)::Ctx1) T2 Ty *
H1 : typeOf Ctx2 T1 Ty1
Lkp : X = X1 -> false
Lkp1 : lookup Ctx1 X1 XTy
H2 : lookup Ctx2 X1 XTy
============================
lookup ((X, Ty1)::Ctx2) X1 XTy
< search.
Subgoal 4:
Variables: Ctx1 Ctx2 Ty Ty1 T2 T1 X
IH : forall Ctx1 Ctx2 T Ty,
typeOf Ctx1 T Ty * -> (forall X XTy,
lookup Ctx1 X XTy -> lookup Ctx2 X XTy) -> typeOf Ctx2 T Ty
Ty : typeOf Ctx1 (let X T1 T2) Ty @
L : forall X XTy, lookup Ctx1 X XTy -> lookup Ctx2 X XTy
Ty1 : typeOf Ctx1 T1 Ty1 *
Ty2 : typeOf ((X, Ty1)::Ctx1) T2 Ty *
H1 : typeOf Ctx2 T1 Ty1
H2 : typeOf ((X, Ty1)::Ctx2) T2 Ty
============================
typeOf Ctx2 (let X T1 T2) Ty
< search.
Proof completed.
< Prove walkthrough:host:subst_type_preservation.
Subgoal 6:
Variables: Ctx X XTy Ty R S2 S1 Y T2 T1
IH : forall T Ctx X XTy Ty R S,
typeOf ((X, XTy)::Ctx) T Ty -> subst X R T S * -> typeOf [] R XTy -> typeOf Ctx S Ty
TTy : typeOf ((X, XTy)::Ctx) (let Y T1 T2) Ty
S : subst X R (let Y T1 T2) (let Y S1 S2) @
RTy : typeOf [] R XTy
S1 : X = Y -> false
S2 : subst X R T1 S1 *
S3 : subst X R T2 S2 *
============================
typeOf Ctx (let Y S1 S2) Ty
< Ty: case TTy.
Subgoal 6:
Variables: Ctx X XTy Ty R S2 S1 Y T2 T1 Ty1
IH : forall T Ctx X XTy Ty R S,
typeOf ((X, XTy)::Ctx) T Ty -> subst X R T S * -> typeOf [] R XTy -> typeOf Ctx S Ty
S : subst X R (let Y T1 T2) (let Y S1 S2) @
RTy : typeOf [] R XTy
S1 : X = Y -> false
S2 : subst X R T1 S1 *
S3 : subst X R T2 S2 *
Ty : typeOf ((X, XTy)::Ctx) T1 Ty1
Ty1 : typeOf ((Y, Ty1)::((X, XTy)::Ctx)) T2 Ty
============================
typeOf Ctx (let Y S1 S2) Ty
< apply IH to Ty S2 RTy.
Subgoal 6:
Variables: Ctx X XTy Ty R S2 S1 Y T2 T1 Ty1
IH : forall T Ctx X XTy Ty R S,
typeOf ((X, XTy)::Ctx) T Ty -> subst X R T S * -> typeOf [] R XTy -> typeOf Ctx S Ty
S : subst X R (let Y T1 T2) (let Y S1 S2) @
RTy : typeOf [] R XTy
S1 : X = Y -> false
S2 : subst X R T1 S1 *
S3 : subst X R T2 S2 *
Ty : typeOf ((X, XTy)::Ctx) T1 Ty1
Ty1 : typeOf ((Y, Ty1)::((X, XTy)::Ctx)) T2 Ty
H1 : typeOf Ctx S1 Ty1
============================
typeOf Ctx (let Y S1 S2) Ty
< Ty': apply ty_lookup to Ty1 _ with
Ctx2 = (X, XTy)::((Y, Ty1)::Ctx).
Subgoal 6.1:
Variables: Ctx X XTy Ty R S2 S1 Y T2 T1 Ty1
IH : forall T Ctx X XTy Ty R S,
typeOf ((X, XTy)::Ctx) T Ty -> subst X R T S * -> typeOf [] R XTy -> typeOf Ctx S Ty
S : subst X R (let Y T1 T2) (let Y S1 S2) @
RTy : typeOf [] R XTy
S1 : X = Y -> false
S2 : subst X R T1 S1 *
S3 : subst X R T2 S2 *
Ty : typeOf ((X, XTy)::Ctx) T1 Ty1
Ty1 : typeOf ((Y, Ty1)::((X, XTy)::Ctx)) T2 Ty
H1 : typeOf Ctx S1 Ty1
============================
forall X1 XTy1,
lookup ((Y, Ty1)::((X, XTy)::Ctx)) X1 XTy1 -> lookup ((X, XTy)::((Y, Ty1)::Ctx)) X1 XTy1
< intros L.
Subgoal 6.1:
Variables: Ctx X XTy Ty R S2 S1 Y T2 T1 Ty1 X1 XTy1
IH : forall T Ctx X XTy Ty R S,
typeOf ((X, XTy)::Ctx) T Ty -> subst X R T S * -> typeOf [] R XTy -> typeOf Ctx S Ty
S : subst X R (let Y T1 T2) (let Y S1 S2) @
RTy : typeOf [] R XTy
S1 : X = Y -> false
S2 : subst X R T1 S1 *
S3 : subst X R T2 S2 *
Ty : typeOf ((X, XTy)::Ctx) T1 Ty1
Ty1 : typeOf ((Y, Ty1)::((X, XTy)::Ctx)) T2 Ty
H1 : typeOf Ctx S1 Ty1
L : lookup ((Y, Ty1)::((X, XTy)::Ctx)) X1 XTy1
============================
lookup ((X, XTy)::((Y, Ty1)::Ctx)) X1 XTy1
< L: case L.
Subgoal 6.1.1:
Variables: Ctx X XTy Ty R S2 S1 T2 T1 X1 XTy1
IH : forall T Ctx X XTy Ty R S,
typeOf ((X, XTy)::Ctx) T Ty -> subst X R T S * -> typeOf [] R XTy -> typeOf Ctx S Ty
S : subst X R (let X1 T1 T2) (let X1 S1 S2) @
RTy : typeOf [] R XTy
S1 : X = X1 -> false
S2 : subst X R T1 S1 *
S3 : subst X R T2 S2 *
Ty : typeOf ((X, XTy)::Ctx) T1 XTy1
Ty1 : typeOf ((X1, XTy1)::((X, XTy)::Ctx)) T2 Ty
H1 : typeOf Ctx S1 XTy1
============================
lookup ((X, XTy)::((X1, XTy1)::Ctx)) X1 XTy1
< search.
Subgoal 6.1.2:
Variables: Ctx X XTy Ty R S2 S1 Y T2 T1 Ty1 X1 XTy1
IH : forall T Ctx X XTy Ty R S,
typeOf ((X, XTy)::Ctx) T Ty -> subst X R T S * -> typeOf [] R XTy -> typeOf Ctx S Ty
S : subst X R (let Y T1 T2) (let Y S1 S2) @
RTy : typeOf [] R XTy
S1 : X = Y -> false
S2 : subst X R T1 S1 *
S3 : subst X R T2 S2 *
Ty : typeOf ((X, XTy)::Ctx) T1 Ty1
Ty1 : typeOf ((Y, Ty1)::((X, XTy)::Ctx)) T2 Ty
H1 : typeOf Ctx S1 Ty1
L : Y = X1 -> false
L1 : lookup ((X, XTy)::Ctx) X1 XTy1
============================
lookup ((X, XTy)::((Y, Ty1)::Ctx)) X1 XTy1
< L: case L1.
Subgoal 6.1.2.1:
Variables: Ctx Ty R S2 S1 Y T2 T1 Ty1 X1 XTy1
IH : forall T Ctx X XTy Ty R S,
typeOf ((X, XTy)::Ctx) T Ty -> subst X R T S * -> typeOf [] R XTy -> typeOf Ctx S Ty
S : subst X1 R (let Y T1 T2) (let Y S1 S2) @
RTy : typeOf [] R XTy1
S1 : X1 = Y -> false
S2 : subst X1 R T1 S1 *
S3 : subst X1 R T2 S2 *
Ty : typeOf ((X1, XTy1)::Ctx) T1 Ty1
Ty1 : typeOf ((Y, Ty1)::((X1, XTy1)::Ctx)) T2 Ty
H1 : typeOf Ctx S1 Ty1
L : Y = X1 -> false
============================
lookup ((X1, XTy1)::((Y, Ty1)::Ctx)) X1 XTy1
< search.
Subgoal 6.1.2.2:
Variables: Ctx X XTy Ty R S2 S1 Y T2 T1 Ty1 X1 XTy1
IH : forall T Ctx X XTy Ty R S,
typeOf ((X, XTy)::Ctx) T Ty -> subst X R T S * -> typeOf [] R XTy -> typeOf Ctx S Ty
S : subst X R (let Y T1 T2) (let Y S1 S2) @
RTy : typeOf [] R XTy
S1 : X = Y -> false
S2 : subst X R T1 S1 *
S3 : subst X R T2 S2 *
Ty : typeOf ((X, XTy)::Ctx) T1 Ty1
Ty1 : typeOf ((Y, Ty1)::((X, XTy)::Ctx)) T2 Ty
H1 : typeOf Ctx S1 Ty1
L : Y = X1 -> false
L1 : X = X1 -> false
L2 : lookup Ctx X1 XTy1
============================
lookup ((X, XTy)::((Y, Ty1)::Ctx)) X1 XTy1
< search.
Subgoal 6:
Variables: Ctx X XTy Ty R S2 S1 Y T2 T1 Ty1
IH : forall T Ctx X XTy Ty R S,
typeOf ((X, XTy)::Ctx) T Ty -> subst X R T S * -> typeOf [] R XTy -> typeOf Ctx S Ty
S : subst X R (let Y T1 T2) (let Y S1 S2) @
RTy : typeOf [] R XTy
S1 : X = Y -> false
S2 : subst X R T1 S1 *
S3 : subst X R T2 S2 *
Ty : typeOf ((X, XTy)::Ctx) T1 Ty1
Ty1 : typeOf ((Y, Ty1)::((X, XTy)::Ctx)) T2 Ty
H1 : typeOf Ctx S1 Ty1
Ty' : typeOf ((X, XTy)::((Y, Ty1)::Ctx)) T2 Ty
============================
typeOf Ctx (let Y S1 S2) Ty
< apply IH to Ty' S3 RTy.
Subgoal 6:
Variables: Ctx X XTy Ty R S2 S1 Y T2 T1 Ty1
IH : forall T Ctx X XTy Ty R S,
typeOf ((X, XTy)::Ctx) T Ty -> subst X R T S * -> typeOf [] R XTy -> typeOf Ctx S Ty
S : subst X R (let Y T1 T2) (let Y S1 S2) @
RTy : typeOf [] R XTy
S1 : X = Y -> false
S2 : subst X R T1 S1 *
S3 : subst X R T2 S2 *
Ty : typeOf ((X, XTy)::Ctx) T1 Ty1
Ty1 : typeOf ((Y, Ty1)::((X, XTy)::Ctx)) T2 Ty
H1 : typeOf Ctx S1 Ty1
Ty' : typeOf ((X, XTy)::((Y, Ty1)::Ctx)) T2 Ty
H2 : typeOf ((Y, Ty1)::Ctx) S2 Ty
============================
typeOf Ctx (let Y S1 S2) Ty
< search.
Subgoal 7:
Variables: Ctx X XTy Ty R T2 S1 T1
IH : forall T Ctx X XTy Ty R S,
typeOf ((X, XTy)::Ctx) T Ty -> subst X R T S * -> typeOf [] R XTy -> typeOf Ctx S Ty
TTy : typeOf ((X, XTy)::Ctx) (let X T1 T2) Ty
S : subst X R (let X T1 T2) (let X S1 T2) @
RTy : typeOf [] R XTy
S1 : subst X R T1 S1 *
============================
typeOf Ctx (let X S1 T2) Ty
< Ty: case TTy.
Subgoal 7:
Variables: Ctx X XTy Ty R T2 S1 T1 Ty1
IH : forall T Ctx X XTy Ty R S,
typeOf ((X, XTy)::Ctx) T Ty -> subst X R T S * -> typeOf [] R XTy -> typeOf Ctx S Ty
S : subst X R (let X T1 T2) (let X S1 T2) @
RTy : typeOf [] R XTy
S1 : subst X R T1 S1 *
Ty : typeOf ((X, XTy)::Ctx) T1 Ty1
Ty1 : typeOf ((X, Ty1)::((X, XTy)::Ctx)) T2 Ty
============================
typeOf Ctx (let X S1 T2) Ty
< apply IH to Ty S1 RTy.
Subgoal 7:
Variables: Ctx X XTy Ty R T2 S1 T1 Ty1
IH : forall T Ctx X XTy Ty R S,
typeOf ((X, XTy)::Ctx) T Ty -> subst X R T S * -> typeOf [] R XTy -> typeOf Ctx S Ty
S : subst X R (let X T1 T2) (let X S1 T2) @
RTy : typeOf [] R XTy
S1 : subst X R T1 S1 *
Ty : typeOf ((X, XTy)::Ctx) T1 Ty1
Ty1 : typeOf ((X, Ty1)::((X, XTy)::Ctx)) T2 Ty
H1 : typeOf Ctx S1 Ty1
============================
typeOf Ctx (let X S1 T2) Ty
< apply ty_lookup to Ty1 _ with
Ctx2 = (X, Ty1)::Ctx.
Subgoal 7.1:
Variables: Ctx X XTy Ty R T2 S1 T1 Ty1
IH : forall T Ctx X XTy Ty R S,
typeOf ((X, XTy)::Ctx) T Ty -> subst X R T S * -> typeOf [] R XTy -> typeOf Ctx S Ty
S : subst X R (let X T1 T2) (let X S1 T2) @
RTy : typeOf [] R XTy
S1 : subst X R T1 S1 *
Ty : typeOf ((X, XTy)::Ctx) T1 Ty1
Ty1 : typeOf ((X, Ty1)::((X, XTy)::Ctx)) T2 Ty
H1 : typeOf Ctx S1 Ty1
============================
forall X1 XTy1,
lookup ((X, Ty1)::((X, XTy)::Ctx)) X1 XTy1 -> lookup ((X, Ty1)::Ctx) X1 XTy1
< intros L.
Subgoal 7.1:
Variables: Ctx X XTy Ty R T2 S1 T1 Ty1 X1 XTy1
IH : forall T Ctx X XTy Ty R S,
typeOf ((X, XTy)::Ctx) T Ty -> subst X R T S * -> typeOf [] R XTy -> typeOf Ctx S Ty
S : subst X R (let X T1 T2) (let X S1 T2) @
RTy : typeOf [] R XTy
S1 : subst X R T1 S1 *
Ty : typeOf ((X, XTy)::Ctx) T1 Ty1
Ty1 : typeOf ((X, Ty1)::((X, XTy)::Ctx)) T2 Ty
H1 : typeOf Ctx S1 Ty1
L : lookup ((X, Ty1)::((X, XTy)::Ctx)) X1 XTy1
============================
lookup ((X, Ty1)::Ctx) X1 XTy1
< L: case L.
Subgoal 7.1.1:
Variables: Ctx XTy Ty R T2 S1 T1 X1 XTy1
IH : forall T Ctx X XTy Ty R S,
typeOf ((X, XTy)::Ctx) T Ty -> subst X R T S * -> typeOf [] R XTy -> typeOf Ctx S Ty
S : subst X1 R (let X1 T1 T2) (let X1 S1 T2) @
RTy : typeOf [] R XTy
S1 : subst X1 R T1 S1 *
Ty : typeOf ((X1, XTy)::Ctx) T1 XTy1
Ty1 : typeOf ((X1, XTy1)::((X1, XTy)::Ctx)) T2 Ty
H1 : typeOf Ctx S1 XTy1
============================
lookup ((X1, XTy1)::Ctx) X1 XTy1
< search.
Subgoal 7.1.2:
Variables: Ctx X XTy Ty R T2 S1 T1 Ty1 X1 XTy1
IH : forall T Ctx X XTy Ty R S,
typeOf ((X, XTy)::Ctx) T Ty -> subst X R T S * -> typeOf [] R XTy -> typeOf Ctx S Ty
S : subst X R (let X T1 T2) (let X S1 T2) @
RTy : typeOf [] R XTy
S1 : subst X R T1 S1 *
Ty : typeOf ((X, XTy)::Ctx) T1 Ty1
Ty1 : typeOf ((X, Ty1)::((X, XTy)::Ctx)) T2 Ty
H1 : typeOf Ctx S1 Ty1
L : X = X1 -> false
L1 : lookup ((X, XTy)::Ctx) X1 XTy1
============================
lookup ((X, Ty1)::Ctx) X1 XTy1
< L: case L1.
Subgoal 7.1.2.1:
Variables: Ctx Ty R T2 S1 T1 Ty1 X1 XTy1
IH : forall T Ctx X XTy Ty R S,
typeOf ((X, XTy)::Ctx) T Ty -> subst X R T S * -> typeOf [] R XTy -> typeOf Ctx S Ty
S : subst X1 R (let X1 T1 T2) (let X1 S1 T2) @
RTy : typeOf [] R XTy1
S1 : subst X1 R T1 S1 *
Ty : typeOf ((X1, XTy1)::Ctx) T1 Ty1
Ty1 : typeOf ((X1, Ty1)::((X1, XTy1)::Ctx)) T2 Ty
H1 : typeOf Ctx S1 Ty1
L : X1 = X1 -> false
============================
lookup ((X1, Ty1)::Ctx) X1 XTy1
< apply L to _.
Subgoal 7.1.2.2:
Variables: Ctx X XTy Ty R T2 S1 T1 Ty1 X1 XTy1
IH : forall T Ctx X XTy Ty R S,
typeOf ((X, XTy)::Ctx) T Ty -> subst X R T S * -> typeOf [] R XTy -> typeOf Ctx S Ty
S : subst X R (let X T1 T2) (let X S1 T2) @
RTy : typeOf [] R XTy
S1 : subst X R T1 S1 *
Ty : typeOf ((X, XTy)::Ctx) T1 Ty1
Ty1 : typeOf ((X, Ty1)::((X, XTy)::Ctx)) T2 Ty
H1 : typeOf Ctx S1 Ty1
L : X = X1 -> false
L1 : X = X1 -> false
L2 : lookup Ctx X1 XTy1
============================
lookup ((X, Ty1)::Ctx) X1 XTy1
< search.
Subgoal 7:
Variables: Ctx X XTy Ty R T2 S1 T1 Ty1
IH : forall T Ctx X XTy Ty R S,
typeOf ((X, XTy)::Ctx) T Ty -> subst X R T S * -> typeOf [] R XTy -> typeOf Ctx S Ty
S : subst X R (let X T1 T2) (let X S1 T2) @
RTy : typeOf [] R XTy
S1 : subst X R T1 S1 *
Ty : typeOf ((X, XTy)::Ctx) T1 Ty1
Ty1 : typeOf ((X, Ty1)::((X, XTy)::Ctx)) T2 Ty
H1 : typeOf Ctx S1 Ty1
H2 : typeOf ((X, Ty1)::Ctx) T2 Ty
============================
typeOf Ctx (let X S1 T2) Ty
< search.
Proof completed.
< Prove walkthrough:host:type_preservation.
Subgoal 4:
Variables: Ty T2 T11 X T1
IH : forall T Ty T', typeOf [] T Ty -> eval T T' * -> typeOf [] T' Ty
Ty : typeOf [] (let X T1 T2) Ty
Ev : eval (let X T1 T2) (let X T11 T2) @
Ev1 : eval T1 T11 *
============================
typeOf [] (let X T11 T2) Ty
< Ty: case Ty.
Subgoal 4:
Variables: Ty T2 T11 X T1 Ty1
IH : forall T Ty T', typeOf [] T Ty -> eval T T' * -> typeOf [] T' Ty
Ev : eval (let X T1 T2) (let X T11 T2) @
Ev1 : eval T1 T11 *
Ty : typeOf [] T1 Ty1
Ty1 : typeOf [(X, Ty1)] T2 Ty
============================
typeOf [] (let X T11 T2) Ty
< apply IH to Ty Ev1.
Subgoal 4:
Variables: Ty T2 T11 X T1 Ty1
IH : forall T Ty T', typeOf [] T Ty -> eval T T' * -> typeOf [] T' Ty
Ev : eval (let X T1 T2) (let X T11 T2) @
Ev1 : eval T1 T11 *
Ty : typeOf [] T1 Ty1
Ty1 : typeOf [(X, Ty1)] T2 Ty
H1 : typeOf [] T11 Ty1
============================
typeOf [] (let X T11 T2) Ty
< search.
Subgoal 5:
Variables: Ty T' T2 T1 X
IH : forall T Ty T', typeOf [] T Ty -> eval T T' * -> typeOf [] T' Ty
Ty : typeOf [] (let X T1 T2) Ty
Ev : eval (let X T1 T2) T' @
Ev1 : value T1
Ev2 : subst X T1 T2 T'
============================
typeOf [] T' Ty
< Ty: case Ty.
Subgoal 5:
Variables: Ty T' T2 T1 X Ty1
IH : forall T Ty T', typeOf [] T Ty -> eval T T' * -> typeOf [] T' Ty
Ev : eval (let X T1 T2) T' @
Ev1 : value T1
Ev2 : subst X T1 T2 T'
Ty : typeOf [] T1 Ty1
Ty1 : typeOf [(X, Ty1)] T2 Ty
============================
typeOf [] T' Ty
< apply subst_type_preservation to Ty1 Ev2 Ty.
Subgoal 5:
Variables: Ty T' T2 T1 X Ty1
IH : forall T Ty T', typeOf [] T Ty -> eval T T' * -> typeOf [] T' Ty
Ev : eval (let X T1 T2) T' @
Ev1 : value T1
Ev2 : subst X T1 T2 T'
Ty : typeOf [] T1 Ty1
Ty1 : typeOf [(X, Ty1)] T2 Ty
H1 : typeOf [] T' Ty
============================
typeOf [] T' Ty
< search.
Proof completed.
< Prove_Constraint walkthrough:host:proj_type_same.
Variables: G Ty T1 T2 Ty1 X
Hyp : G |{tm}- let X T1 T2 ~~> app (abs X Ty1 T2) T1
Hyp1 : typeOf G (let X T1 T2) Ty
Hyp2 : typeOf G T1 Ty1
============================
typeOf G (app (abs X Ty1 T2) T1) Ty
< case Hyp1.
Variables: G Ty T1 T2 Ty1 X Ty2
Hyp : G |{tm}- let X T1 T2 ~~> app (abs X Ty1 T2) T1
Hyp2 : typeOf G T1 Ty1
H1 : typeOf G T1 Ty2
H2 : typeOf ((X, Ty2)::G) T2 Ty
============================
typeOf G (app (abs X Ty1 T2) T1) Ty
< apply typeOf_unique to Hyp2 H1.
Variables: G Ty T1 T2 X Ty2
Hyp : G |{tm}- let X T1 T2 ~~> app (abs X Ty2 T2) T1
Hyp2 : typeOf G T1 Ty2
H1 : typeOf G T1 Ty2
H2 : typeOf ((X, Ty2)::G) T2 Ty
============================
typeOf G (app (abs X Ty2 T2) T1) Ty
< search.
Proof completed.
< Add_Ext_Size walkthrough:host:eval.
Proof completed.
< Add_Proj_Rel walkthrough:host:eval.
Proof completed.
< Prove_Ext_Ind walkthrough:host:eval.
Subgoal 4:
Variables: N G Ty N2 T2 T11 X T1
IH : forall N G T T' Ty,
<eval {ES}> T T' N -> acc N * -> typeOf G T Ty -> <eval {P}> T T'
IH1 : forall N G T T' Ty,
<eval {ES}> T T' N ** -> acc N @ -> typeOf G T Ty -> <eval {P}> T T'
R : <eval {ES}> (let X T1 T2) (let X T11 T2) N @@
Acc : acc N @
Ty : typeOf G (let X T1 T2) Ty
R1 : 1 + N2 = N
R2 : <eval {ES}> T1 T11 N2 **
============================
<eval {P}> (let X T1 T2) (let X T11 T2)
< Acc: case Acc.
Subgoal 4:
Variables: N G Ty N2 T2 T11 X T1
IH : forall N G T T' Ty,
<eval {ES}> T T' N -> acc N * -> typeOf G T Ty -> <eval {P}> T T'
IH1 : forall N G T T' Ty,
<eval {ES}> T T' N ** -> acc N @ -> typeOf G T Ty -> <eval {P}> T T'
R : <eval {ES}> (let X T1 T2) (let X T11 T2) N @@
Ty : typeOf G (let X T1 T2) Ty
R1 : 1 + N2 = N
R2 : <eval {ES}> T1 T11 N2 **
Acc : forall M, 0 <= M -> M < N -> acc M *
============================
<eval {P}> (let X T1 T2) (let X T11 T2)
< unfold .
Subgoal 4:
Variables: N G Ty N2 T2 T11 X T1
IH : forall N G T T' Ty,
<eval {ES}> T T' N -> acc N * -> typeOf G T Ty -> <eval {P}> T T'
IH1 : forall N G T T' Ty,
<eval {ES}> T T' N ** -> acc N @ -> typeOf G T Ty -> <eval {P}> T T'
R : <eval {ES}> (let X T1 T2) (let X T11 T2) N @@
Ty : typeOf G (let X T1 T2) Ty
R1 : 1 + N2 = N
R2 : <eval {ES}> T1 T11 N2 **
Acc : forall M, 0 <= M -> M < N -> acc M *
============================
exists Ctx T_T T3,
<eval {P}> T1 T11 /\ (Ctx |{tm}- let X T1 T2 ~~> T_T /\ <eval {P}> T_T T3)
< Ty: case Ty.
Subgoal 4:
Variables: N G Ty N2 T2 T11 X T1 Ty1
IH : forall N G T T' Ty,
<eval {ES}> T T' N -> acc N * -> typeOf G T Ty -> <eval {P}> T T'
IH1 : forall N G T T' Ty,
<eval {ES}> T T' N ** -> acc N @ -> typeOf G T Ty -> <eval {P}> T T'
R : <eval {ES}> (let X T1 T2) (let X T11 T2) N @@
R1 : 1 + N2 = N
R2 : <eval {ES}> T1 T11 N2 **
Acc : forall M, 0 <= M -> M < N -> acc M *
Ty : typeOf G T1 Ty1
Ty1 : typeOf ((X, Ty1)::G) T2 Ty
============================
exists Ctx T_T T3,
<eval {P}> T1 T11 /\ (Ctx |{tm}- let X T1 T2 ~~> T_T /\ <eval {P}> T_T T3)
< assert G |{tm}- let X T1 T2 ~~> app (abs X Ty1 T2) T1.
Subgoal 4:
Variables: N G Ty N2 T2 T11 X T1 Ty1
IH : forall N G T T' Ty,
<eval {ES}> T T' N -> acc N * -> typeOf G T Ty -> <eval {P}> T T'
IH1 : forall N G T T' Ty,
<eval {ES}> T T' N ** -> acc N @ -> typeOf G T Ty -> <eval {P}> T T'
R : <eval {ES}> (let X T1 T2) (let X T11 T2) N @@
R1 : 1 + N2 = N
R2 : <eval {ES}> T1 T11 N2 **
Acc : forall M, 0 <= M -> M < N -> acc M *
Ty : typeOf G T1 Ty1
Ty1 : typeOf ((X, Ty1)::G) T2 Ty
H1 : G |{tm}- let X T1 T2 ~~> app (abs X Ty1 T2) T1
============================
exists Ctx T_T T3,
<eval {P}> T1 T11 /\ (Ctx |{tm}- let X T1 T2 ~~> T_T /\ <eval {P}> T_T T3)
< IsN2: apply ext_size_is_int_eval to R2.
Subgoal 4:
Variables: N G Ty N2 T2 T11 X T1 Ty1
IH : forall N G T T' Ty,
<eval {ES}> T T' N -> acc N * -> typeOf G T Ty -> <eval {P}> T T'
IH1 : forall N G T T' Ty,
<eval {ES}> T T' N ** -> acc N @ -> typeOf G T Ty -> <eval {P}> T T'
R : <eval {ES}> (let X T1 T2) (let X T11 T2) N @@
R1 : 1 + N2 = N
R2 : <eval {ES}> T1 T11 N2 **
Acc : forall M, 0 <= M -> M < N -> acc M *
Ty : typeOf G T1 Ty1
Ty1 : typeOf ((X, Ty1)::G) T2 Ty
H1 : G |{tm}- let X T1 T2 ~~> app (abs X Ty1 T2) T1
IsN2 : is_integer N2
============================
exists Ctx T_T T3,
<eval {P}> T1 T11 /\ (Ctx |{tm}- let X T1 T2 ~~> T_T /\ <eval {P}> T_T T3)
< L: apply lt_plus_one to R1 _.
Subgoal 4:
Variables: N G Ty N2 T2 T11 X T1 Ty1
IH : forall N G T T' Ty,
<eval {ES}> T T' N -> acc N * -> typeOf G T Ty -> <eval {P}> T T'
IH1 : forall N G T T' Ty,
<eval {ES}> T T' N ** -> acc N @ -> typeOf G T Ty -> <eval {P}> T T'
R : <eval {ES}> (let X T1 T2) (let X T11 T2) N @@
R1 : 1 + N2 = N
R2 : <eval {ES}> T1 T11 N2 **
Acc : forall M, 0 <= M -> M < N -> acc M *
Ty : typeOf G T1 Ty1
Ty1 : typeOf ((X, Ty1)::G) T2 Ty
H1 : G |{tm}- let X T1 T2 ~~> app (abs X Ty1 T2) T1
IsN2 : is_integer N2
L : N2 < N
============================
exists Ctx T_T T3,
<eval {P}> T1 T11 /\ (Ctx |{tm}- let X T1 T2 ~~> T_T /\ <eval {P}> T_T T3)
< PosN2: apply ext_size_pos_eval to R2.
Subgoal 4:
Variables: N G Ty N2 T2 T11 X T1 Ty1
IH : forall N G T T' Ty,
<eval {ES}> T T' N -> acc N * -> typeOf G T Ty -> <eval {P}> T T'
IH1 : forall N G T T' Ty,
<eval {ES}> T T' N ** -> acc N @ -> typeOf G T Ty -> <eval {P}> T T'
R : <eval {ES}> (let X T1 T2) (let X T11 T2) N @@
R1 : 1 + N2 = N
R2 : <eval {ES}> T1 T11 N2 **
Acc : forall M, 0 <= M -> M < N -> acc M *
Ty : typeOf G T1 Ty1
Ty1 : typeOf ((X, Ty1)::G) T2 Ty
H1 : G |{tm}- let X T1 T2 ~~> app (abs X Ty1 T2) T1
IsN2 : is_integer N2
L : N2 < N
PosN2 : 0 <= N2
============================
exists Ctx T_T T3,
<eval {P}> T1 T11 /\ (Ctx |{tm}- let X T1 T2 ~~> T_T /\ <eval {P}> T_T T3)
< A: apply Acc to PosN2 L.
Subgoal 4:
Variables: N G Ty N2 T2 T11 X T1 Ty1
IH : forall N G T T' Ty,
<eval {ES}> T T' N -> acc N * -> typeOf G T Ty -> <eval {P}> T T'
IH1 : forall N G T T' Ty,
<eval {ES}> T T' N ** -> acc N @ -> typeOf G T Ty -> <eval {P}> T T'
R : <eval {ES}> (let X T1 T2) (let X T11 T2) N @@
R1 : 1 + N2 = N
R2 : <eval {ES}> T1 T11 N2 **
Acc : forall M, 0 <= M -> M < N -> acc M *
Ty : typeOf G T1 Ty1
Ty1 : typeOf ((X, Ty1)::G) T2 Ty
H1 : G |{tm}- let X T1 T2 ~~> app (abs X Ty1 T2) T1
IsN2 : is_integer N2
L : N2 < N
PosN2 : 0 <= N2
A : acc N2 *
============================
exists Ctx T_T T3,
<eval {P}> T1 T11 /\ (Ctx |{tm}- let X T1 T2 ~~> T_T /\ <eval {P}> T_T T3)
< apply IH to R2 A Ty.
Subgoal 4:
Variables: N G Ty N2 T2 T11 X T1 Ty1
IH : forall N G T T' Ty,
<eval {ES}> T T' N -> acc N * -> typeOf G T Ty -> <eval {P}> T T'
IH1 : forall N G T T' Ty,
<eval {ES}> T T' N ** -> acc N @ -> typeOf G T Ty -> <eval {P}> T T'
R : <eval {ES}> (let X T1 T2) (let X T11 T2) N @@
R1 : 1 + N2 = N
R2 : <eval {ES}> T1 T11 N2 **
Acc : forall M, 0 <= M -> M < N -> acc M *
Ty : typeOf G T1 Ty1
Ty1 : typeOf ((X, Ty1)::G) T2 Ty
H1 : G |{tm}- let X T1 T2 ~~> app (abs X Ty1 T2) T1
IsN2 : is_integer N2
L : N2 < N
PosN2 : 0 <= N2
A : acc N2 *
H2 : <eval {P}> T1 T11
============================
exists Ctx T_T T3,
<eval {P}> T1 T11 /\ (Ctx |{tm}- let X T1 T2 ~~> T_T /\ <eval {P}> T_T T3)
< search.
Subgoal 5:
Variables: G T' Ty T2 T1 X
IH : forall N G T T' Ty,
<eval {ES}> T T' N -> acc N * -> typeOf G T Ty -> <eval {P}> T T'
IH1 : forall N G T T' Ty,
<eval {ES}> T T' N ** -> acc N @ -> typeOf G T Ty -> <eval {P}> T T'
R : <eval {ES}> (let X T1 T2) T' 1 @@
Acc : acc 1 @
Ty : typeOf G (let X T1 T2) Ty
R1 : value T1
R2 : subst X T1 T2 T'
============================
<eval {P}> (let X T1 T2) T'
< unfold .
Subgoal 5:
Variables: G T' Ty T2 T1 X
IH : forall N G T T' Ty,
<eval {ES}> T T' N -> acc N * -> typeOf G T Ty -> <eval {P}> T T'
IH1 : forall N G T T' Ty,
<eval {ES}> T T' N ** -> acc N @ -> typeOf G T Ty -> <eval {P}> T T'
R : <eval {ES}> (let X T1 T2) T' 1 @@
Acc : acc 1 @
Ty : typeOf G (let X T1 T2) Ty
R1 : value T1
R2 : subst X T1 T2 T'
============================
exists Ctx T_T T3,
(value T1 /\ subst X T1 T2 T') /\
(Ctx |{tm}- let X T1 T2 ~~> T_T /\ <eval {P}> T_T T3)
< Ty: case Ty.
Subgoal 5:
Variables: G T' Ty T2 T1 X Ty1
IH : forall N G T T' Ty,
<eval {ES}> T T' N -> acc N * -> typeOf G T Ty -> <eval {P}> T T'
IH1 : forall N G T T' Ty,
<eval {ES}> T T' N ** -> acc N @ -> typeOf G T Ty -> <eval {P}> T T'
R : <eval {ES}> (let X T1 T2) T' 1 @@
Acc : acc 1 @
R1 : value T1
R2 : subst X T1 T2 T'
Ty : typeOf G T1 Ty1
Ty1 : typeOf ((X, Ty1)::G) T2 Ty
============================
exists Ctx T_T T3,
(value T1 /\ subst X T1 T2 T') /\
(Ctx |{tm}- let X T1 T2 ~~> T_T /\ <eval {P}> T_T T3)
< assert G |{tm}- let X T1 T2 ~~> app (abs X Ty1 T2) T1.
Subgoal 5:
Variables: G T' Ty T2 T1 X Ty1
IH : forall N G T T' Ty,
<eval {ES}> T T' N -> acc N * -> typeOf G T Ty -> <eval {P}> T T'
IH1 : forall N G T T' Ty,
<eval {ES}> T T' N ** -> acc N @ -> typeOf G T Ty -> <eval {P}> T T'
R : <eval {ES}> (let X T1 T2) T' 1 @@
Acc : acc 1 @
R1 : value T1
R2 : subst X T1 T2 T'
Ty : typeOf G T1 Ty1
Ty1 : typeOf ((X, Ty1)::G) T2 Ty
H1 : G |{tm}- let X T1 T2 ~~> app (abs X Ty1 T2) T1
============================
exists Ctx T_T T3,
(value T1 /\ subst X T1 T2 T') /\
(Ctx |{tm}- let X T1 T2 ~~> T_T /\ <eval {P}> T_T T3)
< search.
Proof completed.
