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 pointer_bits
    bits Γ p Proof unfold ptr to bits by rewrite ptr type of freeze ptr freeze freeze Qed Lemma ptr to bits length alt Γ p length ptr to bits Γ p bit size of Γ type of p Proof unfold ptr to bits by rewrite to fragments length Qed Lemma ptr to bits length Γ Δ p τ p Γ Δ p τ p length ptr to bits Γ p bit size of Γ τ p Proof intros erewrite ptr to bits length alt type of correct eauto Qed Lemma ptr to bits valid Γ Δ p τ p Γ Δ p τ p Γ Δ ptr to bits Γ p Proof intros apply Forall to fragments intros i erewrite type of correct by eauto exists τ p simpl rewrite ptr typed freeze unfold frozen by rewrite ptr freeze freeze Qed Lemma ptr of bits Exists Forall typed Γ Δ τ p pbs is Some ptr of bits Γ τ p pbs Exists Γ Δ pbs Γ Δ pbs Proof unfold ptr of bits intros p simplify option equality rewrite of to fragments 1 p pbs by eauto unfold to fragments at 1 rewrite Exists fmap Exists exists intros i simplify type equality apply Forall to fragments eexists eauto Qed Lemma ptr of bits typed frozen Γ Δ p τ p pbs ptr of bits Γ τ p pbs Some p Γ Δ pbs Γ Δ p τ p frozen p Proof unfold ptr of bits intros simplify option equality destruct Forall of fragments bit size of Γ type of p Γ Δ p pbs 0 as eauto using type of typed by apply Nat neq 0 lt 0 bit size of base ne 0 Qed Lemma ptr of bits typed Γ Δ p τ p pbs ptr of bits Γ τ p pbs Some p Γ Δ pbs Γ Δ p τ p Proof intros eapply ptr of bits typed frozen eauto Qed Lemma ptr of bits frozen Γ Δ p τ p pbs ptr of bits Γ τ p pbs Some p Γ Δ pbs frozen p Proof intros eapply ptr of bits typed frozen eauto Qed Lemma ptr of bits type of Γ p τ p pbs ptr of bits Γ τ p pbs Some p type of p τ p Proof by unfold ptr of bits intros simplify option equality Qed Lemma ptr to of bits Γ Δ p τ p pbs ptr of bits Γ τ p pbs Some p Γ Δ pbs ptr to bits Γ p pbs Proof intros assert frozen p as Hp by eauto using ptr of bits frozen unfold ptr of bits ptr to bits in destruct of fragments eqn simplify option equality by rewrite Hp of to fragments 1 pbs by done Qed Lemma ptr of to bits Γ p ptr of bits Γ type of p ptr to bits Γ p Some freeze true p Proof unfold ptr of bits ptr to bits rewrite of to fragments

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


  • Module pointer_bits_refine
    exists τ p erewrite bit size of weaken by eauto using TBase valid TPtr valid ptr refine typed l ptr typed type valid eauto using ptr refine weaken Qed Lemma ptr bit refine valid l Γ α f Δ1 Δ2 pb1 pb2 Γ pb1 Γ α f Δ1 Δ2 pb2 Γ Δ1 pb1 Proof intros τ p exists τ p eauto using ptr refine typed l ptr refine frozen Qed Lemma ptr bit refine valid r Γ α Δ1 Δ2 f pb1 pb2 Γ pb1 Γ α f Δ1 Δ2 pb2 Γ Δ2 pb2 Proof intros τ p exists τ p eauto using ptr refine typed r with congruence Qed Lemma ptr bits refine valid l Γ α f Δ1 Δ2 pbs1 pbs2 Γ pbs1 Γ α f Δ1 Δ2 pbs2 Γ Δ1 pbs1 Proof induction 2 eauto using ptr bit refine valid l Qed Lemma ptr bits refine valid r Γ α f Δ1 Δ2 pbs1 pbs2 Γ pbs1 Γ α f Δ1 Δ2 pbs2 Γ Δ2 pbs2 Proof induction 2 eauto using ptr bit refine valid r Qed Lemma ptr bit refine unique l Γ f Δ1 Δ2 pb1 pb2 pb3 pb1 Γ false f Δ1 Δ2 pb3 pb2 Γ false f Δ1 Δ2 pb3 pb1 pb2 Proof destruct pb1 pb2 intros τ p1 τ p2 f equal eauto using ptr refine unique l with congruence Qed Lemma ptr bits refine unique l Γ f Δ1 Δ2 pbs1 pbs2 pbs3 pbs1 Γ false f Δ1 Δ2 pbs3 pbs2 Γ false f Δ1 Δ2 pbs3 pbs1 pbs2 Proof intros Hpbs revert pbs2 induction Hpbs inversion clear 1 f equal eauto using ptr bit refine unique l Qed Lemma ptr bit refine unique r Γ α f Δ1 Δ2 pb1 pb2 pb3 pb1 Γ α f Δ1 Δ2 pb2 pb1 Γ α f Δ1 Δ2 pb3 pb2 pb3 Proof destruct pb2 pb3 intros τ p1 τ p2 f equal eauto using ptr refine unique r with congruence Qed Lemma ptr bits refine unique r Γ α f Δ1 Δ2 pbs1 pbs2 pbs3 pbs1 Γ α f Δ1 Δ2 pbs2 pbs1 Γ α f Δ1 Δ2 pbs3 pbs2 pbs3 Proof intros Hpbs revert pbs3 induction Hpbs inversion clear 1 f equal eauto using ptr bit refine unique r Qed Lemma ptr to bits refine Γ α f Δ1 Δ2 p1 p2 σ p1 Γ α f Δ1 Δ2 p2 σ ptr to bits Γ p1 Γ α f Δ1 Δ2 ptr to bits Γ p2 Proof intros unfold ptr to bits to fragments erewrite ptr refine type of l ptr refine type of r by eauto apply Forall2 fmap Forall2 Forall Forall seq intros j exists σ simpl split ands unfold frozen auto using ptr freeze freeze by apply ptr freeze refine Qed Lemma ptr of bits refine Γ α f Δ1 Δ2 σ pbs1 pbs2 p1 ptr of bits Γ σ pbs1 Some p1 pbs1 Γ α f Δ1 Δ2 pbs2 p2 ptr of bits Γ σ pbs2 Some p2

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

  • Module bits
    β s bs BBit β s Proof refine cast if decide is Some mapM maybe BBit bs abstract by setoid rewrite maybe BBits spec Defined Lemma maybe BPtrs spec bs pbs mapM maybe BPtr bs Some pbs bs BPtr pbs Proof split apply mapM fmap Some inv by intros simplify equality intros by apply mapM fmap Some Qed Global Instance BPtrs dec bs Decision pbs bs BPtr pbs Proof refine cast if decide is Some mapM maybe BPtr bs abstract by setoid rewrite maybe BPtrs spec Defined Weak Refinements Global Instance PartialOrder bit weak refine K Proof repeat split intros constructor destruct 1 done constructor by destruct 1 inversion 1 Qed Lemma bits subseteq eq bs1 bs2 bs1 bs2 bs1 bs2 BIndet bs1 Proof induction 1 as IH rewrite elem of cons naive solver Qed Lemma bits subseteq indet bs1 bs2 BIndet bs1 bs2 bs1 BIndet bs2 Proof intros Hbs induction 1 as rewrite elem of cons in Hbs naive solver Qed Lemma bits subseteq indets bs1 bs2 Forall BIndet bs2 bs1 bs2 bs1 bs2 Proof induction 2 as decompose Forall hyps f equal auto Qed Lemma bit join valid Γ Δ b1 b2 b3 bit join b1 b2 Some b3 Γ Δ b1 Γ Δ b2 Γ Δ b3 Proof destruct 2 1 simplify option equality constructor auto Qed Global Instance Commutative eq option bit K bit join Proof intros intros simplify option equality auto Qed Lemma bit join indet l b bit join BIndet b Some b Proof by destruct b simplify option equality Qed Lemma bit join indet r b bit join b BIndet Some b Proof by destruct b simplify option equality Qed Lemma bit join diag b bit join b b Some b Proof by destruct b simplify option equality Qed Lemma bit join Some l b1 b2 b3 bit join b1 b2 Some b3 b1 b3 Proof destruct b1 b2 intros simplify option equality constructor Qed Lemma bit join Some r b1 b2 b3 bit join b1 b2 Some b3 b2 b3 Proof destruct b1 b2 intros simplify option equality constructor Qed Lemma bit join exists b1 b2 b4 b1 b4 b2 b4 b3 bit join b1 b2 Some b3 b3 b4 Proof destruct 1 inversion clear 1 eauto using bit join diag bit join indet l bit join indet r BIndet weak refine Qed Lemma bits join valid Γ Δ bs1 bs2 bs3 bits join bs1 bs2 Some bs3 Γ Δ bs1 Γ Δ bs2 Γ Δ bs3 Proof intros Hbs Hbs1 revert bs2 bs3 Hbs induction Hbs1 destruct 2 simplify option equality constructor eauto using bit join valid Qed Global Instance Commutative eq option list bit K bits join Proof intros bs1 induction bs1 as b1 bs1 IH intros b2 bs2 simpl try done rewrite commutative bit join by destruct bit join simpl rewrite IH Qed Lemma bits join indet l bs bits join replicate length bs BIndet bs Some bs Proof induction bs as b bs IH simpl done by rewrite

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

  • Module bits_refine
    α f Δ1 Δ2 b2 Proof destruct 2 as Hpb constructor eauto using bit valid weaken ptr bit refine weaken ptr bit valid weaken ptr dead weaken destruct Hpb as eauto using ptr dead weaken Qed Lemma BIndet refine Γ Δ1 Δ2 f b Γ Δ2 b BIndet Γ true f Δ1 Δ2 b Proof by constructor Qed Lemma BIndets refine Γ Δ1 Δ2 f bs1 bs2 Forall BIndet bs1 Γ Δ2 bs2 length bs1 length bs2 bs1 Γ true f Δ1 Δ2 bs2 Proof rewrite Forall2 same length induction 3 decompose Forall hyps repeat constructor auto Qed Lemma BIndet BIndet refine Γ α f Δ1 Δ2 BIndet Γ α f Δ1 Δ2 BIndet Proof repeat constructor Qed Lemma BBit refine Γ α f Δ1 Δ2 β BBit β Γ α f Δ1 Δ2 BBit β Proof by constructor Qed Lemma BPtr refine Γ α f Δ1 Δ2 pb1 pb2 pb1 Γ α f Δ1 Δ2 pb2 BPtr pb1 Γ α f Δ1 Δ2 BPtr pb2 Proof by constructor Qed Lemma BBits refine Γ α f Δ1 Δ2 β s BBit β s Γ α f Δ1 Δ2 BBit β s Proof induction β s constructor auto using BBit refine Qed Lemma BPtrs refine Γ α f Δ1 Δ2 pbs1 pbs2 pbs1 Γ α f Δ1 Δ2 pbs2 BPtr pbs1 Γ α f Δ1 Δ2 BPtr pbs2 Proof induction 1 constructor auto using BPtr refine Qed Lemma BIndets refine l inv Γ α f Δ1 Δ2 bs1 bs2 Forall BIndet bs1 bs1 Γ α f Δ1 Δ2 bs2 Γ Δ2 bs2 Proof induction 2 as decompose Forall hyps repeat constructor eauto Qed Lemma BIndets refine l inv Γ f Δ1 Δ2 bs1 bs2 Forall BIndet bs1 bs1 Γ false f Δ1 Δ2 bs2 Forall BIndet bs2 Proof by induction 2 as decompose Forall hyps repeat constructor eauto Qed Lemma BIndet refine r inv Γ α f Δ1 Δ2 b1 b3 b1 Γ α f Δ1 Δ2 BIndet Γ Δ2 b3 b1 Γ true f Δ1 Δ2 b3 Proof by inversion 1 constructor auto Qed Lemma BIndets refine r inv Γ α f Δ1 Δ2 bs1 bs2 bs3 bs1 Γ α f Δ1 Δ2 bs2 Forall BIndet bs2 Γ Δ2 bs3 length bs1 length bs3 bs1 Γ true f Δ1 Δ2 bs3 Proof rewrite Forall2 same length intros Hbs Hbs2 revert bs3 induction Hbs intros decompose Forall hyps eauto using BIndet refine r inv Qed Lemma BIndets refine r inv Γ f Δ1 Δ2 bs1 bs2 bs3 Forall BIndet bs2 bs1 Γ false f Δ1 Δ2 bs2 Forall BIndet bs1 Proof by induction 2 as decompose Forall hyps repeat constructor eauto Qed Lemma BBits refine inv l Γ α f Δ1 Δ2 β s bs BBit β s Γ α f Δ1 Δ2 bs bs BBit β s Proof rewrite Forall2 fmap l by induction 1 as Hb inversion Hb simplify equality Qed Lemma BBits refine inv r Γ f Δ1 Δ2 β s bs bs Γ false f Δ1 Δ2

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

  • Module permission_bits
    unmapped Qed Lemma pbit unlock mapped γ b sep valid γ b sep unmapped pbit unlock γ b sep unmapped γ b Proof destruct γ b sep unfold naive solver auto using perm unlock mapped Qed Lemma pbits kind weaken γ bs k1 k2 Forall λ γ b k2 pbit kind γ b γ bs k1 k2 Forall λ γ b k1 pbit kind γ b γ bs Proof intros eapply Forall impl eauto intros γ b by transitivity k2 Qed Lemma pbits mapped γ bs Forall λ γ b Some Readable pbit kind γ b γ bs Forall not sep unmapped γ bs Proof induction 1 as x b constructor auto intros simplify equality eapply perm mapped eauto Qed Lemma PBits unshared γ s bs Forall sep unshared γ s Forall sep unshared zip with PBit γ s bs Proof intros H γ s revert bs induction H γ s intros constructor eauto Qed Lemma pbits unshared γ bs Forall sep valid γ bs Forall λ γ b Some Locked pbit kind γ b γ bs Forall sep unshared γ bs Proof induction 1 as x b intros decompose Forall hyps repeat constructor sep unfold auto using perm unshared Qed Lemma PBits indetify γ s pbit indetify flip PBit BIndet K γ s flip PBit BIndet γ s Proof induction γ s f equal auto Qed Lemma pbit indetify valid Γ Δ γ b Γ Δ γ b Γ Δ pbit indetify γ b Proof destruct γ b intros repeat split eauto using BIndet valid Qed Lemma pbits indetify valid Γ Δ γ bs Γ Δ γ bs Γ Δ pbit indetify γ bs Proof induction 1 csimpl auto using pbit indetify valid Qed Lemma pbits indetify idempotent γ bs pbit indetify pbit indetify γ bs pbit indetify γ bs Proof by induction γ bs f equal Qed Lemma pbit indetify unmapped γ b sep unmapped γ b pbit indetify γ b γ b Proof destruct γ b intros naive solver Qed Lemma pbit unmapped indetify γ b sep unmapped γ b sep unmapped pbit indetify γ b Proof destruct γ b intros split naive solver Qed Lemma pbits unmapped tag γ bs Forall sep unmapped γ bs tagged tag γ bs replicate length γ bs BIndet Proof by induction 1 as f equal Qed Lemma pbit unmapped indetify inv γ b sep valid γ b sep unmapped pbit indetify γ b sep unmapped γ b Proof destruct γ b intros split naive solver Qed Lemma pbits unmapped indetify inv β s γ bs Forall sep valid γ bs Forall sep unmapped mask pbit indetify β s γ bs Forall sep unmapped γ bs Proof intros H γ bs revert β s induction H γ bs intros decompose Forall hyps eauto using pbit unmapped indetify inv Qed Lemma pbits indetify unmapped γ bs Forall sep unmapped γ bs pbit indetify γ bs γ bs Proof induction 1 f equal auto using pbit indetify unmapped Qed Lemma pbits indetify mask

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

  • Module permission_bits_refine
    Qed Lemma pbit refine mapped Γ α f Δ1 Δ2 γ b1 γ b2 sep unmapped γ b2 γ b1 Γ α f Δ1 Δ2 γ b2 sep unmapped γ b1 Proof intros split eauto with congruence Qed Lemma pbits refine mapped Γ α f Δ1 Δ2 γ bs1 γ bs2 Forall sep unmapped γ bs2 γ bs1 Γ α f Δ1 Δ2 γ bs2 Forall sep unmapped γ bs1 Proof induction 2 decompose Forall hyps eauto using pbit refine mapped Qed Lemma pbit refine unshared Γ α f Δ1 Δ2 γ b1 γ b2 sep unshared γ b1 γ b1 Γ α f Δ1 Δ2 γ b2 sep unshared γ b2 Proof destruct γ b1 γ b2 intros naive solver Qed Lemma pbits refine unshared Γ α f Δ1 Δ2 γ bs1 γ bs2 Forall sep unshared γ bs1 γ bs1 Γ α f Δ1 Δ2 γ bs2 Forall sep unshared γ bs2 Proof induction 2 decompose Forall hyps eauto using pbit refine unshared Qed Lemma pbit refine shared Γ α f Δ1 Δ2 γ b1 γ b2 sep unshared γ b2 γ b1 Γ α f Δ1 Δ2 γ b2 sep unshared γ b1 Proof destruct γ b1 γ b2 intros naive solver Qed Lemma pbits refine shared Γ α f Δ1 Δ2 γ bs1 γ bs2 Forall sep unshared γ bs2 γ bs1 Γ α f Δ1 Δ2 γ bs2 Forall sep unshared γ bs1 Proof induction 2 decompose Forall hyps eauto using pbit refine shared Qed Lemma pbit empty refine Γ α f Δ1 Δ2 pbit K Γ α f Δ1 Δ2 Proof repeat split simpl auto using BIndet BIndet refine sep empty valid Qed Lemma PBit refine Γ α f Δ1 Δ2 γ b1 b2 sep valid γ sep unmapped γ b1 Γ α f Δ1 Δ2 b2 PBit γ b1 Γ α f Δ1 Δ2 PBit γ b2 Proof repeat split naive solver eauto using BBit refine Qed Lemma PBits refine Γ α f Δ1 Δ2 γ s bs1 bs2 Forall sep valid γ s Forall not sep unmapped γ s bs1 Γ α f Δ1 Δ2 bs2 zip with PBit γ s bs1 Γ α f Δ1 Δ2 zip with PBit γ s bs2 Proof intros H γ s H γ s Hbs revert γ s H γ s H γ s induction Hbs intros decompose Forall hyps eauto using PBit refine Qed Lemma PBit BIndet refine Γ α f Δ1 Δ2 γ sep valid γ PBit γ BIndet Γ α f Δ1 Δ2 PBit γ BIndet Proof repeat split auto using BIndet BIndet refine Qed Lemma PBits BIndet refine Γ α f Δ1 Δ2 γ s Forall sep valid γ s flip PBit BIndet γ s Γ α f Δ1 Δ2 flip PBit BIndet γ s Proof induction 1 csimpl auto using PBit BIndet refine Qed Lemma PBit BIndet refine l Γ Δ γ b Γ Δ γ b PBit tagged perm γ b BIndet Γ true Δ γ b Proof intros

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

  • Module permission_bits_separation
    BIndet K γ s1 γ s2 flip PBit BIndet γ s1 flip PBit BIndet γ s2 Proof revert γ s2 induction γ s1 intros f equal eauto Qed Lemma pbits locked union γ bs1 γ bs2 γ bs1 γ bs2 pbit locked γ bs1 γ bs2 pbit locked γ bs1 pbit locked γ bs2 Proof assert γ1 γ2 γ1 γ2 perm locked γ1 γ2 perm locked γ1 perm locked γ2 intros repeat sep unfold naive solver unfold pbit locked induction 1 as f equal auto Qed Lemma pbits unlock union 1 β s1 β s2 γ bs zip with pbit unlock if γ bs β s1 β s2 zip with pbit unlock if zip with pbit unlock if γ bs β s2 β s1 Proof assert γ perm unlock γ perm unlock perm unlock γ by intros revert β s1 β s2 unfold pbit unlock if pbit unlock induction γ bs as intros f equal auto with f equal Qed Lemma pbit lock disjoint γ b1 γ b2 Some Writable pbit kind γ b1 γ b1 γ b2 pbit lock γ b1 γ b2 Proof destruct γ b1 as γ1 b1 γ b2 as γ2 b2 intros split ands simplify equality intuition auto using perm lock disjoint perm lock mapped destruct perm mapped γ1 auto by transitivity Some Writable Qed Lemma pbits lock disjoint γ bs1 γ bs2 Forall λ γ b Some Writable pbit kind γ b γ bs1 γ bs1 γ bs2 pbit lock γ bs1 γ bs2 Proof induction 2 decompose Forall hyps auto using pbit lock disjoint Qed Lemma pbit lock union γ b1 γ b2 pbit lock γ b1 γ b2 pbit lock γ b1 γ b2 Proof sep unfold destruct γ b1 γ b2 f equal auto using perm lock union Qed Lemma pbit unlock disjoint γ b1 γ b2 γ b1 γ b2 pbit unlock γ b1 γ b2 Proof sep unfold destruct γ b1 as x1 b1 γ b2 as x2 b2 naive solver eauto using perm unlock disjoint perm unlock unmapped perm unlock mapped sep disjoint valid r Qed Lemma pbit unlock union γ b1 γ b2 γ b1 γ b2 pbit locked γ b1 pbit unlock γ b1 γ b2 pbit unlock γ b1 γ b2 Proof sep unfold intros destruct γ b1 γ b2 f equal naive solver auto using perm unlock union Qed Lemma pbits unlock disjoint γ bs1 γ bs2 β s γ bs1 γ bs2 β s pbit locked γ bs1 zip with pbit unlock if γ bs1 β s γ bs2 Proof rewrite Forall2 fmap r intros H γ bs revert β s induction H γ bs intros decompose Forall hyps auto using pbit unlock disjoint Qed Lemma pbits unlock union γ bs1 γ bs2 β s γ bs1 γ bs2 β s pbit locked γ bs1 zip with pbit unlock if γ bs1 γ bs2 β s zip with pbit unlock if γ bs1 β s γ bs2 Proof rewrite Forall2 fmap r intros

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

  • Module memory_trees
    c t τ s Γ Γ t Some τ s ctree new Γ γ b compoundT c t match c with Struct kind MStruct t zip ctree new Γ γ b τ s flip replicate pbit indetify γ b field bit padding Γ τ s Union kind MUnionAll t replicate bit size of Γ unionT t γ b end Proof intros H Γ Ht unfold ctree new erewrite ctree unflatten compound by eauto destruct c f equal erewrite bit size of struct by eauto clear Ht unfold struct unflatten field bit padding by induction bit size of fields τ s H Γ decompose Forall hyps rewrite take replicate plus drop replicate plus take replicate drop replicate Min min l fmap replicate by done repeat f equal Qed Lemma ctree new weaken Γ1 Γ2 γ b τ Γ1 Γ1 τ Γ1 Γ2 ctree new Γ1 γ b τ ctree new Γ2 γ b τ Proof intros unfold ctree new by erewrite ctree unflatten weaken bit size of weaken by eauto Qed Lemma ctree news weaken Γ1 Γ2 γ b τ s Γ1 Γ1 τ s Γ1 Γ2 ctree new Γ1 γ b τ s ctree new Γ2 γ b τ s Proof induction 2 intros f equal eauto using ctree new weaken Qed Lemma ctree new Forall P pbit K Prop Γ γ b τ Γ Γ τ P γ b P pbit indetify γ b ctree Forall P ctree new Γ γ b τ Proof intros unfold ctree new rewrite ctree flatten unflatten le by done generalize type mask Γ τ induction bit size of Γ τ intros simpl constructor auto Qed Lemma ctree new type of Γ γ b τ Γ Γ τ type of ctree new Γ γ b τ τ Proof by apply ctree unflatten type of Qed Lemma ctree new typed Γ Δ γ b τ Γ Γ τ Γ Δ γ b Γ Δ ctree new Γ γ b τ τ Proof intros apply ctree unflatten typed auto using replicate length Qed Lemma ctree new union free Γ γ b τ Γ Γ τ union free ctree new Γ γ b τ Proof by apply ctree unflatten union free Qed Lemma ctree flatten new Γ τ γ b Γ Γ τ pbit indetify γ b γ b ctree flatten ctree new Γ γ b τ replicate bit size of Γ τ γ b Proof intros unfold ctree new rewrite ctree flatten unflatten by done generalize type mask Γ τ induction bit size of intros f equal auto Qed Lemma ctree flatten replicate new Γ τ n γ b Γ Γ τ pbit indetify γ b γ b replicate n ctree new Γ γ b τ ctree flatten replicate n bit size of Γ τ γ b Proof intros induction n as n IH csimpl auto by rewrite replicate plus ctree flatten new IH by done Qed The map operation Lemma ctree map typed alt Γ Δ h w τ Γ Γ Δ w τ Γ Δ h ctree flatten w ctree Forall λ γ b sep unmapped h γ b sep unmapped γ b w γ b pbit indetify γ b γ b pbit indetify h γ b h γ b Γ Δ ctree map h w τ Proof intros Hw Hw Hw revert w τ Hw Hw Hw assert γ bs pbit indetify γ bs γ bs pbit indetify h γ bs h γ bs induction γ bs intros simplify equality f equal auto assert γ bs Forall λ γ b sep unmapped h γ b sep unmapped γ b γ bs Forall sep unmapped h γ bs Forall sep unmapped γ bs induction 1 intros decompose Forall hyps auto refine ctree typed ind simpl typed constructor auto intros ws τ IH Hlen Hw Hw typed constructor auto clear Hlen revert Hw Hw induction IH csimpl rewrite fmap app intros decompose Forall hyps constructor auto intros t w γ bss τ s Ht IH H γ bs Hindet Hlen Hw Hw typed constructor eauto revert Hw Hw elim IH intros csimpl rewrite fmap app intros decompose Forall hyps auto revert Hw Hw elim H γ bs intros csimpl rewrite fmap app intros decompose Forall hyps auto elim Hindet intros constructor simpl auto rewrite Hlen elim w γ bss intros f equal auto intros t i τ s w γ bs τ rewrite fmap app intros decompose Forall hyps typed constructor eauto using ctree flatten valid try solve length rewrite ctree flatten map intuition eauto using ctree flatten valid typed constructor eauto Qed Lemma ctree map typed Γ Δ h w τ Γ Γ Δ w τ Γ Δ h ctree flatten w γ b Γ Δ γ b sep unmapped h γ b sep unmapped γ b γ b pbit indetify γ b γ b pbit indetify h γ b h γ b Γ Δ ctree map h w τ Proof eauto using ctree map typed alt Forall impl ctree flatten valid Qed Lemma ctree map type of h w type of ctree map h w type of w Proof destruct w simpl unfold MUnion repeat case decide auto Qed Lookup operation Lemma ctree lookup nil Γ lookupE Γ nil ref seg K Some mtree K Proof done Qed Lemma ctree lookup cons Γ rs r lookupE Γ rs r λ w mtree K w Γ r lookupE Γ rs Proof done Qed Lemma ctree lookup app Γ r1 r2 w w Γ r1 r2 w Γ r2 lookupE Γ r1 Proof induction r1 as rs1 r1 IH simpl by destruct w r2 by rewrite ctree lookup cons IH option bind assoc Qed Lemma ctree lookup snoc Γ r rs w w Γ r rs w Γ rs lookupE Γ r Proof apply ctree lookup app Qed Lemma ctree lookup seg le Γ w rs1 rs2 w w Γ rs1 Some w rs1 rs2 w Γ rs2 Some w Proof destruct 2 as simpl in intuition destruct w simplify option equality auto Qed Lemma ctree lookup le Γ w r1 r2 w w Γ r1 Some w r1 r2 w Γ r2 Some w Proof intros Hw Hr revert w Hw induction Hr intros w done rewrite ctree lookup cons bind Some intros eauto using ctree lookup seg le Qed Lemma ctree lookup seg freeze proper Γ q1 q2 w rs1 rs2 w1 w2 w Γ rs1 Some w1 w Γ rs2 Some w2 freeze q1 rs1 freeze q2 rs2 w1 w2 Proof intros by destruct w rs1 rs2 simplify option equality Qed Lemma ctree lookup freeze proper Γ q1 q2 w r1 r2 w1 w2 w Γ r1 Some w1 w Γ r2 Some w2 freeze q1 r1 freeze q2 r2 w1 w2 Proof revert r2 w1 w2 induction r1 as rs1 r1 IH intros rs2 r2 try done intros by simplify equality rewrite ctree lookup cons intros simplify option equality efeed pose proof IH eauto subst eauto using ctree lookup seg freeze proper Qed Lemma ctree lookup seg inv P Γ rs w w w Γ rs Some w match rs w with RArray i τ n MArray τ ws w τ τ n length ws ws i Some w P w P w RStruct i t MStruct t w γ bss w γ bs t t w γ bss i Some w γ bs P w P w RUnion i t q MUnion t j w γ bs t t i j P w τ s τ t t i j q false Γ t Some τ s τ s i Some τ ctree unshared w Forall sep unshared γ bs P ctree unflatten Γ τ take bit size of Γ τ ctree flatten w γ bs P w RUnion i t MUnionAll t γ bs τ s τ t t Γ t Some τ s τ s i Some τ Forall sep unshared γ bs P ctree unflatten Γ τ take bit size of Γ τ γ bs P w P w end Proof destruct rs w intros simplify option equality repeat match goal with p prod destruct p end eauto Qed Lemma ctree lookup seg weaken Γ1 Γ2 rs w w Γ1 Γ1 Γ2 w Γ1 rs Some w w Γ2 rs Some w Proof intros Hrs by destruct w rs pattern w apply ctree lookup seg inv Hrs intros simplify option equality by eauto using lookup compound weaken erewrite bit size of weaken Γ1 Γ2 ctree unflatten weaken Γ1 Γ2 by eauto Qed Lemma ctree lookup weaken Γ1 Γ2 r w w Γ1 Γ1 Γ2 w Γ1 r Some w w Γ2 r Some w Proof intros revert w induction r as rs r IH intros w done rewrite ctree lookup cons intros simplify option equality eauto using ctree lookup seg weaken Qed Lemma ctree lookup seg union free Γ w rs w Γ union free w w Γ rs Some w union free w Proof intros Hw Hrs destruct Hw rs apply ctree lookup seg inv Hrs by intros decompose Forall hyps by intros decompose Forall hyps eauto using ctree unflatten union free env valid lookup singleton Qed Lemma ctree lookup union free Γ w r w Γ union free w w Γ r Some w union free w Proof intros H Γ revert w induction r using rev ind intros w Hw Hr rewrite ctree lookup snoc in Hr simplify option equality simplify type equality eauto using ctree lookup seg union free Qed Lemma ctree lookup seg Some Γ Δ w τ rs w Γ Γ Δ w τ w Γ rs Some w σ Γ rs τ σ Γ Δ w σ Proof intros Hw Hrs destruct rs as i τ n i i destruct Hw as τ γ bs ws s w γ bss τ s Hws s j τ s w γ bs τ s τ s γ bs change ctree typed Γ Δ with typed Γ Δ in pattern w apply ctree lookup seg inv Hrs clear Hrs intros w exists τ decompose Forall hyps repeat constructor eauto using lookup lt is Some 1 intros w γ bs destruct Forall2 lookup l i w γ bs Hws as σ eauto exists σ repeat econstructor eauto intros exists τ repeat econstructor eauto intros τ simplify equality exists τ repeat econstructor eauto 6 using ctree unflatten typed ctree flatten valid intros simplify equality exists τ repeat econstructor eauto using ctree unflatten typed Qed Lemma ctree lookup seg Some type of Γ Δ w τ rs w Γ Γ Δ w τ w Γ rs Some w Γ Δ w type of w Proof intros destruct ctree lookup seg Some Γ Δ w τ rs w as eauto using type of typed Qed Lemma ctree lookup Some Γ Δ w τ r w Γ Γ Δ w τ w Γ r Some w σ Γ r τ σ Γ Δ w σ Proof intros H Γ revert w τ induction r as rs r IH using rev ind intros w τ Hv τ Hr simplify type equality eexists split econstructor eauto rewrite ctree lookup snoc in Hr simplify option equality edestruct ctree lookup seg Some as eauto edestruct IH as eauto eexists split eapply ref typed snoc eauto Qed Lemma ctree lookup Some type of Γ Δ w τ r w Γ Γ Δ w τ w Γ r Some w Γ Δ w type of w Proof intros destruct ctree lookup Some Γ Δ w τ r w as eauto using type of typed Qed Lemma ctree lookup seg typed Γ Δ w τ rs w σ Γ Γ Δ w τ w Γ rs Some w Γ rs τ σ Γ Δ w σ Proof intros H Γ Hv τ Hw by destruct ctree lookup seg Some H Γ Hv τ Hw as σ Hr σ simplify type equality Qed Lemma ctree lookup typed Γ Δ w τ r w σ Γ Γ Δ w τ w Γ r Some w Γ r τ σ Γ Δ w σ Proof intros H Γ Hv τ Hw by destruct ctree lookup Some H Γ Hv τ Hw as σ Hr σ simplify type equality Qed Lemma ctree lookup seg Forall P pbit K Prop Γ w rs w Γ γ b P γ b P pbit indetify γ b ctree Forall P w w Γ rs Some w ctree Forall P w Proof intros assert β s γ bs Forall P γ bs Forall P mask pbit indetify β s γ bs intros β s γ bs H γ bs revert β s induction H γ bs intros simpl auto intros Hw Hrs destruct w rs simpl in Hw rewrite Forall bind in Hw pattern w apply ctree lookup seg inv Hrs clear Hrs intros decompose Forall hyps eauto 7 using ctree unflatten Forall le Qed Lemma ctree lookup Forall P pbit K Prop Γ w r w Γ γ b P γ b P pbit indetify γ b ctree Forall P w w Γ r Some w ctree Forall P w Proof intros H Γ revert w induction r as rs r using rev ind intros w rewrite ctree lookup snoc intros simplify option equality simplify type equality eauto using ctree lookup seg Forall Qed Lemma ctree lookup Forall typed P pbit K Prop Γ Δ w τ r w Γ Γ Δ w τ γ b Γ Δ γ b P γ b P pbit indetify γ b ctree Forall P w w Γ r Some w ctree Forall P w Proof intros eapply Forall and l with Γ Δ ctree lookup Forall eauto intros eauto using pbit indetify valid rewrite Forall and eauto using ctree flatten valid Qed Lemma ctree new lookup seg Γ τ γ rs σ Γ sep unshared γ Γ τ Γ rs τ σ ctree new Γ γ τ Γ rs Some ctree new Γ γ σ Proof destruct 4 as τ n i s i τ s τ Ht H τ s s i q τ s τ rewrite ctree new array simplify option equality by rewrite lookup replicate by done erewrite ctree new compound by eauto simplify option equality by rewrite list lookup fmap fst zip list lookup fmap H τ s by by rewrite fmap length field bit padding length erewrite ctree new compound by eauto simplify option equality by eauto by rewrite take replicate Min min l by eauto using bit size of union lookup Qed Lemma ctree new lookup Γ γ τ r σ Γ sep unshared γ Γ τ Γ r τ σ ctree new Γ γ τ Γ r Some ctree new Γ γ σ Proof induction 4 as r rs τ1 τ2 τ3 IH using ref typed ind done rewrite ctree lookup cons IH simpl eauto using ctree new lookup seg ref typed type valid Qed Lemma ctree lookup seg unfreeze exists Γ Δ w τ rs σ Γ Γ Δ w τ ctree unshared w Γ rs τ σ w w Γ freeze false rs Some w Proof destruct 2 as ws τ s w γ bss τ s inversion 2 decompose Forall hyps simplify option equality eauto by apply lookup lt is Some 2 Qed Lemma ctree lookup unfreeze exists Γ Δ w τ r σ Γ Γ Δ w τ ctree unshared w Γ r τ σ w w Γ freeze false r Some w Proof intros H Γ revert w τ induction r as rs r IH using rev ind intros w τ Hw τ Hw Hr rewrite ref typed nil in Hr subst by exists w rewrite ref typed snoc in Hr destruct Hr as σ destruct ctree lookup seg unfreeze exists Γ Δ w τ rs σ as w auto destruct IH w σ as w eauto using ctree lookup seg union free ctree lookup seg Forall ctree lookup seg typed pbit indetify unshared ref seg typed le ref seg freeze le r exists w rewrite fmap app csimpl rewrite ctree lookup snoc by simplify option equality Qed Lemma type mask ref seg Γ τ rs σ Γ Γ rs τ σ Γ τ take bit size of Γ σ drop ref seg object offset Γ rs type mask Γ τ type mask Γ σ Proof intros H Γ Hrs H τ destruct Hrs as τ i n Hin s i τ s τ Ht Hi simplify option equality rewrite type mask array apply reflexive eq revert i Hin apply TArray valid inv type in H τ induction n as n intros i simplify equality rewrite drop 0 take app alt drop drop drop app alt by done auto with lia erewrite type mask compound by eauto simpl apply reflexive eq assert Γ τ s as H τ s by eauto revert i Hi H τ s clear Ht H τ unfold bit offset of induction bit size of fields τ s H Γ intros i decompose Forall hyps rewrite drop drop drop app alt drop 0 resize ge associative L take app alt by done auto erewrite type mask compound by eauto simpl rewrite drop 0 take replicate Min min l by solve length by apply replicate false Qed Lemma ctree lookup seg flatten Γ Δ w τ rs w τ Γ Γ Δ w τ w Γ rs Some w Γ Δ w τ mask pbit indetify type mask Γ τ take bit size of Γ τ drop ref seg object offset Γ rs ctree flatten w ctree flatten w Proof intros H Γ Hw Hrs Hw rewrite type of correct Γ Δ w τ by done clear Hw revert w τ Hw Hrs refine ctree typed ind by destruct rs intros ws τ Hws Hrs destruct rs as i pattern w apply ctree lookup seg inv Hrs clear w Hrs assert ws Γ Δ ws τ length ws ctree flatten length ws bit size of Γ τ as help induction 1 f equal auto intros w decompose Forall hyps simplify type equality rewrite take drop middle ws i w bind app bind cons by done rewrite drop app alt by by rewrite help take length le by eauto using Nat lt le incl lookup lt Some by erewrite take app alt ctree mask flatten by eauto intros t w γ bss τ s Ht Hws Hindet Hlen Hrs destruct rs as i pattern w apply ctree lookup seg inv Hrs clear Hrs intros w γ bs Hi destruct Forall2 lookup l typed Γ Δ fst w γ bss τ s i w γ bs as τ Hi Hw auto simplify option equality simplify type equality assert bit offset of Γ τ s i length take i w γ bss λ w γ bs ctree flatten w γ bs 1 w γ bs 2 as help2 clear Ht Hi Hw Hindet apply lookup lt Some in Hi unfold field bit padding bit offset of in revert i w γ bss Hi Hlen Hws induction bit size of fields τ s H Γ intros decompose Forall hyps rewrite app length f equal auto solve length rewrite take drop middle w γ bss i w γ bs bind app by done csimpl by erewrite drop app alt associative L take app alt ctree mask flatten by eauto intros t i τ s w γ bs τ Ht H τ Hindet Hrs destruct rs as i pattern w apply ctree lookup seg inv Hrs clear Hrs intros simplify option equality simplify type equality by erewrite drop 0 take app alt ctree mask flatten by eauto intros τ simplify option equality rewrite ctree unflatten type of by eauto by rewrite ctree flatten unflatten by eauto intros t τ s γ bs Hrs destruct rs as i pattern w apply ctree lookup seg inv Hrs clear Hrs intros simplify option equality rewrite ctree unflatten type of by eauto by rewrite ctree flatten unflatten by eauto Qed Lemma ctree lookup flatten Γ Δ w τ r w τ Γ Γ Δ w τ w Γ r Some w Γ Δ w τ mask pbit indetify type mask Γ τ take bit size of Γ τ drop ref object offset Γ r ctree flatten w ctree flatten w Proof intros H Γ unfold ref object offset revert w τ induction r as rs r IH intros w τ intros simplify type equality by erewrite drop 0 take ge ctree mask flatten by eauto rewrite ctree lookup cons intros destruct w Γ r as w eqn simplify equality destruct ctree lookup Some Γ Δ w τ r w as τ auto destruct ctree lookup seg Some Γ Δ w τ rs w as auto simplify type equality assert ref seg object offset Γ rs bit size of Γ τ bit size of Γ τ by eauto using ref seg object offset size rewrite Nat add comm drop drop Min min l bit size of Γ τ bit size of Γ τ ref seg object offset Γ rs take take take drop commute le plus minus r by lia by erewrite mask mask pbit indetify take mask drop mask IH ctree lookup seg flatten by eauto using type mask ref seg Qed Lemma ctree lookup seg merge B Set Γ Δ h pbit K B pbit K w ys τ rs w τ Γ γ b y h pbit indetify γ b y pbit indetify h γ b y γ b y sep unshared γ b sep unshared h γ b y Γ Δ w τ length ys bit size of Γ τ w Γ rs Some w Γ Δ w τ ctree merge h w ys Γ rs Some ctree merge h w take bit size of Γ τ drop ref seg object offset Γ rs ys Proof intros H Γ Hw Hlen Hrs Hw rewrite type of correct Γ Δ w τ by done assert γ bs ys zip with h pbit indetify γ bs ys pbit indetify zip with h γ bs ys induction γ bs intros f equal auto clear Hw revert w τ Hw Hlen Hrs assert γ bs ys Forall sep unshared γ bs Forall sep unshared zip with h γ bs ys induction γ bs intros decompose Forall hyps auto refine ctree typed ind by destruct rs intros ws τ Hws Hrs destruct rs as i pattern w apply ctree lookup seg inv Hrs clear w Hrs intros w Hw simplify equality erewrite type of correct by decompose Forall hyps eauto assert length ctree merge array ctree merge h ws ys length ws as Hlen by generalize ys elim ws intros f equal auto simplify option equality clear Hlen revert i w ys Hw induction Hws as w ws IH intros i w ys simplify equality by erewrite ctree flatten length by eauto by erewrite IH ctree flatten length drop drop by eauto intros t w γ bss τ s Ht Hws Hlen Hrs destruct rs as i pattern w apply ctree lookup seg inv Hrs clear w Hrs intros w γ bs Hw γ bs destruct Forall2 lookup l typed Γ Δ fst w γ bss τ s i w γ bs as τ H τ Hw auto simplify option equality simplify type equality clear Ht Hw revert w γ bss i w γ bs τ ys H τ Hws Hlen Hw γ bs unfold field bit padding bit offset of induction bit size of fields τ s H Γ as τ sz τ s szs IH intros w γ bs w γ bss i ys decompose Forall hyps by erewrite ctree flatten length by eauto erewrite IH ctree flatten length drop drop by eauto do 4 f equal lia intros t i τ s w γ bs τ Ht H τ Hindet Hrs destruct rs as i pattern w apply ctree lookup seg inv Hrs clear Hrs intros simplify option equality simplify type equality by erewrite ctree flatten length drop 0 by eauto intros τ simplify equality rewrite ctree flatten merge simplify option equality f equal rewrite ctree unflatten type of ctree merge unflatten drop 0 by eauto by rewrite zip with app zip with take take drop by auto intros t τ s γ bs Hrs destruct rs as i pattern w apply ctree lookup seg inv Hrs clear Hrs intros simplify option equality f equal rewrite ctree unflatten type of by eauto by rewrite ctree merge unflatten drop 0 zip with take by eauto Qed Lemma ctree lookup merge B Set Γ Δ h pbit K B pbit K w ys τ r w τ Γ γ b y h pbit indetify γ b y pbit indetify h γ b y γ b y sep unshared γ b sep unshared h γ b y Γ Δ w τ length ys bit size of Γ τ w Γ r Some w Γ Δ w τ ctree merge h w ys Γ r Some ctree merge h w take bit size of Γ τ drop ref object offset Γ r ys Proof intros unfold ref object offset revert w τ induction r as rs r IH intros w τ intros simplify type equality by rewrite drop 0 take ge by auto rewrite ctree lookup cons intros destruct w Γ r as w eqn simplify equality destruct ctree lookup Some Γ Δ w τ r w as τ auto destruct ctree lookup seg Some Γ Δ w τ rs w as auto erewrite IH by eauto simplify type equality assert sum list ref seg object offset Γ r bit size of Γ τ bit size of Γ τ by by apply ref object offset size assert ref seg object offset Γ rs bit size of Γ τ bit size of Γ τ by eauto using ref seg object offset size erewrite ctree lookup seg merge by eauto do 2 f equal rewrite drop drop take drop commute drop drop take take repeat lia f equal Qed Alter operation Lemma ctree alter nil Γ g ctree alter Γ g g Proof done Qed Lemma ctree alter cons Γ g rs r ctree alter Γ g rs r ctree alter Γ ctree alter seg Γ g rs r Proof done Qed Lemma ctree alter app Γ g w r1 r2 ctree alter Γ g r1 r2 w ctree alter Γ ctree alter Γ g r1 r2 w Proof revert g induction r1 simpl intros rewrite ctree alter cons auto Qed Lemma ctree alter snoc Γ g w r rs ctree alter Γ g r rs w ctree alter seg Γ ctree alter Γ g r rs w Proof apply ctree alter app Qed Lemma ctree alter seg le Γ g rs1 rs2 rs1 rs2 ctree alter seg Γ g rs1 ctree alter seg Γ g rs2 Proof by destruct 1 Qed Lemma ctree alter le Γ g r1 r2 r1 r2 ctree alter Γ g r1 ctree alter Γ g r2 Proof intros Hr revert g induction Hr as rs1 rs2 r1 r2 IH intros g simpl auto by erewrite IH ctree alter seg le by eauto Qed Lemma ctree alter seg ext Γ g1 g2 w rs w g1 w g2 w ctree alter seg Γ g1 rs w ctree alter seg Γ g2 rs w Proof intros destruct rs w simpl unfold default simplify option equality repeat case match f equal auto using list fmap ext list alter ext by apply list alter ext intros f equal auto Qed Lemma ctree alter ext Γ g1 g2 w r w g1 w g2 w ctree alter Γ g1 r w ctree alter Γ g2 r w Proof intros revert w induction r as rs r IH using rev ind intros w done rewrite ctree alter snoc by apply ctree alter seg ext Qed Lemma ctree alter seg ext typed Γ Δ g1 g2 w τ rs Γ w τ Γ Δ w τ g1 w g2 w Γ Δ w τ ctree alter seg Γ g1 rs w ctree alter seg Γ g2 rs w Proof intros Hg destruct rs 1 simpl unfold default simplify option equality f equal eauto apply list alter ext intros decompose Forall hyps eauto apply list alter ext auto intros decompose Forall hyps f equal eauto case match f equal eauto eapply Hg eauto using ctree unflatten typed ctree flatten valid case match decompose Forall f equal eauto using ctree unflatten typed Qed Lemma ctree alter ext typed Γ Δ g1 g2 w τ r Γ w τ Γ Δ w τ g1 w g2 w Γ Δ w τ ctree alter Γ g1 r w ctree alter Γ g2 r w Proof intros revert g1 g2 w τ induction r as rs r IH intros g1 g2 w τ eauto rewrite ctree alter cons eauto using ctree alter seg ext typed Qed Lemma ctree alter seg compose Γ g1 g2 w rs ctree alter seg Γ g1 g2 rs w ctree alter seg Γ g1 rs ctree alter seg Γ g2 rs w Proof destruct w as s w γ bss rs as i i i simpl unfold default repeat simplify option equality case match f equal auto using list alter compose list fmap compose rewrite list alter compose by apply list alter ext Qed Lemma ctree alter compose Γ g1 g2 w r ctree alter Γ g1 g2 r w ctree alter Γ g1 r ctree alter Γ g2 r w Proof intros revert w induction r as rs r IH using rev ind intros w done rewrite ctree alter snoc ctree alter seg compose by apply ctree alter seg ext Qed Lemma ctree alter seg commute Γ g1 g2 w rs1 rs2 rs1 rs2 ctree alter seg Γ g1 rs1 ctree alter seg Γ g2 rs2 w ctree alter seg Γ g2 rs2 ctree alter seg Γ g1 rs1 w Proof destruct 1 as i1 i2 Hi w as w γ bss intros simplify option equality f equal auto using list alter commute Qed Lemma ctree alter commute Γ g1 g2 w r1 r2 r1 r2 ctree alter Γ g1 r1 ctree alter Γ g2 r2 w ctree alter Γ g2 r2 ctree alter Γ g1 r1 w Proof rewrite ref disjoint alt intros r1 rs1 r1 r2 rs2 r2 Hr rewrite ctree alter app ctree alter cons ctree alter nil erewrite ctree alter le freeze true r1 Hr ctree alter le freeze true r2 r2 by eauto using ref freeze le l rewrite ctree alter compose apply ctree alter ext intros w simpl auto by apply ctree alter seg commute Qed Lemma ctree alter seg weaken Γ1 Γ2 Δ g rs w τ Γ1 Γ1 Γ2 Γ1 Δ w τ ctree alter seg Γ1 g rs w ctree alter seg Γ2 g rs w Proof destruct rs as j 3 simplify option equality auto erewrite lookup compound weaken by eauto simpl destruct j eqn f equal by erewrite bit size of weaken Γ1 Γ2 ctree unflatten weaken by eauto using TCompound valid erewrite lookup compound weaken by eauto simpl destruct j eqn f equal by erewrite bit size of weaken Γ1 Γ2 ctree unflatten weaken by eauto using TCompound valid Qed Lemma ctree alter weaken Γ1 Γ2 Δ g r w τ Γ1 Γ1 Γ2 Γ1 Δ w τ ctree alter Γ1 g r w ctree alter Γ2 g r w Proof intros revert g w τ induction r as rs r IH intros g w τ done erewrite ctree alter cons IH by eauto eapply ctree alter ext typed eauto using ctree alter seg weaken Qed Lemma ctree alter lookup seg Forall P pbit K Prop Γ g w rs w ctree Forall P ctree alter seg Γ g rs w w Γ rs Some w ctree Forall P g w Proof intros Hgw Hrs destruct w as τ ws s w γ bss s i w γ bs rs as i i i pattern w apply ctree lookup seg inv Hrs clear w Hrs intros w Hw simplify equality rewrite Forall bind in Hgw apply Forall lookup 1 λ w ctree Forall P w alter g i ws i auto by rewrite list lookup alter Hw intros w γ bs Hw γ bs simplify equality rewrite Forall bind in Hgw assert alter prod map g id i w γ bss i Some g w γ bs by rewrite list lookup alter Hw γ bs by decompose Forall hyps by intros simplify option equality decompose Forall hyps by intros simplify option equality decompose Forall hyps by intros simplify option equality decompose Forall hyps Qed Lemma ctree alter lookup Forall P pbit K Prop Γ g w r w ctree Forall P ctree alter Γ g r w w Γ r Some w ctree Forall P g w Proof revert g w induction r as rs r IH using rev ind intros g w rewrite ctree lookup nil naive solver intros g w rewrite ctree alter snoc ctree lookup snoc intros destruct w Γ rs as w eqn Hw simplify equality eauto using ctree alter lookup seg Forall Qed Lemma ctree alter seg Forall P pbit K Prop Γ g w rs w γ b P γ b P pbit indetify γ b ctree Forall P w w Γ rs Some w ctree Forall P g w ctree Forall P ctree alter seg Γ g rs w Proof intros assert γ bs Forall P γ bs Forall P pbit indetify γ bs induction 1 simpl auto intros Hw Hrs destruct w as τ ws s w γ bss s i w γ bs rs as i i i pattern w apply ctree lookup seg inv Hrs clear w Hrs intros w simplify equality rewrite Forall bind in Hw apply Forall alter intros simplify equality auto intros w γ bs simplify equality rewrite Forall bind in Hw apply Forall alter intros decompose Forall hyps auto intros simplify option equality decompose Forall hyps auto intros simplify option equality decompose Forall hyps auto intros simplify option equality decompose Forall hyps auto Qed Lemma ctree alter Forall P pbit K Prop Γ g w r w Γ γ b P γ b P pbit indetify γ b ctree Forall P w w Γ r Some w ctree Forall P g w ctree Forall P ctree alter Γ g r w Proof intros revert g w induction r as rs r IH using rev ind intros g w rewrite ctree lookup nil naive solver intros g w rewrite ctree alter snoc ctree lookup snoc intros destruct w Γ rs as w eqn Hw simplify equality eauto using ctree alter seg Forall ctree lookup seg Forall Qed Lemma ctree alter seg typed Γ Δ g w rs τ w Γ Γ Δ w τ w Γ rs Some w Γ Δ g w type of w ctree unmapped g w Γ Δ ctree alter seg Γ g rs w τ Proof intros H Γ Hw Hrs destruct rs as i i i Hw as τ ws s w γ bss τ s Hindet Hlen change ctree typed Γ Δ with typed Γ Δ in pattern w apply ctree lookup seg inv Hrs clear Hrs intros simplify option equality typed constructor auto using alter length apply Forall alter g i auto by intros simplify type equality intros simplify option equality typed constructor eauto apply Forall2 alter l auto 1 by intros simplify type equality apply Forall alter auto apply Forall alter auto rewrite Hlen generalize i elim w γ bss done intros w γ bss f equal auto intros simplify option equality typed constructor eauto by simplify type equality intuition intros τ intros simplify option equality typed constructor eauto using pbits indetify idempotent erewrite ctree unflatten type of by eauto eauto eauto using pbits indetify valid ctree flatten valid erewrite fmap length drop length app length ctree flatten length by eauto solve length by intros intros τ intros simplify option equality typed constructor eauto using pbits indetify valid pbits indetify idempotent

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