summaryrefslogtreecommitdiff
path: root/ocaml/README.md
blob: 18784e7232a947e7ebb9ea1e39956ef20cd3c870 (plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
# Vere Nock Interpreter - OCaml Port

This is an OCaml port of the Nock interpreter from Vere (the Urbit C runtime).

## Overview

This initial port focuses on the **reference Nock interpreter** (`_n_nock_on` from `vere/pkg/noun/nock.c`). It implements the core Nock specification with all 12 opcodes.

### What's Implemented

- **Noun type system** (`noun.ml`): Nouns are either atoms (arbitrary-precision integers via Zarith) or cells (pairs of nouns)
- **Basic noun operations**:
  - Fragment/axis addressing (`slot`)
  - Head/tail extraction
  - Equality testing
  - Pretty printing

- **Nock interpreter** (`nock.ml`): Complete implementation of all Nock opcodes:
  - **0**: Slot/fragment lookup
  - **1**: Constant
  - **2**: Nock (recursion with new subject)
  - **3**: Is-cell test
  - **4**: Increment
  - **5**: Equality test
  - **6**: If-then-else
  - **7**: Composition
  - **8**: Push (augment subject)
  - **9**: Call with axis
  - **10**: Hint (currently ignored, as in reference implementation)
  - **11**: Scry (raises Exit, as in reference implementation)

- **Test suite** (`test_nock.ml`): Comprehensive tests for all opcodes

## Building

Requires:
- OCaml (tested with recent versions)
- Dune build system
- Zarith library (for arbitrary-precision integers)

```bash
dune build
```

## Running Tests

```bash
dune exec ./test_nock.exe
```

All tests should pass.

## Benchmarks

Run benchmarks to compare performance:

```bash
# Run OCaml benchmark
dune exec ./bench_nock.exe

# Run simple C benchmark (for comparison)
./bench_simple

# Run full comparison
./compare.sh
```

### Performance Comparison

Benchmark results comparing the OCaml implementation against a simple C implementation:

| Operation              | C (Mops/sec) | OCaml (Mops/sec) | Ratio (C/OCaml) |
|------------------------|--------------|------------------|-----------------|
| Slot/fragment          | 579          | 42.5             | 13.6x           |
| Constant               | 595          | 142              | 4.2x            |
| Is-cell test           | 271          | 56.6             | 4.8x            |
| Increment              | 265          | 63.1             | 4.2x            |
| Equality               | 24           | 29.6             | 0.8x (faster!)  |
| If-then-else           | 185          | 37.2             | 5.0x            |
| Composition            | 174          | 36.0             | 4.8x            |
| Push                   | 26.5         | 32.7             | 0.8x (faster!)  |
| Cell construction      | 25.9         | 53.2             | 0.5x (faster!)  |
| Deep slot lookup       | 566          | 19.2             | 29.6x           |

**Key observations:**

1. **Simple operations** (slot, constant): C is 4-14x faster due to no GC overhead and direct pointer manipulation
2. **Memory-intensive operations** (equality, push, cell construction): OCaml is **competitive or faster** due to efficient allocation and GC
3. **Average performance**: C is ~2-5x faster for most operations

**Important notes:**
- The C benchmark is a simplified implementation without Vere's loom allocator, jet system, or other infrastructure
- OCaml uses Zarith (GMP-based) for arbitrary-precision integers, while simple C uses direct 64-bit values
- OCaml provides memory safety and type safety with reasonable performance
- For production use, the full Vere implementation would be faster due to jets and memoization

## Architecture

### Differences from C Implementation

1. **Memory management**: OCaml's GC vs Vere's loom-based allocation
2. **No bytecode compiler** (yet): This port only includes the reference interpreter, not the optimized bytecode interpreter
3. **No jet system** (yet): Jets (optimized implementations of common Nock formulas) are not yet implemented
4. **Simple error handling**: Uses OCaml exceptions instead of Vere's bail mechanism

### Type Mapping

| Vere (C)            | OCaml                 |
|---------------------|----------------------|
| `u3_noun`           | `noun` (variant type) |
| `u3_atom`           | `Atom of Z.t`        |
| `u3_cell`           | `Cell of noun * noun`|
| `u3_none`           | Not used (Option type instead) |

## Next Steps for Porting

Potential areas to expand:

1. **Bytecode compiler**: Port the bytecode compiler and interpreter (~100 opcodes)
2. **Jet system**: Implement the jet dashboard for accelerating common computations
3. **Memory management**: Implement loom-style allocation (optional, for closer parity)
4. **Memoization**: Port the `%memo` hint implementation
5. **Integration**: Hook up to other Vere subsystems (jets, traces, etc.)

## Files

- `noun.ml` - Noun type and basic operations
- `nock.ml` - Nock interpreter
- `test_nock.ml` - Test suite
- `dune` - Build configuration
- `dune-project` - Dune project file

## References

- [Nock Specification](https://developers.urbit.org/reference/nock/definition)
- [Vere Source](https://github.com/urbit/vere)
- Original C implementation: `vere/pkg/noun/nock.c`