< Module stlc:let.
< Prove_Constraint stlc:host:proj_ty_is.
Proof completed.
< Prove stlc:host:type_is.
Subgoal 6:
Variables: Ctx Ty Ty1 T2 T1 X
IH : forall Ctx T Ty,
is_list (is_pair is_string is_ty) Ctx -> is_tm T -> typeOf Ctx T Ty * -> is_ty Ty
IsCtx : is_list (is_pair is_string is_ty) Ctx
IsT : is_tm (let X T1 T2)
Ty : typeOf Ctx (let X T1 T2) Ty @
Ty1 : typeOf Ctx T1 Ty1 *
Ty2 : typeOf ((X, Ty1)::Ctx) T2 Ty *
============================
is_ty Ty
< Is: case IsT.
Subgoal 6:
Variables: Ctx Ty Ty1 T2 T1 X
IH : forall Ctx T Ty,
is_list (is_pair is_string is_ty) Ctx -> is_tm T -> typeOf Ctx T Ty * -> is_ty Ty
IsCtx : is_list (is_pair is_string is_ty) Ctx
Ty : typeOf Ctx (let X T1 T2) Ty @
Ty1 : typeOf Ctx T1 Ty1 *
Ty2 : typeOf ((X, Ty1)::Ctx) T2 Ty *
Is : is_string X
Is1 : is_tm T1
Is2 : is_tm T2
============================
is_ty Ty
< apply IH to _ Is1 Ty1.
Subgoal 6:
Variables: Ctx Ty Ty1 T2 T1 X
IH : forall Ctx T Ty,
is_list (is_pair is_string is_ty) Ctx -> is_tm T -> typeOf Ctx T Ty * -> is_ty Ty
IsCtx : is_list (is_pair is_string is_ty) Ctx
Ty : typeOf Ctx (let X T1 T2) Ty @
Ty1 : typeOf Ctx T1 Ty1 *
Ty2 : typeOf ((X, Ty1)::Ctx) T2 Ty *
Is : is_string X
Is1 : is_tm T1
Is2 : is_tm T2
H1 : is_ty Ty1
============================
is_ty Ty
< apply IH to _ Is2 Ty2.
Subgoal 6:
Variables: Ctx Ty Ty1 T2 T1 X
IH : forall Ctx T Ty,
is_list (is_pair is_string is_ty) Ctx -> is_tm T -> typeOf Ctx T Ty * -> is_ty Ty
IsCtx : is_list (is_pair is_string is_ty) Ctx
Ty : typeOf Ctx (let X T1 T2) Ty @
Ty1 : typeOf Ctx T1 Ty1 *
Ty2 : typeOf ((X, Ty1)::Ctx) T2 Ty *
Is : is_string X
Is1 : is_tm T1
Is2 : is_tm T2
H1 : is_ty Ty1
H2 : is_ty Ty
============================
is_ty Ty
< search.
Proof completed.
< Prove_Constraint stlc:host:proj_is.
Variables: Ctx T1 T2 Ty X
Proj : Ctx |{tm}- let X T1 T2 ~~> app (abs X Ty T2) T1
IsCtx : is_list (is_pair is_string is_ty) Ctx
IsT : is_tm (let X T1 T2)
Proj1 : typeOf Ctx T1 Ty
============================
is_tm (app (abs X Ty T2) T1)
< case IsT.
Variables: Ctx T1 T2 Ty X
Proj : Ctx |{tm}- let X T1 T2 ~~> app (abs X Ty T2) T1
IsCtx : is_list (is_pair is_string is_ty) Ctx
Proj1 : typeOf Ctx T1 Ty
H1 : is_string X
H2 : is_tm T1
H3 : is_tm T2
============================
is_tm (app (abs X Ty T2) T1)
< apply type_is to _ _ Proj1.
Variables: Ctx T1 T2 Ty X
Proj : Ctx |{tm}- let X T1 T2 ~~> app (abs X Ty T2) T1
IsCtx : is_list (is_pair is_string is_ty) Ctx
Proj1 : typeOf Ctx T1 Ty
H1 : is_string X
H2 : is_tm T1
H3 : is_tm T2
H4 : is_ty Ty
============================
is_tm (app (abs X Ty T2) T1)
< search.
Proof completed.
< Prove stlc:host:type_unique.
Subgoal 6:
Variables: Ctx TyA TyB Ty1 T2 T1 X
IH : forall Ctx T TyA TyB,
is_list (is_pair is_string is_ty) Ctx -> is_tm T -> typeOf Ctx T TyA * ->
typeOf Ctx T TyB -> TyA = TyB
IsCtx : is_list (is_pair is_string is_ty) Ctx
IsT : is_tm (let X T1 T2)
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 6:
Variables: Ctx TyA TyB Ty1 T2 T1 X Ty2
IH : forall Ctx T TyA TyB,
is_list (is_pair is_string is_ty) Ctx -> is_tm T -> typeOf Ctx T TyA * ->
typeOf Ctx T TyB -> TyA = TyB
IsCtx : is_list (is_pair is_string is_ty) Ctx
IsT : is_tm (let X T1 T2)
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
< case IsT.
Subgoal 6:
Variables: Ctx TyA TyB Ty1 T2 T1 X Ty2
IH : forall Ctx T TyA TyB,
is_list (is_pair is_string is_ty) Ctx -> is_tm T -> typeOf Ctx T TyA * ->
typeOf Ctx T TyB -> TyA = TyB
IsCtx : is_list (is_pair is_string is_ty) Ctx
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
H1 : is_string X
H2 : is_tm T1
H3 : is_tm T2
============================
TyA = TyB
< apply IH to _ _ TyA1 TyB.
Subgoal 6:
Variables: Ctx TyA TyB T2 T1 X Ty2
IH : forall Ctx T TyA TyB,
is_list (is_pair is_string is_ty) Ctx -> is_tm T -> typeOf Ctx T TyA * ->
typeOf Ctx T TyB -> TyA = TyB
IsCtx : is_list (is_pair is_string is_ty) Ctx
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
H1 : is_string X
H2 : is_tm T1
H3 : is_tm T2
============================
TyA = TyB
< apply type_is to _ _ TyA1.
Subgoal 6:
Variables: Ctx TyA TyB T2 T1 X Ty2
IH : forall Ctx T TyA TyB,
is_list (is_pair is_string is_ty) Ctx -> is_tm T -> typeOf Ctx T TyA * ->
typeOf Ctx T TyB -> TyA = TyB
IsCtx : is_list (is_pair is_string is_ty) Ctx
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
H1 : is_string X
H2 : is_tm T1
H3 : is_tm T2
H4 : is_ty Ty2
============================
TyA = TyB
< apply IH to _ _ TyA2 TyB1.
Subgoal 6:
Variables: Ctx TyB T2 T1 X Ty2
IH : forall Ctx T TyA TyB,
is_list (is_pair is_string is_ty) Ctx -> is_tm T -> typeOf Ctx T TyA * ->
typeOf Ctx T TyB -> TyA = TyB
IsCtx : is_list (is_pair is_string is_ty) Ctx
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
H1 : is_string X
H2 : is_tm T1
H3 : is_tm T2
H4 : is_ty Ty2
============================
TyB = TyB
< search.
Proof completed.
< Prove_Constraint stlc:host:proj_ty_unique.
Proof completed.
< Prove_Constraint stlc:host:proj_tm_unique.
Variables: Ctx TB T1 T2 Ty X
Hyp : Ctx |{tm}- let X T1 T2 ~~> app (abs X Ty T2) T1
Hyp1 : Ctx |{tm}- let X T1 T2 ~~> TB
Hyp2 : is_tm (let X T1 T2)
Hyp3 : is_list (is_pair is_string is_ty) Ctx
Hyp4 : typeOf Ctx T1 Ty
============================
app (abs X Ty T2) T1 = TB
< case Hyp1.
Variables: Ctx T1 T2 Ty X Ty1
Hyp : Ctx |{tm}- let X T1 T2 ~~> app (abs X Ty T2) T1
Hyp2 : is_tm (let X T1 T2)
Hyp3 : is_list (is_pair is_string is_ty) Ctx
Hyp4 : typeOf Ctx T1 Ty
H1 : typeOf Ctx T1 Ty1
============================
app (abs X Ty T2) T1 = app (abs X Ty1 T2) T1
< case Hyp2.
Variables: Ctx T1 T2 Ty X Ty1
Hyp : Ctx |{tm}- let X T1 T2 ~~> app (abs X Ty T2) T1
Hyp3 : is_list (is_pair is_string is_ty) Ctx
Hyp4 : typeOf Ctx T1 Ty
H1 : typeOf Ctx T1 Ty1
H2 : is_string X
H3 : is_tm T1
H4 : is_tm T2
============================
app (abs X Ty T2) T1 = app (abs X Ty1 T2) T1
< apply type_unique to _ _ Hyp4 H1.
Variables: Ctx T1 T2 X Ty1
Hyp : Ctx |{tm}- let X T1 T2 ~~> app (abs X Ty1 T2) T1
Hyp3 : is_list (is_pair is_string is_ty) Ctx
Hyp4 : typeOf Ctx T1 Ty1
H1 : typeOf Ctx T1 Ty1
H2 : is_string X
H3 : is_tm T1
H4 : is_tm T2
============================
app (abs X Ty1 T2) T1 = app (abs X Ty1 T2) T1
< search.
Proof completed.
< Prove stlc:host:subst_is.
Subgoal 8:
Variables: X R S2 S1 Y T2 T1
IH : forall X R T S,
is_tm T -> is_string X -> is_tm R -> subst X R T S * -> is_tm S
IsT : is_tm (let Y T1 T2)
IsX : is_string X
IsR : is_tm R
S : subst X R (let Y T1 T2) (let Y S1 S2) @
S1 : X = Y -> false
S2 : subst X R T1 S1 *
S3 : subst X R T2 S2 *
============================
is_tm (let Y S1 S2)
< Is: case IsT.
Subgoal 8:
Variables: X R S2 S1 Y T2 T1
IH : forall X R T S,
is_tm T -> is_string X -> is_tm R -> subst X R T S * -> is_tm S
IsX : is_string X
IsR : is_tm R
S : subst X R (let Y T1 T2) (let Y S1 S2) @
S1 : X = Y -> false
S2 : subst X R T1 S1 *
S3 : subst X R T2 S2 *
Is : is_string Y
Is1 : is_tm T1
Is2 : is_tm T2
============================
is_tm (let Y S1 S2)
< apply IH to _ _ _ S2.
Subgoal 8:
Variables: X R S2 S1 Y T2 T1
IH : forall X R T S,
is_tm T -> is_string X -> is_tm R -> subst X R T S * -> is_tm S
IsX : is_string X
IsR : is_tm R
S : subst X R (let Y T1 T2) (let Y S1 S2) @
S1 : X = Y -> false
S2 : subst X R T1 S1 *
S3 : subst X R T2 S2 *
Is : is_string Y
Is1 : is_tm T1
Is2 : is_tm T2
H1 : is_tm S1
============================
is_tm (let Y S1 S2)
< apply IH to _ _ _ S3.
Subgoal 8:
Variables: X R S2 S1 Y T2 T1
IH : forall X R T S,
is_tm T -> is_string X -> is_tm R -> subst X R T S * -> is_tm S
IsX : is_string X
IsR : is_tm R
S : subst X R (let Y T1 T2) (let Y S1 S2) @
S1 : X = Y -> false
S2 : subst X R T1 S1 *
S3 : subst X R T2 S2 *
Is : is_string Y
Is1 : is_tm T1
Is2 : is_tm T2
H1 : is_tm S1
H2 : is_tm S2
============================
is_tm (let Y S1 S2)
< search.
Subgoal 9:
Variables: X R T2 S1 T1
IH : forall X R T S,
is_tm T -> is_string X -> is_tm R -> subst X R T S * -> is_tm S
IsT : is_tm (let X T1 T2)
IsX : is_string X
IsR : is_tm R
S : subst X R (let X T1 T2) (let X S1 T2) @
S1 : subst X R T1 S1 *
============================
is_tm (let X S1 T2)
< Is: case IsT.
Subgoal 9:
Variables: X R T2 S1 T1
IH : forall X R T S,
is_tm T -> is_string X -> is_tm R -> subst X R T S * -> is_tm S
IsX : is_string X
IsR : is_tm R
S : subst X R (let X T1 T2) (let X S1 T2) @
S1 : subst X R T1 S1 *
Is : is_string X
Is1 : is_tm T1
Is2 : is_tm T2
============================
is_tm (let X S1 T2)
< apply IH to _ _ _ S1.
Subgoal 9:
Variables: X R T2 S1 T1
IH : forall X R T S,
is_tm T -> is_string X -> is_tm R -> subst X R T S * -> is_tm S
IsX : is_string X
IsR : is_tm R
S : subst X R (let X T1 T2) (let X S1 T2) @
S1 : subst X R T1 S1 *
Is : is_string X
Is1 : is_tm T1
Is2 : is_tm T2
H1 : is_tm S1
============================
is_tm (let X S1 T2)
< search.
Proof completed.
< Prove stlc:host:eval_is.
Subgoal 7:
Variables: T2 T11 X T1
IH : forall T T', is_tm T -> eval T T' * -> is_tm T'
IsT : is_tm (let X T1 T2)
Ev : eval (let X T1 T2) (let X T11 T2) @
Ev1 : eval T1 T11 *
============================
is_tm (let X T11 T2)
< Is: case IsT.
Subgoal 7:
Variables: T2 T11 X T1
IH : forall T T', is_tm T -> eval T T' * -> is_tm T'
Ev : eval (let X T1 T2) (let X T11 T2) @
Ev1 : eval T1 T11 *
Is : is_string X
Is1 : is_tm T1
Is2 : is_tm T2
============================
is_tm (let X T11 T2)
< apply IH to _ Ev1.
Subgoal 7:
Variables: T2 T11 X T1
IH : forall T T', is_tm T -> eval T T' * -> is_tm T'
Ev : eval (let X T1 T2) (let X T11 T2) @
Ev1 : eval T1 T11 *
Is : is_string X
Is1 : is_tm T1
Is2 : is_tm T2
H1 : is_tm T11
============================
is_tm (let X T11 T2)
< search.
Subgoal 8:
Variables: T' T2 T1 X
IH : forall T T', is_tm T -> eval T T' * -> is_tm T'
IsT : is_tm (let X T1 T2)
Ev : eval (let X T1 T2) T' @
Ev1 : value T1
Ev2 : subst X T1 T2 T'
============================
is_tm T'
< Is: case IsT.
Subgoal 8:
Variables: T' T2 T1 X
IH : forall T T', is_tm T -> eval T T' * -> is_tm T'
Ev : eval (let X T1 T2) T' @
Ev1 : value T1
Ev2 : subst X T1 T2 T'
Is : is_string X
Is1 : is_tm T1
Is2 : is_tm T2
============================
is_tm T'
< apply subst_is to _ _ _ Ev2.
Subgoal 8:
Variables: T' T2 T1 X
IH : forall T T', is_tm T -> eval T T' * -> is_tm T'
Ev : eval (let X T1 T2) T' @
Ev1 : value T1
Ev2 : subst X T1 T2 T'
Is : is_string X
Is1 : is_tm T1
Is2 : is_tm T2
H1 : is_tm T'
============================
is_tm T'
< search.
Proof completed.
< Prove stlc:host:subst_unique.
Subgoal 8:
Variables: X R VB S2 S1 Y T2 T1
IH : forall X R T VA VB, subst X R T VA * -> subst X R T VB -> VA = VB
SA : subst X R (let Y T1 T2) (let Y S1 S2) @
SB : subst X R (let Y T1 T2) VB
SA1 : X = Y -> false
SA2 : subst X R T1 S1 *
SA3 : subst X R T2 S2 *
============================
let Y S1 S2 = VB
< SB: case SB.
Subgoal 8.1:
Variables: X R S2 S1 Y T2 T1 S4 S3
IH : forall X R T VA VB, subst X R T VA * -> subst X R T VB -> VA = VB
SA : subst X R (let Y T1 T2) (let Y S1 S2) @
SA1 : X = Y -> false
SA2 : subst X R T1 S1 *
SA3 : subst X R T2 S2 *
SB : X = Y -> false
SB1 : subst X R T1 S3
SB2 : subst X R T2 S4
============================
let Y S1 S2 = let Y S3 S4
< apply IH to SA2 SB1.
Subgoal 8.1:
Variables: X R S2 Y T2 T1 S4 S3
IH : forall X R T VA VB, subst X R T VA * -> subst X R T VB -> VA = VB
SA : subst X R (let Y T1 T2) (let Y S3 S2) @
SA1 : X = Y -> false
SA2 : subst X R T1 S3 *
SA3 : subst X R T2 S2 *
SB : X = Y -> false
SB1 : subst X R T1 S3
SB2 : subst X R T2 S4
============================
let Y S3 S2 = let Y S3 S4
< apply IH to SA3 SB2.
Subgoal 8.1:
Variables: X R Y T2 T1 S4 S3
IH : forall X R T VA VB, subst X R T VA * -> subst X R T VB -> VA = VB
SA : subst X R (let Y T1 T2) (let Y S3 S4) @
SA1 : X = Y -> false
SA2 : subst X R T1 S3 *
SA3 : subst X R T2 S4 *
SB : X = Y -> false
SB1 : subst X R T1 S3
SB2 : subst X R T2 S4
============================
let Y S3 S4 = let Y S3 S4
< search.
Subgoal 8.2:
Variables: R S2 S1 Y T2 T1 S3
IH : forall X R T VA VB, subst X R T VA * -> subst X R T VB -> VA = VB
SA : subst Y R (let Y T1 T2) (let Y S1 S2) @
SA1 : Y = Y -> false
SA2 : subst Y R T1 S1 *
SA3 : subst Y R T2 S2 *
SB : subst Y R T1 S3
============================
let Y S1 S2 = let Y S3 T2
< apply SA1 to _.
Subgoal 9:
Variables: X R VB T2 S1 T1
IH : forall X R T VA VB, subst X R T VA * -> subst X R T VB -> VA = VB
SA : subst X R (let X T1 T2) (let X S1 T2) @
SB : subst X R (let X T1 T2) VB
SA1 : subst X R T1 S1 *
============================
let X S1 T2 = VB
< SB: case SB.
Subgoal 9.1:
Variables: X R T2 S1 T1 S3 S2
IH : forall X R T VA VB, subst X R T VA * -> subst X R T VB -> VA = VB
SA : subst X R (let X T1 T2) (let X S1 T2) @
SA1 : subst X R T1 S1 *
SB : X = X -> false
SB1 : subst X R T1 S2
SB2 : subst X R T2 S3
============================
let X S1 T2 = let X S2 S3
< apply SB to _.
Subgoal 9.2:
Variables: X R T2 S1 T1 S2
IH : forall X R T VA VB, subst X R T VA * -> subst X R T VB -> VA = VB
SA : subst X R (let X T1 T2) (let X S1 T2) @
SA1 : subst X R T1 S1 *
SB : subst X R T1 S2
============================
let X S1 T2 = let X S2 T2
< apply IH to SA1 SB.
Subgoal 9.2:
Variables: X R T2 T1 S2
IH : forall X R T VA VB, subst X R T VA * -> subst X R T VB -> VA = VB
SA : subst X R (let X T1 T2) (let X S2 T2) @
SA1 : subst X R T1 S2 *
SB : subst X R T1 S2
============================
let X S2 T2 = let X S2 T2
< search.
Proof completed.
< Prove stlc:host:value_eval_false.
Proof completed.
< Prove stlc:host:eval_unique.
Subgoal 7:
Variables: VB T2 T11 X T1
IH : forall T VA VB, eval T VA * -> eval T VB -> VA = VB
EvA : eval (let X T1 T2) (let X T11 T2) @
EvB : eval (let X T1 T2) VB
EvA1 : eval T1 T11 *
============================
let X T11 T2 = VB
< EvB: case EvB.
Subgoal 7.1:
Variables: T2 T11 X T1 T5
IH : forall T VA VB, eval T VA * -> eval T VB -> VA = VB
EvA : eval (let X T1 T2) (let X T11 T2) @
EvA1 : eval T1 T11 *
EvB : eval T1 T5
============================
let X T11 T2 = let X T5 T2
< apply IH to EvA1 EvB.
Subgoal 7.1:
Variables: T2 X T1 T5
IH : forall T VA VB, eval T VA * -> eval T VB -> VA = VB
EvA : eval (let X T1 T2) (let X T5 T2) @
EvA1 : eval T1 T5 *
EvB : eval T1 T5
============================
let X T5 T2 = let X T5 T2
< search.
Subgoal 7.2:
Variables: VB T2 T11 X T1
IH : forall T VA VB, eval T VA * -> eval T VB -> VA = VB
EvA : eval (let X T1 T2) (let X T11 T2) @
EvA1 : eval T1 T11 *
EvB : value T1
EvB1 : subst X T1 T2 VB
============================
let X T11 T2 = VB
< apply value_eval_false to EvB EvA1.
Subgoal 8:
Variables: VA VB T2 T1 X
IH : forall T VA VB, eval T VA * -> eval T VB -> VA = VB
EvA : eval (let X T1 T2) VA @
EvB : eval (let X T1 T2) VB
EvA1 : value T1
EvA2 : subst X T1 T2 VA
============================
VA = VB
< EvB: case EvB.
Subgoal 8.1:
Variables: VA T2 T1 X T11
IH : forall T VA VB, eval T VA * -> eval T VB -> VA = VB
EvA : eval (let X T1 T2) VA @
EvA1 : value T1
EvA2 : subst X T1 T2 VA
EvB : eval T1 T11
============================
VA = let X T11 T2
< apply value_eval_false to EvA1 EvB.
Subgoal 8.2:
Variables: VA VB T2 T1 X
IH : forall T VA VB, eval T VA * -> eval T VB -> VA = VB
EvA : eval (let X T1 T2) VA @
EvA1 : value T1
EvA2 : subst X T1 T2 VA
EvB : value T1
EvB1 : subst X T1 T2 VB
============================
VA = VB
< apply subst_unique to EvA2 EvB1.
Subgoal 8.2:
Variables: VB T2 T1 X
IH : forall T VA VB, eval T VA * -> eval T VB -> VA = VB
EvA : eval (let X T1 T2) VB @
EvA1 : value T1
EvA2 : subst X T1 T2 VB
EvB : value T1
EvB1 : subst X T1 T2 VB
============================
VB = VB
< search.
Proof completed.
< Prove stlc:host:ty_lookup.
Subgoal 6:
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 6:
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 6.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 6.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 6.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 6.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 6.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 6:
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 stlc:host:subst_type_preservation.
Subgoal 8:
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 8:
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 8:
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 8.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 8.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 8.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 8.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 8.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 8.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 8:
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 8:
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 9:
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 9:
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 9:
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 9.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 9.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 9.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 9.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 9.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 9.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 9:
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 stlc:host:type_preservation.
Subgoal 7:
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 7:
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 7:
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 8:
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 8:
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 8:
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 stlc:host:subst_total.
Subgoal 6:
Variables: X R Tm Tm1 S
IH : forall X R T, is_tm T * -> is_string X -> exists S, subst X R T S
IsT : is_tm (let S Tm1 Tm) @
IsX : is_string X
IsT1 : is_string S
IsT2 : is_tm Tm1 *
IsT3 : is_tm Tm *
============================
exists S1, subst X R (let S Tm1 Tm) S1
< Or: apply is_string_eq_or_not to IsX IsT1.
Subgoal 6:
Variables: X R Tm Tm1 S
IH : forall X R T, is_tm T * -> is_string X -> exists S, subst X R T S
IsT : is_tm (let S Tm1 Tm) @
IsX : is_string X
IsT1 : is_string S
IsT2 : is_tm Tm1 *
IsT3 : is_tm Tm *
Or : X = S \/ (X = S -> false)
============================
exists S1, subst X R (let S Tm1 Tm) S1
< E: case Or.
Subgoal 6.1:
Variables: R Tm Tm1 S
IH : forall X R T, is_tm T * -> is_string X -> exists S, subst X R T S
IsT : is_tm (let S Tm1 Tm) @
IsX : is_string S
IsT1 : is_string S
IsT2 : is_tm Tm1 *
IsT3 : is_tm Tm *
============================
exists S1, subst S R (let S Tm1 Tm) S1
< apply IH to IsT2 IsX with
R = R.
Subgoal 6.1:
Variables: R Tm Tm1 S S1
IH : forall X R T, is_tm T * -> is_string X -> exists S, subst X R T S
IsT : is_tm (let S Tm1 Tm) @
IsX : is_string S
IsT1 : is_string S
IsT2 : is_tm Tm1 *
IsT3 : is_tm Tm *
H1 : subst S R Tm1 S1
============================
exists S1, subst S R (let S Tm1 Tm) S1
< search.
Subgoal 6.2:
Variables: X R Tm Tm1 S
IH : forall X R T, is_tm T * -> is_string X -> exists S, subst X R T S
IsT : is_tm (let S Tm1 Tm) @
IsX : is_string X
IsT1 : is_string S
IsT2 : is_tm Tm1 *
IsT3 : is_tm Tm *
E : X = S -> false
============================
exists S1, subst X R (let S Tm1 Tm) S1
< apply IH to IsT2 IsX with
R = R.
Subgoal 6.2:
Variables: X R Tm Tm1 S S1
IH : forall X R T, is_tm T * -> is_string X -> exists S, subst X R T S
IsT : is_tm (let S Tm1 Tm) @
IsX : is_string X
IsT1 : is_string S
IsT2 : is_tm Tm1 *
IsT3 : is_tm Tm *
E : X = S -> false
H1 : subst X R Tm1 S1
============================
exists S1, subst X R (let S Tm1 Tm) S1
< apply IH to IsT3 IsX with
R = R.
Subgoal 6.2:
Variables: X R Tm Tm1 S S1 S2
IH : forall X R T, is_tm T * -> is_string X -> exists S, subst X R T S
IsT : is_tm (let S Tm1 Tm) @
IsX : is_string X
IsT1 : is_string S
IsT2 : is_tm Tm1 *
IsT3 : is_tm Tm *
E : X = S -> false
H1 : subst X R Tm1 S1
H2 : subst X R Tm S2
============================
exists S1, subst X R (let S Tm1 Tm) S1
< search.
Proof completed.
< Prove stlc:host:canonical_forms.
Proof completed.
< Prove stlc:host:progress.
Subgoal 6:
Variables: Ty Ty1 T2 T1 X
IH : forall T Ty,
is_tm T -> typeOf [] T Ty * -> (exists T', eval T T') \/ value T
IsT : is_tm (let X T1 T2)
Ty : typeOf [] (let X T1 T2) Ty @
Ty1 : typeOf [] T1 Ty1 *
Ty2 : typeOf [(X, Ty1)] T2 Ty *
============================
(exists T', eval (let X T1 T2) T') \/ value (let X T1 T2)
< Is: case IsT.
Subgoal 6:
Variables: Ty Ty1 T2 T1 X
IH : forall T Ty,
is_tm T -> typeOf [] T Ty * -> (exists T', eval T T') \/ value T
Ty : typeOf [] (let X T1 T2) Ty @
Ty1 : typeOf [] T1 Ty1 *
Ty2 : typeOf [(X, Ty1)] T2 Ty *
Is : is_string X
Is1 : is_tm T1
Is2 : is_tm T2
============================
(exists T', eval (let X T1 T2) T') \/ value (let X T1 T2)
< Or: apply IH to _ Ty1.
Subgoal 6:
Variables: Ty Ty1 T2 T1 X
IH : forall T Ty,
is_tm T -> typeOf [] T Ty * -> (exists T', eval T T') \/ value T
Ty : typeOf [] (let X T1 T2) Ty @
Ty1 : typeOf [] T1 Ty1 *
Ty2 : typeOf [(X, Ty1)] T2 Ty *
Is : is_string X
Is1 : is_tm T1
Is2 : is_tm T2
Or : (exists T', eval T1 T') \/ value T1
============================
(exists T', eval (let X T1 T2) T') \/ value (let X T1 T2)
< EV: case Or.
Subgoal 6.1:
Variables: Ty Ty1 T2 T1 X T'
IH : forall T Ty,
is_tm T -> typeOf [] T Ty * -> (exists T', eval T T') \/ value T
Ty : typeOf [] (let X T1 T2) Ty @
Ty1 : typeOf [] T1 Ty1 *
Ty2 : typeOf [(X, Ty1)] T2 Ty *
Is : is_string X
Is1 : is_tm T1
Is2 : is_tm T2
EV : eval T1 T'
============================
(exists T', eval (let X T1 T2) T') \/ value (let X T1 T2)
< search.
Subgoal 6.2:
Variables: Ty Ty1 T2 T1 X
IH : forall T Ty,
is_tm T -> typeOf [] T Ty * -> (exists T', eval T T') \/ value T
Ty : typeOf [] (let X T1 T2) Ty @
Ty1 : typeOf [] T1 Ty1 *
Ty2 : typeOf [(X, Ty1)] T2 Ty *
Is : is_string X
Is1 : is_tm T1
Is2 : is_tm T2
EV : value T1
============================
(exists T', eval (let X T1 T2) T') \/ value (let X T1 T2)
< apply subst_total to Is2 Is with
R = T1.
Subgoal 6.2:
Variables: Ty Ty1 T2 T1 X S
IH : forall T Ty,
is_tm T -> typeOf [] T Ty * -> (exists T', eval T T') \/ value T
Ty : typeOf [] (let X T1 T2) Ty @
Ty1 : typeOf [] T1 Ty1 *
Ty2 : typeOf [(X, Ty1)] T2 Ty *
Is : is_string X
Is1 : is_tm T1
Is2 : is_tm T2
EV : value T1
H1 : subst X T1 T2 S
============================
(exists T', eval (let X T1 T2) T') \/ value (let X T1 T2)
< search.
Proof completed.
