< Module lambda_calculus:typing.
< Prove_Constraint lambda_calculus:host:proj_is.
Variables: Body X Ty
Hyp : |{e}- tyabs X Ty Body ~~> abs X Body
Hyp1 : is_e (tyabs X Ty Body)
============================
is_e (abs X Body)
< case Hyp1.
Variables: Body X Ty
Hyp : |{e}- tyabs X Ty Body ~~> abs X Body
H1 : is_string X
H2 : is_ty Ty
H3 : is_e Body
============================
is_e (abs X Body)
< search.
Proof completed.
< Add_Proj_Rel lambda_calculus:host:is_e.
Proof completed.
< Prove_Ext_Ind lambda_calculus:host:is_e.
Warning: No definition of Ext Size for all relations in Ext Ind; defaulting to proving Ext Ind without Ext Size
Subgoal 6:
Variables: E1 Ty S
IH : forall E, is_e E * -> <is_e {P}> E
R : is_e (tyabs S Ty E1) @
R1 : is_string S
R2 : is_ty Ty
R3 : is_e E1 *
============================
<is_e {P}> (tyabs S Ty E1)
< apply IH to R3.
Subgoal 6:
Variables: E1 Ty S
IH : forall E, is_e E * -> <is_e {P}> E
R : is_e (tyabs S Ty E1) @
R1 : is_string S
R2 : is_ty Ty
R3 : is_e E1 *
H1 : <is_e {P}> E1
============================
<is_e {P}> (tyabs S Ty E1)
< search.
Proof completed.
< Prove_Constraint lambda_calculus:host:proj_same.
Variables: E2 Body X Ty
Hyp : |{e}- tyabs X Ty Body ~~> abs X Body
Hyp1 : |{e}- tyabs X Ty Body ~~> E2
============================
abs X Body = E2
< case Hyp1.
Variables: Body X Ty
Hyp : |{e}- tyabs X Ty Body ~~> abs X Body
============================
abs X Body = abs X Body
< search.
Proof completed.
< Prove lambda_calculus:host:subst_exists.
Subgoal 6:
Variables: X R E1 Ty S
IH : forall X R E, is_e E * -> is_string X -> is_e R -> exists S, subst X R E S
IsE : is_e (tyabs S Ty E1) @
IsX : is_string X
IsR : is_e R
IsE1 : is_string S
IsE2 : is_ty Ty
IsE3 : is_e E1 *
============================
exists S1, subst X R (tyabs S Ty E1) S1
< Or: apply is_string_eq_or_not to IsX IsE1.
Subgoal 6:
Variables: X R E1 Ty S
IH : forall X R E, is_e E * -> is_string X -> is_e R -> exists S, subst X R E S
IsE : is_e (tyabs S Ty E1) @
IsX : is_string X
IsR : is_e R
IsE1 : is_string S
IsE2 : is_ty Ty
IsE3 : is_e E1 *
Or : X = S \/ (X = S -> false)
============================
exists S1, subst X R (tyabs S Ty E1) S1
< Eq: case Or.
Subgoal 6.1:
Variables: R E1 Ty S
IH : forall X R E, is_e E * -> is_string X -> is_e R -> exists S, subst X R E S
IsE : is_e (tyabs S Ty E1) @
IsX : is_string S
IsR : is_e R
IsE1 : is_string S
IsE2 : is_ty Ty
IsE3 : is_e E1 *
============================
exists S1, subst S R (tyabs S Ty E1) S1
< search.
Subgoal 6.2:
Variables: X R E1 Ty S
IH : forall X R E, is_e E * -> is_string X -> is_e R -> exists S, subst X R E S
IsE : is_e (tyabs S Ty E1) @
IsX : is_string X
IsR : is_e R
IsE1 : is_string S
IsE2 : is_ty Ty
IsE3 : is_e E1 *
Eq : X = S -> false
============================
exists S1, subst X R (tyabs S Ty E1) S1
< apply IH to IsE3 IsX IsR.
Subgoal 6.2:
Variables: X R E1 Ty S S1
IH : forall X R E, is_e E * -> is_string X -> is_e R -> exists S, subst X R E S
IsE : is_e (tyabs S Ty E1) @
IsX : is_string X
IsR : is_e R
IsE1 : is_string S
IsE2 : is_ty Ty
IsE3 : is_e E1 *
Eq : X = S -> false
H1 : subst X R E1 S1
============================
exists S1, subst X R (tyabs S Ty E1) S1
< search.
Proof completed.
< Prove lambda_calculus:host:subst_is.
Subgoal 8:
Variables: X R Body Ty
IH : forall X R E S,
is_e E -> is_string X -> is_e R -> subst X R E S * -> is_e S
IsE : is_e (tyabs X Ty Body)
IsX : is_string X
IsR : is_e R
S : subst X R (tyabs X Ty Body) (abs X Body) @
============================
is_e (abs X Body)
< case IsE.
Subgoal 8:
Variables: X R Body Ty
IH : forall X R E S,
is_e E -> is_string X -> is_e R -> subst X R E S * -> is_e S
IsX : is_string X
IsR : is_e R
S : subst X R (tyabs X Ty Body) (abs X Body) @
H1 : is_string X
H2 : is_ty Ty
H3 : is_e Body
============================
is_e (abs X Body)
< search.
Subgoal 9:
Variables: X R B Y Body Ty
IH : forall X R E S,
is_e E -> is_string X -> is_e R -> subst X R E S * -> is_e S
IsE : is_e (tyabs Y Ty Body)
IsX : is_string X
IsR : is_e R
S : subst X R (tyabs Y Ty Body) (abs Y B) @
S1 : X = Y -> false
S2 : subst X R Body B *
============================
is_e (abs Y B)
< Is: case IsE.
Subgoal 9:
Variables: X R B Y Body Ty
IH : forall X R E S,
is_e E -> is_string X -> is_e R -> subst X R E S * -> is_e S
IsX : is_string X
IsR : is_e R
S : subst X R (tyabs Y Ty Body) (abs Y B) @
S1 : X = Y -> false
S2 : subst X R Body B *
Is : is_string Y
Is1 : is_ty Ty
Is2 : is_e Body
============================
is_e (abs Y B)
< apply IH to _ _ _ S2.
Subgoal 9:
Variables: X R B Y Body Ty
IH : forall X R E S,
is_e E -> is_string X -> is_e R -> subst X R E S * -> is_e S
IsX : is_string X
IsR : is_e R
S : subst X R (tyabs Y Ty Body) (abs Y B) @
S1 : X = Y -> false
S2 : subst X R Body B *
Is : is_string Y
Is1 : is_ty Ty
Is2 : is_e Body
H1 : is_e B
============================
is_e (abs Y B)
< search.
Proof completed.
< Prove lambda_calculus:host:eval_is.
Subgoal 5:
Variables: Body X Ty
IH : forall E V, is_e E -> eval E V * -> is_e V
IsE : is_e (tyabs X Ty Body)
Ev : eval (tyabs X Ty Body) (abs X Body) @
============================
is_e (abs X Body)
< Is: case IsE.
Subgoal 5:
Variables: Body X Ty
IH : forall E V, is_e E -> eval E V * -> is_e V
Ev : eval (tyabs X Ty Body) (abs X Body) @
Is : is_string X
Is1 : is_ty Ty
Is2 : is_e Body
============================
is_e (abs X Body)
< search.
Proof completed.
< Prove lambda_calculus:host:subst_unique.
Subgoal 8:
Variables: X R SB Body Ty
IH : forall X R E SA SB,
is_e E -> is_string X -> is_e R -> subst X R E SA * -> subst X R E SB -> SA = SB
IsE : is_e (tyabs X Ty Body)
IsX : is_string X
IsR : is_e R
SA : subst X R (tyabs X Ty Body) (abs X Body) @
SB : subst X R (tyabs X Ty Body) SB
============================
abs X Body = SB
< SB: case SB.
Subgoal 8.1:
Variables: X R Body Ty
IH : forall X R E SA SB,
is_e E -> is_string X -> is_e R -> subst X R E SA * -> subst X R E SB -> SA = SB
IsE : is_e (tyabs X Ty Body)
IsX : is_string X
IsR : is_e R
SA : subst X R (tyabs X Ty Body) (abs X Body) @
============================
abs X Body = abs X Body
< search.
Subgoal 8.2:
Variables: X R Body Ty B
IH : forall X R E SA SB,
is_e E -> is_string X -> is_e R -> subst X R E SA * -> subst X R E SB -> SA = SB
IsE : is_e (tyabs X Ty Body)
IsX : is_string X
IsR : is_e R
SA : subst X R (tyabs X Ty Body) (abs X Body) @
SB : X = X -> false
SB1 : subst X R Body B
============================
abs X Body = abs X B
< apply SB to _.
Subgoal 9:
Variables: X R SB B Y Body Ty
IH : forall X R E SA SB,
is_e E -> is_string X -> is_e R -> subst X R E SA * -> subst X R E SB -> SA = SB
IsE : is_e (tyabs Y Ty Body)
IsX : is_string X
IsR : is_e R
SA : subst X R (tyabs Y Ty Body) (abs Y B) @
SB : subst X R (tyabs Y Ty Body) SB
SA1 : X = Y -> false
SA2 : subst X R Body B *
============================
abs Y B = SB
< SB: case SB.
Subgoal 9.1:
Variables: R B Y Body Ty
IH : forall X R E SA SB,
is_e E -> is_string X -> is_e R -> subst X R E SA * -> subst X R E SB -> SA = SB
IsE : is_e (tyabs Y Ty Body)
IsX : is_string Y
IsR : is_e R
SA : subst Y R (tyabs Y Ty Body) (abs Y B) @
SA1 : Y = Y -> false
SA2 : subst Y R Body B *
============================
abs Y B = abs Y Body
< apply SA1 to _.
Subgoal 9.2:
Variables: X R B Y Body Ty B1
IH : forall X R E SA SB,
is_e E -> is_string X -> is_e R -> subst X R E SA * -> subst X R E SB -> SA = SB
IsE : is_e (tyabs Y Ty Body)
IsX : is_string X
IsR : is_e R
SA : subst X R (tyabs Y Ty Body) (abs Y B) @
SA1 : X = Y -> false
SA2 : subst X R Body B *
SB : X = Y -> false
SB1 : subst X R Body B1
============================
abs Y B = abs Y B1
< Is: case IsE.
Subgoal 9.2:
Variables: X R B Y Body Ty B1
IH : forall X R E SA SB,
is_e E -> is_string X -> is_e R -> subst X R E SA * -> subst X R E SB -> SA = SB
IsX : is_string X
IsR : is_e R
SA : subst X R (tyabs Y Ty Body) (abs Y B) @
SA1 : X = Y -> false
SA2 : subst X R Body B *
SB : X = Y -> false
SB1 : subst X R Body B1
Is : is_string Y
Is1 : is_ty Ty
Is2 : is_e Body
============================
abs Y B = abs Y B1
< apply IH to _ _ _ SA2 SB1.
Subgoal 9.2:
Variables: X R Y Body Ty B1
IH : forall X R E SA SB,
is_e E -> is_string X -> is_e R -> subst X R E SA * -> subst X R E SB -> SA = SB
IsX : is_string X
IsR : is_e R
SA : subst X R (tyabs Y Ty Body) (abs Y B1) @
SA1 : X = Y -> false
SA2 : subst X R Body B1 *
SB : X = Y -> false
SB1 : subst X R Body B1
Is : is_string Y
Is1 : is_ty Ty
Is2 : is_e Body
============================
abs Y B1 = abs Y B1
< search.
Proof completed.
< Prove lambda_calculus:host:eval_unique.
Subgoal 5:
Variables: VB Body X Ty
IH : forall E VA VB, is_e E -> eval E VA * -> eval E VB -> VA = VB
IsE : is_e (tyabs X Ty Body)
EvA : eval (tyabs X Ty Body) (abs X Body) @
EvB : eval (tyabs X Ty Body) VB
============================
abs X Body = VB
< case EvB.
Subgoal 5:
Variables: Body X Ty
IH : forall E VA VB, is_e E -> eval E VA * -> eval E VB -> VA = VB
IsE : is_e (tyabs X Ty Body)
EvA : eval (tyabs X Ty Body) (abs X Body) @
============================
abs X Body = abs X Body
< search.
Proof completed.
< Prove_Constraint lambda_calculus:host:proj_subst.
Variables: X R S Body X1 Ty
Proj : |{e}- tyabs X1 Ty Body ~~> abs X1 Body
IsE : is_e (tyabs X1 Ty Body)
IsX : is_string X
IsR : is_e R
S : subst X R (tyabs X1 Ty Body) S
============================
exists S', subst X R (abs X1 Body) S'
< S: case S.
Subgoal 1:
Variables: R Body X1 Ty
Proj : |{e}- tyabs X1 Ty Body ~~> abs X1 Body
IsE : is_e (tyabs X1 Ty Body)
IsX : is_string X1
IsR : is_e R
============================
exists S', subst X1 R (abs X1 Body) S'
< search.
Subgoal 2:
Variables: X R Body X1 Ty B
Proj : |{e}- tyabs X1 Ty Body ~~> abs X1 Body
IsE : is_e (tyabs X1 Ty Body)
IsX : is_string X
IsR : is_e R
S : X = X1 -> false
S1 : subst X R Body B
============================
exists S', subst X R (abs X1 Body) S'
< search.
Proof completed.
< Prove_Constraint lambda_calculus:host:proj_subst_same.
Variables: X R S S' Body X1 Ty
Proj : |{e}- tyabs X1 Ty Body ~~> abs X1 Body
IsE : is_e (tyabs X1 Ty Body)
IsX : is_string X
IsR : is_e R
S : subst X R (tyabs X1 Ty Body) S
S' : subst X R (abs X1 Body) S'
============================
S = S'
< S: case S.
Subgoal 1:
Variables: R S' Body X1 Ty
Proj : |{e}- tyabs X1 Ty Body ~~> abs X1 Body
IsE : is_e (tyabs X1 Ty Body)
IsX : is_string X1
IsR : is_e R
S' : subst X1 R (abs X1 Body) S'
============================
abs X1 Body = S'
< S': case S'.
Subgoal 1.1:
Variables: R Body X1 Ty
Proj : |{e}- tyabs X1 Ty Body ~~> abs X1 Body
IsE : is_e (tyabs X1 Ty Body)
IsX : is_string X1
IsR : is_e R
============================
abs X1 Body = abs X1 Body
< search.
Subgoal 1.2:
Variables: R Body X1 Ty B
Proj : |{e}- tyabs X1 Ty Body ~~> abs X1 Body
IsE : is_e (tyabs X1 Ty Body)
IsX : is_string X1
IsR : is_e R
S' : X1 = X1 -> false
S'1 : subst X1 R Body B
============================
abs X1 Body = abs X1 B
< apply S' to _.
Subgoal 2:
Variables: X R S' Body X1 Ty B
Proj : |{e}- tyabs X1 Ty Body ~~> abs X1 Body
IsE : is_e (tyabs X1 Ty Body)
IsX : is_string X
IsR : is_e R
S' : subst X R (abs X1 Body) S'
S : X = X1 -> false
S1 : subst X R Body B
============================
abs X1 B = S'
< S': case S'.
Subgoal 2.1:
Variables: R Body X1 Ty B
Proj : |{e}- tyabs X1 Ty Body ~~> abs X1 Body
IsE : is_e (tyabs X1 Ty Body)
IsX : is_string X1
IsR : is_e R
S : X1 = X1 -> false
S1 : subst X1 R Body B
============================
abs X1 B = abs X1 Body
< apply S to _.
Subgoal 2.2:
Variables: X R Body X1 Ty B B1
Proj : |{e}- tyabs X1 Ty Body ~~> abs X1 Body
IsE : is_e (tyabs X1 Ty Body)
IsX : is_string X
IsR : is_e R
S : X = X1 -> false
S1 : subst X R Body B
S' : X = X1 -> false
S'1 : subst X R Body B1
============================
abs X1 B = abs X1 B1
< case IsE.
Subgoal 2.2:
Variables: X R Body X1 Ty B B1
Proj : |{e}- tyabs X1 Ty Body ~~> abs X1 Body
IsX : is_string X
IsR : is_e R
S : X = X1 -> false
S1 : subst X R Body B
S' : X = X1 -> false
S'1 : subst X R Body B1
H1 : is_string X1
H2 : is_ty Ty
H3 : is_e Body
============================
abs X1 B = abs X1 B1
< apply subst_unique to _ _ _ S1 S'1.
Subgoal 2.2:
Variables: X R Body X1 Ty B1
Proj : |{e}- tyabs X1 Ty Body ~~> abs X1 Body
IsX : is_string X
IsR : is_e R
S : X = X1 -> false
S1 : subst X R Body B1
S' : X = X1 -> false
S'1 : subst X R Body B1
H1 : is_string X1
H2 : is_ty Ty
H3 : is_e Body
============================
abs X1 B1 = abs X1 B1
< search.
Proof completed.
< Prove_Constraint lambda_calculus:host:proj_eval.
Variables: V Body X Ty
Proj : |{e}- tyabs X Ty Body ~~> abs X Body
IsE : is_e (tyabs X Ty Body)
Ev : eval (tyabs X Ty Body) V
============================
exists V', eval (abs X Body) V'
< case Ev.
Variables: Body X Ty
Proj : |{e}- tyabs X Ty Body ~~> abs X Body
IsE : is_e (tyabs X Ty Body)
============================
exists V', eval (abs X Body) V'
< search.
Proof completed.
< Prove_Constraint lambda_calculus:host:proj_eval_same.
Variables: V V' Body X Ty
Proj : |{e}- tyabs X Ty Body ~~> abs X Body
IsE : is_e (tyabs X Ty Body)
Ev : eval (tyabs X Ty Body) V
Ev' : eval (abs X Body) V'
============================
V = V'
< case Ev.
Variables: V' Body X Ty
Proj : |{e}- tyabs X Ty Body ~~> abs X Body
IsE : is_e (tyabs X Ty Body)
Ev' : eval (abs X Body) V'
============================
abs X Body = V'
< case Ev'.
Variables: Body X Ty
Proj : |{e}- tyabs X Ty Body ~~> abs X Body
IsE : is_e (tyabs X Ty Body)
============================
abs X Body = abs X Body
< search.
Proof completed.
< Add_Ext_Size lambda_calculus:host:eval.
Proof completed.
< Add_Proj_Rel lambda_calculus:host:eval.
Proof completed.
< Prove_Ext_Ind lambda_calculus:host:eval.
Subgoal 5:
Variables: Body X Ty
IH : forall N E V, <eval {ES}> E V N -> acc N * -> <eval {P}> E V
IH1 : forall N E V, <eval {ES}> E V N ** -> acc N @ -> <eval {P}> E V
R : <eval {ES}> (tyabs X Ty Body) (abs X Body) 1 @@
Acc : acc 1 @
============================
<eval {P}> (tyabs X Ty Body) (abs X Body)
< search.
Proof completed.
< Extensible_Theorem
type_weakening : forall G E Ty G',
IsE : is_e E ->
Ty : typeOf G E Ty ->
Lkp : (forall X XTy,
lookup G X XTy -> lookup G' X XTy) ->
typeOf G' E Ty
on Ty.
Subgoal 1:
Variables: G Ty G' X
IH : forall G E Ty G',
is_e E -> typeOf G E Ty * -> (forall X XTy,
lookup G X XTy -> lookup G' X XTy) -> typeOf G' E Ty
IsE : is_e (var X)
Ty : typeOf G (var X) Ty @
Lkp : forall X XTy, lookup G X XTy -> lookup G' X XTy
Ty1 : lookup G X Ty
============================
typeOf G' (var X) Ty
< apply Lkp to Ty1.
Subgoal 1:
Variables: G Ty G' X
IH : forall G E Ty G',
is_e E -> typeOf G E Ty * -> (forall X XTy,
lookup G X XTy -> lookup G' X XTy) -> typeOf G' E Ty
IsE : is_e (var X)
Ty : typeOf G (var X) Ty @
Lkp : forall X XTy, lookup G X XTy -> lookup G' X XTy
Ty1 : lookup G X Ty
H1 : lookup G' X Ty
============================
typeOf G' (var X) Ty
< search.
Subgoal 2:
Variables: G G' Ty2 Ty1 Body X
IH : forall G E Ty G',
is_e E -> typeOf G E Ty * -> (forall X XTy,
lookup G X XTy -> lookup G' X XTy) -> typeOf G' E Ty
IsE : is_e (abs X Body)
Ty : typeOf G (abs X Body) (arrowTy Ty1 Ty2) @
Lkp : forall X XTy, lookup G X XTy -> lookup G' X XTy
Ty1 : typeOf ((X, Ty1)::G) Body Ty2 *
============================
typeOf G' (abs X Body) (arrowTy Ty1 Ty2)
< Is: case IsE.
Subgoal 2:
Variables: G G' Ty2 Ty1 Body X
IH : forall G E Ty G',
is_e E -> typeOf G E Ty * -> (forall X XTy,
lookup G X XTy -> lookup G' X XTy) -> typeOf G' E Ty
Ty : typeOf G (abs X Body) (arrowTy Ty1 Ty2) @
Lkp : forall X XTy, lookup G X XTy -> lookup G' X XTy
Ty1 : typeOf ((X, Ty1)::G) Body Ty2 *
Is : is_string X
Is1 : is_e Body
============================
typeOf G' (abs X Body) (arrowTy Ty1 Ty2)
< apply IH to _ Ty1 _ with
G' = (X, Ty1)::G'.
Subgoal 2.1:
Variables: G G' Ty2 Ty1 Body X
IH : forall G E Ty G',
is_e E -> typeOf G E Ty * -> (forall X XTy,
lookup G X XTy -> lookup G' X XTy) -> typeOf G' E Ty
Ty : typeOf G (abs X Body) (arrowTy Ty1 Ty2) @
Lkp : forall X XTy, lookup G X XTy -> lookup G' X XTy
Ty1 : typeOf ((X, Ty1)::G) Body Ty2 *
Is : is_string X
Is1 : is_e Body
============================
forall X1 XTy, lookup ((X, Ty1)::G) X1 XTy -> lookup ((X, Ty1)::G') X1 XTy
< intros L.
Subgoal 2.1:
Variables: G G' Ty2 Ty1 Body X X1 XTy
IH : forall G E Ty G',
is_e E -> typeOf G E Ty * -> (forall X XTy,
lookup G X XTy -> lookup G' X XTy) -> typeOf G' E Ty
Ty : typeOf G (abs X Body) (arrowTy Ty1 Ty2) @
Lkp : forall X XTy, lookup G X XTy -> lookup G' X XTy
Ty1 : typeOf ((X, Ty1)::G) Body Ty2 *
Is : is_string X
Is1 : is_e Body
L : lookup ((X, Ty1)::G) X1 XTy
============================
lookup ((X, Ty1)::G') X1 XTy
< L: case L.
Subgoal 2.1.1:
Variables: G G' Ty2 Body X1 XTy
IH : forall G E Ty G',
is_e E -> typeOf G E Ty * -> (forall X XTy,
lookup G X XTy -> lookup G' X XTy) -> typeOf G' E Ty
Ty : typeOf G (abs X1 Body) (arrowTy XTy Ty2) @
Lkp : forall X XTy, lookup G X XTy -> lookup G' X XTy
Ty1 : typeOf ((X1, XTy)::G) Body Ty2 *
Is : is_string X1
Is1 : is_e Body
============================
lookup ((X1, XTy)::G') X1 XTy
< search.
Subgoal 2.1.2:
Variables: G G' Ty2 Ty1 Body X X1 XTy
IH : forall G E Ty G',
is_e E -> typeOf G E Ty * -> (forall X XTy,
lookup G X XTy -> lookup G' X XTy) -> typeOf G' E Ty
Ty : typeOf G (abs X Body) (arrowTy Ty1 Ty2) @
Lkp : forall X XTy, lookup G X XTy -> lookup G' X XTy
Ty1 : typeOf ((X, Ty1)::G) Body Ty2 *
Is : is_string X
Is1 : is_e Body
L : X = X1 -> false
L1 : lookup G X1 XTy
============================
lookup ((X, Ty1)::G') X1 XTy
< apply Lkp to L1.
Subgoal 2.1.2:
Variables: G G' Ty2 Ty1 Body X X1 XTy
IH : forall G E Ty G',
is_e E -> typeOf G E Ty * -> (forall X XTy,
lookup G X XTy -> lookup G' X XTy) -> typeOf G' E Ty
Ty : typeOf G (abs X Body) (arrowTy Ty1 Ty2) @
Lkp : forall X XTy, lookup G X XTy -> lookup G' X XTy
Ty1 : typeOf ((X, Ty1)::G) Body Ty2 *
Is : is_string X
Is1 : is_e Body
L : X = X1 -> false
L1 : lookup G X1 XTy
H1 : lookup G' X1 XTy
============================
lookup ((X, Ty1)::G') X1 XTy
< search.
Subgoal 2:
Variables: G G' Ty2 Ty1 Body X
IH : forall G E Ty G',
is_e E -> typeOf G E Ty * -> (forall X XTy,
lookup G X XTy -> lookup G' X XTy) -> typeOf G' E Ty
Ty : typeOf G (abs X Body) (arrowTy Ty1 Ty2) @
Lkp : forall X XTy, lookup G X XTy -> lookup G' X XTy
Ty1 : typeOf ((X, Ty1)::G) Body Ty2 *
Is : is_string X
Is1 : is_e Body
H1 : typeOf ((X, Ty1)::G') Body Ty2
============================
typeOf G' (abs X Body) (arrowTy Ty1 Ty2)
< search.
Subgoal 3:
Variables: G G' Ty2 Ty1 Body X
IH : forall G E Ty G',
is_e E -> typeOf G E Ty * -> (forall X XTy,
lookup G X XTy -> lookup G' X XTy) -> typeOf G' E Ty
IsE : is_e (tyabs X Ty1 Body)
Ty : typeOf G (tyabs X Ty1 Body) (arrowTy Ty1 Ty2) @
Lkp : forall X XTy, lookup G X XTy -> lookup G' X XTy
Ty1 : typeOf ((X, Ty1)::G) Body Ty2 *
============================
typeOf G' (tyabs X Ty1 Body) (arrowTy Ty1 Ty2)
< Is: case IsE.
Subgoal 3:
Variables: G G' Ty2 Ty1 Body X
IH : forall G E Ty G',
is_e E -> typeOf G E Ty * -> (forall X XTy,
lookup G X XTy -> lookup G' X XTy) -> typeOf G' E Ty
Ty : typeOf G (tyabs X Ty1 Body) (arrowTy Ty1 Ty2) @
Lkp : forall X XTy, lookup G X XTy -> lookup G' X XTy
Ty1 : typeOf ((X, Ty1)::G) Body Ty2 *
Is : is_string X
Is1 : is_ty Ty1
Is2 : is_e Body
============================
typeOf G' (tyabs X Ty1 Body) (arrowTy Ty1 Ty2)
< apply IH to _ Ty1 _ with
G' = (X, Ty1)::G'.
Subgoal 3.1:
Variables: G G' Ty2 Ty1 Body X
IH : forall G E Ty G',
is_e E -> typeOf G E Ty * -> (forall X XTy,
lookup G X XTy -> lookup G' X XTy) -> typeOf G' E Ty
Ty : typeOf G (tyabs X Ty1 Body) (arrowTy Ty1 Ty2) @
Lkp : forall X XTy, lookup G X XTy -> lookup G' X XTy
Ty1 : typeOf ((X, Ty1)::G) Body Ty2 *
Is : is_string X
Is1 : is_ty Ty1
Is2 : is_e Body
============================
forall X1 XTy, lookup ((X, Ty1)::G) X1 XTy -> lookup ((X, Ty1)::G') X1 XTy
< intros L.
Subgoal 3.1:
Variables: G G' Ty2 Ty1 Body X X1 XTy
IH : forall G E Ty G',
is_e E -> typeOf G E Ty * -> (forall X XTy,
lookup G X XTy -> lookup G' X XTy) -> typeOf G' E Ty
Ty : typeOf G (tyabs X Ty1 Body) (arrowTy Ty1 Ty2) @
Lkp : forall X XTy, lookup G X XTy -> lookup G' X XTy
Ty1 : typeOf ((X, Ty1)::G) Body Ty2 *
Is : is_string X
Is1 : is_ty Ty1
Is2 : is_e Body
L : lookup ((X, Ty1)::G) X1 XTy
============================
lookup ((X, Ty1)::G') X1 XTy
< L: case L.
Subgoal 3.1.1:
Variables: G G' Ty2 Body X1 XTy
IH : forall G E Ty G',
is_e E -> typeOf G E Ty * -> (forall X XTy,
lookup G X XTy -> lookup G' X XTy) -> typeOf G' E Ty
Ty : typeOf G (tyabs X1 XTy Body) (arrowTy XTy Ty2) @
Lkp : forall X XTy, lookup G X XTy -> lookup G' X XTy
Ty1 : typeOf ((X1, XTy)::G) Body Ty2 *
Is : is_string X1
Is1 : is_ty XTy
Is2 : is_e Body
============================
lookup ((X1, XTy)::G') X1 XTy
< search.
Subgoal 3.1.2:
Variables: G G' Ty2 Ty1 Body X X1 XTy
IH : forall G E Ty G',
is_e E -> typeOf G E Ty * -> (forall X XTy,
lookup G X XTy -> lookup G' X XTy) -> typeOf G' E Ty
Ty : typeOf G (tyabs X Ty1 Body) (arrowTy Ty1 Ty2) @
Lkp : forall X XTy, lookup G X XTy -> lookup G' X XTy
Ty1 : typeOf ((X, Ty1)::G) Body Ty2 *
Is : is_string X
Is1 : is_ty Ty1
Is2 : is_e Body
L : X = X1 -> false
L1 : lookup G X1 XTy
============================
lookup ((X, Ty1)::G') X1 XTy
< apply Lkp to L1.
Subgoal 3.1.2:
Variables: G G' Ty2 Ty1 Body X X1 XTy
IH : forall G E Ty G',
is_e E -> typeOf G E Ty * -> (forall X XTy,
lookup G X XTy -> lookup G' X XTy) -> typeOf G' E Ty
Ty : typeOf G (tyabs X Ty1 Body) (arrowTy Ty1 Ty2) @
Lkp : forall X XTy, lookup G X XTy -> lookup G' X XTy
Ty1 : typeOf ((X, Ty1)::G) Body Ty2 *
Is : is_string X
Is1 : is_ty Ty1
Is2 : is_e Body
L : X = X1 -> false
L1 : lookup G X1 XTy
H1 : lookup G' X1 XTy
============================
lookup ((X, Ty1)::G') X1 XTy
< search.
Subgoal 3:
Variables: G G' Ty2 Ty1 Body X
IH : forall G E Ty G',
is_e E -> typeOf G E Ty * -> (forall X XTy,
lookup G X XTy -> lookup G' X XTy) -> typeOf G' E Ty
Ty : typeOf G (tyabs X Ty1 Body) (arrowTy Ty1 Ty2) @
Lkp : forall X XTy, lookup G X XTy -> lookup G' X XTy
Ty1 : typeOf ((X, Ty1)::G) Body Ty2 *
Is : is_string X
Is1 : is_ty Ty1
Is2 : is_e Body
H1 : typeOf ((X, Ty1)::G') Body Ty2
============================
typeOf G' (tyabs X Ty1 Body) (arrowTy Ty1 Ty2)
< search.
Subgoal 4:
Variables: G Ty G' Ty1 E2 E1
IH : forall G E Ty G',
is_e E -> typeOf G E Ty * -> (forall X XTy,
lookup G X XTy -> lookup G' X XTy) -> typeOf G' E Ty
IsE : is_e (app E1 E2)
Ty : typeOf G (app E1 E2) Ty @
Lkp : forall X XTy, lookup G X XTy -> lookup G' X XTy
Ty1 : typeOf G E1 (arrowTy Ty1 Ty) *
Ty2 : typeOf G E2 Ty1 *
============================
typeOf G' (app E1 E2) Ty
< Is: case IsE.
Subgoal 4:
Variables: G Ty G' Ty1 E2 E1
IH : forall G E Ty G',
is_e E -> typeOf G E Ty * -> (forall X XTy,
lookup G X XTy -> lookup G' X XTy) -> typeOf G' E Ty
Ty : typeOf G (app E1 E2) Ty @
Lkp : forall X XTy, lookup G X XTy -> lookup G' X XTy
Ty1 : typeOf G E1 (arrowTy Ty1 Ty) *
Ty2 : typeOf G E2 Ty1 *
Is : is_e E1
Is1 : is_e E2
============================
typeOf G' (app E1 E2) Ty
< apply IH to _ Ty1 _.
Subgoal 4:
Variables: G Ty G' Ty1 E2 E1
IH : forall G E Ty G',
is_e E -> typeOf G E Ty * -> (forall X XTy,
lookup G X XTy -> lookup G' X XTy) -> typeOf G' E Ty
Ty : typeOf G (app E1 E2) Ty @
Lkp : forall X XTy, lookup G X XTy -> lookup G' X XTy
Ty1 : typeOf G E1 (arrowTy Ty1 Ty) *
Ty2 : typeOf G E2 Ty1 *
Is : is_e E1
Is1 : is_e E2
H1 : typeOf G' E1 (arrowTy Ty1 Ty)
============================
typeOf G' (app E1 E2) Ty
< apply IH to _ Ty2 _.
Subgoal 4:
Variables: G Ty G' Ty1 E2 E1
IH : forall G E Ty G',
is_e E -> typeOf G E Ty * -> (forall X XTy,
lookup G X XTy -> lookup G' X XTy) -> typeOf G' E Ty
Ty : typeOf G (app E1 E2) Ty @
Lkp : forall X XTy, lookup G X XTy -> lookup G' X XTy
Ty1 : typeOf G E1 (arrowTy Ty1 Ty) *
Ty2 : typeOf G E2 Ty1 *
Is : is_e E1
Is1 : is_e E2
H1 : typeOf G' E1 (arrowTy Ty1 Ty)
H2 : typeOf G' E2 Ty1
============================
typeOf G' (app E1 E2) Ty
< search.
Subgoal 5:
Variables: G G' I
IH : forall G E Ty G',
is_e E -> typeOf G E Ty * -> (forall X XTy,
lookup G X XTy -> lookup G' X XTy) -> typeOf G' E Ty
IsE : is_e (intE I)
Ty : typeOf G (intE I) intTy @
Lkp : forall X XTy, lookup G X XTy -> lookup G' X XTy
============================
typeOf G' (intE I) intTy
< search.
Subgoal 6:
Variables: G G' E2 E1
IH : forall G E Ty G',
is_e E -> typeOf G E Ty * -> (forall X XTy,
lookup G X XTy -> lookup G' X XTy) -> typeOf G' E Ty
IsE : is_e (plus E1 E2)
Ty : typeOf G (plus E1 E2) intTy @
Lkp : forall X XTy, lookup G X XTy -> lookup G' X XTy
Ty1 : typeOf G E1 intTy *
Ty2 : typeOf G E2 intTy *
============================
typeOf G' (plus E1 E2) intTy
< case IsE.
Subgoal 6:
Variables: G G' E2 E1
IH : forall G E Ty G',
is_e E -> typeOf G E Ty * -> (forall X XTy,
lookup G X XTy -> lookup G' X XTy) -> typeOf G' E Ty
Ty : typeOf G (plus E1 E2) intTy @
Lkp : forall X XTy, lookup G X XTy -> lookup G' X XTy
Ty1 : typeOf G E1 intTy *
Ty2 : typeOf G E2 intTy *
H1 : is_e E1
H2 : is_e E2
============================
typeOf G' (plus E1 E2) intTy
< apply IH to _ Ty1 Lkp.
Subgoal 6:
Variables: G G' E2 E1
IH : forall G E Ty G',
is_e E -> typeOf G E Ty * -> (forall X XTy,
lookup G X XTy -> lookup G' X XTy) -> typeOf G' E Ty
Ty : typeOf G (plus E1 E2) intTy @
Lkp : forall X XTy, lookup G X XTy -> lookup G' X XTy
Ty1 : typeOf G E1 intTy *
Ty2 : typeOf G E2 intTy *
H1 : is_e E1
H2 : is_e E2
H3 : typeOf G' E1 intTy
============================
typeOf G' (plus E1 E2) intTy
< apply IH to _ Ty2 Lkp.
Subgoal 6:
Variables: G G' E2 E1
IH : forall G E Ty G',
is_e E -> typeOf G E Ty * -> (forall X XTy,
lookup G X XTy -> lookup G' X XTy) -> typeOf G' E Ty
Ty : typeOf G (plus E1 E2) intTy @
Lkp : forall X XTy, lookup G X XTy -> lookup G' X XTy
Ty1 : typeOf G E1 intTy *
Ty2 : typeOf G E2 intTy *
H1 : is_e E1
H2 : is_e E2
H3 : typeOf G' E1 intTy
H4 : typeOf G' E2 intTy
============================
typeOf G' (plus E1 E2) intTy
< search.
Subgoal 7:
Variables: G Ty G' E_T
IH : forall G E Ty G',
is_e E -> typeOf G E Ty * -> (forall X XTy,
lookup G X XTy -> lookup G' X XTy) -> typeOf G' E Ty
IsE : is_e <unknown I e>
Ty : typeOf G <unknown I e> Ty @
Lkp : forall X XTy, lookup G X XTy -> lookup G' X XTy
Ty1 : |{e}- <unknown I e> ~~> E_T
Ty2 : typeOf G E_T Ty *
============================
typeOf G' <unknown I e> Ty
< apply proj_is to Ty1 IsE.
Subgoal 7:
Variables: G Ty G' E_T
IH : forall G E Ty G',
is_e E -> typeOf G E Ty * -> (forall X XTy,
lookup G X XTy -> lookup G' X XTy) -> typeOf G' E Ty
IsE : is_e <unknown I e>
Ty : typeOf G <unknown I e> Ty @
Lkp : forall X XTy, lookup G X XTy -> lookup G' X XTy
Ty1 : |{e}- <unknown I e> ~~> E_T
Ty2 : typeOf G E_T Ty *
H1 : is_e E_T
============================
typeOf G' <unknown I e> Ty
< apply IH to _ Ty2 _.
Subgoal 7:
Variables: G Ty G' E_T
IH : forall G E Ty G',
is_e E -> typeOf G E Ty * -> (forall X XTy,
lookup G X XTy -> lookup G' X XTy) -> typeOf G' E Ty
IsE : is_e <unknown I e>
Ty : typeOf G <unknown I e> Ty @
Lkp : forall X XTy, lookup G X XTy -> lookup G' X XTy
Ty1 : |{e}- <unknown I e> ~~> E_T
Ty2 : typeOf G E_T Ty *
H1 : is_e E_T
H2 : typeOf G' E_T Ty
============================
typeOf G' <unknown I e> Ty
< search.
Proof completed.
< Theorem any_ctx :
forall E Ty G, is_e E -> typeOf [] E Ty -> typeOf G E Ty.
============================
forall E Ty G, is_e E -> typeOf [] E Ty -> typeOf G E Ty
< intros Is Ty.
Variables: E Ty G
Is : is_e E
Ty : typeOf [] E Ty
============================
typeOf G E Ty
< backchain type_weakening to
G = [].
Variables: E Ty G
Is : is_e E
Ty : typeOf [] E Ty
============================
forall X XTy, lookup [] X XTy -> lookup G X XTy
< intros L.
Variables: E Ty G X XTy
Is : is_e E
Ty : typeOf [] E Ty
L : lookup [] X XTy
============================
lookup G X XTy
< case L.
Proof completed.
< Extensible_Theorem
tyabs_or_not : forall E,
IsE : is_e E ->
(exists X Ty B, E = tyabs X Ty B) \/
((exists X Ty B, E = tyabs X Ty B) -> false)
on IsE.
Subgoal 1:
Variables: S
IH : forall E,
is_e E * -> (exists X Ty B, E = tyabs X Ty B) \/
((exists X Ty B, E = tyabs X Ty B) -> false)
IsE : is_e (var S) @
IsE1 : is_string S
============================
(exists X Ty B, var S = tyabs X Ty B) \/
((exists X Ty B, var S = tyabs X Ty B) -> false)
< right.
Subgoal 1:
Variables: S
IH : forall E,
is_e E * -> (exists X Ty B, E = tyabs X Ty B) \/
((exists X Ty B, E = tyabs X Ty B) -> false)
IsE : is_e (var S) @
IsE1 : is_string S
============================
(exists X Ty B, var S = tyabs X Ty B) -> false
< intros E.
Subgoal 1:
Variables: S
IH : forall E,
is_e E * -> (exists X Ty B, E = tyabs X Ty B) \/
((exists X Ty B, E = tyabs X Ty B) -> false)
IsE : is_e (var S) @
IsE1 : is_string S
E : exists X Ty B, var S = tyabs X Ty B
============================
false
< case E.
Subgoal 2:
Variables: E1 S
IH : forall E,
is_e E * -> (exists X Ty B, E = tyabs X Ty B) \/
((exists X Ty B, E = tyabs X Ty B) -> false)
IsE : is_e (abs S E1) @
IsE1 : is_string S
IsE2 : is_e E1 *
============================
(exists X Ty B, abs S E1 = tyabs X Ty B) \/
((exists X Ty B, abs S E1 = tyabs X Ty B) -> false)
< right.
Subgoal 2:
Variables: E1 S
IH : forall E,
is_e E * -> (exists X Ty B, E = tyabs X Ty B) \/
((exists X Ty B, E = tyabs X Ty B) -> false)
IsE : is_e (abs S E1) @
IsE1 : is_string S
IsE2 : is_e E1 *
============================
(exists X Ty B, abs S E1 = tyabs X Ty B) -> false
< intros E.
Subgoal 2:
Variables: E1 S
IH : forall E,
is_e E * -> (exists X Ty B, E = tyabs X Ty B) \/
((exists X Ty B, E = tyabs X Ty B) -> false)
IsE : is_e (abs S E1) @
IsE1 : is_string S
IsE2 : is_e E1 *
E : exists X Ty B, abs S E1 = tyabs X Ty B
============================
false
< case E.
Subgoal 3:
Variables: E2 E1
IH : forall E,
is_e E * -> (exists X Ty B, E = tyabs X Ty B) \/
((exists X Ty B, E = tyabs X Ty B) -> false)
IsE : is_e (app E1 E2) @
IsE1 : is_e E1 *
IsE2 : is_e E2 *
============================
(exists X Ty B, app E1 E2 = tyabs X Ty B) \/
((exists X Ty B, app E1 E2 = tyabs X Ty B) -> false)
< right.
Subgoal 3:
Variables: E2 E1
IH : forall E,
is_e E * -> (exists X Ty B, E = tyabs X Ty B) \/
((exists X Ty B, E = tyabs X Ty B) -> false)
IsE : is_e (app E1 E2) @
IsE1 : is_e E1 *
IsE2 : is_e E2 *
============================
(exists X Ty B, app E1 E2 = tyabs X Ty B) -> false
< intros E.
Subgoal 3:
Variables: E2 E1
IH : forall E,
is_e E * -> (exists X Ty B, E = tyabs X Ty B) \/
((exists X Ty B, E = tyabs X Ty B) -> false)
IsE : is_e (app E1 E2) @
IsE1 : is_e E1 *
IsE2 : is_e E2 *
E : exists X Ty B, app E1 E2 = tyabs X Ty B
============================
false
< case E.
Subgoal 4:
Variables: I
IH : forall E,
is_e E * -> (exists X Ty B, E = tyabs X Ty B) \/
((exists X Ty B, E = tyabs X Ty B) -> false)
IsE : is_e (intE I) @
IsE1 : is_integer I
============================
(exists X Ty B, intE I = tyabs X Ty B) \/
((exists X Ty B, intE I = tyabs X Ty B) -> false)
< search.
Subgoal 5:
Variables: E2 E1
IH : forall E,
is_e E * -> (exists X Ty B, E = tyabs X Ty B) \/
((exists X Ty B, E = tyabs X Ty B) -> false)
IsE : is_e (plus E1 E2) @
IsE1 : is_e E1 *
IsE2 : is_e E2 *
============================
(exists X Ty B, plus E1 E2 = tyabs X Ty B) \/
((exists X Ty B, plus E1 E2 = tyabs X Ty B) -> false)
< search.
Subgoal 6:
Variables: E1 Ty S
IH : forall E,
is_e E * -> (exists X Ty B, E = tyabs X Ty B) \/
((exists X Ty B, E = tyabs X Ty B) -> false)
IsE : is_e (tyabs S Ty E1) @
IsE1 : is_string S
IsE2 : is_ty Ty
IsE3 : is_e E1 *
============================
(exists X Ty1 B, tyabs S Ty E1 = tyabs X Ty1 B) \/
((exists X Ty1 B, tyabs S Ty E1 = tyabs X Ty1 B) -> false)
< search.
Subgoal 7:
Variables: X_T
IH : forall E,
is_e E * -> (exists X Ty B, E = tyabs X Ty B) \/
((exists X Ty B, E = tyabs X Ty B) -> false)
IsE : is_e <unknown K is_e> @
IsE1 : |{e}- <unknown K is_e> ~~> X_T
IsE2 : is_e X_T *
============================
(exists X Ty B, <unknown K is_e> = tyabs X Ty B) \/
((exists X Ty B, <unknown K is_e> = tyabs X Ty B) -> false)
< right.
Subgoal 7:
Variables: X_T
IH : forall E,
is_e E * -> (exists X Ty B, E = tyabs X Ty B) \/
((exists X Ty B, E = tyabs X Ty B) -> false)
IsE : is_e <unknown K is_e> @
IsE1 : |{e}- <unknown K is_e> ~~> X_T
IsE2 : is_e X_T *
============================
(exists X Ty B, <unknown K is_e> = tyabs X Ty B) -> false
< intros E.
Subgoal 7:
Variables: X_T
IH : forall E,
is_e E * -> (exists X Ty B, E = tyabs X Ty B) \/
((exists X Ty B, E = tyabs X Ty B) -> false)
IsE : is_e <unknown K is_e> @
IsE1 : |{e}- <unknown K is_e> ~~> X_T
IsE2 : is_e X_T *
E : exists X Ty B, <unknown K is_e> = tyabs X Ty B
============================
false
< case E.
Proof completed.
< Extensible_Theorem
subst_type_preservation : forall X R E S G TyE TyX G',
IsE : is_e E ->
IsX : is_string X ->
IsR : is_e R ->
S : subst X R E S ->
TyE : typeOf G E TyE ->
TyR : typeOf [] R TyX ->
Lkp : lookup G X TyX ->
Slct : select (X, TyX) G' G ->
typeOf G' S TyE
on TyE.
Subgoal 1:
Variables: X R S G TyE TyX G' X1
IH : forall X R E S G TyE TyX G',
is_e E -> is_string X -> is_e R -> subst X R E S -> typeOf G E TyE * -> typeOf [] R TyX ->
lookup G X TyX -> select (X, TyX) G' G -> typeOf G' S TyE
IsE : is_e (var X1)
IsX : is_string X
IsR : is_e R
S : subst X R (var X1) S
TyE : typeOf G (var X1) TyE @
TyR : typeOf [] R TyX
Lkp : lookup G X TyX
Slct : select (X, TyX) G' G
TyE1 : lookup G X1 TyE
============================
typeOf G' S TyE
< S: case S.
Subgoal 1.1:
Variables: S G TyE TyX G' X1
IH : forall X R E S G TyE TyX G',
is_e E -> is_string X -> is_e R -> subst X R E S -> typeOf G E TyE * -> typeOf [] R TyX ->
lookup G X TyX -> select (X, TyX) G' G -> typeOf G' S TyE
IsE : is_e (var X1)
IsX : is_string X1
IsR : is_e S
TyE : typeOf G (var X1) TyE @
TyR : typeOf [] S TyX
Lkp : lookup G X1 TyX
Slct : select (X1, TyX) G' G
TyE1 : lookup G X1 TyE
============================
typeOf G' S TyE
< apply any_ctx to _ TyR with
G = G'.
Subgoal 1.1:
Variables: S G TyE TyX G' X1
IH : forall X R E S G TyE TyX G',
is_e E -> is_string X -> is_e R -> subst X R E S -> typeOf G E TyE * -> typeOf [] R TyX ->
lookup G X TyX -> select (X, TyX) G' G -> typeOf G' S TyE
IsE : is_e (var X1)
IsX : is_string X1
IsR : is_e S
TyE : typeOf G (var X1) TyE @
TyR : typeOf [] S TyX
Lkp : lookup G X1 TyX
Slct : select (X1, TyX) G' G
TyE1 : lookup G X1 TyE
H1 : typeOf G' S TyX
============================
typeOf G' S TyE
< apply lookup_unique to Lkp TyE1.
Subgoal 1.1:
Variables: S G TyE G' X1
IH : forall X R E S G TyE TyX G',
is_e E -> is_string X -> is_e R -> subst X R E S -> typeOf G E TyE * -> typeOf [] R TyX ->
lookup G X TyX -> select (X, TyX) G' G -> typeOf G' S TyE
IsE : is_e (var X1)
IsX : is_string X1
IsR : is_e S
TyE : typeOf G (var X1) TyE @
TyR : typeOf [] S TyE
Lkp : lookup G X1 TyE
Slct : select (X1, TyE) G' G
TyE1 : lookup G X1 TyE
H1 : typeOf G' S TyE
============================
typeOf G' S TyE
< search.
Subgoal 1.2:
Variables: X R G TyE TyX G' X1
IH : forall X R E S G TyE TyX G',
is_e E -> is_string X -> is_e R -> subst X R E S -> typeOf G E TyE * -> typeOf [] R TyX ->
lookup G X TyX -> select (X, TyX) G' G -> typeOf G' S TyE
IsE : is_e (var X1)
IsX : is_string X
IsR : is_e R
TyE : typeOf G (var X1) TyE @
TyR : typeOf [] R TyX
Lkp : lookup G X TyX
Slct : select (X, TyX) G' G
TyE1 : lookup G X1 TyE
S : X = X1 -> false
============================
typeOf G' (var X1) TyE
< NEq: assert X1 = X -> false.
Subgoal 1.2.1:
Variables: X R G TyE TyX G' X1
IH : forall X R E S G TyE TyX G',
is_e E -> is_string X -> is_e R -> subst X R E S -> typeOf G E TyE * -> typeOf [] R TyX ->
lookup G X TyX -> select (X, TyX) G' G -> typeOf G' S TyE
IsE : is_e (var X1)
IsX : is_string X
IsR : is_e R
TyE : typeOf G (var X1) TyE @
TyR : typeOf [] R TyX
Lkp : lookup G X TyX
Slct : select (X, TyX) G' G
TyE1 : lookup G X1 TyE
S : X = X1 -> false
============================
X1 = X -> false
< intros E.
Subgoal 1.2.1:
Variables: X R G TyE TyX G' X1
IH : forall X R E S G TyE TyX G',
is_e E -> is_string X -> is_e R -> subst X R E S -> typeOf G E TyE * -> typeOf [] R TyX ->
lookup G X TyX -> select (X, TyX) G' G -> typeOf G' S TyE
IsE : is_e (var X1)
IsX : is_string X
IsR : is_e R
TyE : typeOf G (var X1) TyE @
TyR : typeOf [] R TyX
Lkp : lookup G X TyX
Slct : select (X, TyX) G' G
TyE1 : lookup G X1 TyE
S : X = X1 -> false
E : X1 = X
============================
false
< case E.
Subgoal 1.2.1:
Variables: X R G TyE TyX G'
IH : forall X R E S G TyE TyX G',
is_e E -> is_string X -> is_e R -> subst X R E S -> typeOf G E TyE * -> typeOf [] R TyX ->
lookup G X TyX -> select (X, TyX) G' G -> typeOf G' S TyE
IsE : is_e (var X)
IsX : is_string X
IsR : is_e R
TyE : typeOf G (var X) TyE @
TyR : typeOf [] R TyX
Lkp : lookup G X TyX
Slct : select (X, TyX) G' G
TyE1 : lookup G X TyE
S : X = X -> false
============================
false
< backchain S.
Subgoal 1.2:
Variables: X R G TyE TyX G' X1
IH : forall X R E S G TyE TyX G',
is_e E -> is_string X -> is_e R -> subst X R E S -> typeOf G E TyE * -> typeOf [] R TyX ->
lookup G X TyX -> select (X, TyX) G' G -> typeOf G' S TyE
IsE : is_e (var X1)
IsX : is_string X
IsR : is_e R
TyE : typeOf G (var X1) TyE @
TyR : typeOf [] R TyX
Lkp : lookup G X TyX
Slct : select (X, TyX) G' G
TyE1 : lookup G X1 TyE
S : X = X1 -> false
NEq : X1 = X -> false
============================
typeOf G' (var X1) TyE
< apply select_lookup to TyE1 Slct NEq.
Subgoal 1.2:
Variables: X R G TyE TyX G' X1
IH : forall X R E S G TyE TyX G',
is_e E -> is_string X -> is_e R -> subst X R E S -> typeOf G E TyE * -> typeOf [] R TyX ->
lookup G X TyX -> select (X, TyX) G' G -> typeOf G' S TyE
IsE : is_e (var X1)
IsX : is_string X
IsR : is_e R
TyE : typeOf G (var X1) TyE @
TyR : typeOf [] R TyX
Lkp : lookup G X TyX
Slct : select (X, TyX) G' G
TyE1 : lookup G X1 TyE
S : X = X1 -> false
NEq : X1 = X -> false
H1 : lookup G' X1 TyE
============================
typeOf G' (var X1) TyE
< search.
Subgoal 2:
Variables: X R S G TyX G' Ty2 Ty1 Body X1
IH : forall X R E S G TyE TyX G',
is_e E -> is_string X -> is_e R -> subst X R E S -> typeOf G E TyE * -> typeOf [] R TyX ->
lookup G X TyX -> select (X, TyX) G' G -> typeOf G' S TyE
IsE : is_e (abs X1 Body)
IsX : is_string X
IsR : is_e R
S : subst X R (abs X1 Body) S
TyE : typeOf G (abs X1 Body) (arrowTy Ty1 Ty2) @
TyR : typeOf [] R TyX
Lkp : lookup G X TyX
Slct : select (X, TyX) G' G
TyE1 : typeOf ((X1, Ty1)::G) Body Ty2 *
============================
typeOf G' S (arrowTy Ty1 Ty2)
< Is: case IsE.
Subgoal 2:
Variables: X R S G TyX G' Ty2 Ty1 Body X1
IH : forall X R E S G TyE TyX G',
is_e E -> is_string X -> is_e R -> subst X R E S -> typeOf G E TyE * -> typeOf [] R TyX ->
lookup G X TyX -> select (X, TyX) G' G -> typeOf G' S TyE
IsX : is_string X
IsR : is_e R
S : subst X R (abs X1 Body) S
TyE : typeOf G (abs X1 Body) (arrowTy Ty1 Ty2) @
TyR : typeOf [] R TyX
Lkp : lookup G X TyX
Slct : select (X, TyX) G' G
TyE1 : typeOf ((X1, Ty1)::G) Body Ty2 *
Is : is_string X1
Is1 : is_e Body
============================
typeOf G' S (arrowTy Ty1 Ty2)
< S: case S.
Subgoal 2.1:
Variables: R G TyX G' Ty2 Ty1 Body X1
IH : forall X R E S G TyE TyX G',
is_e E -> is_string X -> is_e R -> subst X R E S -> typeOf G E TyE * -> typeOf [] R TyX ->
lookup G X TyX -> select (X, TyX) G' G -> typeOf G' S TyE
IsX : is_string X1
IsR : is_e R
TyE : typeOf G (abs X1 Body) (arrowTy Ty1 Ty2) @
TyR : typeOf [] R TyX
Lkp : lookup G X1 TyX
Slct : select (X1, TyX) G' G
TyE1 : typeOf ((X1, Ty1)::G) Body Ty2 *
Is : is_string X1
Is1 : is_e Body
============================
typeOf G' (abs X1 Body) (arrowTy Ty1 Ty2)
< L: assert forall Z ZTy,
lookup ((X1, Ty1)::G) Z ZTy -> lookup ((X1, Ty1)::G') Z ZTy.
Subgoal 2.1.1:
Variables: R G TyX G' Ty2 Ty1 Body X1
IH : forall X R E S G TyE TyX G',
is_e E -> is_string X -> is_e R -> subst X R E S -> typeOf G E TyE * -> typeOf [] R TyX ->
lookup G X TyX -> select (X, TyX) G' G -> typeOf G' S TyE
IsX : is_string X1
IsR : is_e R
TyE : typeOf G (abs X1 Body) (arrowTy Ty1 Ty2) @
TyR : typeOf [] R TyX
Lkp : lookup G X1 TyX
Slct : select (X1, TyX) G' G
TyE1 : typeOf ((X1, Ty1)::G) Body Ty2 *
Is : is_string X1
Is1 : is_e Body
============================
forall Z ZTy, lookup ((X1, Ty1)::G) Z ZTy -> lookup ((X1, Ty1)::G') Z ZTy
< intros L.
Subgoal 2.1.1:
Variables: R G TyX G' Ty2 Ty1 Body X1 Z ZTy
IH : forall X R E S G TyE TyX G',
is_e E -> is_string X -> is_e R -> subst X R E S -> typeOf G E TyE * -> typeOf [] R TyX ->
lookup G X TyX -> select (X, TyX) G' G -> typeOf G' S TyE
IsX : is_string X1
IsR : is_e R
TyE : typeOf G (abs X1 Body) (arrowTy Ty1 Ty2) @
TyR : typeOf [] R TyX
Lkp : lookup G X1 TyX
Slct : select (X1, TyX) G' G
TyE1 : typeOf ((X1, Ty1)::G) Body Ty2 *
Is : is_string X1
Is1 : is_e Body
L : lookup ((X1, Ty1)::G) Z ZTy
============================
lookup ((X1, Ty1)::G') Z ZTy
< L: case L.
Subgoal 2.1.1.1:
Variables: R G TyX G' Ty2 Body Z ZTy
IH : forall X R E S G TyE TyX G',
is_e E -> is_string X -> is_e R -> subst X R E S -> typeOf G E TyE * -> typeOf [] R TyX ->
lookup G X TyX -> select (X, TyX) G' G -> typeOf G' S TyE
IsX : is_string Z
IsR : is_e R
TyE : typeOf G (abs Z Body) (arrowTy ZTy Ty2) @
TyR : typeOf [] R TyX
Lkp : lookup G Z TyX
Slct : select (Z, TyX) G' G
TyE1 : typeOf ((Z, ZTy)::G) Body Ty2 *
Is : is_string Z
Is1 : is_e Body
============================
lookup ((Z, ZTy)::G') Z ZTy
< search.
Subgoal 2.1.1.2:
Variables: R G TyX G' Ty2 Ty1 Body X1 Z ZTy
IH : forall X R E S G TyE TyX G',
is_e E -> is_string X -> is_e R -> subst X R E S -> typeOf G E TyE * -> typeOf [] R TyX ->
lookup G X TyX -> select (X, TyX) G' G -> typeOf G' S TyE
IsX : is_string X1
IsR : is_e R
TyE : typeOf G (abs X1 Body) (arrowTy Ty1 Ty2) @
TyR : typeOf [] R TyX
Lkp : lookup G X1 TyX
Slct : select (X1, TyX) G' G
TyE1 : typeOf ((X1, Ty1)::G) Body Ty2 *
Is : is_string X1
Is1 : is_e Body
L : X1 = Z -> false
L1 : lookup G Z ZTy
============================
lookup ((X1, Ty1)::G') Z ZTy
< NEq: assert Z = X1 -> false.
Subgoal 2.1.1.2.1:
Variables: R G TyX G' Ty2 Ty1 Body X1 Z ZTy
IH : forall X R E S G TyE TyX G',
is_e E -> is_string X -> is_e R -> subst X R E S -> typeOf G E TyE * -> typeOf [] R TyX ->
lookup G X TyX -> select (X, TyX) G' G -> typeOf G' S TyE
IsX : is_string X1
IsR : is_e R
TyE : typeOf G (abs X1 Body) (arrowTy Ty1 Ty2) @
TyR : typeOf [] R TyX
Lkp : lookup G X1 TyX
Slct : select (X1, TyX) G' G
TyE1 : typeOf ((X1, Ty1)::G) Body Ty2 *
Is : is_string X1
Is1 : is_e Body
L : X1 = Z -> false
L1 : lookup G Z ZTy
============================
Z = X1 -> false
< intros E.
Subgoal 2.1.1.2.1:
Variables: R G TyX G' Ty2 Ty1 Body X1 Z ZTy
IH : forall X R E S G TyE TyX G',
is_e E -> is_string X -> is_e R -> subst X R E S -> typeOf G E TyE * -> typeOf [] R TyX ->
lookup G X TyX -> select (X, TyX) G' G -> typeOf G' S TyE
IsX : is_string X1
IsR : is_e R
TyE : typeOf G (abs X1 Body) (arrowTy Ty1 Ty2) @
TyR : typeOf [] R TyX
Lkp : lookup G X1 TyX
Slct : select (X1, TyX) G' G
TyE1 : typeOf ((X1, Ty1)::G) Body Ty2 *
Is : is_string X1
Is1 : is_e Body
L : X1 = Z -> false
L1 : lookup G Z ZTy
E : Z = X1
============================
false
< case E.
Subgoal 2.1.1.2.1:
Variables: R G TyX G' Ty2 Ty1 Body X1 ZTy
IH : forall X R E S G TyE TyX G',
is_e E -> is_string X -> is_e R -> subst X R E S -> typeOf G E TyE * -> typeOf [] R TyX ->
lookup G X TyX -> select (X, TyX) G' G -> typeOf G' S TyE
IsX : is_string X1
IsR : is_e R
TyE : typeOf G (abs X1 Body) (arrowTy Ty1 Ty2) @
TyR : typeOf [] R TyX
Lkp : lookup G X1 TyX
Slct : select (X1, TyX) G' G
TyE1 : typeOf ((X1, Ty1)::G) Body Ty2 *
Is : is_string X1
Is1 : is_e Body
L : X1 = X1 -> false
L1 : lookup G X1 ZTy
============================
false
< backchain L.
Subgoal 2.1.1.2:
Variables: R G TyX G' Ty2 Ty1 Body X1 Z ZTy
IH : forall X R E S G TyE TyX G',
is_e E -> is_string X -> is_e R -> subst X R E S -> typeOf G E TyE * -> typeOf [] R TyX ->
lookup G X TyX -> select (X, TyX) G' G -> typeOf G' S TyE
IsX : is_string X1
IsR : is_e R
TyE : typeOf G (abs X1 Body) (arrowTy Ty1 Ty2) @
TyR : typeOf [] R TyX
Lkp : lookup G X1 TyX
Slct : select (X1, TyX) G' G
TyE1 : typeOf ((X1, Ty1)::G) Body Ty2 *
Is : is_string X1
Is1 : is_e Body
L : X1 = Z -> false
L1 : lookup G Z ZTy
NEq : Z = X1 -> false
============================
lookup ((X1, Ty1)::G') Z ZTy
< apply select_lookup to L1 Slct NEq.
Subgoal 2.1.1.2:
Variables: R G TyX G' Ty2 Ty1 Body X1 Z ZTy
IH : forall X R E S G TyE TyX G',
is_e E -> is_string X -> is_e R -> subst X R E S -> typeOf G E TyE * -> typeOf [] R TyX ->
lookup G X TyX -> select (X, TyX) G' G -> typeOf G' S TyE
IsX : is_string X1
IsR : is_e R
TyE : typeOf G (abs X1 Body) (arrowTy Ty1 Ty2) @
TyR : typeOf [] R TyX
Lkp : lookup G X1 TyX
Slct : select (X1, TyX) G' G
TyE1 : typeOf ((X1, Ty1)::G) Body Ty2 *
Is : is_string X1
Is1 : is_e Body
L : X1 = Z -> false
L1 : lookup G Z ZTy
NEq : Z = X1 -> false
H1 : lookup G' Z ZTy
============================
lookup ((X1, Ty1)::G') Z ZTy
< search.
Subgoal 2.1:
Variables: R G TyX G' Ty2 Ty1 Body X1
IH : forall X R E S G TyE TyX G',
is_e E -> is_string X -> is_e R -> subst X R E S -> typeOf G E TyE * -> typeOf [] R TyX ->
lookup G X TyX -> select (X, TyX) G' G -> typeOf G' S TyE
IsX : is_string X1
IsR : is_e R
TyE : typeOf G (abs X1 Body) (arrowTy Ty1 Ty2) @
TyR : typeOf [] R TyX
Lkp : lookup G X1 TyX
Slct : select (X1, TyX) G' G
TyE1 : typeOf ((X1, Ty1)::G) Body Ty2 *
Is : is_string X1
Is1 : is_e Body
L : forall Z ZTy, lookup ((X1, Ty1)::G) Z ZTy -> lookup ((X1, Ty1)::G') Z ZTy
============================
typeOf G' (abs X1 Body) (arrowTy Ty1 Ty2)
< apply type_weakening to _ TyE1 L.
Subgoal 2.1:
Variables: R G TyX G' Ty2 Ty1 Body X1
IH : forall X R E S G TyE TyX G',
is_e E -> is_string X -> is_e R -> subst X R E S -> typeOf G E TyE * -> typeOf [] R TyX ->
lookup G X TyX -> select (X, TyX) G' G -> typeOf G' S TyE
IsX : is_string X1
IsR : is_e R
TyE : typeOf G (abs X1 Body) (arrowTy Ty1 Ty2) @
TyR : typeOf [] R TyX
Lkp : lookup G X1 TyX
Slct : select (X1, TyX) G' G
TyE1 : typeOf ((X1, Ty1)::G) Body Ty2 *
Is : is_string X1
Is1 : is_e Body
L : forall Z ZTy, lookup ((X1, Ty1)::G) Z ZTy -> lookup ((X1, Ty1)::G') Z ZTy
H1 : typeOf ((X1, Ty1)::G') Body Ty2
============================
typeOf G' (abs X1 Body) (arrowTy Ty1 Ty2)
< search.
Subgoal 2.2:
Variables: X R G TyX G' Ty2 Ty1 Body X1 B
IH : forall X R E S G TyE TyX G',
is_e E -> is_string X -> is_e R -> subst X R E S -> typeOf G E TyE * -> typeOf [] R TyX ->
lookup G X TyX -> select (X, TyX) G' G -> typeOf G' S TyE
IsX : is_string X
IsR : is_e R
TyE : typeOf G (abs X1 Body) (arrowTy Ty1 Ty2) @
TyR : typeOf [] R TyX
Lkp : lookup G X TyX
Slct : select (X, TyX) G' G
TyE1 : typeOf ((X1, Ty1)::G) Body Ty2 *
Is : is_string X1
Is1 : is_e Body
S : X = X1 -> false
S1 : subst X R Body B
============================
typeOf G' (abs X1 B) (arrowTy Ty1 Ty2)
< assert X1 = X -> false.
Subgoal 2.2.1:
Variables: X R G TyX G' Ty2 Ty1 Body X1 B
IH : forall X R E S G TyE TyX G',
is_e E -> is_string X -> is_e R -> subst X R E S -> typeOf G E TyE * -> typeOf [] R TyX ->
lookup G X TyX -> select (X, TyX) G' G -> typeOf G' S TyE
IsX : is_string X
IsR : is_e R
TyE : typeOf G (abs X1 Body) (arrowTy Ty1 Ty2) @
TyR : typeOf [] R TyX
Lkp : lookup G X TyX
Slct : select (X, TyX) G' G
TyE1 : typeOf ((X1, Ty1)::G) Body Ty2 *
Is : is_string X1
Is1 : is_e Body
S : X = X1 -> false
S1 : subst X R Body B
============================
X1 = X -> false
< intros E.
Subgoal 2.2.1:
Variables: X R G TyX G' Ty2 Ty1 Body X1 B
IH : forall X R E S G TyE TyX G',
is_e E -> is_string X -> is_e R -> subst X R E S -> typeOf G E TyE * -> typeOf [] R TyX ->
lookup G X TyX -> select (X, TyX) G' G -> typeOf G' S TyE
IsX : is_string X
IsR : is_e R
TyE : typeOf G (abs X1 Body) (arrowTy Ty1 Ty2) @
TyR : typeOf [] R TyX
Lkp : lookup G X TyX
Slct : select (X, TyX) G' G
TyE1 : typeOf ((X1, Ty1)::G) Body Ty2 *
Is : is_string X1
Is1 : is_e Body
S : X = X1 -> false
S1 : subst X R Body B
E : X1 = X
============================
false
< case E.
Subgoal 2.2.1:
Variables: X R G TyX G' Ty2 Ty1 Body B
IH : forall X R E S G TyE TyX G',
is_e E -> is_string X -> is_e R -> subst X R E S -> typeOf G E TyE * -> typeOf [] R TyX ->
lookup G X TyX -> select (X, TyX) G' G -> typeOf G' S TyE
IsX : is_string X
IsR : is_e R
TyE : typeOf G (abs X Body) (arrowTy Ty1 Ty2) @
TyR : typeOf [] R TyX
Lkp : lookup G X TyX
Slct : select (X, TyX) G' G
TyE1 : typeOf ((X, Ty1)::G) Body Ty2 *
Is : is_string X
Is1 : is_e Body
S : X = X -> false
S1 : subst X R Body B
============================
false
< backchain S.
Subgoal 2.2:
Variables: X R G TyX G' Ty2 Ty1 Body X1 B
IH : forall X R E S G TyE TyX G',
is_e E -> is_string X -> is_e R -> subst X R E S -> typeOf G E TyE * -> typeOf [] R TyX ->
lookup G X TyX -> select (X, TyX) G' G -> typeOf G' S TyE
IsX : is_string X
IsR : is_e R
TyE : typeOf G (abs X1 Body) (arrowTy Ty1 Ty2) @
TyR : typeOf [] R TyX
Lkp : lookup G X TyX
Slct : select (X, TyX) G' G
TyE1 : typeOf ((X1, Ty1)::G) Body Ty2 *
Is : is_string X1
Is1 : is_e Body
S : X = X1 -> false
S1 : subst X R Body B
H1 : X1 = X -> false
============================
typeOf G' (abs X1 B) (arrowTy Ty1 Ty2)
< apply IH to _ _ _ S1 TyE1 _ _ _ with
G' = (X1, Ty1)::G'.
Subgoal 2.2:
Variables: X R G TyX G' Ty2 Ty1 Body X1 B
IH : forall X R E S G TyE TyX G',
is_e E -> is_string X -> is_e R -> subst X R E S -> typeOf G E TyE * -> typeOf [] R TyX ->
lookup G X TyX -> select (X, TyX) G' G -> typeOf G' S TyE
IsX : is_string X
IsR : is_e R
TyE : typeOf G (abs X1 Body) (arrowTy Ty1 Ty2) @
TyR : typeOf [] R TyX
Lkp : lookup G X TyX
Slct : select (X, TyX) G' G
TyE1 : typeOf ((X1, Ty1)::G) Body Ty2 *
Is : is_string X1
Is1 : is_e Body
S : X = X1 -> false
S1 : subst X R Body B
H1 : X1 = X -> false
H2 : typeOf ((X1, Ty1)::G') B Ty2
============================
typeOf G' (abs X1 B) (arrowTy Ty1 Ty2)
< search.
Subgoal 3:
Variables: X R S G TyX G' Ty2 Ty1 Body X1
IH : forall X R E S G TyE TyX G',
is_e E -> is_string X -> is_e R -> subst X R E S -> typeOf G E TyE * -> typeOf [] R TyX ->
lookup G X TyX -> select (X, TyX) G' G -> typeOf G' S TyE
IsE : is_e (tyabs X1 Ty1 Body)
IsX : is_string X
IsR : is_e R
S : subst X R (tyabs X1 Ty1 Body) S
TyE : typeOf G (tyabs X1 Ty1 Body) (arrowTy Ty1 Ty2) @
TyR : typeOf [] R TyX
Lkp : lookup G X TyX
Slct : select (X, TyX) G' G
TyE1 : typeOf ((X1, Ty1)::G) Body Ty2 *
============================
typeOf G' S (arrowTy Ty1 Ty2)
< Is: case IsE.
Subgoal 3:
Variables: X R S G TyX G' Ty2 Ty1 Body X1
IH : forall X R E S G TyE TyX G',
is_e E -> is_string X -> is_e R -> subst X R E S -> typeOf G E TyE * -> typeOf [] R TyX ->
lookup G X TyX -> select (X, TyX) G' G -> typeOf G' S TyE
IsX : is_string X
IsR : is_e R
S : subst X R (tyabs X1 Ty1 Body) S
TyE : typeOf G (tyabs X1 Ty1 Body) (arrowTy Ty1 Ty2) @
TyR : typeOf [] R TyX
Lkp : lookup G X TyX
Slct : select (X, TyX) G' G
TyE1 : typeOf ((X1, Ty1)::G) Body Ty2 *
Is : is_string X1
Is1 : is_ty Ty1
Is2 : is_e Body
============================
typeOf G' S (arrowTy Ty1 Ty2)
< S: case S.
Subgoal 3.1:
Variables: R G TyX G' Ty2 Ty1 Body X1
IH : forall X R E S G TyE TyX G',
is_e E -> is_string X -> is_e R -> subst X R E S -> typeOf G E TyE * -> typeOf [] R TyX ->
lookup G X TyX -> select (X, TyX) G' G -> typeOf G' S TyE
IsX : is_string X1
IsR : is_e R
TyE : typeOf G (tyabs X1 Ty1 Body) (arrowTy Ty1 Ty2) @
TyR : typeOf [] R TyX
Lkp : lookup G X1 TyX
Slct : select (X1, TyX) G' G
TyE1 : typeOf ((X1, Ty1)::G) Body Ty2 *
Is : is_string X1
Is1 : is_ty Ty1
Is2 : is_e Body
============================
typeOf G' (abs X1 Body) (arrowTy Ty1 Ty2)
< L: assert forall Z ZTy,
lookup ((X1, Ty1)::G) Z ZTy -> lookup ((X1, Ty1)::G') Z ZTy.
Subgoal 3.1.1:
Variables: R G TyX G' Ty2 Ty1 Body X1
IH : forall X R E S G TyE TyX G',
is_e E -> is_string X -> is_e R -> subst X R E S -> typeOf G E TyE * -> typeOf [] R TyX ->
lookup G X TyX -> select (X, TyX) G' G -> typeOf G' S TyE
IsX : is_string X1
IsR : is_e R
TyE : typeOf G (tyabs X1 Ty1 Body) (arrowTy Ty1 Ty2) @
TyR : typeOf [] R TyX
Lkp : lookup G X1 TyX
Slct : select (X1, TyX) G' G
TyE1 : typeOf ((X1, Ty1)::G) Body Ty2 *
Is : is_string X1
Is1 : is_ty Ty1
Is2 : is_e Body
============================
forall Z ZTy, lookup ((X1, Ty1)::G) Z ZTy -> lookup ((X1, Ty1)::G') Z ZTy
< intros L.
Subgoal 3.1.1:
Variables: R G TyX G' Ty2 Ty1 Body X1 Z ZTy
IH : forall X R E S G TyE TyX G',
is_e E -> is_string X -> is_e R -> subst X R E S -> typeOf G E TyE * -> typeOf [] R TyX ->
lookup G X TyX -> select (X, TyX) G' G -> typeOf G' S TyE
IsX : is_string X1
IsR : is_e R
TyE : typeOf G (tyabs X1 Ty1 Body) (arrowTy Ty1 Ty2) @
TyR : typeOf [] R TyX
Lkp : lookup G X1 TyX
Slct : select (X1, TyX) G' G
TyE1 : typeOf ((X1, Ty1)::G) Body Ty2 *
Is : is_string X1
Is1 : is_ty Ty1
Is2 : is_e Body
L : lookup ((X1, Ty1)::G) Z ZTy
============================
lookup ((X1, Ty1)::G') Z ZTy
< L: case L.
Subgoal 3.1.1.1:
Variables: R G TyX G' Ty2 Body Z ZTy
IH : forall X R E S G TyE TyX G',
is_e E -> is_string X -> is_e R -> subst X R E S -> typeOf G E TyE * -> typeOf [] R TyX ->
lookup G X TyX -> select (X, TyX) G' G -> typeOf G' S TyE
IsX : is_string Z
IsR : is_e R
TyE : typeOf G (tyabs Z ZTy Body) (arrowTy ZTy Ty2) @
TyR : typeOf [] R TyX
Lkp : lookup G Z TyX
Slct : select (Z, TyX) G' G
TyE1 : typeOf ((Z, ZTy)::G) Body Ty2 *
Is : is_string Z
Is1 : is_ty ZTy
Is2 : is_e Body
============================
lookup ((Z, ZTy)::G') Z ZTy
< search.
Subgoal 3.1.1.2:
Variables: R G TyX G' Ty2 Ty1 Body X1 Z ZTy
IH : forall X R E S G TyE TyX G',
is_e E -> is_string X -> is_e R -> subst X R E S -> typeOf G E TyE * -> typeOf [] R TyX ->
lookup G X TyX -> select (X, TyX) G' G -> typeOf G' S TyE
IsX : is_string X1
IsR : is_e R
TyE : typeOf G (tyabs X1 Ty1 Body) (arrowTy Ty1 Ty2) @
TyR : typeOf [] R TyX
Lkp : lookup G X1 TyX
Slct : select (X1, TyX) G' G
TyE1 : typeOf ((X1, Ty1)::G) Body Ty2 *
Is : is_string X1
Is1 : is_ty Ty1
Is2 : is_e Body
L : X1 = Z -> false
L1 : lookup G Z ZTy
============================
lookup ((X1, Ty1)::G') Z ZTy
< NEq: assert Z = X1 -> false.
Subgoal 3.1.1.2.1:
Variables: R G TyX G' Ty2 Ty1 Body X1 Z ZTy
IH : forall X R E S G TyE TyX G',
is_e E -> is_string X -> is_e R -> subst X R E S -> typeOf G E TyE * -> typeOf [] R TyX ->
lookup G X TyX -> select (X, TyX) G' G -> typeOf G' S TyE
IsX : is_string X1
IsR : is_e R
TyE : typeOf G (tyabs X1 Ty1 Body) (arrowTy Ty1 Ty2) @
TyR : typeOf [] R TyX
Lkp : lookup G X1 TyX
Slct : select (X1, TyX) G' G
TyE1 : typeOf ((X1, Ty1)::G) Body Ty2 *
Is : is_string X1
Is1 : is_ty Ty1
Is2 : is_e Body
L : X1 = Z -> false
L1 : lookup G Z ZTy
============================
Z = X1 -> false
< intros E.
Subgoal 3.1.1.2.1:
Variables: R G TyX G' Ty2 Ty1 Body X1 Z ZTy
IH : forall X R E S G TyE TyX G',
is_e E -> is_string X -> is_e R -> subst X R E S -> typeOf G E TyE * -> typeOf [] R TyX ->
lookup G X TyX -> select (X, TyX) G' G -> typeOf G' S TyE
IsX : is_string X1
IsR : is_e R
TyE : typeOf G (tyabs X1 Ty1 Body) (arrowTy Ty1 Ty2) @
TyR : typeOf [] R TyX
Lkp : lookup G X1 TyX
Slct : select (X1, TyX) G' G
TyE1 : typeOf ((X1, Ty1)::G) Body Ty2 *
Is : is_string X1
Is1 : is_ty Ty1
Is2 : is_e Body
L : X1 = Z -> false
L1 : lookup G Z ZTy
E : Z = X1
============================
false
< case E.
Subgoal 3.1.1.2.1:
Variables: R G TyX G' Ty2 Ty1 Body X1 ZTy
IH : forall X R E S G TyE TyX G',
is_e E -> is_string X -> is_e R -> subst X R E S -> typeOf G E TyE * -> typeOf [] R TyX ->
lookup G X TyX -> select (X, TyX) G' G -> typeOf G' S TyE
IsX : is_string X1
IsR : is_e R
TyE : typeOf G (tyabs X1 Ty1 Body) (arrowTy Ty1 Ty2) @
TyR : typeOf [] R TyX
Lkp : lookup G X1 TyX
Slct : select (X1, TyX) G' G
TyE1 : typeOf ((X1, Ty1)::G) Body Ty2 *
Is : is_string X1
Is1 : is_ty Ty1
Is2 : is_e Body
L : X1 = X1 -> false
L1 : lookup G X1 ZTy
============================
false
< backchain L.
Subgoal 3.1.1.2:
Variables: R G TyX G' Ty2 Ty1 Body X1 Z ZTy
IH : forall X R E S G TyE TyX G',
is_e E -> is_string X -> is_e R -> subst X R E S -> typeOf G E TyE * -> typeOf [] R TyX ->
lookup G X TyX -> select (X, TyX) G' G -> typeOf G' S TyE
IsX : is_string X1
IsR : is_e R
TyE : typeOf G (tyabs X1 Ty1 Body) (arrowTy Ty1 Ty2) @
TyR : typeOf [] R TyX
Lkp : lookup G X1 TyX
Slct : select (X1, TyX) G' G
TyE1 : typeOf ((X1, Ty1)::G) Body Ty2 *
Is : is_string X1
Is1 : is_ty Ty1
Is2 : is_e Body
L : X1 = Z -> false
L1 : lookup G Z ZTy
NEq : Z = X1 -> false
============================
lookup ((X1, Ty1)::G') Z ZTy
< apply select_lookup to L1 Slct NEq.
Subgoal 3.1.1.2:
Variables: R G TyX G' Ty2 Ty1 Body X1 Z ZTy
IH : forall X R E S G TyE TyX G',
is_e E -> is_string X -> is_e R -> subst X R E S -> typeOf G E TyE * -> typeOf [] R TyX ->
lookup G X TyX -> select (X, TyX) G' G -> typeOf G' S TyE
IsX : is_string X1
IsR : is_e R
TyE : typeOf G (tyabs X1 Ty1 Body) (arrowTy Ty1 Ty2) @
TyR : typeOf [] R TyX
Lkp : lookup G X1 TyX
Slct : select (X1, TyX) G' G
TyE1 : typeOf ((X1, Ty1)::G) Body Ty2 *
Is : is_string X1
Is1 : is_ty Ty1
Is2 : is_e Body
L : X1 = Z -> false
L1 : lookup G Z ZTy
NEq : Z = X1 -> false
H1 : lookup G' Z ZTy
============================
lookup ((X1, Ty1)::G') Z ZTy
< search.
Subgoal 3.1:
Variables: R G TyX G' Ty2 Ty1 Body X1
IH : forall X R E S G TyE TyX G',
is_e E -> is_string X -> is_e R -> subst X R E S -> typeOf G E TyE * -> typeOf [] R TyX ->
lookup G X TyX -> select (X, TyX) G' G -> typeOf G' S TyE
IsX : is_string X1
IsR : is_e R
TyE : typeOf G (tyabs X1 Ty1 Body) (arrowTy Ty1 Ty2) @
TyR : typeOf [] R TyX
Lkp : lookup G X1 TyX
Slct : select (X1, TyX) G' G
TyE1 : typeOf ((X1, Ty1)::G) Body Ty2 *
Is : is_string X1
Is1 : is_ty Ty1
Is2 : is_e Body
L : forall Z ZTy, lookup ((X1, Ty1)::G) Z ZTy -> lookup ((X1, Ty1)::G') Z ZTy
============================
typeOf G' (abs X1 Body) (arrowTy Ty1 Ty2)
< apply type_weakening to _ TyE1 L.
Subgoal 3.1:
Variables: R G TyX G' Ty2 Ty1 Body X1
IH : forall X R E S G TyE TyX G',
is_e E -> is_string X -> is_e R -> subst X R E S -> typeOf G E TyE * -> typeOf [] R TyX ->
lookup G X TyX -> select (X, TyX) G' G -> typeOf G' S TyE
IsX : is_string X1
IsR : is_e R
TyE : typeOf G (tyabs X1 Ty1 Body) (arrowTy Ty1 Ty2) @
TyR : typeOf [] R TyX
Lkp : lookup G X1 TyX
Slct : select (X1, TyX) G' G
TyE1 : typeOf ((X1, Ty1)::G) Body Ty2 *
Is : is_string X1
Is1 : is_ty Ty1
Is2 : is_e Body
L : forall Z ZTy, lookup ((X1, Ty1)::G) Z ZTy -> lookup ((X1, Ty1)::G') Z ZTy
H1 : typeOf ((X1, Ty1)::G') Body Ty2
============================
typeOf G' (abs X1 Body) (arrowTy Ty1 Ty2)
< search.
Subgoal 3.2:
Variables: X R G TyX G' Ty2 Ty1 Body X1 B
IH : forall X R E S G TyE TyX G',
is_e E -> is_string X -> is_e R -> subst X R E S -> typeOf G E TyE * -> typeOf [] R TyX ->
lookup G X TyX -> select (X, TyX) G' G -> typeOf G' S TyE
IsX : is_string X
IsR : is_e R
TyE : typeOf G (tyabs X1 Ty1 Body) (arrowTy Ty1 Ty2) @
TyR : typeOf [] R TyX
Lkp : lookup G X TyX
Slct : select (X, TyX) G' G
TyE1 : typeOf ((X1, Ty1)::G) Body Ty2 *
Is : is_string X1
Is1 : is_ty Ty1
Is2 : is_e Body
S : X = X1 -> false
S1 : subst X R Body B
============================
typeOf G' (abs X1 B) (arrowTy Ty1 Ty2)
< assert X1 = X -> false.
Subgoal 3.2.1:
Variables: X R G TyX G' Ty2 Ty1 Body X1 B
IH : forall X R E S G TyE TyX G',
is_e E -> is_string X -> is_e R -> subst X R E S -> typeOf G E TyE * -> typeOf [] R TyX ->
lookup G X TyX -> select (X, TyX) G' G -> typeOf G' S TyE
IsX : is_string X
IsR : is_e R
TyE : typeOf G (tyabs X1 Ty1 Body) (arrowTy Ty1 Ty2) @
TyR : typeOf [] R TyX
Lkp : lookup G X TyX
Slct : select (X, TyX) G' G
TyE1 : typeOf ((X1, Ty1)::G) Body Ty2 *
Is : is_string X1
Is1 : is_ty Ty1
Is2 : is_e Body
S : X = X1 -> false
S1 : subst X R Body B
============================
X1 = X -> false
< intros E.
Subgoal 3.2.1:
Variables: X R G TyX G' Ty2 Ty1 Body X1 B
IH : forall X R E S G TyE TyX G',
is_e E -> is_string X -> is_e R -> subst X R E S -> typeOf G E TyE * -> typeOf [] R TyX ->
lookup G X TyX -> select (X, TyX) G' G -> typeOf G' S TyE
IsX : is_string X
IsR : is_e R
TyE : typeOf G (tyabs X1 Ty1 Body) (arrowTy Ty1 Ty2) @
TyR : typeOf [] R TyX
Lkp : lookup G X TyX
Slct : select (X, TyX) G' G
TyE1 : typeOf ((X1, Ty1)::G) Body Ty2 *
Is : is_string X1
Is1 : is_ty Ty1
Is2 : is_e Body
S : X = X1 -> false
S1 : subst X R Body B
E : X1 = X
============================
false
< case E.
Subgoal 3.2.1:
Variables: X R G TyX G' Ty2 Ty1 Body B
IH : forall X R E S G TyE TyX G',
is_e E -> is_string X -> is_e R -> subst X R E S -> typeOf G E TyE * -> typeOf [] R TyX ->
lookup G X TyX -> select (X, TyX) G' G -> typeOf G' S TyE
IsX : is_string X
IsR : is_e R
TyE : typeOf G (tyabs X Ty1 Body) (arrowTy Ty1 Ty2) @
TyR : typeOf [] R TyX
Lkp : lookup G X TyX
Slct : select (X, TyX) G' G
TyE1 : typeOf ((X, Ty1)::G) Body Ty2 *
Is : is_string X
Is1 : is_ty Ty1
Is2 : is_e Body
S : X = X -> false
S1 : subst X R Body B
============================
false
< backchain S.
Subgoal 3.2:
Variables: X R G TyX G' Ty2 Ty1 Body X1 B
IH : forall X R E S G TyE TyX G',
is_e E -> is_string X -> is_e R -> subst X R E S -> typeOf G E TyE * -> typeOf [] R TyX ->
lookup G X TyX -> select (X, TyX) G' G -> typeOf G' S TyE
IsX : is_string X
IsR : is_e R
TyE : typeOf G (tyabs X1 Ty1 Body) (arrowTy Ty1 Ty2) @
TyR : typeOf [] R TyX
Lkp : lookup G X TyX
Slct : select (X, TyX) G' G
TyE1 : typeOf ((X1, Ty1)::G) Body Ty2 *
Is : is_string X1
Is1 : is_ty Ty1
Is2 : is_e Body
S : X = X1 -> false
S1 : subst X R Body B
H1 : X1 = X -> false
============================
typeOf G' (abs X1 B) (arrowTy Ty1 Ty2)
< apply IH to _ _ _ S1 TyE1 _ _ _ with
G' = (X1, Ty1)::G'.
Subgoal 3.2:
Variables: X R G TyX G' Ty2 Ty1 Body X1 B
IH : forall X R E S G TyE TyX G',
is_e E -> is_string X -> is_e R -> subst X R E S -> typeOf G E TyE * -> typeOf [] R TyX ->
lookup G X TyX -> select (X, TyX) G' G -> typeOf G' S TyE
IsX : is_string X
IsR : is_e R
TyE : typeOf G (tyabs X1 Ty1 Body) (arrowTy Ty1 Ty2) @
TyR : typeOf [] R TyX
Lkp : lookup G X TyX
Slct : select (X, TyX) G' G
TyE1 : typeOf ((X1, Ty1)::G) Body Ty2 *
Is : is_string X1
Is1 : is_ty Ty1
Is2 : is_e Body
S : X = X1 -> false
S1 : subst X R Body B
H1 : X1 = X -> false
H2 : typeOf ((X1, Ty1)::G') B Ty2
============================
typeOf G' (abs X1 B) (arrowTy Ty1 Ty2)
< search.
Subgoal 4:
Variables: X R S G TyE TyX G' Ty1 E2 E1
IH : forall X R E S G TyE TyX G',
is_e E -> is_string X -> is_e R -> subst X R E S -> typeOf G E TyE * -> typeOf [] R TyX ->
lookup G X TyX -> select (X, TyX) G' G -> typeOf G' S TyE
IsE : is_e (app E1 E2)
IsX : is_string X
IsR : is_e R
S : subst X R (app E1 E2) S
TyE : typeOf G (app E1 E2) TyE @
TyR : typeOf [] R TyX
Lkp : lookup G X TyX
Slct : select (X, TyX) G' G
TyE1 : typeOf G E1 (arrowTy Ty1 TyE) *
TyE2 : typeOf G E2 Ty1 *
============================
typeOf G' S TyE
< Is: case IsE.
Subgoal 4:
Variables: X R S G TyE TyX G' Ty1 E2 E1
IH : forall X R E S G TyE TyX G',
is_e E -> is_string X -> is_e R -> subst X R E S -> typeOf G E TyE * -> typeOf [] R TyX ->
lookup G X TyX -> select (X, TyX) G' G -> typeOf G' S TyE
IsX : is_string X
IsR : is_e R
S : subst X R (app E1 E2) S
TyE : typeOf G (app E1 E2) TyE @
TyR : typeOf [] R TyX
Lkp : lookup G X TyX
Slct : select (X, TyX) G' G
TyE1 : typeOf G E1 (arrowTy Ty1 TyE) *
TyE2 : typeOf G E2 Ty1 *
Is : is_e E1
Is1 : is_e E2
============================
typeOf G' S TyE
< S: case S.
Subgoal 4:
Variables: X R G TyE TyX G' Ty1 E2 E1 S2 S1
IH : forall X R E S G TyE TyX G',
is_e E -> is_string X -> is_e R -> subst X R E S -> typeOf G E TyE * -> typeOf [] R TyX ->
lookup G X TyX -> select (X, TyX) G' G -> typeOf G' S TyE
IsX : is_string X
IsR : is_e R
TyE : typeOf G (app E1 E2) TyE @
TyR : typeOf [] R TyX
Lkp : lookup G X TyX
Slct : select (X, TyX) G' G
TyE1 : typeOf G E1 (arrowTy Ty1 TyE) *
TyE2 : typeOf G E2 Ty1 *
Is : is_e E1
Is1 : is_e E2
S : subst X R E1 S1
S1 : subst X R E2 S2
============================
typeOf G' (app S1 S2) TyE
< apply IH to _ _ _ S TyE1 _ _ _.
Subgoal 4:
Variables: X R G TyE TyX G' Ty1 E2 E1 S2 S1
IH : forall X R E S G TyE TyX G',
is_e E -> is_string X -> is_e R -> subst X R E S -> typeOf G E TyE * -> typeOf [] R TyX ->
lookup G X TyX -> select (X, TyX) G' G -> typeOf G' S TyE
IsX : is_string X
IsR : is_e R
TyE : typeOf G (app E1 E2) TyE @
TyR : typeOf [] R TyX
Lkp : lookup G X TyX
Slct : select (X, TyX) G' G
TyE1 : typeOf G E1 (arrowTy Ty1 TyE) *
TyE2 : typeOf G E2 Ty1 *
Is : is_e E1
Is1 : is_e E2
S : subst X R E1 S1
S1 : subst X R E2 S2
H1 : typeOf G' S1 (arrowTy Ty1 TyE)
============================
typeOf G' (app S1 S2) TyE
< apply IH to _ _ _ S1 TyE2 _ _ _.
Subgoal 4:
Variables: X R G TyE TyX G' Ty1 E2 E1 S2 S1
IH : forall X R E S G TyE TyX G',
is_e E -> is_string X -> is_e R -> subst X R E S -> typeOf G E TyE * -> typeOf [] R TyX ->
lookup G X TyX -> select (X, TyX) G' G -> typeOf G' S TyE
IsX : is_string X
IsR : is_e R
TyE : typeOf G (app E1 E2) TyE @
TyR : typeOf [] R TyX
Lkp : lookup G X TyX
Slct : select (X, TyX) G' G
TyE1 : typeOf G E1 (arrowTy Ty1 TyE) *
TyE2 : typeOf G E2 Ty1 *
Is : is_e E1
Is1 : is_e E2
S : subst X R E1 S1
S1 : subst X R E2 S2
H1 : typeOf G' S1 (arrowTy Ty1 TyE)
H2 : typeOf G' S2 Ty1
============================
typeOf G' (app S1 S2) TyE
< search.
Subgoal 5:
Variables: X R S G TyX G' I
IH : forall X R E S G TyE TyX G',
is_e E -> is_string X -> is_e R -> subst X R E S -> typeOf G E TyE * -> typeOf [] R TyX ->
lookup G X TyX -> select (X, TyX) G' G -> typeOf G' S TyE
IsE : is_e (intE I)
IsX : is_string X
IsR : is_e R
S : subst X R (intE I) S
TyE : typeOf G (intE I) intTy @
TyR : typeOf [] R TyX
Lkp : lookup G X TyX
Slct : select (X, TyX) G' G
============================
typeOf G' S intTy
< case S.
Subgoal 5:
Variables: X R G TyX G' I
IH : forall X R E S G TyE TyX G',
is_e E -> is_string X -> is_e R -> subst X R E S -> typeOf G E TyE * -> typeOf [] R TyX ->
lookup G X TyX -> select (X, TyX) G' G -> typeOf G' S TyE
IsE : is_e (intE I)
IsX : is_string X
IsR : is_e R
TyE : typeOf G (intE I) intTy @
TyR : typeOf [] R TyX
Lkp : lookup G X TyX
Slct : select (X, TyX) G' G
============================
typeOf G' (intE I) intTy
< search.
Subgoal 6:
Variables: X R S G TyX G' E2 E1
IH : forall X R E S G TyE TyX G',
is_e E -> is_string X -> is_e R -> subst X R E S -> typeOf G E TyE * -> typeOf [] R TyX ->
lookup G X TyX -> select (X, TyX) G' G -> typeOf G' S TyE
IsE : is_e (plus E1 E2)
IsX : is_string X
IsR : is_e R
S : subst X R (plus E1 E2) S
TyE : typeOf G (plus E1 E2) intTy @
TyR : typeOf [] R TyX
Lkp : lookup G X TyX
Slct : select (X, TyX) G' G
TyE1 : typeOf G E1 intTy *
TyE2 : typeOf G E2 intTy *
============================
typeOf G' S intTy
< case IsE.
Subgoal 6:
Variables: X R S G TyX G' E2 E1
IH : forall X R E S G TyE TyX G',
is_e E -> is_string X -> is_e R -> subst X R E S -> typeOf G E TyE * -> typeOf [] R TyX ->
lookup G X TyX -> select (X, TyX) G' G -> typeOf G' S TyE
IsX : is_string X
IsR : is_e R
S : subst X R (plus E1 E2) S
TyE : typeOf G (plus E1 E2) intTy @
TyR : typeOf [] R TyX
Lkp : lookup G X TyX
Slct : select (X, TyX) G' G
TyE1 : typeOf G E1 intTy *
TyE2 : typeOf G E2 intTy *
H1 : is_e E1
H2 : is_e E2
============================
typeOf G' S intTy
< S: case S.
Subgoal 6:
Variables: X R G TyX G' E2 E1 S2 S1
IH : forall X R E S G TyE TyX G',
is_e E -> is_string X -> is_e R -> subst X R E S -> typeOf G E TyE * -> typeOf [] R TyX ->
lookup G X TyX -> select (X, TyX) G' G -> typeOf G' S TyE
IsX : is_string X
IsR : is_e R
TyE : typeOf G (plus E1 E2) intTy @
TyR : typeOf [] R TyX
Lkp : lookup G X TyX
Slct : select (X, TyX) G' G
TyE1 : typeOf G E1 intTy *
TyE2 : typeOf G E2 intTy *
H1 : is_e E1
H2 : is_e E2
S : subst X R E1 S1
S1 : subst X R E2 S2
============================
typeOf G' (plus S1 S2) intTy
< apply IH to _ _ _ S TyE1 _ _ _.
Subgoal 6:
Variables: X R G TyX G' E2 E1 S2 S1
IH : forall X R E S G TyE TyX G',
is_e E -> is_string X -> is_e R -> subst X R E S -> typeOf G E TyE * -> typeOf [] R TyX ->
lookup G X TyX -> select (X, TyX) G' G -> typeOf G' S TyE
IsX : is_string X
IsR : is_e R
TyE : typeOf G (plus E1 E2) intTy @
TyR : typeOf [] R TyX
Lkp : lookup G X TyX
Slct : select (X, TyX) G' G
TyE1 : typeOf G E1 intTy *
TyE2 : typeOf G E2 intTy *
H1 : is_e E1
H2 : is_e E2
S : subst X R E1 S1
S1 : subst X R E2 S2
H3 : typeOf G' S1 intTy
============================
typeOf G' (plus S1 S2) intTy
< apply IH to _ _ _ S1 TyE2 _ _ _.
Subgoal 6:
Variables: X R G TyX G' E2 E1 S2 S1
IH : forall X R E S G TyE TyX G',
is_e E -> is_string X -> is_e R -> subst X R E S -> typeOf G E TyE * -> typeOf [] R TyX ->
lookup G X TyX -> select (X, TyX) G' G -> typeOf G' S TyE
IsX : is_string X
IsR : is_e R
TyE : typeOf G (plus E1 E2) intTy @
TyR : typeOf [] R TyX
Lkp : lookup G X TyX
Slct : select (X, TyX) G' G
TyE1 : typeOf G E1 intTy *
TyE2 : typeOf G E2 intTy *
H1 : is_e E1
H2 : is_e E2
S : subst X R E1 S1
S1 : subst X R E2 S2
H3 : typeOf G' S1 intTy
H4 : typeOf G' S2 intTy
============================
typeOf G' (plus S1 S2) intTy
< search.
Subgoal 7:
Variables: X R S G TyE TyX G' E_T
IH : forall X R E S G TyE TyX G',
is_e E -> is_string X -> is_e R -> subst X R E S -> typeOf G E TyE * -> typeOf [] R TyX ->
lookup G X TyX -> select (X, TyX) G' G -> typeOf G' S TyE
IsE : is_e <unknown I e>
IsX : is_string X
IsR : is_e R
S : subst X R <unknown I e> S
TyE : typeOf G <unknown I e> TyE @
TyR : typeOf [] R TyX
Lkp : lookup G X TyX
Slct : select (X, TyX) G' G
TyE1 : |{e}- <unknown I e> ~~> E_T
TyE2 : typeOf G E_T TyE *
============================
typeOf G' S TyE
< ST: apply proj_subst to TyE1 _ _ _ S.
Subgoal 7:
Variables: X R S G TyE TyX G' E_T S'
IH : forall X R E S G TyE TyX G',
is_e E -> is_string X -> is_e R -> subst X R E S -> typeOf G E TyE * -> typeOf [] R TyX ->
lookup G X TyX -> select (X, TyX) G' G -> typeOf G' S TyE
IsE : is_e <unknown I e>
IsX : is_string X
IsR : is_e R
S : subst X R <unknown I e> S
TyE : typeOf G <unknown I e> TyE @
TyR : typeOf [] R TyX
Lkp : lookup G X TyX
Slct : select (X, TyX) G' G
TyE1 : |{e}- <unknown I e> ~~> E_T
TyE2 : typeOf G E_T TyE *
ST : subst X R E_T S'
============================
typeOf G' S TyE
< apply proj_is to TyE1 _.
Subgoal 7:
Variables: X R S G TyE TyX G' E_T S'
IH : forall X R E S G TyE TyX G',
is_e E -> is_string X -> is_e R -> subst X R E S -> typeOf G E TyE * -> typeOf [] R TyX ->
lookup G X TyX -> select (X, TyX) G' G -> typeOf G' S TyE
IsE : is_e <unknown I e>
IsX : is_string X
IsR : is_e R
S : subst X R <unknown I e> S
TyE : typeOf G <unknown I e> TyE @
TyR : typeOf [] R TyX
Lkp : lookup G X TyX
Slct : select (X, TyX) G' G
TyE1 : |{e}- <unknown I e> ~~> E_T
TyE2 : typeOf G E_T TyE *
ST : subst X R E_T S'
H1 : is_e E_T
============================
typeOf G' S TyE
< apply proj_subst_same to TyE1 _ _ _ S ST.
Subgoal 7:
Variables: X R G TyE TyX G' E_T S'
IH : forall X R E S G TyE TyX G',
is_e E -> is_string X -> is_e R -> subst X R E S -> typeOf G E TyE * -> typeOf [] R TyX ->
lookup G X TyX -> select (X, TyX) G' G -> typeOf G' S TyE
IsE : is_e <unknown I e>
IsX : is_string X
IsR : is_e R
S : subst X R <unknown I e> S'
TyE : typeOf G <unknown I e> TyE @
TyR : typeOf [] R TyX
Lkp : lookup G X TyX
Slct : select (X, TyX) G' G
TyE1 : |{e}- <unknown I e> ~~> E_T
TyE2 : typeOf G E_T TyE *
ST : subst X R E_T S'
H1 : is_e E_T
============================
typeOf G' S' TyE
< apply IH to _ _ _ ST TyE2 _ _ _.
Subgoal 7:
Variables: X R G TyE TyX G' E_T S'
IH : forall X R E S G TyE TyX G',
is_e E -> is_string X -> is_e R -> subst X R E S -> typeOf G E TyE * -> typeOf [] R TyX ->
lookup G X TyX -> select (X, TyX) G' G -> typeOf G' S TyE
IsE : is_e <unknown I e>
IsX : is_string X
IsR : is_e R
S : subst X R <unknown I e> S'
TyE : typeOf G <unknown I e> TyE @
TyR : typeOf [] R TyX
Lkp : lookup G X TyX
Slct : select (X, TyX) G' G
TyE1 : |{e}- <unknown I e> ~~> E_T
TyE2 : typeOf G E_T TyE *
ST : subst X R E_T S'
H1 : is_e E_T
H2 : typeOf G' S' TyE
============================
typeOf G' S' TyE
< search.
Proof completed.
< Extensible_Theorem
type_preservation : forall E Ty V,
IsE : is_e E ->
Ty : typeOf [] E Ty ->
Ev : eval E V ->
typeOf [] V Ty
on Ev.
Subgoal 1:
Variables: Ty Body X
IH : forall E Ty V, is_e E -> typeOf [] E Ty -> eval E V * -> typeOf [] V Ty
IsE : is_e (abs X Body)
Ty : typeOf [] (abs X Body) Ty
Ev : eval (abs X Body) (abs X Body) @
============================
typeOf [] (abs X Body) Ty
< search.
Subgoal 2:
Variables: Ty V X Body V2 B E2 E1
IH : forall E Ty V, is_e E -> typeOf [] E Ty -> eval E V * -> typeOf [] V Ty
IsE : is_e (app E1 E2)
Ty : typeOf [] (app E1 E2) Ty
Ev : eval (app E1 E2) V @
Ev1 : eval E1 (abs X Body) *
Ev2 : eval E2 V2 *
Ev3 : subst X V2 Body B
Ev4 : eval B V *
============================
typeOf [] V Ty
< Is: case IsE.
Subgoal 2:
Variables: Ty V X Body V2 B E2 E1
IH : forall E Ty V, is_e E -> typeOf [] E Ty -> eval E V * -> typeOf [] V Ty
Ty : typeOf [] (app E1 E2) Ty
Ev : eval (app E1 E2) V @
Ev1 : eval E1 (abs X Body) *
Ev2 : eval E2 V2 *
Ev3 : subst X V2 Body B
Ev4 : eval B V *
Is : is_e E1
Is1 : is_e E2
============================
typeOf [] V Ty
< Ty: case Ty.
Subgoal 2:
Variables: Ty V X Body V2 B E2 E1 Ty1
IH : forall E Ty V, is_e E -> typeOf [] E Ty -> eval E V * -> typeOf [] V Ty
Ev : eval (app E1 E2) V @
Ev1 : eval E1 (abs X Body) *
Ev2 : eval E2 V2 *
Ev3 : subst X V2 Body B
Ev4 : eval B V *
Is : is_e E1
Is1 : is_e E2
Ty : typeOf [] E1 (arrowTy Ty1 Ty)
Ty1 : typeOf [] E2 Ty1
============================
typeOf [] V Ty
< AbsTy: apply IH to _ Ty Ev1.
Subgoal 2:
Variables: Ty V X Body V2 B E2 E1 Ty1
IH : forall E Ty V, is_e E -> typeOf [] E Ty -> eval E V * -> typeOf [] V Ty
Ev : eval (app E1 E2) V @
Ev1 : eval E1 (abs X Body) *
Ev2 : eval E2 V2 *
Ev3 : subst X V2 Body B
Ev4 : eval B V *
Is : is_e E1
Is1 : is_e E2
Ty : typeOf [] E1 (arrowTy Ty1 Ty)
Ty1 : typeOf [] E2 Ty1
AbsTy : typeOf [] (abs X Body) (arrowTy Ty1 Ty)
============================
typeOf [] V Ty
< Ty': case AbsTy.
Subgoal 2:
Variables: Ty V X Body V2 B E2 E1 Ty1
IH : forall E Ty V, is_e E -> typeOf [] E Ty -> eval E V * -> typeOf [] V Ty
Ev : eval (app E1 E2) V @
Ev1 : eval E1 (abs X Body) *
Ev2 : eval E2 V2 *
Ev3 : subst X V2 Body B
Ev4 : eval B V *
Is : is_e E1
Is1 : is_e E2
Ty : typeOf [] E1 (arrowTy Ty1 Ty)
Ty1 : typeOf [] E2 Ty1
Ty' : typeOf [(X, Ty1)] Body Ty
============================
typeOf [] V Ty
< apply IH to _ Ty1 Ev2.
Subgoal 2:
Variables: Ty V X Body V2 B E2 E1 Ty1
IH : forall E Ty V, is_e E -> typeOf [] E Ty -> eval E V * -> typeOf [] V Ty
Ev : eval (app E1 E2) V @
Ev1 : eval E1 (abs X Body) *
Ev2 : eval E2 V2 *
Ev3 : subst X V2 Body B
Ev4 : eval B V *
Is : is_e E1
Is1 : is_e E2
Ty : typeOf [] E1 (arrowTy Ty1 Ty)
Ty1 : typeOf [] E2 Ty1
Ty' : typeOf [(X, Ty1)] Body Ty
H1 : typeOf [] V2 Ty1
============================
typeOf [] V Ty
< apply eval_is to _ Ev2.
Subgoal 2:
Variables: Ty V X Body V2 B E2 E1 Ty1
IH : forall E Ty V, is_e E -> typeOf [] E Ty -> eval E V * -> typeOf [] V Ty
Ev : eval (app E1 E2) V @
Ev1 : eval E1 (abs X Body) *
Ev2 : eval E2 V2 *
Ev3 : subst X V2 Body B
Ev4 : eval B V *
Is : is_e E1
Is1 : is_e E2
Ty : typeOf [] E1 (arrowTy Ty1 Ty)
Ty1 : typeOf [] E2 Ty1
Ty' : typeOf [(X, Ty1)] Body Ty
H1 : typeOf [] V2 Ty1
H2 : is_e V2
============================
typeOf [] V Ty
< IsAbs: apply eval_is to _ Ev1.
Subgoal 2:
Variables: Ty V X Body V2 B E2 E1 Ty1
IH : forall E Ty V, is_e E -> typeOf [] E Ty -> eval E V * -> typeOf [] V Ty
Ev : eval (app E1 E2) V @
Ev1 : eval E1 (abs X Body) *
Ev2 : eval E2 V2 *
Ev3 : subst X V2 Body B
Ev4 : eval B V *
Is : is_e E1
Is1 : is_e E2
Ty : typeOf [] E1 (arrowTy Ty1 Ty)
Ty1 : typeOf [] E2 Ty1
Ty' : typeOf [(X, Ty1)] Body Ty
H1 : typeOf [] V2 Ty1
H2 : is_e V2
IsAbs : is_e (abs X Body)
============================
typeOf [] V Ty
< case IsAbs.
Subgoal 2:
Variables: Ty V X Body V2 B E2 E1 Ty1
IH : forall E Ty V, is_e E -> typeOf [] E Ty -> eval E V * -> typeOf [] V Ty
Ev : eval (app E1 E2) V @
Ev1 : eval E1 (abs X Body) *
Ev2 : eval E2 V2 *
Ev3 : subst X V2 Body B
Ev4 : eval B V *
Is : is_e E1
Is1 : is_e E2
Ty : typeOf [] E1 (arrowTy Ty1 Ty)
Ty1 : typeOf [] E2 Ty1
Ty' : typeOf [(X, Ty1)] Body Ty
H1 : typeOf [] V2 Ty1
H2 : is_e V2
H3 : is_string X
H4 : is_e Body
============================
typeOf [] V Ty
< TyB: apply subst_type_preservation to _ _ _ Ev3 Ty' _ _ _.
Subgoal 2:
Variables: Ty V X Body V2 B E2 E1 Ty1
IH : forall E Ty V, is_e E -> typeOf [] E Ty -> eval E V * -> typeOf [] V Ty
Ev : eval (app E1 E2) V @
Ev1 : eval E1 (abs X Body) *
Ev2 : eval E2 V2 *
Ev3 : subst X V2 Body B
Ev4 : eval B V *
Is : is_e E1
Is1 : is_e E2
Ty : typeOf [] E1 (arrowTy Ty1 Ty)
Ty1 : typeOf [] E2 Ty1
Ty' : typeOf [(X, Ty1)] Body Ty
H1 : typeOf [] V2 Ty1
H2 : is_e V2
H3 : is_string X
H4 : is_e Body
TyB : typeOf [] B Ty
============================
typeOf [] V Ty
< apply subst_is to _ _ _ Ev3.
Subgoal 2:
Variables: Ty V X Body V2 B E2 E1 Ty1
IH : forall E Ty V, is_e E -> typeOf [] E Ty -> eval E V * -> typeOf [] V Ty
Ev : eval (app E1 E2) V @
Ev1 : eval E1 (abs X Body) *
Ev2 : eval E2 V2 *
Ev3 : subst X V2 Body B
Ev4 : eval B V *
Is : is_e E1
Is1 : is_e E2
Ty : typeOf [] E1 (arrowTy Ty1 Ty)
Ty1 : typeOf [] E2 Ty1
Ty' : typeOf [(X, Ty1)] Body Ty
H1 : typeOf [] V2 Ty1
H2 : is_e V2
H3 : is_string X
H4 : is_e Body
TyB : typeOf [] B Ty
H5 : is_e B
============================
typeOf [] V Ty
< apply IH to _ TyB Ev4.
Subgoal 2:
Variables: Ty V X Body V2 B E2 E1 Ty1
IH : forall E Ty V, is_e E -> typeOf [] E Ty -> eval E V * -> typeOf [] V Ty
Ev : eval (app E1 E2) V @
Ev1 : eval E1 (abs X Body) *
Ev2 : eval E2 V2 *
Ev3 : subst X V2 Body B
Ev4 : eval B V *
Is : is_e E1
Is1 : is_e E2
Ty : typeOf [] E1 (arrowTy Ty1 Ty)
Ty1 : typeOf [] E2 Ty1
Ty' : typeOf [(X, Ty1)] Body Ty
H1 : typeOf [] V2 Ty1
H2 : is_e V2
H3 : is_string X
H4 : is_e Body
TyB : typeOf [] B Ty
H5 : is_e B
H6 : typeOf [] V Ty
============================
typeOf [] V Ty
< search.
Subgoal 3:
Variables: Ty I
IH : forall E Ty V, is_e E -> typeOf [] E Ty -> eval E V * -> typeOf [] V Ty
IsE : is_e (intE I)
Ty : typeOf [] (intE I) Ty
Ev : eval (intE I) (intE I) @
============================
typeOf [] (intE I) Ty
< case Ty.
Subgoal 3:
Variables: I
IH : forall E Ty V, is_e E -> typeOf [] E Ty -> eval E V * -> typeOf [] V Ty
IsE : is_e (intE I)
Ev : eval (intE I) (intE I) @
============================
typeOf [] (intE I) intTy
< search.
Subgoal 4:
Variables: Ty I1 I2 I E2 E1
IH : forall E Ty V, is_e E -> typeOf [] E Ty -> eval E V * -> typeOf [] V Ty
IsE : is_e (plus E1 E2)
Ty : typeOf [] (plus E1 E2) Ty
Ev : eval (plus E1 E2) (intE I) @
Ev1 : eval E1 (intE I1) *
Ev2 : eval E2 (intE I2) *
Ev3 : I1 + I2 = I
============================
typeOf [] (intE I) Ty
< case Ty.
Subgoal 4:
Variables: I1 I2 I E2 E1
IH : forall E Ty V, is_e E -> typeOf [] E Ty -> eval E V * -> typeOf [] V Ty
IsE : is_e (plus E1 E2)
Ev : eval (plus E1 E2) (intE I) @
Ev1 : eval E1 (intE I1) *
Ev2 : eval E2 (intE I2) *
Ev3 : I1 + I2 = I
H1 : typeOf [] E1 intTy
H2 : typeOf [] E2 intTy
============================
typeOf [] (intE I) intTy
< search.
Subgoal 5:
Variables: Ty Body X Ty1
IH : forall E Ty V, is_e E -> typeOf [] E Ty -> eval E V * -> typeOf [] V Ty
IsE : is_e (tyabs X Ty1 Body)
Ty : typeOf [] (tyabs X Ty1 Body) Ty
Ev : eval (tyabs X Ty1 Body) (abs X Body) @
============================
typeOf [] (abs X Body) Ty
< case Ty.
Subgoal 5:
Variables: Body X Ty1 Ty3
IH : forall E Ty V, is_e E -> typeOf [] E Ty -> eval E V * -> typeOf [] V Ty
IsE : is_e (tyabs X Ty1 Body)
Ev : eval (tyabs X Ty1 Body) (abs X Body) @
H1 : typeOf [(X, Ty1)] Body Ty3
============================
typeOf [] (abs X Body) (arrowTy Ty1 Ty3)
< search.
Subgoal 6:
Variables: Ty V E_T
IH : forall E Ty V, is_e E -> typeOf [] E Ty -> eval E V * -> typeOf [] V Ty
IsE : is_e <unknown K eval>
Ty : typeOf [] <unknown K eval> Ty
Ev : eval <unknown K eval> V @
Ev1 : |{e}- <unknown K eval> ~~> E_T
Ev2 : eval E_T V *
============================
typeOf [] V Ty
< Ty: case Ty.
Subgoal 6:
Variables: Ty V E_T E_T1
IH : forall E Ty V, is_e E -> typeOf [] E Ty -> eval E V * -> typeOf [] V Ty
IsE : is_e <unknown K eval>
Ev : eval <unknown K eval> V @
Ev1 : |{e}- <unknown K eval> ~~> E_T
Ev2 : eval E_T V *
Ty : |{e}- <unknown K eval> ~~> E_T1
Ty1 : typeOf [] E_T1 Ty
============================
typeOf [] V Ty
< apply proj_same to Ev1 Ty.
Subgoal 6:
Variables: Ty V E_T1
IH : forall E Ty V, is_e E -> typeOf [] E Ty -> eval E V * -> typeOf [] V Ty
IsE : is_e <unknown K eval>
Ev : eval <unknown K eval> V @
Ev1 : |{e}- <unknown K eval> ~~> E_T1
Ev2 : eval E_T1 V *
Ty : |{e}- <unknown K eval> ~~> E_T1
Ty1 : typeOf [] E_T1 Ty
============================
typeOf [] V Ty
< apply proj_is to Ty _.
Subgoal 6:
Variables: Ty V E_T1
IH : forall E Ty V, is_e E -> typeOf [] E Ty -> eval E V * -> typeOf [] V Ty
IsE : is_e <unknown K eval>
Ev : eval <unknown K eval> V @
Ev1 : |{e}- <unknown K eval> ~~> E_T1
Ev2 : eval E_T1 V *
Ty : |{e}- <unknown K eval> ~~> E_T1
Ty1 : typeOf [] E_T1 Ty
H1 : is_e E_T1
============================
typeOf [] V Ty
< apply IH to _ Ty1 Ev2.
Subgoal 6:
Variables: Ty V E_T1
IH : forall E Ty V, is_e E -> typeOf [] E Ty -> eval E V * -> typeOf [] V Ty
IsE : is_e <unknown K eval>
Ev : eval <unknown K eval> V @
Ev1 : |{e}- <unknown K eval> ~~> E_T1
Ev2 : eval E_T1 V *
Ty : |{e}- <unknown K eval> ~~> E_T1
Ty1 : typeOf [] E_T1 Ty
H1 : is_e E_T1
H2 : typeOf [] V Ty
============================
typeOf [] V Ty
< search.
Proof completed.
