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 ctrees
    MUnion t2 i2 w2 xs2 cast if and5 decide t1 t2 decide i1 i2 decide w1 w2 decide xs1 xs2 decide ctree unmapped w1 Forall sep unmapped xs1 MUnionAll t1 xs1 MUnionAll t2 xs2 cast if and decide t1 t2 decide xs1 xs2 MUnionAll t1 xs1 MUnion t2 w2 xs2 cast if and5 decide t1 t2 decide xs1 ctree flatten w2 xs2 decide Forall sep unmapped xs1 decide ctree valid w2 decide ctree unmapped w2 Forall sep unmapped xs2 right end clear go abstract first by subst constructor by inversion 1 Defined Global Instance ctree union Union ctree K A fix go w1 w2 let Union go in match w1 w2 with MBase τ b xs1 MBase xs2 MBase τ b xs1 xs2 MArray τ ws1 MArray ws2 MArray τ ws1 ws2 MStruct t wxss1 MStruct wxss2 MStruct t wxss1 wxss2 MUnion t i w1 xs1 MUnion w2 xs2 MUnion t i w1 w2 xs1 xs2 MUnionAll t xs1 MUnionAll xs2 MUnionAll t xs1 xs2 w MUnionAll xs MUnionAll xs w ctree merge w xs w1 end Definition ctree difference merge ctree K A list A ctree K A fix go w ys match w with MBase τ b xs MBase τ b zip with xs ys MArray τ ws MArray τ ctree merge array go ws ys MStruct t wxss MStruct t ctree merge struct go wxss ys MUnion t i w xs let sz length ctree flatten w in let w go w take sz ys in let xs zip with xs drop sz ys in MUnion t i w xs MUnionAll t xs MUnionAll t zip with xs ys end Global Instance ctree difference Difference ctree K A fix go w1 w2 let Difference go in match w1 w2 with MBase τ b xs1 MBase xs2 MBase τ b xs1 xs2 MArray τ ws1 MArray ws2 MArray τ ws1 ws2 MStruct t wxss1 MStruct wxss2 MStruct t wxss1 wxss2 MUnion t i w1 xs1 MUnion w2 xs2 MUnion t i w1 w2 xs1 xs2 MUnionAll t xs1 MUnionAll xs2 MUnionAll t xs1 xs2 w MUnionAll xs2 ctree difference merge w xs2 w1 end End operations Section memory trees Context K A Set Separation A Implicit Types x A Implicit Types xs list A Implicit Types xss list list A Implicit Types w ctree K A Implicit Types ws list ctree K A Implicit Types wxs ctree K A list A Implicit Types wxss list ctree K A list A Implicit Types τ b base type K Implicit Types τ type K Implicit Types τ s list type K Local Arguments union Local Arguments difference Local Arguments half Hint Resolve Forall app 2 Forall2 app Hint Immediate seps disjoint lr seps disjoint ll Hint Immediate seps disjoint rl seps disjoint rr Ltac simplifier repeat match goal with progress list simplifier progress autorewrite with simplifier progress autorewrite with simplifier in H zs xs zs apply seps cancel l in H subst xs by eauto by eauto H xs zs zs apply seps cancel r in H subst xs by eauto by eauto end Lemma ctree valid Forall w ctree valid w ctree Forall sep valid w Proof induction 1 as ws IH ws IH using ctree valid ind alt simpl auto induction IH simplifier auto Qed Hint Immediate ctree valid Forall Section merge Context B C Set SeparationOps C Lemma ctree flatten merge f A B C w ys ctree flatten ctree merge f w ys zip with f ctree flatten w ys Proof revert w ys refine ctree ind alt simpl done induction 2 csimpl intros rewrite zip with app l f equal auto induction 2 as intros simplifier rewrite associative L zip with app l repeat f equal auto intros rewrite zip with app l f equal auto done Qed Lemma ctree merge valid f A B C w ys ctree valid w length ctree flatten w length ys Forall2 λ x y sep unmapped f x y sep unmapped x ctree flatten w ys Forall sep valid zip with f ctree flatten w ys ctree valid ctree merge f w ys Proof intros Hw rewrite Forall2 same length revert w Hw ys assert xs ys Forall2 λ x y sep unmapped f x y sep unmapped x xs ys Forall sep unmapped zip with f xs ys Forall sep unmapped xs induction 1 intros simplifier constructor auto refine ctree valid ind alt simpl by constructor intros τ ws IH ys Hys Hys Hys constructor revert ys Hys Hys Hys induction IH intros simplifier auto intros t IH ys Hys Hys Hys constructor revert ys Hys Hys Hys induction IH as intros simplifier constructor simpl eauto intros t i w xs IH Hun ys Hys Hys Hys simplifier constructor rewrite ctree flatten merge intuition eauto 10 by constructor Qed End merge Hint Rewrite ctree flatten merge simplifier Lemma ctree flatten disjoint w1 w2 w1 w2 ctree flatten w1 ctree flatten w2 Proof revert w1 w2 refine ctree disjoint ind alt simpl auto 2 using Forall2 bind intros wxss1 wxss2 IH induction IH simplifier auto Qed Ltac list solve length repeat rewrite app length repeat match goal with H apply ctree flatten disjoint in H H Forall2 apply Forall2 length in H end assumption congruence Lemma ctree flatten union w1 w2 w1 w2 ctree flatten w1 w2 ctree flatten w1 ctree flatten w2 Proof revert w1 w2 refine ctree disjoint ind alt simpl auto 1 intros τ ws1 ws2 IH induction IH simplifier f equal auto intros t wxss1 wxss2 IH induction IH as simplifier repeat f equal auto intros simplifier by f equal intros simplifier f equal eauto using seps commutative by intros simplifier Qed Lemma ctree flatten disjoint l w1 w2 ys w1 w2 ctree flatten w1 w2 ys ctree flatten w2 ys Proof intros rewrite ctree flatten union by done eauto using seps disjoint lr ctree flatten disjoint Qed Global Instance ctree symmetric Symmetric disjoint ctree K A Proof induction 1 using ctree disjoint ind alt constructor done apply Forall2 flip eauto using Forall2 impl Qed Lemma ctree disjoint valid l w1 w2 w1 w2 ctree valid w1 Proof induction 1 as τ ws1 ws2 IH t wxss1 wxss2 IH Hwxss using ctree disjoint ind alt simplifier constructor eauto using seps disjoint valid l induction IH auto clear Hwxss induction IH auto clear IH induction Hwxss eauto using seps disjoint valid l Qed Lemma ctree disjoint valid r w1 w2 w1 w2 ctree valid w2 Proof intros by apply ctree disjoint valid l with w1 Qed Lemma ctree flatten difference merge w ys ctree flatten ctree difference merge w ys ctree flatten w ys Proof revert w ys refine ctree ind alt simpl done induction 2 csimpl intros rewrite zip with app l f equal auto induction 2 as intros simplifier rewrite associative L zip with app l repeat f equal auto intros unfold MUnion case decide rewrite zip with app l f equal auto done Qed Hint Rewrite ctree flatten difference merge simplifier Lemma ctree difference merge valid w ys ctree valid w ys ctree flatten w ctree valid ctree difference merge w ys Proof intros Hw revert w Hw ys refine ctree valid ind alt simpl constructor eauto using seps difference valid intros τ ws IH ys Hys constructor revert ys Hys induction IH intros simplifier auto intros t IH ys Hys constructor revert ys Hys induction IH as intros simplifier constructor simpl eauto using seps difference valid intros t i w xs IH Hun ys Hys simplifier unfold MUnion rewrite ctree flatten difference merge case decide constructor rewrite ctree flatten difference merge eauto using seps difference valid constructor eauto using seps difference valid Qed Lemma ctree disjoint difference w1 w2 w1 w2 w1 w2 w1 Proof revert w1 w2 refine ctree subseteq ind alt simpl constructor auto using seps disjoint difference intros τ ws1 ws2 IH constructor induction IH simpl auto intros t wxss1 wxss2 IH Hwxss constructor clear Hwxss induction IH simpl auto clear IH induction Hwxss as constructor simpl auto using seps disjoint difference intros unfold MUnion case decide constructor intuition eauto using seps disjoint difference ctree disjoint valid l ctree flatten disjoint constructor auto using seps disjoint difference intros t i xs1 w2 xs2 unfold MUnion case decide constructor simplifier auto using seps disjoint difference ctree difference merge valid Qed Ltac list solve length rewrite ctree flatten union by done repeat match goal with H w1 w2 unless w1 w2 w1 by assumption assert w1 w2 w1 by by apply ctree disjoint difference H xs1 xs2 unless xs1 xs2 xs1 by assumption assert xs1 xs2 xs1 by by apply seps disjoint difference end repeat match goal with H apply ctree flatten disjoint l in H done H apply seps disjoint lr in H done H apply seps disjoint rr in H done H apply ctree flatten disjoint in H end repeat match goal with H Forall2 apply Forall2 length in H rewrite zip with length l eq rewrite replicate length rewrite app length rewrite fmap length rewrite app length end assumption congruence Section merge merge Context B C D Set Context f A B A g A C A h1 A D A h2 C B D Lemma ctree merge merge w ys1 ys2 length ctree flatten w length ys1 length ctree flatten w length ys2 zip with f zip with g ctree flatten w ys1 ys2 zip with h1 ctree flatten w zip with h2 ys1 ys2 ctree merge f ctree merge g w ys1 ys2 ctree merge h1 w zip with h2 ys1 ys2 Proof rewrite Forall2 same length revert ys1 ys2 induction w as τ ws IH s wxs IH using ctree ind alt simpl intros simplifier f equal auto intros ys1 ys2 Hys1 Hys2 Hys3 f equal revert ys1 ys2 Hys1 Hys2 Hys3 induction IH intros simplifier f equal auto intros ys1 ys2 Hys1 Hys2 Hys3 f equal revert ys1 ys2 Hys1 Hys2 Hys3 induction IH as intros simplifier repeat f equal auto intros simplifier f equal auto intros simplifier f equal auto Qed End merge merge Section merge union Context B Set f A B A Lemma ctree merge disjoint w1 w2 ys w1 w2 length ctree flatten w1 length ys Forall2 λ x y sep unmapped f x y sep unmapped x ctree flatten w1 ys Forall2 λ x y sep unmapped x sep unmapped f x y ctree flatten w1 ys zip with f ctree flatten w1 ys ctree flatten w2 ctree merge f w1 ys w2 Proof intros Hw rewrite Forall2 same length revert w1 w2 Hw ys assert xs ys Forall2 λ x y sep unmapped f x y sep unmapped x xs ys Forall sep unmapped zip with f xs ys Forall sep unmapped xs induction 1 intros simplifier constructor auto assert xs ys Forall2 λ x y sep unmapped x sep unmapped f x y xs ys Forall sep unmapped xs Forall sep unmapped zip with f xs ys induction 1 intros simplifier constructor auto refine ctree disjoint ind alt simpl by constructor intros τ ws1 ws2 IH ys Hys1 Hys2 Hys3 Hys4 constructor revert ys Hys1 Hys2 Hys3 Hys4 induction IH intros simplifier constructor auto intros t wxss1 wxss2 IH ys Hys1 Hys2 Hys3 Hys4 constructor revert ys Hys1 Hys2 Hys3 Hys4 induction IH as intros simplifier constructor simpl eauto intros simplifier constructor auto rewrite ctree flatten merge intuition eauto 10 by constructor intros simplifier constructor eauto intros simplifier constructor rewrite ctree flatten merge intuition eauto using ctree merge valid Forall2 impl seps disjoint valid l Forall2 length Qed Lemma ctree merge union commute w xs ys length ctree flatten w length xs length ctree flatten w length ys zip with f ctree flatten w xs ys zip with f ctree flatten w ys xs ctree merge f ctree merge w xs ys ctree merge ctree merge f w ys xs Proof rewrite Forall2 same length revert xs ys induction w as τ ws IH s wxs IH using ctree ind alt simpl intros simplifier f equal auto intros ys1 ys2 Hys1 Hys2 Hys3 f equal revert ys1 ys2 Hys1 Hys2 Hys3 induction IH intros simplifier f equal auto intros ys1 ys2 Hys1 Hys2 Hys3 f equal revert ys1 ys2 Hys1 Hys2 Hys3 induction IH as intros simplifier repeat f equal auto intros simplifier f equal auto intros simplifier f equal auto Qed Lemma ctree merge union w1 w2 ys w1 w2 length ctree flatten w1 length ys zip with f ctree flatten w1 ys ctree flatten w2 zip with f ctree flatten w1 ctree flatten w2 ys zip with f ctree flatten w1 ys ctree flatten w2 ctree merge f w1 w2 ys ctree merge f w1 ys w2 Proof intros Hw rewrite Forall2 same length revert w1 w2 Hw ys refine ctree disjoint ind alt simpl intros by f equal intros τ ws1 ws2 IH ys Hys1 Hys2 Hys3 f equal revert ys Hys1 Hys2 Hys3 induction IH intros simplifier f equal auto intros t wxss1 wxss2 IH ys Hys1 Hys2 Hys3 f equal revert ys Hys1 Hys2 Hys3 induction IH as intros simplifier repeat f equal simpl eauto intros simplifier f equal auto intros by f equal intros simplifier f equal auto rewrite ctree merge merge f f auto try list solve length rewrite seps commutative by done etransitivity eassumption by rewrite seps commutative by done rewrite seps commutative by done etransitivity eassumption by rewrite seps commutative by done intros simplifier f equal auto apply ctree merge union commute list solve length Qed Lemma ctree merge map g A A w ys length ctree flatten w length ys zip with f ctree flatten w ys g ctree flatten w ctree merge f w ys ctree map g w Proof rewrite Forall2 same length revert ys induction w as τ ws IH t wxss IH using ctree ind alt intros ys Hys Hys simplifier f equal auto revert ys Hys Hys induction IH intros simplifier f equal auto revert ys Hys Hys induction IH as intros simplifier repeat f equal auto Qed End merge union Section map union Context f A A Hint Rewrite app length A replicate plus simplifier Lemma ctree merge replicate w ctree merge λ x f x w replicate length ctree flatten w ctree map f w Proof apply ctree merge map auto using replicate length by rewrite zip with replicate r Qed Lemma ctree map disjoint w1 w2 w1 w2 Forall λ x sep unmapped f x sep unmapped x ctree flatten w1 Forall λ x sep unmapped x sep unmapped f x ctree flatten w1 f ctree flatten w1 ctree flatten w2 ctree map f w1 w2 Proof intros Hf1 Hf2 Hf3 rewrite ctree merge replicate apply ctree merge disjoint auto using replicate length elim Hf1 simpl auto elim Hf2 simpl auto rewrite Forall2 fmap l in Hf3 elim Hf3 simplifier auto Qed Lemma ctree map union w1 w2 w1 w2 f ctree flatten w1 ctree flatten w2 f ctree flatten w1 ctree flatten w2 f ctree flatten w1 ctree flatten w2 ctree map f w1 w2 ctree map f w1 w2 Proof intros Hf1 Hf2 rewrite ctree merge replicate ctree flatten union by done rewrite zip with length l eq by list solve length apply ctree merge union auto using replicate length rewrite Forall2 fmap l in Hf1 elim Hf1 simplifier auto by rewrite zip with replicate r eq by list solve length Qed End map union Lemma ctree merge unmapped w ys ctree flatten w ys ctree unmapped w Forall sep unmapped ys ctree unmapped ctree merge w ys Proof rewrite ctree flatten merge by done eauto using seps unmapped union Qed Lemma ctree merge mapped w ys ctree flatten w ys ctree unmapped ctree merge w ys ctree unmapped w Proof rewrite ctree flatten merge by done eauto using seps unmapped union l Qed Lemma ctree merge union valid w ys ctree valid w ctree flatten w ys Forall sep unmapped ys ctree valid ctree merge w ys Proof eauto 10 using ctree merge valid seps union valid Forall2 length Forall2 impl sep unmapped union l Qed Lemma ctree merge flatten w1 w2 w1 w2 ctree unmapped w2 ctree merge w1 ctree flatten w2 w1 w2 Proof revert w1 w2 refine ctree disjoint ind alt simpl done intros τ ws1 ws2 IH f equal induction IH simplifier f equal auto intros t wxss1 wxss2 IH f equal induction IH as simplifier repeat f equal auto intros t i w1 w2 xs1 xs2 intros simplifier f equal auto done intros simplifier naive solver intros simplifier naive solver Qed Lemma ctree unmapped union w1 w2 w1 w2 ctree unmapped w1 ctree unmapped w2 ctree unmapped w1 w2 Proof intros rewrite ctree flatten union by done eauto using seps unmapped union ctree flatten disjoint Qed Lemma ctree unmapped union l w1 w2 w1 w2 ctree unmapped w1 w2 ctree unmapped w1 Proof intros rewrite ctree flatten union by done eauto using seps unmapped union l ctree flatten disjoint Qed Lemma ctree unmapped union r w1 w2 w1 w2 ctree unmapped w1 w2 ctree unmapped w2 Proof intros rewrite ctree flatten union by done eauto using seps unmapped union r ctree flatten disjoint Qed Lemma ctree positive l w1 w2 w1 w2 ctree empty w1 w2 ctree empty w1 Proof intros rewrite ctree flatten union by done eauto using seps positive l ctree flatten disjoint Qed Lemma ctree union valid w1 w2 w1 w2 ctree valid w1 w2 Proof revert w1 w2 refine ctree disjoint ind alt simpl constructor eauto using seps union valid intros τ ws1 ws2 IH constructor induction IH simpl auto intros t wxss1 wxss2 IH Hwxss constructor clear Hwxss induction IH simpl auto clear IH induction Hwxss constructor simpl eauto using seps union valid constructor intuition eauto using seps union valid ctree unmapped union l seps unmapped union l constructor eauto using seps union valid intros simplifier constructor eauto using seps union valid ctree merge union valid intuition eauto using ctree merge mapped seps unmapped union l intros simplifier constructor eauto using seps union valid ctree merge union valid intuition eauto using ctree merge mapped seps unmapped union l Qed Lemma ctree commutative w1 w2 w1 w2 w1 w2 w2 w1 Proof induction 1 as τ ws1 ws2 IH t wxss1 wxss2 IH Hwxss using ctree disjoint ind alt f equal auto using seps commutative induction IH f equal auto induction IH as simplifier auto using seps commutative with f equal Qed Lemma ctree merge id B Set h A B A w ys length ctree flatten w length ys zip with h ctree flatten w ys ctree flatten w ctree merge h w ys w Proof rewrite Forall2 same length revert w ys refine ctree ind alt simpl by intros f equal intros τ ws IH ys Hys Hys f equal revert ys Hys Hys induction IH intros simplifier f equal eauto intros t wxss IH ys Hys Hys f equal revert ys Hys Hys induction IH as intros simplifier repeat f equal auto intros simplifier f equal auto by intros f equal Qed Lemma ctree flatten map B Set h A B w ctree flatten ctree map h w h ctree flatten w Proof induction w as ws IH wxss IH using ctree ind alt simpl auto induction IH csimpl rewrite fmap app f equal auto induction IH csimpl rewrite fmap app repeat f equal auto rewrite fmap app f equal auto Qed Lemma ctree merge empty w ys ctree flatten w ys Forall ys ctree merge w ys w Proof eauto using ctree merge id seps right id Forall2 length Qed Lemma ctree left id w1 w2 w1 w2 ctree empty w1 w1 w2 w2 Proof revert w1 w2 refine ctree disjoint ind alt simpl intros f equal auto using seps left id intros τ ws1 ws2 IH f equal induction IH simplifier f equal auto intros t wxss1 wxss2 IH Hwxss f equal induction IH as simplifier repeat f equal auto using seps left id intros simplifier f equal auto using seps left id intros simplifier f equal auto using seps left id intros simplifier f equal auto using seps right id ctree merge empty intros simplifier exfalso naive solver eauto using Forall impl sep unmapped empty alt Qed Lemma ctree right id w1 w2 w1 w2 ctree empty w2 w1 w2 w1 Proof intros by rewrite ctree commutative ctree left id Qed Lemma ctree merge disjoint l w1 w2 ys ctree valid w1 ctree flatten w1 ys ctree merge w1 ys w2 w1 w2 Proof intros Hw1 revert w1 Hw1 w2 ys refine ctree valid ind alt simpl intros τ b xs1 w2 ys Hys Hw2 apply ctree disjoint inv l Hw2 constructor eauto intros τ ws1 IH w2 ys Hys Hw2 apply ctree disjoint inv l Hw2 clear w2 Hw2 intros ws2 Hws2 constructor revert ws2 ys Hys Hws2 induction IH intros simplifier eauto intros t wxss IH w2 ys Hys Hw2 apply ctree disjoint inv l Hw2 clear w2 Hw2 intros wxss2 Hwxss Hwxss constructor clear Hwxss revert wxss2 ys Hys Hwxss induction IH as intros simplifier eauto clear IH Hwxss revert wxss2 ys Hys Hwxss induction wxss as intros simplifier eauto intros t i w1 xs1 Hw1 IH w2 ys Hys Hw2 simplifier apply ctree disjoint inv l Hw2 clear w2 Hw2 intros w2 xs2 constructor eauto intros xs2 simplifier constructor eauto intros t xs1 w2 ys Hys Hw2 apply ctree disjoint inv l Hw2 constructor eauto using seps unmapped union l Qed Lemma ctree disjoint ll w1 w2 w3 w1 w2 w1 w2 w3 w1 w3 Proof intros Hw12 revert w1 w2 Hw12 w3 refine ctree disjoint ind alt simpl intros τ b xs1 xs2 w3 Hw3 apply ctree disjoint inv l Hw3 constructor eauto intros τ ws1 ws2 IH w3 Hw3 apply ctree disjoint inv l Hw3 clear w3 Hw3 intros ws3 Hws3 constructor revert ws3 Hws3 induction IH intros simplifier auto intros t wxss1 wxss2 IH Hwxss w3 Hw3 apply ctree disjoint inv l Hw3 clear w3 Hw3 intros wxss3 Hwxss3 Hwxss3 constructor clear Hwxss Hwxss3 revert wxss3 Hwxss3 induction IH intros simplifier auto clear IH Hwxss3 revert wxss3 Hwxss3 induction Hwxss intros simplifier eauto intros t i w1 w2 xs1 xs2 IH Hxs w3 Hw3 apply ctree disjoint inv l Hw3 clear w3 Hw3 constructor eauto intros xs3 rewrite ctree flatten union by done intros Hxs3 simplifier constructor eauto using ctree disjoint valid l seps disjoint ll ctree flatten disjoint intros t xs1 xs2 Hxs w3 Hw3 apply ctree disjoint inv l Hw3 constructor eauto using seps unmapped union l intros t i xs1 w2 xs2 w3 Hw3 simplifier apply ctree disjoint inv l Hw3 clear w3 Hw3 intros w3 xs3 Hw3 constructor eauto using ctree disjoint valid r apply ctree flatten disjoint in Hw3 simplifier eauto constructor simplifier eauto intros t i w1 xs1 xs2 w3 Hw3 simplifier apply ctree disjoint inv l Hw3 constructor simplifier eauto using ctree merge disjoint l Qed Lemma ctree disjoint lr w1 w2 w3 w1 w2 w1 w2 w3 w2 w3 Proof intros rewrite ctree commutative by done by apply ctree disjoint ll Qed Lemma ctree merge move w1 w2 ys w1 w2 ctree flatten w1 w2 ys Forall sep unmapped ys w1 ctree merge w2 ys Proof intros Hw revert w1 w2 Hw ys refine ctree disjoint ind alt simpl constructor eauto using seps disjoint move l intros τ ws1 ws2 Hws IH ys Hys Hys constructor revert ys Hys Hys induction IH intros simplifier constructor auto intros t wxss1 wxss2 Hws IH Hxss ys Hys Hys constructor revert ys Hys Hys induction IH as intros constructor simplifier auto revert ys Hys Hys clear IH induction Hxss as intros constructor simplifier auto using seps disjoint move l intros t i w1 w2 xs1 xs2 IH Hc2 ys rewrite Forall2 app inv l intros ys1 ys2 Hys1 Hys2 rewrite Forall app intros simplifier constructor eauto using seps disjoint move l rewrite ctree flatten union in Hys1 by done intros destruct Hc2 split eauto using ctree merge mapped seps unmapped union l seps disjoint lr ctree flatten disjoint constructor eauto using seps disjoint move l intros t i xs1 w2 xs2 rewrite Forall2 app inv r intros xs1 xs1 Hxs1 Hxs1 rewrite Forall app intros Hc ys simplifier rewrite seps commutative xs1 Forall2 app inv l by done intros ys1 ys2 Hys1 Hys2 rewrite Forall app intros simplifier rewrite seps commutative in Hys2 by done constructor simplifier eauto using seps disjoint move l eauto eauto using ctree merge union valid intuition eauto using ctree merge mapped seps unmapped union l intros t i w1 xs1 xs2 ys simplifier constructor eauto using seps disjoint move l seps unmapped union Qed Lemma ctree disjoint move l w1 w2 w3 w1 w2 w1 w2 w3 w1 w2 w3 Proof intros Hw12 revert w1 w2 Hw12 w3 refine ctree disjoint ind alt simpl intros τ b xs1 xs2 w3 Hw3 pattern w3 apply ctree disjoint inv l Hw3 constructor eauto using seps disjoint move l intros τ ws1 ws2 IH w3 Hw3 pattern w3 apply ctree disjoint inv l Hw3 clear w3 Hw3 intros ws3 Hws3 constructor revert ws3 Hws3 induction IH intros simplifier auto intros t wxss1 wxss2 IH Hwxss w3 Hw3 pattern w3 apply ctree disjoint inv l Hw3 clear w3 Hw3 intros wxss3 Hwxss3 Hwxss3 constructor clear Hwxss Hwxss3 revert wxss3 Hwxss3 induction IH intros simplifier constructor simpl auto clear IH Hwxss3 revert wxss3 Hwxss3 induction Hwxss intros simplifier constructor simpl eauto using seps disjoint move l intros t i w1 w2 xs1 xs2 IH Hxs Hc2 w3 Hw3 pattern w3 apply ctree disjoint inv l Hw3 clear w3 Hw3 simpl intros w3 xs3 constructor eauto using seps disjoint move l assert w2 w3 by eauto using ctree disjoint lr intuition eauto using seps unmapped union l ctree unmapped union l intros xs3 rewrite Forall2 app inv l intros xs3 xs3 rewrite Forall app intros assert ctree flatten w2 xs3 apply seps disjoint lr with ctree flatten w1 rewrite ctree flatten union eauto using ctree flatten disjoint simplifier constructor eauto using ctree merge move seps disjoint move l intuition eauto using ctree merge mapped seps unmapped union l intros t xs1 xs2 Hxs w3 Hw3 pattern w3 apply ctree disjoint inv l Hw3 clear w3 Hw3 simpl constructor eauto using seps disjoint move l intros i w2 zs rewrite Forall2 app inv r intros Hxs3 apply zip with app inv in Hxs3 destruct Hxs3 as xs3 xs3 xs4 xs4 intros simplifier assert xs3 ctree flatten w2 by eauto using seps disjoint lr assert xs4 zs by eauto using seps disjoint lr simplifier constructor simplifier apply Forall2 app rewrite seps commutative by done eauto using seps disjoint move l eauto using seps unmapped union l eauto using ctree merge union valid seps unmapped union r intuition eauto using seps unmapped union l ctree merge mapped intros t i xs1 w2 xs2 rewrite Forall2 app inv r intros xs1 xs1 Hxs1 Hxs2 w3 Hw3 simplifier symmetry in Hxs2 pattern w3 apply ctree disjoint inv l Hw3 clear w3 Hw3 simpl intros w3 xs3 rewrite seps commutative by done intros assert w2 w3 by eauto using ctree merge disjoint l constructor eauto using ctree union valid apply Forall2 app eauto using seps disjoint move l rewrite ctree flatten union by done apply seps disjoint move l auto rewrite seps commutative ctree flatten merge by done eauto using ctree flatten disjoint intuition eauto using seps unmapped union l ctree unmapped union l intros xs3 rewrite ctree flatten merge seps commutative xs1 seps commutative xs1 Forall2 app inv l by done intros xs3 xs3 rewrite Forall app intros simplifier constructor simplifier eauto using seps disjoint move l eauto eauto using ctree merge union valid intuition eauto using seps unmapped union l ctree merge mapped intros t i w1 xs1 xs2 rewrite Forall2 app inv l intros xs2 xs2 Hxs2 Hxs2 w3 Hw3 simplifier pattern w3 apply ctree disjoint inv l Hw3 clear w3 Hw3 simpl intros w3 xs3 assert xs2 ctree flatten w3 apply seps disjoint ll with ctree flatten w1 auto rewrite seps commutative ctree flatten merge by auto eauto using ctree flatten disjoint assert xs3 xs2 by eauto simplifier rewrite seps commutative constructor eauto eapply ctree merge move eauto using ctree merge disjoint l rewrite ctree flatten union by eauto using ctree merge disjoint l symmetry apply seps disjoint move l auto rewrite seps commutative ctree flatten merge by done eauto using ctree flatten disjoint eauto using seps disjoint move l intuition eauto using ctree merge mapped seps unmapped union r eauto intros xs3 simplifier constructor eauto using seps disjoint move l seps unmapped union Qed Lemma ctree merge associative 1 w ys1 ys2 ctree valid w ys1 ys2 ctree flatten w ys1 ys2 ctree merge w ys1 ys2 ctree merge ctree merge w ys1 ys2 Proof intros Hw revert w Hw ys1 ys2 refine ctree valid ind alt simpl intros f equal auto using seps associative intros τ ws IH ys1 ys2 Hys Hys f equal revert ys1 ys2 Hys Hys induction IH intros simplifier f equal auto intros t wxss IH Hwxss ys1 ys2 Hys Hys f equal revert ys1 ys2 Hys Hys induction IH as intros simplifier f equal auto using seps associative with f equal intros simplifier f equal auto using seps associative intros f equal auto using seps associative Qed Lemma ctree merge associative 2 w1 w2 ys w1 w2 ctree flatten w1 w2 ys ctree merge w1 w2 ys w1 ctree merge w2 ys Proof intros Hw revert w1 w2 Hw ys refine ctree disjoint ind alt simpl intros f equal auto using seps associative rev intros τ ws1 ws2 Hws IH ys Hys f equal revert ys Hys induction IH intros simplifier f equal auto intros t wxss1 wxss2 Hws IH Hxss ys Hys f equal revert ys Hys induction IH as intros simplifier f equal auto using seps associative rev with f equal intros simplifier f equal auto using seps associative rev intros f equal auto using seps associative rev intros t i xs1 w2 xs2 rewrite Forall2 app inv r intros xs1 xs1 Hxs1 Hxs1 rewrite Forall app intros ys simplifier rewrite Forall2 app inv l intros ys1 ys2 Hys1 Hys2 assert xs1 ys1 by eauto assert ctree flatten w2 ys1 xs1 apply seps disjoint move r auto rewrite seps commutative by done by apply seps disjoint move l simplifier by rewrite seps permute ctree merge associative 1 seps commutative xs1 by eauto using seps disjoint move l intros simplifier by rewrite ctree merge associative 1 seps associative rev by eauto using seps disjoint move l Qed Lemma ctree associative 2 w1 w2 w3 w1 w2 w1 w2 w3 w1 w2 w3 w1 w2 w3 Proof intros Hw12 revert w1 w2 Hw12 w3 refine ctree disjoint ind alt simpl intros τ b xs1 xs2 w3 Hw3 pattern w3 apply ctree disjoint inv l Hw3 intros xs3 simpl f equal auto using seps associative rev intros τ ws1 ws2 IH w3 Hw3 pattern w3 apply ctree disjoint inv l Hw3 clear w3 Hw3 simpl intros ws3 Hws3 f equal revert ws3 Hws3 induction IH intros simplifier f equal auto intros t wxss1 wxss2 IH Hwxss w3 Hw3 pattern w3 apply ctree disjoint inv l Hw3 clear w3 Hw3 simpl intros wxss3 Hwxss3 Hwxss3 f equal revert wxss3 Hwxss3 Hwxss3 induction IH as intros simplifier f equal auto using seps associative rev with f equal intros t i w1 w2 xs1 xs2 IH Hxs w3 Hw3 pattern w3 apply ctree disjoint inv l Hw3 clear w3 Hw3 simpl intros f equal auto using seps associative rev intros xs3 simplifier f equal auto using ctree merge associative 2 seps associative rev intros t xs1 xs2 w3 Hw3 pattern w3 apply ctree disjoint inv l Hw3 clear w3 Hw3 simpl intros f equal auto using seps associative rev intros i w3 xs3 rewrite Forall2 app inv r intros xs12 xs12 Hxs12 apply zip with app inv in Hxs12 destruct Hxs12 as xs1 xs2 xs1 xs2 simplifier assert xs2 ctree flatten w3 by eauto assert ctree flatten w3 xs2 xs1 apply seps disjoint move r auto by rewrite seps commutative assert xs3 xs2 xs1 by by rewrite seps commutative simplifier rewrite ctree merge associative 1 seps associative rev seps commutative xs1 seps commutative xs1 eauto using seps disjoint move l seps disjoint move r intros t i xs1 w2 xs2 rewrite Forall2 app inv r intros xs1 xs1 w3 Hw3 pattern w3 apply ctree disjoint inv l Hw3 clear w3 Hw3 simpl intros w3 xs3 simplifier intros assert w2 w3 by eauto using ctree merge disjoint l rewrite ctree commutative w2 by done assert ctree flatten w3 w2 xs1 rewrite ctree flatten union by done apply seps disjoint move r auto rewrite ctree flatten merge by done eauto using ctree flatten disjoint simplifier by rewrite seps permute ctree merge associative 2 ctree commutative by eauto intros xs3 simplifier rewrite Forall2 app inv l intros xs3 xs3 assert ctree flatten w2 xs3 by eauto assert ctree flatten w2 xs3 xs1 rewrite seps commutative by eauto eauto using seps disjoint move r simplifier by rewrite ctree merge associative 1 seps commutative xs1 seps permute by eauto using seps disjoint move l intros t i w1 xs1 xs2 rewrite Forall2 app inv l intros xs2 xs2 w3 Hw3 pattern w3 apply ctree disjoint inv l Hw3 clear w3 Hw3 simpl intros w3 xs3 simplifier intros assert w1 w3 by eauto using ctree merge disjoint l assert ctree flatten w3 xs2 apply seps disjoint rr with ctree flatten w1 auto rewrite ctree flatten merge by done eauto using ctree flatten disjoint assert ctree flatten w3 w1 xs2 rewrite ctree flatten union by done apply seps disjoint move r auto rewrite ctree flatten merge by done eauto using ctree flatten disjoint assert ctree flatten w1 w3 xs2 by by rewrite ctree commutative simplifier by rewrite seps associative rev seps commutative xs2 ctree commutative w3 ctree merge associative 2 ctree commutative w3 by eauto intros simplifier by rewrite ctree merge associative 1 seps associative rev by eauto using seps disjoint move l Qed Lemma ctree associative w1 w2 w3 w2 w3 w1 w2 w3 w1 w2 w3 w1 w2 w3 Proof intros assert w1 w2 symmetry by apply ctree disjoint ll with w3 assert w1 w2 w3 symmetry rewrite ctree commutative by done by apply ctree disjoint move l rewrite 1 ctree commutative by done by rewrite ctree associative 2 by done Qed Lemma ctree cancel empty l w1 w2 w1 w2 w1 w2 w2 ctree empty w1 Proof revert w1 w2 refine ctree disjoint ind alt simpl intros simplifier eauto using seps cancel empty l intros τ ws1 ws2 IH simplify equality induction IH simplifier auto intros t wxss1 wxss2 IH simplifier induction IH as simplifier eauto 6 using seps cancel empty l intros simplifier eauto using seps cancel empty l intros simplifier eauto using seps cancel empty l intros t i xs1 w2 xs2 simplifier apply Forall app 2 eauto using seps cancel empty r apply seps cancel empty r with ctree flatten w2 auto rewrite ctree flatten merge by done congruence done Qed Lemma ctree cancel empty r w1 w2 w1 w2 w1 w2 w1 ctree empty w2 Proof intros rewrite ctree commutative by done by apply ctree cancel empty l Qed Lemma ctree merge cancel 1 w ys1 ys2 ctree flatten w ys1 ctree flatten w ys2 ctree merge w ys1 ctree merge w ys2 ys1 ys2 Proof revert w ys1 ys2 refine ctree ind alt simpl by intros simplifier intros τ ws IH ys1 ys2 rewrite injective iff MArray τ revert ys1 ys2 induction IH intros simplifier f equal auto intros t wxss IH ys1 ys2 rewrite injective iff MStruct t revert ys1 ys2 induction IH as intros simplifier repeat f equal eauto intros simplifier f equal eauto by

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


  • Module cmap
    ctree valid w ctree empty w cmap elem Forall True λ w ctree valid w ctree empty w m1 m2 sep splittable m let m m in map Forall λ cmap elem Forall False λ w ctree valid w ctree empty w ctree splittable w m sep subseteq m1 m2 let m1 m1 in let m2 m2 in map Forall2 cmap elem Forall2 True λ w1 w2 w1 w2 ctree empty w1 λ False cmap elem Forall True λ w ctree valid w ctree empty w m1 m2 sep unmapped m cmap car m sep unshared m False Proof intros apply intros apply intros apply solve decision intros apply Defined Instance cmap sep K A Set k1 k2 K Decision k1 k2 Separation A Separation cmap K A Proof split destruct sep inhabited A as x generalize String EmptyString tag intros t eexists CMap fresh Obj MUnionAll t x false split by intro intros o w simplify map equality split by constructor rewrite Forall singleton inversion clear 1 decompose Forall hyps eauto using sep unmapped empty sep unfold intros m1 m2 Hm o w1 specialize Hm o simpl in intros Hx rewrite Hx in Hm destruct w1 m2 o as simpl in intuition eauto using ctree disjoint valid l sep unfold intros m1 m2 Hm o w specialize Hm o simpl in rewrite lookup union with intros destruct m1 o as m2 o as simplify equality intuition eauto using ctree union valid ctree positive l sep unfold intros m Hm o specialize Hm o simplify map equality destruct m o as eauto sep unfold intros m f equal by rewrite left id L sep unfold intros m1 m2 Hm o specialize Hm o simpl in destruct m1 o as m2 o as simpl in intuition sep unfold intros m1 m2 Hm f equal apply union with commutative intros o specialize Hm o simplify option equality intuition auto using ctree commutative with f equal sep unfold intros m1 m2 m3 Hm Hm o specialize Hm o specialize Hm o simpl in rewrite lookup union with in Hm destruct m1 o as eqn m2 o as m3 o as simplify equality intuition eauto using ctree disjoint valid l ctree disjoint ll sep unfold intros m1 m2 m3 Hm Hm o specialize Hm o specialize Hm o simpl in rewrite lookup union with in Hm destruct m1 o as eqn m2 o as m3 o as simplify equality intuition eauto using ctree disjoint valid l ctree disjoint move l ctree union valid ctree positive l ctree disjoint lr sep unfold intros m1 m2 m3 Hm Hm f equal apply map eq intros o specialize Hm o specialize Hm o simpl in rewrite lookup union with rewrite lookup union with in Hm destruct m1 o as eqn m2 o as m3 o as simplify equality eauto f equal intuition auto using ctree associative with f equal sep unfold intros m1 m2 rewrite injective iff CMap intros Hm apply map eq intros o rewrite lookup

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

  • Module memory_basics
    nat lockset λ oi dexist oi 1 oi 2 Next Obligation intros o ω rewrite lookup singleton Some intros apply non empty singleton L Qed Program Instance lockset union Union lockset λ Ω1 Ω2 let Ω1 H Ω1 Ω1 in let Ω2 H Ω2 Ω2 in dexist union with λ ω1 ω2 Some ω1 ω2 Ω1 Ω2 Next Obligation apply bool decide unpack in H Ω1 apply bool decide unpack in H Ω2 intros n ω rewrite lookup union with Some intros ω1 ω2 simplify equality eauto apply collection positive l alt L eauto Qed Program Instance lockset intersection Intersection lockset λ Ω1 Ω2 let Ω1 H Ω1 Ω1 in let Ω2 H Ω2 Ω2 in dexist intersection with λ ω1 ω2 let ω ω1 ω2 in guard ω Some ω Ω1 Ω2 Next Obligation apply bool decide unpack in H Ω1 apply bool decide unpack in H Ω2 intros n ω rewrite lookup intersection with Some intros ω1 ω2 simplify option equality eauto Qed Program Instance lockset difference Difference lockset λ Ω1 Ω2 let Ω1 H Ω1 Ω1 in let Ω2 H Ω2 Ω2 in dexist difference with λ ω1 ω2 let ω ω1 ω2 in guard ω Some ω Ω1 Ω2 Next Obligation apply bool decide unpack in H Ω1 apply bool decide unpack in H Ω2 intros n ω rewrite lookup difference with Some intros ω1 ω2 simplify option equality eauto Qed Instance lockset elems Elements index nat lockset λ Ω let Ω Ω in map to list Ω λ o ω pair o ω 1 elements o ω 2 natset Lemma lockset eq Ω1 Ω2 lockset Ω1 Ω2 o i o i Ω1 o i Ω2 Proof revert Ω1 Ω2 cut Ω1 Ω2 indexmap natset ω o o i ω Ω1 o Some ω i ω ω Ω2 o Some ω i ω map Forall λ Ω1 Ω1 o Some ω Ω2 o Some ω intros help Ω1 Ω2 split by intros destruct Ω1 as Ω1 H Ω1 Ω2 as Ω2 H Ω2 unfold elem of lockset elem of simpl intros apply dsig eq simpl apply map eq intros o apply bool decide unpack in H Ω1 apply bool decide unpack in H Ω2 by apply option eq split apply help intros Ω1 Ω2 ω o Hoi destruct collection choose L ω as i eauto destruct proj1 Hoi o i as ω Ho eauto rewrite Ho f equal apply elem of equiv L intros j split intros by destruct proj2 Hoi o j as eauto simplify equality by destruct proj1 Hoi o j as eauto simplify equality Qed Instance lockset elem of dec oi Ω lockset Decision oi Ω 1 Proof refine match Ω oi 1 as m ω return Decision ω m ω Some ω oi 2 ω with Some ω cast if decide oi 2 ω None right end abstract naive solver Defined Instance FinCollection index nat lockset Proof split split split intros simplify map equality unfold elem of lockset elem of singleton lockset

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

  • Module references
    r τ σ Γ Γ r τ σ Γ τ Γ σ Proof intro induction 1 eauto using ref seg typed type valid Qed Global Instance PathTypeCheckSpecUnique env K type K type K ref seg K λ True Proof split intros Γ rs τ σ split by destruct 1 simplify option equality destruct rs τ as intros simplify option equality econstructor eauto by destruct 2 inversion 1 Qed Global Instance PathTypeCheckSpecUnique env K type K type K ref K λ True Proof split intros Γ r τ σ split revert σ induction r as rs r IH intros σ rewrite ref lookup nil intros simplify equality constructor rewrite ref lookup cons ref typed cons bind Some intros σ exists σ split auto by apply path type check correct induction 1 done rewrite ref lookup cons simplify option equality by apply path type check complete intros Γ r τ1 τ2 σ Hr revert τ2 induction Hr as r rs σ1 σ2 σ3 IH using ref typed ind intros τ1 by rewrite ref typed nil rewrite ref typed cons intros τ2 apply IH by rewrite path typed unique l Γ rs σ2 τ2 σ3 by done Qed Lemma ref seg typed weaken Γ1 Γ2 rs τ σ Γ1 rs τ σ Γ1 Γ2 Γ2 rs τ σ Proof destruct 1 econstructor eauto using lookup compound weaken Qed Lemma ref typed weaken Γ1 Γ2 r τ σ Γ1 r τ σ Γ1 Γ2 Γ2 r τ σ Proof intros Hr induction Hr using ref typed ind econstructor eauto using ref seg typed weaken Qed Lemma ref lookup weaken Γ1 Γ2 r τ σ τ Γ1 r Some σ Γ1 Γ2 τ Γ2 r Some σ Proof rewrite path type check correct by done by apply ref typed weaken Qed Lemma ref seg typed inv base Γ τ b rs σ Γ rs baseT τ b σ Proof inversion 1 Qed Lemma ref typed inv base Γ τ b r σ Γ r baseT τ b σ σ baseT τ b r Proof destruct r as rs r using rev ind by rewrite ref typed nil rewrite ref typed snoc intros Hrs edestruct ref seg typed inv base eauto Qed Lemma ref seg typed size Γ τ rs σ Γ rs τ σ ref seg offset rs ref seg size rs Proof destruct 1 auto with lia Qed Lemma ref typed size Γ τ r σ Γ r τ σ ref offset r ref size r Proof destruct 1 csimpl eauto using ref seg typed size Qed Lemma ref set offset length r i length ref set offset i r length r Proof by destruct r Qed Lemma ref seg size set offset i rs ref seg size ref seg set offset i rs ref seg size rs Proof by destruct rs Qed Lemma ref size set offset i r ref size ref set offset i r ref size r Proof destruct r simpl auto using ref seg size set offset Qed Lemma ref seg offset set offset rs i i ref seg size rs ref seg offset ref seg set offset i rs i Proof destruct rs simpl in auto with lia Qed Lemma ref offset set offset r i i ref size r ref offset ref set offset i r i Proof destruct r simpl auto using ref seg offset set offset with lia Qed Lemma ref offset base nil r ref base r ref offset r 0 Proof by destruct r Qed Lemma ref seg set offset typed Γ τ rs σ i i ref seg size rs Γ rs τ σ Γ ref seg set offset i rs τ σ Proof destruct 2 econstructor eauto Qed Lemma ref set offset typed Γ τ r σ i i ref size r Γ r τ σ Γ ref set offset i r τ σ Proof destruct 2 econstructor eauto using ref seg set offset typed Qed Lemma ref seg set offset offset rs ref seg set offset ref seg offset rs rs rs Proof by destruct rs Qed Lemma ref set offset offset r ref set offset ref offset r r r Proof destruct r f equal auto using ref seg set offset offset Qed Lemma ref set offset set offset r i j ref set offset i ref set offset j r ref set offset i r Proof by destruct r as Qed Lemma ref set offset typed unique Γ τ r σ1 σ2 i Γ r τ σ1 Γ ref set offset i r τ σ2 σ1 σ2 Proof destruct r as rs r simpl rewrite ref typed nil congruence rewrite ref typed cons intros τ1 Hrs1 τ2 Hrs2 simplify type equality by destruct Hrs1 inversion Hrs2 simplify option equality Qed Lemma size of ref Γ τ r σ Γ Γ r τ σ size of Γ σ ref size r size of Γ τ Proof intros induction 1 as r rs τ1 τ2 τ3 Hrs Hr IH using ref typed ind simpl lia transitivity size of Γ τ2 ref size r done apply ref typed size in Hr destruct Hrs as τ i n s i τ s τ s i τ s τ simpl rewrite Nat mul 1 r size of Γ τ n size of array apply Nat mul le mono auto with lia apply Nat mul le mono eauto using size of struct lookup with lia apply Nat mul le mono eauto using size of union lookup with lia Qed Lemma size of ref Γ τ r σ Γ Γ r τ σ size of Γ σ size of Γ τ Proof intros Hr rewrite Nat mul 1 r size of Γ σ transitivity size of Γ σ ref size r auto using size of ref apply ref typed size in Hr apply Nat mul le mono l lia Qed Global Instance PreOrder subseteqE env K type K Γ Proof intros Γ repeat split eexists constructor intros r1 r2 exists r1 r2 apply ref typed app eauto Qed Lemma ref typed subtype Γ τ r1 r2 σ1 σ2 Γ r1 τ σ1 Γ r2 τ σ2 r1 suffix of r2 σ2 Γ σ1 Proof intros Hr1 Hr2 r rewrite ref typed app in Hr2 destruct Hr2 as σ simplify type equality by exists r Qed Lemma subtype weaken Γ Σ σ τ σ Γ τ Γ Σ σ Σ τ Proof intros r exists r eauto using ref typed weaken Qed Lemma ref seg freeze freeze β1 β2 rs freeze β1 freeze β2 rs freeze β1 rs Proof by destruct rs Qed Lemma ref freeze freeze β1 β2 r freeze β1 freeze β2 r freeze β1 r Proof rewrite list fmap compose apply list fmap ext simpl auto using ref seg freeze freeze Qed Lemma ref seg freeze le l rs freeze true rs rs Proof by destruct rs constructor Qed Lemma ref freeze le l r freeze true r r Proof induction r simpl auto using ref seg freeze le l Qed Lemma ref seg freeze le r rs rs freeze false rs Proof by destruct rs constructor Qed Lemma ref freeze le r r r freeze false r Proof induction r simpl auto using ref seg freeze le r Qed Lemma ref seg freeze le β rs1 rs2 rs1 rs2 freeze β rs1 freeze β rs2 Proof by destruct 1 Qed Lemma ref freeze le β r1 r2 r1 r2 freeze β r1 freeze β r2 Proof induction 1 f equal eauto using ref seg freeze le Qed Global Instance PartialOrder subseteq ref seg K Proof repeat split by intros constructor destruct 1 inversion 1 constructor auto destruct 1 inversion 1 f equal by apply eq bool prop intro Qed Lemma ref seg typed le Γ rs1 rs2 τ σ Γ rs1 τ σ rs1 rs2 Γ rs2 τ σ Proof destruct 1 inversion 1 econstructor eauto Qed Lemma ref typed le Γ r1 r2 τ σ Γ r1 τ σ r1 r2 Γ r2 τ σ Proof intros Hr1 revert r2 induction Hr1 using ref typed ind intros decompose Forall hyps typed constructor eauto using ref seg typed le Qed Lemma ref seg typed ge Γ rs1 rs2 τ σ Γ rs2 τ σ rs1 rs2 Γ rs1 τ σ Proof destruct 1 inversion 1 econstructor eauto Qed Lemma ref typed ge Γ r1 r2 τ σ Γ r2 τ σ r1 r2 Γ r1 τ σ Proof intros Hr2 revert r1 induction Hr2 using ref typed ind intros decompose Forall hyps typed constructor eauto using ref seg typed ge Qed Lemma ref seg typed freeze Γ β τ rs σ Γ freeze β rs τ σ Γ rs τ σ Proof destruct β split eauto using ref seg typed ge ref seg typed le ref seg freeze le l ref seg freeze le r Qed Lemma ref typed freeze Γ β τ r σ Γ freeze β r τ σ Γ r τ σ Proof destruct β split eauto using ref typed ge ref typed le ref freeze le l ref freeze le r Qed Lemma ref offset le r1 r2 r1 r2 ref offset r1 ref offset r2 Proof by destruct 1 as Qed Lemma ref size le r1 r2 r1 r2 ref size r1 ref size r2 Proof by destruct 1 as Qed Lemma ref frozen le r1 r2 r1 r2 freeze true r2 r2 freeze true r1 r1 Proof induction 1 as intros simplify equality f equal tauto Qed Lemma ref le unique r1 r2 r3 r1 r2 r1 r3 freeze true r2 freeze true r3 Proof intros transitivity freeze true r1 auto using ref freeze le eq sym Qed Lemma ref le unique alt r1 r2 r3 r1 r2 r1 r3 freeze true r2 r2 freeze true r3 r3 r2 r3 Proof intros eauto using ref le unique Qed Lemma ref seg set offset le rs1 rs2 i rs1 rs2 ref seg set offset i rs1 ref seg set offset i rs2 Proof by destruct 1 constructor Qed Lemma ref set offset le r1 r2 i r1 r2 ref set offset i r1 ref set offset i r2 Proof destruct 1 constructor auto using ref seg set offset le Qed Lemma ref seg offset freeze β rs ref seg offset freeze β rs ref seg offset rs Proof by destruct rs Qed Lemma ref offset freeze β r ref offset freeze β r ref offset r Proof destruct r simpl auto using ref seg offset freeze Qed Lemma ref seg set offset freeze β rs i ref seg set offset i freeze β rs freeze β ref seg set offset i rs Proof by destruct rs Qed Lemma ref set offset freeze β r i ref set offset i freeze β r freeze β ref set offset i r Proof destruct r f equal auto using ref seg set offset freeze Qed Lemma ref seg size freeze β rs ref seg size freeze β rs ref seg size rs Proof by destruct rs Qed Lemma ref size freeze β r ref size freeze β r ref size r Proof destruct r simpl auto using ref seg size freeze Qed Lemma ref seg object offset freeze Γ β rs ref seg object offset Γ freeze β rs ref seg object offset Γ rs Proof by destruct rs Qed Lemma ref object offset freeze Γ β r ref object offset Γ freeze β r ref object offset Γ r Proof unfold ref object offset induction r f equal auto using ref seg object offset freeze Qed Lemma ref object offset le Γ r1 r2 r1 r2 ref object offset Γ r1 ref object offset Γ r2 Proof intros rewrite ref object offset freeze Γ false r1 ref object offset freeze Γ false r2 f equal auto using ref freeze le Qed Lemma ref disjoint app l r1 r1 r2 r1 r2 r1 r1 r2 Proof induction r1 simpl auto using ref disjoint cons l Qed Lemma ref disjoint app r r2 r1 r2 r1 r2 r1 r2 r2 Proof induction r2 simpl auto using ref disjoint cons r Qed Lemma ref disjoint app r1 r2 r1 r2 r1 r2 r1 r1 r2 r2 Proof auto using ref disjoint app l ref disjoint app r Qed Lemma ref disjoint here app 1 r1 r2 r1 r2 r1 r2 freeze true r1 freeze true r2 r1 r1 r2 r2 Proof induction 1 simpl constructor rewrite fmap app auto with f equal Qed Global Instance Symmetric disjoint ref seg K Proof destruct 1 constructor auto Qed Global Instance Symmetric disjoint ref K Proof induction 1 constructor by auto Qed Lemma ref disjoint alt r1 r2 r1 r2 r1 rs1 r1 r2 rs2 r2 r1 r1 rs1 r1 r2 r2 rs2 r2 rs1 rs2 freeze true r1 freeze true r2 Proof split induction 1 as rs1 rs2 r1 r2 rs1 r1 r2 r1 rs1 r1 r2 rs2 r2 rs2 r1 r2 r1 rs1 r1 r2 rs2 r2 by eexists rs1 r1 rs2 r2 by eexists rs1 r1 rs1 r1 r2 rs2 r2 by eexists r1 rs1 r1 rs2 r2 rs2 r2 intros r1 rs1 r1 r2 rs2 r2 apply ref disjoint app by constructor Qed Lemma ref disjoint snoc r1 r2 rs1 rs2 r1 rs1 r2 rs2 rs1 rs2 r1 r2 freeze true rs1 freeze true rs2 Proof split rewrite ref disjoint alt intros r1 rs1 r1 r2 rs2 r2 Hr1 Hr2 Hr destruct r1 as rs1 r1 using rev ind destruct r2 as rs2 r2 using rev ind simplify list equality by left rewrite fmap app in Hr by discriminate list equality rewrite fmap app in Hr by discriminate list equality simplify list equality right split by apply ref disjoint app constructor done intros Hr rewrite ref disjoint alt naive solver by apply ref disjoint here app 1 f equal Qed Lemma ref disjoint singleton rs1 rs2 rs1 rs2 rs1 rs2 Proof rewrite ref disjoint alt split by intros simplify list equality try discriminate list equality intros by eexists rs1 rs2 Qed Lemma ref disjoint nil inv l r r Proof rewrite ref disjoint alt intros simplify list equality discriminate list equality Qed Lemma ref disjoint nil inv r r r Proof intros by apply ref disjoint nil inv l r Qed Global Instance Irreflexive disjoint ref seg K Proof by inversion 1 Qed Lemma ref disjoint app inv l r1 r2 r1 r2 r2 Proof rewrite ref disjoint alt intros r1 rs1 r1 r2 rs2 r2 Hr Hrs Hr simplify list equality by destruct irreflexivity rs1 Qed Lemma ref disjoint app inv r r1 r2 r2 r1 r2 Proof intros by destruct ref disjoint app inv l r1 r2 Qed Global Instance Irreflexive disjoint ref K Proof intros r by destruct ref disjoint app inv l r Qed Lemma ref disjoint here app 2 r1 r2 r r1 r r2 r r1 r2 Proof induction r as rs r IH using rev ind by rewrite right id L rewrite associative L ref disjoint snoc intros auto by destruct irreflexivity rs Qed Lemma ref disjoint here app r1 r2 r r1 r2 r1 r r2 r Proof split eauto using ref disjoint here app 2 intros by apply ref disjoint here app 1 Qed Lemma ref seg disjoint le rs1 rs2 rs3 rs4 rs1 rs2 rs1 rs3 rs2 rs4 rs3 rs4 Proof by destruct 1 do 2 inversion 1 constructor Qed Lemma ref disjoint le r1 r2 r3 r4 r1 r2 r1 r3 r2 r4 r3 r4 Proof rewrite ref disjoint alt intros r1 rs1 r1 r2 rs2 r2 decompose Forall hyps apply ref disjoint app ref disjoint here eauto using ref seg disjoint le transitivity freeze true r1 auto using ref freeze le eq sym transitivity freeze true r2 auto using ref freeze le eq sym Qed Lemma ref seg disjoint ge rs1 rs2 rs3 rs4 rs3 rs4 rs1 rs3 rs2 rs4 rs1 rs2 Proof by destruct 1 do 2 inversion 1 constructor Qed Lemma ref disjoint ge r1 r2 r3 r4 r3 r4 r1 r3 r2 r4 r1 r2 Proof rewrite ref disjoint alt intros r3 rs3 r3 r4 rs4 r4 decompose Forall hyps apply ref disjoint app ref disjoint here eauto using ref seg disjoint ge transitivity freeze true r3 auto using ref freeze le eq sym transitivity freeze true r4 auto using ref freeze le eq sym Qed Global Instance ref seg disjoint dec rs1 rs2 Decision rs1 rs2 Proof refine match rs1 rs2 with RArray i τ1 n1 RArray j τ2 n2 cast if decide n1 n2 τ1 τ2 i j RStruct i t1 RStruct j t2 cast if decide t1 t2 i j right end abstract first intuition subst by constructor inversion 1 intuition Defined Inductive ref disjoint rev ref K ref K Prop ref disjoint rev here rs1 rs2 r1 r2 rs1 rs2 ref disjoint rev rs1 r1 rs2 r2 ref disjoint rev cons rs1 rs2 r1 r2 freeze true rs1 freeze true rs2 ref disjoint rev r1 r2 ref disjoint rev rs1 r1 rs2 r2 Global Instance ref disjoint rev dec r1 r2 Decision ref disjoint rev r1 r2 Proof refine fix go r1 r2 match r1 r2 return Decision ref disjoint rev r1 r2 with rs1 r1 rs2 r2 if decide rs1 rs2 then left else cast if and decide freeze true rs1 freeze true rs2 go r1 r2 right end clear go abstract first subst constructor by auto inversion 1 auto Defined Lemma ref disjoint rev correct 1 r1 r2 ref disjoint rev r1 r2 reverse r1 reverse r2 Proof induction 1 as rs1 r1 r2 rewrite reverse cons by apply ref disjoint app ref disjoint singleton by apply ref disjoint here app 1 f equal Qed Lemma ref disjoint rev correct 2 r1 r2 r1 r2 ref disjoint rev reverse r1 reverse r2 Proof rewrite ref disjoint alt intros r1 rs1 r1 r2 rs2 r2 Hr rewrite reverse app reverse singleton associative L simpl apply f equal reverse in Hr rewrite fmap

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

  • Module addresses
    of freeze β a type of freeze β a type of a Proof by destruct a Qed Lemma addr ref freeze Γ β a addr ref Γ freeze β a freeze β addr ref Γ a Proof unfold addr ref by rewrite addr ref base freeze addr byte freeze addr type base freeze ref set offset freeze Qed Lemma addr is obj freeze β a addr is obj freeze β a addr is obj a Proof unfold addr is obj by rewrite addr type of freeze addr type base freeze Qed Lemma addr is obj freeze 2 β a addr is obj a addr is obj freeze β a Proof by rewrite addr is obj freeze Qed Lemma addr strict freeze Γ β a addr strict Γ freeze β a addr strict Γ a Proof unfold addr strict by rewrite addr byte freeze addr type base freeze addr ref base freeze ref size freeze Qed Lemma addr strict freeze 2 Γ β a addr strict Γ a addr strict Γ freeze β a Proof by rewrite addr strict freeze Qed Lemma addr ref byte freeze Γ β a addr ref byte Γ freeze β a addr ref byte Γ a Proof unfold addr ref byte by rewrite addr byte freeze addr type base freeze Qed Lemma addr typed freeze Γ Δ β a σ p Γ Δ freeze β a σ p Γ Δ a σ p Proof rewrite addr typed alt destruct a simpl by rewrite ref offset freeze ref size freeze setoid rewrite ref typed freeze Qed Lemma addr is obj ref byte Γ Δ a σ p Γ Γ Δ a σ p addr is obj a addr ref byte Γ a 0 Proof destruct 2 intros simplify equality apply Nat mod divide eauto using size of ne 0 Qed Lemma addr is obj type Γ Δ a σ Γ Δ a TType σ addr is obj a σ addr type base a Proof inversion 1 naive solver Qed Lemma addr not is obj type Γ Δ a σ Γ Δ a TType σ addr is obj a σ ucharT Proof inversion 1 match goal with H inversion H end naive solver Qed Lemma addr byte range Γ Δ a σ Γ Γ Δ a TType σ addr strict Γ a addr ref byte Γ a size of Γ σ size of Γ addr type base a Proof intros destruct decide addr is obj a by erewrite addr is obj type addr is obj ref byte by eauto erewrite addr not is obj type σ size of char by eauto rewrite Nat add 1 r Nat le succ l apply Nat mod bound pos auto with lia eapply size of pos addr typed type base valid eauto Qed Lemma addr bit range Γ Δ a σ Γ Γ Δ a TType σ addr strict Γ a addr ref byte Γ a char bits bit size of Γ σ bit size of Γ addr type base a Proof intros unfold bit size of rewrite Nat mul add distr r Nat mul le mono pos r by auto using char bits pos eauto using addr byte range Qed Lemma addr strict weaken Γ1 Γ2 m1 a σ p Γ1 Γ1 m1 a σ p addr strict Γ1 a Γ1 Γ2 addr strict Γ2 a Proof unfold addr strict intros by erewrite size of weaken by eauto using addr typed type base valid Qed Lemma addr ref weaken Γ1 Γ2 m1 a σ p Γ1 Γ1 m1 a σ p Γ1 Γ2 addr ref Γ1 a addr ref Γ2 a Proof intros simpl by erewrite size of weaken by eauto using ref typed type valid Qed Lemma addr ref byte weaken Γ1 Γ2 m1 a σ p Γ1 Γ1 m1 a σ p Γ1 Γ2 addr ref byte Γ1 a addr ref byte Γ2 a Proof intros simpl by erewrite size of weaken by eauto using ref typed type valid Qed Lemma addr object offset weaken Γ1 Γ2 Δ a σ p Γ1 Γ1 Δ a σ p Γ1 Γ2 addr object offset Γ1 a addr object offset Γ2 a Proof intros unfold addr object offset eauto using ref object offset weaken addr typed ref base typed addr typed type object valid Qed Lemma addr object offset alt Γ Δ a σ p Γ Γ Δ a σ p addr strict Γ a addr object offset Γ a ref object offset Γ addr ref Γ a addr ref byte Γ a char bits Proof intros o r i τ σ σ p Hor simpl in erewrite ref object offset set offset 0 by eauto using Nat div lt upper bound size of ne 0 ref typed type valid rewrite Nat div mod i size of Γ σ at 1 by eauto using size of ne 0 ref typed type valid unfold bit size of lia Qed Lemma align of addr object offset Γ Δ a σ Γ Γ Δ a TType σ bit align of Γ σ addr object offset Γ a Proof inversion clear 2 simplify equality apply Nat divide add r eauto using Nat mul divide mono r Nat divide trans bit align of castable align of divide castable type valid size of ne 0 bit align of ref object offset Qed Lemma addr object offset bit size Γ Δ a σ p Γ Γ Δ a σ p addr strict Γ a addr object offset Γ a ptr bit size of Γ σ p bit size of Γ addr type object a Proof destruct 2 as o r i τ σ σ p Hoff Hi Hcast intros Ha simplify equality eapply Nat le trans eapply ref object offset size eauto rewrite Nat add assoc Nat add le mono l Hoff Nat sub 0 r unfold bit size of rewrite ptr bit size of alt rewrite Nat mul assoc Nat mul add distr r rewrite Nat mul le mono pos r by auto using char bits pos destruct

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

  • Module addresses_refine
    inversion Hr destruct memenv refine perm l Γ f Δ1 Δ2 o1 τ1 as auto simplify type equality refine constructor eauto using lookup meminj inverse 2 memenv refine inverse ref typed nil 2 Qed Lemma addr refine weaken Γ Γ α α f f Δ1 Δ2 Δ1 Δ2 a1 a2 σ p Γ a1 Γ α f Δ1 Δ2 a2 σ p Γ Γ α α Δ1 Γ α f Δ2 Δ1 ₘ Δ1 meminj extend f f Δ1 Δ2 a1 Γ α f Δ1 Δ2 a2 σ p Proof destruct 2 as o1 o2 r1 r r2 i1 i2 τ1 τ2 σ σ p Hr intros refine constructor eauto using type valid weaken ref typed weaken eauto using option eq 1 alt by erewrite size of weaken by eauto using ref typed type valid destruct σ p as σ simpl auto by erewrite size of weaken by eauto using ref typed type valid castable type valid erewrite size of weaken by eauto using ref typed type valid destruct Hr α csimpl in try tauto constructor done apply ref refine id Qed Lemma addr refine unique l Γ f Δ1 Δ2 a1 a2 a3 σ p2 σ p3 a1 Γ false f Δ1 Δ2 a3 σ p2 a2 Γ false f Δ1 Δ2 a3 σ p3 a1 a2 Proof destruct 1 as o1 o2 r r2 r3 i i3 τ τ2 σ σ p Hr inversion 1 as o1 o2 r r2 i τ Hr inversion Hr inversion Hr simplify equality destruct meminj injective alt f o1 o1 o2 as eauto using memenv refine injective simplify type equality auto by destruct ref disjoint nil inv l nil ref seg K Qed Lemma addr refine unique r Γ α f Δ1 Δ2 a1 a2 a3 σ p2 σ p3 a1 Γ α f Δ1 Δ2 a2 σ p2 a1 Γ α f Δ1 Δ2 a3 σ p3 frozen a2 frozen a3 a2 a3 Proof unfold frozen destruct 1 as Hr1 inversion 1 as Hr2 destruct Hr1 inversion Hr2 intros simplify type equality f equal eauto using ref le unique alt Qed Lemma addr freeze refine l Γ Δ a σ p Γ Δ a σ p freeze true a Γ true Δ a σ p Proof destruct 1 eexists csimpl auto using memenv refine id by apply ref typed nil eauto using ref typed ge ref freeze le l by rewrite ref offset freeze by rewrite ref size freeze destruct decide r as constructor simpl auto with lia constructor rewrite right id L auto using ref freeze le l by destruct r Qed Lemma addr freeze refine Γ α f Δ1 Δ2 a1 a2 σ p a1 Γ α f Δ1 Δ2 a2 σ p freeze true a1 Γ α f Δ1 Δ2 freeze true a2 σ p Proof destruct 1 as o1 o2 r1 r r2 i1 i2 τ1 τ2 σ σ p H Δ Hr csimpl refine constructor eauto by apply ref typed freeze by rewrite ref offset freeze by rewrite ref size freeze destruct Hr as r1 i1 r2 i2 r1 r1 r2 i constructor auto erewrite memenv refine frozen H Δ r1 by eauto by erewrite ref set offset freeze ref freeze le by eauto erewrite memenv refine frozen H Δ r1 fmap app by eauto by erewrite ref freeze le by eauto by destruct r1 Qed Lemma addr ref refine Γ α f Δ1 Δ2 a1 a2 σ p a1 Γ α f Δ1 Δ2 a2 σ p addr strict Γ a1 r f addr index a1 Some addr index a2 r Γ r addr type object a2 addr type object a1 addr ref Γ a1 r addr ref Γ a2 Proof destruct 1 as o1 o2 r1 r r2 i1 i2 τ1 τ2 σ Hr intros simplify equality exists r split ands auto destruct Hr as r1 i1 r2 i2 r1 r1 r2 i simplify type equality auto by rewrite right id L rewrite Nat mul comm Nat div add Nat div small Nat add 0 l by lia rewrite ref set offset offset r1 at 1 rewrite ref set offset set offset r1 0 auto using ref set offset le destruct r1 decompose Forall hyps constructor auto using Forall2 app ref seg set offset le Qed Lemma addr ref byte refine Γ α f Δ1 Δ2 a1 a2 σ p a1 Γ α f Δ1 Δ2 a2 σ p addr strict Γ a1 addr ref byte Γ a1 addr ref byte Γ a2 Proof destruct 1 as o1 o2 r1 r r2 i1 i2 τ1 τ2 σ Hr intros destruct Hr simplify equality auto by rewrite Nat mul comm Nat mod add by lia Qed Lemma addr is obj refine Γ α f Δ1 Δ2 a1 a2 σ p a1 Γ α f Δ1 Δ2 a2 σ p addr is obj a1 addr is obj a2 Proof by destruct 1 Qed Lemma addr disjoint refine Γ α α f Δ1 Δ2 a1 a2 a3 a4 σ p1 σ p3 Γ meminj injective f addr strict Γ a1 addr strict Γ a3 a1 Γ α f Δ1 Δ2 a2 σ p1 a3 Γ α f Δ1 Δ2 a4 σ p3 a1 Γ a3 a2 Γ a4 Proof intros destruct addr ref refine Γ α f Δ1 Δ2 a1 a2 σ p1 as r1 Hf1 Hr1 auto destruct addr ref refine Γ α f Δ1 Δ2 a3 a4 σ p3 as r2 Hf2 Hr2 auto intros Hidx Hidx Ha edestruct meminj injective ne f addr index a1 addr index a2 as eauto by left right left eauto using ref disjoint le ref disjoint app rewrite Hidx in Hf1 simplify option equality right left eauto using ref disjoint le ref disjoint here app 1 rewrite Hidx in Hf1 simplify option equality do 2 right split done erewrite addr ref byte refine a1 a2 addr ref byte refine a3 a4 addr is obj refine a1 a2 addr is obj refine a3 a4 by eauto split ands auto transitivity

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

  • Module pointers
    of a FunPtr τ s τ τ s τ end Global Instance ptr type check TypeCheck env K memenv K ptr type K ptr K λ ΓΔ p let Γ Δ ΓΔ in match p with NULL τ p guard Γ τ p Some τ p Ptr a type check Γ Δ a FunPtr f τ s τ τ s τ Γ f guard τ s τ s guard τ τ Some τ s τ end Inductive is NULL ptr K Prop mk is NULL τ is NULL NULL τ Definition ptr alive Δ memenv K p ptr K Prop match p with Ptr a index alive Δ addr index a True end End pointer operations Section pointers Context EnvSpec K Implicit Types Γ env K Implicit Types Δ memenv K Implicit Types τ p ptr type K Implicit Types a addr K Implicit Types p ptr K Lemma Ptr typed inv Γ Δ a τ p Γ Δ Ptr a τ p Γ Δ a τ p Proof by inversion 1 Qed Global Instance Injective Ptr K Proof by injection 1 Qed Lemma ptr typed type valid Γ Δ p τ p Γ Γ Δ p τ p Γ τ p Proof destruct 2 eauto using addr typed ptr type valid TFun ptr valid env valid args valid env valid ret valid type valid ptr type valid Qed Global Instance TypeOfSpec env K memenv K ptr type K ptr K Proof intros by destruct 1 simpl erewrite type of correct by eauto Qed Global Instance TypeCheckSpec env K memenv K ptr type K ptr K λ True Proof intros Γ Δ m p τ split destruct p intros repeat case match simplify option equality constructor auto by apply type check sound by destruct 1 simplify option equality erewrite type

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

  • Module pointers_refine
    Δ2 p1 p2 τ p p1 Γ α f Δ1 Δ2 p2 τ p type of p1 τ p Proof destruct 1 simpl eauto using addr refine type of l Qed Lemma ptr refine type of r Γ α f Δ1 Δ2 p1 p2 τ p p1 Γ α f Δ1 Δ2 p2 τ p type of p2 τ p Proof destruct 1 simpl eauto using addr refine type of r Qed Lemma ptr refine frozen Γ α f Δ1 Δ2 p1 p2 τ p p1 Γ α f Δ1 Δ2 p2 τ p frozen p2 frozen p1 Proof unfold frozen destruct 1 simpl auto rewrite injective iff Ptr eapply addr refine frozen eauto Qed Lemma ptr refine id Γ α Δ p τ p Γ Δ p τ p p Γ α Δ p τ p Proof destruct 1 constructor eauto using addr refine id Qed Lemma ptr refine compose Γ α1 α2 f1 f2 Δ1 Δ2 Δ3 p1 p2 p3 τ p τ p Γ p1 Γ α1 f1 Δ1 Δ2 p2 τ p p2 Γ α2 f2 Δ2 Δ3 p3 τ p p1 Γ α1 α2 f2 f1 Δ1 Δ3 p3 τ p Proof destruct 2 inversion clear 1 constructor eauto using addr refine compose Qed Lemma ptr refine inverse Γ f Δ1 Δ2 p1 p2 τ p p1 Γ false f Δ1 Δ2 p2 τ p p2 Γ false meminj inverse f Δ2 Δ1 p1 τ p Proof destruct 1 constructor eauto using addr refine inverse Qed Lemma ptr refine weaken Γ Γ α α f f Δ1 Δ2 Δ1 Δ2 p1 p2 τ p Γ p1 Γ α f Δ1 Δ2 p2 τ p Γ Γ α α Δ1 Γ α f Δ2 Δ1 ₘ Δ1 meminj extend f f Δ1 Δ2 p1 Γ α

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