# 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