Ridgun

The language itself: a compiler that compiles itself, the stable project tool, the specification and the book

low_level_ridgun_runtime_design.md258 lines · 12.6 KBRaw

1	# Low-Level Ridgun Runtime Architecture: Portable Runtime Kernel vs Symbolic Assembly (`TASK-0013` Study)
2
3	## 1. Executive Summary & Motivation
4
5	With the completion of `TASK-0013` (`v0.9.11`), the self-hosted Ridgun compiler (`ridgunc`) emits 100% of its native ELF64 runtime kernel (`x86_64` and `arm64`) through symbolic Ridgun functions (`src/main/ridgun/lib/x86_64.rg` and `src/main/ridgun/lib/arm64.rg`), eliminating all legacy pre-assembled hex strings.
6
7	However, maintaining two architecture-specific runtime emitters (~3,000 lines of `x86_64` and ~1,800 lines of `arm64` symbolic instruction builders) still requires implementing every runtime routine twice:
8	1. Once in `x86_64` (`push rbp`, `mov rdi, ...`, `syscall`), and
9	2. Once in `arm64` (`stp x29, x30, [sp, #-16]!`, `ldr x0, ...`, `svc #0`).
10
11	This architectural study evaluates the next evolutionary step: writing 95%+ of the Ridgun runtime kernel directly in low-level, freestanding Ridgun, leaving only a minimal (~50-line) architecture-specific bootstrap and syscall/atomics intrinsic lowering per CPU target.
12
13	---
14
15	## 2. Why Ordinary Ridgun Cannot Directly Implement the Runtime Kernel
16
17	If a runtime helper such as `rt clone slot` or `rt drop val` were compiled as a normal Ridgun function today, three circularity hazards (`infinite recursion`) would occur:
18
19	1. Frame Prologue / Epilogue Circularity:
20	Normal Ridgun functions allocate a 16-byte `(tag, payload)` slot frame on the heap/arena via Slot 0 (`rt init frame`) and release it via Slot 1 (`rt epilogue`). If `rt init frame` itself were compiled as a normal function, its prologue would call `rt init frame` infinitely.
21	2. RMM1 / RMM2 Recursive Drop Circularity:
22	In normal Ridgun, variable reassignments and scope exits automatically emit calls to Slot 33 (`rt drop val`) or Slot 34 (`rt drop unless`). If `rt drop val` triggered automatic RMM drops on its own local pointer variables, it would recurse infinitely.
23	3. Boxed Value Representation vs Raw 64-Bit Pointers:
24	Normal Ridgun variables hold boxed 16-byte `(tag: i64, payload: i64)` slots. Inside the runtime kernel, routines manipulate raw 64-bit memory addresses, arena bump pointers, Linux `futex` words, and raw `i64` / `u8` memory offsets directly in CPU registers.
25
26	---
27
28	## 3. Minimal Low-Level Primitives Required (`@freestanding` / Unboxed Mode)
29
30	To write the runtime kernel in Ridgun without breaking language purity or introducing C-like syntax, only two compiler mechanisms and six intrinsic operations are required:
31
32	### 3.1 Unboxed Stack-Only Functions (`hardware` or Freestanding Mode)
33	Functions inside the runtime kernel module execute in unboxed register/stack mode:
34	- Local `Int` bindings map directly to 64-bit stack/register slots (`[rbp - 8k]` on `x86_64`, `[x29 - 8k]` on `arm64`) with no call to `rt init frame` or `rt epilogue`.
35	- Automatic RMM1/RMM2 drops are disabled inside freestanding runtime functions (since all values are raw 64-bit words/addresses).
36
37	### 3.2 Six Intrinsic Low-Level Operations (Lowered Directly to 1–3 Instructions by `x86_64` / `arm64`)
38
39	Using Ridgun's natural space-separated syntax and space-separated tuple signatures (`FR-COMP-005`, `FR-COMP-008`), the entire low-level memory and OS interface fits in six intrinsics:
40
41	\| Intrinsic Signature \| Semantics \| `x86_64` Lowering (1–2 insts) \| `arm64` Lowering (1–2 insts) \|
42	\|---\|---\|---\|---\|
43	\| `fn :: ptr load i64 (addr) :: Int -> Int` \| Read 64-bit word at `addr` \| `mov rax, [rdi]` \| `ldr x0, [x0]` \|
44	\| `fn :: ptr store i64 (addr) (val) :: Int Int -> Int` \| Write 64-bit word `val` at `addr` \| `mov [rdi], rsi` \| `str x1, [x0]` \|
45	\| `fn :: ptr load u8 (addr) :: Int -> Int` \| Read zero-extended byte at `addr` \| `movzx eax, byte [rdi]` \| `ldrb w0, [x0]` \|
46	\| `fn :: ptr store u8 (addr) (val) :: Int Int -> Int` \| Write low byte of `val` at `addr` \| `mov [rdi], sil` \| `strb w1, [x0]` \|
47	\| `fn :: atomic add i64 (addr) (delta) :: Int Int -> Int` \| Atomic fetch-and-add (`LOCK XADD` / `LDADDAL`) \| `lock xadd [rdi], rsi` \| `ldaddal x1, x0, [x0]` \|
48	\| `fn :: sys call (nr) (a0) (a1) (a2) (a3) (a4) (a5) :: Int Int Int Int Int Int Int -> Int` \| Raw Linux kernel syscall \| `mov rax, ...; syscall` \| `mov x8, ...; svc #0` \|
49
50	---
51
52	## 4. Side-by-Side Comparison: Symbolic Assembly vs Low-Level Ridgun
53
54	### 4.1 Example 1: Arena Bump Allocator & Frame Initialization (`Slot 0: rt init frame`)
55
56	#### Current Symbolic `x86_64` (`src/main/ridgun/lib/x86_64.rg`)
57	```ridgun
58	fn :: x86 rt slot00 init frame (p) :: Bytes -> Bytes
59	x86 rt slot00 init frame (p) = do
60	c = x86 push rbp (p)
61	c = x86 mov rbp rsp (c)
62	c = x86 push rbx (c)
63	c = x86 push r12 (c)
64	c = x86 mov r12 rdi (c)
65	c = x86 lea rbx rip (c) 0
66	...
67	c
68	```
69
70	#### Proposed Portable Low-Level Ridgun (`src/main/ridgun/lib/runtime kernel.rg`)
71	```ridgun
72	-- Arena state layout at global base:
73	-- offset 0: current bump pointer (Int)
74	-- offset 8: arena limit pointer (Int)
75
76	fn :: rt alloc bytes (arena base) (nbytes) :: Int Int -> Int
77	rt alloc bytes (arena base) (nbytes) = do
78	aligned = ((nbytes + 15) / 16) * 16
79	cur = ptr load i64 (arena base)
80	lim = ptr load i64 (arena base + 8)
81	next = cur + aligned
82	ptr = allocate or grow (arena base) (cur) (next) (lim) (aligned)
83	ptr
84
85	fn :: allocate or grow (arena base) (cur) (next) (lim) (aligned) :: Int Int Int Int Int -> Int
86	allocate or grow (arena base) (cur) (next) (lim) (aligned)
87	\| cur != 0 and next <= lim = do
88	_ = ptr store i64 (arena base) (next)
89	cur
90	\| otherwise = do
91	-- Linux mmap(NULL, 256 MiB, PROT_READ\|PROT_WRITE, MAP_PRIVATE\|MAP_ANONYMOUS, -1, 0)
92	chunk size = 268435456
93	base = sys call (sys mmap nr) 0 (chunk size) 3 34 (0 - 1) 0
94	_ = ptr store i64 (arena base) (base + aligned)
95	_ = ptr store i64 (arena base + 8) (base + chunk size)
96	base
97
98	fn :: rt init frame (arena base) (num slots) :: Int Int -> Int
99	rt init frame (arena base) (num slots) = do
100	nbytes = num slots * 16
101	base = rt alloc bytes (arena base) (nbytes)
102	_ = zero frame slots (base) 0 (num slots)
103	base
104
105	fn :: zero frame slots (base) (idx) (total) :: Int Int Int -> Int
106	zero frame slots (base) (idx) (total)
107	\| idx >= total = 0
108	\| otherwise = do
109	slot addr = base + (idx * 16)
110	_ = ptr store i64 (slot addr) 0
111	_ = ptr store i64 (slot addr + 8) 0
112	zero frame slots (base) (idx + 1) (total)
113	```
114
115	---
116
117	### 4.2 Example 2: RMM2 Reference Counting & Cascaded Drop (`Slots 32..34`)
118
119	In RMM2 (`FR-COMP-002`), heap structures (Lists, Maps, Tensors, ADTs) carry an 8-byte atomic reference count (`rc`) at offset `0` of their header, followed by `len` at offset `8` and elements starting at offset `16`.
120	- Assigning a structure increments `rc` (`+1`).
121	- Dropping a structure decrements `rc` (`-1`), and when `rc` reaches `0`, cascades `rt drop val` to every child element before returning the block to the free-list.
122
123	#### Proposed Portable Low-Level Ridgun (`Slots 32..34`)
124	```ridgun
125	-- Value tags:
126	-- 0 = Nil, 1 = Int, 2 = Float, 3 = Bool, 4 = Char
127	-- 5 = String, 6 = List/Seq, 7 = Map, 8 = ADT, 9 = Tensor
128
129	fn :: is heap counted tag (tag) :: Int -> Bool
130	is heap counted tag (tag) = tag >= 6 and tag <= 9
131
132	-- Slot 32: rt clone slot (RMM2 +1 reference count on assignment)
133	fn :: rt clone slot (dst slot) (src slot) :: Int Int -> Int
134	rt clone slot (dst slot) (src slot) = do
135	tag = ptr load i64 (src slot)
136	payload = ptr load i64 (src slot + 8)
137	_ = bump rc if heap (tag) (payload)
138	_ = ptr store i64 (dst slot) (tag)
139	_ = ptr store i64 (dst slot + 8) (payload)
140	0
141
142	fn :: bump rc if heap (tag) (payload) :: Int Int -> Int
143	bump rc if heap (tag) (payload)
144	\| is heap counted tag (tag) and payload != 0 = atomic add i64 (payload) 1
145	\| otherwise = 0
146
147	-- Slot 33: rt drop val (RMM1/RMM2 deterministic deallocation with child cascade)
148	fn :: rt drop val (slot addr) :: Int -> Int
149	rt drop val (slot addr) = do
150	tag = ptr load i64 (slot addr)
151	payload = ptr load i64 (slot addr + 8)
152	_ = ptr store i64 (slot addr) 0
153	_ = ptr store i64 (slot addr + 8) 0
154	release payload if needed (tag) (payload)
155
156	fn :: release payload if needed (tag) (payload) :: Int Int -> Int
157	release payload if needed (tag) (payload)
158	\| not (is heap counted tag (tag)) or payload == 0 = 0
159	\| otherwise = do
160	prev rc = atomic add i64 (payload) (0 - 1)
161	cascade if last ref (tag) (payload) (prev rc)
162
163	fn :: cascade if last ref (tag) (payload) (prev rc) :: Int Int Int -> Int
164	cascade if last ref (tag) (payload) (prev rc)
165	\| prev rc > 1 = 0
166	\| tag == 6 or tag == 8 = do
167	-- List/Seq (tag 6) or ADT (tag 8): [rc: i64, len: i64, elem_0 (16B), elem_1 (16B), ...]
168	count = ptr load i64 (payload + 8)
169	_ = drop child slots (payload + 16) 0 (count)
170	free heap block (payload)
171	\| otherwise = free heap block (payload)
172
173	fn :: drop child slots (items base) (idx) (count) :: Int Int Int -> Int
174	drop child slots (items base) (idx) (count)
175	\| idx >= count = 0
176	\| otherwise = do
177	_ = rt drop val (items base + (idx * 16))
178	drop child slots (items base) (idx + 1) (count)
179
180	-- Slot 34: rt drop unless (Conditional RMM1 pointer-identity guard: ptr(a) != ptr(c))
181	fn :: rt drop unless (slot a) (slot c) :: Int Int -> Int
182	rt drop unless (slot a) (slot c) = do
183	ptr a = ptr load i64 (slot a + 8)
184	ptr c = ptr load i64 (slot c + 8)
185	drop when distinct (slot a) (ptr a) (ptr c)
186
187	fn :: drop when distinct (slot a) (ptr a) (ptr c) :: Int Int Int -> Int
188	drop when distinct (slot a) (ptr a) (ptr c)
189	\| ptr a == ptr c = 0
190	\| otherwise = rt drop val (slot a)
191	```
192
193	---
194
195	### 4.3 Example 3: String Comparison & UTF-8 String Concatenation (`Slots 14 & 29`)
196
197	```ridgun
198	-- String layout in Ridgun native ABI:
199	-- offset 0: byte length (i64)
200	-- offset 8..8+len-1: UTF-8 bytes
201
202	-- Slot 14: rt str eq
203	fn :: rt str eq (s1) (s2) :: Int Int -> Int
204	rt str eq (s1) (s2)
205	\| s1 == s2 = 1
206	\| s1 == 0 or s2 == 0 = 0
207	\| otherwise = do
208	len1 = ptr load i64 (s1)
209	len2 = ptr load i64 (s2)
210	compare string bytes (s1 + 8) (s2 + 8) (len1) (len2) 0
211
212	fn :: compare string bytes (p1) (p2) (len1) (len2) (idx) :: Int Int Int Int Int -> Int
213	compare string bytes (p1) (p2) (len1) (len2) (idx)
214	\| len1 != len2 = 0
215	\| idx >= len1 = 1
216	\| ptr load u8 (p1 + idx) != ptr load u8 (p2 + idx) = 0
217	\| otherwise = compare string bytes (p1) (p2) (len1) (len2) (idx + 1)
218
219	-- Slot 29: rt str concat
220	fn :: rt str concat (arena base) (s1) (s2) :: Int Int Int -> Int
221	rt str concat (arena base) (s1) (s2) = do
222	len1 = ptr load i64 (s1)
223	len2 = ptr load i64 (s2)
224	total = len1 + len2
225	dst = rt alloc bytes (arena base) (total + 9)
226	_ = ptr store i64 (dst) (total)
227	_ = copy bytes (dst + 8) (s1 + 8) 0 (len1)
228	_ = copy bytes (dst + 8 + len1) (s2 + 8) 0 (len2)
229	_ = ptr store u8 (dst + 8 + total) 0
230	dst
231
232	fn :: copy bytes (dst) (src) (idx) (count) :: Int Int Int Int -> Int
233	copy bytes (dst) (src) (idx) (count)
234	\| idx >= count = 0
235	\| otherwise = do
236	b = ptr load u8 (src + idx)
237	_ = ptr store u8 (dst + idx) (b)
238	copy bytes (dst) (src) (idx + 1) (count)
239	```
240
241	---
242
243	## 5. Architectural Trade-Off Analysis
244
245	\| Dimension \| Current Symbolic Assembly (`x86_64.rg` + `arm64.rg`, `v0.9.11`) \| Portable Low-Level Ridgun Runtime (`runtime kernel.rg`) \|
246	\|---\|---\|---\|
247	\| Zero Hex / 100% Auditable \| Yes (`0` hex blobs; every instruction is a named Ridgun function call) \| Yes (`0` hex blobs; runtime logic is high-level guarded Ridgun functions) \|
248	\| Lines of Target-Specific Code \| ~3,000 lines (`x86_64.rg`) + ~1,800 lines (`arm64.rg`) \| ~150 lines per target (only `_start`, slot jump table, and the 6 intrinsics) \|
249	\| Adding a 3rd Target (e.g., `riscv64`) \| Requires writing ~2,000 lines of `riscv64` runtime slot assembly \| Requires only ~150 lines of `riscv64` codegen for the 6 intrinsics + `_start` \|
250	\| Execution Overhead \| Hand-tuned register usage per slot (0 spill overhead) \| Requires a simple register-allocation or stack-slot pass for freestanding `Int` locals \|
251	\| Compiler Complexity \| Zero new compiler passes; uses existing `Bytes` buffers \| Requires adding a `@freestanding` / unboxed compilation mode in `compiler.rg` \|
252
253	## 6. Recommendation & Staged Roadmap
254
255	1. Short-Term (`v0.9.11` — Completed):
256	`src/main/ridgun/lib/x86_64.rg` and `src/main/ridgun/lib/arm64.rg` are now 100% symbolic, free of hex blobs, formatted with natural spaces, and verified at the 2-stage self-hosting fixed point (`cmp -s target/ridgunc_stage1 target/ridgunc_candidate`).
257	2. Medium-Term (`v0.10.x` Candidate):
258	Introduce an internal unboxed/freestanding compilation mode for `src/main/ridgun/lib/runtime.rg` with the 6 low-level intrinsics (`ptr load i64`, `ptr store i64`, `ptr load u8`, `ptr store u8`, `atomic add i64`, `sys call`), migrating complex data-structure runtime routines (`Slot 37` JSON/TOML/YAML parser, `Slot 40` Einsum, `Slot 55` built-in string/collection helpers, and `PAL` services) into a single architecture-independent Ridgun module shared by `x86_64`, `arm64`, and future targets.