< Module stlc:pair.
< Prove_Constraint stlc:host:proj_ty_is.
Variables: Ty1
Proj : |{ty}- pairTy Ty1 ~~> arrowTy (arrowTy Ty1 (arrowTy Ty1 Ty1)) Ty1
IsTy : is_ty (pairTy Ty1)
============================
is_ty (arrowTy (arrowTy Ty1 (arrowTy Ty1 Ty1)) Ty1)
< case IsTy.
Variables: Ty1
Proj : |{ty}- pairTy Ty1 ~~> arrowTy (arrowTy Ty1 (arrowTy Ty1 Ty1)) Ty1
H1 : is_ty Ty1
============================
is_ty (arrowTy (arrowTy Ty1 (arrowTy Ty1 Ty1)) Ty1)
< search.
Proof completed.
< Prove stlc:host:type_is.
Subgoal 6:
Variables: Ctx Ty1 T2 T1
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 (pair T1 T2)
Ty : typeOf Ctx (pair T1 T2) (pairTy Ty1) @
Ty1 : typeOf Ctx T1 Ty1 *
Ty2 : typeOf Ctx T2 Ty1 *
============================
is_ty (pairTy Ty1)
< Is: case IsT.
Subgoal 6:
Variables: Ctx Ty1 T2 T1
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 (pair T1 T2) (pairTy Ty1) @
Ty1 : typeOf Ctx T1 Ty1 *
Ty2 : typeOf Ctx T2 Ty1 *
Is : is_tm T1
Is1 : is_tm T2
============================
is_ty (pairTy Ty1)
< apply IH to _ _ Ty1.
Subgoal 6:
Variables: Ctx Ty1 T2 T1
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 (pair T1 T2) (pairTy Ty1) @
Ty1 : typeOf Ctx T1 Ty1 *
Ty2 : typeOf Ctx T2 Ty1 *
Is : is_tm T1
Is1 : is_tm T2
H1 : is_ty Ty1
============================
is_ty (pairTy Ty1)
< search.
Subgoal 7:
Variables: Ctx Ty T1
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 (fst T1)
Ty : typeOf Ctx (fst T1) Ty @
Ty1 : typeOf Ctx T1 (pairTy Ty) *
============================
is_ty Ty
< Is: case IsT.
Subgoal 7:
Variables: Ctx Ty T1
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 (fst T1) Ty @
Ty1 : typeOf Ctx T1 (pairTy Ty) *
Is : is_tm T1
============================
is_ty Ty
< IsTy: apply IH to _ _ Ty1.
Subgoal 7:
Variables: Ctx Ty T1
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 (fst T1) Ty @
Ty1 : typeOf Ctx T1 (pairTy Ty) *
Is : is_tm T1
IsTy : is_ty (pairTy Ty)
============================
is_ty Ty
< case IsTy.
Subgoal 7:
Variables: Ctx Ty T1
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 (fst T1) Ty @
Ty1 : typeOf Ctx T1 (pairTy Ty) *
Is : is_tm T1
H1 : is_ty Ty
============================
is_ty Ty
< search.
Subgoal 8:
Variables: Ctx Ty T1
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 (snd T1)
Ty : typeOf Ctx (snd T1) Ty @
Ty1 : typeOf Ctx T1 (pairTy Ty) *
============================
is_ty Ty
< Is: case IsT.
Subgoal 8:
Variables: Ctx Ty T1
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 (snd T1) Ty @
Ty1 : typeOf Ctx T1 (pairTy Ty) *
Is : is_tm T1
============================
is_ty Ty
< IsTy: apply IH to _ _ Ty1.
Subgoal 8:
Variables: Ctx Ty T1
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 (snd T1) Ty @
Ty1 : typeOf Ctx T1 (pairTy Ty) *
Is : is_tm T1
IsTy : is_ty (pairTy Ty)
============================
is_ty Ty
< case IsTy.
Subgoal 8:
Variables: Ctx Ty T1
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 (snd T1) Ty @
Ty1 : typeOf Ctx T1 (pairTy Ty) *
Is : is_tm T1
H1 : is_ty Ty
============================
is_ty Ty
< search.
Proof completed.
< Prove_Constraint stlc:host:proj_is.
Subgoal 1:
Variables: Ctx T2 T1 Ty
Proj : Ctx |{tm}- pair T1 T2 ~~> app (app (abs "A" Ty (abs "B" Ty (abs "S" (arrowTy Ty (arrowTy Ty Ty)) (app (app (var "S") (var "A")) (var "B"))))) T1) T2
IsCtx : is_list (is_pair is_string is_ty) Ctx
IsT : is_tm (pair T1 T2)
Proj1 : typeOf Ctx T1 Ty
============================
is_tm (app (app (abs "A" Ty (abs "B" Ty (abs "S" (arrowTy Ty (arrowTy Ty Ty)) (app (app (var "S") (var "A")) (var "B"))))) T1) T2)
< case IsT.
Subgoal 1:
Variables: Ctx T2 T1 Ty
Proj : Ctx |{tm}- pair T1 T2 ~~> app (app (abs "A" Ty (abs "B" Ty (abs "S" (arrowTy Ty (arrowTy Ty Ty)) (app (app (var "S") (var "A")) (var "B"))))) T1) T2
IsCtx : is_list (is_pair is_string is_ty) Ctx
Proj1 : typeOf Ctx T1 Ty
H1 : is_tm T1
H2 : is_tm T2
============================
is_tm (app (app (abs "A" Ty (abs "B" Ty (abs "S" (arrowTy Ty (arrowTy Ty Ty)) (app (app (var "S") (var "A")) (var "B"))))) T1) T2)
< apply type_is to _ _ Proj1.
Subgoal 1:
Variables: Ctx T2 T1 Ty
Proj : Ctx |{tm}- pair T1 T2 ~~> app (app (abs "A" Ty (abs "B" Ty (abs "S" (arrowTy Ty (arrowTy Ty Ty)) (app (app (var "S") (var "A")) (var "B"))))) T1) T2
IsCtx : is_list (is_pair is_string is_ty) Ctx
Proj1 : typeOf Ctx T1 Ty
H1 : is_tm T1
H2 : is_tm T2
H3 : is_ty Ty
============================
is_tm (app (app (abs "A" Ty (abs "B" Ty (abs "S" (arrowTy Ty (arrowTy Ty Ty)) (app (app (var "S") (var "A")) (var "B"))))) T1) T2)
< search 11.
Subgoal 2:
Variables: Ctx Ty T1
Proj : Ctx |{tm}- fst T1 ~~> app T1 (abs "A" Ty (abs "B" Ty (var "A")))
IsCtx : is_list (is_pair is_string is_ty) Ctx
IsT : is_tm (fst T1)
Proj1 : typeOf Ctx T1 (pairTy Ty)
============================
is_tm (app T1 (abs "A" Ty (abs "B" Ty (var "A"))))
< case IsT.
Subgoal 2:
Variables: Ctx Ty T1
Proj : Ctx |{tm}- fst T1 ~~> app T1 (abs "A" Ty (abs "B" Ty (var "A")))
IsCtx : is_list (is_pair is_string is_ty) Ctx
Proj1 : typeOf Ctx T1 (pairTy Ty)
H1 : is_tm T1
============================
is_tm (app T1 (abs "A" Ty (abs "B" Ty (var "A"))))
< IsTy: apply type_is to _ _ Proj1.
Subgoal 2:
Variables: Ctx Ty T1
Proj : Ctx |{tm}- fst T1 ~~> app T1 (abs "A" Ty (abs "B" Ty (var "A")))
IsCtx : is_list (is_pair is_string is_ty) Ctx
Proj1 : typeOf Ctx T1 (pairTy Ty)
H1 : is_tm T1
IsTy : is_ty (pairTy Ty)
============================
is_tm (app T1 (abs "A" Ty (abs "B" Ty (var "A"))))
< case IsTy.
Subgoal 2:
Variables: Ctx Ty T1
Proj : Ctx |{tm}- fst T1 ~~> app T1 (abs "A" Ty (abs "B" Ty (var "A")))
IsCtx : is_list (is_pair is_string is_ty) Ctx
Proj1 : typeOf Ctx T1 (pairTy Ty)
H1 : is_tm T1
H2 : is_ty Ty
============================
is_tm (app T1 (abs "A" Ty (abs "B" Ty (var "A"))))
< search 7.
Subgoal 3:
Variables: Ctx Ty T1
Proj : Ctx |{tm}- snd T1 ~~> app T1 (abs "A" Ty (abs "B" Ty (var "B")))
IsCtx : is_list (is_pair is_string is_ty) Ctx
IsT : is_tm (snd T1)
Proj1 : typeOf Ctx T1 (pairTy Ty)
============================
is_tm (app T1 (abs "A" Ty (abs "B" Ty (var "B"))))
< case IsT.
Subgoal 3:
Variables: Ctx Ty T1
Proj : Ctx |{tm}- snd T1 ~~> app T1 (abs "A" Ty (abs "B" Ty (var "B")))
IsCtx : is_list (is_pair is_string is_ty) Ctx
Proj1 : typeOf Ctx T1 (pairTy Ty)
H1 : is_tm T1
============================
is_tm (app T1 (abs "A" Ty (abs "B" Ty (var "B"))))
< IsTy: apply type_is to _ _ Proj1.
Subgoal 3:
Variables: Ctx Ty T1
Proj : Ctx |{tm}- snd T1 ~~> app T1 (abs "A" Ty (abs "B" Ty (var "B")))
IsCtx : is_list (is_pair is_string is_ty) Ctx
Proj1 : typeOf Ctx T1 (pairTy Ty)
H1 : is_tm T1
IsTy : is_ty (pairTy Ty)
============================
is_tm (app T1 (abs "A" Ty (abs "B" Ty (var "B"))))
< case IsTy.
Subgoal 3:
Variables: Ctx Ty T1
Proj : Ctx |{tm}- snd T1 ~~> app T1 (abs "A" Ty (abs "B" Ty (var "B")))
IsCtx : is_list (is_pair is_string is_ty) Ctx
Proj1 : typeOf Ctx T1 (pairTy Ty)
H1 : is_tm T1
H2 : is_ty Ty
============================
is_tm (app T1 (abs "A" Ty (abs "B" Ty (var "B"))))
< search 7.
Proof completed.
< Prove stlc:host:type_unique.
Subgoal 6:
Variables: Ctx TyB Ty T2 T1
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 (pair T1 T2)
TyA : typeOf Ctx (pair T1 T2) (pairTy Ty) @
TyB : typeOf Ctx (pair T1 T2) TyB
TyA1 : typeOf Ctx T1 Ty *
TyA2 : typeOf Ctx T2 Ty *
============================
pairTy Ty = TyB
< case IsT.
Subgoal 6:
Variables: Ctx TyB Ty T2 T1
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 (pair T1 T2) (pairTy Ty) @
TyB : typeOf Ctx (pair T1 T2) TyB
TyA1 : typeOf Ctx T1 Ty *
TyA2 : typeOf Ctx T2 Ty *
H1 : is_tm T1
H2 : is_tm T2
============================
pairTy Ty = TyB
< TyB: case TyB.
Subgoal 6:
Variables: Ctx Ty T2 T1 Ty1
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 (pair T1 T2) (pairTy Ty) @
TyA1 : typeOf Ctx T1 Ty *
TyA2 : typeOf Ctx T2 Ty *
H1 : is_tm T1
H2 : is_tm T2
TyB : typeOf Ctx T1 Ty1
TyB1 : typeOf Ctx T2 Ty1
============================
pairTy Ty = pairTy Ty1
< apply IH to _ _ TyA1 TyB.
Subgoal 6:
Variables: Ctx T2 T1 Ty1
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 (pair T1 T2) (pairTy Ty1) @
TyA1 : typeOf Ctx T1 Ty1 *
TyA2 : typeOf Ctx T2 Ty1 *
H1 : is_tm T1
H2 : is_tm T2
TyB : typeOf Ctx T1 Ty1
TyB1 : typeOf Ctx T2 Ty1
============================
pairTy Ty1 = pairTy Ty1
< search.
Subgoal 7:
Variables: Ctx TyA TyB T1
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 (fst T1)
TyA : typeOf Ctx (fst T1) TyA @
TyB : typeOf Ctx (fst T1) TyB
TyA1 : typeOf Ctx T1 (pairTy TyA) *
============================
TyA = TyB
< case IsT.
Subgoal 7:
Variables: Ctx TyA TyB T1
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 (fst T1) TyA @
TyB : typeOf Ctx (fst T1) TyB
TyA1 : typeOf Ctx T1 (pairTy TyA) *
H1 : is_tm T1
============================
TyA = TyB
< TyB: case TyB.
Subgoal 7:
Variables: Ctx TyA TyB T1
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 (fst T1) TyA @
TyA1 : typeOf Ctx T1 (pairTy TyA) *
H1 : is_tm T1
TyB : typeOf Ctx T1 (pairTy TyB)
============================
TyA = TyB
< apply IH to _ _ TyA1 TyB.
Subgoal 7:
Variables: Ctx TyB T1
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 (fst T1) TyB @
TyA1 : typeOf Ctx T1 (pairTy TyB) *
H1 : is_tm T1
TyB : typeOf Ctx T1 (pairTy TyB)
============================
TyB = TyB
< search.
Subgoal 8:
Variables: Ctx TyA TyB T1
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 (snd T1)
TyA : typeOf Ctx (snd T1) TyA @
TyB : typeOf Ctx (snd T1) TyB
TyA1 : typeOf Ctx T1 (pairTy TyA) *
============================
TyA = TyB
< case IsT.
Subgoal 8:
Variables: Ctx TyA TyB T1
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 (snd T1) TyA @
TyB : typeOf Ctx (snd T1) TyB
TyA1 : typeOf Ctx T1 (pairTy TyA) *
H1 : is_tm T1
============================
TyA = TyB
< TyB: case TyB.
Subgoal 8:
Variables: Ctx TyA TyB T1
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 (snd T1) TyA @
TyA1 : typeOf Ctx T1 (pairTy TyA) *
H1 : is_tm T1
TyB : typeOf Ctx T1 (pairTy TyB)
============================
TyA = TyB
< apply IH to _ _ TyA1 TyB.
Subgoal 8:
Variables: Ctx TyB T1
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 (snd T1) TyB @
TyA1 : typeOf Ctx T1 (pairTy TyB) *
H1 : is_tm T1
TyB : typeOf Ctx T1 (pairTy TyB)
============================
TyB = TyB
< search.
Proof completed.
< Prove_Constraint stlc:host:proj_ty_unique.
Variables: TyB Ty1
Hyp : |{ty}- pairTy Ty1 ~~> arrowTy (arrowTy Ty1 (arrowTy Ty1 Ty1)) Ty1
Hyp1 : |{ty}- pairTy Ty1 ~~> TyB
Hyp2 : is_ty (pairTy Ty1)
============================
arrowTy (arrowTy Ty1 (arrowTy Ty1 Ty1)) Ty1 = TyB
< case Hyp1.
Variables: Ty1
Hyp : |{ty}- pairTy Ty1 ~~> arrowTy (arrowTy Ty1 (arrowTy Ty1 Ty1)) Ty1
Hyp2 : is_ty (pairTy Ty1)
============================
arrowTy (arrowTy Ty1 (arrowTy Ty1 Ty1)) Ty1 = arrowTy (arrowTy Ty1 (arrowTy Ty1 Ty1)) Ty1
< search.
Proof completed.
< Prove_Constraint stlc:host:proj_tm_unique.
Subgoal 1:
Variables: Ctx TB T2 T1 Ty
Hyp : Ctx |{tm}- pair T1 T2 ~~> app (app (abs "A" Ty (abs "B" Ty (abs "S" (arrowTy Ty (arrowTy Ty Ty)) (app (app (var "S") (var "A")) (var "B"))))) T1) T2
Hyp1 : Ctx |{tm}- pair T1 T2 ~~> TB
Hyp2 : is_tm (pair T1 T2)
Hyp3 : is_list (is_pair is_string is_ty) Ctx
Hyp4 : typeOf Ctx T1 Ty
============================
app (app (abs "A" Ty (abs "B" Ty (abs "S" (arrowTy Ty (arrowTy Ty Ty)) (app (app (var "S") (var "A")) (var "B"))))) T1) T2 = TB
< case Hyp1.
Subgoal 1:
Variables: Ctx T2 T1 Ty Ty1
Hyp : Ctx |{tm}- pair T1 T2 ~~> app (app (abs "A" Ty (abs "B" Ty (abs "S" (arrowTy Ty (arrowTy Ty Ty)) (app (app (var "S") (var "A")) (var "B"))))) T1) T2
Hyp2 : is_tm (pair T1 T2)
Hyp3 : is_list (is_pair is_string is_ty) Ctx
Hyp4 : typeOf Ctx T1 Ty
H1 : typeOf Ctx T1 Ty1
============================
app (app (abs "A" Ty (abs "B" Ty (abs "S" (arrowTy Ty (arrowTy Ty Ty)) (app (app (var "S") (var "A")) (var "B"))))) T1) T2 = app (app (abs "A" Ty1 (abs "B" Ty1 (abs "S" (arrowTy Ty1 (arrowTy Ty1 Ty1)) (app (app (var "S") (var "A")) (var "B"))))) T1) T2
< case Hyp2.
Subgoal 1:
Variables: Ctx T2 T1 Ty Ty1
Hyp : Ctx |{tm}- pair T1 T2 ~~> app (app (abs "A" Ty (abs "B" Ty (abs "S" (arrowTy Ty (arrowTy Ty Ty)) (app (app (var "S") (var "A")) (var "B"))))) T1) T2
Hyp3 : is_list (is_pair is_string is_ty) Ctx
Hyp4 : typeOf Ctx T1 Ty
H1 : typeOf Ctx T1 Ty1
H2 : is_tm T1
H3 : is_tm T2
============================
app (app (abs "A" Ty (abs "B" Ty (abs "S" (arrowTy Ty (arrowTy Ty Ty)) (app (app (var "S") (var "A")) (var "B"))))) T1) T2 = app (app (abs "A" Ty1 (abs "B" Ty1 (abs "S" (arrowTy Ty1 (arrowTy Ty1 Ty1)) (app (app (var "S") (var "A")) (var "B"))))) T1) T2
< apply type_unique to _ _ Hyp4 H1.
Subgoal 1:
Variables: Ctx T2 T1 Ty1
Hyp : Ctx |{tm}- pair T1 T2 ~~> app (app (abs "A" Ty1 (abs "B" Ty1 (abs "S" (arrowTy Ty1 (arrowTy Ty1 Ty1)) (app (app (var "S") (var "A")) (var "B"))))) T1) T2
Hyp3 : is_list (is_pair is_string is_ty) Ctx
Hyp4 : typeOf Ctx T1 Ty1
H1 : typeOf Ctx T1 Ty1
H2 : is_tm T1
H3 : is_tm T2
============================
app (app (abs "A" Ty1 (abs "B" Ty1 (abs "S" (arrowTy Ty1 (arrowTy Ty1 Ty1)) (app (app (var "S") (var "A")) (var "B"))))) T1) T2 = app (app (abs "A" Ty1 (abs "B" Ty1 (abs "S" (arrowTy Ty1 (arrowTy Ty1 Ty1)) (app (app (var "S") (var "A")) (var "B"))))) T1) T2
< search.
Subgoal 2:
Variables: Ctx TB Ty T1
Hyp : Ctx |{tm}- fst T1 ~~> app T1 (abs "A" Ty (abs "B" Ty (var "A")))
Hyp1 : Ctx |{tm}- fst T1 ~~> TB
Hyp2 : is_tm (fst T1)
Hyp3 : is_list (is_pair is_string is_ty) Ctx
Hyp4 : typeOf Ctx T1 (pairTy Ty)
============================
app T1 (abs "A" Ty (abs "B" Ty (var "A"))) = TB
< case Hyp1.
Subgoal 2:
Variables: Ctx Ty T1 Ty1
Hyp : Ctx |{tm}- fst T1 ~~> app T1 (abs "A" Ty (abs "B" Ty (var "A")))
Hyp2 : is_tm (fst T1)
Hyp3 : is_list (is_pair is_string is_ty) Ctx
Hyp4 : typeOf Ctx T1 (pairTy Ty)
H1 : typeOf Ctx T1 (pairTy Ty1)
============================
app T1 (abs "A" Ty (abs "B" Ty (var "A"))) = app T1 (abs "A" Ty1 (abs "B" Ty1 (var "A")))
< case Hyp2.
Subgoal 2:
Variables: Ctx Ty T1 Ty1
Hyp : Ctx |{tm}- fst T1 ~~> app T1 (abs "A" Ty (abs "B" Ty (var "A")))
Hyp3 : is_list (is_pair is_string is_ty) Ctx
Hyp4 : typeOf Ctx T1 (pairTy Ty)
H1 : typeOf Ctx T1 (pairTy Ty1)
H2 : is_tm T1
============================
app T1 (abs "A" Ty (abs "B" Ty (var "A"))) = app T1 (abs "A" Ty1 (abs "B" Ty1 (var "A")))
< apply type_unique to _ _ Hyp4 H1.
Subgoal 2:
Variables: Ctx T1 Ty1
Hyp : Ctx |{tm}- fst T1 ~~> app T1 (abs "A" Ty1 (abs "B" Ty1 (var "A")))
Hyp3 : is_list (is_pair is_string is_ty) Ctx
Hyp4 : typeOf Ctx T1 (pairTy Ty1)
H1 : typeOf Ctx T1 (pairTy Ty1)
H2 : is_tm T1
============================
app T1 (abs "A" Ty1 (abs "B" Ty1 (var "A"))) = app T1 (abs "A" Ty1 (abs "B" Ty1 (var "A")))
< search.
Subgoal 3:
Variables: Ctx TB Ty T1
Hyp : Ctx |{tm}- snd T1 ~~> app T1 (abs "A" Ty (abs "B" Ty (var "B")))
Hyp1 : Ctx |{tm}- snd T1 ~~> TB
Hyp2 : is_tm (snd T1)
Hyp3 : is_list (is_pair is_string is_ty) Ctx
Hyp4 : typeOf Ctx T1 (pairTy Ty)
============================
app T1 (abs "A" Ty (abs "B" Ty (var "B"))) = TB
< case Hyp1.
Subgoal 3:
Variables: Ctx Ty T1 Ty1
Hyp : Ctx |{tm}- snd T1 ~~> app T1 (abs "A" Ty (abs "B" Ty (var "B")))
Hyp2 : is_tm (snd T1)
Hyp3 : is_list (is_pair is_string is_ty) Ctx
Hyp4 : typeOf Ctx T1 (pairTy Ty)
H1 : typeOf Ctx T1 (pairTy Ty1)
============================
app T1 (abs "A" Ty (abs "B" Ty (var "B"))) = app T1 (abs "A" Ty1 (abs "B" Ty1 (var "B")))
< case Hyp2.
Subgoal 3:
Variables: Ctx Ty T1 Ty1
Hyp : Ctx |{tm}- snd T1 ~~> app T1 (abs "A" Ty (abs "B" Ty (var "B")))
Hyp3 : is_list (is_pair is_string is_ty) Ctx
Hyp4 : typeOf Ctx T1 (pairTy Ty)
H1 : typeOf Ctx T1 (pairTy Ty1)
H2 : is_tm T1
============================
app T1 (abs "A" Ty (abs "B" Ty (var "B"))) = app T1 (abs "A" Ty1 (abs "B" Ty1 (var "B")))
< apply type_unique to _ _ Hyp4 H1.
Subgoal 3:
Variables: Ctx T1 Ty1
Hyp : Ctx |{tm}- snd T1 ~~> app T1 (abs "A" Ty1 (abs "B" Ty1 (var "B")))
Hyp3 : is_list (is_pair is_string is_ty) Ctx
Hyp4 : typeOf Ctx T1 (pairTy Ty1)
H1 : typeOf Ctx T1 (pairTy Ty1)
H2 : is_tm T1
============================
app T1 (abs "A" Ty1 (abs "B" Ty1 (var "B"))) = app T1 (abs "A" Ty1 (abs "B" Ty1 (var "B")))
< search.
Proof completed.
< Prove stlc:host:subst_is.
Subgoal 8:
Variables: X R T21 T11 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 (pair T1 T2)
IsX : is_string X
IsR : is_tm R
S : subst X R (pair T1 T2) (pair T11 T21) @
S1 : subst X R T1 T11 *
S2 : subst X R T2 T21 *
============================
is_tm (pair T11 T21)
< Is: case IsT.
Subgoal 8:
Variables: X R T21 T11 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 (pair T1 T2) (pair T11 T21) @
S1 : subst X R T1 T11 *
S2 : subst X R T2 T21 *
Is : is_tm T1
Is1 : is_tm T2
============================
is_tm (pair T11 T21)
< apply IH to _ _ _ S1.
Subgoal 8:
Variables: X R T21 T11 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 (pair T1 T2) (pair T11 T21) @
S1 : subst X R T1 T11 *
S2 : subst X R T2 T21 *
Is : is_tm T1
Is1 : is_tm T2
H1 : is_tm T11
============================
is_tm (pair T11 T21)
< apply IH to _ _ _ S2.
Subgoal 8:
Variables: X R T21 T11 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 (pair T1 T2) (pair T11 T21) @
S1 : subst X R T1 T11 *
S2 : subst X R T2 T21 *
Is : is_tm T1
Is1 : is_tm T2
H1 : is_tm T11
H2 : is_tm T21
============================
is_tm (pair T11 T21)
< search.
Subgoal 9:
Variables: X R 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 (fst T1)
IsX : is_string X
IsR : is_tm R
S : subst X R (fst T1) (fst T2) @
S1 : subst X R T1 T2 *
============================
is_tm (fst T2)
< Is: case IsT.
Subgoal 9:
Variables: X R 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 (fst T1) (fst T2) @
S1 : subst X R T1 T2 *
Is : is_tm T1
============================
is_tm (fst T2)
< apply IH to _ _ _ S1.
Subgoal 9:
Variables: X R 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 (fst T1) (fst T2) @
S1 : subst X R T1 T2 *
Is : is_tm T1
H1 : is_tm T2
============================
is_tm (fst T2)
< search.
Subgoal 10:
Variables: X R 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 (snd T1)
IsX : is_string X
IsR : is_tm R
S : subst X R (snd T1) (snd T2) @
S1 : subst X R T1 T2 *
============================
is_tm (snd T2)
< Is: case IsT.
Subgoal 10:
Variables: X R 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 (snd T1) (snd T2) @
S1 : subst X R T1 T2 *
Is : is_tm T1
============================
is_tm (snd T2)
< apply IH to _ _ _ S1.
Subgoal 10:
Variables: X R 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 (snd T1) (snd T2) @
S1 : subst X R T1 T2 *
Is : is_tm T1
H1 : is_tm T2
============================
is_tm (snd T2)
< search.
Proof completed.
< Prove stlc:host:eval_is.
Subgoal 7:
Variables: T2 T11 T1
IH : forall T T', is_tm T -> eval T T' * -> is_tm T'
IsT : is_tm (pair T1 T2)
Ev : eval (pair T1 T2) (pair T11 T2) @
Ev1 : eval T1 T11 *
============================
is_tm (pair T11 T2)
< Is: case IsT.
Subgoal 7:
Variables: T2 T11 T1
IH : forall T T', is_tm T -> eval T T' * -> is_tm T'
Ev : eval (pair T1 T2) (pair T11 T2) @
Ev1 : eval T1 T11 *
Is : is_tm T1
Is1 : is_tm T2
============================
is_tm (pair T11 T2)
< apply IH to _ Ev1.
Subgoal 7:
Variables: T2 T11 T1
IH : forall T T', is_tm T -> eval T T' * -> is_tm T'
Ev : eval (pair T1 T2) (pair T11 T2) @
Ev1 : eval T1 T11 *
Is : is_tm T1
Is1 : is_tm T2
H1 : is_tm T11
============================
is_tm (pair T11 T2)
< search.
Subgoal 8:
Variables: T21 T1 T2
IH : forall T T', is_tm T -> eval T T' * -> is_tm T'
IsT : is_tm (pair T1 T2)
Ev : eval (pair T1 T2) (pair T1 T21) @
Ev1 : value T1
Ev2 : eval T2 T21 *
============================
is_tm (pair T1 T21)
< Is: case IsT.
Subgoal 8:
Variables: T21 T1 T2
IH : forall T T', is_tm T -> eval T T' * -> is_tm T'
Ev : eval (pair T1 T2) (pair T1 T21) @
Ev1 : value T1
Ev2 : eval T2 T21 *
Is : is_tm T1
Is1 : is_tm T2
============================
is_tm (pair T1 T21)
< apply IH to _ Ev2.
Subgoal 8:
Variables: T21 T1 T2
IH : forall T T', is_tm T -> eval T T' * -> is_tm T'
Ev : eval (pair T1 T2) (pair T1 T21) @
Ev1 : value T1
Ev2 : eval T2 T21 *
Is : is_tm T1
Is1 : is_tm T2
H1 : is_tm T21
============================
is_tm (pair T1 T21)
< search.
Subgoal 9:
Variables: T2 T1
IH : forall T T', is_tm T -> eval T T' * -> is_tm T'
IsT : is_tm (fst T1)
Ev : eval (fst T1) (fst T2) @
Ev1 : eval T1 T2 *
============================
is_tm (fst T2)
< Is: case IsT.
Subgoal 9:
Variables: T2 T1
IH : forall T T', is_tm T -> eval T T' * -> is_tm T'
Ev : eval (fst T1) (fst T2) @
Ev1 : eval T1 T2 *
Is : is_tm T1
============================
is_tm (fst T2)
< apply IH to _ Ev1.
Subgoal 9:
Variables: T2 T1
IH : forall T T', is_tm T -> eval T T' * -> is_tm T'
Ev : eval (fst T1) (fst T2) @
Ev1 : eval T1 T2 *
Is : is_tm T1
H1 : is_tm T2
============================
is_tm (fst T2)
< search.
Subgoal 10:
Variables: T' T2
IH : forall T T', is_tm T -> eval T T' * -> is_tm T'
IsT : is_tm (fst (pair T' T2))
Ev : eval (fst (pair T' T2)) T' @
Ev1 : value (pair T' T2)
============================
is_tm T'
< Is: case IsT.
Subgoal 10:
Variables: T' T2
IH : forall T T', is_tm T -> eval T T' * -> is_tm T'
Ev : eval (fst (pair T' T2)) T' @
Ev1 : value (pair T' T2)
Is : is_tm (pair T' T2)
============================
is_tm T'
< case Is.
Subgoal 10:
Variables: T' T2
IH : forall T T', is_tm T -> eval T T' * -> is_tm T'
Ev : eval (fst (pair T' T2)) T' @
Ev1 : value (pair T' T2)
H1 : is_tm T'
H2 : is_tm T2
============================
is_tm T'
< search.
Subgoal 11:
Variables: T2 T1
IH : forall T T', is_tm T -> eval T T' * -> is_tm T'
IsT : is_tm (snd T1)
Ev : eval (snd T1) (snd T2) @
Ev1 : eval T1 T2 *
============================
is_tm (snd T2)
< Is: case IsT.
Subgoal 11:
Variables: T2 T1
IH : forall T T', is_tm T -> eval T T' * -> is_tm T'
Ev : eval (snd T1) (snd T2) @
Ev1 : eval T1 T2 *
Is : is_tm T1
============================
is_tm (snd T2)
< apply IH to _ Ev1.
Subgoal 11:
Variables: T2 T1
IH : forall T T', is_tm T -> eval T T' * -> is_tm T'
Ev : eval (snd T1) (snd T2) @
Ev1 : eval T1 T2 *
Is : is_tm T1
H1 : is_tm T2
============================
is_tm (snd T2)
< search.
Subgoal 12:
Variables: T' T1
IH : forall T T', is_tm T -> eval T T' * -> is_tm T'
IsT : is_tm (snd (pair T1 T'))
Ev : eval (snd (pair T1 T')) T' @
Ev1 : value (pair T1 T')
============================
is_tm T'
< Is: case IsT.
Subgoal 12:
Variables: T' T1
IH : forall T T', is_tm T -> eval T T' * -> is_tm T'
Ev : eval (snd (pair T1 T')) T' @
Ev1 : value (pair T1 T')
Is : is_tm (pair T1 T')
============================
is_tm T'
< case Is.
Subgoal 12:
Variables: T' T1
IH : forall T T', is_tm T -> eval T T' * -> is_tm T'
Ev : eval (snd (pair T1 T')) T' @
Ev1 : value (pair T1 T')
H1 : is_tm T1
H2 : is_tm T'
============================
is_tm T'
< search.
Proof completed.
< Prove stlc:host:subst_unique.
Subgoal 8:
Variables: X R VB T21 T11 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 (pair T1 T2) (pair T11 T21) @
SB : subst X R (pair T1 T2) VB
SA1 : subst X R T1 T11 *
SA2 : subst X R T2 T21 *
============================
pair T11 T21 = VB
< SB: case SB.
Subgoal 8:
Variables: X R T21 T11 T2 T1 T6 T5
IH : forall X R T VA VB, subst X R T VA * -> subst X R T VB -> VA = VB
SA : subst X R (pair T1 T2) (pair T11 T21) @
SA1 : subst X R T1 T11 *
SA2 : subst X R T2 T21 *
SB : subst X R T1 T5
SB1 : subst X R T2 T6
============================
pair T11 T21 = pair T5 T6
< apply IH to SA1 SB.
Subgoal 8:
Variables: X R T21 T2 T1 T6 T5
IH : forall X R T VA VB, subst X R T VA * -> subst X R T VB -> VA = VB
SA : subst X R (pair T1 T2) (pair T5 T21) @
SA1 : subst X R T1 T5 *
SA2 : subst X R T2 T21 *
SB : subst X R T1 T5
SB1 : subst X R T2 T6
============================
pair T5 T21 = pair T5 T6
< apply IH to SA2 SB1.
Subgoal 8:
Variables: X R T2 T1 T6 T5
IH : forall X R T VA VB, subst X R T VA * -> subst X R T VB -> VA = VB
SA : subst X R (pair T1 T2) (pair T5 T6) @
SA1 : subst X R T1 T5 *
SA2 : subst X R T2 T6 *
SB : subst X R T1 T5
SB1 : subst X R T2 T6
============================
pair T5 T6 = pair T5 T6
< search.
Subgoal 9:
Variables: X R VB 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 (fst T1) (fst T2) @
SB : subst X R (fst T1) VB
SA1 : subst X R T1 T2 *
============================
fst T2 = VB
< SB: case SB.
Subgoal 9:
Variables: X R T2 T1 T4
IH : forall X R T VA VB, subst X R T VA * -> subst X R T VB -> VA = VB
SA : subst X R (fst T1) (fst T2) @
SA1 : subst X R T1 T2 *
SB : subst X R T1 T4
============================
fst T2 = fst T4
< apply IH to SA1 SB.
Subgoal 9:
Variables: X R T1 T4
IH : forall X R T VA VB, subst X R T VA * -> subst X R T VB -> VA = VB
SA : subst X R (fst T1) (fst T4) @
SA1 : subst X R T1 T4 *
SB : subst X R T1 T4
============================
fst T4 = fst T4
< search.
Subgoal 10:
Variables: X R VB 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 (snd T1) (snd T2) @
SB : subst X R (snd T1) VB
SA1 : subst X R T1 T2 *
============================
snd T2 = VB
< SB: case SB.
Subgoal 10:
Variables: X R T2 T1 T4
IH : forall X R T VA VB, subst X R T VA * -> subst X R T VB -> VA = VB
SA : subst X R (snd T1) (snd T2) @
SA1 : subst X R T1 T2 *
SB : subst X R T1 T4
============================
snd T2 = snd T4
< apply IH to SA1 SB.
Subgoal 10:
Variables: X R T1 T4
IH : forall X R T VA VB, subst X R T VA * -> subst X R T VB -> VA = VB
SA : subst X R (snd T1) (snd T4) @
SA1 : subst X R T1 T4 *
SB : subst X R T1 T4
============================
snd T4 = snd T4
< search.
Proof completed.
< Prove stlc:host:value_eval_false.
Subgoal 3:
Variables: V T2 T1
IH : forall T V, value T * -> eval T V -> false
Val : value (pair T1 T2) @
Ev : eval (pair T1 T2) V
Val1 : value T1 *
Val2 : value T2 *
============================
false
< Ev: case Ev.
Subgoal 3.1:
Variables: T2 T1 T11
IH : forall T V, value T * -> eval T V -> false
Val : value (pair T1 T2) @
Val1 : value T1 *
Val2 : value T2 *
Ev : eval T1 T11
============================
false
< apply IH to Val1 Ev.
Subgoal 3.2:
Variables: T2 T1 T21
IH : forall T V, value T * -> eval T V -> false
Val : value (pair T1 T2) @
Val1 : value T1 *
Val2 : value T2 *
Ev : value T1
Ev1 : eval T2 T21
============================
false
< apply IH to Val2 Ev1.
Proof completed.
< Prove stlc:host:eval_unique.
Subgoal 7:
Variables: VB T2 T11 T1
IH : forall T VA VB, eval T VA * -> eval T VB -> VA = VB
EvA : eval (pair T1 T2) (pair T11 T2) @
EvB : eval (pair T1 T2) VB
EvA1 : eval T1 T11 *
============================
pair T11 T2 = VB
< EvB: case EvB.
Subgoal 7.1:
Variables: T2 T11 T1 T5
IH : forall T VA VB, eval T VA * -> eval T VB -> VA = VB
EvA : eval (pair T1 T2) (pair T11 T2) @
EvA1 : eval T1 T11 *
EvB : eval T1 T5
============================
pair T11 T2 = pair T5 T2
< apply IH to EvA1 EvB.
Subgoal 7.1:
Variables: T2 T1 T5
IH : forall T VA VB, eval T VA * -> eval T VB -> VA = VB
EvA : eval (pair T1 T2) (pair T5 T2) @
EvA1 : eval T1 T5 *
EvB : eval T1 T5
============================
pair T5 T2 = pair T5 T2
< search.
Subgoal 7.2:
Variables: T2 T11 T1 T21
IH : forall T VA VB, eval T VA * -> eval T VB -> VA = VB
EvA : eval (pair T1 T2) (pair T11 T2) @
EvA1 : eval T1 T11 *
EvB : value T1
EvB1 : eval T2 T21
============================
pair T11 T2 = pair T1 T21
< apply value_eval_false to EvB EvA1.
Subgoal 8:
Variables: VB T21 T1 T2
IH : forall T VA VB, eval T VA * -> eval T VB -> VA = VB
EvA : eval (pair T1 T2) (pair T1 T21) @
EvB : eval (pair T1 T2) VB
EvA1 : value T1
EvA2 : eval T2 T21 *
============================
pair T1 T21 = VB
< EvB: case EvB.
Subgoal 8.1:
Variables: T21 T1 T2 T11
IH : forall T VA VB, eval T VA * -> eval T VB -> VA = VB
EvA : eval (pair T1 T2) (pair T1 T21) @
EvA1 : value T1
EvA2 : eval T2 T21 *
EvB : eval T1 T11
============================
pair T1 T21 = pair T11 T2
< apply value_eval_false to EvA1 EvB.
Subgoal 8.2:
Variables: T21 T1 T2 T5
IH : forall T VA VB, eval T VA * -> eval T VB -> VA = VB
EvA : eval (pair T1 T2) (pair T1 T21) @
EvA1 : value T1
EvA2 : eval T2 T21 *
EvB : value T1
EvB1 : eval T2 T5
============================
pair T1 T21 = pair T1 T5
< apply IH to EvA2 EvB1.
Subgoal 8.2:
Variables: T1 T2 T5
IH : forall T VA VB, eval T VA * -> eval T VB -> VA = VB
EvA : eval (pair T1 T2) (pair T1 T5) @
EvA1 : value T1
EvA2 : eval T2 T5 *
EvB : value T1
EvB1 : eval T2 T5
============================
pair T1 T5 = pair T1 T5
< search.
Subgoal 9:
Variables: VB T2 T1
IH : forall T VA VB, eval T VA * -> eval T VB -> VA = VB
EvA : eval (fst T1) (fst T2) @
EvB : eval (fst T1) VB
EvA1 : eval T1 T2 *
============================
fst T2 = VB
< EvB: case EvB.
Subgoal 9.1:
Variables: T2 T1 T4
IH : forall T VA VB, eval T VA * -> eval T VB -> VA = VB
EvA : eval (fst T1) (fst T2) @
EvA1 : eval T1 T2 *
EvB : eval T1 T4
============================
fst T2 = fst T4
< apply IH to EvA1 EvB.
Subgoal 9.1:
Variables: T1 T4
IH : forall T VA VB, eval T VA * -> eval T VB -> VA = VB
EvA : eval (fst T1) (fst T4) @
EvA1 : eval T1 T4 *
EvB : eval T1 T4
============================
fst T4 = fst T4
< search.
Subgoal 9.2:
Variables: VB T2 T4
IH : forall T VA VB, eval T VA * -> eval T VB -> VA = VB
EvA : eval (fst (pair VB T4)) (fst T2) @
EvA1 : eval (pair VB T4) T2 *
EvB : value (pair VB T4)
============================
fst T2 = VB
< apply value_eval_false to EvB EvA1.
Subgoal 10:
Variables: VA VB T2
IH : forall T VA VB, eval T VA * -> eval T VB -> VA = VB
EvA : eval (fst (pair VA T2)) VA @
EvB : eval (fst (pair VA T2)) VB
EvA1 : value (pair VA T2)
============================
VA = VB
< EvB: case EvB.
Subgoal 10.1:
Variables: VA T2 T3
IH : forall T VA VB, eval T VA * -> eval T VB -> VA = VB
EvA : eval (fst (pair VA T2)) VA @
EvA1 : value (pair VA T2)
EvB : eval (pair VA T2) T3
============================
VA = fst T3
< apply value_eval_false to EvA1 EvB.
Subgoal 10.2:
Variables: VB T2
IH : forall T VA VB, eval T VA * -> eval T VB -> VA = VB
EvA : eval (fst (pair VB T2)) VB @
EvA1 : value (pair VB T2)
EvB : value (pair VB T2)
============================
VB = VB
< search.
Subgoal 11:
Variables: VB T2 T1
IH : forall T VA VB, eval T VA * -> eval T VB -> VA = VB
EvA : eval (snd T1) (snd T2) @
EvB : eval (snd T1) VB
EvA1 : eval T1 T2 *
============================
snd T2 = VB
< EvB: case EvB.
Subgoal 11.1:
Variables: T2 T1 T4
IH : forall T VA VB, eval T VA * -> eval T VB -> VA = VB
EvA : eval (snd T1) (snd T2) @
EvA1 : eval T1 T2 *
EvB : eval T1 T4
============================
snd T2 = snd T4
< apply IH to EvA1 EvB.
Subgoal 11.1:
Variables: T1 T4
IH : forall T VA VB, eval T VA * -> eval T VB -> VA = VB
EvA : eval (snd T1) (snd T4) @
EvA1 : eval T1 T4 *
EvB : eval T1 T4
============================
snd T4 = snd T4
< search.
Subgoal 11.2:
Variables: VB T2 T3
IH : forall T VA VB, eval T VA * -> eval T VB -> VA = VB
EvA : eval (snd (pair T3 VB)) (snd T2) @
EvA1 : eval (pair T3 VB) T2 *
EvB : value (pair T3 VB)
============================
snd T2 = VB
< apply value_eval_false to EvB EvA1.
Subgoal 12:
Variables: VA VB T1
IH : forall T VA VB, eval T VA * -> eval T VB -> VA = VB
EvA : eval (snd (pair T1 VA)) VA @
EvB : eval (snd (pair T1 VA)) VB
EvA1 : value (pair T1 VA)
============================
VA = VB
< EvB: case EvB.
Subgoal 12.1:
Variables: VA T1 T3
IH : forall T VA VB, eval T VA * -> eval T VB -> VA = VB
EvA : eval (snd (pair T1 VA)) VA @
EvA1 : value (pair T1 VA)
EvB : eval (pair T1 VA) T3
============================
VA = snd T3
< apply value_eval_false to EvA1 EvB.
Subgoal 12.2:
Variables: VB T1
IH : forall T VA VB, eval T VA * -> eval T VB -> VA = VB
EvA : eval (snd (pair T1 VB)) VB @
EvA1 : value (pair T1 VB)
EvB : value (pair T1 VB)
============================
VB = VB
< search.
Proof completed.
< Prove stlc:host:ty_lookup.
Subgoal 6:
Variables: Ctx1 Ctx2 Ty1 T2 T1
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 (pair T1 T2) (pairTy Ty1) @
L : forall X XTy, lookup Ctx1 X XTy -> lookup Ctx2 X XTy
Ty1 : typeOf Ctx1 T1 Ty1 *
Ty2 : typeOf Ctx1 T2 Ty1 *
============================
typeOf Ctx2 (pair T1 T2) (pairTy Ty1)
< apply IH to Ty1 L.
Subgoal 6:
Variables: Ctx1 Ctx2 Ty1 T2 T1
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 (pair T1 T2) (pairTy Ty1) @
L : forall X XTy, lookup Ctx1 X XTy -> lookup Ctx2 X XTy
Ty1 : typeOf Ctx1 T1 Ty1 *
Ty2 : typeOf Ctx1 T2 Ty1 *
H1 : typeOf Ctx2 T1 Ty1
============================
typeOf Ctx2 (pair T1 T2) (pairTy Ty1)
< apply IH to Ty2 L.
Subgoal 6:
Variables: Ctx1 Ctx2 Ty1 T2 T1
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 (pair T1 T2) (pairTy Ty1) @
L : forall X XTy, lookup Ctx1 X XTy -> lookup Ctx2 X XTy
Ty1 : typeOf Ctx1 T1 Ty1 *
Ty2 : typeOf Ctx1 T2 Ty1 *
H1 : typeOf Ctx2 T1 Ty1
H2 : typeOf Ctx2 T2 Ty1
============================
typeOf Ctx2 (pair T1 T2) (pairTy Ty1)
< search.
Subgoal 7:
Variables: Ctx1 Ctx2 Ty T1
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 (fst T1) Ty @
L : forall X XTy, lookup Ctx1 X XTy -> lookup Ctx2 X XTy
Ty1 : typeOf Ctx1 T1 (pairTy Ty) *
============================
typeOf Ctx2 (fst T1) Ty
< apply IH to Ty1 L.
Subgoal 7:
Variables: Ctx1 Ctx2 Ty T1
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 (fst T1) Ty @
L : forall X XTy, lookup Ctx1 X XTy -> lookup Ctx2 X XTy
Ty1 : typeOf Ctx1 T1 (pairTy Ty) *
H1 : typeOf Ctx2 T1 (pairTy Ty)
============================
typeOf Ctx2 (fst T1) Ty
< search.
Subgoal 8:
Variables: Ctx1 Ctx2 Ty T1
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 (snd T1) Ty @
L : forall X XTy, lookup Ctx1 X XTy -> lookup Ctx2 X XTy
Ty1 : typeOf Ctx1 T1 (pairTy Ty) *
============================
typeOf Ctx2 (snd T1) Ty
< apply IH to Ty1 L.
Subgoal 8:
Variables: Ctx1 Ctx2 Ty T1
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 (snd T1) Ty @
L : forall X XTy, lookup Ctx1 X XTy -> lookup Ctx2 X XTy
Ty1 : typeOf Ctx1 T1 (pairTy Ty) *
H1 : typeOf Ctx2 T1 (pairTy Ty)
============================
typeOf Ctx2 (snd T1) Ty
< search.
Proof completed.
< Prove stlc:host:subst_type_preservation.
Subgoal 8:
Variables: Ctx X XTy Ty R T21 T11 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) (pair T1 T2) Ty
S : subst X R (pair T1 T2) (pair T11 T21) @
RTy : typeOf [] R XTy
S1 : subst X R T1 T11 *
S2 : subst X R T2 T21 *
============================
typeOf Ctx (pair T11 T21) Ty
< Ty: case TTy.
Subgoal 8:
Variables: Ctx X XTy R T21 T11 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 (pair T1 T2) (pair T11 T21) @
RTy : typeOf [] R XTy
S1 : subst X R T1 T11 *
S2 : subst X R T2 T21 *
Ty : typeOf ((X, XTy)::Ctx) T1 Ty1
Ty1 : typeOf ((X, XTy)::Ctx) T2 Ty1
============================
typeOf Ctx (pair T11 T21) (pairTy Ty1)
< apply IH to Ty S1 RTy.
Subgoal 8:
Variables: Ctx X XTy R T21 T11 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 (pair T1 T2) (pair T11 T21) @
RTy : typeOf [] R XTy
S1 : subst X R T1 T11 *
S2 : subst X R T2 T21 *
Ty : typeOf ((X, XTy)::Ctx) T1 Ty1
Ty1 : typeOf ((X, XTy)::Ctx) T2 Ty1
H1 : typeOf Ctx T11 Ty1
============================
typeOf Ctx (pair T11 T21) (pairTy Ty1)
< apply IH to Ty1 S2 RTy.
Subgoal 8:
Variables: Ctx X XTy R T21 T11 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 (pair T1 T2) (pair T11 T21) @
RTy : typeOf [] R XTy
S1 : subst X R T1 T11 *
S2 : subst X R T2 T21 *
Ty : typeOf ((X, XTy)::Ctx) T1 Ty1
Ty1 : typeOf ((X, XTy)::Ctx) T2 Ty1
H1 : typeOf Ctx T11 Ty1
H2 : typeOf Ctx T21 Ty1
============================
typeOf Ctx (pair T11 T21) (pairTy Ty1)
< search.
Subgoal 9:
Variables: Ctx X XTy Ty R 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) (fst T1) Ty
S : subst X R (fst T1) (fst T2) @
RTy : typeOf [] R XTy
S1 : subst X R T1 T2 *
============================
typeOf Ctx (fst T2) Ty
< Ty: case TTy.
Subgoal 9:
Variables: Ctx X XTy Ty R 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
S : subst X R (fst T1) (fst T2) @
RTy : typeOf [] R XTy
S1 : subst X R T1 T2 *
Ty : typeOf ((X, XTy)::Ctx) T1 (pairTy Ty)
============================
typeOf Ctx (fst T2) Ty
< apply IH to Ty S1 RTy.
Subgoal 9:
Variables: Ctx X XTy Ty R 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
S : subst X R (fst T1) (fst T2) @
RTy : typeOf [] R XTy
S1 : subst X R T1 T2 *
Ty : typeOf ((X, XTy)::Ctx) T1 (pairTy Ty)
H1 : typeOf Ctx T2 (pairTy Ty)
============================
typeOf Ctx (fst T2) Ty
< search.
Subgoal 10:
Variables: Ctx X XTy Ty R 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) (snd T1) Ty
S : subst X R (snd T1) (snd T2) @
RTy : typeOf [] R XTy
S1 : subst X R T1 T2 *
============================
typeOf Ctx (snd T2) Ty
< Ty: case TTy.
Subgoal 10:
Variables: Ctx X XTy Ty R 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
S : subst X R (snd T1) (snd T2) @
RTy : typeOf [] R XTy
S1 : subst X R T1 T2 *
Ty : typeOf ((X, XTy)::Ctx) T1 (pairTy Ty)
============================
typeOf Ctx (snd T2) Ty
< apply IH to Ty S1 RTy.
Subgoal 10:
Variables: Ctx X XTy Ty R 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
S : subst X R (snd T1) (snd T2) @
RTy : typeOf [] R XTy
S1 : subst X R T1 T2 *
Ty : typeOf ((X, XTy)::Ctx) T1 (pairTy Ty)
H1 : typeOf Ctx T2 (pairTy Ty)
============================
typeOf Ctx (snd T2) Ty
< search.
Proof completed.
< Prove stlc:host:type_preservation.
Subgoal 7:
Variables: Ty T2 T11 T1
IH : forall T Ty T', typeOf [] T Ty -> eval T T' * -> typeOf [] T' Ty
Ty : typeOf [] (pair T1 T2) Ty
Ev : eval (pair T1 T2) (pair T11 T2) @
Ev1 : eval T1 T11 *
============================
typeOf [] (pair T11 T2) Ty
< Ty: case Ty.
Subgoal 7:
Variables: T2 T11 T1 Ty1
IH : forall T Ty T', typeOf [] T Ty -> eval T T' * -> typeOf [] T' Ty
Ev : eval (pair T1 T2) (pair T11 T2) @
Ev1 : eval T1 T11 *
Ty : typeOf [] T1 Ty1
Ty1 : typeOf [] T2 Ty1
============================
typeOf [] (pair T11 T2) (pairTy Ty1)
< apply IH to Ty Ev1.
Subgoal 7:
Variables: T2 T11 T1 Ty1
IH : forall T Ty T', typeOf [] T Ty -> eval T T' * -> typeOf [] T' Ty
Ev : eval (pair T1 T2) (pair T11 T2) @
Ev1 : eval T1 T11 *
Ty : typeOf [] T1 Ty1
Ty1 : typeOf [] T2 Ty1
H1 : typeOf [] T11 Ty1
============================
typeOf [] (pair T11 T2) (pairTy Ty1)
< search.
Subgoal 8:
Variables: Ty T21 T1 T2
IH : forall T Ty T', typeOf [] T Ty -> eval T T' * -> typeOf [] T' Ty
Ty : typeOf [] (pair T1 T2) Ty
Ev : eval (pair T1 T2) (pair T1 T21) @
Ev1 : value T1
Ev2 : eval T2 T21 *
============================
typeOf [] (pair T1 T21) Ty
< Ty: case Ty.
Subgoal 8:
Variables: T21 T1 T2 Ty1
IH : forall T Ty T', typeOf [] T Ty -> eval T T' * -> typeOf [] T' Ty
Ev : eval (pair T1 T2) (pair T1 T21) @
Ev1 : value T1
Ev2 : eval T2 T21 *
Ty : typeOf [] T1 Ty1
Ty1 : typeOf [] T2 Ty1
============================
typeOf [] (pair T1 T21) (pairTy Ty1)
< apply IH to Ty1 Ev2.
Subgoal 8:
Variables: T21 T1 T2 Ty1
IH : forall T Ty T', typeOf [] T Ty -> eval T T' * -> typeOf [] T' Ty
Ev : eval (pair T1 T2) (pair T1 T21) @
Ev1 : value T1
Ev2 : eval T2 T21 *
Ty : typeOf [] T1 Ty1
Ty1 : typeOf [] T2 Ty1
H1 : typeOf [] T21 Ty1
============================
typeOf [] (pair T1 T21) (pairTy Ty1)
< search.
Subgoal 9:
Variables: Ty T2 T1
IH : forall T Ty T', typeOf [] T Ty -> eval T T' * -> typeOf [] T' Ty
Ty : typeOf [] (fst T1) Ty
Ev : eval (fst T1) (fst T2) @
Ev1 : eval T1 T2 *
============================
typeOf [] (fst T2) Ty
< Ty: case Ty.
Subgoal 9:
Variables: Ty T2 T1
IH : forall T Ty T', typeOf [] T Ty -> eval T T' * -> typeOf [] T' Ty
Ev : eval (fst T1) (fst T2) @
Ev1 : eval T1 T2 *
Ty : typeOf [] T1 (pairTy Ty)
============================
typeOf [] (fst T2) Ty
< apply IH to Ty Ev1.
Subgoal 9:
Variables: Ty T2 T1
IH : forall T Ty T', typeOf [] T Ty -> eval T T' * -> typeOf [] T' Ty
Ev : eval (fst T1) (fst T2) @
Ev1 : eval T1 T2 *
Ty : typeOf [] T1 (pairTy Ty)
H1 : typeOf [] T2 (pairTy Ty)
============================
typeOf [] (fst T2) Ty
< search.
Subgoal 10:
Variables: Ty T' T2
IH : forall T Ty T', typeOf [] T Ty -> eval T T' * -> typeOf [] T' Ty
Ty : typeOf [] (fst (pair T' T2)) Ty
Ev : eval (fst (pair T' T2)) T' @
Ev1 : value (pair T' T2)
============================
typeOf [] T' Ty
< Ty: case Ty.
Subgoal 10:
Variables: Ty T' T2
IH : forall T Ty T', typeOf [] T Ty -> eval T T' * -> typeOf [] T' Ty
Ev : eval (fst (pair T' T2)) T' @
Ev1 : value (pair T' T2)
Ty : typeOf [] (pair T' T2) (pairTy Ty)
============================
typeOf [] T' Ty
< case Ty.
Subgoal 10:
Variables: Ty T' T2
IH : forall T Ty T', typeOf [] T Ty -> eval T T' * -> typeOf [] T' Ty
Ev : eval (fst (pair T' T2)) T' @
Ev1 : value (pair T' T2)
H1 : typeOf [] T' Ty
H2 : typeOf [] T2 Ty
============================
typeOf [] T' Ty
< search.
Subgoal 11:
Variables: Ty T2 T1
IH : forall T Ty T', typeOf [] T Ty -> eval T T' * -> typeOf [] T' Ty
Ty : typeOf [] (snd T1) Ty
Ev : eval (snd T1) (snd T2) @
Ev1 : eval T1 T2 *
============================
typeOf [] (snd T2) Ty
< Ty: case Ty.
Subgoal 11:
Variables: Ty T2 T1
IH : forall T Ty T', typeOf [] T Ty -> eval T T' * -> typeOf [] T' Ty
Ev : eval (snd T1) (snd T2) @
Ev1 : eval T1 T2 *
Ty : typeOf [] T1 (pairTy Ty)
============================
typeOf [] (snd T2) Ty
< apply IH to Ty Ev1.
Subgoal 11:
Variables: Ty T2 T1
IH : forall T Ty T', typeOf [] T Ty -> eval T T' * -> typeOf [] T' Ty
Ev : eval (snd T1) (snd T2) @
Ev1 : eval T1 T2 *
Ty : typeOf [] T1 (pairTy Ty)
H1 : typeOf [] T2 (pairTy Ty)
============================
typeOf [] (snd T2) Ty
< search.
Subgoal 12:
Variables: Ty T' T1
IH : forall T Ty T', typeOf [] T Ty -> eval T T' * -> typeOf [] T' Ty
Ty : typeOf [] (snd (pair T1 T')) Ty
Ev : eval (snd (pair T1 T')) T' @
Ev1 : value (pair T1 T')
============================
typeOf [] T' Ty
< Ty: case Ty.
Subgoal 12:
Variables: Ty T' T1
IH : forall T Ty T', typeOf [] T Ty -> eval T T' * -> typeOf [] T' Ty
Ev : eval (snd (pair T1 T')) T' @
Ev1 : value (pair T1 T')
Ty : typeOf [] (pair T1 T') (pairTy Ty)
============================
typeOf [] T' Ty
< case Ty.
Subgoal 12:
Variables: Ty T' T1
IH : forall T Ty T', typeOf [] T Ty -> eval T T' * -> typeOf [] T' Ty
Ev : eval (snd (pair T1 T')) T' @
Ev1 : value (pair T1 T')
H1 : typeOf [] T1 Ty
H2 : typeOf [] T' Ty
============================
typeOf [] T' Ty
< search.
Proof completed.
< Prove stlc:host:subst_total.
Subgoal 6:
Variables: X R Tm Tm1
IH : forall X R T, is_tm T * -> is_string X -> exists S, subst X R T S
IsT : is_tm (pair Tm1 Tm) @
IsX : is_string X
IsT1 : is_tm Tm1 *
IsT2 : is_tm Tm *
============================
exists S, subst X R (pair Tm1 Tm) S
< apply IH to IsT1 IsX with
R = R.
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 (pair Tm1 Tm) @
IsX : is_string X
IsT1 : is_tm Tm1 *
IsT2 : is_tm Tm *
H1 : subst X R Tm1 S
============================
exists S, subst X R (pair Tm1 Tm) S
< apply IH to IsT2 IsX with
R = R.
Subgoal 6:
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 (pair Tm1 Tm) @
IsX : is_string X
IsT1 : is_tm Tm1 *
IsT2 : is_tm Tm *
H1 : subst X R Tm1 S
H2 : subst X R Tm S1
============================
exists S, subst X R (pair Tm1 Tm) S
< search.
Subgoal 7:
Variables: X R Tm
IH : forall X R T, is_tm T * -> is_string X -> exists S, subst X R T S
IsT : is_tm (fst Tm) @
IsX : is_string X
IsT1 : is_tm Tm *
============================
exists S, subst X R (fst Tm) S
< apply IH to IsT1 IsX with
R = R.
Subgoal 7:
Variables: X R Tm S
IH : forall X R T, is_tm T * -> is_string X -> exists S, subst X R T S
IsT : is_tm (fst Tm) @
IsX : is_string X
IsT1 : is_tm Tm *
H1 : subst X R Tm S
============================
exists S, subst X R (fst Tm) S
< search.
Subgoal 8:
Variables: X R Tm
IH : forall X R T, is_tm T * -> is_string X -> exists S, subst X R T S
IsT : is_tm (snd Tm) @
IsX : is_string X
IsT1 : is_tm Tm *
============================
exists S, subst X R (snd Tm) S
< apply IH to IsT1 IsX with
R = R.
Subgoal 8:
Variables: X R Tm S
IH : forall X R T, is_tm T * -> is_string X -> exists S, subst X R T S
IsT : is_tm (snd Tm) @
IsX : is_string X
IsT1 : is_tm Tm *
H1 : subst X R Tm S
============================
exists S, subst X R (snd Tm) S
< search.
Proof completed.
< Prove stlc:host:canonical_forms.
Subgoal 3:
Variables: Ty T2 T1
IH : forall V Ty, value V * -> typeOf [] V Ty -> canonicalForm Ty V
V : value (pair T1 T2) @
Ty : typeOf [] (pair T1 T2) Ty
V1 : value T1 *
V2 : value T2 *
============================
canonicalForm Ty (pair T1 T2)
< Ty: case Ty.
Subgoal 3:
Variables: T2 T1 Ty1
IH : forall V Ty, value V * -> typeOf [] V Ty -> canonicalForm Ty V
V : value (pair T1 T2) @
V1 : value T1 *
V2 : value T2 *
Ty : typeOf [] T1 Ty1
Ty1 : typeOf [] T2 Ty1
============================
canonicalForm (pairTy Ty1) (pair T1 T2)
< search.
Proof completed.
< Theorem canonical_form_pairTy :
forall V Ty, value V -> typeOf [] V (pairTy Ty) -> exists A B, V = pair A B.
============================
forall V Ty, value V -> typeOf [] V (pairTy Ty) -> exists A B, V = pair A B
< intros V Ty.
Variables: V Ty
V : value V
Ty : typeOf [] V (pairTy Ty)
============================
exists A B, V = pair A B
< CF: apply canonical_forms to V Ty.
Variables: V Ty
V : value V
Ty : typeOf [] V (pairTy Ty)
CF : canonicalForm (pairTy Ty) V
============================
exists A B, V = pair A B
< case CF.
Variables: Ty B A
V : value (pair A B)
Ty : typeOf [] (pair A B) (pairTy Ty)
============================
exists A1 B1, pair A B = pair A1 B1
< search.
Proof completed.
< Prove stlc:host:progress.
Subgoal 6:
Variables: Ty1 T2 T1
IH : forall T Ty,
is_tm T -> typeOf [] T Ty * -> (exists T', eval T T') \/ value T
IsT : is_tm (pair T1 T2)
Ty : typeOf [] (pair T1 T2) (pairTy Ty1) @
Ty1 : typeOf [] T1 Ty1 *
Ty2 : typeOf [] T2 Ty1 *
============================
(exists T', eval (pair T1 T2) T') \/ value (pair T1 T2)
< Is: case IsT.
Subgoal 6:
Variables: Ty1 T2 T1
IH : forall T Ty,
is_tm T -> typeOf [] T Ty * -> (exists T', eval T T') \/ value T
Ty : typeOf [] (pair T1 T2) (pairTy Ty1) @
Ty1 : typeOf [] T1 Ty1 *
Ty2 : typeOf [] T2 Ty1 *
Is : is_tm T1
Is1 : is_tm T2
============================
(exists T', eval (pair T1 T2) T') \/ value (pair T1 T2)
< Or1: apply IH to _ Ty1.
Subgoal 6:
Variables: Ty1 T2 T1
IH : forall T Ty,
is_tm T -> typeOf [] T Ty * -> (exists T', eval T T') \/ value T
Ty : typeOf [] (pair T1 T2) (pairTy Ty1) @
Ty1 : typeOf [] T1 Ty1 *
Ty2 : typeOf [] T2 Ty1 *
Is : is_tm T1
Is1 : is_tm T2
Or1 : (exists T', eval T1 T') \/ value T1
============================
(exists T', eval (pair T1 T2) T') \/ value (pair T1 T2)
< Or2: apply IH to _ Ty2.
Subgoal 6:
Variables: Ty1 T2 T1
IH : forall T Ty,
is_tm T -> typeOf [] T Ty * -> (exists T', eval T T') \/ value T
Ty : typeOf [] (pair T1 T2) (pairTy Ty1) @
Ty1 : typeOf [] T1 Ty1 *
Ty2 : typeOf [] T2 Ty1 *
Is : is_tm T1
Is1 : is_tm T2
Or1 : (exists T', eval T1 T') \/ value T1
Or2 : (exists T', eval T2 T') \/ value T2
============================
(exists T', eval (pair T1 T2) T') \/ value (pair T1 T2)
< EV1: case Or1.
Subgoal 6.1:
Variables: Ty1 T2 T1 T'
IH : forall T Ty,
is_tm T -> typeOf [] T Ty * -> (exists T', eval T T') \/ value T
Ty : typeOf [] (pair T1 T2) (pairTy Ty1) @
Ty1 : typeOf [] T1 Ty1 *
Ty2 : typeOf [] T2 Ty1 *
Is : is_tm T1
Is1 : is_tm T2
Or2 : (exists T', eval T2 T') \/ value T2
EV1 : eval T1 T'
============================
(exists T', eval (pair T1 T2) T') \/ value (pair T1 T2)
< search.
Subgoal 6.2:
Variables: Ty1 T2 T1
IH : forall T Ty,
is_tm T -> typeOf [] T Ty * -> (exists T', eval T T') \/ value T
Ty : typeOf [] (pair T1 T2) (pairTy Ty1) @
Ty1 : typeOf [] T1 Ty1 *
Ty2 : typeOf [] T2 Ty1 *
Is : is_tm T1
Is1 : is_tm T2
Or2 : (exists T', eval T2 T') \/ value T2
EV1 : value T1
============================
(exists T', eval (pair T1 T2) T') \/ value (pair T1 T2)
< EV2: case Or2.
Subgoal 6.2.1:
Variables: Ty1 T2 T1 T'
IH : forall T Ty,
is_tm T -> typeOf [] T Ty * -> (exists T', eval T T') \/ value T
Ty : typeOf [] (pair T1 T2) (pairTy Ty1) @
Ty1 : typeOf [] T1 Ty1 *
Ty2 : typeOf [] T2 Ty1 *
Is : is_tm T1
Is1 : is_tm T2
EV1 : value T1
EV2 : eval T2 T'
============================
(exists T', eval (pair T1 T2) T') \/ value (pair T1 T2)
< search.
Subgoal 6.2.2:
Variables: Ty1 T2 T1
IH : forall T Ty,
is_tm T -> typeOf [] T Ty * -> (exists T', eval T T') \/ value T
Ty : typeOf [] (pair T1 T2) (pairTy Ty1) @
Ty1 : typeOf [] T1 Ty1 *
Ty2 : typeOf [] T2 Ty1 *
Is : is_tm T1
Is1 : is_tm T2
EV1 : value T1
EV2 : value T2
============================
(exists T', eval (pair T1 T2) T') \/ value (pair T1 T2)
< search.
Subgoal 7:
Variables: Ty T1
IH : forall T Ty,
is_tm T -> typeOf [] T Ty * -> (exists T', eval T T') \/ value T
IsT : is_tm (fst T1)
Ty : typeOf [] (fst T1) Ty @
Ty1 : typeOf [] T1 (pairTy Ty) *
============================
(exists T', eval (fst T1) T') \/ value (fst T1)
< Is: case IsT.
Subgoal 7:
Variables: Ty T1
IH : forall T Ty,
is_tm T -> typeOf [] T Ty * -> (exists T', eval T T') \/ value T
Ty : typeOf [] (fst T1) Ty @
Ty1 : typeOf [] T1 (pairTy Ty) *
Is : is_tm T1
============================
(exists T', eval (fst T1) T') \/ value (fst T1)
< Or: apply IH to _ Ty1.
Subgoal 7:
Variables: Ty T1
IH : forall T Ty,
is_tm T -> typeOf [] T Ty * -> (exists T', eval T T') \/ value T
Ty : typeOf [] (fst T1) Ty @
Ty1 : typeOf [] T1 (pairTy Ty) *
Is : is_tm T1
Or : (exists T', eval T1 T') \/ value T1
============================
(exists T', eval (fst T1) T') \/ value (fst T1)
< EV: case Or.
Subgoal 7.1:
Variables: Ty T1 T'
IH : forall T Ty,
is_tm T -> typeOf [] T Ty * -> (exists T', eval T T') \/ value T
Ty : typeOf [] (fst T1) Ty @
Ty1 : typeOf [] T1 (pairTy Ty) *
Is : is_tm T1
EV : eval T1 T'
============================
(exists T', eval (fst T1) T') \/ value (fst T1)
< search.
Subgoal 7.2:
Variables: Ty T1
IH : forall T Ty,
is_tm T -> typeOf [] T Ty * -> (exists T', eval T T') \/ value T
Ty : typeOf [] (fst T1) Ty @
Ty1 : typeOf [] T1 (pairTy Ty) *
Is : is_tm T1
EV : value T1
============================
(exists T', eval (fst T1) T') \/ value (fst T1)
< apply canonical_form_pairTy to EV Ty1.
Subgoal 7.2:
Variables: Ty A B
IH : forall T Ty,
is_tm T -> typeOf [] T Ty * -> (exists T', eval T T') \/ value T
Ty : typeOf [] (fst (pair A B)) Ty @
Ty1 : typeOf [] (pair A B) (pairTy Ty) *
Is : is_tm (pair A B)
EV : value (pair A B)
============================
(exists T', eval (fst (pair A B)) T') \/ value (fst (pair A B))
< search.
Subgoal 8:
Variables: Ty T1
IH : forall T Ty,
is_tm T -> typeOf [] T Ty * -> (exists T', eval T T') \/ value T
IsT : is_tm (snd T1)
Ty : typeOf [] (snd T1) Ty @
Ty1 : typeOf [] T1 (pairTy Ty) *
============================
(exists T', eval (snd T1) T') \/ value (snd T1)
< Is: case IsT.
Subgoal 8:
Variables: Ty T1
IH : forall T Ty,
is_tm T -> typeOf [] T Ty * -> (exists T', eval T T') \/ value T
Ty : typeOf [] (snd T1) Ty @
Ty1 : typeOf [] T1 (pairTy Ty) *
Is : is_tm T1
============================
(exists T', eval (snd T1) T') \/ value (snd T1)
< Or: apply IH to _ Ty1.
Subgoal 8:
Variables: Ty T1
IH : forall T Ty,
is_tm T -> typeOf [] T Ty * -> (exists T', eval T T') \/ value T
Ty : typeOf [] (snd T1) Ty @
Ty1 : typeOf [] T1 (pairTy Ty) *
Is : is_tm T1
Or : (exists T', eval T1 T') \/ value T1
============================
(exists T', eval (snd T1) T') \/ value (snd T1)
< EV: case Or.
Subgoal 8.1:
Variables: Ty T1 T'
IH : forall T Ty,
is_tm T -> typeOf [] T Ty * -> (exists T', eval T T') \/ value T
Ty : typeOf [] (snd T1) Ty @
Ty1 : typeOf [] T1 (pairTy Ty) *
Is : is_tm T1
EV : eval T1 T'
============================
(exists T', eval (snd T1) T') \/ value (snd T1)
< search.
Subgoal 8.2:
Variables: Ty T1
IH : forall T Ty,
is_tm T -> typeOf [] T Ty * -> (exists T', eval T T') \/ value T
Ty : typeOf [] (snd T1) Ty @
Ty1 : typeOf [] T1 (pairTy Ty) *
Is : is_tm T1
EV : value T1
============================
(exists T', eval (snd T1) T') \/ value (snd T1)
< apply canonical_form_pairTy to EV Ty1.
Subgoal 8.2:
Variables: Ty A B
IH : forall T Ty,
is_tm T -> typeOf [] T Ty * -> (exists T', eval T T') \/ value T
Ty : typeOf [] (snd (pair A B)) Ty @
Ty1 : typeOf [] (pair A B) (pairTy Ty) *
Is : is_tm (pair A B)
EV : value (pair A B)
============================
(exists T', eval (snd (pair A B)) T') \/ value (snd (pair A B))
< search.
Proof completed.
