Replace the two-bank machine with a K-bank ring, prove its reproduction in Rocq, and revise the paper
a9ea017 Download rocq/Indep.v from phanerozoic/threshold-computers: direct link, hf CLI and curl.
- Browser
- Download file 9.29 kB
-
https://huggingface.co/phanerozoic/threshold-computers/resolve/main/rocq/Indep.v
- Command line
-
hf download hf://phanerozoic/threshold-computers/rocq/Indep.v
-
curl -L -o Indep.v https://huggingface.co/phanerozoic/threshold-computers/resolve/main/rocq/Indep.v
9.29 kB
| (* Cells a pass writes before it reads them carry nothing from one pass to the next. *) | |
| From Stdlib Require Import List Bool Arith ZArith Lia. | |
| Import ListNotations. | |
| From TH Require Import TwoHead Abstract. | |
| Definition ao_of (r : rec) : nat := match r with Rec _ _ _ _ _ ao => ao end. | |
| Definition reads_ok (istmp : nat -> bool) (written : list nat) (a : nat) (w : Z) : bool := | |
| Z.eqb w 0 || Nat.leb a CPY || negb (istmp a) || existsb (Nat.eqb a) written. | |
| Fixpoint wbr_from (rs : list rec) (istmp : nat -> bool) (written : list nat) : bool := | |
| match rs with | |
| | [] => true | |
| | Rec a0 w0 a1 w1 _ ao :: t => | |
| reads_ok istmp written a0 w0 && reads_ok istmp written a1 w1 | |
| && wbr_from t istmp (written ++ [ao]) | |
| end. | |
| (* two windows agree on the cells from 4 on that are not temporaries or that the pass has written *) | |
| Definition wagree (istmp : nat -> bool) (written : list nat) (w1 w2 : list bool) : Prop := | |
| forall x, 4 <= x -> (istmp x = false \/ In x written) -> wget w1 x = wget w2 x. | |
| Lemma acell_agree : forall istmp written t1 t2 a w, | |
| aR t1 = aR t2 -> aA t1 = aA t2 -> aK t1 = aK t2 -> | |
| wagree istmp written (aw t1) (aw t2) -> | |
| reads_ok istmp written a w = true -> | |
| (w * b2z (acell t1 a) = w * b2z (acell t2 a))%Z. | |
| Proof. | |
| intros istmp written t1 t2 a w HR HA HK Hw Hok. unfold reads_ok in Hok. unfold acell. | |
| rewrite HR, HA, HK. | |
| destruct (Z.eqb w 0) eqn:Ew; [apply Z.eqb_eq in Ew; rewrite Ew; reflexivity|]. | |
| destruct (Nat.eqb a SINK) eqn:E0; [reflexivity|]. | |
| destruct (Nat.eqb a RD) eqn:E1; [reflexivity|]. | |
| destruct (Nat.eqb a ARM) eqn:E2; [reflexivity|]. | |
| destruct (Nat.eqb a CPY) eqn:E3; [reflexivity|]. | |
| apply Nat.eqb_neq in E0, E1, E2, E3. | |
| cbn [orb] in Hok. destruct (Nat.leb_spec a CPY) as [Hc|Hc]; [unfold SINK, RD, ARM, CPY in *; lia|]. | |
| cbn [orb] in Hok. rewrite Hw; [reflexivity | unfold CPY in Hc; lia |]. | |
| destruct (istmp a) eqn:Et; [right | left; reflexivity]. | |
| cbn [negb orb] in Hok. apply existsb_exists in Hok as (y & Hy & Hey). | |
| apply Nat.eqb_eq in Hey. subst. exact Hy. | |
| Qed. | |
| Lemma opok_heads : forall t1 t2 a w, | |
| aR t1 = aR t2 -> aA t1 = aA t2 -> aK t1 = aK t2 -> opok t1 a w = opok t2 a w. | |
| Proof. intros t1 t2 a w HR HA HK. unfold opok. rewrite HR, HA, HK. reflexivity. Qed. | |
| Lemma wagree_step : forall istmp written w1 w2 ao v, | |
| wagree istmp written w1 w2 -> length w1 = length w2 -> | |
| (forall c, AR <= c <= HO -> istmp c = false) -> | |
| wagree istmp (written ++ [ao]) (clearq (wnext w1 ao v)) (clearq (wnext w2 ao v)). | |
| Proof. | |
| intros istmp written w1 w2 ao v H Hl Hreq x H4 Hx. | |
| assert (Hc : forall w, wget (clearq w) x = if (AR <=? x) && (x <=? HO) && (x <? length w) then false else wget w x). | |
| { intro w. unfold clearq. rewrite !wget_upd, !upd_length. | |
| unfold AR, AA, AC, RR, RA, RC, CB, CT, HO. | |
| destruct (Nat.eqb_spec x 12); [subst; destruct (12 <? length w); reflexivity|]. | |
| destruct (Nat.eqb_spec x 11); [subst; destruct (11 <? length w); reflexivity|]. | |
| destruct (Nat.eqb_spec x 10); [subst; destruct (10 <? length w); reflexivity|]. | |
| destruct (Nat.eqb_spec x 9); [subst; destruct (9 <? length w); reflexivity|]. | |
| destruct (Nat.eqb_spec x 8); [subst; destruct (8 <? length w); reflexivity|]. | |
| destruct (Nat.eqb_spec x 7); [subst; destruct (7 <? length w); reflexivity|]. | |
| destruct (Nat.eqb_spec x 6); [subst; destruct (6 <? length w); reflexivity|]. | |
| destruct (Nat.eqb_spec x 5); [subst; destruct (5 <? length w); reflexivity|]. | |
| destruct (Nat.eqb_spec x 4); [subst; destruct (4 <? length w); reflexivity|]. | |
| destruct (Nat.leb_spec 4 x), (Nat.leb_spec x 12); cbn [andb]; try reflexivity; lia. } | |
| rewrite !Hc, !length_wnext, Hl. | |
| destruct ((AR <=? x) && (x <=? HO) && (x <? length w2)); [reflexivity|]. | |
| unfold wnext. destruct (Nat.leb_spec ao CPY) as [E|E]. | |
| - apply H; [exact H4|]. destruct Hx as [Hx|Hx]; [left; exact Hx|]. | |
| apply in_app_or in Hx as [Hx|Hx]; [right; exact Hx|]. | |
| destruct Hx as [Hx|[]]. subst x. unfold CPY in E. lia. | |
| - rewrite !wget_upd, Hl. | |
| destruct (Nat.eqb x ao && Nat.ltb ao (length w2)) eqn:Ex; [reflexivity|]. | |
| destruct Hx as [Hx|Hx]; [apply H; auto|]. | |
| apply in_app_or in Hx as [Hx|Hx]; [apply H; auto|]. | |
| destruct Hx as [Hx|[]]. subst x. | |
| rewrite Nat.eqb_refl in Ex. cbn [andb] in Ex. apply Nat.ltb_ge in Ex. | |
| unfold wget. rewrite !nth_overflow by lia. reflexivity. | |
| Qed. | |
| Lemma firstn_S_nth : forall (rs : list rec) j r, nth_error rs j = Some r -> | |
| firstn (S j) rs = firstn j rs ++ [r]. | |
| Proof. | |
| induction rs as [|y rs IH]; intros [|j] r H; cbn in *; try discriminate. | |
| - injection H as ->. reflexivity. | |
| - rewrite (IH j r H). reflexivity. | |
| Qed. | |
| Lemma skipn_nth : forall (rs : list rec) j r, nth_error rs j = Some r -> | |
| skipn j rs = r :: skipn (S j) rs. | |
| Proof. | |
| induction rs as [|y rs IH]; intros [|j] r H; cbn in *; try discriminate. | |
| - injection H as ->. reflexivity. | |
| - apply IH. exact H. | |
| Qed. | |
| (* two abstract runs that start from states agreeing away from the temporaries agree there at the end *) | |
| Lemma aiter_indep : forall n rs istmp t1 t2, | |
| (forall c, AR <= c <= HO -> istmp c = false) -> | |
| wbr_from (skipn (ai t1) rs) istmp (map ao_of (firstn (ai t1) rs)) = true -> | |
| ai t1 = ai t2 -> aR t1 = aR t2 -> aA t1 = aA t2 -> aK t1 = aK t2 -> aho t1 = aho t2 -> bad t1 = bad t2 -> | |
| length (aw t1) = length (aw t2) -> | |
| wagree istmp (map ao_of (firstn (ai t1) rs)) (aw t1) (aw t2) -> | |
| ai (aiter n rs t1) = ai (aiter n rs t2) | |
| /\ aR (aiter n rs t1) = aR (aiter n rs t2) | |
| /\ aA (aiter n rs t1) = aA (aiter n rs t2) | |
| /\ aK (aiter n rs t1) = aK (aiter n rs t2) | |
| /\ aho (aiter n rs t1) = aho (aiter n rs t2) | |
| /\ bad (aiter n rs t1) = bad (aiter n rs t2) | |
| /\ (forall x, 4 <= x -> istmp x = false -> wget (aw (aiter n rs t1)) x = wget (aw (aiter n rs t2)) x) | |
| /\ wagree istmp (map ao_of (firstn (ai (aiter n rs t1)) rs)) (aw (aiter n rs t1)) (aw (aiter n rs t2)). | |
| Proof. | |
| induction n as [|n IH]; intros rs istmp t1 t2 Hreq Hwbr Hi HR HA HK Hho Hb Hl Hw. | |
| - cbn [aiter]. refine (conj Hi (conj HR (conj HA (conj HK (conj Hho (conj Hb (conj _ Hw))))))). | |
| intros x H4 Hx. apply Hw; auto. | |
| - cbn [aiter]. | |
| destruct (nth_error rs (ai t1)) as [r|] eqn:Er. | |
| + assert (Er2 : nth_error rs (ai t2) = Some r) by (rewrite <- Hi; exact Er). | |
| rewrite (skipn_nth rs _ r Er) in Hwbr. | |
| destruct r as [a0 w0 a1 w1 beta ao]. cbn [wbr_from] in Hwbr. | |
| apply andb_prop in Hwbr as [Hrd Hwbr]. apply andb_prop in Hrd as [Hr0 Hr1]. | |
| unfold astep. rewrite Er, Er2. | |
| rewrite (acell_agree istmp _ t1 t2 a0 w0 HR HA HK Hw Hr0), (acell_agree istmp _ t1 t2 a1 w1 HR HA HK Hw Hr1). | |
| set (v := Z.leb 0 (w0 * b2z (acell t2 a0) + w1 * b2z (acell t2 a1) + beta)%Z). | |
| assert (Hq : forall c, AR <= c <= HO -> wget (wnext (aw t1) ao v) c = wget (wnext (aw t2) ao v) c). | |
| { intros c Hc. unfold wnext. destruct (Nat.leb ao CPY). | |
| - apply Hw; [unfold AR in Hc; lia | left; apply Hreq; exact Hc]. | |
| - rewrite !wget_upd, Hl. destruct (_ && _); [reflexivity|]. | |
| apply Hw; [unfold AR in Hc; lia | left; apply Hreq; exact Hc]. } | |
| apply IH; auto; unfold astepres; cbv zeta; cbn [ai aR aA aK aho bad aw]. | |
| * rewrite (firstn_S_nth rs _ _ Er), map_app. exact Hwbr. | |
| * rewrite Hi; reflexivity. | |
| * rewrite !Hq by (unfold AR, RR, HO; lia). rewrite HR. reflexivity. | |
| * rewrite !Hq by (unfold AR, RA, AA, CB, HO; lia). rewrite HA. reflexivity. | |
| * rewrite !Hq by (unfold AR, RC, AC, CT, HO; lia). rewrite HK. reflexivity. | |
| * rewrite !Hq by (unfold AR, HO; lia). rewrite Hho. reflexivity. | |
| * rewrite Hb, Hho, (opok_heads t1 t2 a0 w0 HR HA HK), (opok_heads t1 t2 a1 w1 HR HA HK), HA, HK, Hi, | |
| !Hq by (unfold AR, HO; lia). reflexivity. | |
| * rewrite !length_clearq, !length_wnext. exact Hl. | |
| * rewrite (firstn_S_nth rs _ _ Er), map_app. apply wagree_step; auto. | |
| + assert (Er2 : nth_error rs (ai t2) = None) by (rewrite <- Hi; exact Er). | |
| unfold astep. rewrite Er, Er2. | |
| apply IH; cbn [ai aR aA aK aho bad aw]; auto. | |
| Qed. | |
| (* the cells outside the requests that no record writes keep their values *) | |
| Lemma wget_clearq_out : forall w x, x < AR \/ HO < x -> wget (clearq w) x = wget w x. | |
| Proof. | |
| intros w x Hx. unfold clearq. rewrite !wget_upd. | |
| unfold AR, AA, AC, RR, RA, RC, CB, CT, HO in *. | |
| repeat match goal with |- context [Nat.eqb x ?c] => | |
| replace (Nat.eqb x c) with false by (symmetry; apply Nat.eqb_neq; lia) end. | |
| reflexivity. | |
| Qed. | |
| Lemma wget_wnext_other : forall w ao v x, ao <> x -> wget (wnext w ao v) x = wget w x. | |
| Proof. | |
| intros w ao v x H. unfold wnext. destruct (Nat.leb ao CPY); [reflexivity|]. | |
| rewrite wget_upd. replace (Nat.eqb x ao) with false by (symmetry; apply Nat.eqb_neq; lia). reflexivity. | |
| Qed. | |
| Lemma aiter_unwritten : forall n rs t x, HO < x -> ~ In x (map ao_of rs) -> | |
| wget (aw (aiter n rs t)) x = wget (aw t) x. | |
| Proof. | |
| induction n as [|n IH]; intros rs t x Hx Hn; [reflexivity|]. | |
| cbn [aiter]. rewrite IH by assumption. unfold astep. | |
| destruct (nth_error rs (ai t)) as [r|] eqn:Er; [|reflexivity]. | |
| destruct r as [a0 w0 a1 w1 beta ao]. unfold astepres. cbv zeta. cbn [aw]. | |
| rewrite wget_clearq_out by (right; exact Hx). | |
| apply wget_wnext_other. intro E. subst ao. apply Hn. apply in_map_iff. | |
| exists (Rec a0 w0 a1 w1 beta x). split; [reflexivity|]. eapply nth_error_In. exact Er. | |
| Qed. | |