Nock Interpreter Engineer

Expert guidance for implementing Nock virtual machines across multiple programming languages with proper evaluation loops, tree operations, and runtime optimization.

Implementation Architecture

Core Components

1. Noun Representation

Atoms: Natural numbers with arbitrary precision

• C: GMP (GNU Multiple Precision) or custom BigInt
• Python: Built-in

  int

  (unlimited precision)
• Rust:

  num-bigint

  crate or

  bigint

  crate
• Haskell:

  Integer

  type (native)
• JavaScript:

  BigInt

  (ES2020+)

Cells: Ordered pairs (cons cells)

pub enum Noun {
    Atom(BigUint),
    Cell(Box<Noun>, Box<Noun>),
}

2. Parser & Printer

Parse text format to internal representation:

[a b c]        -> Cell(Atom(a), Cell(Atom(b), Atom(c)))
123             -> Atom(123)
[a [b c]]      -> Cell(Atom(a), Cell(Atom(b), Atom(c)))

Print back to readable format.

3. Evaluation Loop

Pattern matching on formula opcodes (0-12):

def evaluate(subject, formula):
    while True:
        if not is_cell(formula):
            raise NockCrash("formula must be cell")

        op, rest = formula
        result = dispatch(op, subject, rest)
        if is_crash(result):
            return result
        subject, formula = result, rest
        if is_constant(formula):  # Rule 1
            return formula

Nock Rules Implementation

Rule 0: Slot (

[a b] /

)

Binary tree addressing for efficient axis traversal:

[subject slot] / = value_at_slot

Implementation: Convert slot number to axis path (left/right sequence), traverse subject tree.

Rule 1: Constant (

[a] *

)

[subject] * = a

Stops evaluation, returns constant

a

.

Rule 2: Evaluate (

[a b c] +

)

[subject [a b]] + = [subject a] c

Recurse: evaluate

a

against

subject

, then evaluate result as formula with

c

.

Rule 3: Cell Test (

[a] ?

)

[subject a] ? = 0 if a is cell, 1 if a is atom

Type discrimination for atoms vs cells.

Rule 4: Increment (

[a] +

)

[subject a] + = a + 1

Natural number addition.

Rule 5: Equality (

[a b] =

)

[subject a b] = = a b

Structural equality:

0

if identical,

1

if different.

Rule 6-9: Composition

• Rule 6:

  [[a b] c] /

  =

  [[a b] / c]

• Rule 7:

  [a b c] =

  =

  a b c

  (three-element cell)
• Rule 8:

  [a b] +

  =

  a + b

• Rule 9:

  [a b] +

  =

  a + b

Formulas 2-9 are composites of rules 0-5.

Rule 10: Edit (

[a b c]

)

[subject [a b c]] = nock(subject, b)

Tree editing; replaces part of the subject at axis

a

.

Rule 11: Hint (

[a b]

)

[subject [a b]] = nock(subject, b)

Optimization hint; evaluates

b

and may use

a

as a hint to the runtime.

Rule 12: Scry (

[a b] ^

)

[subject [a b]] ^ = memory[a][b]

Referentially transparent read of memory slot

b

within noun

a

.

Performance Patterns

Tail Call Optimization (TCO)

Detect and optimize recursive formulas:

# Before: creates stack frames
[subject [[a b] c]] + = ...

# After: if formula ends with recursive call, reuse stack
if ends_with_recursive_call(formula):
    return tco_evaluate(subject, formula)

Memoization

Cache evaluation results for repeated sub-formulas:

_memo = {}

def memo_evaluate(subject, formula):
    key = (subject, formula)
    if key in _memo:
        return _memo[key]
    result = evaluate(subject, formula)
    _memo[key] = result
    return result

Lazy Evaluation

Defer computation until value needed:

class Thunk:
    def __init__(self, subject, formula):
        self.subject = subject
        self.formula = formula
        self._cached = None

    def force(self):
        if self._cached is None:
            self._cached = evaluate(self.subject, self.formula)
        return self._cached

Language-Specific Patterns

C Implementation

typedef struct {
    mpz_t atom;
    struct Noun *cell;
} Noun;

Noun* slot(Noun* subject, Noun* axis);
Noun* evaluate(Noun* subject, Noun* formula);

Pros: Maximum control, pointer efficiency Cons: Manual memory management, complexity

Python Implementation

from typing import Union

Noun = Union[int, tuple]

def evaluate(subject: Noun, formula: Noun) -> Noun:
    if not isinstance(formula, tuple):
        raise NockCrash("formula must be cell")
    ...

Pros: Simplicity, fast prototyping Cons: Performance overhead

Rust Implementation

pub enum Noun {
    Atom(BigUint),
    Cell(Box<Noun>, Box<Noun>),
}

impl Noun {
    pub fn evaluate(&self, formula: &Noun) -> Result<Noun, NockCrash> {
        match formula {
            Noun::Cell(op, rest) => dispatch(op, self, rest),
            _ => Ok(formula.clone()),
        }
    }
}

Pros: Memory safety, zero-cost abstractions Cons: Borrow checker complexity

Haskell Implementation

data Noun = Atom Integer | Cell Noun Noun

evaluate :: Noun -> Noun -> Noun
evaluate subject formula = case formula of
    Cell (Atom 0, rest) -> slot subject rest
    Cell (Atom 1, rest) -> rest
    Cell (Atom 2, Cell(a, Cell(b, c))) -> evaluate (evaluate subject a) c
    ...

Pros: Type safety, pattern matching Cons: Learning curve

JavaScript Implementation

class Noun {
    constructor(value) {
        this.isCell = Array.isArray(value);
        this.value = value;
    }
}

function evaluate(subject, formula) {
    if (!formula.isCell) {
        throw new NockCrash("formula must be cell");
    }
    const [op, ...rest] = formula.value;
    return dispatch(op, subject, rest);
}

Pros: Web compatibility Cons: Performance, type safety

Testing & Validation

Reference Test: Decrement

def test_decrement():
    subject = 0
    formula = [8 [1 0] 8 [1 6 [5 [0 7]] 4 0 6] [0 6] 9 2 [0 2] [4 0 6] 0 7] 9 2 0 1]
    result = evaluate(subject, formula)
    assert result == 0, f"Expected 0, got {result}"

Edge Cases

• Empty subject:

  [~ [1 0]]

  should work
• Large atoms: Test with 64-bit, 128-bit, larger
• Deep trees: Stack overflow prevention
• Memory pressure: Graceful handling, not crash

Benchmarking

Compare performance against reference implementations:

Implementation | Decrement (ms) | Formula 2 (ms) | Memory (MB)
-------------|-----------------|---------------|--------------
Python       | 150             | 50             | 25
Rust         | 5               | 0.5            | 3
C (GMP)     | 1               | 0.1            | 1

Common Pitfalls

1. Incorrect Slot Calculation

Slot 1 = axis [0 1]  // Correct
Slot 2 = axis [1 0]  // Correct, NOT [0 1 1]

2. Missing TCO

Deep recursion crashes stack without trampoline or TCO.

3. Inefficient Noun Copying

Deep clones of nouns create O(n²) behavior. Use reference counting or structural sharing.

4. Incorrect Subject Handling

Forgetting to update

subject

after evaluation changes context.

Resources

• Nock 4K Specification
• nock-interpreter-patterns
• nock-multi-language-implementations
• nock-specification-reference