Download rocq/Schedule.v from phanerozoic/threshold-computers: direct link, hf CLI and curl.
- Browser
- Download file 13.4 kB
-
https://huggingface.co/phanerozoic/threshold-computers/resolve/main/rocq/Schedule.v
- Command line
-
hf download hf://phanerozoic/threshold-computers/rocq/Schedule.v
-
curl -L -o Schedule.v https://huggingface.co/phanerozoic/threshold-computers/resolve/main/rocq/Schedule.v
13.4 kB
| (* Lemma 3.3. A pass of records that read and write the window alone, held in the active bank and followed by empty | |
| slots, runs them in order on the window. The records of a clocked netlist of units of at most two inputs, one for | |
| each unit in the order of the netlist, each writing a cell that holds the unit's value until the last record that | |
| reads it, and the record of each next value writing its state bit after every record that reads the bit, leave the | |
| next state in the cells of the state bits after one pass. *) | |
| From Stdlib Require Import List Bool Arith ZArith Lia. | |
| Import ListNotations. | |
| From TH Require Import TwoHead Net Abstract Indep Run View Stored WinRun StoredBoot. | |
| (* ---- a pass of window records ------------------------------------------------------------------------------------ *) | |
| Lemma wrec_empty : wrec EMPTY. | |
| Proof. unfold wrec, EMPTY. auto. Qed. | |
| Lemma rec_ok_empty : forall al, rec_ok al EMPTY. | |
| Proof. intro al. pose proof (Nat.pow_nonzero 2 al ltac:(lia)). unfold rec_ok, EMPTY. lia. Qed. | |
| Lemma wrun_empty : forall p w, wrun (repeat EMPTY p) w = w. | |
| Proof. induction p as [|p IH]; intro w; [reflexivity|]. cbn [repeat wrun]. unfold wexec. cbn [ao_of EMPTY]. apply IH. Qed. | |
| Lemma Forall_prefix : forall (T : Type) (P : T -> Prop) l j, Forall P l -> Forall P (firstn j l). | |
| Proof. intros T P l j H. rewrite <- (firstn_skipn j l) in H. apply Forall_app in H. exact (proj1 H). Qed. | |
| Section Pass. | |
| Variables (al K S0 L : nat) (s0 : st) (rs : list rec). | |
| Hypotheses (Hal : 4 <= al) (HK : 2 <= K) (HS : 1 <= S0) (HL : 1 <= L) (Hfit : fits al K S0 L s0) | |
| (Hbank : bq (nth (kap s0) (banks s0) bank0) = encA al (rs ++ repeat EMPTY (S0 - length rs))) | |
| (Hslot : bs (nth (kap s0) (banks s0) bank0) = 0) (Hlen : length rs <= S0) | |
| (Hok : Forall (rec_ok al) rs) (Hw : Forall wrec rs) (Hq : reqclear (win s0)). | |
| Let pad : list rec := rs ++ repeat EMPTY (S0 - length rs). | |
| Lemma pad_len : length pad = S0. | |
| Proof. unfold pad. rewrite length_app, repeat_length. lia. Qed. | |
| Lemma pad_wrec : Forall wrec pad. | |
| Proof. | |
| unfold pad. apply Forall_app. split; [exact Hw|]. apply Forall_forall. intros r Hr. apply repeat_spec in Hr. subst r. | |
| exact wrec_empty. | |
| Qed. | |
| (* the S0 steps of a pass are the records of the bank run in order on the window; the heads and the bank index stay *) | |
| Theorem pass_run : | |
| View.mv al K S0 L s0 S0 (itern al K S0 L S0 s0) | |
| (mkV (wrun rs (win s0)) (vr (view0 al K s0)) (va (view0 al K s0)) (vc (view0 al K s0)) false). | |
| Proof. | |
| assert (Hq0 : reqclear (vw (view0 al K s0))) by exact Hq. | |
| assert (Hok' : Forall (rec_ok al) pad). | |
| { unfold pad. apply Forall_app. split; [exact Hok|]. apply Forall_forall. intros r Hr. apply repeat_spec in Hr. | |
| subst r. apply rec_ok_empty. } | |
| assert (Hho : forall j, 1 <= j < length pad -> vho (vrun (S0 * recw al) L (firstn j pad) (view0 al K s0)) = false). | |
| { intros j _. rewrite (vrun_wrun _ _ _ _ (Forall_prefix _ _ _ j pad_wrec) Hq0). reflexivity. } | |
| pose proof (seg_run al K S0 L s0 Hal HK HS HL Hfit pad [] ltac:(rewrite app_nil_r; exact Hbank) Hslot | |
| ltac:(rewrite pad_len; lia) Hok' Hho S0 ltac:(rewrite pad_len; lia)) as M. | |
| rewrite firstn_all2 in M by (rewrite pad_len; lia). | |
| rewrite (vrun_wrun _ _ _ _ pad_wrec Hq0) in M. unfold pad in M. rewrite wrun_app, wrun_empty in M. exact M. | |
| Qed. | |
| End Pass. | |
| (* ---- the records of a netlist ----------------------------------------------------------------------------------- *) | |
| Section Sched. | |
| (* the n state bits in the cells sc i, unit k writing cell oc k *) | |
| Variables (n : nat) (us : list tu) (sc oc : nat -> nat). | |
| (* the cell of a signal: a state bit has its own, a unit's value is in the cell its record writes *) | |
| Definition scell (p : nat) : nat := if p <? n then sc p else oc (p - n). | |
| (* the record of unit k: its inputs by their cells, the empty places reading the sink with weight 0 *) | |
| Definition rec_of (k : nat) (u : tu) : rec := | |
| match tin u with | |
| | [] => Rec SINK 0 SINK 0 (Net.tb u) (oc k) | |
| | [(p, z)] => Rec (scell p) z SINK 0 (Net.tb u) (oc k) | |
| | (p0, z0) :: (p1, z1) :: _ => Rec (scell p0) z0 (scell p1) z1 (Net.tb u) (oc k) | |
| end. | |
| Definition net_recs : list rec := map (fun k => rec_of k (nth k us tu0)) (seq 0 (length us)). | |
| (* the last of the first m records that writes cell c *) | |
| Fixpoint lastw (m c : nat) : option nat := | |
| match m with O => None | S m' => if Nat.eqb (oc m') c then Some m' else lastw m' c end. | |
| Variable w0 : list bool. | |
| Hypotheses | |
| (Hrb : forall k, k < length us -> reads_below (nth k us tu0) (n + k)) | |
| (Hsc : forall i, i < n -> HO < sc i < length w0) | |
| (Hoc : forall k, k < length us -> HO < oc k < length w0). | |
| (* the state the window holds, and the values of the netlist on it *) | |
| Definition x0 : list bool := map (fun i => wget w0 (sc i)) (seq 0 n). | |
| Definition E0 : nat -> bool := run us n (fun i => nth i x0 false). | |
| (* the records read and write the window alone *) | |
| Theorem net_recs_wrec : Forall wrec net_recs. | |
| Proof. | |
| apply Forall_forall. intros r Hr. unfold net_recs in Hr. apply in_map_iff in Hr as (k & <- & Hk). apply in_seq in Hk. | |
| assert (Hc : forall p, p < n + k -> CPY < scell p). | |
| { intros p Hp. unfold scell. destruct (Nat.ltb_spec p n); [pose proof (Hsc p ltac:(lia)) | pose proof (Hoc (p - n) ltac:(lia))]; | |
| unfold CPY, HO in *; lia. } | |
| pose proof (Hoc k ltac:(lia)) as Ho. pose proof (Hrb k ltac:(lia)) as Hb. | |
| unfold rec_of. destruct (tin (nth k us tu0)) as [|[p0 z0] [|[p1 z1] t]] eqn:Et; unfold wrec. | |
| - split; [auto|]. split; [auto | right; lia]. | |
| - split; [right; right; apply Hc; apply (Hb p0 z0); rewrite Et; left; reflexivity|]. split; [auto | right; lia]. | |
| - split; [right; right; apply Hc; apply (Hb p0 z0); rewrite Et; left; reflexivity|]. | |
| split; [right; right; apply Hc; apply (Hb p1 z1); rewrite Et; right; left; reflexivity | right; lia]. | |
| Qed. | |
| (* they fit the code of the records when the weights are 1 and -1, the biases lie in [-8, 7] and the cells in 2^al *) | |
| Theorem net_recs_ok : forall al, length w0 = 2 ^ al -> | |
| (forall k p z, k < length us -> In (p, z) (tin (nth k us tu0)) -> z = 1%Z \/ z = (-1)%Z) -> | |
| (forall k, k < length us -> (-8 <= Net.tb (nth k us tu0) <= 7)%Z) -> Forall (rec_ok al) net_recs. | |
| Proof. | |
| intros al HW Hz Hbias. apply Forall_forall. intros r Hr. unfold net_recs in Hr. | |
| apply in_map_iff in Hr as (k & <- & Hk). apply in_seq in Hk. | |
| assert (Hc : forall p, p < n + k -> scell p < 2 ^ al). | |
| { intros p Hp. unfold scell. destruct (Nat.ltb_spec p n); [pose proof (Hsc p ltac:(lia)) | pose proof (Hoc (p - n) ltac:(lia))]; | |
| lia. } | |
| pose proof (Hoc k ltac:(lia)) as Ho. pose proof (Hrb k ltac:(lia)) as Hb. pose proof (Hbias k ltac:(lia)) as Hbs. | |
| pose proof (Nat.pow_nonzero 2 al ltac:(lia)) as Hp2. | |
| unfold rec_of. destruct (tin (nth k us tu0)) as [|[p0 z0] [|[p1 z1] t]] eqn:Et; unfold rec_ok, SINK. | |
| - lia. | |
| - assert (H0 : In (p0, z0) (tin (nth k us tu0))) by (rewrite Et; left; reflexivity). | |
| pose proof (Hz k p0 z0 ltac:(lia) H0). pose proof (Hc p0 (Hb p0 z0 H0)). lia. | |
| - assert (H0 : In (p0, z0) (tin (nth k us tu0))) by (rewrite Et; left; reflexivity). | |
| assert (H1 : In (p1, z1) (tin (nth k us tu0))) by (rewrite Et; right; left; reflexivity). | |
| pose proof (Hz k p0 z0 ltac:(lia) H0). pose proof (Hz k p1 z1 ltac:(lia) H1). | |
| pose proof (Hc p0 (Hb p0 z0 H0)). pose proof (Hc p1 (Hb p1 z1 H1)). lia. | |
| Qed. | |
| Hypotheses | |
| (Hfan : forall k, k < length us -> length (tin (nth k us tu0)) <= 2) | |
| (* the cell of a unit's value holds it until every record that reads it *) | |
| (Hunit : forall k p z, k < length us -> In (p, z) (tin (nth k us tu0)) -> n <= p -> lastw k (oc (p - n)) = Some (p - n)) | |
| (* the cell of a state bit is not written before a record that reads the bit *) | |
| (Hbit : forall k p z, k < length us -> In (p, z) (tin (nth k us tu0)) -> p < n -> lastw k (sc p) = None). | |
| Lemma wval_rec : forall k u w, length (tin u) <= 2 -> (forall p z, In (p, z) (tin u) -> wcell w (scell p) = E0 p) -> | |
| wval w (rec_of k u) = fire u E0. | |
| Proof. | |
| intros k u w Hl H. unfold rec_of, fire. destruct (tin u) as [|[p0 z0] [|[p1 z1] t]] eqn:Et; cbn [length] in Hl. | |
| - cbn [wval wsum]. f_equal. lia. | |
| - cbn [wval wsum]. rewrite (H p0 z0 (or_introl eq_refl)). f_equal. lia. | |
| - destruct t as [|? ?]; [|cbn [length] in Hl; lia]. cbn [wval wsum]. | |
| rewrite (H p0 z0 (or_introl eq_refl)), (H p1 z1 (or_intror (or_introl eq_refl))). f_equal. lia. | |
| Qed. | |
| Lemma net_recs_nth : forall k, k < length us -> nth_error net_recs k = Some (rec_of k (nth k us tu0)). | |
| Proof. | |
| intros k Hk. unfold net_recs. rewrite nth_error_map, nth_error_seq. | |
| destruct (Nat.ltb_spec k (length us)); [reflexivity | lia]. | |
| Qed. | |
| (* after the first m records every cell holds the value of the last record that wrote it, or its first value *) | |
| Lemma sched_inv : forall m, m <= length us -> forall c, | |
| wget (wrun (firstn m net_recs) w0) c = match lastw m c with Some k => E0 (n + k) | None => wget w0 c end. | |
| Proof. | |
| induction m as [|m IH]; intros Hm c; [reflexivity|]. | |
| rewrite (firstn_S_nth _ m _ (net_recs_nth m ltac:(lia))), wrun_app. cbn [wrun]. unfold wexec. | |
| set (w := wrun (firstn m net_recs) w0). | |
| assert (Hlw : length w = length w0) by apply length_wrun. | |
| assert (Hao : ao_of (rec_of m (nth m us tu0)) = oc m) by (unfold rec_of; destruct (tin _) as [|[? ?] [|[? ?] ?]]; reflexivity). | |
| rewrite Hao, wget_wnext by (pose proof (Hoc m ltac:(lia)); lia). | |
| cbn [lastw]. rewrite (Nat.eqb_sym c (oc m)). destruct (Nat.eqb_spec (oc m) c) as [Ec|Ec]; [|apply IH; lia]. | |
| unfold E0. rewrite run_at by (lia || exact Hrb). apply wval_rec; [apply Hfan; lia|]. | |
| intros p z Hin. pose proof (Hrb m ltac:(lia) p z Hin) as Hp. | |
| unfold scell, wcell. destruct (Nat.ltb_spec p n) as [Hpn|Hpn]. | |
| - pose proof (Hsc p Hpn) as Hs. replace (Nat.eqb (sc p) SINK) with false by (symmetry; apply Nat.eqb_neq; unfold SINK, HO in *; lia). | |
| unfold w. rewrite (IH ltac:(lia)), (Hbit m p z ltac:(lia) Hin Hpn). unfold E0. rewrite run_prefix by exact Hpn. | |
| unfold x0. rewrite (nth_map_seq _ (fun i => wget w0 (sc i)) n p false Hpn). reflexivity. | |
| - pose proof (Hoc (p - n) ltac:(lia)) as Ho. | |
| replace (Nat.eqb (oc (p - n)) SINK) with false by (symmetry; apply Nat.eqb_neq; unfold SINK, HO in *; lia). | |
| unfold w. rewrite (IH ltac:(lia)), (Hunit m p z ltac:(lia) Hin Hpn). f_equal. lia. | |
| Qed. | |
| (* the cell of each state bit is written last by the unit of its next value *) | |
| Variable nx : list nat. | |
| Hypotheses (Hnx : length nx = n) | |
| (Hnext : forall i, i < n -> exists k, nth i nx 0 = n + k /\ lastw (length us) (sc i) = Some k). | |
| (* one run of the records leaves the next state of the netlist in the cells of the state bits *) | |
| Theorem sched_run : forall i, i < n -> wget (wrun net_recs w0) (sc i) = nth i (netstep n us nx x0) false. | |
| Proof. | |
| intros i Hi. assert (Hl : length net_recs = length us) by (unfold net_recs; rewrite length_map, length_seq; reflexivity). | |
| rewrite <- (firstn_all2 net_recs (le_n _)), Hl, (sched_inv (length us) (le_n _)). | |
| destruct (Hnext i Hi) as (k & Ek & Lk). rewrite Lk. | |
| unfold netstep. cbv zeta. rewrite (nth_map_d _ _ _ nx i false 0) by lia. rewrite Ek. reflexivity. | |
| Qed. | |
| End Sched. | |
| (* ---- Lemma 3.3: one pass of the records of a netlist evaluates it ------------------------------------------------- *) | |
| Theorem netlist_pass : forall al K S0 L s0 n us nx sc oc, | |
| 4 <= al -> 2 <= K -> 1 <= S0 -> 1 <= L -> fits al K S0 L s0 -> | |
| let rs := net_recs n us sc oc in | |
| bq (nth (kap s0) (banks s0) bank0) = encA al (rs ++ repeat EMPTY (S0 - length rs)) -> | |
| bs (nth (kap s0) (banks s0) bank0) = 0 -> length us <= S0 -> reqclear (win s0) -> | |
| (forall k p z, k < length us -> In (p, z) (tin (nth k us tu0)) -> z = 1%Z \/ z = (-1)%Z) -> | |
| (forall k, k < length us -> (-8 <= Net.tb (nth k us tu0) <= 7)%Z) -> | |
| (forall k, k < length us -> length (tin (nth k us tu0)) <= 2) -> | |
| (forall k, k < length us -> reads_below (nth k us tu0) (n + k)) -> | |
| (forall i, i < n -> HO < sc i < 2 ^ al) -> (forall k, k < length us -> HO < oc k < 2 ^ al) -> | |
| (forall k p z, k < length us -> In (p, z) (tin (nth k us tu0)) -> n <= p -> lastw oc k (oc (p - n)) = Some (p - n)) -> | |
| (forall k p z, k < length us -> In (p, z) (tin (nth k us tu0)) -> p < n -> lastw oc k (sc p) = None) -> | |
| length nx = n -> (forall i, i < n -> exists k, nth i nx 0 = n + k /\ lastw oc (length us) (sc i) = Some k) -> | |
| let s := itern al K S0 L S0 s0 in | |
| (forall i, i < n -> wget (win s) (sc i) = nth i (netstep n us nx (x0 n sc (win s0))) false) | |
| /\ View.mv al K S0 L s0 S0 s | |
| (mkV (win s) (vr (view0 al K s0)) (va (view0 al K s0)) (vc (view0 al K s0)) false). | |
| Proof. | |
| intros al K S0 L s0 n us nx sc oc Hal HK HS HL Hfit rs Hbank Hslot Hlen Hq Hz Hbias Hfan Hrb Hsc Hoc Hunit Hbit | |
| Hnx Hnext s. | |
| assert (HW : length (win s0) = 2 ^ al) by (destruct Hfit; assumption). | |
| assert (Hlr : length rs = length us) by (unfold rs, net_recs; rewrite length_map, length_seq; reflexivity). | |
| rewrite <- HW in Hsc, Hoc. | |
| pose proof (pass_run al K S0 L s0 rs Hal HK HS HL Hfit Hbank Hslot ltac:(lia) | |
| (net_recs_ok n us sc oc (win s0) Hrb Hsc Hoc al HW Hz Hbias) | |
| (net_recs_wrec n us sc oc (win s0) Hrb Hsc Hoc) Hq) as M. | |
| fold s in M. | |
| assert (Ew : win s = wrun rs (win s0)) by (destruct M as (_ & E & _); exact E). | |
| split. | |
| - intros i Hi. rewrite Ew. exact (sched_run n us sc oc (win s0) Hrb Hsc Hoc Hfan Hunit Hbit nx Hnx Hnext i Hi). | |
| - rewrite Ew. exact M. | |
| Qed. | |