archive-nl.com » NL » R » ROBBERTKREBBERS.NL

Total: 145

Choose link from "Titles, links and description words view":

Or switch to "Titles and links view".
  • Module type_system_decidable
    Ei lookupE Γ s E end Definition rettype union alt m σ1 m σ2 option type K option option type K match m σ1 m σ2 with Some σ1 Some σ2 guard σ1 σ2 Some Some σ1 None m σ m σ None Some m σ end Global Instance rettype match dec cm σ rettype K σ Decision rettype match cm σ σ Proof refine match cm σ with true Some σ cast if decide σ σ false Some σ cast if decide σ σ σ voidT true None left false None cast if decide σ voidT end abstract first by intuition subst constructor inversion 1 subst intuition Defined Global Instance stmt type check TypeCheck envs rettype K stmt K fix go Γ s s struct s let TypeCheck envs go in let Γ Δ τ s Γ s in match s with skip Some false None e type check Γ s e maybe inr guard locks e Some false None goto throw Some true None ret e τ type check Γ s e maybe inr guard locks e Some true Some τ label scase Some false None local τ s guard Γ τ type check Γ Δ τ τ s s s1 s2 c1 m σ1 type check Γ s s1 c2 m σ2 type check Γ s s2 m σ rettype union alt m σ1 m σ2 Some c2 m σ catch s c m σ type check Γ s s Some false m σ loop s m σ type check Γ s s Some true m σ if e s1 else s2 τ b type check Γ s e maybe inr TBase guard τ b TVoid K guard locks e c1 m σ1 type check Γ s s1 c2 m σ2 type check Γ s s2 m σ rettype union alt m σ1 m σ2 Some c1 c2 m σ switch e s τ i type check Γ s e maybe inr TBase TInt guard locks e m σ type check Γ s s Some false m σ end S Global Instance sctx item lookup LookupE envs sctx item K rettype K rettype K λ Γ s Es τ lr match Es τ lr with s2 c1 m σ1 c2 m σ2 type check Γ s s2 m σ rettype union alt m σ1 m σ2 Some c2 m σ s1 c2 m σ2 c1 m σ1 type check Γ s s1 m σ rettype union alt m σ1 m σ2 Some c2 m σ catch c m σ Some false m σ loop c m σ Some true m σ if e else s2 c1 m σ1 τ b type check Γ s e maybe inr TBase guard τ b TVoid K guard locks e c2 m σ2 type check Γ s s2 m σ rettype union alt m σ1 m σ2 Some c1 c2 m σ if e s1 else c2 m σ2 τ b type check Γ s e maybe inr TBase guard τ b TVoid K guard locks e c1 m σ1 type check Γ s s1 m σ rettype union alt m σ1 m σ2 Some c1 c2 m σ switch e c m σ τ b type check Γ s e maybe inr TBase TInt guard locks e Some false m σ end S Global Instance esctx item lookup LookupE envs esctx item K rettype K type K λ Γ s Ee τ lr match Ee τ lr with Some false None ret Some true Some τ lr if s1 else s2 baseT τ b guard τ b TVoid c1 m σ1 type check Γ s s1 c2 m σ2 type check Γ s s2 m σ rettype union alt m σ1 m σ2 Some c1 c2 m σ switch s intT τ i m σ type check Γ s s Some false m σ None end S Global Instance ctx item lookup LookupE envs ctx item K focustype K focustype K λ Γ s Ek τ lr let Γ Δ τ s Γ s in match Ek τ lr with CStmt Es Stmt type cm σ1 Stmt type cm σ1 Γ s Es CLocal o τ Stmt type cm σ guard Δ o τ Some Stmt type cm σ CExpr e Ee Expr type τ τ type check Γ s e maybe inr guard locks e guard τ τ Stmt type τ Γ s Ee CFun E Fun type f σ s τ Γ f Expr type inr τ Γ s E maybe inr CParams f o σ s Stmt type cm σ σ s σ Γ f let os o σ s 1 in let σ s o σ s 2 in guard σ s σ s guard Δ os σ s guard rettype match cm σ σ Some Fun type f None end Global Instance focus type check TypeCheck envs focustype K focus K λ Γ s φ let Γ Δ τ s Γ s in match φ with Stmt d s cm σ type check Γ s s match d cm σ with v c Some τ τ type check Γ Δ v guard τ type K τ Some Stmt type cm σ false Some Stmt type cm σ None end Expr e Expr type type check Γ s e maybe inr Call f vs σ s Γ f σ s mapM type check Γ Δ vs guard σ s list type K σ s Some Fun type f Return f v σ Γ f σ type check Γ Δ v guard σ type K σ Some Fun type f Undef UndefExpr E e Expr type type check Γ s e lookupE Γ s E maybe inr Undef UndefBranch Es Ω v guard Γ Δ Ω τ type check Γ Δ v Stmt type τ Γ s Es end End deciders Section properties Context EnvSpec K Implicit Types Γ env K Implicit Types Δ memenv K Implicit Types τ σ type K Notation envs env K memenv

    Original URL path: http://robbertkrebbers.nl/research/ch2o/type_system_decidable.html (2015-08-10)
    Open archived version from archive


  • Module type_preservation
    stmt typed weaken mem unlock forward mem unlock valid intros m k e Ω v s1 s2 τ f HS typed inversion all split eauto using mem unlock forward eexists simpl split ands repeat typed constructor eauto using ctx typed weaken expr typed weaken stmt typed weaken mem unlock forward mem unlock valid intros m k e Ω v s1 s2 τ f HS typed inversion all eauto 10 intros m k e Ω v s1 s2 τ f HS typed inversion all split eauto using mem unlock forward eexists simpl split ands repeat typed constructor eauto using ctx typed weaken expr typed weaken stmt typed weaken mem unlock forward mem unlock valid intros m k e Ω v τ i x s τ f HS typed inversion all split eauto using mem unlock forward eexists simpl split ands repeat typed constructor eauto using ctx typed weaken expr typed weaken stmt typed weaken mem unlock forward mem unlock valid intros m k e Ω τ i x s τ f HS typed inversion all split eauto using mem unlock forward eexists simpl split ands repeat typed constructor eauto using ctx typed weaken expr typed weaken stmt typed weaken mem unlock forward mem unlock valid intros m k e Ω vb s τ f HS typed inversion all eauto 10 intros m k s1 s2 τ f HS typed inversion all eauto 10 intros m k s1 s2 τ f HS typed inversion all eauto 10 intros m k s1 s2 τ f HS typed inversion all eauto 10 intros m k s τ f HS typed inversion all eauto 10 intros m k s τ f HS typed inversion all eauto 10 intros m k s τ f HS typed inversion all eauto 10 intros m k s τ f HS typed inversion all eauto 10 intros m k e s1 s2 τ f HS typed inversion all eauto 10 intros m k e s1 s2 τ f HS typed inversion all split auto eexists simpl split ands repeat typed constructor eauto by rewrite andb false r intros m k e s τ f HS typed inversion all eauto 10 intros m k f s os vs τ f HS typed inversion all edestruct funenv lookup Γ m δ f as s cm τ eauto erewrite fmap type of by eauto simplify equality edestruct mem alloc list valid Γ m as eauto split auto eexists simpl split ands repeat typed constructor eauto using ctx typed weaken rewrite snd zip by erewrite Forall2 length by eauto lia eauto using stmt typed weaken intros m k f o σ s s τ f HS typed inversion all match goal with H rettype match apply rettype match false inv in H subst end eauto 10 using mem foldr free forward ctx typed weaken mem foldr free forward mem foldr free valid intros m k f o σ s v s τ f HS typed inversion all typed inversion all match goal with H

    Original URL path: http://robbertkrebbers.nl/research/ch2o/type_preservation.html (2015-08-10)
    Open archived version from archive

  • Module memory_injections
    unfold lookup simpl by rewrite proj1 not elem of dom by apply is fresh generalize Hfg fresh dom m1 unfold lookup simpl by rewrite proj1 not elem of dom by apply is fresh f equal apply map eq Hfg Qed Lemma lookup meminj id o meminj id K o Some o Proof done Qed Lemma lookup meminj id Some o1 o2 r meminj id o1 Some o2 r o2 o1 r Proof rewrite lookup meminj id naive solver Qed Lemma lookup meminj compose f g o f g o y1 r1 g o y2 r2 f y1 Some y2 r1 r2 Proof unfold lookup destruct f as m1 g as m2 csimpl done by destruct o as csimpl rewrite right id L by destruct o as by rewrite lookup merge by done Qed Lemma lookup meminj compose Some f g o1 o3 r f g o1 Some o3 r o2 r2 r3 g o1 Some o2 r2 f o2 Some o3 r3 r r2 r3 Proof rewrite lookup meminj compose split intros destruct g o1 as o2 r2 eqn simplify equality destruct f o2 as eqn naive solver by intros simplify option equality Qed Global Instance LeftId eq meminj K meminj id Proof by intros Qed Global Instance RightId eq meminj K meminj id Proof by intros Qed Global Instance Associative eq meminj K Proof intros f g h apply meminj eq intros o1 rewrite lookup meminj compose destruct h o1 as o2 r2 csimpl done rewrite lookup meminj compose destruct g o2 as o3 r3 csimpl done by destruct f o3 as csimpl rewrite associative L Qed Lemma meminj positive l f g f g meminj id f meminj id Proof by destruct f g Qed Lemma meminj positive r f g f g meminj id g meminj id

    Original URL path: http://robbertkrebbers.nl/research/ch2o/memory_injections.html (2015-08-10)
    Open archived version from archive

  • Module refinement_classes
    Xs Γ α f m1 m2 Ys C scope Notation Xss Γ α f m1 m2 2 Yss Forall2 λ Xs Ys Xs 2 Γ α f m1 m2 Ys 2 Xss Yss at level 70 format Xss Γ α f m1 m2 2 Yss C scope Notation X Γ α m Y X Γ α meminj id m m Y at level 70 format X Γ α m Y C scope Notation Xs Γ α m Ys Xs Γ α meminj id m m Ys at level 70 format Xs Γ α m Ys C scope Notation Xss Γ α m 2 Yss Xss Γ α meminj id m m 2 Yss at level 70 format Xss Γ α m 2 Yss C scope Notation X Γ α f m1 m2 Y τ refineT Γ α f m1 m2 X Y τ at level 70 Y at next level format X Γ α f m1 m2 Y τ C scope Notation Xs Γ α f m1 m2 Ys τ Forall2 λ X Y X Γ α f m1 m2 Y τ Xs Ys at level 70 Ys at next level format Xs Γ α f m1 m2 Ys τ C scope Notation Xs Γ α f m1 m2 Ys τ s Forall3 refineT Γ α f m1 m2 Xs Ys τ s at level 70 Ys at next level format Xs Γ α f m1 m2 Ys τ s C scope Notation Xs Γ α f m1 m2 1 Ys τ s Forall3 λ X Y τ X 1 Γ α f m1 m2 Y 1 τ Xs Ys τ s at level 70 Ys at next level format Xs Γ α f m1 m2 1 Ys τ s C scope Notation X Γ α m Y τ X Γ α meminj id m m Y τ at level 70 Y at next level format X Γ α m Y τ C scope Notation Xs Γ α m Ys τ Xs Γ α meminj id m m Ys τ at level 70 Ys at next level format Xs Γ α m Ys τ C scope Notation Xs Γ α m Ys τ s Xs Γ α meminj id m m Ys τ s at level 70 Ys at next level format Xs Γ α m Ys τ s C scope Notation Xs Γ α m 1 Ys τ s Xs Γ α meminj id m m 1 Ys τ s at level 70 Ys at next level format Xs Γ α m 1 Ys τ s C scope Notation X Γ α f m1 m2 Y τ σ path refine Γ α f m1 m2 X Y τ σ at level 70 Y at next level τ at next level σ at next level format X Γ α f m1 m2 Y τ σ C scope Notation X Γ α m Y τ σ X Γ α meminj id m m Y τ σ at level 70 Y at

    Original URL path: http://robbertkrebbers.nl/research/ch2o/refinement_classes.html (2015-08-10)
    Open archived version from archive

  • Module refinements
    elem of map of list 1 help rewrite elem of list fmap eexists o1 o2 r2 split auto by apply elem of map to list intros rewrite elem of list fmap intros o1 o2 r2 Ho1 simplify equality f equal apply elem of map to list in Ho1 destruct memenv refine injective Γ false meminj map f Δ1 Δ2 H Δ o1 o1 o2 r2 r2 simplify equality auto destruct memenv refine perm l Γ meminj map f Δ1 Δ2 o1 τ as simplify equality auto by destruct ref disjoint nil inv l r2 Qed Lemma memenv refine inverse Γ f Δ1 Δ2 Δ1 Γ false f Δ2 Δ2 Γ false meminj inverse f Δ1 Proof intros H Δ constructor intros o2 o2 o1 r1 r1 destruct lookup meminj inverse 1 help Γ f Δ1 Δ2 o1 o2 r1 auto destruct lookup meminj inverse 1 help Γ f Δ1 Δ2 o1 o2 r1 naive solver intros o2 o1 r destruct lookup meminj inverse 1 help Γ f Δ1 Δ2 o1 o2 r naive solver intros o2 o1 r τ destruct lookup meminj inverse 1 Γ f Δ1 Δ2 o1 o2 r τ as auto eauto using ref typed nil 2 intros o1 o2 r τ destruct lookup meminj inverse 1 help Γ f Δ1 Δ2 o2 o1 r as r memenv refine perm l Γ f Δ1 Δ2 o2 τ as o2 auto simplify equality eauto using ref typed nil 2 intros o2 o1 r destruct lookup meminj inverse 1 help Γ f Δ1 Δ2 o1 o2 r as eauto using memenv refine alive r intros o1 o2 r destruct lookup meminj inverse 1 help Γ f Δ1 Δ2 o2 o1 r as eauto using memenv refine alive l intros o2 τ2 destruct memenv refine perm r Γ f Δ1 Δ2 o2 τ2 as o1 eauto using lookup meminj inverse 2 intros o1 τ1 destruct memenv refine perm l Γ f Δ1 Δ2 o1 τ1 as o2 eauto using lookup meminj inverse 2 Qed Lemma memenv refine inverse compose Γ f Δ1 Δ2 o1 τ1 Δ1 Γ false f Δ2 Δ1 o1 τ1 meminj inverse f f o1 Some o1 Proof intros H Δ rewrite lookup meminj compose Some destruct memenv refine perm l Γ f Δ1 Δ2 o1 τ1 as o2 auto eexists o2 eauto using lookup meminj inverse 2 Qed Lemma memenv refine compose inverse Γ f Δ1 Δ2 o2 τ2 Δ1 Γ false f Δ2 Δ2 o2 τ2 f meminj inverse f o2 Some o2 Proof intros H Δ rewrite lookup meminj compose Some destruct memenv refine perm r Γ f Δ1 Δ2 o2 τ2 as o1 auto eexists o1 eauto using lookup meminj inverse 2 Qed Lemma memenv refine id Γ Δ α Δ Γ α Δ Proof repeat split intros until 0 rewrite lookup meminj id naive solver eauto using meminj id injective ref typed nil 2 Qed Lemma memenv refine compose Γ α1 α2 f1 f2 Δ1 Δ2 Δ3 Γ Δ1 Γ α1 f1

    Original URL path: http://robbertkrebbers.nl/research/ch2o/refinements.html (2015-08-10)
    Open archived version from archive

  • Module refinement_system
    m σ true m σ CIfL refine e1 e2 τ b s1 s2 c m σ c m σ m σ r e1 Γ τ s α f Δ1 Δ2 e2 inr baseT τ b τ b TVoid locks e1 locks e2 s1 Γ τ s α f Δ1 Δ2 s2 c m σ rettype union m σ m σ m σ r sctx item refine Γ τ s α f Δ1 Δ2 if e1 else s1 if e2 else s2 c m σ c c m σ r CIfR refine e1 e2 τ b s1 s2 c m σ c m σ m σ r e1 Γ τ s α f Δ1 Δ2 e2 inr baseT τ b τ b TVoid locks e1 locks e2 s1 Γ τ s α f Δ1 Δ2 s2 c m σ rettype union m σ m σ m σ r sctx item refine Γ τ s α f Δ1 Δ2 if e1 s1 else if e2 s2 else c m σ c c m σ r CSwitch refine e1 e2 τ i c m σ e1 Γ τ s α f Δ1 Δ2 e2 inr intT τ i locks e1 locks e2 sctx item refine Γ τ s α f Δ1 Δ2 switch e1 switch e2 c m σ false m σ Global Instance sctx refine PathRefine K env K list type K rettype K rettype K sctx item K curry sctx item refine Inductive esctx item refine Γ env K τ s list type K α bool f meminj K Δ1 Δ2 memenv K esctx item K esctx item K type K rettype K Prop CDoE refine τ esctx item refine Γ τ s α f Δ1 Δ2 τ false None CReturnE refine τ esctx item refine Γ τ s α f Δ1 Δ2 ret ret τ true Some τ CIfE refine τ b s1 s2 s1 s2 c m σ c m σ m σ r τ b TVoid s1 Γ τ s α f Δ1 Δ2 s2 c m σ s1 Γ τ s α f Δ1 Δ2 s2 c m σ rettype union m σ m σ m σ r esctx item refine Γ τ s α f Δ1 Δ2 if s1 else s1 S if s2 else s2 S baseT τ b c c m σ r CSwitchE refine τ i s1 s2 c m σ s1 Γ τ s α f Δ1 Δ2 s2 c m σ esctx item refine Γ τ s α f Δ1 Δ2 switch s1 switch s2 intT τ i false m σ Global Instance esctx item refine PathRefine K env K list type K type K rettype K esctx item K curry esctx item refine Inductive ctx item refine Γ env K τ s list type K α bool f meminj K Δ1 Δ2 memenv K ctx item K ctx item K focustype K focustype K Prop CStmt refine Es1 Es2 cm σ cm σ Es1 Γ τ s α f Δ1 Δ2 Es2 cm σ cm σ ctx item refine Γ τ s α f Δ1 Δ2 CStmt Es1 CStmt Es2 Stmt type cm σ Stmt type cm σ CLocal refine o1 o2 τ c m σ Δ1 o1 τ Δ2 o2 τ f o1 Some o2 ctx item refine Γ τ s α f Δ1 Δ2 CLocal o1 τ CLocal o2 τ Stmt type c m σ Stmt type c m σ CExpr refine e1 e2 Ee1 Ee2 τ cm σ e1 Γ τ s α f Δ1 Δ2 e2 inr τ locks e1 locks e2 Ee1 Γ τ s α f Δ1 Δ2 Ee2 τ cm σ ctx item refine Γ τ s α f Δ1 Δ2 CExpr e1 Ee1 CExpr e2 Ee2 Expr type τ Stmt type cm σ CFun refine E1 E2 g σ s τ σ Γ g Some σ s τ E1 Γ τ s α f Δ1 Δ2 E2 inr τ inr σ ctx item refine Γ τ s α f Δ1 Δ2 CFun E1 CFun E2 Fun type g Expr type σ CParams refine g os1 os2 σ s cm σ σ Γ g Some σ s σ Δ1 os1 σ s Δ2 os2 σ s Forall2 λ o1 o2 f o1 Some o2 os1 os2 rettype match cm σ σ ctx item refine Γ τ s α f Δ1 Δ2 CParams g zip os1 σ s CParams g zip os2 σ s Stmt type cm σ Fun type g Global Instance ctx item refine PathRefine K env K list type K focustype K focustype K ctx item K curry ctx item refine Inductive ctx refine Γ env K α bool f meminj K Δ1 Δ2 memenv K ctx K ctx K focustype K focustype K Prop ctx nil refine 2 τ f ctx refine Γ α f Δ1 Δ2 τ f τ f ctx cons refine 2 Ek1 Ek2 k1 k2 τ f τ f τ f Ek1 Γ locals k1 2 α f Δ1 Δ2 Ek2 τ f τ f ctx refine Γ α f Δ1 Δ2 k1 k2 τ f τ f ctx refine Γ α f Δ1 Δ2 Ek1 k1 Ek2 k2 τ f τ f Global Instance ctx refine PathRefine K env K focustype K focustype K ctx K ctx refine Inductive direction refine Γ env K α bool f meminj K Δ1 Δ2 memenv K direction K direction K rettype K Prop Down refine cm τ direction refine Γ α f Δ1 Δ2 cm τ Up refine m τ direction refine Γ α f Δ1 Δ2 false m τ Top refine c v1 v2 τ v1 Γ α f Δ1 Δ2 v2 τ direction refine Γ α f Δ1 Δ2 v1 v2 c Some τ Goto refine l cm τ direction refine Γ α f Δ1 Δ2 l l cm τ Throw refine n cm τ direction refine Γ α f Δ1 Δ2 n n cm τ Switch refine mx cm τ direction refine Γ α f Δ1 Δ2 mx mx cm τ Global Instance direction refine RefineT K env K rettype K direction K direction refine Inductive focus refine Γ env K τ s list type K α bool f meminj K Δ1 Δ2 memenv K focus K focus K focustype K Prop Stmt refine d1 d2 s1 s2 cm σ s1 Γ τ s α f Δ1 Δ2 s2 cm σ d1 Γ α f Δ1 Δ2 d2 cm σ focus refine Γ τ s α f Δ1 Δ2 Stmt d1 s1 Stmt d2 s2 Stmt type cm σ Expr refine e1 e2 τ e1 Γ τ s α f Δ1 Δ2 e2 inr τ focus refine Γ τ s α f Δ1 Δ2 Expr e1 Expr e2 Expr type τ Call refine g vs1 vs2 σ s σ Γ g Some σ s σ vs1 Γ α f Δ1 Δ2 vs2 σ s focus refine Γ τ s α f Δ1 Δ2 Call g vs1 Call g vs2 Fun type g Return refine g σ s σ v1 v2 Γ g Some σ s σ v1 Γ α f Δ1 Δ2 v2 σ focus refine Γ τ s α f Δ1 Δ2 Return g v1 Return g v2 Fun type g UndefExpr refine E1 E2 e1 e2 τ lr τ e1 Γ τ s α f Δ1 Δ2 e2 τ lr E1 Γ τ s α f Δ1 Δ2 E2 τ lr inr τ focus refine Γ τ s α f Δ1 Δ2 Undef UndefExpr E1 e1 Undef UndefExpr E2 e2 Expr type τ UndefBranch refine Es1 Es2 Ω1 Ω2 v1 v2 τ m σ v1 Γ α f Δ1 Δ2 v2 τ Es1 Γ τ s α f Δ1 Δ2 Es2 τ m σ Ω1 Γ α f Δ1 Δ2 Ω2 focus refine Γ τ s α f Δ1 Δ2 Undef UndefBranch Es1 Ω1 v1 Undef UndefBranch Es2 Ω2 v2 Stmt type m σ Global Instance focus refine RefineT K env K list type K focustype K focus K curry focus refine Inductive state refine Γ env K α bool f meminj K state K state K focustype K Prop State refine k1 φ1 m1 k2 φ2 m2 τ f σ f φ1 Γ locals k1 2 α f m1 m2 φ2 τ f k1 Γ α f m1 m2 k2 τ f σ f m1 Γ α f m2 state refine Γ α f State k1 φ1 m1 State k2 φ2 m2 σ f Undef State refine S1 S2 σ f α Γ S1 σ f Γ S2 σ f is undef state S1 state refine Γ α f S1 S2 σ f Global Instance state refine RefineTM K env K focustype K state K state refine Global Instance funenv refine Refine K env K funenv K λ Γ α f Δ1 Δ2 δ1 δ2 g match δ1 g δ2 g Γ g with Some s1 Some s2 Some τ s τ cm τ Forall type complete Γ τ s s1 Γ τ s α f Δ1 Δ2 s2 cm τ rettype match cm τ τ gotos s1 labels s1 throws valid 0 s1 None None None True False end End refinements Section properties Context EnvSpec K Implicit Types Γ env K Implicit Types f meminj K Implicit Types α bool Implicit Types o index Implicit Types Δ memenv K Implicit Types m mem K Implicit Types e expr K Implicit Types es list expr K Implicit Types s stmt K Implicit Types τ σ type K Implicit Types a addr K Implicit Types v val K Implicit Types ν lrval K Implicit Types d direction K Implicit Types Ei ectx item K Implicit Types E ectx K Implicit Types Es sctx item K Implicit Types Ee esctx item K Implicit Types Ek ctx item K Implicit Types k ctx K Implicit Types φ focus K Ltac solve length simplify equality repeat match goal with H Forall2 apply Forall2 length in H end lia Lemma EVal refine inv l Γ α f Δ1 Δ2 τ s Ω s1 vs1 es2 σ s Ω s1 vs1 Γ τ s α f Δ1 Δ2 es2 inr σ s length vs1 length Ω s1 Ω s2 vs2 es2 Ω s2 vs2 Ω s1 Γ α f Δ1 Δ2 Ω s2 length Ω s2 length vs2 vs1 Γ α f Δ1 Δ2 vs2 σ s Proof rewrite Forall2 same length revert Ω s1 vs1 σ s induction es2 as IH intros inversion 1 destruct 1 intros simplify equality refine inversion all eexists repeat constructor edestruct IH as eauto subst eexists split ands simpl eauto using Forall3 cons with arith Qed Lemma EVal refine inv r Γ α f Δ1 Δ2 τ s es1 Ω s2 vs2 σ s es1 Γ τ s α f Δ1 Δ2 Ω s2 vs2 inr σ s length vs2 length Ω s2 Ω s1 vs1 es1 Ω s1 vs1 Ω s1 Γ α f Δ1 Δ2 Ω s2 length Ω s1 length vs1 vs1 Γ α f Δ1 Δ2 vs2 σ s Proof rewrite Forall2 same length revert Ω s2 vs2 σ s induction es1 as IH intros inversion 1 destruct 1 intros simplify equality refine inversion all eexists repeat constructor edestruct IH as eauto subst eexists split ands simpl eauto using Forall3 cons with arith Qed Lemma ectx item subst refine Γ α f Δ1 Δ2 τ s Ei1 Ei2 e1 e2 τ lr τ lr Ei1 Γ τ s α f Δ1 Δ2 Ei2 τ lr τ lr e1 Γ τ s α f Δ1 Δ2 e2 τ lr subst Ei1 e1 Γ τ s α f Δ1 Δ2 subst Ei2 e2 τ lr Proof destruct 1 simpl refine constructor eauto rewrite fmap app eauto using Forall3 app Forall3 cons Qed Lemma ectx subst refine Γ α f Δ1 Δ2 τ s E1 E2 e1 e2 τ lr τ lr E1 Γ τ s α f Δ1 Δ2 E2 τ lr τ lr e1 Γ τ s α f Δ1 Δ2 e2 τ lr subst E1 e1 Γ τ s α f Δ1 Δ2 subst E2 e2 τ lr Proof intros HE revert e1 e2 induction HE simpl eauto using ectx item subst refine Qed Lemma sctx item subst refine Γ α f Δ1 Δ2 τ s Es1 Es2 s1 s2 mc τ mc τ Es1 Γ τ s α f Δ1 Δ2 Es2 mc τ mc τ s1 Γ τ s α f Δ1 Δ2 s2 mc τ subst Es1 s1 Γ τ s α f Δ1 Δ2 subst Es2 s2 mc τ Proof destruct 1 simpl refine constructor eauto Qed Lemma ectx item subst refine inv r Γ α f Δ1 Δ2 τ s e1 Ei2 e2 τ lr e1 Γ τ s α f Δ1 Δ2 subst Ei2 e2 τ lr e1 Ei1 τ lr e1 subst Ei1 e1 Ei1 Γ τ s α f Δ1 Δ2 Ei2 τ lr τ lr e1 Γ τ s α f Δ1 Δ2 e2 τ lr Proof intros He destruct Ei2 refine inversion He list simplifier try match goal with H E reverse rewrite reverse involutive E in H end by do 3 eexists split ands repeat refine constructor simpl eauto rewrite reverse involutive Qed Lemma ectx subst refine inv r Γ α f Δ1 Δ2 τ s e1 E2 e2 τ lr e1 Γ τ s α f Δ1 Δ2 subst E2 e2 τ lr e1 E1 τ lr e1 subst E1 e1 E1 Γ τ s α f Δ1 Δ2 E2 τ lr τ lr e1 Γ τ s α f Δ1 Δ2 e2 τ lr Proof revert e2 induction E2 as Ei2 E2 IH intros e2 He simpl in by eexists e1 τ lr split ands repeat refine constructor destruct IH subst Ei2 e2 as e1 E1 τ lr auto destruct ectx item subst refine inv r Γ α f Δ1 Δ2 τ s e1 Ei2 e2 τ lr as e1 Ee1 τ lr auto exists e1 Ee1 E1 τ lr split ands repeat refine constructor eauto Qed Lemma esctx item subst refine inv r Γ α f Δ1 Δ2 τ s s1 Ee2 e2 mc τ s1 Γ τ s α f Δ1 Δ2 subst Ee2 e2 mc τ e1 Ee1 τ s1 subst Ee1 e1 Ee1 Γ τ s α f Δ1 Δ2 Ee2 τ mc τ e1 Γ τ s α f Δ1 Δ2 e2 inr τ locks e1 locks e2 Proof by destruct Ee2 inversion 1 subst do 3 eexists split ands repeat refine constructor eauto Qed Lemma sctx item subst refine inv r Γ α f Δ1 Δ2 τ s s1 Es2 s2 mc τ s1 Γ τ s α f Δ1 Δ2 subst Es2 s2 mc τ s1 Es1 mc τ s1 subst Es1 s1 Es1 Γ τ s α f Δ1 Δ2 Es2 mc τ mc τ s1 Γ τ s α f Δ1 Δ2 s2 mc τ Proof by destruct Es2 inversion 1 subst do 3 eexists split ands repeat refine constructor eauto Qed Lemma expr refine nf inv Γ α f Δ1 Δ2 τ s e1 e2 τ lr e1 Γ τ s α f Δ1 Δ2 e2 τ lr is nf e2 is nf e1 Proof destruct 1 inversion clear 1 constructor Qed Lemma exprs refine nf inv Γ α f Δ1 Δ2 τ s es1 es2 τ lrs es1 Γ τ s α f Δ1 Δ2 es2 τ lrs Forall is nf es2 Forall is nf es1 Proof induction 1 inversion clear 1 eauto using expr refine nf inv Qed Lemma expr refine redex inv Γ α f Δ1 Δ2 τ s e1 e2 τ lr e1 Γ τ s α f Δ1 Δ2 e2 τ lr is redex e2 is redex e1 Proof destruct 1 inversion clear 1 constructor eauto using expr refine nf inv exprs refine nf inv Qed Lemma stmt refine gotos Γ α f Δ1 Δ2 τ s s1 s2 mc τ s1 Γ τ s α f Δ1 Δ2 s2 mc τ gotos s1 gotos s2 Proof induction 1 simpl auto with f equal Qed Lemma stmt refine labels Γ α f Δ1 Δ2 τ s s1 s2 mc τ s1 Γ τ s α f Δ1 Δ2 s2 mc τ labels s1 labels s2 Proof induction 1 simpl auto with f equal Qed Lemma stmt refine throws valid Γ α f Δ1 Δ2 τ s s1 s2 mc τ n s1 Γ τ s α f Δ1 Δ2 s2 mc τ throws valid n s1 throws valid n s2 Proof intros Hs revert n induction Hs naive solver Qed Lemma stmt refine cases Γ α f Δ1 Δ2 τ s s1 s2 mc τ s1 Γ τ s α f Δ1 Δ2 s2 mc τ cases s1 cases s2 Proof induction 1 simpl auto with f equal Qed Lemma ctx refine locals types Γ α f Δ1 Δ2 k1 k2 τ f τ f Γ k1 Γ α f Δ1 Δ2 k2 τ f τ f locals k1 2 locals k2 2 Proof assert os1 os2 list index σ s list type K P Forall2 P os1 os2 zip os1 σ s 2 zip os2 σ s 2 intros os1 os2 σ s P Hos revert σ s induction Hos intros f equal auto induction 2 as simpl eauto with f equal Qed Lemma ctx refine locals refine Γ α f Δ1 Δ2 k1 k2 τ f τ f k1 Γ α f Δ1 Δ2 k2 τ f τ f Forall2 stack item refine f Δ1 Δ2 locals k1 locals k2 Proof assert os1 os2 σ s Δ1 os1 σ s Δ2 os2 σ s Forall2 λ o1 o2 f o1 Some o2 os1 os2 Forall2 stack item refine f Δ1 Δ2 zip os1 σ s zip os2 σ s intros os1 os2 σ s Hos revert os2 induction Hos intros decompose Forall hyps repeat constructor eauto induction 1 as simplify equality repeat constructor eauto Qed Lemma sctx item catch refine Γ α f Δ1 Δ2 τ s Es1 Es2 s1 s2 mc τ mc τ Es1 Γ τ s α f Δ1 Δ2 Es2 mc τ mc τ Es1 catch Es2 catch Proof by destruct 1 Qed Lemma sctx item switch refine Γ α f Δ1 Δ2 τ s Es1 Es2 s1 s2 mc τ mc τ Es1 Γ τ s α f Δ1 Δ2 Es2 mc τ mc τ maybe CSwitch Es2 None maybe CSwitch Es1 None Proof by destruct 1 Qed Lemma direction in refine r Γ τ s α f Δ1 Δ2 s1 s2 d1 d2 mc τ s1 Γ τ s α f Δ1 Δ2 s2 mc τ d1 Γ α f Δ1 Δ2 d2 mc τ direction in d2 s2 direction in d1 s1 Proof by destruct 2 simpl erewrite stmt refine labels stmt refine cases by eauto Qed Lemma direction out refine r Γ τ s α f Δ1 Δ2 s1 s2 d1 d2 mc τ s1 Γ τ s α f Δ1 Δ2 s2 mc τ d1 Γ α f Δ1 Δ2 d2 mc τ direction out d2 s2 direction out d1 s1 Proof by destruct 2 simpl erewrite stmt refine labels by eauto Qed Lemma funenv lookup refine r Γ α f Δ1 Δ2 δ1 δ2 g s2 δ1 Γ α f Δ1 Δ2 δ2 δ2 g Some s2 s1 τ s τ cm τ δ1 g Some s1 Γ g Some τ s τ s1 Γ τ s α f Δ1 Δ2 s2 cm τ rettype match cm τ τ gotos s1 labels s1 throws valid 0 s1 Proof intros H δ specialize H δ g repeat case match naive solver Qed Lemma state refine mem Γ α f S1 S2 σ f is undef state S1 S1 Γ α f S2 σ f SMem S1 Γ α f SMem S2 Proof by destruct 2 eauto using cmap refine memenv refine Qed Lemma lrval refine typed l Γ α f Δ1 Δ2 ν1 ν2 τ lr Γ ν1 Γ α f Δ1 Δ2 ν2 τ lr Γ Δ1 ν1 τ lr Proof destruct 2 typed constructor eauto using val refine typed l ptr refine typed l Qed Lemma expr refine typed l Γ α f Δ1 Δ2 τ s e1 e2 τ lr Γ e1 Γ τ s α f Δ1 Δ2 e2 τ lr Γ Δ1 τ s e1 τ lr Proof assert es1 es2 τ lrs Forall3 λ e1 τ lr Γ Δ1 τ s e1 τ lr es1 es2 τ lrs Γ Δ1 τ s es1 τ lrs induction 1 constructor eauto induction 2 using expr refine ind typed constructor eauto using lrval refine typed l locks refine valid l Qed Lemma exprs refine typed l Γ α f Δ1 Δ2 τ s es1 es2 τ lrs Γ es1 Γ τ s α f Δ1 Δ2 es2 τ lrs Γ Δ1 τ s es1 τ lrs Proof induction 2 eauto using expr refine typed l Qed Lemma ectx item refine typed l Γ α f Δ1 Δ2 τ s Ei1 Ei2 τ lr τ lr Γ Ei1 Γ τ s α f Δ1 Δ2 Ei2 τ lr τ lr Γ Δ1 τ s Ei1 τ lr τ lr Proof destruct 2 typed constructor eauto using expr refine typed l exprs refine typed l Qed Lemma ectx refine typed l Γ α f Δ1 Δ2 τ s E1 E2 τ lr τ lr Γ E1 Γ τ s α f Δ1 Δ2 E2 τ lr τ lr Γ Δ1 τ s E1 τ lr τ lr Proof induction 2 typed constructor eauto using ectx item refine typed l Qed Lemma stmt refine typed l Γ α f Δ1 Δ2 τ s s1 s2 mc τ Γ s1 Γ τ s α f Δ1 Δ2 s2 mc τ Γ Δ1 τ s s1 mc τ Proof induction 2 typed constructor eauto using expr refine typed l Qed Lemma sctx item refine typed l Γ α f Δ1 Δ2 τ s Es1 Es2 mc τ mc τ Γ Es1 Γ τ s α f Δ1 Δ2 Es2 mc τ mc τ Γ Δ1 τ s Es1 mc τ mc τ Proof destruct 2 typed constructor eauto using stmt refine typed l expr refine typed l Qed Lemma esctx item refine typed l Γ α f Δ1 Δ2 τ s Ee1 Ee2 τ lr mc τ Γ Ee1 Γ τ s α f Δ1 Δ2 Ee2 τ lr mc τ Γ Δ1 τ s Ee1 τ lr mc τ Proof destruct 2 typed constructor eauto using stmt refine typed l Qed Lemma ctx item refine typed l Γ α f Δ1 Δ2 τ s Ek1 Ek2 τ f τ f Γ Ek1 Γ τ s α f Δ1 Δ2 Ek2 τ f τ f Γ Δ1 τ s Ek1 τ f τ f Proof destruct 2 typed constructor eauto using expr refine typed l esctx item refine typed l sctx item refine typed l ectx refine typed l Qed Lemma ctx refine typed l Γ α f Δ1 Δ2 k1 k2 τ f τ f Γ k1 Γ α f Δ1 Δ2 k2 τ f τ f Γ Δ1 k1 τ f τ f Proof induction 2 typed constructor eauto using ctx item refine typed l Qed Lemma direction refine typed l Γ α f Δ1 Δ2 d1 d2 τ lr Γ d1 Γ α f Δ1 Δ2 d2 τ lr Γ Δ1 d1 τ lr Proof destruct 2 typed constructor eauto using val refine typed l Qed Lemma focus refine typed l Γ α f Δ1 Δ2 τ s φ1 φ2 τ f Γ φ1 Γ τ s α f Δ1 Δ2 φ2 τ f Γ Δ1 τ s φ1 τ f Proof induction 2 typed constructor eauto using stmt refine typed l direction refine typed l expr refine typed l vals refine typed l val refine typed l ectx refine typed l esctx item refine typed l locks refine valid l Qed Lemma state refine typed l Γ α f S1 S2 σ f Γ S1 Γ α f S2 σ f Γ S1 σ f Proof destruct 2 do 2 red eauto 10 using focus refine typed l ctx refine typed l cmap refine valid l Qed Lemma funenv refine typed l Γ α f Δ1 Δ2 δ1 δ2 Γ δ1 Γ α f Δ1 Δ2 δ2 Γ Δ1 δ1 Proof intros H δ split intros g s specialize H δ g destruct δ2 Γ as τ s τ simplify option equality try done destruct H δ as cm τ eauto 20 using stmt refine typed l rewrite elem of subseteq intros g rewrite elem of dom intros τ s τ specialize H δ g destruct δ1 g δ2 g simplify option equality naive solver Qed Lemma lrval refine typed r Γ α f Δ1 Δ2 ν1 ν2 τ lr Γ ν1 Γ α f Δ1 Δ2 ν2 τ lr Γ Δ2 ν2 τ lr Proof destruct 2 typed constructor eauto using val refine typed r ptr refine typed r Qed Lemma expr refine typed r Γ α f Δ1 Δ2 τ s e1 e2 τ lr Γ e1 Γ τ s α f Δ1 Δ2 e2 τ lr Γ Δ2 τ s e2 τ lr Proof assert es1 es2 τ lrs Forall3 λ e2 τ lr Γ Δ2 τ s e2 τ lr es1 es2 τ lrs Γ Δ2 τ s es2 τ lrs induction 1 constructor eauto induction 2 using expr refine ind typed constructor eauto using lrval refine typed r locks refine valid r Qed Lemma exprs refine typed r Γ α f Δ1 Δ2 τ s es1 es2 τ lrs Γ es1 Γ τ s α f Δ1 Δ2 es2 τ lrs Γ Δ2 τ s es2 τ lrs Proof induction 2 eauto using expr refine typed r Qed Lemma ectx item refine typed r Γ α f Δ1 Δ2 τ s Ei1 Ei2 τ lr τ lr Γ Ei1 Γ τ s α f Δ1 Δ2 Ei2 τ lr τ lr Γ Δ2 τ s Ei2 τ lr τ lr Proof destruct 2 typed constructor eauto using expr refine typed r exprs refine typed r Qed Lemma ectx refine typed r Γ α f Δ1 Δ2 τ s E1 E2 τ lr τ lr Γ E1 Γ τ s α f Δ1 Δ2 E2 τ lr τ lr Γ Δ2 τ s E2 τ lr τ lr Proof induction 2 typed constructor eauto using ectx item refine typed r Qed Lemma stmt refine typed r Γ f α Δ1 Δ2 τ s s1 s2 mc τ Γ s1 Γ τ s α f Δ1 Δ2 s2 mc τ Γ Δ2 τ s s2 mc τ Proof induction 2 typed constructor eauto using expr refine typed r Qed Lemma sctx item refine typed r Γ α f Δ1 Δ2 τ s Es1 Es2 mc τ mc τ Γ Es1 Γ τ s α f Δ1 Δ2 Es2 mc τ mc τ Γ Δ2 τ s Es2 mc τ mc τ Proof destruct 2 typed constructor eauto using stmt refine typed r expr refine typed r Qed Lemma esctx item refine typed r Γ α f Δ1 Δ2 τ s Ee1 Ee2 τ lr mc τ Γ Ee1 Γ τ s α f Δ1 Δ2 Ee2 τ lr mc τ Γ Δ2 τ s Ee2 τ lr mc τ Proof destruct 2 typed constructor eauto using stmt refine typed r Qed Lemma ctx item refine typed r Γ α f Δ1 Δ2 τ s Ek1 Ek2 τ f τ f Γ Ek1 Γ τ s α f Δ1 Δ2 Ek2 τ f τ f Γ Δ2 τ s Ek2 τ f τ f Proof destruct 2 typed constructor eauto using expr refine typed r esctx item refine typed r sctx item refine typed r ectx refine typed r Qed Lemma ctx refine typed r Γ α f Δ1 Δ2 k1 k2 τ f τ f Γ k1 Γ α f Δ1 Δ2 k2 τ f τ f Γ Δ2 k2 τ f τ f Proof induction 2 typed constructor erewrite ctx refine locals types by eauto eauto using ctx item refine typed r Qed Lemma direction refine typed r Γ α f Δ1 Δ2 d1 d2 τ lr Γ d1 Γ α f Δ1 Δ2 d2 τ lr Γ Δ2 d2 τ lr Proof destruct 2 typed constructor eauto using val refine typed r Qed Lemma focus refine typed r Γ α f Δ1 Δ2 τ s φ1 φ2 τ f Γ φ1 Γ τ s α f Δ1 Δ2 φ2 τ f Γ Δ2 τ s φ2 τ f Proof induction 2 typed constructor eauto using stmt refine typed r direction refine typed r expr refine typed r vals refine typed r val refine typed r ectx refine typed r esctx item refine typed r locks refine valid r Qed Lemma state refine typed r Γ α f S1 S2 σ f Γ S1 Γ α f S2 σ f Γ S2 σ f Proof destruct 2 eauto eexists split ands erewrite ctx refine locals types by eauto eauto using focus refine typed r ctx refine typed r cmap refine valid r Qed Lemma funenv refine typed r Γ α f Δ1 Δ2 δ1 δ2 Γ δ1 Γ α f Δ1 Δ2 δ2 Γ Δ2 δ2 Proof intros H δ split intros g s specialize H δ g destruct δ1 Γ as τ s τ simplify option equality try done destruct H δ as cm τ erewrite stmt refine labels stmt refine gotos by eauto eauto 15 using stmt refine typed r stmt refine throws valid rewrite elem of subseteq intros g rewrite elem of dom intros τ s τ specialize H δ g destruct δ1 δ2 simplify option equality naive solver Qed Lemma lrval refine id Γ α Δ ν τ lr Γ Δ ν τ lr ν Γ α Δ ν τ lr Proof destruct 1 constructor eauto using val refine id ptr refine id Qed Lemma expr refine id Γ α Δ τ s e τ lr Γ Δ τ s e τ lr e Γ τ s α Δ e τ lr Proof assert es τ lrs Forall2 λ e τ lr e Γ τ s α Δ e τ lr es τ lrs es Γ τ s α Δ es τ lrs induction 1 constructor eauto induction 1 using expr typed ind refine constructor eauto using locks refine id lrval refine id Qed Lemma exprs refine id Γ α Δ τ s es τ lrs Γ Δ τ s es τ lrs es Γ τ s α Δ es τ lrs Proof induction 1 constructor eauto using expr refine id Qed Lemma ectx item refine id Γ α Δ τ s Ei τ lr τ lr Γ Δ τ s Ei τ lr τ lr Ei Γ τ s α Δ Ei τ lr τ lr Proof destruct 1 refine constructor eauto using expr refine id exprs refine id Qed Lemma ectx refine id Γ α Δ τ s E τ lr τ lr Γ Δ τ s E τ lr τ lr E Γ τ s α Δ E τ lr τ lr Proof induction 1 refine constructor eauto using ectx item refine id Qed Lemma stmt refine id Γ α Δ τ s s mc σ Γ Δ τ s s mc σ s Γ τ s α Δ s mc σ Proof induction 1 refine constructor eauto using expr refine id Qed Lemma sctx item refine id Γ α Δ τ s Es mc σ mc σ Γ Δ τ s Es mc σ mc σ Es Γ τ s α Δ Es mc σ mc σ Proof destruct 1 refine constructor eauto using stmt refine id expr refine id Qed Lemma esctx item refine id Γ α Δ τ s Ee τ lr τ lr Γ Δ τ s Ee τ lr τ lr Ee Γ τ s α Δ Ee τ lr τ lr Proof destruct 1 refine constructor eauto using stmt refine id Qed Lemma ctx item refine id Γ α Δ τ s Ek τ f τ f Γ Δ τ s Ek τ f τ f Ek Γ τ s α Δ Ek τ f τ f Proof assert os Forall2 λ o1 o2 meminj id K o1 Some o2 os os induction os auto destruct 1 refine constructor eauto using sctx item refine id expr refine id ectx refine id esctx item refine id Qed Lemma ctx refine id Γ α Δ k τ f τ f Γ Δ k τ f τ f k Γ α Δ k τ f τ f Proof induction 1 refine constructor eauto using ctx item refine id Qed Lemma direction refine id Γ α Δ d cm σ Γ Δ d cm σ d Γ α Δ d cm σ Proof destruct 1 refine constructor eauto using val refine id Qed Lemma focus refine id Γ α Δ τ s φ τ f Γ Δ τ s φ τ f φ Γ τ s α Δ φ τ f Proof destruct 1 refine constructor eauto using stmt refine id direction refine id expr refine id val refine id ectx refine id esctx item refine id vals refine id locks refine id Qed Lemma state refine id Γ α S σ f Γ Γ S σ f S Γ α S σ f Proof destruct S intros τ f eleft eauto using cmap refine id ctx refine id focus refine id Qed Lemma funenv refine id Γ α Δ δ Γ Γ Δ δ δ Γ α Δ δ Proof intros H δ Hdom g specialize Hdom g rewrite elem of dom in Hdom destruct δ g eqn auto destruct H δ g s as τ s τ naive solver eauto using stmt refine id unfold lookup env lookup fun destruct env f Γ g by destruct Hdom eauto done Qed Lemma lrval refine compose Γ α1 α2 f1 f2 Δ1 Δ2 Δ3 ν1 ν2 ν3 τ lr τ lr Γ ν1 Γ α1 f1 Δ1 Δ2 ν2 τ lr ν2 Γ α2 f2 Δ2 Δ3 ν3 τ lr ν1 Γ α1 α2 f2 f1 Δ1 Δ3 ν3 τ lr Proof destruct 2 inversion clear 1 refine constructor eauto using val refine compose ptr refine compose Qed Lemma expr refine compose Γ τ s α1 α2 f1 f2 Δ1 Δ2 Δ3 e1 e2 e3 τ lr τ lr Γ e1 Γ τ s α1 f1 Δ1 Δ2 e2 τ lr e2 Γ τ s α2 f2 Δ2 Δ3 e3 τ lr e1 Γ τ s α1 α2 f2 f1 Δ1 Δ3 e3 τ lr Proof assert es1 es2 es3 τ lrs τ lrs Forall3 λ e1 e2 τ lr e3 τ lr e2 Γ τ s α2 f2 Δ2 Δ3 e3 τ lr e1 Γ τ s α1 α2 f2 f1 Δ1 Δ3 e3 τ lr es1 es2 τ lrs es2 Γ τ s α2 f2 Δ2 Δ3 es3 τ lrs es1 Γ τ s α1 α2 f2 f1 Δ1 Δ3 es3 τ lrs intros es3 τ lrs Hes revert es3 τ lrs induction Hes inversion clear 1 constructor eauto intros He revert e3 τ lr induction He using expr refine ind intros He refine inversion He simplify type equality refine constructor eauto using locks refine compose lrval refine compose Qed Lemma exprs refine compose Γ τ s α1 α2 f1 f2 Δ1 Δ2 Δ3 es1 es2 es3 τ lrs τ lrs Γ es1 Γ τ s α1 f1 Δ1 Δ2 es2 τ lrs es2 Γ τ s α2 f2 Δ2 Δ3 es3 τ lrs es1 Γ τ s α1 α2 f2 f1 Δ1 Δ3 es3 τ lrs Proof intros Hes revert es3 τ lrs induction Hes inversion clear 1 constructor eauto using expr refine compose Qed Lemma ectx item refine compose Γ

    Original URL path: http://robbertkrebbers.nl/research/ch2o/refinement_system.html (2015-08-10)
    Open archived version from archive

  • Module refinement_preservation
    e2 e2 τ lr Γ Γ ρ2 ₕ e2 m2 e2 m2 m1 Γ α f m2 e1 Γ ρ1 2 α f m1 m2 e2 τ lr Forall2 stack item refine f m1 m2 ρ1 ρ2 f m1 e1 1 Γ ρ1 ₕ e1 m1 e1 m1 2 m1 Γ α f m2 3 e1 Γ ρ1 2 α f m1 m2 e2 τ lr 4 meminj extend f f m1 m2 is redex e1 Γ ρ1 ₕ safe e1 m1 Proof intros destruct Some dec maybe2 EAlloc e2 as τ e simplify option equality refine inversion all inv ehstep refine inversion all try by right repeat constructor inversion 1 inv ehstep left go f eauto 10 using type valid ptr type valid edestruct λ Γ f m1 m2 o1 o2 τ n mem alloc new refine Γ α f m1 m2 o1 o2 true perm full τ n as f eauto using perm full mapped perm full unshared left go f eauto refine constructor eauto 10 using addr top array refine mem alloc new index typed eapply locks refine weaken eauto using mem alloc new forward option eq 1 destruct ehstep dec Γ ρ1 e1 m1 as e1 m1 left destruct ehstep refine forward Γ α f m1 m2 m1 ρ1 ρ2 e1 e2 e1 τ lr as f m2 e2 auto destruct ehstep deterministic Γ ρ2 e2 m2 e2 m2 e2 m2 simplify equality eauto 10 right split eauto using expr refine redex inv ehstep is redex destruct 1 refine inversion all inv ehstep naive solver Qed Lemma ehsafe refine Γ α f m1 m2 ρ1 ρ2 e1 e2 τ lr Γ Γ ρ1 ₕ safe e1 m1 m1 Γ α f m2 e1 Γ ρ1 2 α f m1 m2 e2 τ lr Forall2 stack item refine f m1 m2 ρ1 ρ2 Γ ρ2 ₕ safe e2 m2 Proof destruct 2 as e1 m1 e1 m1 intros refine inversion all edestruct EVal refine inv l as eauto subst by constructor intros destruct ehstep refine forward Γ α f m1 m2 m1 ρ1 ρ2 e1 e2 e1 τ lr as auto econstructor eauto Qed Ltac invert repeat match goal with progress simplify equality H rettype match apply rettype match false inv in H subst H rettype match apply rettype match Some inv in H subst H labels erewrite stmt refine labels in H by eauto H labels erewrite stmt refine labels in H by eauto H cases erewrite stmt refine cases in H by eauto H cases erewrite stmt refine cases in H by eauto H apply EVal refine inv r in H auto destruct H as H X subst apply esctx item subst refine inv r in H destruct H as H X subst apply ectx subst refine inv r in H destruct H as H X subst apply sctx item subst refine inv r in H destruct H as H X Y first is var X is var Y fail 1 refine inversion H H

    Original URL path: http://robbertkrebbers.nl/research/ch2o/refinement_preservation.html (2015-08-10)
    Open archived version from archive

  • Module expression_eval
    ρ m Some ν2 P e2 ν2 P e1 e2 ν2 Context Pcast τ e v e Γ ρ m Some inr v P e inr v val cast ok Γ m TType τ v P cast τ e inr val cast TType τ v Context Pinsert r e1 e2 v1 v2 e1 Γ ρ m Some inr v1 P e1 inr v1 e2 Γ ρ m Some inr v2 P e2 inr v2 is Some v2 Γ r P r e1 e2 inr val alter Γ λ v1 r v2 Lemma expr eval ind e ν e Γ ρ m Some ν P e ν Proof induction e using expr ind alt intros repeat first progress simplify option equality case match eauto Qed End expr eval ind Lemma EVal expr eval Γ ρ m v v Γ ρ m Some inr v Proof done Qed Lemma EVals expr eval Γ ρ m Ω s vs length Ω s length vs Ω s mapM λ e e Γ ρ m maybe inr Ω s vs Some vs Proof rewrite empty union list L rewrite Forall2 same length induction 1 intros decompose Forall simplify option equality auto Qed Lemma Forall2 expr eval val inv Γ ρ m Ω s vs vs length Ω s length vs Forall2 λ e v e Γ ρ m maybe inr Some v Ω s vs vs vs vs Proof rewrite Forall2 same length intros H Ω vs revert vs induction H Ω vs simpl intros decompose Forall simplify option equality f equal eauto Qed Lemma expr eval typed aux Γ Δ τ s ρ m e ν τ lr Γ Γ Δ m e Γ ρ m Some ν Δ ρ ρ 2 prefix of τ s Γ Δ τ s e τ lr Γ Δ ν τ lr Proof intros H ν τ s He revert e ν H ν τ lr He apply expr eval ind Γ ρ m λ e τ lr e τ lr Prop intros repeat match goal with progress typed inversion all progress decompose Forall hyps H ρ 2 τ s i Some τ1 H2 ρ Some τ2 assert ρ 2 τ s i Some τ by apply lookup app l Some by rewrite list lookup fmap H2 H e H2 e specialize H2 H end try typed constructor eauto using val unop typed val binop typed val cast typed addr top typed cmap index typed valid addr top strict addr elt typed addr elt strict addr elt typed addr elt strict val lookup seg typed val alter const typed mem lookup typed Qed Lemma expr eval typed Γ Δ ρ m e ν τ lr Γ Γ Δ m e Γ ρ m Some ν Δ ρ Γ Δ ρ 2 e τ lr Γ Δ ν τ lr Proof intros eapply expr eval typed aux eauto Qed Lemma expr eval weaken Γ1 Γ2 Δ1 ρ1 ρ2 m1 m2 e ν τ lr Γ1 Γ1 Δ1 m1 Δ1

    Original URL path: http://robbertkrebbers.nl/research/ch2o/expression_eval.html (2015-08-10)
    Open archived version from archive