< Module mtc:bool.
< Prove mtc:shared_declarations:type_preservation.
Subgoal 1:
Variables: TG Ty EG
IH : forall TG E Ty EG V,
typeOfCtx TG EG -> typeOf TG E Ty -> eval EG E V * -> valueType V Ty
Rel : typeOfCtx TG EG
Ty : typeOf TG trueE Ty
Ev : eval EG trueE trueVal @
============================
valueType trueVal Ty
< case Ty.
Subgoal 1:
Variables: TG EG
IH : forall TG E Ty EG V,
typeOfCtx TG EG -> typeOf TG E Ty -> eval EG E V * -> valueType V Ty
Rel : typeOfCtx TG EG
Ev : eval EG trueE trueVal @
============================
valueType trueVal boolTy
< search.
Subgoal 2:
Variables: TG Ty EG
IH : forall TG E Ty EG V,
typeOfCtx TG EG -> typeOf TG E Ty -> eval EG E V * -> valueType V Ty
Rel : typeOfCtx TG EG
Ty : typeOf TG falseE Ty
Ev : eval EG falseE falseVal @
============================
valueType falseVal Ty
< case Ty.
Subgoal 2:
Variables: TG EG
IH : forall TG E Ty EG V,
typeOfCtx TG EG -> typeOf TG E Ty -> eval EG E V * -> valueType V Ty
Rel : typeOfCtx TG EG
Ev : eval EG falseE falseVal @
============================
valueType falseVal boolTy
< search.
Subgoal 3:
Variables: TG Ty EG V F T C
IH : forall TG E Ty EG V,
typeOfCtx TG EG -> typeOf TG E Ty -> eval EG E V * -> valueType V Ty
Rel : typeOfCtx TG EG
Ty : typeOf TG (ifThenElse C T F) Ty
Ev : eval EG (ifThenElse C T F) V @
Ev1 : eval EG C trueVal *
Ev2 : eval EG T V *
============================
valueType V Ty
< Ty: case Ty.
Subgoal 3:
Variables: TG Ty EG V F T C
IH : forall TG E Ty EG V,
typeOfCtx TG EG -> typeOf TG E Ty -> eval EG E V * -> valueType V Ty
Rel : typeOfCtx TG EG
Ev : eval EG (ifThenElse C T F) V @
Ev1 : eval EG C trueVal *
Ev2 : eval EG T V *
Ty : typeOf TG C boolTy
Ty1 : typeOf TG T Ty
Ty2 : typeOf TG F Ty
============================
valueType V Ty
< apply IH to _ Ty1 Ev2.
Subgoal 3:
Variables: TG Ty EG V F T C
IH : forall TG E Ty EG V,
typeOfCtx TG EG -> typeOf TG E Ty -> eval EG E V * -> valueType V Ty
Rel : typeOfCtx TG EG
Ev : eval EG (ifThenElse C T F) V @
Ev1 : eval EG C trueVal *
Ev2 : eval EG T V *
Ty : typeOf TG C boolTy
Ty1 : typeOf TG T Ty
Ty2 : typeOf TG F Ty
H1 : valueType V Ty
============================
valueType V Ty
< search.
Subgoal 4:
Variables: TG Ty EG V F T C
IH : forall TG E Ty EG V,
typeOfCtx TG EG -> typeOf TG E Ty -> eval EG E V * -> valueType V Ty
Rel : typeOfCtx TG EG
Ty : typeOf TG (ifThenElse C T F) Ty
Ev : eval EG (ifThenElse C T F) V @
Ev1 : eval EG C falseVal *
Ev2 : eval EG F V *
============================
valueType V Ty
< Ty: case Ty.
Subgoal 4:
Variables: TG Ty EG V F T C
IH : forall TG E Ty EG V,
typeOfCtx TG EG -> typeOf TG E Ty -> eval EG E V * -> valueType V Ty
Rel : typeOfCtx TG EG
Ev : eval EG (ifThenElse C T F) V @
Ev1 : eval EG C falseVal *
Ev2 : eval EG F V *
Ty : typeOf TG C boolTy
Ty1 : typeOf TG T Ty
Ty2 : typeOf TG F Ty
============================
valueType V Ty
< apply IH to _ Ty2 Ev2.
Subgoal 4:
Variables: TG Ty EG V F T C
IH : forall TG E Ty EG V,
typeOfCtx TG EG -> typeOf TG E Ty -> eval EG E V * -> valueType V Ty
Rel : typeOfCtx TG EG
Ev : eval EG (ifThenElse C T F) V @
Ev1 : eval EG C falseVal *
Ev2 : eval EG F V *
Ty : typeOf TG C boolTy
Ty1 : typeOf TG T Ty
Ty2 : typeOf TG F Ty
H1 : valueType V Ty
============================
valueType V Ty
< search.
Proof completed.
< Prove mtc:shared_declarations:value_evalStep_false.
Subgoal 1:
Variables: E'
IH : forall E E', value E * -> evalStep E E' -> false
V : value trueE @
Ev : evalStep trueE E'
============================
false
< case Ev.
Subgoal 2:
Variables: E'
IH : forall E E', value E * -> evalStep E E' -> false
V : value falseE @
Ev : evalStep falseE E'
============================
false
< case Ev.
Proof completed.
< Prove mtc:shared_declarations:subst_unique.
Subgoal 1:
Variables: X R EB
IH : forall X R E EA EB, subst X R E EA * -> subst X R E EB -> EA = EB
SA : subst X R trueE trueE @
SB : subst X R trueE EB
============================
trueE = EB
< case SB.
Subgoal 1:
Variables: X R
IH : forall X R E EA EB, subst X R E EA * -> subst X R E EB -> EA = EB
SA : subst X R trueE trueE @
============================
trueE = trueE
< search.
Subgoal 2:
Variables: X R EB
IH : forall X R E EA EB, subst X R E EA * -> subst X R E EB -> EA = EB
SA : subst X R falseE falseE @
SB : subst X R falseE EB
============================
falseE = EB
< case SB.
Subgoal 2:
Variables: X R
IH : forall X R E EA EB, subst X R E EA * -> subst X R E EB -> EA = EB
SA : subst X R falseE falseE @
============================
falseE = falseE
< search.
Subgoal 3:
Variables: X R EB F1 T1 C1 F T C
IH : forall X R E EA EB, subst X R E EA * -> subst X R E EB -> EA = EB
SA : subst X R (ifThenElse C T F) (ifThenElse C1 T1 F1) @
SB : subst X R (ifThenElse C T F) EB
SA1 : subst X R C C1 *
SA2 : subst X R T T1 *
SA3 : subst X R F F1 *
============================
ifThenElse C1 T1 F1 = EB
< SB: case SB.
Subgoal 3:
Variables: X R F1 T1 C1 F T C F3 T3 C3
IH : forall X R E EA EB, subst X R E EA * -> subst X R E EB -> EA = EB
SA : subst X R (ifThenElse C T F) (ifThenElse C1 T1 F1) @
SA1 : subst X R C C1 *
SA2 : subst X R T T1 *
SA3 : subst X R F F1 *
SB : subst X R C C3
SB1 : subst X R T T3
SB2 : subst X R F F3
============================
ifThenElse C1 T1 F1 = ifThenElse C3 T3 F3
< apply IH to SA1 SB.
Subgoal 3:
Variables: X R F1 T1 F T C F3 T3 C3
IH : forall X R E EA EB, subst X R E EA * -> subst X R E EB -> EA = EB
SA : subst X R (ifThenElse C T F) (ifThenElse C3 T1 F1) @
SA1 : subst X R C C3 *
SA2 : subst X R T T1 *
SA3 : subst X R F F1 *
SB : subst X R C C3
SB1 : subst X R T T3
SB2 : subst X R F F3
============================
ifThenElse C3 T1 F1 = ifThenElse C3 T3 F3
< apply IH to SA2 SB1.
Subgoal 3:
Variables: X R F1 F T C F3 T3 C3
IH : forall X R E EA EB, subst X R E EA * -> subst X R E EB -> EA = EB
SA : subst X R (ifThenElse C T F) (ifThenElse C3 T3 F1) @
SA1 : subst X R C C3 *
SA2 : subst X R T T3 *
SA3 : subst X R F F1 *
SB : subst X R C C3
SB1 : subst X R T T3
SB2 : subst X R F F3
============================
ifThenElse C3 T3 F1 = ifThenElse C3 T3 F3
< apply IH to SA3 SB2.
Subgoal 3:
Variables: X R F T C F3 T3 C3
IH : forall X R E EA EB, subst X R E EA * -> subst X R E EB -> EA = EB
SA : subst X R (ifThenElse C T F) (ifThenElse C3 T3 F3) @
SA1 : subst X R C C3 *
SA2 : subst X R T T3 *
SA3 : subst X R F F3 *
SB : subst X R C C3
SB1 : subst X R T T3
SB2 : subst X R F F3
============================
ifThenElse C3 T3 F3 = ifThenElse C3 T3 F3
< search.
Proof completed.
< Prove mtc:shared_declarations:evalStep_unique.
Subgoal 1:
Variables: EB F T C1 C
IH : forall E EA EB, evalStep E EA * -> evalStep E EB -> EA = EB
EvA : evalStep (ifThenElse C T F) (ifThenElse C1 T F) @
EvB : evalStep (ifThenElse C T F) EB
EvA1 : evalStep C C1 *
============================
ifThenElse C1 T F = EB
< EvB: case EvB.
Subgoal 1.1:
Variables: F T C1 C C3
IH : forall E EA EB, evalStep E EA * -> evalStep E EB -> EA = EB
EvA : evalStep (ifThenElse C T F) (ifThenElse C1 T F) @
EvA1 : evalStep C C1 *
EvB : evalStep C C3
============================
ifThenElse C1 T F = ifThenElse C3 T F
< apply IH to EvA1 EvB.
Subgoal 1.1:
Variables: F T C C3
IH : forall E EA EB, evalStep E EA * -> evalStep E EB -> EA = EB
EvA : evalStep (ifThenElse C T F) (ifThenElse C3 T F) @
EvA1 : evalStep C C3 *
EvB : evalStep C C3
============================
ifThenElse C3 T F = ifThenElse C3 T F
< search.
Subgoal 1.2:
Variables: EB F C1
IH : forall E EA EB, evalStep E EA * -> evalStep E EB -> EA = EB
EvA : evalStep (ifThenElse trueE EB F) (ifThenElse C1 EB F) @
EvA1 : evalStep trueE C1 *
============================
ifThenElse C1 EB F = EB
< case EvA1.
Subgoal 1.3:
Variables: EB T C1
IH : forall E EA EB, evalStep E EA * -> evalStep E EB -> EA = EB
EvA : evalStep (ifThenElse falseE T EB) (ifThenElse C1 T EB) @
EvA1 : evalStep falseE C1 *
============================
ifThenElse C1 T EB = EB
< case EvA1.
Subgoal 2:
Variables: EA EB F
IH : forall E EA EB, evalStep E EA * -> evalStep E EB -> EA = EB
EvA : evalStep (ifThenElse trueE EA F) EA @
EvB : evalStep (ifThenElse trueE EA F) EB
============================
EA = EB
< EvB: case EvB.
Subgoal 2.1:
Variables: EA F C1
IH : forall E EA EB, evalStep E EA * -> evalStep E EB -> EA = EB
EvA : evalStep (ifThenElse trueE EA F) EA @
EvB : evalStep trueE C1
============================
EA = ifThenElse C1 EA F
< case EvB.
Subgoal 2.2:
Variables: EB F
IH : forall E EA EB, evalStep E EA * -> evalStep E EB -> EA = EB
EvA : evalStep (ifThenElse trueE EB F) EB @
============================
EB = EB
< search.
Subgoal 3:
Variables: EA EB T
IH : forall E EA EB, evalStep E EA * -> evalStep E EB -> EA = EB
EvA : evalStep (ifThenElse falseE T EA) EA @
EvB : evalStep (ifThenElse falseE T EA) EB
============================
EA = EB
< EvB: case EvB.
Subgoal 3.1:
Variables: EA T C1
IH : forall E EA EB, evalStep E EA * -> evalStep E EB -> EA = EB
EvA : evalStep (ifThenElse falseE T EA) EA @
EvB : evalStep falseE C1
============================
EA = ifThenElse C1 T EA
< case EvB.
Subgoal 3.2:
Variables: EB T
IH : forall E EA EB, evalStep E EA * -> evalStep E EB -> EA = EB
EvA : evalStep (ifThenElse falseE T EB) EB @
============================
EB = EB
< search.
Proof completed.
< Prove mtc:shared_declarations:ty_lookup.
Subgoal 1:
Variables: G1 G2
IH : forall G1 G2 E Ty,
typeOf G1 E Ty * -> (forall X XTy, lookup G1 X XTy -> lookup G2 X XTy) ->
typeOf G2 E Ty
Ty : typeOf G1 trueE boolTy @
L : forall X XTy, lookup G1 X XTy -> lookup G2 X XTy
============================
typeOf G2 trueE boolTy
< search.
Subgoal 2:
Variables: G1 G2
IH : forall G1 G2 E Ty,
typeOf G1 E Ty * -> (forall X XTy, lookup G1 X XTy -> lookup G2 X XTy) ->
typeOf G2 E Ty
Ty : typeOf G1 falseE boolTy @
L : forall X XTy, lookup G1 X XTy -> lookup G2 X XTy
============================
typeOf G2 falseE boolTy
< search.
Subgoal 3:
Variables: G1 G2 Ty F T C
IH : forall G1 G2 E Ty,
typeOf G1 E Ty * -> (forall X XTy, lookup G1 X XTy -> lookup G2 X XTy) ->
typeOf G2 E Ty
Ty : typeOf G1 (ifThenElse C T F) Ty @
L : forall X XTy, lookup G1 X XTy -> lookup G2 X XTy
Ty1 : typeOf G1 C boolTy *
Ty2 : typeOf G1 T Ty *
Ty3 : typeOf G1 F Ty *
============================
typeOf G2 (ifThenElse C T F) Ty
< apply IH to Ty1 L.
Subgoal 3:
Variables: G1 G2 Ty F T C
IH : forall G1 G2 E Ty,
typeOf G1 E Ty * -> (forall X XTy, lookup G1 X XTy -> lookup G2 X XTy) ->
typeOf G2 E Ty
Ty : typeOf G1 (ifThenElse C T F) Ty @
L : forall X XTy, lookup G1 X XTy -> lookup G2 X XTy
Ty1 : typeOf G1 C boolTy *
Ty2 : typeOf G1 T Ty *
Ty3 : typeOf G1 F Ty *
H1 : typeOf G2 C boolTy
============================
typeOf G2 (ifThenElse C T F) Ty
< apply IH to Ty2 L.
Subgoal 3:
Variables: G1 G2 Ty F T C
IH : forall G1 G2 E Ty,
typeOf G1 E Ty * -> (forall X XTy, lookup G1 X XTy -> lookup G2 X XTy) ->
typeOf G2 E Ty
Ty : typeOf G1 (ifThenElse C T F) Ty @
L : forall X XTy, lookup G1 X XTy -> lookup G2 X XTy
Ty1 : typeOf G1 C boolTy *
Ty2 : typeOf G1 T Ty *
Ty3 : typeOf G1 F Ty *
H1 : typeOf G2 C boolTy
H2 : typeOf G2 T Ty
============================
typeOf G2 (ifThenElse C T F) Ty
< apply IH to Ty3 L.
Subgoal 3:
Variables: G1 G2 Ty F T C
IH : forall G1 G2 E Ty,
typeOf G1 E Ty * -> (forall X XTy, lookup G1 X XTy -> lookup G2 X XTy) ->
typeOf G2 E Ty
Ty : typeOf G1 (ifThenElse C T F) Ty @
L : forall X XTy, lookup G1 X XTy -> lookup G2 X XTy
Ty1 : typeOf G1 C boolTy *
Ty2 : typeOf G1 T Ty *
Ty3 : typeOf G1 F Ty *
H1 : typeOf G2 C boolTy
H2 : typeOf G2 T Ty
H3 : typeOf G2 F Ty
============================
typeOf G2 (ifThenElse C T F) Ty
< search.
Proof completed.
< Prove mtc:shared_declarations:subst_preservation.
Subgoal 1:
Variables: X XTy TG Ty R
IH : forall X XTy TG E Ty R E',
typeOf ((X, XTy)::TG) E Ty -> subst X R E E' * -> typeOf [] R XTy -> typeOf TG E' Ty
Ty : typeOf ((X, XTy)::TG) trueE Ty
S : subst X R trueE trueE @
RTy : typeOf [] R XTy
============================
typeOf TG trueE Ty
< case Ty.
Subgoal 1:
Variables: X XTy TG R
IH : forall X XTy TG E Ty R E',
typeOf ((X, XTy)::TG) E Ty -> subst X R E E' * -> typeOf [] R XTy -> typeOf TG E' Ty
S : subst X R trueE trueE @
RTy : typeOf [] R XTy
============================
typeOf TG trueE boolTy
< search.
Subgoal 2:
Variables: X XTy TG Ty R
IH : forall X XTy TG E Ty R E',
typeOf ((X, XTy)::TG) E Ty -> subst X R E E' * -> typeOf [] R XTy -> typeOf TG E' Ty
Ty : typeOf ((X, XTy)::TG) falseE Ty
S : subst X R falseE falseE @
RTy : typeOf [] R XTy
============================
typeOf TG falseE Ty
< case Ty.
Subgoal 2:
Variables: X XTy TG R
IH : forall X XTy TG E Ty R E',
typeOf ((X, XTy)::TG) E Ty -> subst X R E E' * -> typeOf [] R XTy -> typeOf TG E' Ty
S : subst X R falseE falseE @
RTy : typeOf [] R XTy
============================
typeOf TG falseE boolTy
< search.
Subgoal 3:
Variables: X XTy TG Ty R F1 T1 C1 F T C
IH : forall X XTy TG E Ty R E',
typeOf ((X, XTy)::TG) E Ty -> subst X R E E' * -> typeOf [] R XTy -> typeOf TG E' Ty
Ty : typeOf ((X, XTy)::TG) (ifThenElse C T F) Ty
S : subst X R (ifThenElse C T F) (ifThenElse C1 T1 F1) @
RTy : typeOf [] R XTy
S1 : subst X R C C1 *
S2 : subst X R T T1 *
S3 : subst X R F F1 *
============================
typeOf TG (ifThenElse C1 T1 F1) Ty
< Ty: case Ty.
Subgoal 3:
Variables: X XTy TG Ty R F1 T1 C1 F T C
IH : forall X XTy TG E Ty R E',
typeOf ((X, XTy)::TG) E Ty -> subst X R E E' * -> typeOf [] R XTy -> typeOf TG E' Ty
S : subst X R (ifThenElse C T F) (ifThenElse C1 T1 F1) @
RTy : typeOf [] R XTy
S1 : subst X R C C1 *
S2 : subst X R T T1 *
S3 : subst X R F F1 *
Ty : typeOf ((X, XTy)::TG) C boolTy
Ty1 : typeOf ((X, XTy)::TG) T Ty
Ty2 : typeOf ((X, XTy)::TG) F Ty
============================
typeOf TG (ifThenElse C1 T1 F1) Ty
< apply IH to Ty S1 RTy.
Subgoal 3:
Variables: X XTy TG Ty R F1 T1 C1 F T C
IH : forall X XTy TG E Ty R E',
typeOf ((X, XTy)::TG) E Ty -> subst X R E E' * -> typeOf [] R XTy -> typeOf TG E' Ty
S : subst X R (ifThenElse C T F) (ifThenElse C1 T1 F1) @
RTy : typeOf [] R XTy
S1 : subst X R C C1 *
S2 : subst X R T T1 *
S3 : subst X R F F1 *
Ty : typeOf ((X, XTy)::TG) C boolTy
Ty1 : typeOf ((X, XTy)::TG) T Ty
Ty2 : typeOf ((X, XTy)::TG) F Ty
H1 : typeOf TG C1 boolTy
============================
typeOf TG (ifThenElse C1 T1 F1) Ty
< apply IH to Ty1 S2 RTy.
Subgoal 3:
Variables: X XTy TG Ty R F1 T1 C1 F T C
IH : forall X XTy TG E Ty R E',
typeOf ((X, XTy)::TG) E Ty -> subst X R E E' * -> typeOf [] R XTy -> typeOf TG E' Ty
S : subst X R (ifThenElse C T F) (ifThenElse C1 T1 F1) @
RTy : typeOf [] R XTy
S1 : subst X R C C1 *
S2 : subst X R T T1 *
S3 : subst X R F F1 *
Ty : typeOf ((X, XTy)::TG) C boolTy
Ty1 : typeOf ((X, XTy)::TG) T Ty
Ty2 : typeOf ((X, XTy)::TG) F Ty
H1 : typeOf TG C1 boolTy
H2 : typeOf TG T1 Ty
============================
typeOf TG (ifThenElse C1 T1 F1) Ty
< apply IH to Ty2 S3 RTy.
Subgoal 3:
Variables: X XTy TG Ty R F1 T1 C1 F T C
IH : forall X XTy TG E Ty R E',
typeOf ((X, XTy)::TG) E Ty -> subst X R E E' * -> typeOf [] R XTy -> typeOf TG E' Ty
S : subst X R (ifThenElse C T F) (ifThenElse C1 T1 F1) @
RTy : typeOf [] R XTy
S1 : subst X R C C1 *
S2 : subst X R T T1 *
S3 : subst X R F F1 *
Ty : typeOf ((X, XTy)::TG) C boolTy
Ty1 : typeOf ((X, XTy)::TG) T Ty
Ty2 : typeOf ((X, XTy)::TG) F Ty
H1 : typeOf TG C1 boolTy
H2 : typeOf TG T1 Ty
H3 : typeOf TG F1 Ty
============================
typeOf TG (ifThenElse C1 T1 F1) Ty
< search.
Proof completed.
< Prove mtc:shared_declarations:evalStep_type_preservation.
Subgoal 1:
Variables: Ty F T C1 C
IH : forall E Ty E', typeOf [] E Ty -> evalStep E E' * -> typeOf [] E' Ty
Ty : typeOf [] (ifThenElse C T F) Ty
Ev : evalStep (ifThenElse C T F) (ifThenElse C1 T F) @
Ev1 : evalStep C C1 *
============================
typeOf [] (ifThenElse C1 T F) Ty
< Ty: case Ty.
Subgoal 1:
Variables: Ty F T C1 C
IH : forall E Ty E', typeOf [] E Ty -> evalStep E E' * -> typeOf [] E' Ty
Ev : evalStep (ifThenElse C T F) (ifThenElse C1 T F) @
Ev1 : evalStep C C1 *
Ty : typeOf [] C boolTy
Ty1 : typeOf [] T Ty
Ty2 : typeOf [] F Ty
============================
typeOf [] (ifThenElse C1 T F) Ty
< apply IH to Ty Ev1.
Subgoal 1:
Variables: Ty F T C1 C
IH : forall E Ty E', typeOf [] E Ty -> evalStep E E' * -> typeOf [] E' Ty
Ev : evalStep (ifThenElse C T F) (ifThenElse C1 T F) @
Ev1 : evalStep C C1 *
Ty : typeOf [] C boolTy
Ty1 : typeOf [] T Ty
Ty2 : typeOf [] F Ty
H1 : typeOf [] C1 boolTy
============================
typeOf [] (ifThenElse C1 T F) Ty
< search.
Subgoal 2:
Variables: Ty E' F
IH : forall E Ty E', typeOf [] E Ty -> evalStep E E' * -> typeOf [] E' Ty
Ty : typeOf [] (ifThenElse trueE E' F) Ty
Ev : evalStep (ifThenElse trueE E' F) E' @
============================
typeOf [] E' Ty
< case Ty.
Subgoal 2:
Variables: Ty E' F
IH : forall E Ty E', typeOf [] E Ty -> evalStep E E' * -> typeOf [] E' Ty
Ev : evalStep (ifThenElse trueE E' F) E' @
H1 : typeOf [] trueE boolTy
H2 : typeOf [] E' Ty
H3 : typeOf [] F Ty
============================
typeOf [] E' Ty
< search.
Subgoal 3:
Variables: Ty E' T
IH : forall E Ty E', typeOf [] E Ty -> evalStep E E' * -> typeOf [] E' Ty
Ty : typeOf [] (ifThenElse falseE T E') Ty
Ev : evalStep (ifThenElse falseE T E') E' @
============================
typeOf [] E' Ty
< case Ty.
Subgoal 3:
Variables: Ty E' T
IH : forall E Ty E', typeOf [] E Ty -> evalStep E E' * -> typeOf [] E' Ty
Ev : evalStep (ifThenElse falseE T E') E' @
H1 : typeOf [] falseE boolTy
H2 : typeOf [] T Ty
H3 : typeOf [] E' Ty
============================
typeOf [] E' Ty
< search.
Proof completed.
< Prove mtc:shared_declarations:canonical_form.
Subgoal 1:
Variables: Ty
IH : forall V Ty, value V * -> typeOf [] V Ty -> canon Ty V
V : value trueE @
Ty : typeOf [] trueE Ty
============================
canon Ty trueE
< case Ty.
Subgoal 1:
IH : forall V Ty, value V * -> typeOf [] V Ty -> canon Ty V
V : value trueE @
============================
canon boolTy trueE
< search.
Subgoal 2:
Variables: Ty
IH : forall V Ty, value V * -> typeOf [] V Ty -> canon Ty V
V : value falseE @
Ty : typeOf [] falseE Ty
============================
canon Ty falseE
< case Ty.
Subgoal 2:
IH : forall V Ty, value V * -> typeOf [] V Ty -> canon Ty V
V : value falseE @
============================
canon boolTy falseE
< search.
Proof completed.
< Prove mtc:shared_declarations:subst_is.
Subgoal 1:
Variables: X R
IH : forall X R E E', is_e E -> is_e R -> subst X R E E' * -> is_e E'
IsE : is_e trueE
IsR : is_e R
S : subst X R trueE trueE @
============================
is_e trueE
< search.
Subgoal 2:
Variables: X R
IH : forall X R E E', is_e E -> is_e R -> subst X R E E' * -> is_e E'
IsE : is_e falseE
IsR : is_e R
S : subst X R falseE falseE @
============================
is_e falseE
< search.
Subgoal 3:
Variables: X R F1 T1 C1 F T C
IH : forall X R E E', is_e E -> is_e R -> subst X R E E' * -> is_e E'
IsE : is_e (ifThenElse C T F)
IsR : is_e R
S : subst X R (ifThenElse C T F) (ifThenElse C1 T1 F1) @
S1 : subst X R C C1 *
S2 : subst X R T T1 *
S3 : subst X R F F1 *
============================
is_e (ifThenElse C1 T1 F1)
< case IsE.
Subgoal 3:
Variables: X R F1 T1 C1 F T C
IH : forall X R E E', is_e E -> is_e R -> subst X R E E' * -> is_e E'
IsR : is_e R
S : subst X R (ifThenElse C T F) (ifThenElse C1 T1 F1) @
S1 : subst X R C C1 *
S2 : subst X R T T1 *
S3 : subst X R F F1 *
H1 : is_e C
H2 : is_e T
H3 : is_e F
============================
is_e (ifThenElse C1 T1 F1)
< apply IH to _ _ S1.
Subgoal 3:
Variables: X R F1 T1 C1 F T C
IH : forall X R E E', is_e E -> is_e R -> subst X R E E' * -> is_e E'
IsR : is_e R
S : subst X R (ifThenElse C T F) (ifThenElse C1 T1 F1) @
S1 : subst X R C C1 *
S2 : subst X R T T1 *
S3 : subst X R F F1 *
H1 : is_e C
H2 : is_e T
H3 : is_e F
H4 : is_e C1
============================
is_e (ifThenElse C1 T1 F1)
< apply IH to _ _ S2.
Subgoal 3:
Variables: X R F1 T1 C1 F T C
IH : forall X R E E', is_e E -> is_e R -> subst X R E E' * -> is_e E'
IsR : is_e R
S : subst X R (ifThenElse C T F) (ifThenElse C1 T1 F1) @
S1 : subst X R C C1 *
S2 : subst X R T T1 *
S3 : subst X R F F1 *
H1 : is_e C
H2 : is_e T
H3 : is_e F
H4 : is_e C1
H5 : is_e T1
============================
is_e (ifThenElse C1 T1 F1)
< apply IH to _ _ S3.
Subgoal 3:
Variables: X R F1 T1 C1 F T C
IH : forall X R E E', is_e E -> is_e R -> subst X R E E' * -> is_e E'
IsR : is_e R
S : subst X R (ifThenElse C T F) (ifThenElse C1 T1 F1) @
S1 : subst X R C C1 *
S2 : subst X R T T1 *
S3 : subst X R F F1 *
H1 : is_e C
H2 : is_e T
H3 : is_e F
H4 : is_e C1
H5 : is_e T1
H6 : is_e F1
============================
is_e (ifThenElse C1 T1 F1)
< search.
Proof completed.
< Prove mtc:shared_declarations:evalStep_is.
Subgoal 1:
Variables: F T C1 C
IH : forall E E', is_e E -> evalStep E E' * -> is_e E'
IsE : is_e (ifThenElse C T F)
Ev : evalStep (ifThenElse C T F) (ifThenElse C1 T F) @
Ev1 : evalStep C C1 *
============================
is_e (ifThenElse C1 T F)
< case IsE.
Subgoal 1:
Variables: F T C1 C
IH : forall E E', is_e E -> evalStep E E' * -> is_e E'
Ev : evalStep (ifThenElse C T F) (ifThenElse C1 T F) @
Ev1 : evalStep C C1 *
H1 : is_e C
H2 : is_e T
H3 : is_e F
============================
is_e (ifThenElse C1 T F)
< apply IH to _ Ev1.
Subgoal 1:
Variables: F T C1 C
IH : forall E E', is_e E -> evalStep E E' * -> is_e E'
Ev : evalStep (ifThenElse C T F) (ifThenElse C1 T F) @
Ev1 : evalStep C C1 *
H1 : is_e C
H2 : is_e T
H3 : is_e F
H4 : is_e C1
============================
is_e (ifThenElse C1 T F)
< search.
Subgoal 2:
Variables: E' F
IH : forall E E', is_e E -> evalStep E E' * -> is_e E'
IsE : is_e (ifThenElse trueE E' F)
Ev : evalStep (ifThenElse trueE E' F) E' @
============================
is_e E'
< case IsE.
Subgoal 2:
Variables: E' F
IH : forall E E', is_e E -> evalStep E E' * -> is_e E'
Ev : evalStep (ifThenElse trueE E' F) E' @
H1 : is_e trueE
H2 : is_e E'
H3 : is_e F
============================
is_e E'
< search.
Subgoal 3:
Variables: E' T
IH : forall E E', is_e E -> evalStep E E' * -> is_e E'
IsE : is_e (ifThenElse falseE T E')
Ev : evalStep (ifThenElse falseE T E') E' @
============================
is_e E'
< case IsE.
Subgoal 3:
Variables: E' T
IH : forall E E', is_e E -> evalStep E E' * -> is_e E'
Ev : evalStep (ifThenElse falseE T E') E' @
H1 : is_e falseE
H2 : is_e T
H3 : is_e E'
============================
is_e E'
< search.
Proof completed.
< Prove mtc:shared_declarations:subst_total.
Subgoal 2:
Variables: X R
IH : forall X R E,
is_e E * -> is_string X -> is_e R -> exists E', subst X R E E'
IsE : is_e trueE @
IsX : is_string X
IsR : is_e R
============================
exists E', subst X R trueE E'
< search.
Subgoal 3:
Variables: X R
IH : forall X R E,
is_e E * -> is_string X -> is_e R -> exists E', subst X R E E'
IsE : is_e falseE @
IsX : is_string X
IsR : is_e R
============================
exists E', subst X R falseE E'
< search.
Subgoal 4:
Variables: X R E3 E1 E2
IH : forall X R E,
is_e E * -> is_string X -> is_e R -> exists E', subst X R E E'
IsE : is_e (ifThenElse E2 E1 E3) @
IsX : is_string X
IsR : is_e R
IsE1 : is_e E2 *
IsE2 : is_e E1 *
IsE3 : is_e E3 *
============================
exists E', subst X R (ifThenElse E2 E1 E3) E'
< apply IH to IsE1 IsX IsR.
Subgoal 4:
Variables: X R E3 E1 E2 E'
IH : forall X R E,
is_e E * -> is_string X -> is_e R -> exists E', subst X R E E'
IsE : is_e (ifThenElse E2 E1 E3) @
IsX : is_string X
IsR : is_e R
IsE1 : is_e E2 *
IsE2 : is_e E1 *
IsE3 : is_e E3 *
H1 : subst X R E2 E'
============================
exists E', subst X R (ifThenElse E2 E1 E3) E'
< apply IH to IsE2 IsX IsR.
Subgoal 4:
Variables: X R E3 E1 E2 E' E'1
IH : forall X R E,
is_e E * -> is_string X -> is_e R -> exists E', subst X R E E'
IsE : is_e (ifThenElse E2 E1 E3) @
IsX : is_string X
IsR : is_e R
IsE1 : is_e E2 *
IsE2 : is_e E1 *
IsE3 : is_e E3 *
H1 : subst X R E2 E'
H2 : subst X R E1 E'1
============================
exists E', subst X R (ifThenElse E2 E1 E3) E'
< apply IH to IsE3 IsX IsR.
Subgoal 4:
Variables: X R E3 E1 E2 E' E'1 E'2
IH : forall X R E,
is_e E * -> is_string X -> is_e R -> exists E', subst X R E E'
IsE : is_e (ifThenElse E2 E1 E3) @
IsX : is_string X
IsR : is_e R
IsE1 : is_e E2 *
IsE2 : is_e E1 *
IsE3 : is_e E3 *
H1 : subst X R E2 E'
H2 : subst X R E1 E'1
H3 : subst X R E3 E'2
============================
exists E', subst X R (ifThenElse E2 E1 E3) E'
< search.
Proof completed.
< Prove mtc:shared_declarations:progress.
Subgoal 1:
IH : forall E Ty,
is_e E -> typeOf [] E Ty * -> value E \/ (exists E', evalStep E E')
IsE : is_e trueE
Ty : typeOf [] trueE boolTy @
============================
value trueE \/ (exists E', evalStep trueE E')
< search.
Subgoal 2:
IH : forall E Ty,
is_e E -> typeOf [] E Ty * -> value E \/ (exists E', evalStep E E')
IsE : is_e falseE
Ty : typeOf [] falseE boolTy @
============================
value falseE \/ (exists E', evalStep falseE E')
< search.
Subgoal 3:
Variables: Ty F T C
IH : forall E Ty,
is_e E -> typeOf [] E Ty * -> value E \/ (exists E', evalStep E E')
IsE : is_e (ifThenElse C T F)
Ty : typeOf [] (ifThenElse C T F) Ty @
Ty1 : typeOf [] C boolTy *
Ty2 : typeOf [] T Ty *
Ty3 : typeOf [] F Ty *
============================
value (ifThenElse C T F) \/ (exists E', evalStep (ifThenElse C T F) E')
< case IsE.
Subgoal 3:
Variables: Ty F T C
IH : forall E Ty,
is_e E -> typeOf [] E Ty * -> value E \/ (exists E', evalStep E E')
Ty : typeOf [] (ifThenElse C T F) Ty @
Ty1 : typeOf [] C boolTy *
Ty2 : typeOf [] T Ty *
Ty3 : typeOf [] F Ty *
H1 : is_e C
H2 : is_e T
H3 : is_e F
============================
value (ifThenElse C T F) \/ (exists E', evalStep (ifThenElse C T F) E')
< Or: apply IH to _ Ty1.
Subgoal 3:
Variables: Ty F T C
IH : forall E Ty,
is_e E -> typeOf [] E Ty * -> value E \/ (exists E', evalStep E E')
Ty : typeOf [] (ifThenElse C T F) Ty @
Ty1 : typeOf [] C boolTy *
Ty2 : typeOf [] T Ty *
Ty3 : typeOf [] F Ty *
H1 : is_e C
H2 : is_e T
H3 : is_e F
Or : value C \/ (exists E', evalStep C E')
============================
value (ifThenElse C T F) \/ (exists E', evalStep (ifThenElse C T F) E')
< E: case Or.
Subgoal 3.1:
Variables: Ty F T C
IH : forall E Ty,
is_e E -> typeOf [] E Ty * -> value E \/ (exists E', evalStep E E')
Ty : typeOf [] (ifThenElse C T F) Ty @
Ty1 : typeOf [] C boolTy *
Ty2 : typeOf [] T Ty *
Ty3 : typeOf [] F Ty *
H1 : is_e C
H2 : is_e T
H3 : is_e F
E : value C
============================
value (ifThenElse C T F) \/ (exists E', evalStep (ifThenElse C T F) E')
< C: apply canonical_form to E Ty1.
Subgoal 3.1:
Variables: Ty F T C
IH : forall E Ty,
is_e E -> typeOf [] E Ty * -> value E \/ (exists E', evalStep E E')
Ty : typeOf [] (ifThenElse C T F) Ty @
Ty1 : typeOf [] C boolTy *
Ty2 : typeOf [] T Ty *
Ty3 : typeOf [] F Ty *
H1 : is_e C
H2 : is_e T
H3 : is_e F
E : value C
C : canon boolTy C
============================
value (ifThenElse C T F) \/ (exists E', evalStep (ifThenElse C T F) E')
< case C.
Subgoal 3.1.1:
Variables: Ty F T
IH : forall E Ty,
is_e E -> typeOf [] E Ty * -> value E \/ (exists E', evalStep E E')
Ty : typeOf [] (ifThenElse trueE T F) Ty @
Ty1 : typeOf [] trueE boolTy *
Ty2 : typeOf [] T Ty *
Ty3 : typeOf [] F Ty *
H1 : is_e trueE
H2 : is_e T
H3 : is_e F
E : value trueE
============================
value (ifThenElse trueE T F) \/ (exists E', evalStep (ifThenElse trueE T F) E')
< search.
Subgoal 3.1.2:
Variables: Ty F T
IH : forall E Ty,
is_e E -> typeOf [] E Ty * -> value E \/ (exists E', evalStep E E')
Ty : typeOf [] (ifThenElse falseE T F) Ty @
Ty1 : typeOf [] falseE boolTy *
Ty2 : typeOf [] T Ty *
Ty3 : typeOf [] F Ty *
H1 : is_e falseE
H2 : is_e T
H3 : is_e F
E : value falseE
============================
value (ifThenElse falseE T F) \/
(exists E', evalStep (ifThenElse falseE T F) E')
< search.
Subgoal 3.2:
Variables: Ty F T C E'
IH : forall E Ty,
is_e E -> typeOf [] E Ty * -> value E \/ (exists E', evalStep E E')
Ty : typeOf [] (ifThenElse C T F) Ty @
Ty1 : typeOf [] C boolTy *
Ty2 : typeOf [] T Ty *
Ty3 : typeOf [] F Ty *
H1 : is_e C
H2 : is_e T
H3 : is_e F
E : evalStep C E'
============================
value (ifThenElse C T F) \/ (exists E', evalStep (ifThenElse C T F) E')
< search.
Proof completed.
