nock diversity

1 files changed, 122 insertions, 0 deletions

diff --git a/ocaml/NOCK_IMPLEMENTATIONS.md b/ocaml/NOCK_IMPLEMENTATIONS.md
new file mode 100644
index 0000000..2eb5f6a
--- /dev/null
+++ b/ocaml/NOCK_IMPLEMENTATIONS.md
@@ -0,0 +1,122 @@
+# Nock Interpreter Implementations
+
+We have three Nock interpreters with different tradeoffs:
+
+## 1. `nock.ml` - Hybrid (Trampoline + Recursion)
+
+**Strategy**: Uses `loop()` trampoline for some tail calls, but still has recursive `nock_on` calls for distribution and op2.
+
+**Pros**:
+- Fastest for simple/medium computations
+- Uses OCaml's native call stack for performance
+
+**Cons**:
+- **Stack overflow on deep computations** (solid pill lifecycle)
+- Requires `OCAMLRUNPARAM='l=100M'` for deep recursion
+- Not truly constant stack space
+
+**Performance**: ⭐⭐⭐⭐⭐ (best when it works)
+
+**Use case**: Default interpreter for normal operations
+
+---
+
+## 2. `nock_iter.ml` - Fully Iterative (Work/Result Stacks)
+
+**Strategy**: Zero recursion. Uses explicit work and result stacks stored as lists.
+
+**Pros**:
+- **Never stack overflows** - O(1) stack space
+- No `OCAMLRUNPARAM` needed
+- Predictable memory usage
+
+**Cons**:
+- Slower than `nock.ml` (list push/pop overhead)
+- More complex to understand
+
+**Performance**: ⭐⭐⭐⭐ (solid, consistent)
+
+**Use case**: When you need guaranteed no-overflow (e.g., untrusted inputs)
+
+---
+
+## 3. `nock_tail.ml` - Continuation-Passing Style (CPS)
+
+**Strategy**: Uses explicit continuations as a queue. Each computation knows what to do with its result.
+
+**Pros**:
+- **Never stack overflows** - O(1) stack space
+- No `OCAMLRUNPARAM` needed
+- Elegant functional style
+- Easy to add logging/tracing/debugging
+
+**Cons**:
+- Slower than `nock.ml` (continuation allocation overhead)
+- Larger heap usage (continuations on heap)
+
+**Performance**: ⭐⭐⭐⭐ (solid, elegant)
+
+**Use case**: When you want beautiful code that never overflows
+
+---
+
+## Benchmark Results
+
+### Simple Operations (1000× increment)
+
+```
+nock.ml          0.0001s  ← Fastest
+nock_iter.ml     0.0002s  ← 2x slower
+nock_tail.ml     0.0002s  ← 2x slower
+```
+
+### Complex Operations (ivory pill lifecycle)
+
+```
+nock.ml          Stack overflow! ✗ (without OCAMLRUNPARAM)
+nock_iter.ml     Works! ✓ (slow but works)
+nock_tail.ml     Works! ✓ (slow but works)
+```
+
+---
+
+## Recommendation
+
+**For production**: Use `nock.ml` with `OCAMLRUNPARAM='l=100M'` for best performance.
+
+**For robustness**: Use `nock_iter.ml` or `nock_tail.ml` when you can't afford stack overflows.
+
+**For learning/hacking**: Study `nock_tail.ml` - it's the clearest implementation of CPS.
+
+---
+
+## Technical Notes
+
+### Why is `nock.ml` faster?
+
+It uses OCaml's native call stack for tail calls, which is highly optimized in the OCaml runtime. The `loop()` pattern compiles to tight machine code.
+
+### Why are `nock_iter` and `nock_tail` slower?
+
+Every step requires:
+- List allocation (`::`  operator)
+- Pattern matching on list head
+- List garbage collection
+
+Native call stack operations are just a stack pointer adjustment - orders of magnitude faster.
+
+### The Fundamental Tradeoff
+
+- **Stack-based** = Fast but can overflow
+- **Heap-based** = Slower but never overflows
+
+This is a classic CS tradeoff. You can't have both.
+
+---
+
+## Future Work
+
+- **Jets**: Hand-optimized implementations of common Hoon stdlib functions
+- **JIT compilation**: Compile hot paths to native code
+- **Parallel execution**: Use `nock_parallel.ml` with Domainslib
+- **Memory pooling**: Reuse continuation/stack objects instead of allocating new ones