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 memory_trees_refine
    α f Δ1 Δ2 MUnionAll t γ bs1 MUnionAll t γ bs2 MUnion MUnionAll shape t i w1 γ bs1 γ bs2 α ctree flatten w1 γ bs1 Γ α f Δ1 Δ2 γ bs2 Forall sep unshared γ bs2 ctree leaf refine Γ α f Δ1 Δ2 MUnion t i w1 γ bs1 MUnionAll t γ bs2 Section ctree leaf refine Context Γ α f Δ1 Δ2 P mtree K mtree K Prop Context Pbase τ b γ bs1 γ bs2 γ bs1 Γ α f Δ1 Δ2 γ bs2 P MBase τ b γ bs1 MBase τ b γ bs2 Context Parray τ ws1 ws2 Forall2 ctree leaf refine Γ α f Δ1 Δ2 ws1 ws2 Forall2 P ws1 ws2 P MArray τ ws1 MArray τ ws2 Context Pstruct t w γ bss1 w γ bss2 Forall2 λ w γ bs1 w γ bs2 ctree leaf refine Γ α f Δ1 Δ2 w γ bs1 1 w γ bs2 1 w γ bss1 w γ bss2 Forall2 λ w γ bs1 w γ bs2 P w γ bs1 1 w γ bs2 1 w γ bss1 w γ bss2 w γ bss1 Γ α f Δ1 Δ2 2 w γ bss2 P MStruct t w γ bss1 MStruct t w γ bss2 Context Punion t i w1 w2 γ bs1 γ bs2 ctree leaf refine Γ α f Δ1 Δ2 w1 w2 P w1 w2 γ bs1 Γ α f Δ1 Δ2 γ bs2 P MUnion t i w1 γ bs1 MUnion t i w2 γ bs2 Context Munionall t γ bs1 γ bs2 γ bs1 Γ α f Δ1 Δ2 γ bs2 P MUnionAll t γ bs1 MUnionAll t γ bs2 Context Munionall t i w1 γ bs1 γ bs2 α ctree flatten w1 γ bs1 Γ α f Δ1 Δ2 γ bs2 Forall sep unshared γ bs2 P MUnion t i w1 γ bs1 MUnionAll t γ bs2 Lemma ctree leaf refine ind alt w1 w2 ctree leaf refine Γ α f Δ1 Δ2 w1 w2 P w1 w2 Proof fix 3 destruct 1 eauto using Forall2 impl Qed End ctree leaf refine Lemma ctree refine leaf Γ α f Δ1 Δ2 w1 w2 τ w1 Γ α f Δ1 Δ2 w2 τ ctree leaf refine Γ α f Δ1 Δ2 w1 w2 Proof induction 1 as IH using ctree refine ind constructor auto elim IH auto Qed Hint Immediate ctree refine leaf Lemma ctree leaf refine refine Γ α f Δ1 Δ2 w1 w2 τ Γ ctree leaf refine Γ α f Δ1 Δ2 w1 w2 Γ Δ1 w1 τ Γ Δ2 w2 τ w1 Γ α f Δ1 Δ2 w2 τ Proof intros Hw revert τ revert w1 w2 Hw refine ctree leaf refine ind alt simpl intros τ b γ bs1 γ bs2 τ Hw1 apply ctree typed inv l Hw1 by refine constructor intros τ ws1 ws2 IH τ Hw1 pattern τ apply ctree typed inv l Hw1 clear τ Hw1 intros Hws1 Hlen Hw2 apply ctree typed inv Hw2 clear Hw2 intros Hws2 refine constructor eauto clear Hlen induction IH decompose Forall hyps auto intros t w γ bss1 w γ bss2 IH H γ bs τ Hw1 pattern τ apply ctree typed inv l Hw1 clear τ Hw1 intros τ s Ht Hws1 H γ bs1 Hindet1 Hlen Hw2 apply ctree typed inv Hw2 clear Hw2 intros Hws2 H γ bs2 Hindet2 simplify equality refine constructor eauto clear Ht H γ bs1 Hlen H γ bs2 Hindet1 Hindet2 H γ bs revert τ s Hws1 Hws2 induction IH intros decompose Forall hyps constructor auto intros t i w1 w2 γ bs1 γ bs2 τ Hw1 pattern τ apply ctree typed inv l Hw1 clear τ Hw1 intros τ s τ Hw2 apply ctree typed inv Hw2 intros decompose Forall hyps refine constructor eauto intros t γ bs1 γ bs2 τ Hw1 apply ctree typed inv l Hw1 refine constructor eauto intros t i w1 γ bs1 γ bs2 τ Hw1 pattern τ apply ctree typed inv l Hw1 intros Hw2 apply ctree typed inv Hw2 intros simplify equality refine constructor eauto Qed Lemma ctree flatten leaf refine Γ α f Δ1 Δ2 w1 w2 ctree leaf refine Γ α f Δ1 Δ2 w1 w2 ctree flatten w1 Γ α f Δ1 Δ2 ctree flatten w2 Proof revert w1 w2 refine ctree leaf refine ind alt simpl auto 2 eauto using Forall2 bind intros t w γ bss1 w γ bss2 IH induction IH decompose Forall hyps auto Qed Lemma ctree unflatten leaf refine Γ α f Δ1 Δ2 τ γ bs1 γ bs2 Γ Γ τ γ bs1 Γ α f Δ1 Δ2 γ bs2 ctree leaf refine Γ α f Δ1 Δ2 ctree unflatten Γ τ γ bs1 ctree unflatten Γ τ γ bs2 Proof intros H Γ H τ revert τ H τ γ bs1 γ bs2 refine type env ind H Γ intros rewrite ctree unflatten base by constructor intros τ n IH γ bs1 γ bs2 H γ bs rewrite ctree unflatten array constructor revert γ bs1 γ bs2 H γ bs induction n simpl auto intros t τ s Ht IH γ bs1 γ bs2 H γ bs erewrite ctree unflatten compound by eauto simpl clear Ht by constructor unfold struct unflatten constructor revert γ bs1 γ bs2 H γ bs induction bit size of fields τ s H Γ intros decompose Forall hyps constructor simpl auto revert γ bs1 γ bs2 H γ bs induction bit size of fields τ s H Γ intros decompose Forall hyps constructor simpl auto using pbits indetify refine Qed Lemma ctree unflatten refine Γ α f Δ1 Δ2 τ γ bs1 γ bs2 Γ Γ τ γ bs1 Γ α f Δ1 Δ2 γ bs2 length γ bs1 bit size of Γ τ ctree unflatten Γ τ γ bs1 Γ α f Δ1 Δ2 ctree unflatten Γ τ γ bs2 τ Proof intros apply ctree leaf refine refine eauto using ctree unflatten typed pbits refine valid l pbits refine valid r ctree unflatten leaf refine Qed Lemma ctree flatten refine Γ α f Δ1 Δ2 w1 w2 τ w1 Γ α f Δ1 Δ2 w2 τ ctree flatten w1 Γ α f Δ1 Δ2 ctree flatten w2 Proof eauto using ctree flatten leaf refine Qed Lemma ctree refine typed l Γ α f Δ1 Δ2 w1 w2 τ Γ w1 Γ α f Δ1 Δ2 w2 τ Γ Δ1 w1 τ Proof intros revert w1 w2 τ refine ctree refine ind typed constructor eauto using pbits refine valid l intros τ n ws1 ws2 Hn IH typed constructor auto clear Hn induction IH auto intros t τ s w γ bss1 w γ bss2 Ht IH H γ bs Hindet Hlen typed constructor eauto clear Ht Hlen induction IH decompose Forall hyps eauto using pbits refine valid l typed constructor eauto using pbits refine valid l intros typed constructor eauto using pbits refine valid l intros decompose Forall hyps typed constructor eauto using pbits refine valid l Qed Lemma ctree refine typed r Γ α f Δ1 Δ2 w1 w2 τ Γ w1 Γ α f Δ1 Δ2 w2 τ Γ Δ2 w2 τ Proof intros revert w1 w2 τ refine ctree refine ind typed constructor eauto using Forall2 length l pbits refine valid r intros τ n ws1 ws2 IH Hn typed constructor eauto using Forall2 length clear Hn induction IH auto intros t τ s w γ bss1 w γ bss2 Ht IH H γ bs Hlen typed constructor eauto elim IH eauto elim H γ bs eauto using pbits refine valid r rewrite Hlen symmetry elim H γ bs intros f equal eauto using Forall2 length intros typed constructor eauto using pbits refine valid r solve length typed constructor eauto using Forall2 length l pbits refine valid r typed constructor eauto using Forall2 length l pbits refine valid r Qed Hint Immediate ctree refine typed l ctree refine typed r Lemma ctree refine type valid l Γ α f Δ1 Δ2 w1 w2 τ Γ w1 Γ α f Δ1 Δ2 w2 τ Γ τ Proof eauto using ctree typed type valid Qed Lemma ctree refine type of l Γ α f Δ1 Δ2 w1 w2 τ w1 Γ α f Δ1 Δ2 w2 τ type of w1 τ Proof destruct 1 using ctree refine ind simpl auto Qed Lemma ctree refine type of r Γ α f Δ1 Δ2 w1 w2 τ w1 Γ α f Δ1 Δ2 w2 τ type of w2 τ Proof destruct 1 f equal eauto using Forall2 length l Qed Lemma ctree refine id Γ α Δ w τ Γ Δ w τ w Γ α Δ w τ Proof revert w τ refine ctree typed ind try by intros refine constructor eauto using pbits refine id intros ws τ IH Hlen refine constructor auto elim IH auto intros t w γ bss τ s IH Hw γ bss refine constructor eauto elim IH constructor eauto elim Hw γ bss constructor eauto using pbits refine id Qed Lemma ctree refine compose Γ α1 α2 f1 f2 Δ1 Δ2 Δ3 w1 w2 w3 τ Γ w1 Γ α1 f1 Δ1 Δ2 w2 τ w2 Γ α2 f2 Δ2 Δ3 w3 τ w1 Γ α1 α2 f2 f1 Δ1 Δ3 w3 τ Proof intros Hw Hw3 apply ctree leaf refine refine eauto revert w1 w2 τ Hw w3 Hw3 refine ctree refine ind simpl intros τ b γ bs1 γ bs2 w3 Hw3 pattern w3 apply ctree refine inv l Hw3 constructor eauto using pbits refine compose intros τ n ws1 ws2 IH w3 Hw3 pattern w3 apply ctree refine inv l Hw3 clear w3 Hw3 intros ws3 Hws3 constructor revert ws3 Hws3 induction IH intros decompose Forall hyps constructor auto intros t τ s w γ bss1 w γ bss2 Ht IH H γ bs w3 Hw3 pattern w3 apply ctree refine inv l Hw3 clear w3 Hw3 intros w γ bss3 Hws3 H γ bs3 simplify equality constructor clear Ht H γ bs3 H γ bs revert w γ bss3 Hws3 induction IH inversion clear 1 constructor eauto clear Ht IH Hws3 revert w γ bss3 H γ bs3 induction H γ bs intros decompose Forall hyps constructor eauto using pbits refine compose intros t τ s i w1 w2 γ bs1 γ bs2 τ Ht H τ s IH w3 Hw3 pattern w3 apply ctree refine inv l Hw3 clear w3 Hw3 intros decompose Forall hyps constructor eauto using ctree flatten refine pbits refine compose intros t τ s γ bs1 γ bs2 Ht w3 Hw3 pattern w3 apply ctree refine inv l Hw3 constructor eauto using pbits refine compose intros t i τ s w1 γ bs1 γ bs2 τ w3 Hw3 pattern w3 apply ctree refine inv l Hw3 clear w3 Hw3 constructor eauto using pbits refine compose pbits refine unshared Qed Lemma ctree refine inverse Γ f Δ1 Δ2 w1 w2 τ w1 Γ false f Δ1 Δ2 w2 τ w2 Γ false meminj inverse f Δ2 Δ1 w1 τ Proof revert w1 w2 τ refine ctree refine ind simpl refine constructor eauto using pbits refine inverse refine constructor auto by apply Forall2 flip intros IH H γ bss Hlen refine constructor eauto elim IH constructor eauto elim H γ bss eauto using pbits refine inverse rewrite Hlen elim H γ bss intros f equal auto refine constructor eauto using pbits refine inverse solve length refine constructor eauto using pbits refine inverse done Qed Lemma ctree refine weaken Γ Γ α α f f Δ1 Δ2 Δ1 Δ2 w1 w2 τ Γ w1 Γ α f Δ1 Δ2 w2 τ Γ Γ α α Δ1 Γ α f Δ2 Δ1 ₘ Δ1 Δ2 ₘ Δ2 meminj extend f f Δ1 Δ2 w1 Γ α f Δ1 Δ2 w2 τ Proof intros Hw intros induction Hw using ctree refine ind refine constructor try eapply Forall2 impl eassumption simpl eauto using base type valid weaken lookup compound weaken pbit refine weaken ctree typed weaken erewrite bit size of weaken Γ Γ field bit padding weaken Γ Γ by eauto using TBase valid TCompound valid auto simpl eauto using Forall2 impl pbit refine weaken Qed Lemma union free refine Γ α f Δ1 Δ2 w1 w2 τ union free w1 w1 Γ α f Δ1 Δ2 w2 τ union free w2 Proof intros Hw1 Hw revert w1 w2 τ Hw Hw1 refine ctree refine ind simpl try by constructor intros τ n ws1 ws2 IH inversion clear 1 constructor induction IH decompose Forall hyps auto intros t τ s w γ bss1 wxnss2 IH inversion clear 1 constructor induction IH decompose Forall hyps auto inversion clear 11 Qed Lemma union reset above Γ f Δ1 Δ2 w1 w2 τ Γ w1 Γ true f Δ1 Δ2 w2 τ ctree unshared w2 w1 Γ true f Δ1 Δ2 union reset w2 τ Proof intros H Γ revert w1 w2 τ refine ctree refine ind simpl by refine constructor intros τ n ws1 ws2 Hn IH refine constructor auto clear Hn induction IH decompose Forall hyps auto intros t τ s w γ bss1 w γ bss2 Ht IH Hindet1 Hindet2 Hlen refine constructor eauto clear Ht Hlen induction IH decompose Forall hyps constructor auto refine constructor eauto using ctree flatten refine refine constructor eauto refine constructor eauto Qed Lemma union reset refine Γ α f Δ1 Δ2 w1 w2 τ Γ w1 Γ α f Δ1 Δ2 w2 τ union reset w1 Γ α f Δ1 Δ2 union reset w2 τ Proof intros Hw apply ctree leaf refine refine eauto using union reset typed revert w1 w2 τ Hw refine ctree refine ind simpl try by intros constructor eauto 1 intros τ n ws1 ws2 IH constructor auto elim IH constructor eauto intros t τ s w γ bss1 w γ bss2 IH H γ bs constructor eauto elim IH constructor eauto elim H γ bs constructor eauto constructor eauto using ctree flatten refine Qed Lemma ctree flatten unflatten refine Γ f Δ1 Δ2 w γ bs τ Γ Γ Δ1 w τ Forall sep unshared γ bs ctree flatten w Γ true f Δ1 Δ2 γ bs w Γ true f Δ1 Δ2 ctree unflatten Γ τ γ bs τ Proof intros rewrite right id L f orb diag true apply ctree refine compose with Δ1 ctree unflatten Γ τ ctree flatten w auto erewrite ctree unflatten flatten by eauto apply union reset above eauto using ctree refine id eauto using pbits refine shared apply ctree unflatten refine eauto using ctree typed type valid Qed Lemma ctree lookup seg refine Γ α f Δ1 Δ2 w1 w2 τ rs w3 Γ w1 Γ α f Δ1 Δ2 w2 τ w1 Γ rs Some w3 w4 w2 Γ rs Some w4 w3 Γ α f Δ1 Δ2 w4 type of w3 Proof intros Hw Hrs cut w4 w2 Γ rs Some w4 ctree leaf refine Γ α f Δ1 Δ2 w3 w4 intros w4 exists w4 split auto destruct ctree lookup seg Some Γ Δ1 w1 τ rs w3 as ctree lookup seg Some Γ Δ2 w2 τ rs w4 as eauto simplify type equality eauto using ctree leaf refine refine destruct Hw rs change ctree refine Γ α f Δ1 Δ2 with refineT Γ α f Δ1 Δ2 in pattern w3 apply ctree lookup seg inv Hrs simpl clear Hrs intros simplify option equality decompose Forall hyps eauto intros repeat simplify option equality decompose Forall hyps eauto intros simplify option equality eauto intros simplify option equality by eauto using pbits refine unshared ctree flatten refine eexists split eauto eapply ctree refine leaf eauto using ctree unflatten refine ctree flatten refine intros simplify option equality by eauto using pbits refine unshared eexists eauto using ctree refine leaf ctree unflatten refine intros destruct α try done simplify option equality decompose Forall hyps rewrite take app alt by by erewrite Forall2 length by eauto eexists eauto using ctree refine leaf ctree flatten unflatten refine intros simplify option equality eexists split eauto eapply ctree refine leaf eauto using ctree unflatten refine ctree flatten refine Qed Lemma ctree lookup refine Γ α f Δ1 Δ2 w1 w2 τ r w3 Γ w1 Γ α f Δ1 Δ2 w2 τ w1 Γ r Some w3 w4 w2 Γ r Some w4 w3 Γ α f Δ1 Δ2 w4 type of w3 Proof intros H Γ revert w1 w2 τ induction r as rs r IH using rev ind simpl intros rewrite ctree lookup nil simplify type equality erewrite ctree refine type of l by eauto eauto intros w1 w2 rewrite ctree lookup snoc intros simplify option equality edestruct ctree lookup seg refine Γ α f Δ1 Δ2 w1 w2 τ rs as simplify option equality eauto Qed Lemma ctree lookup refine both Γ α f Δ1 Δ2 w1 w2 τ r w3 w4 Γ w1 Γ α f Δ1 Δ2 w2 τ w1 Γ r Some w3 w2 Γ r Some w4 w3 Γ α f Δ1 Δ2 w4 type of w3 Proof intros destruct ctree lookup refine Γ α f Δ1 Δ2 w1 w2 τ r w3 as simplify equality auto Qed Lemma ctree alter seg refine Γ α f Δ1 Δ2 g1 g2 w1 w2 τ rs w3 w4 Γ w1 Γ α f Δ1 Δ2 w2 τ w1 Γ rs Some w3 w2 Γ rs Some w4 g1 w3 Γ α f Δ1 Δ2 g2 w4 type of w3 ctree unmapped g1 w3 ctree alter seg Γ g1 rs w1 Γ α f Δ1 Δ2 ctree alter seg Γ g2 rs w2 τ Proof intros Hw Hw3 Hw4 Hgw cut ctree leaf refine Γ α f Δ1 Δ2 ctree alter seg Γ g1 rs w1 ctree alter seg Γ g2 rs w2 intros assert Γ Δ2 g2 w4 type of w4 destruct ctree lookup seg Some Γ Δ1 w1 τ rs

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


  • Module memory_trees_separation
    ws2 IH τ Hw pattern τ apply ctree typed inv l Hw clear τ Hw intros Hws2 Hlen typed constructor auto clear Hlen revert τ Hws2 induction IH intros decompose Forall hyps auto intros t w γ bss1 w γ bss2 IH H γ bs τ Hw pattern τ apply ctree typed inv l Hw clear τ Hw intros τ s Ht Hws2 H γ bs2 Hlen typed constructor eauto clear Hlen H γ bs2 Ht revert τ s Hws2 induction IH intros decompose Forall hyps auto clear Hlen Ht Hws2 IH induction H γ bs decompose Forall hyps eauto using pbits disjoint valid clear Hlen Ht Hws2 H γ bs2 IH induction H γ bs decompose Forall hyps eauto using pbits disjoint indetified rewrite Hlen elim H γ bs intros f equal auto intros decompose Forall hyps naive solver intros t τ Hw pattern τ apply ctree typed inv l Hw intros typed constructor eauto using pbits disjoint valid intros decompose Forall hyps naive solver intros t i w1 γ bs1 γ bs2 τ Hw pattern τ apply ctree typed inv l Hw clear τ Hw intros τ s τ intros assert length γ bs2 bit size of Γ unionT t erewrite Forall2 length by eauto auto econstructor eauto using pbits disjoint valid ctree flatten valid Qed Lemma ctree unflatten disjoint Γ τ γ bs1 γ bs2 Γ Γ τ γ bs1 γ bs2 ctree unflatten Γ τ γ bs1 ctree unflatten Γ τ γ bs2 Proof intros H Γ H τ revert τ H τ γ bs1 γ bs2 refine type env ind H Γ intros rewrite ctree unflatten base by constructor intros τ n IH γ bs1 γ bs2 H γ bs rewrite ctree unflatten array constructor revert γ bs1 γ bs2 H γ bs induction n simpl intros constructor auto intros t τ s Ht IH γ bs1 γ bs2 H γ bs erewrite ctree unflatten compound by eauto constructor auto revert γ bs1 γ bs2 H γ bs clear Ht unfold struct unflatten induction bit size of fields τ s H Γ intros decompose Forall hyps constructor simpl auto revert γ bs1 γ bs2 H γ bs clear Ht IH unfold struct unflatten induction bit size of fields τ s H Γ intros constructor simpl auto using pbits indetify disjoint Qed Lemma ctree unflatten union Γ τ γ bs1 γ bs2 Γ Γ τ γ bs1 γ bs2 ctree unflatten Γ τ γ bs1 γ bs2 ctree unflatten Γ τ γ bs1 ctree unflatten Γ τ γ bs2 Proof intros H Γ H τ revert τ H τ γ bs1 γ bs2 refine type env ind H Γ intros by rewrite ctree unflatten base intros τ n IH γ bs1 γ bs2 H γ bs rewrite ctree unflatten array f equal revert γ bs1 γ bs2 H γ bs induction n simpl intros f equal rewrite zip with take zip with drop auto intros t τ s Ht IH γ bs1 γ bs2 H γ bs erewrite ctree unflatten compound by eauto f equal auto revert γ bs1 γ bs2 H γ bs clear Ht unfold struct unflatten induction bit size of fields τ s H Γ intros decompose Forall hyps repeat f equal simpl rewrite fmap drop zip with take pbits indetify union zip with drop eauto Qed Lemma ctree unflatten subseteq Γ τ γ bs1 γ bs2 Γ Γ τ γ bs1 γ bs2 ctree unflatten Γ τ γ bs1 ctree unflatten Γ τ γ bs2 Proof intros rewrite seps union difference γ bs1 γ bs2 by done rewrite ctree unflatten union eauto using seps disjoint difference apply ctree union subseteq l ctree unflatten disjoint eauto using seps disjoint difference Qed Lemma ctree flatten unflatten disjoint Γ Δ w τ ys Γ Γ Δ w τ ys ctree flatten w Forall sep unmapped ys ctree unflatten Γ τ ys w Proof intros H Γ Hw revert w τ Hw ys refine ctree typed ind by constructor intros ws τ Hws IH ys Hys Hys rewrite ctree unflatten array simplify equality constructor revert ys Hys Hys induction IH intros decompose Forall hyps rewrite take app alt drop app alt by erewrite Forall2 length by eauto auto constructor auto intros t w γ bss τ s Ht Hws IH Hlen ys Hys Hys erewrite ctree unflatten compound by eauto simplify equality clear Ht constructor revert dependent w γ bss revert dependent ys unfold field bit padding struct unflatten induction bit size of fields τ s H Γ intros decompose Forall hyps rewrite take app alt drop app alt by erewrite app length Forall2 length by eauto solve length rewrite pbits indetify unmapped by auto constructor eauto intros t i τ s w γ bs τ ys Hys Hys erewrite ctree unflatten compound by eauto decompose Forall hyps constructor eauto using ctree typed sep valid intros erewrite ctree unflatten compound by eauto by constructor Qed Lemma ctree new disjoint l Γ Δ w τ Γ Γ Δ w τ ctree new Γ τ w Proof intros eapply ctree flatten unflatten disjoint eauto using sep unmapped empty eapply Forall2 replicate l Forall impl eauto using ctree flatten valid eauto using sep disjoint empty l pbit valid sep valid Qed Lemma ctree new disjoint r Γ Δ w τ Γ Γ Δ w τ w ctree new Γ τ Proof intros symmetry eauto using ctree new disjoint l Qed Lemma ctree new union l Γ Δ w τ Γ Γ Δ w τ ctree new Γ τ w w Proof eauto using ctree left id ctree new disjoint l ctree new Forall Qed Lemma ctree new union r Γ Δ w τ Γ Γ Δ w τ w ctree new Γ τ w Proof eauto using ctree right id ctree new disjoint r ctree new Forall Qed Lemma ctrees new union l Γ Δ ws τ n Γ Γ Δ ws τ length ws n replicate n ctree new Γ τ ws ws Proof intros Hws induction Hws f equal eauto using ctree new union l Qed Lemma ctree new subseteq Γ Δ w τ Γ Γ Δ w τ ctree new Γ τ w Proof intros erewrite ctree new union l w by eauto eauto using ctree union subseteq l ctree new disjoint l Qed Lemma ctree lookup seg disjoint Γ Δ1 Δ2 w1 w2 τ rs w1 w2 Γ Γ Δ1 w1 τ Γ Δ2 w2 τ w1 w2 w1 Γ rs Some w1 w2 Γ rs Some w2 w1 w2 Proof intros Hw1 Hw2 Hw Hrs1 Hrs2 destruct Hw rs pattern w1 apply ctree lookup seg inv Hrs1 clear Hrs1 pattern w2 apply ctree lookup seg inv Hrs2 clear Hrs2 intros decompose Forall hyps eauto using ctree unflatten disjoint ctree flatten disjoint apply ctree typed inv l Hw2 intros simplify equality rewrite take app alt by erewrite Forall2 length by eauto auto eauto using ctree flatten unflatten disjoint apply ctree typed inv l Hw1 intros simplify equality rewrite take app alt by erewrite Forall2 length by eauto auto symmetry eauto using ctree flatten unflatten disjoint Qed Lemma ctree lookup disjoint Γ Δ1 Δ2 w1 w2 τ r w1 w2 Γ Γ Δ1 w1 τ Γ Δ2 w2 τ w1 w2 w1 Γ r Some w1 w2 Γ r Some w2 w1 w2 Proof intros revert w1 w2 induction r as rs r intros w1 w2 by intros simplify type equality rewrite ctree lookup cons intros destruct w1 Γ r as w1 eqn w2 Γ r as w2 eqn simplify equality destruct ctree lookup Some Γ Δ1 w1 τ r w1 as σ1 auto destruct ctree lookup Some Γ Δ2 w2 τ r w2 as σ1 auto simplify type equality eauto 3 using ctree lookup seg disjoint Qed Lemma ctree lookup seg subseteq Γ w1 w2 rs w1 Γ w1 w2 w1 Γ rs Some w1 ctree Forall sep unmapped w1 w2 w2 Γ rs Some w2 w1 w2 Proof intros Hw Hrs1 destruct Hw rs pattern w1 apply ctree lookup seg inv Hrs1 clear Hrs1 intros decompose Forall hyps eauto 1 simplify option equality eauto simplify option equality eauto simplify option equality eauto simplify option equality by eauto using seps unshared weaken ctree unshared weaken eexists split eauto using ctree unflatten subseteq ctree flatten subseteq simplify option equality by eauto using seps unshared weaken eexists split eauto eauto using ctree unflatten subseteq exfalso naive solver eauto using ctree unflatten Forall le pbit unmapped indetify Qed Lemma ctree lookup subseteq Γ w1 w2 r w1 Γ w1 w2 w1 Γ r Some w1 ctree Forall sep unmapped w1 w2 w2 Γ r Some w2 w1 w2 Proof intros revert w1 induction r as rs r IH intros w1 w2 intros simplify type equality by exists w2 rewrite ctree lookup cons intros destruct w1 Γ r as w1 eqn simplify equality destruct IH w1 as eauto using ctree lookup seg Forall pbit unmapped indetify csimpl eauto using ctree lookup seg subseteq Qed Lemma ctree alter seg disjoint Γ Δ g w1 w2 τ rs w1 Γ Γ Δ w1 τ w1 w2 w1 Γ rs Some w1 ctree unmapped g w1 w2 w1 w2 g w1 w2 ctree alter seg Γ g rs w1 w2 Proof intros Hw1 Hw Hw1 Hrs revert w1 w2 Hw Hw1 Hw1 Hrs refine ctree disjoint ind by destruct rs intros τ ws1 ws2 Hrs Hg destruct rs simplify option equality constructor apply Forall2 alter l auto 1 intros decompose Forall hyps eauto intros t w γ bss1 w γ bss2 Hws H γ bss Hrs destruct rs as i pattern w1 apply ctree lookup seg inv Hrs clear Hrs intros w1 γ bs simpl constructor apply Forall2 alter l elim Hws constructor simpl eauto intros decompose Forall hyps eauto apply Forall2 alter l elim H γ bss constructor simpl eauto intros decompose Forall hyps eauto intros t i w1 w2 γ bs1 γ bs2 Hum Hrs destruct rs as i pattern w1 apply ctree lookup seg inv Hrs clear Hrs intros simplify option equality constructor naive solver intros τ s τ destruct Hum simplify equality eauto using seps disjoint unshared unmapped ctree flatten disjoint intros t γ bs1 γ bs2 Hrs destruct rs as i pattern w1 apply ctree lookup seg inv Hrs clear Hrs intros τ s τ simplify option equality constructor rewrite take drop bit size of Γ τ γ bs2 apply Forall2 app erewrite pbits indetify mask unmapped ctree flatten unflatten le Γ τ by eauto using seps disjoint unshared unmapped eauto using ctree flatten disjoint ctree unflatten disjoint erewrite pbits indetify unmapped by eauto using seps disjoint unshared unmapped eauto using pbits indetify disjoint eauto using seps disjoint unshared unmapped eapply ctree disjoint valid l eauto using ctree flatten disjoint ctree unflatten disjoint naive solver intros t i γ bs1 w2 γ bs2 Hum Hrs destruct rs as i pattern w1 apply ctree lookup seg inv Hrs clear Hrs intros τ s τ destruct Hum simplify equality rewrite Forall app eauto using seps disjoint unshared unmapped intros t i w1 γ bs1 γ bs2 H γ bs2 Hw1 Hrs apply ctree typed inv l Hw1 clear Hw1 τ intros τ s τ destruct rs as i pattern w1 apply ctree lookup seg inv Hrs clear Hrs rewrite Forall2 app inv l in H γ bs2 destruct H γ bs2 as γ bs2 γ bs2 intros Hw simplify option equality decompose Forall hyps constructor auto apply Forall2 app auto erewrite pbits indetify mask unmapped type mask Γ τ γ bs2 ctree flatten unflatten Γ τ γ bs2 by erewrite Forall2 length ctree flatten by eauto eauto apply ctree flatten disjoint Hw symmetry eauto using ctree flatten unflatten disjoint eapply ctree disjoint valid l Hw symmetry eauto using ctree flatten unflatten disjoint naive solver intros τ simplify option equality constructor auto rewrite take drop bit size of Γ τ γ bs2 apply Forall2 app auto erewrite pbits indetify mask unmapped ctree flatten unflatten le Γ τ by eauto using seps disjoint unshared unmapped eauto using ctree flatten disjoint ctree unflatten disjoint erewrite pbits indetify unmapped by eauto using seps disjoint unshared unmapped eauto using pbits indetify disjoint eapply ctree disjoint valid l eauto using ctree flatten disjoint ctree unflatten disjoint naive solver Qed Lemma ctree alter disjoint Γ Δ g w1 w2 τ r w1 Γ Γ Δ w1 τ w1 w2 w1 Γ r Some w1 ctree unmapped g w1 w2 w1 w2 g w1 w2 ctree alter Γ g r w1 w2 Proof intros revert g w1 induction r as rs r intros g w1 intros simplify type equality eauto rewrite ctree lookup cons intros destruct w1 Γ r as w1 eqn simplify equality destruct ctree lookup Some Γ Δ w1 τ r w1 as σ1 eauto 8 using ctree alter lookup seg Forall ctree alter seg disjoint Qed Lemma ctree alter seg union Γ Δ g w1 w2 τ rs w1 Γ Γ Δ w1 τ w1 w2 w1 Γ rs Some w1 ctree unmapped g w1 w2 w1 w2 g w1 w2 w2 w1 w2 g w1 w2 g w1 w2 ctree alter seg Γ g rs w1 w2 ctree alter seg Γ g rs w1 w2 Proof intros Hw1 Hw Hw1 Hrs revert w1 w2 Hw Hw1 Hw1 Hrs refine ctree disjoint ind by destruct rs intros τ ws1 ws2 Hws Hrs Hg Hg destruct rs as i simplify option equality f equal revert i Hrs induction Hws intros simplify equality f equal eauto intros t w γ bss1 w γ bss2 Hws Hrs destruct rs as i pattern w1 apply ctree lookup seg inv Hrs clear Hrs intros w1 γ bs Hrs Hg Hg f equal revert i Hrs induction Hws as intros simplify equality repeat f equal eauto intros t i w1 w2 γ bs1 γ bs2 Hum Hrs destruct rs as i pattern w1 apply ctree lookup seg inv Hrs clear Hrs intros simplify option equality f equal auto intros τ s τ destruct Hum simplify equality eauto using seps disjoint unshared unmapped ctree flatten disjoint intros t γ bs1 γ bs2 Hw1 Hrs apply ctree typed inv l Hw1 clear Hw1 τ intros τ s destruct rs as i pattern w1 apply ctree lookup seg inv Hrs clear Hrs intros Hg Hg simplify option equality erewrite Forall2 length by eapply ctree flatten disjoint Hg ctree unflatten disjoint eauto rewrite ctree flatten unflatten le mask length take length le by eauto f equal by rewrite zip with take ctree unflatten union Hg ctree merge flatten ctree flatten unflatten le pbits indetify mask unmapped by eauto using ctree unflatten Forall le ctree unflatten disjoint seps disjoint unshared unmapped pbit unmapped indetify by rewrite zip with drop pbits indetify union pbits indetify unmapped drop γ bs2 by eauto using seps disjoint unshared unmapped intros t i γ bs1 w2 γ bs2 Hum Hrs destruct rs as i pattern w1 apply ctree lookup seg inv Hrs clear Hrs intros τ s τ destruct Hum simplify equality rewrite Forall app eauto using seps disjoint unshared unmapped intros t i w1 γ bs1 γ bs2 H γ bs2 Hw1 Hrs apply ctree typed inv l Hw1 clear Hw1 τ intros τ s τ Hw1 destruct rs as i pattern w1 apply ctree lookup seg inv Hrs clear Hrs rewrite Forall2 app inv l in H γ bs2 destruct H γ bs2 as γ bs2 γ bs2 intros Hg Hg simplify option equality decompose Forall hyps assert length γ bs2 bit size of Γ τ erewrite Forall2 length by eauto solve length assert w1 ctree unflatten Γ τ γ bs2 symmetry eauto using ctree flatten unflatten disjoint assert ctree flatten g w1 γ bs2 rewrite pbits indetify mask unmapped type mask Γ τ γ bs2 ctree flatten unflatten by eauto by apply ctree flatten disjoint Hg clear Hw1 rewrite take app alt drop app alt by auto rewrite pbits indetify mask unmapped type mask Γ τ γ bs2 ctree flatten unflatten ctree merge flatten by eauto using ctree unflatten Forall le pbit unmapped indetify f equal auto intros τ Hg Hg simplify option equality assert length γ bs2 bit size of Γ unionT t by erewrite Forall2 length by eauto rewrite ctree flatten merge zip with app zip with take zip with drop take drop by done erewrite Forall2 length by eapply ctree flatten disjoint Hg ctree unflatten disjoint eauto rewrite ctree flatten unflatten le mask length take length le by eauto f equal by rewrite ctree unflatten union Hg ctree merge flatten ctree flatten unflatten pbits indetify mask unmapped by eauto using ctree unflatten Forall le ctree unflatten disjoint seps disjoint unshared unmapped pbit unmapped indetify by rewrite pbits indetify union pbits indetify unmapped drop γ bs2 by auto Qed Lemma ctree alter union Γ Δ g w1 w2 τ r w1 Γ Γ Δ w1 τ w1 w2 w1 Γ r Some w1 ctree unmapped g w1 w2 w1 w2 g w1 w2 w2 w1 w2 g w1 w2 g w1 w2 ctree alter Γ g r w1 w2 ctree alter Γ g r w1 w2 Proof intros revert g w1 induction r as rs r IH intros g w1 intros simplify type equality eauto rewrite ctree lookup cons intros destruct w1 Γ r as w1 eqn simplify equality destruct ctree lookup Some Γ Δ w1 τ r w1 as σ1 auto eapply IH eauto using ctree alter lookup seg Forall ctree alter seg disjoint ctree alter seg union Qed Lemma ctree lookup byte disjoint Γ w1 w2 i c1 c2 Γ w1 w2 w1 Γ i Some c1 w2 Γ i Some c2 c1 c2 Proof unfold lookupE ctree lookup byte sublist lookup intros simplify option equality auto using ctree unflatten disjoint TBase valid TInt valid ctree flatten disjoint Qed Lemma ctree lookup byte subseteq Γ w1 w2 i c1 Γ w1 w2 w1 Γ i Some c1 c2 w2 Γ i Some c2 c1 c2 Proof unfold lookupE ctree lookup byte intros destruct

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

  • Module memory_map
    destruct m as m intros simplify option equality eauto using ctree lookup freeze proper Qed Lemma cmap lookup unfreeze Γ m a w m Γ a Some w m Γ freeze false a Some w Proof unfold lookupE cmap lookup intros case option guard simplify equality rewrite addr index freeze addr ref freeze addr ref byte freeze rewrite option guard True by auto using addr strict freeze 2 destruct m Γ addr ref as w eqn simplify equality erewrite cmap lookup ref le by eauto using cmap lookup ref le ref freeze le r simpl by rewrite decide iff addr is obj freeze Qed Lemma cmap lookup ref Some Γ Δ m o r w Γ Γ Δ m m Γ o r Some w τ σ Δ o τ Γ r τ σ Γ Δ w σ Proof destruct m as m simpl intros Hm destruct m o as w μ eqn Hw simplify equality destruct cmap valid Obj Γ Δ CMap m o w μ as τ auto destruct ctree lookup Some Γ Δ w τ r w as σ eauto Qed Lemma cmap lookup typed Γ Δ m a w σ Γ Γ Δ m Γ Δ a TType σ m Γ a Some w Γ Δ w σ Proof unfold lookupE cmap lookup intros case option guard simplify equality destruct m Γ as w eqn simplify equality destruct cmap lookup ref Some Γ Δ m addr index a addr ref Γ a w as τ σ auto simplify option equality simplify type equality cut σ σ by intros erewrite addr is obj type σ by eauto assert Δ addr index a addr type object a by eauto using addr typed index simplify type equality eauto using ref set offset typed unique addr typed ref base typed erewrite addr not is obj type by eauto eauto using ctree lookup byte typed Qed Lemma cmap lookup strict Γ m a w m Γ a Some w addr strict Γ a Proof by unfold lookupE cmap lookup intros simplify option equality Qed Lemma cmap lookup Some Γ Δ m w a Γ Γ Δ m m Γ a Some w Γ Δ w type of w Proof unfold lookupE cmap lookup intros case option guard simplify equality destruct m Γ as w eqn simplify equality destruct cmap lookup ref Some Γ Δ m addr index a addr ref Γ a w as τ σ auto simplify option equality eauto using ctree lookup byte typed type of typed Qed Lemma cmap lookup ref cons Γ m o rs r m Γ o rs r m Γ o r lookupE Γ rs Proof destruct m as m simpl by destruct m o as w μ Qed Lemma cmap lookup ref app Γ m o r1 r2 m Γ o r1 r2 m Γ o r2 lookupE Γ r1 Proof destruct m as m simpl destruct m o as w μ eqn Hw simplify equality auto by rewrite ctree lookup app Qed Lemma cmap lookup elt Γ Δ m a rs σ σ Γ Γ Δ a TType σ addr strict Γ a Γ rs σ σ m Γ addr elt Γ rs a m Γ a lookupE Γ rs Proof unfold lookupE at 1 3 cmap lookup intros simpl rewrite option guard True by eauto using addr elt strict erewrite addr ref elt addr ref byte elt addr index elt by eauto rewrite cmap lookup ref cons destruct m Γ as w simpl auto rewrite decide True by eauto using addr ref byte is obj parent simpl destruct w Γ rs simpl auto by rewrite decide True by eauto using addr ref byte is obj Qed Lemma cmap alter ref le Γ g o r1 r2 m r1 r2 cmap alter ref Γ g o r1 m cmap alter ref Γ g o r2 m Proof destruct m as m intros f equal by erewrite ctree alter le by eauto Qed Lemma cmap erase alter ref Γ g m o r cmap erase cmap alter ref Γ g o r m cmap alter ref Γ g o r cmap erase m Proof destruct m as m f equal apply map eq intros o destruct decide o o simplify map equality auto by destruct m as Qed Lemma cmap erase alter Γ g m a cmap erase cmap alter Γ g a m cmap alter Γ g a cmap erase m Proof apply cmap erase alter ref Qed Lemma cmap alter ref memenv of Γ Δ m g o r w Γ Γ Δ m m Γ o r Some w type of g w type of w cmap alter ref Γ g o r m m Proof destruct m as m intros apply map eq intros o simpl destruct decide o o simplify map equality auto destruct m o as w μ eqn simplify equality do 2 f equal destruct cmap valid Obj Γ Δ CMap m o w μ as τ auto destruct ctree lookup Some Γ Δ w τ r w as σ eauto using ctree alter type of weak type of typed Qed Lemma cmap alter memenv of Γ Δ m g a w Γ Γ Δ m m Γ a Some w type of g w type of w cmap alter Γ g a m m Proof unfold lookupE cmap lookup intros case option guard simplify equality destruct m Γ as w eqn simplify equality eapply cmap alter ref memenv of eauto simplify option equality eauto cut Γ type of w eauto using ctree alter byte type of destruct cmap lookup ref Some Γ Δ m addr index a addr ref Γ a w as simplify type equality eauto using ctree typed type valid Qed Lemma cmap alter ref valid Γ Δ m g o r w Γ Γ Δ m m Γ o r Some w Γ Δ g w type of w ctree unmapped g w Γ Δ cmap alter ref Γ g o r

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

  • Module memory_map_refine
    as auto assert index alive m1 o1 as help unfold index alive in help apply index alive spec eauto using memenv refine alive r destruct index typed lookup cmap m1 o1 τ as w1 μ simplify map equality try done destruct Hm o1 o2 w1 μ as w1 τ simplify type equality auto exists w1 w1 τ split ands auto using ctree refine inverse Qed Lemma cmap refine weaken Γ Γ α α f f Δ1 Δ2 m1 m2 Γ m1 Γ α f Δ1 Δ2 m2 Γ Γ α α Δ1 Γ α f Δ2 meminj extend f f Δ1 Δ2 m1 Γ α f Δ1 Δ2 m2 Proof intros Hm1 H Δ Hm Hf split split ands eauto using cmap valid weaken memenv valid weaken cmap valid memenv valid intros o1 o2 r w1 μ destruct cmap valid Obj Γ Δ1 m1 o1 w1 μ as τ auto destruct Hm o1 o2 r w1 μ as w2 w2 τ eauto using option eq 1 meminj extend left exists w2 w2 τ split ands eauto using ctree refine weaken ctree lookup weaken option eq 1 alt Qed Lemma cmap lookup alter refine Γ Δ g m a w τ Γ Γ Δ m Γ Δ a TType τ m Γ a Some w Γ Δ g w τ ctree unshared g w w cmap alter Γ g a m Γ a Some w w Γ true Δ g w τ Proof intros destruct decide addr is obj a exists g w erewrite cmap lookup alter by eauto eauto using ctree refine id exists ctree lookup byte after Γ addr type base a addr ref byte Γ a g w split eauto using cmap lookup alter not obj assert τ ucharT by eauto using addr not is obj type subst eauto using ctree lookup byte alter refine Qed Lemma cmap lookup ref refine Γ α f Δ1 Δ2 m1 m2 o1 r1 o2 r2 w1 Γ m1 Γ α f Δ1 Δ2 m2 f o1 Some o2 r2 m1 Γ o1 r1 Some w1 w2 m2 Γ o2 r1 r2 Some w2 w1 Γ α f Δ1 Δ2 w2 type of w1 Proof destruct m1 as m1 m2 as m2 simpl intros Hm1 Hm Ha Hw1 destruct m1 o1 as w1 μ eqn simplify equality destruct Hm o1 o2 r2 w1 μ as w2 w2 τ2 Hr auto csimpl rewrite ctree lookup app Hr csimpl eauto using ctree lookup refine Qed Lemma cmap lookup refine Γ α f Δ1 Δ2 m1 m2 a1 a2 w1 τ Γ m1 Γ α f Δ1 Δ2 m2 a1 Γ α f Δ1 Δ2 a2 TType τ m1 Γ a1 Some w1 w2 m2 Γ a2 Some w2 w1 Γ α f Δ1 Δ2 w2 τ Proof intros assert type of w1 τ by eauto using type of correct cmap lookup typed addr refine typed l unfold lookupE cmap lookup in case option guard simplify equality rewrite option guard True by eauto using addr

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

  • Module memory_map_separation
    Hms rewrite cmap union list valid by eauto using sep disjoint contains contains delete assert n ms vec n i Γ Δ ms Γ Δ ms i intros by rewrite Forall vlookup revert i j Hms induction ms inversion clear 1 intros inv all vec fin decompose Forall hyps eauto with congruence Qed Lemma cmap lookup ref disjoint Γ Δ m1 m2 o r w1 w2 Γ Γ Δ m1 Γ Δ m2 m1 m2 m1 Γ o r Some w1 m2 Γ o r Some w2 w1 w2 Proof destruct m1 as m1 m2 as m2 intros Hm simplify equality specialize Hm o destruct m1 o as w1 μ eqn Hw1 m2 o as w2 μ eqn Hw2 simplify equality destruct cmap valid Obj Γ Δ CMap m1 o w1 μ as τ cmap valid Obj Γ Δ CMap m2 o w2 μ as simplify type equality intuition eauto 3 using ctree lookup disjoint Qed Lemma cmap lookup disjoint Γ Δ m1 m2 a w1 w2 Γ Γ Δ m1 Γ Δ m2 m1 m2 m1 Γ a Some w1 m2 Γ a Some w2 w1 w2 Proof unfold lookupE cmap lookup intros case option guard simplify equality destruct m1 as w1 eqn Hw1 m2 as w2 eqn Hw2 simplify option equality eauto 3 using ctree lookup byte disjoint cmap lookup ref disjoint Qed Lemma cmap lookup ref subseteq Γ m1 m2 o r w1 Γ m1 m2 m1 Γ o r Some w1 ctree Forall sep unmapped w1 w2 m2 Γ o r Some w2 w1 w2 Proof destruct m1 as m1 m2 as m2 simpl intros Hm specialize Hm o destruct m1 o as w1 μ eqn m2 o as w2 μ eqn simplify equality try done destruct ctree lookup subseteq Γ w1 w2 r w1 as w2 simplify option equality intuition eauto Qed Lemma cmap lookup subseteq Γ m1 m2 a w1 Γ m1 m2 m1 Γ a Some w1 ctree Forall sep unmapped w1 w2 m2 Γ a Some w2 w1 w2 Proof unfold lookupE cmap lookup intros case option guard simplify equality destruct m1 as w1 eqn Hw1 simplify equality assert ctree unmapped w1 simplify option equality eauto using ctree lookup byte Forall pbit unmapped indetify destruct cmap lookup ref subseteq Γ m1 m2 addr index a addr ref Γ a w1 as w2 simpl auto simplify option equality by eauto using ctree unshared weaken eauto using ctree lookup byte subseteq Qed Lemma cmap alter ref disjoint Γ Δ1 m1 m2 g o r w1 Γ Γ Δ1 m1 m1 m2 m1 Γ o r Some w1 ctree unmapped g w1 w2 w1 w2 g w1 w2 cmap alter ref Γ g o r m1 m2 Proof assert w ctree empty w ctree unmapped w eauto using Forall impl sep unmapped empty alt destruct m1 as m1 m2 as m2 simpl intros Hm1 Hm o specialize Hm o destruct decide o o simplify map equality auto destruct m1 o as w1 μ eqn simplify equality auto destruct cmap valid Obj Γ Δ1 CMap m1 o w1 μ as τ auto simplify equality destruct m2 o as w2 μ simplify equality auto intuition eauto using ctree alter disjoint ctree alter lookup Forall assert w2 w1 w2 as w2 exists ctree new Γ τ symmetry eauto using ctree new disjoint l split eapply ctree disjoint valid l ctree alter disjoint intuition eauto intuition eauto using ctree alter lookup Forall Qed Lemma cmap alter disjoint Γ Δ1 m1 m2 g a w1 τ1 Γ Γ Δ1 m1 m1 m2 Γ Δ1 a TType τ1 m1 Γ a Some w1 Γ Δ1 g w1 τ1 ctree unmapped g w1 w2 w1 w2 g w1 w2 cmap alter Γ g a m1 m2 Proof assert w ctree empty w ctree unmapped w eauto using Forall impl sep unmapped empty alt unfold lookupE cmap lookup intros case option guard simplify equality destruct m1 as w1 eqn Hw1 simplify equality destruct cmap lookup ref Some Γ Δ1 m1 addr index a addr ref Γ a w1 as τ σ auto eapply cmap alter ref disjoint eauto simplify option equality eauto assert τ1 ucharT T by eauto using addr not is obj type subst intuition eauto 3 using ctree alter byte unmapped intros simplify option equality eauto using ctree alter byte disjoint Qed Lemma cmap alter ref union Γ Δ1 m1 m2 g o r w1 τ1 Γ Γ Δ1 m1 m1 m2 m1 Γ o r Some w1 ctree unmapped g w1 w2 w1 w2 g w1 w2 w2 w1 w2 g w1 w2 g w1 w2 cmap alter ref Γ g o r m1 m2 cmap alter ref Γ g o r m1 m2 Proof destruct m1 as m1 m2 as m2 simpl intros Hm1 Hm unfold union at 2 sep union f equal apply map eq intros o specialize Hm o destruct decide o o simplify map equality rewrite lookup union with lookup alter lookup alter ne lookup union with by done auto destruct m1 o as w1 μ eqn simplify equality auto destruct cmap valid Obj Γ Δ1 CMap m1 o w1 μ as τ auto simplify equality destruct m2 o as w2 μ simplify equality do 2 f equal intuition eauto using ctree alter union Qed Lemma cmap alter union Γ Δ1 m1 m2 g a w1 τ1 Γ Γ Δ1 m1 m1 m2 Γ Δ1 a TType τ1 m1 Γ a Some w1 Γ Δ1 g w1 τ1 ctree unmapped g w1 w2 w1 w2 g w1 w2 w2 w1 w2 g w1 w2 g w1 w2 cmap alter Γ g a m1 m2 cmap alter Γ g a m1 m2 Proof unfold lookupE cmap lookup cmap alter intros case option guard simplify equality destruct m1 as w1 eqn Hw1 simplify equality destruct cmap lookup ref Some Γ Δ1 m1 addr index a addr ref Γ a w1 as τ σ auto eapply cmap alter ref union eauto simplify option equality eauto assert τ1 ucharT T

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

  • Module base_values
    τ b Proof split destruct vb inversion 1 constructor auto by apply ptr typed freeze β destruct 1 constructor auto by apply ptr typed freeze Qed Lemma base typed int frozen Γ Δ vb τ i Γ Δ vb intT τ i frozen vb Proof inversion clear 1 constructor Qed Properties of the base val flatten function Lemma base val flatten valid Γ Δ vb τ b Γ Δ vb τ b Γ Δ base val flatten Γ vb Proof destruct 1 simpl apply Forall replicate BIndet valid apply Forall replicate BIndet valid apply Forall fmap Forall true constructor apply Forall fmap eapply Forall impl Γ Δ eauto using ptr to bits valid BPtr valid eauto using char byte valid bits valid Qed Lemma base val flatten weaken Γ1 Γ2 Δ τ b vb Γ1 Γ1 Δ vb τ b Γ1 Γ2 base val flatten Γ1 vb base val flatten Γ2 vb Proof by destruct 2 intros simpl erewrite ptr to bits weaken bit size of weaken by eauto using TBase valid TVoid valid Qed Lemma base val flatten freeze Γ β vb base val flatten Γ freeze β vb base val flatten Γ vb Proof by destruct vb simpl rewrite ptr to bits freeze Qed Lemma base val flatten length Γ Δ vb τ b Γ Δ vb τ b length base val flatten Γ vb bit size of Γ τ b Proof destruct 1 simplify equality by rewrite replicate length by rewrite replicate length by rewrite fmap length bit size of int int to bits length by erewrite fmap length ptr to bits length alt type of correct by eauto by erewrite bit size of int int width char char byte valid bits by eauto Qed Properties of the base val unflatten function Inductive base val unflatten view Γ base type K list bit K base val K Prop base val of void bs base val unflatten view Γ voidT bs VVoid base val of int τ i β s length β s int width τ i base val unflatten view Γ intT τ i BBit β s VInt τ i int of bits τ i β s base val of ptr τ p p pbs ptr of bits Γ τ p pbs Some p base val unflatten view Γ τ p BPtr pbs VPtr p base val of byte bs length bs char bits Forall BIndet bs β s bs BBit β s base val unflatten view Γ ucharT bs VByte bs base val of byte indet bs length bs char bits Forall BIndet bs base val unflatten view Γ ucharT bs VIndet ucharT base val of int indet τ i bs τ i ucharT IT length bs int width τ i β s bs BBit β s base val unflatten view Γ intT τ i bs VIndet intT τ i base val of ptr indet 1 τ p pbs length pbs bit size of Γ τ p ptr of bits Γ τ p pbs None base val unflatten view Γ τ p BPtr pbs VIndet τ p base val of ptr indet 2 τ p bs length bs bit size of Γ τ p pbs bs BPtr pbs base val unflatten view Γ τ p bs VIndet τ p Lemma base val unflatten spec Γ τ b bs length bs bit size of Γ τ b base val unflatten view Γ τ b bs base val unflatten Γ τ b bs Proof intros Hbs unfold base val unflatten destruct τ b as τ i τ p constructor rewrite bit size of int in Hbs destruct mapM maybe BBit bs as β s eqn H β s rewrite maybe BBits spec in H β s subst rewrite fmap length in Hbs by constructor assert β s bs BBit β s setoid rewrite maybe BBits spec intros simpl in congruence destruct decide as H τ bs rewrite int width char in Hbs by constructor destruct decide τ i ucharT IT as rewrite int width char in Hbs constructor auto apply dec stable naive solver by constructor destruct mapM maybe BPtr bs as pbs eqn Hpbs csimpl rewrite maybe BPtrs spec in Hpbs subst rewrite fmap length in Hbs by destruct ptr of bits Γ τ p pbs as p eqn constructor constructor auto setoid rewrite maybe BPtrs spec intros simplify equality Qed Lemma base val unflatten weaken Γ1 Γ2 τ b bs Γ1 Γ1 τ b Γ1 Γ2 base val unflatten Γ1 τ b bs base val unflatten Γ2 τ b bs Proof intros unfold base val unflatten default repeat match goal with case match H context ptr of bits rewrite ptr of bits weaken Γ1 Γ2 in H by eauto using TPtr valid inv simplify option equality end auto Qed Lemma base val unflatten int Γ τ i β s length β s int width τ i base val unflatten Γ intT τ i BBit β s VInt τ i int of bits τ i β s Proof intro unfold base val unflatten by rewrite mapM fmap Some by done Qed Lemma base val unflatten ptr Γ τ p pbs p ptr of bits Γ τ p pbs Some p base val unflatten Γ τ p BPtr pbs VPtr p Proof intros feed inversion base val unflatten spec Γ τ p BPtr pbs simplify equality auto by erewrite fmap length ptr of bits length by eauto naive solver apply Forall fmap Forall true simpl eauto Qed Lemma base val unflatten byte Γ bs Forall BIndet bs β s bs BBit β s length bs char bits base val unflatten Γ ucharT bs VByte bs Proof intros feed inversion base val unflatten spec Γ ucharT bs simplify equality rewrite bit size of int int width char naive solver Qed Lemma base val unflatten indet Γ τ b bs τ b voidT Forall BIndet bs length bs bit size of Γ τ b base val unflatten Γ τ b bs VIndet τ b Proof intros assert τ i β

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

  • Module base_values_refine
    b Γ Δ vb τ b vb Γ α Δ vb τ b Proof destruct 1 constructor eauto using ptr refine id bits refine id char byte valid bits valid constructor eauto Qed Lemma base val refine compose Γ α1 α2 f1 f2 Δ1 Δ2 Δ3 vb1 vb2 vb3 τ b τ b Γ vb1 Γ α1 f1 Δ1 Δ2 vb2 τ b vb2 Γ α2 f2 Δ2 Δ3 vb3 τ b vb1 Γ α1 α2 f2 f1 Δ1 Δ3 vb3 τ b Proof intros Hvb1 Hvb2 assert τ b τ b as by eapply typed unique vb2 eauto using base val refine typed r base val refine typed l destruct Hvb1 inversion clear Hvb2 refine constructor auto refine constructor eauto using base val refine typed r inversion clear Hvb2 refine constructor by inversion clear Hvb2 refine constructor inversion clear Hvb2 refine constructor eauto using ptr refine compose ptr alive refine ptr refine typed l refine constructor eauto using base val refine typed r inversion clear Hvb2 refine constructor eauto using bits refine compose inversion clear Hvb2 refine constructor eauto using BBits refine bits refine compose refine constructor eauto using base val refine typed r by destruct α1 simpl eauto using bits refine compose true true BIndets refine BIndets valid Qed Lemma base val refine inverse Γ f Δ1 Δ2 vb1 vb2 τ b vb1 Γ false f Δ1 Δ2 vb2 τ b vb2 Γ false meminj inverse f Δ2 Δ1 vb1 τ b Proof destruct 1 try done constructor eauto using ptr refine inverse bits refine inverse Qed Lemma base val refine weaken Γ Γ α α f f Δ1 Δ2 Δ1 Δ2 vb1 vb2 τ b Γ vb1 Γ α f Δ1 Δ2 vb2 τ b Γ Γ α α Δ1 Γ α f Δ2 Δ1 ₘ Δ1 Δ2 ₘ Δ2 meminj extend f f Δ1 Δ2 vb1 Γ α f Δ1 Δ2 vb2 τ b Proof destruct 2 refine constructor eauto using base val typed weaken ptr refine weaken ptr typed weaken char byte valid weaken ptr dead weaken Forall2 impl bit refine weaken base type valid weaken Qed Lemma base val unflatten refine Γ α f Δ1 Δ2 τ b bs1 bs2 Γ Γ τ b bs1 Γ α f Δ1 Δ2 bs2 length bs1 bit size of Γ τ b base val unflatten Γ τ b bs1 Γ α f Δ1 Δ2 base val unflatten Γ τ b bs2 τ b Proof intros Hbs Hbs1 assert length bs2 bit size of Γ τ b as Hbs2 eauto using Forall2 length l assert α false α true as by destruct α auto feed destruct base val unflatten spec Γ τ b bs1 as τ i β s1 τ p1 pbs1 bs1 bs1 τ i bs1 τ pbs1 τ bs1 auto constructor rewrite BBits refine inv l Γ false f Δ1 Δ2 β s1 bs2 base val unflatten int by done constructor by apply int of bits typed destruct BPtrs refine inv l Γ f Δ1 Δ2

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

  • Module values
    typed ind simpl intros by erewrite base val flatten length by eauto intros vs τ IH rewrite bit size of array induction IH csimpl rewrite app length auto intros t vs τ s Ht Hvs IH rewrite bit size of struct τ s Ht by done simpl clear Ht revert vs Hvs IH induction bit size of fields τ s H Γ as τ sz Hn intros decompose Forall hyps done rewrite app length resize length f equal eauto intros by rewrite resize length intros t vs τ s Ht Hvs IH Hrep destruct bits list join as bs eqn Hbs simpl eauto using bits list join length by rewrite replicate length Qed Lemma val flatten valid Γ Δ v τ Γ Γ Δ v τ Γ Δ val flatten Γ v Proof intros H Γ Hv τ revert v τ Hv τ refine val typed ind simpl eauto using base val flatten valid intros vs τ Hvs IH induction IH decompose Forall hyps auto intros t vs τ s Ht Hvs IH rewrite Ht simpl clear Ht revert vs Hvs IH induction bit size of fields τ s H Γ intros decompose Forall hyps auto eauto intros t vs τ s Ht Hvs IH Hrep destruct bits list join as bs eqn Hbs simpl auto eapply bits list join valid eauto elim IH csimpl auto Qed Lemma val flatten weaken Γ1 Γ2 Δ1 v τ Γ1 Γ1 Γ2 Γ1 Δ1 v τ val flatten Γ1 v val flatten Γ2 v Proof intros revert v τ refine val typed ind simpl eauto using base val flatten weaken intros vs τ IH induction IH f equal auto intros t vs τ s Ht IH erewrite Ht lookup compound weaken by eauto simpl erewrite field bit sizes weaken by eauto f equal clear Ht generalize field bit sizes Γ2 τ s induction IH intros f equal auto with f equal intros f equal eauto using bit size of weaken TCompound valid intros t vs τ s Ht IH do 2 f equal eauto using bit size of weaken TCompound valid elim IH intros f equal auto Qed Ltac solve length repeat first rewrite take length rewrite drop length rewrite app length rewrite resize length rewrite fmap length rewrite replicate length erewrite ctree flatten length by eauto erewrite val flatten length by eauto rewrite zip with length erewrite base val flatten length by eauto match goal with context bit size of Γ τ match goal with H Γ t Some τ s H2 τ s Some τ unless bit size of Γ τ bit size of Γ unionT t by done assert bit size of Γ τ bit size of Γ unionT t by eauto using bit size of union lookup H Γ t Some τ unless bit size of Γ τ bit size of Γ unionT t by done assert bit size of Γ τ bit size of Γ unionT t by eauto using bit size of union singleton end end lia Hint Extern 0 length solve length Hint Extern 0 length solve length Hint Extern 0 length solve length Properties of the val unflatten function Lemma val unflatten base Γ τ b val unflatten Γ τ b λ bs VBase base val unflatten Γ τ b bs Proof unfold val unflatten by rewrite type iter base Qed Lemma val unflatten array Γ τ n val unflatten Γ τ n λ bs VArray τ array unflatten Γ val unflatten Γ τ τ n bs Proof unfold val unflatten by rewrite type iter array Qed Lemma val unflatten compound Γ c t τ s bs Γ Γ t Some τ s val unflatten Γ compoundT c t bs match c with Struct kind VStruct t struct unflatten Γ λ τ bs let τ sz bit size of Γ τ in val unflatten Γ τ take τ sz bs τ s bs Union kind VUnionAll t vals unflatten Γ τ s bs end Proof intros H Γ Ht unfold val unflatten erewrite type iter compound pointwise relation list bit K eq val K try done intros f equal by apply array unflatten weaken clear t τ s Ht bs intros f g t τ s Ht H τ s bs f equal eapply struct unflatten weaken Forall impl eauto eapply Forall fmap ext Forall impl eauto Qed Lemma val unflatten weaken Γ1 Γ2 τ bs Γ1 Γ1 τ Γ1 Γ2 val unflatten Γ1 τ bs val unflatten Γ2 τ bs Proof intros apply type iter weaken pointwise relation try done intros by erewrite base val unflatten weaken by eauto intros f equal by apply array unflatten weaken clear bs intros f g t τ s Ht H τ s Hfg bs f equal auto eapply struct unflatten weaken Forall impl eauto 1 auto using bit size of weaken with f equal clear Ht induction Hfg decompose Forall hyps f equal auto using bit size of weaken with f equal Qed Lemma vals unflatten weaken Γ1 Γ2 τ s bs Γ1 Γ1 τ s Γ1 Γ2 vals unflatten Γ1 τ s bs vals unflatten Γ2 τ s bs Proof induction 2 intros f equal auto by erewrite bit size of weaken val unflatten weaken by eauto Qed Lemma val unflatten typed Γ Δ τ bs Γ Γ τ Γ Δ bs length bs bit size of Γ τ Γ Δ val unflatten Γ τ bs τ Proof intros H Γ H τ revert τ H τ bs refine type env ind H Γ intros τ b H τ bs Hbs Hbs rewrite val unflatten base typed constructor auto using base val unflatten typed intros τ n H τ IH Hn bs rewrite val unflatten array bit size of array intros Hbs Hbs typed constructor eauto using array unflatten length revert bs Hbs Hbs clear Hn induction n simpl auto intros t τ s Ht H τ s IH bs erewrite val unflatten compound bit size of struct by eauto intros Hbs Hbs typed constructor eauto unfold struct unflatten revert bs Hbs Hbs clear Ht H τ s induction bit size of fields τ s H Γ intros decompose Forall hyps auto typed constructor eauto clear H τ s pose proof bit size of union H Γ Ht clear Ht induction IH decompose Forall hyps auto exists bs auto rewrite Hbs auto using bit size of union Qed Lemma vals unflatten typed Γ Δ τ s bs Γ Γ τ s Γ Δ bs Forall λ τ bit size of Γ τ length bs τ s Γ Δ vals unflatten Γ τ s bs τ s Proof induction 2 intros decompose Forall hyps auto using val unflatten typed Qed Lemma vals representable typed Γ Δ vs τ s Γ Γ τ s vals representable Γ Δ vs τ s Γ Δ vs τ s Proof intros bs auto using vals unflatten typed Qed Lemma val unflatten type of Γ τ bs Γ Γ τ type of val unflatten Γ τ bs τ Proof intros H Γ H τ revert τ H τ bs refine type env ind H Γ intros τ b bs rewrite val unflatten base simpl by rewrite base val unflatten type of intros τ n IH bs done rewrite val unflatten array simpl by rewrite array unflatten length intros t τ s bs by erewrite val unflatten compound by eauto Qed Lemma vals unflatten type of Γ τ s bs Γ Γ τ s type of vals unflatten Γ τ s bs τ s Proof induction 2 f equal auto using val unflatten type of Qed Lemma vals unflatten representable Γ Δ bs τ s Γ Δ bs Forall λ τ bit size of Γ τ length bs τ s vals representable Γ Δ vals unflatten Γ τ s bs τ s Proof by exists bs Qed Lemma val unflatten frozen Γ Δ τ bs Γ Γ τ Γ Δ bs freeze true val unflatten Γ τ bs val unflatten Γ τ bs Proof intros H Γ H τ revert τ H τ bs refine type env ind H Γ intros rewrite val unflatten base simpl by rewrite base val unflatten frozen by eauto intros τ n IH bs Hbs rewrite val unflatten array f equal revert bs Hbs induction n intros f equal auto intros t τ s Ht IH bs Hbs erewrite val unflatten compound by eauto f equal clear Ht unfold struct unflatten revert bs Hbs induction bit size of fields τ s H Γ intros decompose Forall hyps f equal auto revert bs Hbs induction IH intros f equal eauto Qed Lemma vals unflatten frozen Γ Δ τ s bs Γ Γ τ s Γ Δ bs freeze true vals unflatten Γ τ s bs vals unflatten Γ τ s bs Proof induction 2 intros f equal eauto using val unflatten frozen Qed Lemma val unflatten union free Γ τ bs Γ Γ τ val union free val unflatten Γ τ bs Proof intros H Γ H τ revert τ H τ bs refine type env ind H Γ intros rewrite val unflatten base by constructor intros τ n IH bs rewrite val unflatten array constructor revert bs induction n simpl auto intros t τ s Ht IH bs erewrite val unflatten compound by eauto constructor unfold struct unflatten revert bs clear Ht induction bit size of fields τ s H Γ intros decompose Forall hyps auto constructor elim IH csimpl auto Qed Lemma vals representable union free Γ Δ vs τ s Γ Γ τ s vals representable Γ Δ vs τ s Forall val union free vs Proof intros H τ s bs induction H τ s constructor auto using val unflatten union free Qed Lemma val unflatten between Γ τ bs1 bs2 bs3 Γ Γ τ bs1 bs2 bs2 bs3 length bs1 bit size of Γ τ val unflatten Γ τ bs1 val unflatten Γ τ bs3 val unflatten Γ τ bs2 val unflatten Γ τ bs3 Proof intros H Γ H τ revert τ H τ bs1 bs2 bs3 refine type env ind H Γ intros τ b bs1 bs2 bs3 rewrite val unflatten base injective iff VBase by apply base val unflatten between intros τ n IH bs1 bs2 bs3 Hbs1 Hbs2 rewrite val unflatten array bit size of array injective iff VArray revert bs1 bs2 bs3 Hbs1 Hbs2 induction n intros simplify equality f equal eauto intros t τ s Ht H τ s IH bs1 bs2 bs3 Hbs1 Hbs2 erewrite val unflatten compound bit size of struct by eauto rewrite injective iff VStruct t clear Ht H τ s revert bs1 bs2 bs3 Hbs1 Hbs2 unfold struct unflatten induction bit size of fields τ s H Γ intros simpl rewrite take take intros decompose Forall hyps f equal eauto pose proof bit size of union H Γ Ht clear Ht H τ s rewrite injective iff VUnionAll t revert bs1 bs2 bs3 Hbs1 Hbs2 induction IH intros decompose Forall hyps f equal eauto Qed Lemma vals unflatten between Γ τ s bs1 bs2 bs3 Γ Γ τ s bs1 bs2 bs2 bs3 Forall λ τ bit size of Γ τ length bs1 τ s vals unflatten Γ τ s bs1 vals unflatten Γ τ s bs3 vals unflatten Γ τ s bs2 vals unflatten Γ τ s bs3 Proof induction 2 intros decompose Forall hyps f equal eauto using val unflatten between Qed Global Opaque val unflatten General properties of the typing judgment Lemma val typed int frozen Γ Δ v τ i Γ Δ v intT τ i frozen v Proof inversion clear 1 unfold frozen simpl by erewrite base typed int frozen by eauto Qed Lemma val union free base Γ Δ v τ b Γ Δ v baseT τ b val union free v Proof inversion 1 constructor Qed Lemma val typed type valid Γ Δ v τ Γ Γ Δ v τ Γ τ Proof induction 2 using val typed ind econstructor decompose Forall hyps try match goal with H length vs 0 H2 Forall vs destruct H2 done end eauto eapply base val typed type valid eauto Qed Lemma val typed types valid Γ Δ vs τ s Γ Γ Δ vs τ s Γ τ s Proof induction 2 constructor eauto using val typed type valid Qed Global Instance TypeOfSpec env K memenv K type K val K Proof intros Γ Δ induction 1 using val typed ind decompose Forall hyps f equal eauto eapply type of correct eauto Qed Lemma vals representable weaken Γ1 Γ2 Δ1 Δ2 vs τ s Γ1 Γ1 τ s vals representable Γ1 Δ1 vs τ s Γ1 Γ2 Δ1 ₘ Δ2 vals representable Γ2 Δ2 vs τ s Proof intros H τ s bs Hlen Hvs exists bs eauto using Forall impl bit valid weaken clear Hvs induction H τ s decompose Forall hyps constructor auto 2 by erewrite bit size of weaken by eauto by erewrite vals unflatten weaken by eauto Qed Lemma val typed weaken Γ1 Γ2 Δ1 Δ2 v τ Γ1 Γ1 Δ1 v τ Γ1 Γ2 Δ1 ₘ Δ2 Γ2 Δ2 v τ Proof intros Hv τ induction Hv τ using val typed ind econstructor erewrite 1 vals unflatten weaken erewrite 1 bit size of weaken by eauto using TCompound valid eauto using base val typed weaken lookup compound weaken Forall impl vals representable weaken bit valid weaken val typed types valid Qed Lemma VArray frozen τ vs frozen VArray τ vs Forall frozen vs Proof unfold frozen split intros Hvs f equal induction Hvs f equal auto intros simplify equality induction vs simplify equality auto Qed Lemma val freeze freeze β1 β2 v freeze β1 freeze β2 v freeze β1 v Proof assert vs Forall λ v freeze β1 freeze β2 v freeze β1 v vs freeze β1 freeze β2 vs freeze β1 vs induction 1 f equal auto induction v using val ind alt f equal auto using base val freeze freeze Qed Lemma vals freeze freeze β1 β2 vs freeze β1 freeze β2 vs freeze β1 vs Proof induction vs f equal auto using val freeze freeze Qed Lemma vals representable freeze Γ m vs τ s Γ Γ τ s vals representable Γ m vs τ s vals representable Γ m freeze true vs τ s Proof intros bs exists bs eauto using vals unflatten frozen Qed Lemma val typed freeze Γ Δ v τ Γ Γ Δ v τ Γ Δ freeze true v τ Proof induction 2 using val typed ind simplify equality typed constructor by apply base typed freeze typed constructor auto using fmap length by apply Forall fmap typed constructor eauto by apply Forall2 fmap l typed constructor eauto typed constructor eauto using vals representable freeze by apply Forall2 fmap l Qed Lemma val union free freeze β v val union free freeze β v val union free v Proof split assert vs Forall λ v val union free freeze β v val union free v vs Forall val union free freeze β vs Forall val union free vs induction 1 csimpl intros decompose Forall eauto induction v using val ind alt inversion clear 1 econstructor eauto induction 1 using val union free ind alt simpl econstructor eauto by apply Forall fmap Qed Interaction between val flatten and val unflatten Lemma val union to bits valid Γ Δ sz vs τ s bs Γ bits list join sz val flatten Γ vs Some bs Γ Δ vs τ s Γ Δ bs Proof intros Hbs Hvs eapply bits list join valid eauto elim Hvs intros constructor eauto using val flatten valid Qed Lemma val flatten unflatten Γ Δ τ bs Γ Γ τ Γ Δ bs length bs bit size of Γ τ val flatten Γ val unflatten Γ τ bs bs Proof intros H Γ H τ revert τ H τ bs refine type env ind H Γ intros τ b bs rewrite val unflatten base simpl eauto using base val flatten unflatten intros τ n H τ IH bs rewrite val unflatten array simpl rewrite bit size of array revert bs induction n as n IHn simpl intros bs by erewrite nil length inv by eauto apply Forall2 app l erewrite val flatten length by eauto using val unflatten typed auto intros t τ s Ht H τ s IH bs erewrite val unflatten compound bit size of struct by eauto simpl intros Hbs Hbs rewrite Ht simpl clear Ht H τ s revert bs Hbs Hbs unfold struct unflatten induction bit size of fields τ s H Γ as τ sz τ s szs intros bs decompose Forall hyps by erewrite nil length inv by eauto apply Forall2 app l rewrite resize length resize le BIndet resize resize by done eauto using Forall2 resize r Forall true destruct bits list join as bs eqn Hbs simpl apply bit size of union in Ht auto revert bs Hbs induction IH as τ τ s intros bs Hbs decompose Forall hyps simplify option equality eauto using Forall2 replicate l resize length Forall true eapply bits join min eauto rewrite resize le BIndet by done eauto using Forall2 resize r flip Forall true auto using Forall2 replicate l Forall true resize length Qed Lemma vals representable as bits aux Γ Δ sz vs τ s Γ Γ τ s Forall λ τ bit size of Γ τ sz τ s Forall2 λ v τ val union free v val unflatten Γ τ val flatten Γ v freeze true v vs τ s vals representable Γ Δ vs τ s bs bits list join sz val flatten Γ vs Some bs Γ Δ bs vs vals unflatten Γ τ s bs Proof intros H Γ H τ s Ht IH bs Hlen destruct bits list join exists sz val flatten Γ vals unflatten Γ τ s bs resize sz BIndet bs as bs Hbs Hbsbs by rewrite resize length clear IH induction H τ s decompose Forall hyps constructor auto rewrite resize le BIndet by done eauto using Forall2 resize r Forall true val flatten unflatten exists bs split ands done assert Γ Δ vals unflatten Γ τ s bs τ s as H τ s by auto using vals unflatten typed eapply bits list join valid eauto clear Ht IH Hbs Hbsbs induction H τ s decompose Forall hyps eauto using val flatten valid apply bits list join Some alt in Hbs induction H τ s as τ τ s IH τ s simplify equality auto apply Forall2 cons inv in IH destruct IH as IH IH apply Forall cons in Hbs destruct Hbs as Hbs Hbs decompose Forall hyps f equal auto clear IH Hbs IH τ s symmetry apply val unflatten between val flatten Γ val unflatten Γ τ take bit size of Γ τ bs take bit size of Γ τ bs take bit size of Γ τ bs auto 1 apply Forall2 take bit size of Γ τ in Hbs rewrite take resize le resize all alt in Hbs auto 1 by erewrite val flatten length by eauto using val unflatten typed apply Forall2 take bit size of Γ τ in Hbsbs rewrite take resize le resize le in Hbsbs eauto by erewrite val flatten length by eauto using val unflatten typed by erewrite IH val unflatten frozen by eauto using val unflatten union free Qed Lemma val unflatten flatten Γ Δ τ v Γ Γ Δ v τ val union free v val unflatten Γ τ val flatten Γ v freeze true v Proof intros H Γ revert v τ refine val typed ind intros vb τ b rewrite val unflatten base f equal eauto using base val unflatten flatten intros vs τ IH inversion clear 1 rewrite val unflatten array f equal induction IH decompose Forall hyps rewrite take app alt drop app alt by auto f equal auto intros t vs τ s Ht Hvs IH inversion clear 1 erewrite val unflatten compound by eauto simpl rewrite Ht f equal unfold struct unflatten clear Ht revert dependent vs induction bit size of fields τ s H Γ intros decompose Forall hyps rewrite take app alt drop app alt f equal auto rewrite take resize le resize all alt by auto auto intros t i τ s v τ Ht H τ s Hv IH inversion clear 1 intros t vs τ s Ht Hvs IH Hrepr erewrite val unflatten compound by eauto simpl destruct vals representable as bits aux Γ Δ bit size of Γ unionT t vs τ s as bs eauto using bit size of union simpl by erewrite vals unflatten frozen by eauto Qed Lemma vals representable as bits Γ Δ sz vs τ s Γ Γ τ s Forall λ τ bit size of Γ τ sz τ s vals representable Γ Δ vs τ s bs bits list join sz val flatten Γ vs Some bs length bs sz Γ Δ bs vs vals unflatten Γ τ s bs Proof intros Hvs destruct vals representable as bits aux Γ Δ sz vs τ s as eauto 6 using bits list join length apply vals representable typed in Hvs auto elim Hvs constructor eauto using val unflatten flatten Qed Properties of the val new function Lemma val new base Γ τ b val new Γ τ b VBase if decide τ b voidT BT then VVoid else VIndet τ b Proof unfold val new rewrite val unflatten base case decide subst done by rewrite base val unflatten indet by auto Qed Lemma val new array Γ τ n val new Γ τ n VArray τ replicate n val new Γ τ Proof unfold val new rewrite val unflatten array bit size of array f equal by induction n f equal rewrite take replicate plus drop replicate plus Qed Lemma val new compound Γ c t τ s Γ Γ t Some τ s val new Γ compoundT c t match c with Struct kind VStruct t val new Γ τ s Union kind VUnionAll t val new Γ τ s end Proof intros H Γ Ht unfold val new erewrite val 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 eapply Forall fmap ext Forall impl eapply bit size of union eauto intros by rewrite take replicate Min min l by done Qed Lemma val new weaken Γ1 Γ2 τ Γ1 Γ1 τ Γ1 Γ2 val new Γ1 τ val new Γ2 τ Proof intros unfold val new by erewrite val unflatten weaken bit size of weaken by eauto Qed Lemma val new typed Γ Δ τ Γ Γ τ Γ Δ val new Γ τ τ Proof intros apply val unflatten typed auto using replicate length Qed Lemma vals new typed Γ Δ τ s Γ Γ τ s Γ Δ val new Γ τ s τ s Proof induction 2 simpl eauto using val new typed Qed Lemma val new type of Γ τ Γ Γ τ type of val new Γ τ τ Proof by apply val unflatten type of Qed Lemma val new frozen Γ τ Γ Γ τ frozen val new Γ τ Proof intros apply val unflatten frozen Γ auto Qed Properties of the to val function Lemma to val typed Γ Δ w τ Γ Γ Δ w τ Γ Δ to val Γ w τ Proof intros H Γ induction 1 using ctree typed ind simpl typed constructor eauto using base val unflatten typed pbits tag valid typed constructor auto using fmap length by apply Forall fmap typed constructor eauto by apply Forall2 fmap l typed constructor eauto eauto using val unflatten typed TCompound valid pbits tag valid Qed Lemma to vals typed Γ Δ ws τ s Γ Γ Δ ws τ s Γ Δ to val Γ ws τ s Proof induction 2 csimpl auto using to val typed Qed Lemma to val type of Γ w Γ Γ type of w type of to val Γ w type of w Proof intros H Γ induction w as τ ws IH using ctree ind alt simpl auto by rewrite base val unflatten type of intros by rewrite val unflatten type of Qed Lemma to val weaken Γ1 Γ2 Δ w τ Γ1 Γ1 Δ w τ Γ1 Γ2 to val Γ1 w to val Γ2 w Proof intros Hw revert w τ Hw refine ctree typed ind intros f equal auto using base val unflatten weaken intros f equal auto using Forall fmap ext 1 intros t w γ bss τ s IH f equal induction IH f equal auto by intros f equal eauto using val unflatten weaken TCompound valid Qed Lemma to val frozen Γ Δ w τ Γ Γ Δ w τ frozen to val Γ w Proof unfold frozen induction 2 using ctree typed ind simpl by erewrite base val unflatten frozen by eauto using pbits tag valid f equal rewrite list fmap compose by apply Forall fmap ext f equal rewrite list fmap compose eapply Forall fmap ext Forall2 Forall l eauto eapply Forall true eauto by f equal eauto using val unflatten frozen TCompound valid pbits tag valid Qed Lemma to val union free inv Γ w val union free to val Γ w union free w Proof induction w as ws IH s w γ bss IH using ctree ind alt simpl inversion clear 1 econstructor eauto induction IH decompose Forall hyps auto induction IH decompose Forall hyps auto Qed Lemma to val unflatten Γ τ γ bs Γ Γ τ to val Γ ctree unflatten Γ τ γ bs val unflatten Γ τ tagged tag γ bs Proof intros H Γ H τ revert τ H τ γ bs refine type env ind H Γ intros τ b γ bs by rewrite ctree unflatten base val unflatten base intros τ n IH γ bs rewrite ctree unflatten array val unflatten array f equal revert γ bs induction n intros f equal rewrite fmap drop fmap take auto intros t τ s Ht IH γ bs erewrite ctree unflatten compound val unflatten compound by eauto f equal unfold struct unflatten clear Ht revert γ bs induction bit size of fields τ s H Γ intros decompose Forall hyps rewrite fmap drop fmap take f equal auto by erewrite val unflatten compound by eauto Qed Lemma to val ctree map Γ f w γ b tagged tag f γ b tagged tag γ b to val Γ ctree map f w to val Γ w Proof intros induction w using ctree ind alt f equal auto f equal rewrite list fmap compose by apply list fmap ext rewrite list fmap compose by apply Forall fmap ext rewrite list fmap compose by apply Forall fmap ext rewrite list fmap compose by apply list fmap ext Qed Lemma to val unmapped Γ Δ w τ Γ Γ Δ w τ ctree unmapped w to val Γ w val new Γ τ Proof intros H Γ revert w τ refine ctree typed ind simpl intros τ b γ bs rewrite val new base pbits unmapped tag by done by case decide subst rewrite base val unflatten indet by auto intros ws τ IH rewrite val new array f equal induction IH decompose Forall hyps f equal auto intros t w γ bss τ s Hs IH erewrite val new compound by eauto f equal clear Hs induction IH decompose Forall hyps f equal auto intros t i τ s w γ bs τ decompose Forall hyps tauto intros t τ s γ bs unfold val new rewrite pbits unmapped tag by done congruence Qed Properties of the of val function Lemma ctree flatten of val Γ Δ γ s v τ Γ Γ Δ v τ length γ s bit size of Γ τ ctree flatten of val Γ γ s v zip with PBit γ s val flatten Γ v Proof intros H Γ Hv revert v τ Hv γ s refine val typed ind simpl done intros vs τ Hvs IH γ s rewrite bit size of array revert γ s induction IH intros γ s H γ s decompose Forall hyps erewrite zip with nil r type of correct zip with app r val flatten length by eauto f equal auto intros t vs τ s Ht Hvs IH γ s erewrite Ht bit size of struct fmap type of by eauto simpl unfold field bit padding clear Ht revert vs Hvs IH γ s induction bit size of fields τ s H Γ intros decompose Forall hyps erewrite zip with nil r type of correct resize ge associative L zip with app r val flatten length replicate length zip with replicate r by eauto repeat f equal auto intros t i τ s v τ IH γ s erewrite type of correct resize ge zip with app r val flatten length zip with replicate r by eauto f equal auto done Qed Lemma ctree flatten of val Γ Δ γ s v τ Γ Γ Δ v τ length γ s bit size of Γ τ tagged tag ctree flatten of val Γ γ s v val flatten Γ v Proof intros by erewrite ctree flatten of val fmap zip with r by eauto Qed Lemma of val unshared Γ Δ γ s v τ Γ Γ Δ v τ length γ s bit size of Γ τ Forall sep unshared γ s Forall not sep unmapped γ s ctree unshared of val Γ γ s v Proof intros erewrite ctree flatten of val by eauto eauto using PBits unshared Qed Lemma of val mapped Γ Δ γ s v τ Γ Γ Δ v τ length γ s bit size of Γ τ Forall not sep unmapped γ s ctree Forall not sep unmapped of val Γ γ s v Proof intros erewrite ctree flatten of val by eauto eauto using PBits mapped Qed Lemma of val typed Γ Δ γ s v τ Γ Γ Δ v τ length γ s bit size of Γ τ Forall sep valid γ s Forall not sep unmapped γ s Γ Δ of val Γ γ s v τ Proof intros H Γ Hv revert v τ Hv γ s refine val typed ind simpl intros vb τ b γ s erewrite type of correct by eauto typed constructor eauto using base val typed type valid eauto using PBits valid base val flatten valid erewrite zip with length base val flatten length by eauto lia intros vs τ Hvs IH Hvs γ s rewrite bit size of array intros Hlen H γ s H γ s typed constructor trivial clear Hvs Hvs H γ s H γ s Hlen IH revert γ s induction vs intros f equal auto revert γ s H γ s H γ s Hlen clear Hvs induction IH intros decompose Forall hyps erewrite type of correct by eauto constructor auto intros t vs τ s Ht Hvs IH γ s erewrite bit size of struct fmap type of by eauto intros Hlen H γ s H γ s typed constructor eauto clear Ht unfold field bit padding revert vs γ s Hvs IH H γ s H γ s Hlen induction bit size of fields τ s H Γ intros decompose Forall hyps erewrite type of correct by eauto constructor simpl auto clear IH revert vs γ s Hvs H γ s H γ s Hlen induction bit size of fields τ s H Γ intros decompose Forall hyps erewrite type of correct by eauto constructor simpl auto erewrite zip with replicate r by eauto eauto 7 using PBits valid clear H γ s H γ s Hlen IH revert γ s vs Hvs induction bit size of fields τ s H Γ intros decompose Forall hyps constructor simpl eauto using PBits indetify clear H γ s H γ s IH revert vs γ s Hvs Hlen induction bit size of fields τ s H Γ intros decompose Forall hyps erewrite type of correct by eauto f equal auto intros erewrite type of correct by eauto typed constructor eauto erewrite zip with replicate l zip with flip by eauto auto using PBits valid auto using PBits indetify rewrite fmap length solve length intros Hc eapply ctree Forall not sep unmapped Γ Δ of val Γ take bit size of Γ τ γ s v eauto using of val mapped intros t vs τ s Ht Hvs IH Hrep γ s destruct bits list join as bs eqn Hbs simpl typed constructor eauto eauto using PBits valid val union to bits valid erewrite zip with length bits list join length by eauto auto lia typed constructor eauto using PBits valid Qed Lemma of val weaken Γ1 Γ2 Δ1 γ s v τ Γ1 Γ1 Γ2 Γ1 Δ1 v τ of val Γ1 γ s v of val Γ2 γ s v Proof intros H Γ Hv revert v τ Hv γ s refine val typed ind intros f equal eauto using base val flatten weaken with f equal intros vs τ IH γ s f equal revert γ s induction IH intros decompose Forall hyps simplify type equality erewrite bit size of weaken Γ1 Γ2 by eauto using val typed type valid auto with f equal intros t vs τ s Ht Hvs IH γ s f equal revert γ s erewrite fmap type of field bit padding weaken by eauto clear Ht generalize field bit padding Γ2 τ s induction IH intros decompose Forall hyps simplify type equality erewrite bit size of weaken by eauto using val typed type valid auto with f equal intros simplify type equality erewrite bit size of weaken by eauto using val typed type valid auto with f equal intros unfold of val do 2 f equal eapply val flatten weaken eauto econstructor eauto Qed Lemma of val type of Γ γ s v type of of val Γ γ s v type of v Proof destruct v as vs using val ind alt simplify equality rewrite fmap length f equal auto revert γ s induction vs intros f equal auto Qed Lemma to of val Γ Δ γ s v τ Γ Γ Δ v τ length γ s bit size of Γ τ to val Γ of val Γ γ s v freeze true v Proof intros H Γ Hv τ revert v τ Hv τ γ s refine val typed ind simpl intros by erewrite type of correct fmap zip with r base val unflatten flatten by eauto intros vs τ Hvs IH γ s rewrite bit size of array intros H γ s f equal revert γ s H γ s induction IH intros decompose Forall hyps erewrite type of correct by eauto f equal auto intros t vs τ s Ht Hvs IH γ s erewrite fmap type of bit size of struct by eauto intros H γ s f equal revert vs γ s Hvs IH H γ s unfold field bit padding clear Ht induction bit size of fields τ s H Γ intros decompose Forall hyps erewrite type of correct by eauto f equal eauto intros erewrite type of correct by eauto f equal auto intros t vs τ s Ht Hvs IH Hrepr γ s destruct vals representable as bits Γ Δ bit size of Γ unionT t vs τ s as bs Hbs simpl eauto using bit size of union by erewrite fmap zip with r val unflatten compound Hbs vals unflatten frozen by eauto Qed Lemma of val union free Γ γ s v val union free v union free of val

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