phanerozoic's picture
Put the organism first and move serialization, sizes and the Rocq map to appendices
5ee1fb5
Raw History Blame Contribute Delete
7.64 kB
(* The SUBLEQ host H_A as a netlist of ternary threshold units, block by block in the order of
the generator, for words of A bits (Construction 5.8), and the machine it computes. *)
From Stdlib Require Import List Bool Arith ZArith Lia.
Import ListNotations.
From TH Require Import TwoHead Net Gates.
Section Host.
Variable A : nat.
(* the words of memory, and the state bits: the counter, the halt bit, the memory *)
Definition SW : nat := 2 ^ A.
Definition nH : nat := A + 1 + SW * A.
(* bit t of an A-bit value, most significant first *)
Definition bitof (v t : nat) : bool := Nat.testbit v (A - 1 - t).
Definition pcb (i : nat) : sref := SIn i.
Definition haltb : sref := SIn A.
Definition mu (j t : nat) : sref := SIn (A + 1 + j * A + t).
(* the literals asserting that the bits f 0 .. f (A - 1), most significant first, spell v *)
Definition lits (f : nat -> sref) (v : nat) : list lit := map (fun t => (f t, bitof v t)) (seq 0 A).
Definition opb (o t : nat) : sref := SRef 6 (o * A + t) 0.
Definition xv (i : nat) : sref := SRef 14 (A - 1 - i) 0.
Definition yv (i : nat) : sref := SRef 15 (A - 1 - i) 0.
Definition prr (i : nat) : sref := SRef 16 i 0.
Definition tb : nat := 16 + A.
(* 0 to 16: decode, fetch, operands, reads, propagate signals *)
Definition blk_P : block := Blk SW 1 (fun j => [sAND (lits pcb j)]).
Definition blk_HP : block := Blk A 1 (fun i => [sAND [(pcb i, true); (haltb, true)]]).
Definition blk_FA (o : nat) : block :=
Blk (A * SW) 1 (fun m => [sAND [(mu ((m mod SW + o) mod SW) (m / SW), true); (SRef 0 (m mod SW) 0, true)]]).
Definition blk_Q : block :=
Blk A 1 (fun i => [sOR (map (fun j => (SRef 0 j 0, true))
(filter (fun j => bitof ((j + 3) mod SW) i) (seq 0 SW)))]).
Definition blk_F : block :=
Blk (3 * A) 1 (fun m => [sOR (map (fun j => (SRef (2 + m / A) ((m mod A) * SW + j) 0, true)) (seq 0 SW))]).
Definition blk_PA : block := Blk SW 1 (fun j => [sAND (lits (opb 0) j)]).
Definition blk_PB : block := Blk SW 1 (fun j => [sAND (lits (opb 1) j)]).
Definition blk_AC : block := Blk 1 1 (fun _ => [sAND (map (fun t => (opb 2 t, true)) (seq 0 A))]).
Definition blk_W : block := Blk SW 1 (fun j => [sAND [(haltb, false); (SRef 8 j 0, true)]]).
Definition blk_RX : block :=
Blk (A * SW) 1 (fun m => [sAND [(mu (m mod SW) (m / SW), true); (SRef 7 (m mod SW) 0, true)]]).
Definition blk_RY : block :=
Blk (A * SW) 1 (fun m => [sAND [(mu (m mod SW) (m / SW), true); (SRef 8 (m mod SW) 0, true)]]).
Definition blk_KP : block :=
Blk (SW * A) 1 (fun m => [sAND [(mu (m / A) (m mod A), true); (SRef 10 (m / A) 0, false)]]).
Definition blk_X : block := Blk A 1 (fun t => [sOR (map (fun j => (SRef 11 (t * SW + j) 0, true)) (seq 0 SW))]).
Definition blk_Y : block := Blk A 1 (fun t => [sOR (map (fun j => (SRef 12 (t * SW + j) 0, true)) (seq 0 SW))]).
Definition blk_PR : block := Blk (A - 1) 1 (fun i => [sOR [(xv i, false); (yv i, true)]]).
(* 17 to 15 + A: the carry terms into bit k, for k = 1 .. A - 1 *)
Definition blk_T (k : nat) : block :=
Blk 1 (S k) (fun _ => sAND (map (fun i => (prr i, true)) (seq 0 k))
:: map (fun j => sAND ([(yv j, true); (xv j, false)]
++ map (fun i => (prr i, true)) (seq (S j) (k - S j))))
(seq 0 k)).
(* tb to tb + 14: carries, equality, sum bits, branch, next counter, halt latch, next memory *)
Definition blk_C : block :=
Blk (A - 1) 1 (fun m => [sOR ((SRef (16 + S m) 0 0, true)
:: map (fun j => (SRef (16 + S m) 0 (S j), true)) (seq 0 (S m)))]).
Definition blk_AX : block := Blk A 1 (fun i => [sAND [(xv i, true); (yv i, true)]]).
Definition blk_NX : block := Blk A 1 (fun i => [sAND [(xv i, false); (yv i, false)]]).
Definition blk_XN : block := Blk A 1 (fun i => [sOR [(SRef (tb + 1) i 0, true); (SRef (tb + 2) i 0, true)]]).
Definition blk_EQ : block := Blk 1 1 (fun _ => [sAND (map (fun i => (SRef (tb + 3) i 0, true)) (seq 0 A))]).
Definition blk_R0 : block :=
Blk 1 3 (fun _ => [sOR [(yv 0, true); (xv 0, true)]; sOR [(yv 0, false); (xv 0, false)];
sAND [(SRef (tb + 5) 0 0, true); (SRef (tb + 5) 0 1, true)]]).
Definition blk_H : block :=
Blk (A - 1) 3 (fun m => map (fun b => SU b [(yv (S m), 1%Z); (xv (S m), (-1)%Z); (SRef tb m 0, 1%Z)])
[0%Z; (-1)%Z; (-2)%Z]).
Definition blk_R : block :=
Blk (A - 1) 1 (fun m => [SU (-1) [(SRef (tb + 6) m 0, 1%Z); (SRef (tb + 6) m 1, (-1)%Z);
(SRef (tb + 6) m 2, 1%Z)]]).
Definition blk_LEQ : block :=
Blk 1 1 (fun _ => [SU (-1) [(SRef (tb + 6) (A - 2) 0, 1%Z); (SRef (tb + 6) (A - 2) 1, (-1)%Z);
(SRef (tb + 6) (A - 2) 2, 1%Z); (SRef (tb + 4) 0 0, 1%Z)]]).
Definition rbit (k : nat) : sref := if Nat.eqb k 0 then SRef (tb + 5) 0 2 else SRef (tb + 7) (k - 1) 0.
Definition blk_TA : block :=
Blk A 1 (fun i => [sAND [(haltb, false); (SRef (tb + 8) 0 0, true); (opb 2 i, true)]]).
Definition blk_TB : block :=
Blk A 1 (fun i => [sAND [(haltb, false); (SRef (tb + 8) 0 0, false); (SRef 5 i 0, true)]]).
Definition blk_NP : block :=
Blk A 1 (fun i => [sOR [(SRef 1 i 0, true); (SRef (tb + 9) i 0, true); (SRef (tb + 10) i 0, true)]]).
Definition blk_HAB : block :=
Blk 1 3 (fun _ => [sAND [(haltb, false); (SRef (tb + 8) 0 0, true); (SRef 9 0 0, true)];
sAND [(haltb, false); (SRef (tb + 8) 0 0, false); (SRef 0 (SW - 4) 0, true)];
sOR [(haltb, true); (SRef (tb + 12) 0 0, true); (SRef (tb + 12) 0 1, true)]]).
Definition blk_WR : block :=
Blk (SW * A) 1 (fun m => [sAND [(rbit (A - 1 - m mod A), true); (SRef 10 (m / A) 0, true)]]).
Definition blk_NM : block := Blk (SW * A) 1 (fun m => [sOR [(SRef 13 m 0, true); (SRef (tb + 13) m 0, true)]]).
Definition hpre : list block :=
[blk_P; blk_HP; blk_FA 0; blk_FA 1; blk_FA 2; blk_Q; blk_F; blk_PA; blk_PB; blk_AC; blk_W; blk_RX; blk_RY;
blk_KP; blk_X; blk_Y; blk_PR].
Definition hpost : list block :=
[blk_C; blk_AX; blk_NX; blk_XN; blk_EQ; blk_R0; blk_H; blk_R; blk_LEQ; blk_TA; blk_TB; blk_NP; blk_HAB;
blk_WR; blk_NM].
Definition hblocks : list block := hpre ++ map blk_T (seq 1 (A - 1)) ++ hpost.
(* the unit computing the next value of each state bit *)
Definition hout (i : nat) : sref :=
if i <? A then SRef (tb + 11) i 0
else if Nat.eqb i A then SRef (tb + 12) 0 2
else SRef (tb + 14) (i - A - 1) 0.
Definition host_units : list tu := compile nH hblocks.
Definition host_next : list nat := map (fun i => idx nH hblocks (hout i)) (seq 0 nH).
(* ---- the machine: SUBLEQ on 2^A words of A bits, Definition 5.2 ------------------------ *)
Record hst := mkH { hpc : nat; hhalt : bool; hmem : list nat }.
Definition memv (s : hst) (j : nat) : nat := nth j (hmem s) 0.
Definition subleq (s : hst) : hst :=
if hhalt s then s
else
let p := hpc s in
let a := memv s p in
let b := memv s ((p + 1) mod SW) in
let c := memv s ((p + 2) mod SW) in
let r := (memv s b + SW - memv s a) mod SW in
let leq := Nat.eqb r 0 || Nat.leb (2 ^ (A - 1)) r in
let p' := if leq then c else (p + 3) mod SW in
mkH p' (Nat.eqb p' (SW - 1)) (map (fun j => if Nat.eqb j b then r else memv s j) (seq 0 SW)).
(* the state bits: the counter and each word most significant bit first *)
Definition wbits (v : nat) : list bool := map (bitof v) (seq 0 A).
Definition encodeH (s : hst) : list bool := wbits (hpc s) ++ [hhalt s] ++ concat (map wbits (hmem s)).
Definition hvalid (s : hst) : Prop :=
hpc s < SW /\ length (hmem s) = SW /\ Forall (fun v => v < SW) (hmem s).
End Host.