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 extraction
    extraction Require Import interpreter ExtrOcamlBasic ExtrOcamlString architectures Extraction Blacklist list Extraction parser Extracted ml interpreter interpreter all eval interpreter interpreter rand eval interpreter interpreter initial eval ilp32 llp64 lp64 Generated

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

  • Module memory_singleton
    contradict Hunmap eauto using Forall impl pbit lock mapped eapply ctree map typed eauto using pbit lock mapped pbit lock indetified eapply pbits lock valid Forall impl naive solver eauto using ctree flatten valid rewrite ctree flatten map Forall fmap eapply Forall impl naive solver Qed Lemma mem unlock singleton Γ Δ m a μ γ v τ Γ perm locked γ true mem singleton Γ Δ a μ γ v τ m mem singleton Γ Δ a μ perm unlock γ v τ mem unlock lock singleton Γ a m Proof intros w assert ctree unmapped w as Hunmap eapply ctree Forall not Forall impl eauto intros eapply perm locked mapped eauto assert τ addr type base a by eauto using addr is obj type subst unfold mem unlock cmap singleton lock singleton destruct decide as simplify type equality f equal exists ctree map pbit unlock w split ands eauto by rewrite to val ctree map by done assert ref object offset Γ addr ref Γ a bit size of Γ addr type base a bit size of Γ addr type object a eauto using ref object offset size addr typed ref typed erewrite merge singleton by done erewrite ctree flatten length to of bools by eauto using ctree singleton typed addr typed ref typed assert γ b pbit K β sep valid γ b sep unmapped pbit unlock if γ b β sep unmapped γ b intros eauto using pbit unlock mapped erewrite ctree merge singleton addr object offset alt addr is obj ref byte resize ge associative L drop app alt take app alt by eauto using addr typed ref typed pbit unlock if empty replicate length by erewrite ctree merge map pbit unlock by rewrite zip with replicate r by auto eauto using pbit unlock if empty eapply ctree map typed eauto using pbit unlock mapped pbit valid sep valid eapply Forall fmap Forall impl pbit unlock valid eauto using ctree flatten valid by intros simplify equality rewrite ctree flatten map Forall fmap eapply Forall impl naive solver cut sep valid γ auto using perm unlock empty assert length ctree flatten w 0 erewrite ctree flatten length by eauto eauto using bit size of ne 0 addr typed type valid assert Γ Δ ctree flatten w as Hw by eauto using ctree flatten valid destruct Hw decompose Forall hyps eapply pbit valid sep valid eauto rewrite elem of equiv empty L intros Htrue apply Htrue addr object offset Γ a rewrite elem of of bools lookup app r replicate length Nat sub diag lookup replicate by auto eauto using bit size of pos addr typed type valid Qed Lemma mem unlock all singleton Γ Δ m a μ γ v τ Γ perm locked γ true mem singleton Γ Δ a μ γ v τ m mem singleton Γ Δ a μ perm unlock γ v τ mem unlock all m Proof intros erewrite mem unlock all spec mem locks singleton by eauto eauto using mem unlock singleton Qed Lemma mem unlock all singleton unlocked Γ Δ m a μ γ v τ Γ perm locked γ false mem singleton Γ Δ a μ γ v τ m mem singleton Γ Δ a μ γ v τ mem unlock all m Proof intros by erewrite mem unlock all spec mem locks singleton empty mem unlock empty by eauto Qed Lemma mem alloc singleton Γ Δ m o μ γ v τ Γ Γ Δ m Δ o τ index alive Δ o o dom indexset m sep valid γ sep unmapped γ Γ Δ v τ m mem alloc Γ o μ γ v m m m m m mem singleton Γ Δ addr top o τ μ γ freeze true v τ m Proof intros exists cmap singleton Γ addr top o τ μ of val Γ replicate bit size of Γ type of v γ v split ands rewrite sep left id m at 1 by eauto using cmap valid sep valid by rewrite mem alloc union by done simplify type equality assert Γ Δ of val Γ replicate bit size of Γ τ γ v τ apply of val typed eauto using Forall replicate replicate length eapply cmap singleton disjoint l eauto using addr top typed addr top is obj addr top strict val typed type valid mem alloc index typed cmap valid sep valid ctree Forall not of val mapped Forall replicate eauto using mem alloc memenv valid val typed type valid cmap valid memenv valid simplify type equality exists of val Γ replicate bit size of Γ τ γ v split ands eauto using of val typed addr top typed addr top is obj addr top strict val typed type valid mem alloc index typed Forall replicate sep unmapped empty alt to of val eq sym erewrite ctree flatten of val zip with replicate l by by erewrite val flatten length by eauto eauto by apply Forall fmap Forall true Qed Lemma mem alloc singleton alt Γ Δ m o μ γ v τ Γ Γ Δ m Δ o None sep valid γ sep unmapped γ Γ Δ v τ frozen v m mem alloc Γ o μ γ v m m m m m mem singleton Γ o τ false Δ addr top o τ μ γ v τ m Proof intros Hfrozen setoid rewrite Hfrozen at 2 assert Δ o τ false Δ by by apply insert subseteq apply mem alloc singleton eauto using mem alloc index typed cmap dom None mem alloc index alive val typed weaken memenv subseteq forward cmap valid weaken mem alloc memenv valid val typed type valid cmap valid memenv valid Qed Lemma mem free singleton Γ Δ m o a μ γ v τ mem singleton Γ Δ a μ γ v τ m addr index a o cmap erase mem free o m Proof intros w sep unfold f equal apply map empty intros o by destruct decide o addr index

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

  • Module assertions
    with δ1 n eauto with lia eapply IH assert weaken with S n eauto with lia Qed Lemma assert later weaken Γ δ P P Γ δ P A Proof intros Γ1 Δ ρ δ1 n m n eapply assert weaken with n eauto with lia Qed Lemma assert later impl Γ δ P Q P Q A Γ δ P Q A Proof intros Γ1 Δ1 δ1 ρ n1 m HPQ Γ2 Δ2 δ2 n2 n3 eapply HPQ eauto lia Qed Lemma assert later and Γ δ P Q P Q A Γ δ P Q A Proof solve eauto Qed Lemma assert later or Γ δ P Q P Q A Γ δ P Q A Proof solve eauto Qed Lemma assert later forall A Γ δ P A assert K x P x A Γ δ x P x A Proof solve eauto Qed Lemma assert later exists A Γ δ P A assert K x P x A Γ δ x P x A Proof solve eauto Qed Separation logic connectives Global Instance Proper impl Γ δ assert Prop Proof solve eauto Qed Global Instance Proper iff Γ δ assert Prop Proof solve eauto Qed Global Instance Proper Γ δ Γ δ Γ δ A Proof solve ltac eauto 15 using cmap valid subseteq sep union subseteq l sep union subseteq r Qed Global Instance Proper flip Γ δ flip Γ δ flip Γ δ A Proof solve ltac eauto 15 using cmap valid subseteq sep union subseteq l sep union subseteq r Qed Global Instance Proper Γ δ Γ δ Γ δ A Proof by intros split apply Proper Γ δ Γ δ Γ δ A Qed Global Instance Proper Forall2 Γ δ Γ δ assert sep list Proof induction 1 simpl done by apply Proper Γ δ Γ δ Γ δ A Qed Global Instance Proper flip Γ δ Γ δ Γ δ A Proof intros Γ1 δ1 P1 P2 HP Q1 Q2 HQ Γ2 Δ1 δ2 ρ n1 m HPQ Γ3 Δ2 δ3 n2 apply HQ eauto 10 using indexes valid weaken cmap union valid 2 Qed Global Instance Proper Γ δ Γ δ Γ δ A Proof by intros split apply Proper flip Γ δ Γ δ Γ δ A Qed Global Instance Commutative Γ δ A Proof intros Γ δ P Q Γ1 Δ δ1 ρ n m m1 m2 exists m2 m1 rewrite sep commutative by auto auto Qed Global Instance Commutative Γ δ A Proof split by rewrite commutative A Qed Global Instance LeftId Γ δ emp A A Proof intros δ Γ intros P split intros Γ1 Δ δ1 ρ n m m1 m2 rewrite sep left id by auto auto intros Γ1 Δ δ1 ρ n m eexists m rewrite sep left id sep disjoint equiv empty sep disjoint list singleton by eauto solve eauto Qed Global Instance RightId Γ δ emp A A Proof intros by rewrite commutative left id Qed Global Instance LeftAbsorb Γ δ False A A Proof red solve eauto Qed Global Instance RightAbsorb Γ δ False A A Proof red solve eauto Qed Global Instance Associative Γ δ A Proof intros Γ δ assert P Q R P Q R A Γ δ P Q R A intros P Q R Γ1 Δ δ1 ρ n m3 m1 m2 exists m1 m2 m3 rewrite sep associative by auto split ands auto exists m2 m3 auto assert P Q R P Q R A Γ δ P Q R A intros P Q R Γ1 Δ δ1 ρ n m1 m2 m3 exists m1 m2 m3 rewrite sep associative by auto split ands auto exists m1 m2 auto split auto Qed Lemma assert Prop impl Γ δ P Q Prop P Q A Γ δ P Q A Proof solve eauto Qed Lemma assert Prop not Γ δ P Prop P A Γ δ P A Proof solve eauto Qed Lemma assert Prop and Γ δ P Q Prop P Q A Γ δ P Q A Proof solve eauto Qed Lemma assert Prop or Γ δ P Q Prop P Q A Γ δ P Q A Proof solve eauto Qed Lemma assert Prop l Γ δ P Prop Q P P Q A Γ δ Q Proof intros assert P True as by by split intros by rewrite left id emp A Qed Lemma assert Prop r Γ δ P Prop Q P Q P A Γ δ Q Proof intros by rewrite commutative A assert Prop l Qed Lemma assert Prop intro l Γ δ P Prop Q R P Q Γ δ R P Q A Γ δ R Proof intros HQR Γ1 Δ δ1 ρ n Hm m1 m2 rewrite sep left id in Hm by auto by apply HQR Qed Lemma assert Prop intro r Γ δ P Prop Q R P Q Γ δ R Q P A Γ δ R Proof rewrite commutative A by apply assert Prop intro l Qed Lemma assert Prop True Γ δ P Q Prop P Γ δ Q True A P Γ δ Q P A Proof intros HPQ Γ1 Δ δ1 ρ n m HP destruct HPQ Γ1 Δ δ1 ρ n m as m1 m2 auto rewrite sep left id in HP by auto solve eauto Qed Lemma assert sep preserving Γ δ P P Q Q P Γ δ P Q Γ δ Q P Q A Γ δ P Q A Proof intros HP HQ by rewrite HP HQ Qed Lemma assert sep exist A Γ δ P Q A assert K P x Q x A Γ δ x P Q x A Proof solve eauto Qed Lemma assert exist sep A Γ δ P A assert K Q x P x Q A Γ δ x P x Q A Proof solve eauto Qed Lemma assert wand intro Γ δ P Q R P Q A Γ δ R P Γ δ Q R A Proof intros HPQR Γ1 Δ1 ρ δ1 n1 m1 HP Γ2 Δ2 δ2 n2 m2 HQ apply HPQR eauto using indexes valid weaken cmap union valid 2 exists m1 m2 split ands eauto using assert weaken sep commutative Qed Lemma assert wand elim Γ δ P Q P Q P A Γ δ Q Proof intros Γ1 Δ1 ρ δ1 n m1 m2 HQ rewrite sep commutative by auto eapply HQ eauto using cmap valid subseteq sep union subseteq l sep union subseteq r Qed Global Instance LeftId Γ δ emp A A Proof intros Γ P split rewrite right id A apply assert wand elim apply assert wand intro by rewrite right id A Qed Lemma assert Forall holds 2 Ps list assert K Γ Δ δ ρ ms n ms Forall2 λ P assert K m assert holds P Γ Δ δ ρ n m Ps ms assert holds Π Ps A Γ Δ δ ρ n ms Proof intros Hms HPs revert Hms induction HPs solve eauto Qed Lemma assert Forall holds Ps list assert K Γ Δ δ ρ n m assert holds Π Ps A Γ Δ δ ρ n m ms m ms ms Forall2 λ P assert K m assert holds P Γ Δ δ ρ n m Ps ms Proof split naive solver eauto using assert Forall holds 2 revert m induction Ps as P Ps IH intros m eexists by repeat constructor intros m1 m2 destruct IH m2 as ms trivial exists m1 ms auto Qed Lemma assert Forall holds vec vn Ps vec assert K vn Γ Δ δ ρ n m assert holds Π Ps A Γ Δ δ ρ n m ms vec vn m ms ms i assert holds Ps i Γ Δ δ ρ n ms i Proof rewrite assert Forall holds split intros ms Hms assert vn length ms subst vn by erewrite Forall2 length vec to list length by eauto exists list to vec ms rewrite vec to list of list by rewrite vec to list of list ms Forall2 vlookup in Hms intros ms exists ms by rewrite Forall2 vlookup Qed Lemma assert memext l Γ δ P Q MemExt P P Q A Γ δ P Proof intros transitivity P True A auto using assert sep preserving assert True intro Qed Lemma assert memext r Γ δ P Q MemExt P Q P A Γ δ P Proof rewrite commutative A apply assert memext l Qed Lemma assert memext l Γ δ P Q R MemExt R P Γ δ R P Q A Γ δ R Proof intros rewrite assert memext l R by done eauto using assert sep preserving Qed Lemma assert memext r Γ δ P Q R MemExt R Q Γ δ R P Q A Γ δ R Proof rewrite commutative A apply assert memext l Qed Global Instance assert eval memext e ν MemExt e ν A Proof intros Γ δ Γ Δ δ ρ n m Hm m1 m2 τ lr exists τ lr split auto rewrite cmap union valid in Hm by auto destruct Hm eapply expr eval subseteq with m1 eauto using sep union subseteq l Qed Lemma assert int typed eval Γ δ P x τ i int typed x τ i P Γ δ intV τ i x inr intV τ i x A Proof intros Γ Δ ρ δ n m eexists inr intT τ i T split auto using lockset empty valid Qed Lemma assert eval int typed Γ δ e x τ i e inr intV τ i x A Γ δ int typed x τ i True A Proof intros Γ Δ δ ρ n m τ lr assert Γ Δ inr intV τ i x τ lr by eauto using expr eval typed assert sep valid m by eauto typed inversion all exists mem K m eauto 9 using sep left id eq sym Qed Lemma assert eval int typed Γ δ e x τ i e inr intV τ i x A Γ δ int typed x τ i e inr intV τ i x A Proof eauto using assert Prop True assert eval int typed Qed Hint Extern 1 unop typed constructor Hint Extern 1 base unop typed constructor Lemma assert eval int unop Γ δ op e x τ i int unop ok op x τ i e inr intV τ i x A Γ δ op e inr intV int unop type of op τ i int unop op x τ i A Proof intros Γ Δ δ ρ n m τ lr assert Γ Δ inr intV τ i x τ lr by eauto using expr eval typed typed inversion all simplify option equality eauto 20 using lockset empty valid Qed Lemma assert eval int unop Γ δ P op e x y τ i σ i P Γ δ e inr intV τ i x A int unop type of op τ i σ i int unop ok op x τ i int unop op x τ i y P Γ δ op e inr intV σ i y A Proof intros subst rewrite assert eval int unop by eauto eauto Qed Hint Extern 1 binop typed constructor Hint Extern 1 base binop typed constructor Lemma assert eval int binop Γ δ op e1 e2 x1 x2 τ i1 τ i2 int binop ok op x1 τ i1 x2 τ i2 e1 inr intV τ i1 x1 e2 inr intV τ i2 x2 A Γ δ e1 op e2 inr intV int binop type of op τ i1 τ i2 int binop op x1 τ i1 x2 τ i2 A Proof intros Hok Γ Δ δ ρ n m τ lr1 τ lr2 assert Γ Δ inr intV τ i1 x1 τ lr1 by eauto using expr eval typed assert Γ Δ inr intV τ i2 x2 τ lr2 by eauto using expr eval typed typed inversion all simplify option equality eauto 20 using lockset empty valid Qed Lemma assert eval int binop Γ δ P op e1 e2 x1 x2 y τ i1 τ i2 σ i P Γ δ e1 inr intV τ i1 x1 A P Γ δ e2 inr intV τ i2 x2 A σ i int binop type of op τ i1 τ i2 int binop ok op x1 τ i1 x2 τ i2 int binop op x1 τ i1 x2 τ i2 y P Γ δ e1 op e2 inr intV σ i y A Proof intros subst rewrite assert eval int binop by eauto eauto using assert and intro Qed Lemma assert eval int arithop Γ δ P op e1 e2 x1 x2 y τ i1 τ i2 σ i P Γ δ e1 inr intV τ i1 x1 A P Γ δ e2 inr intV τ i2 x2 A σ i int promote τ i1 int promote τ i2 int pre arithop ok op int pre cast σ i x1 int pre cast σ i x2 σ i int pre arithop op int pre cast σ i x1 int pre cast σ i x2 σ i y P Γ δ e1 ArithOp op e2 inr intV σ i y A Proof intros rewrite assert Prop True by rewrite assert eval int typed e1 auto apply assert Prop intro l intros rewrite assert Prop True by rewrite assert eval int typed e2 auto apply assert Prop intro l intros eapply assert eval int binop eauto by apply int arithop ok more unfold int binop by rewrite int arithop spec by auto Qed Hint Extern 1 cast typed constructor Hint Extern 1 base cast typed constructor Lemma assert eval int cast Γ δ e x τ i σ i int cast ok σ i x e inr intV τ i x A Γ δ cast intT σ i T e inr intV σ i int cast σ i x A Proof intros Γ Δ δ ρ n m τ lr assert Γ Δ inr intV τ i x τ lr by eauto using expr eval typed typed inversion all simplify option equality eauto 20 using lockset empty valid TBase valid TInt valid Qed Lemma assert eval int cast Γ δ P e x τ i σ i y P Γ δ e inr intV τ i x A int cast ok σ i x int cast σ i x y P Γ δ cast intT σ i T e inr intV σ i y A Proof intros subst rewrite assert eval int cast by eauto eauto Qed Lemma assert eval int cast self Γ δ P e x τ i P Γ δ e inr intV τ i x A P Γ δ cast intT τ i T e inr intV τ i x A Proof intros HP rewrite HP assert eval int typed eauto using assert Prop intro l assert eval int cast int cast ok self int cast self Qed Lemma assert eval singleton l Γ δ a e μ γ τ a μ γ e τ A Γ δ a inl a A Proof intros Γ Δ δ ρ n m a v eexists inl TType τ simplify option equality eauto Qed Lemma assert eval singleton r Γ δ e v μ γ τ e μ γ v τ A Γ δ v inr v A Proof intros Γ Δ δ ρ n m a v eexists inr τ simplify option equality eauto Qed Lemma assert singleton l Γ δ e1 e2 μ γ τ e1 μ γ e2 τ A Γ δ a e1 inl a emp a μ γ e2 τ A Proof split intros Γ Δ δ ρ n m a v exists Ptr a assert sep valid m by eauto using cmap valid sep valid eexists m split ands simplify option equality eauto 20 using sep left id eq sym lockset empty valid mem singleton typed addr typed intros Γ Δ δ ρ n m Hm m τ lr a v simplify option equality exists a v rewrite sep left id in Hm by auto split ands auto cut τ lr inl TType τ intros auto typed inversion all apply typed unique Γ Δ inl Ptr a eauto using expr eval typed cmap empty valid cmap valid memenv valid Qed Lemma assert singleton l 2 Γ δ e1 e2 μ γ a τ e1 inl a emp a μ γ e2 τ A Γ δ e1 μ γ e2 τ A Proof rewrite assert singleton l e1 solve eauto Qed Lemma assert singleton l Γ δ e μ γ τ e μ γ τ A Γ δ a e inl a emp a μ γ τ A Proof setoid rewrite assert singleton l Γ δ e by setoid rewrite assert sep exist Γ δ rewrite assert exist exist Qed Lemma assert singleton l 2 Γ δ e μ γ a τ e inl a emp a μ γ τ A Γ δ e μ γ τ A Proof rewrite assert singleton l e solve eauto Qed Lemma assert singleton int typed Γ δ e μ γ z τ i e μ γ intV τ i z intT τ i A Γ δ int typed z τ i True A Proof rewrite assert eval singleton r apply assert eval int typed Qed Lemma assert singleton int typed Γ δ e μ γ z τ i e μ γ intV τ i z intT τ i A Γ δ int typed z τ i e μ γ intV τ i z intT τ i A Proof by apply assert Prop True assert singleton int typed Qed Lemma assert expr lift Γ δ e ν vars e e ν A Γ δ e ν A Proof split intros Γ Δ δ ρ n m τ lr exists τ lr split by apply expr typed var free with tail ρ 2 expr typed lift erewrite expr eval var free

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

  • Module axiomatic_graph
    S n k φ m red rcstep Γ δ ρ State k φ m Proof by inversion 4 subst eauto Qed End basics The predicate ax can be composed This property is used to prove the structural Hoare rules Definition ax compose diagram A B F ax frame cond K A G ax frame cond K B Γ env K k2 ctx K Δ δ k1 n φ m m b Γ Δ δ Γ Δ m frame G Γ Δ δ k1 k2 n φ m m b a 1 frame F Γ Δ δ k1 n φ m m a 2 Δ k1 φ m2 m2 Γ Δ m2 Δ ₘ Δ unframe F Γ Δ δ k1 n φ m2 m2 a unframe G Γ Δ δ k1 k2 n φ m2 m2 b Lemma ax compose diagram diag A F ax frame cond K A Γ ax compose diagram F F Γ Proof intros Δ δ k1 n φ m m a rewrite right id L exists a split auto by intros rewrite right id L Qed Lemma ax compose A B F ax frame cond K A G ax frame cond K B P Q ax assert K Γ δ Δ n φ ρ k1 k2 m Γ Γ Δ δ ax compose diagram F G Γ k2 Γ Δ m ax graph F P Γ δ Δ rlocals ρ k2 n k1 φ m Δ n φ m ax assert holds P Γ Δ δ rlocals ρ k2 n φ m Γ Δ m Δ ₘ Δ n n ax graph G Q Γ δ Δ ρ n k2 φ m ax graph G Q Γ δ Δ ρ n k1 k2 φ m Proof intros revert Δ m k1 φ induction n as n IH using lt wf ind intros apply ax O intros Δ m k1 φ HF Hax Hnext inversion Hax as Hred Hstep subst eauto apply ax further alt intros Δ n m b destruct HF Δ δ k1 S n φ m m b as a eauto using funenv valid weaken split eauto using rcred app intros k φ m p destruct cstep app suffix of Γ δ ρ k1 k2 φ m State k φ m as k3 simplify equality eauto feed inversion Hstep Δ n m a State k3 φ m as Δ n k φ m2 m2 b subst auto using rcstep app inv econstructor eauto 10 using unframe valid funenv valid weaken Qed Lemma ax compose cons A B F ax frame cond K A G ax frame cond K B P Q ax assert K Γ δ Δ n φ ρ Ek m Γ Γ Δ δ ax compose diagram F G Γ Ek Γ Δ m ax graph F P Γ δ Δ rlocals ρ Ek n φ m Δ n φ m ax assert holds P Γ Δ δ rlocals ρ Ek n φ m Γ Δ m Δ ₘ Δ n

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

  • Module axiomatic
    A s S Q A at level 74 δ at next level format Γ δ ₛ P s Q The Hoare judgment for expressions The interpretation of the expression judgment is defined similarly as the interpretation of the judgment for statements At the start we require both the expression and the memory to be lock free In the end the locks in the memory should exactly match the annotated locations in the final expression that remain to be unlocked The latter is important as an unlock operation at a sequence point thereby corresponds to unlocking everything Inductive ax expr frame K Set Set InExpr mf mA mem K InFun mf mem K Arguments InExpr Arguments InFun Inductive ax expr cond frame Env K ρ stack K A assert K Γ env K Δ memenv K δ funenv K k ctx K n nat φ focus K m m mem K ax expr frame K Prop ax frame in expr mA mf m m mf mA Γ Δ mf Γ Δ mA m mf mA k cmap erased mA mem locks mA assert holds A Γ Δ δ ρ n mA ax expr cond frame ρ A Γ Δ δ k n φ m m InExpr mf mA ax frame in fun mf m m mf Γ Δ mf m mf k ax expr cond frame ρ A Γ Δ δ k n φ m m InFun mf Inductive ax expr cond unframe Env K ρ stack K A assert K Γ env K Δ memenv K δ funenv K k ctx K n nat φ focus K m m mem K ax expr frame K Prop ax unframe expr to expr mA mf m m mf mA m mf mA k ax expr cond unframe ρ A Γ Δ δ k n φ m m InExpr mf mA ax unframe fun to expr mA mf m m mf mA m mf mA k cmap erased mA mem locks mA assert holds A Γ Δ δ ρ n mA ax expr cond unframe ρ A Γ Δ δ k n φ m m InFun mf ax unframe expr to fun m mA mf m m mA m m mf mA m mf mA k ax expr cond unframe ρ A Γ Δ δ k n φ m m InExpr mf mA ax unframe fun to fun mf m m mf m mf k ax expr cond unframe ρ A Γ Δ δ k n φ m m InFun mf Program Definition ax expr cond EnvSpec K ρ stack K A assert K ax frame cond K ax expr frame K frame ax expr cond frame ρ A unframe ax expr cond unframe ρ A Next Obligation intros ρ A Γ Δ δ k n φ m m destruct 1 subst auto using cmap union valid 2 Qed Next Obligation intros ρ A Γ Δ δ k n φ m m destruct 1 subst rewrite cmap union valid intuition Qed Definition ax expr invariant Env K A assert K Γ env K Δ memenv K δ funenv K ρ stack K n nat m mem K mA mA m Γ Δ mA cmap erased mA mem locks mA assert holds A Γ Δ δ ρ n mA Inductive ax expr post Env K Q lrval K assert K τ lr lrtype K Γ env K Δ memenv K δ funenv K ρ stack K n nat focus K mem K Prop mk ax expr post ν Ω m Γ Δ ν τ lr mem locks m Ω assert holds Q ν Γ Δ δ ρ n cmap erase m ax expr post Q τ lr Γ Δ δ ρ n Expr Ω ν m Program Definition ax expr post EnvSpec K Q lrval K assert K τ lr lrtype K ax assert K ax assert holds ax expr post Q τ lr Next Obligation intros Q τ lr Γ1 Γ2 Δ1 Δ2 δ1 δ2 ρ n φ m destruct 1 constructor eauto using assert weaken cmap erase valid lrval typed weaken Qed Next Obligation intros Q τ lr Γ Δ δ ρ n φ m m d m p inv rcstep Qed Definition ax expr EnvSpec K Γ env K δ funenv K A P assert K e expr K Q lrval K assert K Prop Γ Δ δ n ρ m τ lr Γ Γ Γ δ δ Γ Δ δ Γ Δ m mem locks m Γ Δ ρ 2 e τ lr locks e Δ ρ ax expr invariant A Γ Δ δ ρ n m assert holds P Γ Δ δ ρ n cmap erase m ax graph ax expr cond ρ A ax expr post Q τ lr Γ δ Δ ρ n Expr e m Instance Params ax expr 5 Notation Γ δ A ₑ P e Q ax expr Γ δ A A P A e Q A at level 74 δ at next level A at next level format Γ δ A ₑ P e Q Function specifications Inductive fassert K Set Env K FAssert fcommon Type fpre fcommon list val K assert K fpost fcommon list val K val K assert K fpre stack indep c vs StackIndep fpre c vs fpost stack indep c vs v StackIndep fpost c vs v Arguments fcommon Arguments fpre Arguments fpost Existing Instance fpre stack indep Existing Instance fpost stack indep Inductive ax fun post Env K f funname τ type K P val K assert K Γ env K Δ memenv K δ funenv K ρ stack K n nat focus K mem K Prop mk ax fun post v m Γ Δ v τ mem locks m assert holds P v Γ Δ δ ρ n cmap erase m ax fun post f τ P Γ Δ δ ρ n Return f v m Program Definition ax fun post EnvSpec K f funname τ type K P val K assert K ax assert K

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

  • Module axiomatic_expressions
    weaken destruct HA Γ Δ δ n mA as τ lr clear HA eauto 4 using assert weaken indexes valid weaken funenv valid weaken rewrite cmap erase disjoint le auto destruct τ lr as τ p simplify option equality typed inversion all simplify type equality assert ptr alive m mf mA p destruct p as a auto apply cmap subseteq index alive with mA cmap erase m auto rewrite sep commutative mA by auto apply sep preserving l auto using sep union subseteq l transitive cmap erase subseteq l split solve rcred intros p inv rcstep p inv ehstep exfalso eauto with cstep apply mk ax next with Δ m auto constructor auto esolve elem of apply ax done constructor eauto using ptr typed weaken assert weaken indexes valid weaken Qed Lemma ax rofl Γ δ A P Q1 Q2 e p Q1 inl p Γ δ Q2 inr ptrV p Γ δ A ₑ P e Q1 Γ δ A ₑ P e Q2 Proof intros HQ Hax Γ Δ δ n ρ m He1e2 He assert τ p τ lr inr τ p Γ Δ ρ 2 e inl τ p as τ p by typed inversion all eauto clear He1e2 apply ax expr compose 1 Γ δ A Q1 Δ DCRofL e ρ n m inl τ p auto esolve elem of clear dependent m intros Δ n a m typed inversion all apply ax further intros solve rcred intros Δ n S Hframe p inversion clear Hframe as mA mf simplify equality simplify mem disjoint hyps inv rcstep p inv ehstep exfalso eauto with cstep apply mk ax next with Δ m auto constructor auto esolve elem of apply ax done constructor eauto 7 using ptr typed weaken apply HQ eauto using assert weaken indexes valid weaken funenv valid weaken Qed Lemma ax load Γ δ A P Q1 Q2 e p Q1 inl p Γ δ v Q2 inr v A load p inr v A Γ δ A ₑ P e Q1 Γ δ A ₑ P load e Q2 Proof intros HQ Hax Γ Δ δ n ρ m τ HA HP typed inversion all apply ax expr compose 1 Γ δ A Q1 Δ DCLoad e ρ n m inl TType τ auto esolve elem of clear dependent m intros Δ n p m typed inversion all apply ax further alt intros Δ n frame Hframe inversion clear Hframe as mA mf clear frame simplify equality destruct HQ p Γ Δ δ ρ n cmap erase m as v HA eauto using indexes valid weaken funenv valid weaken assert mA cmap erase m rewrite cmap erase disjoint le auto destruct HA Γ Δ δ n mA as τ lr clear HA eauto 4 using assert weaken indexes valid weaken funenv valid weaken destruct p as a τ lr as τ simplify option equality typed inversion all assert mA cmap erase m m mf mA rewrite sep commutative mA by auto apply sep preserving l auto using sep union subseteq l transitive cmap erase subseteq l assert mA cmap erase m rewrite cmap erase disjoint le auto assert m mf mA Γ a Some v apply mem lookup subseteq with Δ mA cmap erase m auto assert mem forced Γ a m mf mA apply mem forced subseteq with Δ mA cmap erase m eauto split solve rcred intros S p inv rcstep p inv ehstep simplify equality exfalso eauto with cstep rewrite mem forced force by auto apply mk ax next with Δ m simpl auto constructor auto assert Γ Δ m mf mA by eauto apply ax done constructor eauto using mem lookup typed assert weaken indexes valid weaken addr typed weaken Qed Definition assert assign p ptr K v val K ass assign τ type K va v val K assert K match ass with Assign cast τ v inr va cast τ v inr v PreOp op cast τ load p op v inr va cast τ load p op v inr v PostOp op cast τ load p op v inr va load p inr v end A Lemma ax assign Γ δ A P1 P2 Q1 Q2 Q ass e1 e2 μ γ τ Some Writable perm kind γ p v Q1 inl p Q2 inr v A Γ δ va v p μ γ τ p μ perm lock γ freeze true va τ Q inr v A assert assign p v ass τ va v A Γ δ A ₑ P1 e1 Q1 Γ δ A ₑ P2 e2 Q2 Γ δ A ₑ P1 P2 e1 ass e2 Q Proof intros H γ HQ Hax1 Hax2 Γ Δ δ n ρ m τ1 Hlock He HP typed inversion all assert Some Readable perm kind γ by by transitivity Some Writable assert τ2 Γ Δ ρ 2 e1 inl TType τ1 Γ Δ ρ 2 e2 inr τ2 assign typed τ1 τ2 ass as τ2 by typed inversion all eauto clear He destruct HP as m1 m2 Hm12 Hm12 destruct cmap erase union inv m m1 m2 as m1 m2 auto simplify mem disjoint hyps clear Hm12 Hm12 rewrite mem locks union in Hlock by auto simpl in decompose empty apply ax expr compose 2 Γ δ A Q1 Q2 Δ DCAssign ass e1 e2 ρ n m1 m2 inl TType τ1 inr τ2 eauto using ax expr invariant weaken sep union subseteq l sep union subseteq r esolve elem of esolve elem of clear dependent m1 m2 intros Δ n p v m1 m2 typed inversion all apply ax further alt intros Δ n frame Hframe inversion clear Hframe as mA mf clear frame simplify equality destruct HQ p v Γ Δ δ ρ n cmap erase m1 m2 as va v m1 m2 a va HQ Hass eauto 6 using indexes valid weaken funenv valid weaken clear HQ rewrite cmap erase union exists cmap erase m1 cmap erase m2 split ands auto by rewrite cmap erase disjoint le destruct cmap erase union inv l m1 m2 m1 m2 as m2 Hm Hm auto rewrite Hm in simplify option equality typed inversion all assert TType τ TType τ1 simplify equality eapply typed unique with Γ Δ a eauto simplify mem disjoint hyps assert mem writable Γ a m1 m2 mf mA eapply mem writable subseteq with Δ m1 eauto using mem writable singleton sep union subseteq l transitive sep union subseteq l assert assign sem Γ m1 m2 mf mA a v ass va v clear HQ assert mA cmap erase m1 m2 m1 m2 mf mA rewrite sep commutative mA by auto apply sep preserving l auto using sep union subseteq l transitive cmap erase subseteq l assert mA cmap erase m1 m2 rewrite cmap erase disjoint le auto eapply assign sem subseteq with Δ mA cmap erase m1 m2 τ1 τ2 eauto 15 using addr typed weaken val typed weaken destruct ass destruct Hass Γ Δ δ n mA as eauto 4 using assert weaken indexes valid weaken funenv valid weaken clear Hass simplify option equality econstructor simplify type equality eauto clear Hass split solve rcred intros S p inv rcstep p inv ehstep simplify equality exfalso eauto 6 with cstep match goal with Hass assign sem m va v destruct assign sem deterministic Γ m a v ass va va v v auto subst clear Hass end assert Γ Δ va τ1 Γ Δ v τ1 as eapply assign preservation m1 m2 mf mA eauto using addr typed weaken val typed weaken assert a va Γ m1 m2 mf mA by rewrite mem insert disjoint le by eauto using mem writable singleton addr typed weaken assert Γ Δ a va Γ m1 eauto using mem insert valid mem writable singleton addr typed weaken assert mem writable Γ a a va Γ m1 eauto 6 using mem insert writable mem writable singleton addr typed weaken assert mem lock Γ a a va Γ m1 m2 mf mA by rewrite mem lock disjoint le by eauto using addr typed weaken assert mem locks mem lock Γ a a va Γ m1 m2 lock singleton Γ a mem locks m1 mem locks m2 erewrite mem locks union mem locks lock mem locks insert by eauto using mem writable singleton addr typed weaken rewrite associative L mem locks union Hm mem locks union by auto clear solve elem of rewrite sep associative m1 by auto erewrite mem insert union mem lock union by eauto using mem writable singleton addr typed weaken rewrite sep associative by auto apply mk ax next with Δ mem lock Γ a a va Γ m1 m2 simpl auto constructor auto by apply reflexive eq rewrite sep associative by auto auto using mem lock valid apply ax done constructor auto rewrite cmap erase union mem erase lock mem erase insert cmap erased spec by done eapply HQ rewrite cmap erase disjoint le eauto using cmap erase valid mem lock valid funenv valid weaken exists a freeze true va split ands eauto using addr typed weaken val typed weaken val typed freeze eauto using mem lock singleton mem insert singleton mem singleton weaken Qed Lemma ax eltl Γ δ A P Q1 Q2 e rs p Q1 inl p Γ δ p Q2 inl p A p rs inl p A Γ δ A ₑ P e Q1 Γ δ A ₑ P e rs Q2 Proof intros HQ Hax Γ Δ δ n ρ m σ He typed inversion all assert σ τ σ TType σ Γ Δ ρ 2 e inl TType τ Γ rs τ σ as τ σ by typed inversion all eauto clear He apply ax expr compose 1 Γ δ A Q1 Δ DCEltL rs e ρ n m inl TType σ auto esolve elem of clear dependent m intros Δ n p m typed inversion all apply ax further alt intros Δ n frame Hframe inversion clear Hframe as mA mf clear frame simplify equality simplify mem disjoint hyps destruct HQ p Γ Δ δ ρ n cmap erase m as a HA eauto using indexes valid weaken funenv valid weaken destruct HA Γ Δ δ n mA as τ lr clear HA eauto 4 using assert weaken indexes valid weaken funenv valid weaken rewrite cmap erase disjoint le auto destruct τ lr as τ simplify option equality typed inversion all split solve rcred intros S p inv rcstep p inv ehstep exfalso eauto with cstep apply mk ax next with Δ m auto constructor auto esolve elem of apply ax done constructor eauto using assert weaken addr typed weaken indexes valid weaken addr elt typed addr elt strict Qed Lemma ax eltr Γ δ A P Q1 Q2 e rs v Q1 inr v Γ δ v Q2 inr v A v rs inr v A Γ δ A ₑ P e Q1 Γ δ A ₑ P e rs Q2 Proof intros HQ Hax Γ Δ δ n ρ m σ He typed inversion all assert τ Γ Δ ρ 2 e inr τ Γ rs τ σ as τ by typed inversion all eauto clear He apply ax expr compose 1 Γ δ A Q1 Δ DCEltR rs e ρ n m inr τ auto esolve elem of clear dependent m intros Δ n v m typed inversion all apply ax further alt intros Δ n Hframe inversion clear Hframe as mA mf simplify equality simplify mem disjoint hyps destruct HQ v Γ Δ δ ρ n cmap erase m as v HA eauto using indexes valid weaken funenv valid weaken destruct HA Γ Δ δ n mA as τ lr clear HA eauto 4 using assert weaken indexes valid weaken funenv valid weaken rewrite cmap erase disjoint le auto destruct τ lr as τ simplify option equality typed inversion all split solve rcred intros S p inv rcstep p inv ehstep simplify option equality exfalso eauto with cstep apply mk ax next with Δ m auto constructor auto esolve elem of apply ax done constructor eauto using assert weaken indexes valid weaken val typed weaken val lookup seg typed Qed Lemma ax insert Γ δ A P1 P2 Q1 Q2 R e1 e2 r v1 v2 Q1 inr v1 Q2 inr v2 A Γ δ v R inr v A r v1 v2 inr v A Γ δ A ₑ P1 e1 Q1 Γ δ A ₑ P2 e2 Q2 Γ δ A ₑ P1 P2 r e1 e2 R Proof intros HQ Hax1 Hax2 Γ Δ δ n ρ m τ Hlocks He HP typed inversion all assert σ Γ Δ ρ 2 e1 inr σ Γ Δ ρ 2 e2 inr τ Γ r τ σ as σ by typed inversion all eauto clear He destruct HP as m1 m2 destruct cmap erase union inv m m1 m2 as m1 m2 simplify mem disjoint hyps auto rewrite mem locks union in Hlocks by auto simpl in decompose empty apply ax expr compose 2 Γ δ A Q1 Q2 Δ DCInsert r e1 e2 ρ n m1 m2 inr σ inr τ eauto using ax expr invariant weaken sep union subseteq l sep union subseteq r esolve elem of esolve elem of clear dependent m1 m2 intros Δ n v1 v2 m1 m2 typed inversion all apply ax further alt intros Δ n Hframe inversion clear Hframe as mA mf simplify equality simplify mem disjoint hyps destruct HQ v1 v2 Γ Δ δ ρ n cmap erase m1 m2 as v HA eauto 6 using indexes valid weaken funenv valid weaken rewrite cmap erase union exists cmap erase m1 cmap erase m2 split ands auto by rewrite cmap erase disjoint le destruct HA Γ Δ δ n mA as clear HA eauto 4 using assert weaken indexes valid weaken funenv valid weaken rewrite cmap erase disjoint le auto simplify option equality typed inversion all split solve rcred intros S p inv rcstep p inv ehstep simplify equality exfalso eauto with cstep rewrite mem locks union by auto apply mk ax next with Δ m1 m2 auto constructor auto simpl by rewrite mem locks union by auto apply ax done constructor eauto using assert weaken indexes valid weaken val typed weaken val alter const typed Qed Lemma ax alloc Γ δ A P Q1 Q2 e τ o vb Q1 inr VBase vb Γ δ n τ i vb intV τ i n B Z to nat n 0 Ptr addr top o τ Z to nat n true perm full τ Z to nat n Q2 inl Ptr addr top array o τ n alloc can fail Q2 inl NULL TType τ A Γ δ A ₑ P e Q1 Γ δ A ₑ P alloc τ e Q2 Proof intros HQ Hax Γ Δ δ n ρ m τ lr He assert τ i Γ Δ ρ 2 e inr intT τ i Γ τ τ lr inl TType τ as τ i by typed inversion all eauto clear He apply ax expr compose 1 Γ δ A Q1 Δ DCAlloc τ e ρ n m inr intT τ i auto esolve elem of clear dependent m intros Δ n vb m typed inversion all destruct HQ fresh vb Γ Δ δ ρ n cmap erase m as na τ i Hm Hm Hfail eauto using indexes valid weaken funenv valid weaken typed inversion all rewrite sep left id in Hm by auto simplify equality clear Hm apply ax further intros solve rcred intros Δ n S Hframe p Hdom inversion clear Hframe as mA mf simplify equality simplify mem disjoint hyps assert alloc can fail S State Expr mem locks m NULL TType τ m mf mA o S State Expr mem locks m Ptr addr top array o τ na mem alloc Γ o true perm full val new Γ τ Z to nat na m mf mA o dom indexset m mf mA as o Ho simplify equality clear Hfail p inv rcstep p inv ehstep eauto exfalso eauto with cstep econstructor simpl eauto constructor eauto apply ax done constructor eauto 10 using type valid ptr type valid assert cmap erase m rewrite cmap erase disjoint le auto rewrite sep left id cmap erase m by auto by eapply Hfail eauto using funenv valid weaken assert Δ o None clear Hdom rewrite mem dom alloc in Hdom apply not elem of dom esolve elem of rewrite sep associative cmap dom union not elem of union in Ho by auto destruct Ho assert Γ τ Z to nat na by eauto using TArray valid assert mem alloc Γ o true perm full val new Γ τ Z to nat na m mf mA by eauto using mem alloc disjoint Δ simplify mem disjoint hyps apply mk ax next with o τ Z to nat na false Δ mem alloc Γ o true perm full val new Γ τ Z to nat na m eauto using mem alloc forward mem alloc forward least rewrite sep associative mem alloc union sep associative by auto constructor auto simpl by erewrite mem locks alloc Δ by eauto apply ax done constructor eauto 8 using addr top array typed mem alloc index typed mem locks alloc Δ destruct mem alloc singleton alt Γ Δ m o true perm full val new Γ τ Z to nat na τ Z to nat na as m Hm auto using val new frozen rewrite Hm in simplify mem disjoint hyps clear Hm erewrite cmap erase union mem erase singleton by eauto destruct HQ o intV τ i na B Γ Δ δ ρ n cmap erase m as na τ i m Hm HQ2 eauto using indexes valid weaken funenv valid weaken rewrite sep left id in Hm by auto simplify equality eapply HQ2 clear HQ2 eauto using mem alloc forward indexes valid weaken funenv valid weaken by eapply mem singleton valid eauto using mem

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

  • Module axiomatic_functions
    eauto using mem freeable perm subseteq sep union subseteq l destruct IH alter prod map id λ true o Δ ρ o τ mem free o m1 m2 as Δ Hleast Hlocks eauto using indexes valid weaken mem free forward mem free disjoint funenv valid weaken erewrite mem free union by eauto eauto erewrite mem free union cmap erase union mem free singleton sep left id associative L app length Nat add 1 r by eauto eauto 10 using assert weaken mem free forward simplify mem disjoint hyps assert Δ ₘ Δ transitivity alter prod map id λ true o Δ auto using mem free forward rewrite mem free foldr free exists Δ split ands auto intros Δ Hvalid apply Hleast auto assert τ Δ o Some τ false False intros τ destruct mem free valid index inv Γ Δ foldr mem free m1 m2 os false o rewrite mem free foldr free auto using mem freeable perm foldr free by exists τ rewrite alter id prod map id λ true Δ o by intros naive solver eauto using mem free memenv compat by erewrite mem free union by eauto by erewrite Hlocks mem locks free by eauto apply stack indep spec with ρ o τ eauto using indexes valid weaken funenv valid weaken Qed Lemma assert fun intro Γ δ f funname Pf s τ s τ Γ f Some τ s τ δ f Some s c vs Γ δ ₛ Π imap2 λ i v τ var i false perm full freeze true v τ vs τ s fpre Pf c vs s λ v Π imap λ i τ var i false perm full τ τ s fpost Pf c vs v emp A Γ δ assert fun f Pf τ s τ Proof intros Hf Γ1 Δ1 δ1 ρ n1 m split ands eauto using lookup fun weaken intros Γ2 Δ2 δ2 n2 c vs m apply ax further alt intros Δ3 n3 mf assert Δ2 ρ by eauto using indexes valid weaken assert δ2 f Some s apply lookup weaken with δ auto by transitivity δ1 clear dependent Δ1 n1 split solve rcred intros S p Hdom assert os Forall fresh dom indexset m mf os length os length vs S State CParams f zip os type of vs Stmt s mem alloc list Γ2 os vs m mf as os by inv rcstep p eauto clear p simplify type equality erewrite fmap type of by eauto destruct assert alloc params fpre Pf c vs Γ2 Δ3 δ2 n3 m mf os vs τ s as Δ4 Hpre eauto using Forall2 impl val typed weaken assert weaken indexes valid weaken funenv valid weaken apply mk ax next with Δ4 mem alloc list Γ2 os vs m auto constructor auto eauto using cmap union valid 2 cmap valid weaken intros simplify mem disjoint hyps eauto destruct funenv lookup Γ2 Δ2 δ2 f τ s τ as τ lr eauto using lookup fun weaken simplify equality assert length os length τ s erewrite Forall2 length τ s by eauto lia assert NoDup os by by apply Forall fresh NoDup with dom indexset m mf eapply ax compose cons with ax disjoint cond eauto using funenv valid weaken eapply Hf Hpre eauto using funenv valid weaken by transitivity Γ1 by transitivity δ1 assert Forall fresh dom indexset m os eapply Forall fresh subseteq eauto rewrite cmap dom union solve elem of by erewrite mem locks alloc list by eauto simpl rewrite snd zip by lia eauto using stmt typed weaken clear dependent m mf intros Δ5 n4 m destruct 1 intros apply ax further alt intros Δ6 n5 mf split solve rcred intros S p assert v S State Return f v foldr mem free m mf os assert holds Π imap λ i τ var i false perm full τ A τ s fpost Pf c vs v Γ2 Δ5 δ2 zip os τ s n4 cmap erase m Γ2 Δ5 v τ as v inv rcstep typed inversion all match goal with H rettype match inversion H subst end eexists split ands rewrite fst zip by auto eauto clear dependent p d destruct assert free params fpost Pf c vs v Γ2 Δ6 δ2 n5 m mf os τ s as Δ7 eauto using assert weaken indexes valid weaken funenv valid weaken apply mk ax next with Δ7 foldr mem free m os auto constructor auto intros simplify mem disjoint hyps eauto apply ax done constructor eauto using val typed weaken with congruence Qed Lemma ax call vn Γ δ A Pf P Q Ps Qs R e es vec expr K vn τ s τ c p vs A Q inl p Π vzip with λ Q v Q inr v Qs vs A Γ δ f p FunPtr f τ s τ assert fun f Pf τ s τ fpre Pf c vs vret fpost Pf c vs vret A R inr vret A Γ δ A ₑ P e λ ν Q ν i Γ δ A ₑ Ps i es i λ ν Qs i ν Γ δ A ₑ P Π Ps call e es R Proof intros HQ Hax1 Hax2 Γ Δ δ n ρ m τ lr He HP assert τ τ s vec vn τ lr inr τ Γ Δ ρ 2 e inl τ s τ i Γ Δ ρ 2 es i inr τ s i as τ τ s clear He assert τ τ s τ lr inr τ Γ Δ ρ 2 e inl τ s τ Γ Δ ρ 2 es inr τ s as τ τ s Hes by typed inversion all eauto assert vn length τ s by by erewrite fmap length Forall2 length vec to list length by eauto subst vn exists τ list to vec τ s rewrite vec to list of list by rewrite Forall2 fmap r vec to list of list τ s Forall2 vlookup in

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

  • Module axiomatic_statements
    eauto Qed Lemma ax stmt Prop pre Γ δ A R J T C P Q s l l labels s J l Γ δ A True A mx mx cases s C mx Γ δ A True A A Γ δ R J T C ₛ P s Q Γ δ R J T C ₛ A P s Q Proof intros Hax apply ax stmt Prop pre packed A intros simpl in try by auto by apply assert sep preserving assert True intro intros rewrite assert Prop l by done by apply Hax Qed Structural rules Lemma ax do Γ δ R J T C P Q e Γ δ emp ₑ P e λ Q Γ δ R J T C ₛ P e Q Proof intros Hax Γ Δ δ n ρ m cm τ He typed inversion all try by decompose elem of apply ax further intros solve rcred intros Δ n mf S p subst inv rcstep p econstructor try by eauto esolve elem of clear dependent mf S eapply ax compose cons ax expr cond ρ emp eauto using funenv valid weaken apply Hax eauto using expr typed weaken indexes valid weaken assert weaken funenv valid weaken intros Δ n m φ v typed inversion all apply ax further intros solve rcred intros Δ n mf S p inv rcstep p rewrite mem unlock union mem unlock all spec by solve elem of eapply mk ax next try by eauto split done by rewrite mem unlock all disjoint le by auto apply cmap union valid 2 auto using mem unlock all valid by rewrite sep disjoint list double mem unlock all disjoint le clear dependent m mf φ v S apply ax done constructor auto using mem locks unlock all rewrite mem erase unlock all simpl eauto 6 using assert weaken mem unlock all valid indexes valid weaken Qed Lemma ax skip Γ δ R J T C P Γ δ R J T C ₛ P skip P Proof intros Γ Δ δ n k m cm τ typed inversion all try by decompose elem of apply ax further intros solve rcred intros Δ n m mf S p subst inv rcstep p eapply mk ax next try by eauto apply ax done constructor eauto using assert weaken Qed Lemma ax ret Γ δ R J T C P Q1 Q2 e v Q1 inr v Γ δ R v A Γ δ emp ₑ P e Q1 Γ δ R J T C ₛ P ret e Q2 Proof intros HQ Hax Γ Δ δ n ρ m cm τ typed inversion all try by decompose elem of apply ax further intros solve rcred intros Δ n mf S p subst inv rcstep p econstructor try by eauto esolve elem of clear dependent mf S eapply ax compose cons ax expr cond ρ emp eauto using funenv valid weaken apply Hax eauto using expr typed weaken indexes valid weaken assert weaken funenv valid weaken intros Δ n m φ v typed inversion all apply ax further intros solve rcred intros Δ n mf S p subst inv rcstep p rewrite mem unlock union mem unlock all spec by solve elem of eapply mk ax next try by eauto split done by rewrite mem unlock all disjoint le by auto apply cmap union valid 2 auto using mem unlock all valid by rewrite sep disjoint list double mem unlock all disjoint le apply ax done constructor eauto using mem locks unlock all val typed weaken rewrite mem erase unlock all simpl eapply HQ eauto 6 using assert weaken mem unlock all valid indexes valid weaken funenv valid weaken Qed Lemma ax throw Γ δ R J T C Q i Γ δ R J T C ₛ T i throw i Q Proof intros Γ Δ δ n k m cm τ simplify equality try solve elem of apply ax further intros solve rcred intros Δ n m mf S p subst inv rcstep p eapply mk ax next try by eauto apply ax done constructor eauto using assert weaken Qed Lemma ax catch Γ δ R J T C P Q s Γ δ R J nat rect λ Q λ i T i C ₛ P s Q Γ δ R J T C ₛ P catch s Q Proof intros Hax Γ Δ δ n ρ d m cm τ typed inversion all apply ax further intros solve rcred intros Δ n mf p assert S State CStmt catch Stmt d s m mf by inv rcstep p subst clear p apply mk ax next with Δ m auto eapply ax compose cons eauto using funenv valid weaken eapply Hax eauto using indexes valid weaken stmt typed weaken funenv valid weaken by destruct d as eauto using assert weaken clear dependent d m mf intros Δ n φ m d m clear m apply ax further destruct d as done intros solve rcred intros Δ n mf S p assert d S State Stmt d catch s m mf assert holds dassert pack P Q R J T C d Γ Δ δ ρ n cmap erase m direction out d s Γ Δ d false m σ as d inv rcstep p typed inversion all eexists split ands eauto using assert weaken indexes valid weaken val typed weaken econstructor eauto apply ax done constructor auto Qed Lemma ax goto Γ δ R J T C Q l Γ δ R J T C ₛ J l goto l Q Proof intros Γ Δ δ n k m cm τ simplify equality try solve elem of apply ax further intros solve rcred intros Δ n m mf S p subst inv rcstep p eapply mk ax next try by eauto apply ax done constructor eauto using assert weaken esolve elem of Qed Lemma ax label Γ δ R J T C l Γ δ R J T C ₛ J l label l J l Proof intros Γ Δ δ n k m cm τ simplify equality typed inversion all try solve elem of apply ax further intros solve rcred intros Δ n m mf S p subst inv rcstep p eapply mk ax next try by eauto apply ax done constructor eauto using assert weaken apply ax further intros solve rcred intros Δ n m mf S p subst inv rcstep p eapply mk ax next try by eauto apply ax done constructor eauto using assert weaken Qed Lemma ax case Γ δ R J T C mx Γ δ R J T C ₛ C mx scase mx C mx Proof intros Γ Δ δ n k m cm τ simplify equality typed inversion all try by decompose elem of apply ax further intros solve rcred intros Δ n m mf S p subst inv rcstep p eapply mk ax next try by eauto apply ax done constructor eauto using assert weaken apply ax further intros solve rcred intros Δ n m mf S p subst inv rcstep p eapply mk ax next try by eauto apply ax done constructor eauto using assert weaken Qed Lemma ax localP Γ δ Pd s τ Γ δ λ P var O false perm full τ P A Pd ₚ s Γ δ Pd ₚ local τ s Proof intros Hax Γ Δ δ n ρ d m cm τ Hm typed inversion all change stmt typed Γ Δ τ ρ 2 with typed Γ Δ τ ρ 2 stmt K Prop in apply ax further intros solve rcred intros Δ n mf p Hdom assert o S State CLocal o τ Stmt d s mem alloc Γ o false perm full val new Γ τ m mf o dom indexset m mf as o Ho by inv rcstep p eauto simplify equality clear p assert Δ o None clear Hdom rewrite mem dom alloc in Hdom apply not elem of dom esolve elem of rewrite cmap dom union not elem of union in Ho destruct Ho assert mem alloc Γ o false perm full val new Γ τ m mf by eauto using mem alloc disjoint Δ apply mk ax next with o τ false Δ mem alloc Γ o false perm full val new Γ τ m eauto using mem alloc forward mem alloc forward least rewrite mem alloc union by done constructor auto assert Γ o τ false Δ δ eauto using funenv valid weaken mem alloc forward eapply ax compose cons eauto eapply Hax eauto by erewrite mem locks alloc Δ by auto eauto using stmt typed weaken mem alloc forward constructor eauto using indexes valid weaken mem alloc forward by apply mem alloc index typed destruct mem alloc singleton alt Γ Δ m o false perm full val new Γ τ τ as m auto using val new frozen simplify mem disjoint hyps erewrite cmap erase union directed fmap spec mem erase singleton by eauto exists m cmap erase m split ands csimpl eauto using assert weaken mem alloc forward by rewrite cmap erase disjoint le eexists addr top o τ val new Γ τ split ands simpl eauto clear dependent d m mf intros Δ n φ m d m Hlocks HPd clear m assert Δ ₘ Δ by eauto using mem alloc forward assert Δ o τ by eauto using memenv forward typed mem alloc index typed apply ax further intros solve rcred intros Δ n mf S p assert S State Stmt d local τ s mem free o m mf by by inv rcstep p subst clear p rewrite directed fmap spec in HPd destruct HPd as m1 m2 Hm1 destruct cmap erase union inv l m m1 m2 as m2 Hm12 auto simplify mem disjoint hyps clear Hm12 rewrite mem locks union in Hlocks by auto decompose empty destruct Hm1 as a v simplify option equality assert mem freeable perm o false m1 by eauto using mem freeable perm singleton apply mk ax next with alter prod map id λ true o Δ mem free o m1 m2 eauto using mem free forward mem free forward least erewrite mem free union by eauto using mem freeable perm subseteq sep union subseteq l constructor auto rewrite sep disjoint le union mem free disjoint le by eauto auto intros eapply mem free forward least eauto using sep union subseteq l mem freeable perm subseteq sep union subseteq l transitive apply ax done constructor eauto eauto using direction typed weaken mem free forward erewrite mem locks free mem locks union by eauto using mem freeable perm subseteq sep union subseteq l by erewrite mem locks singleton empty perm full left id L by eauto erewrite mem free union cmap erase union mem free singleton by eauto rewrite sep left id by auto eauto using assert weaken mem free forward indexes valid weaken Qed Lemma ax local Γ δ R J T C P Q s τ Γ δ λ v var O false perm full τ R v λ l var O false perm full τ J l λ i var O false perm full τ T i λ mx var O false perm full τ C mx ₛ var O false perm full τ P s var O false perm full τ Q Γ δ R J T C ₛ P local τ s Q Proof intros by apply ax localP Qed Lemma ax comp Γ δ R J T C P P Q s1 s2 Γ δ R J T C ₛ P s1 P Γ δ R J T C ₛ P s2 Q Γ δ R J T C ₛ P s1 s2 Q Proof intros Hax1 Hax2 Γ Δ δ n ρ d m cm τ revert Δ d m induction n as n IH using lt wf ind constructor intros Δ d m Hs assert m τ c1 m τ1 c2 m τ2 cm τ c2 m τ Γ Δ ρ 2 s1 c1 m τ1 Γ Δ ρ 2 s2 c2 m τ2 rettype union m τ1 m τ2 m τ as m τ c1 m τ1 c2 m τ2 by typed inversion all eauto 10 clear Hs assert Δ n m d Δ ₘ Δ n n Γ Δ m mem locks m direction in d s2 assert holds dassert pack P Q R J T C d Γ Δ δ ρ n cmap erase m ax graph ax disjoint cond ax stmt post dassert pack P Q R J T C s1 s2 c2 m τ Γ δ Δ ρ n CStmt s1 Stmt d s2 m clear dependent m d intros Δ n m d eapply ax compose cons eauto using funenv valid weaken eapply Hax2 eauto using indexes valid weaken stmt typed weaken assert weaken funenv valid weaken clear dependent d m intros Δ n φ m d m clear m apply ax further intros solve rcred intros Δ n mf S p assert S State Stmt d s1 s2 m mf Γ Δ d c2 m τ direction out d s1 s2 l d l l labels s1 l labels s2 as l inv rcstep p typed inversion all erewrite rettype union inv r not elem of union by eauto try match goal with H l labels s2 destruct decide l labels s1 end naive solver eauto using val typed weaken econstructor eauto apply ax done constructor auto by destruct d eauto using assert weaken indexes valid weaken econstructor eauto eapply IH eauto using assert weaken indexes valid weaken funenv valid weaken esolve elem of typed constructor eauto using stmt typed weaken apply ax further intros solve rcred intros Δ n mf p assert l d l l labels s2 S State CStmt s1 Stmt d s2 m mf mx d mx mx cases s2 S State CStmt s1 Stmt d s2 m mf S State CStmt s2 Stmt d s1 m mf direction in d s1 as l mx by inv rcstep p eauto 10 clear p apply mk ax next with Δ m eauto using assert weaken apply mk ax next with Δ m eauto using assert weaken apply mk ax next with Δ m auto eapply ax compose cons eauto using funenv valid weaken eapply Hax1 eauto using indexes valid weaken stmt typed weaken funenv valid weaken by destruct d eauto using assert weaken clear dependent d m mf intros Δ n φ m d m clear m apply ax further intros solve rcred intros Δ n mf S p assert S State Stmt d s1 s2 m mf Γ Δ d c2 m τ d direction out d s1 s2 l d l l labels s1 l labels s2 d S State CStmt s1 Stmt s2 m mf as l inv rcstep p typed inversion all erewrite rettype union inv l not elem of union by eauto try match goal with H l labels s1 destruct decide l labels s2 end naive solver eauto using val typed weaken econstructor eauto apply ax done constructor auto by destruct d eauto using assert weaken indexes valid weaken econstructor eauto eapply IH eauto using assert weaken indexes valid weaken funenv valid weaken esolve elem of typed constructor eauto using stmt typed weaken econstructor eauto 10 using assert weaken indexes valid weaken Qed Lemma ax loop Γ δ R J T C P s Γ δ R J T C ₛ P s P Γ δ R J T C ₛ P loop s False Proof intros Hax Γ Δ δ n ρ d m cm τ revert Δ d m induction n as n IH using lt wf ind constructor intros Δ d m typed inversion all apply ax further intros solve rcred intros Δ n mf S p assert S State CStmt loop Stmt d s m mf by inv rcstep p subst clear p apply mk ax next with Δ m auto eapply ax compose cons eauto using funenv valid weaken eapply Hax eauto using indexes valid weaken stmt typed weaken funenv valid weaken destruct d naive solver eauto using assert weaken indexes valid weaken clear dependent d m mf intros Δ n φ m d m clear m apply ax further intros solve rcred intros Δ n mf S p assert d S State Stmt d loop s m mf Γ Δ d true m σ d S State Stmt loop s m mf as inv rcstep typed inversion all eauto 8 using val typed weaken econstructor eauto apply ax done constructor auto by destruct d eauto using assert weaken indexes valid weaken econstructor eauto eapply IH eauto using assert weaken indexes valid weaken funenv valid weaken stmt typed weaken Qed Lemma ax if Γ δ R J T C P P P1 P2 Q e s1 s2 vb P inr VBase vb Γ δ NotOp VBase vb A vb base val is 0 vb P inr VBase vb Γ δ P1 A vb base val is 0 vb P inr VBase vb Γ δ P2 A Γ δ emp ₑ P e P Γ δ R J T C ₛ P1 s1 Q Γ δ R J T C ₛ P2 s2 Q Γ δ R J T C ₛ P if e s1 else s2 Q Proof intros HP HP1 HP2 Hax Hax1 Hax2 Γ Δ δ n ρ d m cm τ H δ Hm Hlock Hd Hs assert τ b m τ c1 m τ1 c2 m τ2 cm τ c1 c2 m τ Γ Δ ρ 2 e inr baseT τ b locks e Γ Δ ρ 2 s1 c1 m τ1 Γ Δ ρ 2 s2 c2 m τ2 rettype union m τ1 m τ2 m τ as τ b m τ c1 m τ1 c2 m τ2 He Hs1 Hs2 by typed inversion all eauto 20 clear Hs revert Δ d m H δ Hm Hlock Hd He Hs1 Hs2

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