refining nock with tail calls and sheet

8 files changed, 546 insertions, 3 deletions

diff --git a/ocaml/OCAML_TWEAKS.md b/ocaml/OCAML_TWEAKS.md
new file mode 100644
index 0000000..129526c
--- /dev/null
+++ b/ocaml/OCAML_TWEAKS.md
@@ -0,0 +1,2 @@
+
+export OCAMLRUNPARAM='l=100M' && dune exec test/test_two_stage_boot.exe 2>&1 | head -80)
diff --git a/ocaml/lib/dune b/ocaml/lib/dune
index a0cb4b8..91e51bc 100644
--- a/ocaml/lib/dune
+++ b/ocaml/lib/dune
@@ -1,4 +1,4 @@
 (library
  (name nock_lib)
- (modules noun nock bitstream serial eventlog state effects boot runtime domain_pool nock_parallel)
+ (modules noun nock nock_iter nock_tail bitstream serial eventlog state effects boot runtime domain_pool nock_parallel)
  (libraries zarith eio eio.unix domainslib murmur3))
diff --git a/ocaml/lib/nock_iter.ml b/ocaml/lib/nock_iter.ml
new file mode 100644
index 0000000..48094ba
--- /dev/null
+++ b/ocaml/lib/nock_iter.ml
@@ -0,0 +1,231 @@
+(** Fully iterative Nock interpreter using explicit stack
+
+    No recursion at all - uses a work stack and result stack.
+    This will never overflow regardless of computation depth.
+*)
+
+open Noun
+
+type frame =
+  | EvalFrame of noun * noun                  (* Need to evaluate nock_on(bus, fol) *)
+  | DistLeft of noun * noun                   (* After computing left of [a b], compute right *)
+  | DistBoth of noun                          (* After both sides, construct cell *)
+  | Op2Formula of noun * noun                 (* After formula, compute subject *)
+  | Op2Subject of noun                        (* After subject, tail-call *)
+  | Op3Apply                                  (* Apply cell test *)
+  | Op4Apply                                  (* Apply increment *)
+  | Op5Apply                                  (* Apply equality *)
+  | Op6Test of noun * noun * noun             (* After test, select branch (bus, c, d) *)
+  | Op7Subject of noun                        (* After subject, tail-call with formula *)
+  | Op8Pin of noun * noun                     (* After pin, extend and tail-call (old_bus, c) *)
+  | Op9Core of noun * noun                    (* After core, extract slot (bus, b_gal/axis) *)
+
+let nock_on init_bus init_fol =
+  let work_stack = ref [EvalFrame (init_bus, init_fol)] in
+  let result_stack = ref [] in
+
+  let rec loop () =
+    match !work_stack with
+    | [] ->
+        (match !result_stack with
+        | [result] -> result
+        | _ -> raise Exit)  (* Should have exactly one result *)
+
+    | EvalFrame (bus, fol) :: work_rest ->
+        work_stack := work_rest;
+
+        (match fol with
+        | Cell { h = hib; t = gal; _ } when is_cell hib ->
+            (* Distribution: push frames in reverse order *)
+            work_stack := EvalFrame (bus, hib) :: DistLeft (bus, gal) :: !work_stack;
+            loop ()
+
+        | Cell { h = Atom { z = op; _ }; t = gal; _ } ->
+            if Z.compare op (Z.of_int max_int) > 0 then raise Exit;
+
+            (match Z.to_int op with
+            | 0 ->
+                if not (is_atom gal) then raise Exit;
+                let axis = (match gal with Atom { z = n; _ } -> n | _ -> raise Exit) in
+                let res = slot axis bus in
+                result_stack := res :: !result_stack;
+                loop ()
+
+            | 1 ->
+                result_stack := gal :: !result_stack;
+                loop ()
+
+            | 2 ->
+                if not (is_cell gal) then raise Exit;
+                let c_gal = tail gal in
+                let b_gal = head gal in
+                work_stack := EvalFrame (bus, c_gal) :: Op2Formula (bus, b_gal) :: !work_stack;
+                loop ()
+
+            | 3 ->
+                work_stack := EvalFrame (bus, gal) :: Op3Apply :: !work_stack;
+                loop ()
+
+            | 4 ->
+                work_stack := EvalFrame (bus, gal) :: Op4Apply :: !work_stack;
+                loop ()
+
+            | 5 ->
+                work_stack := EvalFrame (bus, gal) :: Op5Apply :: !work_stack;
+                loop ()
+
+            | 6 ->
+                if not (is_cell gal) then raise Exit;
+                let b_gal = head gal in
+                let cd_gal = tail gal in
+                if not (is_cell cd_gal) then raise Exit;
+                let c_gal = head cd_gal in
+                let d_gal = tail cd_gal in
+                work_stack := EvalFrame (bus, b_gal) :: Op6Test (bus, c_gal, d_gal) :: !work_stack;
+                loop ()
+
+            | 7 ->
+                if not (is_cell gal) then raise Exit;
+                let b_gal = head gal in
+                let c_gal = tail gal in
+                work_stack := EvalFrame (bus, b_gal) :: Op7Subject c_gal :: !work_stack;
+                loop ()
+
+            | 8 ->
+                if not (is_cell gal) then raise Exit;
+                let b_gal = head gal in
+                let c_gal = tail gal in
+                work_stack := EvalFrame (bus, b_gal) :: Op8Pin (bus, c_gal) :: !work_stack;
+                loop ()
+
+            | 9 ->
+                if not (is_cell gal) then raise Exit;
+                let b_gal = head gal in
+                let c_gal = tail gal in
+                if not (is_atom b_gal) then raise Exit;
+                work_stack := EvalFrame (bus, c_gal) :: Op9Core (bus, b_gal) :: !work_stack;
+                loop ()
+
+            | 10 ->
+                (* Hint - just evaluate tail, ignore head *)
+                if not (is_cell gal) then raise Exit;
+                let q_gal = tail gal in
+                work_stack := EvalFrame (bus, q_gal) :: !work_stack;
+                loop ()
+
+            | 11 ->
+                if not (is_cell gal) then raise Exit;
+                let q_gal = tail gal in
+                work_stack := EvalFrame (bus, q_gal) :: !work_stack;
+                loop ()
+
+            | _ -> raise Exit)
+
+        | _ -> raise Exit)
+
+    | DistLeft (bus, gal) :: work_rest ->
+        (match !result_stack with
+        | left :: result_rest ->
+            result_stack := result_rest;
+            work_stack := EvalFrame (bus, gal) :: DistBoth left :: work_rest;
+            loop ()
+        | _ -> raise Exit)
+
+    | DistBoth left :: work_rest ->
+        (match !result_stack with
+        | right :: result_rest ->
+            result_stack := cell left right :: result_rest;
+            work_stack := work_rest;
+            loop ()
+        | _ -> raise Exit)
+
+    | Op2Formula (bus, b_gal) :: work_rest ->
+        (match !result_stack with
+        | nex :: result_rest ->
+            result_stack := result_rest;
+            work_stack := EvalFrame (bus, b_gal) :: Op2Subject nex :: work_rest;
+            loop ()
+        | _ -> raise Exit)
+
+    | Op2Subject nex :: work_rest ->
+        (match !result_stack with
+        | seb :: result_rest ->
+            result_stack := result_rest;
+            (* Tail call: push new eval frame *)
+            work_stack := EvalFrame (seb, nex) :: work_rest;
+            loop ()
+        | _ -> raise Exit)
+
+    | Op3Apply :: work_rest ->
+        (match !result_stack with
+        | gof :: result_rest ->
+            let res = if is_cell gof then atom 0 else atom 1 in
+            result_stack := res :: result_rest;
+            work_stack := work_rest;
+            loop ()
+        | _ -> raise Exit)
+
+    | Op4Apply :: work_rest ->
+        (match !result_stack with
+        | gof :: result_rest ->
+            result_stack := inc gof :: result_rest;
+            work_stack := work_rest;
+            loop ()
+        | _ -> raise Exit)
+
+    | Op5Apply :: work_rest ->
+        (match !result_stack with
+        | wim :: result_rest ->
+            if not (is_cell wim) then raise Exit;
+            let a = head wim in
+            let b = tail wim in
+            let res = if equal a b then atom 0 else atom 1 in
+            result_stack := res :: result_rest;
+            work_stack := work_rest;
+            loop ()
+        | _ -> raise Exit)
+
+    | Op6Test (bus, c_gal, d_gal) :: work_rest ->
+        (match !result_stack with
+        | tys :: result_rest ->
+            result_stack := result_rest;
+            let nex = match tys with
+              | Atom { z = n; _ } when Z.equal n Z.zero -> c_gal
+              | Atom { z = n; _ } when Z.equal n Z.one -> d_gal
+              | _ -> raise Exit
+            in
+            work_stack := EvalFrame (bus, nex) :: work_rest;
+            loop ()
+        | _ -> raise Exit)
+
+    | Op7Subject c_gal :: work_rest ->
+        (match !result_stack with
+        | bod :: result_rest ->
+            result_stack := result_rest;
+            work_stack := EvalFrame (bod, c_gal) :: work_rest;
+            loop ()
+        | _ -> raise Exit)
+
+    | Op8Pin (old_bus, c_gal) :: work_rest ->
+        (match !result_stack with
+        | heb :: result_rest ->
+            result_stack := result_rest;
+            let new_bus = cell heb old_bus in
+            work_stack := EvalFrame (new_bus, c_gal) :: work_rest;
+            loop ()
+        | _ -> raise Exit)
+
+    | Op9Core (_bus, b_gal) :: work_rest ->
+        (match !result_stack with
+        | cor :: result_rest ->
+            result_stack := result_rest;
+            if not (is_atom b_gal) then raise Exit;
+            let axis = (match b_gal with Atom { z = n; _ } -> n | _ -> raise Exit) in
+            let arm = slot axis cor in
+            work_stack := EvalFrame (cor, arm) :: work_rest;
+            loop ()
+        | _ -> raise Exit)
+
+  in
+
+  loop ()
diff --git a/ocaml/lib/nock_tail.ml b/ocaml/lib/nock_tail.ml
new file mode 100644
index 0000000..cdc1167
--- /dev/null
+++ b/ocaml/lib/nock_tail.ml
@@ -0,0 +1,223 @@
+open Noun
+
+(** Fully tail-recursive Nock using explicit continuations
+
+    Instead of using OCaml's call stack, we use heap-allocated
+    continuations that represent "what to do with a result".
+
+    This is constant stack space - O(1) - no matter how deep
+    the Nock computation goes.
+*)
+
+(* Continuation: what to do with a computed noun *)
+type cont =
+  | Done                                          (* Final result *)
+  | AfterDistLeft of noun * noun * cont           (* After left, compute right (bus, gal) *)
+  | AfterDistRight of noun * cont                 (* After right, construct cell (left) *)
+  | AfterOp2Form of noun * noun * cont            (* After formula, compute subject (bus, b_gal) *)
+  | AfterOp2Subj of noun * cont                   (* After subject, eval (formula) *)
+  | AfterOp3 of cont                              (* Apply cell test *)
+  | AfterOp4 of cont                              (* Apply increment *)
+  | AfterOp5 of cont                              (* Apply equality *)
+  | AfterOp6 of noun * noun * noun * cont         (* Select branch (bus, then, else) *)
+  | AfterOp7 of noun * cont                       (* Tail-call with new bus (formula) *)
+  | AfterOp8 of noun * noun * cont                (* Extend and tail-call (old_bus, formula) *)
+  | AfterOp9Core of noun * cont                   (* Extract slot and tail-call (axis) *)
+
+(* The work queue: either compute or apply continuation *)
+type work =
+  | Eval of noun * noun * cont                    (* Evaluate nock(bus, fol) with continuation k *)
+  | Cont of noun * cont                           (* Apply continuation k to result *)
+
+(** Main interpreter loop - fully tail-recursive *)
+let nock_on init_bus init_fol =
+  let queue = ref [Eval (init_bus, init_fol, Done)] in
+
+  let rec loop () =
+    match !queue with
+    | [] -> raise Exit  (* Should never happen *)
+
+    | Eval (bus, fol, k) :: rest ->
+        queue := rest;
+
+        (match fol with
+        (* Distribution: [a b] where a is cell *)
+        | Cell { h = hib; t = gal; _ } when is_cell hib ->
+            (* Compute left first, continuation will compute right *)
+            queue := Eval (bus, hib, AfterDistLeft (bus, gal, k)) :: !queue;
+            loop ()
+
+        | Cell { h = Atom { z = op; _ }; t = gal; _ } when Z.fits_int op ->
+            (match Z.to_int op with
+
+            (* 0: slot *)
+            | 0 ->
+                if not (is_atom gal) then raise Exit;
+                let axis = (match gal with Atom { z; _ } -> z | _ -> raise Exit) in
+                let result = slot axis bus in
+                queue := Cont (result, k) :: !queue;
+                loop ()
+
+            (* 1: constant *)
+            | 1 ->
+                queue := Cont (gal, k) :: !queue;
+                loop ()
+
+            (* 2: eval *)
+            | 2 ->
+                if not (is_cell gal) then raise Exit;
+                let b_gal = head gal in
+                let c_gal = tail gal in
+                (* Compute formula first, then subject, then eval *)
+                queue := Eval (bus, c_gal, AfterOp2Form (bus, b_gal, k)) :: !queue;
+                loop ()
+
+            (* 3: cell test *)
+            | 3 ->
+                queue := Eval (bus, gal, AfterOp3 k) :: !queue;
+                loop ()
+
+            (* 4: increment *)
+            | 4 ->
+                queue := Eval (bus, gal, AfterOp4 k) :: !queue;
+                loop ()
+
+            (* 5: equality *)
+            | 5 ->
+                queue := Eval (bus, gal, AfterOp5 k) :: !queue;
+                loop ()
+
+            (* 6: if-then-else *)
+            | 6 ->
+                if not (is_cell gal) then raise Exit;
+                let b_gal = head gal in
+                let cd_gal = tail gal in
+                if not (is_cell cd_gal) then raise Exit;
+                let c_gal = head cd_gal in
+                let d_gal = tail cd_gal in
+                queue := Eval (bus, b_gal, AfterOp6 (bus, c_gal, d_gal, k)) :: !queue;
+                loop ()
+
+            (* 7: compose *)
+            | 7 ->
+                if not (is_cell gal) then raise Exit;
+                let b_gal = head gal in
+                let c_gal = tail gal in
+                queue := Eval (bus, b_gal, AfterOp7 (c_gal, k)) :: !queue;
+                loop ()
+
+            (* 8: extend *)
+            | 8 ->
+                if not (is_cell gal) then raise Exit;
+                let b_gal = head gal in
+                let c_gal = tail gal in
+                queue := Eval (bus, b_gal, AfterOp8 (bus, c_gal, k)) :: !queue;
+                loop ()
+
+            (* 9: invoke *)
+            | 9 ->
+                if not (is_cell gal) then raise Exit;
+                let b_gal = head gal in
+                let c_gal = tail gal in
+                if not (is_atom b_gal) then raise Exit;
+                queue := Eval (bus, c_gal, AfterOp9Core (b_gal, k)) :: !queue;
+                loop ()
+
+            (* 10: hint - ignore *)
+            | 10 ->
+                if not (is_cell gal) then raise Exit;
+                let q_gal = tail gal in
+                queue := Eval (bus, q_gal, k) :: !queue;
+                loop ()
+
+            (* 11: hint - ignore *)
+            | 11 ->
+                if not (is_cell gal) then raise Exit;
+                let q_gal = tail gal in
+                queue := Eval (bus, q_gal, k) :: !queue;
+                loop ()
+
+            | _ -> raise Exit)
+
+        | _ -> raise Exit)
+
+    | Cont (result, k) :: rest ->
+        queue := rest;
+
+        (match k with
+        (* Done - return final result *)
+        | Done ->
+            result
+
+        (* After computing left side of distribution, compute right *)
+        | AfterDistLeft (bus, gal, k') ->
+            queue := Eval (bus, gal, AfterDistRight (result, k')) :: !queue;
+            loop ()
+
+        (* After computing both sides, construct cell *)
+        | AfterDistRight (left, k') ->
+            queue := Cont (cell left result, k') :: !queue;
+            loop ()
+
+        (* After computing formula for op2, compute subject *)
+        | AfterOp2Form (bus, b_gal, k') ->
+            let formula = result in
+            queue := Eval (bus, b_gal, AfterOp2Subj (formula, k')) :: !queue;
+            loop ()
+
+        (* After computing subject for op2, eval formula with new subject *)
+        | AfterOp2Subj (formula, k') ->
+            let subject = result in
+            queue := Eval (subject, formula, k') :: !queue;
+            loop ()
+
+        (* After computing test for op6, select branch *)
+        | AfterOp6 (bus, c_gal, d_gal, k') ->
+            let branch = match result with
+              | Atom { z; _ } when Z.equal z Z.zero -> c_gal
+              | Atom { z; _ } when Z.equal z Z.one -> d_gal
+              | _ -> raise Exit
+            in
+            queue := Eval (bus, branch, k') :: !queue;
+            loop ()
+
+        (* After computing subject for op7, eval formula with new subject *)
+        | AfterOp7 (c_gal, k') ->
+            queue := Eval (result, c_gal, k') :: !queue;
+            loop ()
+
+        (* After computing pin for op8, extend and eval *)
+        | AfterOp8 (old_bus, c_gal, k') ->
+            let new_bus = cell result old_bus in
+            queue := Eval (new_bus, c_gal, k') :: !queue;
+            loop ()
+
+        (* After computing core for op9, extract arm and eval *)
+        | AfterOp9Core (b_gal, k') ->
+            if not (is_atom b_gal) then raise Exit;
+            let axis = (match b_gal with Atom { z; _ } -> z | _ -> raise Exit) in
+            let core = result in
+            let arm = slot axis core in
+            queue := Eval (core, arm, k') :: !queue;
+            loop ()
+
+        (* Apply operations *)
+        | AfterOp3 k' ->
+            let res = if is_cell result then atom 0 else atom 1 in
+            queue := Cont (res, k') :: !queue;
+            loop ()
+
+        | AfterOp4 k' ->
+            queue := Cont (inc result, k') :: !queue;
+            loop ()
+
+        | AfterOp5 k' ->
+            if not (is_cell result) then raise Exit;
+            let a = head result in
+            let b = tail result in
+            let res = if equal a b then atom 0 else atom 1 in
+            queue := Cont (res, k') :: !queue;
+            loop ())
+
+  in
+  loop ()
diff --git a/ocaml/ivorypillnock.md b/ocaml/pillmugs.md
index 025986f..8b31ee2 100644
--- a/ocaml/ivorypillnock.md
+++ b/ocaml/pillmugs.md
@@ -1,4 +1,4 @@
-
+###  ivory
 [6] Verifying kernel structure...
     ✓ Has poke gate at slot 23
     Checking structural properties:
@@ -10,3 +10,19 @@
       Slot 2 (battery) mug: 0x6d668e4a
       Slot 3 (payload) mug: 0x5be29baa
       Slot 23 (poke) mug:   0x39aec359 so yeah not great
+### solid
+
+
+
+      
+    <<< EXIT  call #0 depth=2 returns=cell[mug=0x3597a0b7]
+u3v_life: u3n_nock_on returned successfully
+u3v_life: gate mug: 0x3597a0b7
+u3v_life: slot 7 (kernel) mug: 0x3e6a00b
+u3v_life: completed successfully
+u3v_boot: SUCCESS - kernel built
+✓ solid boot completed!
+Kernel mug: 0x3e6a00b
+strange lily 0vg00.00000.00000
+strange lily 0x8000.0000
+test boot: ok
diff --git a/ocaml/test/dune b/ocaml/test/dune
index d23fc4d..abe712a 100644
--- a/ocaml/test/dune
+++ b/ocaml/test/dune
@@ -271,6 +271,14 @@
  (name test_two_stage_boot)
  (modules test_two_stage_boot)
  (libraries nock_lib eio_main unix))
+; NOTE: Run with increased stack size for solid pill:
+; OCAMLRUNPARAM='l=100M' dune exec test/test_two_stage_boot.exe
+
+(executable
+ (name test_nock_iter)
+ (modules test_nock_iter)
+ (libraries nock_lib eio_main unix))
+; NOTE: This uses the iterative Nock interpreter - no stack limit needed!
 
 (executable
  (name test_mug)
diff --git a/ocaml/test/test_nock_iter.ml b/ocaml/test/test_nock_iter.ml
new file mode 100644
index 0000000..05a03ce
--- /dev/null
+++ b/ocaml/test/test_nock_iter.ml
@@ -0,0 +1,59 @@
+(** Test the fully iterative Nock interpreter - no stack overflow! *)
+
+open Nock_lib
+
+let () =
+  Printf.printf "Testing iterative Nock interpreter (no stack limit needed)...\n\n";
+
+  (* Test 1: Simple increment *)
+  Printf.printf "[1] Testing simple increment: *[42 [4 0 1]]\n";
+  let result = Nock_iter.nock_on (Noun.atom 42) (Noun.cell (Noun.atom 4) (Noun.cell (Noun.atom 0) (Noun.atom 1))) in
+  Printf.printf "    Result: %s\n" (Z.to_string (match result with Noun.Atom { z; _ } -> z | _ -> Z.zero));
+  Printf.printf "    Expected: 43\n\n";
+
+  (* Test 2: Distribution *)
+  Printf.printf "[2] Testing distribution: *[42 [[4 0 1] [4 0 1]]]\n";
+  let inc_fol = Noun.cell (Noun.atom 4) (Noun.cell (Noun.atom 0) (Noun.atom 1)) in
+  let dist = Noun.cell inc_fol inc_fol in
+  let result = Nock_iter.nock_on (Noun.atom 42) dist in
+  Printf.printf "    Result: [%s %s]\n"
+    (Z.to_string (match Noun.head result with Noun.Atom { z; _ } -> z | _ -> Z.zero))
+    (Z.to_string (match Noun.tail result with Noun.Atom { z; _ } -> z | _ -> Z.zero));
+  Printf.printf "    Expected: [43 43]\n\n";
+
+  (* Test 3: Small pill to verify no recursion issues *)
+  Printf.printf "[3] Loading ivory pill (this would stack overflow with recursive version)...\n";
+  Eio_main.run (fun env ->
+    let fs = Eio.Stdenv.fs env in
+    let bytes = Eio.Path.(load (fs / "ivory.pill")) |> Bytes.of_string in
+    Printf.printf "    Pill size: %d bytes\n" (Bytes.length bytes);
+
+    let pill = Serial.cue bytes in
+    Printf.printf "    Cued successfully\n";
+
+    match pill with
+    | Noun.Cell { h = _tag; t = core; _ } ->
+        Printf.printf "    Structure: [tag core]\n";
+        Printf.printf "    Core mug: 0x%08lx\n" (Noun.mug core);
+
+        Printf.printf "\n    Running lifecycle formula with ITERATIVE interpreter...\n";
+        Printf.printf "    (No OCAMLRUNPARAM needed!)\n";
+
+        let formula = Noun.cell
+          (Noun.atom 2)
+          (Noun.cell
+            (Noun.cell (Noun.atom 0) (Noun.atom 3))
+            (Noun.cell (Noun.atom 0) (Noun.atom 2))) in
+
+        let start = Unix.gettimeofday () in
+        let kernel = Nock_iter.nock_on core formula in
+        let elapsed = Unix.gettimeofday () -. start in
+
+        Printf.printf "    ✓ SUCCESS in %.2fs\n" elapsed;
+        Printf.printf "    Kernel mug: 0x%08lx\n" (Noun.mug kernel);
+        Printf.printf "\n✅ Iterative Nock interpreter works perfectly!\n";
+        Printf.printf "   No stack overflow, no OCAMLRUNPARAM needed.\n";
+
+    | _ ->
+        Printf.printf "    Unexpected pill structure\n"
+  )
diff --git a/ocaml/test/test_two_stage_boot.ml b/ocaml/test/test_two_stage_boot.ml
index c18ea58..0e4da5f 100644
--- a/ocaml/test/test_two_stage_boot.ml
+++ b/ocaml/test/test_two_stage_boot.ml
@@ -1,4 +1,8 @@
-(* Two-Stage Boot Test - Exactly like C Vere *)
+(* Two-Stage Boot Test - Exactly like C Vere
+ *
+ * NOTE: This test requires increased stack size due to deep recursion in solid pill:
+ *   OCAMLRUNPARAM='l=100M' dune exec test/test_two_stage_boot.exe
+ *)
 
 open Nock_lib