Ridgun
The language itself: a compiler that compiles itself, the stable project tool, the specification and the book
| 1 | # Ridgun Memory Management (RMM): RMM1 (CMM) & RMM2 Architecture (`FR-COMP-002`) |
| 2 | |
| 3 | ## 1. Overview & Policy Hierarchy |
| 4 | |
| 5 | Ridgun manages memory deterministically without a tracing Garbage Collector (GC) through **RMM (Ridgun Memory Management)**, organized into tiered policies according to static control-flow visibility and data nesting: |
| 6 | |
| 7 | | Policy | Name | Scope of Application | Mechanism | |
| 8 | |---|---|---|---| |
| 9 | | **RMM1** | **CMM (Linear + Conditional)** | Statically known control flow over non-nested bindings | **Zero-RC**: Compile-time liveness (`rg_cmm_drop` / `rg_cmm_move`) + 1-cycle conditional pointer-identity guards (`ptr(a) != ptr(c)` via `rg_cmm_drop_unless`). | |
| 10 | | **RMM2** | **Assignment & Cascaded Structure Counting** | Anonymous functions / dynamic higher-order flow, nested containers (`xs = [a..z]`, `xs[3] = a`), and multi-thread sharing | **Assignment-only RC with child cascade**: Scalars uncounted; structures carry `rc` (`+1` on variable/slot assignment, `+0` on read/borrow, move without `-1` on `return`, `-1` on death with cascade `-1` to each child when parent reaches `0`). | |
| 11 | | **RMM3** | **Aggressive RMM** *(Reserved)* | Future aggressive static/region optimization pass | To be specified in a subsequent phase. | |
| 12 | |
| 13 | --- |
| 14 | |
| 15 | ## 2. Policy 1: `RMM1` — Compiled Memory Management (Linear + Conditional CMM) |
| 16 | |
| 17 | When the execution flow and called functions are statically known at compile time: |
| 18 | |
| 19 | 1. **Linear CMM (Unconditional Static Lifetime)**: |
| 20 | For variables whose lifetimes are strictly linear and do not alias other live variables, the compiler determines the exact statement where each variable is used for the last time: |
| 21 | - Intermediate read-only uses borrow the value (`&RVal`) at **0 cost**. |
| 22 | - The final use moves ownership (`rg_cmm_move(&mut lv_x)`) or emits an unconditional deallocation (`rg_cmm_drop(&mut lv_x)`) immediately after the statement. |
| 23 | 2. **Conditional CMM (Pointer-Identity Guards `ptr(a) != ptr(c)`)**: |
| 24 | When a known branching call (`c = choose_list cond a b`) returns one of several input candidates and at least one candidate remains live alongside `c`, the compiler tracks the **Ancestor May-Alias Graph (`RCmmAlias`)** at compile time and emits a pointer-identity guard at each variable's static last-use line (`if ptr(x) != ptr(c) { free(x) }`). |
| 25 | |
| 26 | ### Canonical `choose_list` Trace under `RMM1` |
| 27 | |
| 28 | ```ridgun |
| 29 | fn :: choose_list Bool [Int] [Int] => [Int] |
| 30 | choose_list cond a b = |
| 31 | | cond = a |
| 32 | | otherwise = b |
| 33 | ``` |
| 34 | |
| 35 | In a caller where `b` is never used after `choose_list`, while `a` **continues to be used** after `choose_list` before `c` is finally consumed: |
| 36 | |
| 37 | ```ridgun |
| 38 | a = make_a () -- Allocates heap block M1 |
| 39 | b = make_b () -- Allocates heap block M2 |
| 40 | c = choose_list cond a b -- c aliases {a, b}; b reaches its last use here |
| 41 | -- [RMM1 for b]: if ptr(b) != ptr(c) { free(b) } |
| 42 | print_list a -- a is still live here and reaches its last use here |
| 43 | -- [RMM1 for a]: if ptr(a) != ptr(c) { free(a) } |
| 44 | consume_list c -- c reaches its last use here; no aliases remain live |
| 45 | -- [RMM1 for c]: free(c) (unconditional) |
| 46 | ``` |
| 47 | |
| 48 | - **Branch `cond == True` (`ptr(c) == ptr(a) == M1`, `ptr(b) == M2`)**: |
| 49 | - Right after `c = choose_list True a b`: `ptr(b) != ptr(c)` is **True** $\rightarrow$ **`M2` is freed immediately**. |
| 50 | - Right after `print_list a`: `ptr(a) != ptr(c)` is **False** $\rightarrow$ `M1` is spared. |
| 51 | - Right after `consume_list c`: no live aliases remain $\rightarrow$ **`M1` is freed unconditionally**. |
| 52 | - **Branch `cond == False` (`ptr(c) == ptr(b) == M2`, `ptr(a) == M1`)**: |
| 53 | - Right after `c = choose_list False a b`: `ptr(b) != ptr(c)` is **False** $\rightarrow$ `M2` is spared. |
| 54 | - Right after `print_list a`: `ptr(a) != ptr(c)` is **True** $\rightarrow$ **`M1` is freed immediately**. |
| 55 | - Right after `consume_list c`: no live aliases remain $\rightarrow$ **`M2` is freed unconditionally**. |
| 56 | |
| 57 | --- |
| 58 | |
| 59 | ## 3. Policy 2: `RMM2` — Assignment & Cascaded Structure Counting |
| 60 | |
| 61 | When control flow cannot be fully resolved at compile time (**anonymous functions / closures / dynamic higher-order calls**), when values are stored inside **nested data structures** (`xs = [a, b, ..., z]`, `xs[3] = a`, ADTs, tuples), or across **multi-threaded boundaries**, `RMM2` unifies variable lifetime tracking and nested container ownership under a single set of rules: |
| 62 | |
| 63 | 1. **Primitive Scalars (`Int`, `Real`, `Bool`, `Unit`)**: |
| 64 | - Never heap-allocated and never reference-counted. Passed and copied by value in CPU registers. |
| 65 | 2. **Heap Structures (`List`, `Tuple`, `Adt`, `Tensor`, `Str`)**: |
| 66 | - Every structure instance has its own counter (`rc`). |
| 67 | - In a nested structure `xs = [a, b, ..., z]`, the parent container `xs` has its own counter `rc(xs)`, and each child structure `a, b, ..., z` has its own independent counter `rc(a), rc(b), ..., rc(z)`. |
| 68 | 3. **Incoming Function Arguments (`pats` / `_arg_i`) Are NEVER Touched (`+0 / -0`)**: |
| 69 | - A function never increments (`+0`) its incoming arguments on entry and never decrements (`-0`) them on exit. Their ownership belongs to the caller. |
| 70 | 4. **Internal Local Variables (`x = ...` / `mut x = ...`) Receive `+1` on Assignment**: |
| 71 | - Assigning a structure to a new local variable (`a = make_a ()`, `b = a`) or inserting/assigning it into a container slot (`xs = [a, ...]`, `xs[3] = a`) increments that structure's counter by **`+1`**. |
| 72 | - On mutable variable reassignment (`mut x = a` followed later by `x = b` or `x = choose_list cond x b`), the new value receives **`+1` before** the old value of `x` receives **`-1`** (preventing premature self-destruction on self-referential updates). |
| 73 | 5. **End of Function / Scope Exit (`-1` on Local Variables & Transit Survival)**: |
| 74 | - **Non-returned internal local variables** receive **`-1` first** (in reverse declaration order): |
| 75 | - If `rc(x) > 0`, the structure survives because another live variable or container still holds it. |
| 76 | - If `rc(x) == 0`, the parent block `x` is freed and **iterates over its direct children `a, b, ..., z` one by one**, applying `-1` to each child structure and freeing any child whose `rc` reaches `0` (recursively cascading to its own children). |
| 77 | - **Returned internal local variable (`return a`)**: |
| 78 | - Receives `-1` at the end of the function (or transfers via `rg_cmm_move`), and **even if its `rc` is `0` in transit, it is NOT destroyed** because the caller's assignment (`c = make_pair ()`) immediately applies `+1` (`0 + 1 = 1`). |
| 79 | - **Returned incoming argument (`return a` in `choose_list cond a b`)**: |
| 80 | - Because `a` is an incoming argument, `choose_list` does not touch it (`+0 / -0`, so `rc(a)` remains `1`). When the caller executes `c = choose_list cond a b`, assigning to `c` applies `+1`, leaving `rc(M1) = 1 + 1 = 2` (shared between `a` and `c` in the caller). |
| 81 | |
| 82 | ### Complete Catalog of the 10 `RMM2` Lifecycle Scenarios |
| 83 | |
| 84 | | # | Scenario | Trace & Counter Evolution | Final State | |
| 85 | |---|---|---|---| |
| 86 | | **1** | **Local created and NOT returned** | `a = [1, 2]` (`rc(M1) = 1`) $\rightarrow$ function ends without returning `a`: `a` gets `-1` $\rightarrow$ `rc(M1) = 0` $\rightarrow$ **freed**. | `0` live blocks | |
| 87 | | **2** | **Local created and RETURNED (`c = make_pair ()`)** | Inside `make_pair`: `a = [1, 2]` (`rc(M1) = 1`) $\rightarrow$ returned: `a` gets `-1` (`rc(M1) = 0`, spared in transit) $\rightarrow$ caller `c = make_pair ()` applies `+1` (`rc(M1) = 1`) $\rightarrow$ caller ends: `c` gets `-1` (`rc(M1) = 0`, **freed**). | `0` live blocks | |
| 88 | | **3** | **Local Alias (`b = a`)** | `a = [1, 2]` (`rc(M1) = 1`) $\rightarrow$ `b = a` (`+1` $\rightarrow$ `rc(M1) = 2`) $\rightarrow$ `b` dies (`-1` $\rightarrow$ `rc(M1) = 1`, survives for `a`) $\rightarrow$ `a` dies (`-1` $\rightarrow$ `rc(M1) = 0`, **freed**). | `0` live blocks | |
| 89 | | **4** | **Read-only Borrow (`print_list a`)** | `a = [1, 2]` (`rc(M1) = 1`) $\rightarrow$ `print_list a` (`p` is an incoming argument: `+0 / -0`, `rc(M1)` stays `1`) $\rightarrow$ `a` continues to be used $\rightarrow$ `a` dies (`-1` $\rightarrow$ `rc(M1) = 0`, **freed**). | `0` live blocks | |
| 90 | | **5** | **Branching on Arguments (`c = choose_list cond a b`)** | Caller creates `a` (`M1, rc=1`) and `b` (`M2, rc=1`). Inside `choose_list True a b`: `a` and `b` are incoming arguments (`+0 / -0`). Returns `M1` (`rc=1`). Caller `c = ...` applies `+1` to `M1` (`rc(M1)=2, rc(M2)=1`). `b` dies (`-1` $\rightarrow$ `rc(M2)=0`, **M2 freed**). `a` dies (`-1` $\rightarrow$ `rc(M1)=1`, **M1 survives for `c`**). `c` dies (`-1` $\rightarrow$ `rc(M1)=0`, **M1 freed**). | `0` live blocks | |
| 91 | | **6** | **Nested Container (`xs = [a, b]`)** | `a` (`M1, rc=1`), `b` (`M2, rc=1`). `xs = [a, b]` creates `MX` (`rc=1`) and increments children (`rc(M1)=2, rc(M2)=2`). `a` and `b` die (`-1` $\rightarrow$ `rc(M1)=1, rc(M2)=1`, kept alive by `MX`). `xs` dies (`-1` $\rightarrow$ `rc(MX)=0`, **MX freed**, cascades `-1` to `M1` and `M2` $\rightarrow$ `rc(M1)=0, rc(M2)=0`, **M1 & M2 freed**). | `0` live blocks | |
| 92 | | **7** | **Container Created Inside Function & Returned** | Inside `make_nested_list`: `a` (`M1, rc=1`), `b` (`M2, rc=1`), `xs = [a, b]` (`rc(MX)=1, rc(M1)=2, rc(M2)=2`). At function exit: non-returned locals `a, b` get `-1` (`rc(M1)=1, rc(M2)=1`); returned `xs` gets `-1` (`rc(MX)=0` in transit, spared); caller `c = make_nested_list ()` applies `+1` (`rc(MX)=1`). When `c` dies: `MX` reaches `0` and cascades `-1` to `M1, M2` (**all freed**). | `0` live blocks | |
| 93 | | **8** | **Extracting Child Before Container Dies (`res = xs[0]`)** | `xs` (`MX, rc=1`) holds `M1` (`rc=1`) and `M2` (`rc=1`). `res = xs[0]` applies `+1` to `M1` (`rc(M1)=2`). Non-returned `xs` gets `-1` **before** returned `res`: `MX` reaches `0` and cascades `-1` to `M1` (`2-1=1`, **survives!**) and `M2` (`1-1=0`, **M2 freed**). Returned `res` transfers `M1` to caller (`rc(M1)=1`). | `0` live blocks | |
| 94 | | **9** | **Slot Overwrite (`xs[0] = c`)** | `xs[0]` initially holds `M1` (`rc=1`). Executing `xs[0] = c` (`M3, rc=1`) applies `+1` to `M3` (`rc(M3)=2`) and `-1` to old slot value `M1` (`rc(M1)=0`, **M1 freed immediately**). | `0` live blocks | |
| 95 | | **10** | **Mutable Variable Reassignment (`mut x = a` then `x = b`)** | `mut x = a` (`rc(M1)=1`). Later `x = b` (`M2`): applies `+1` to new value `M2` **before** applying `-1` to old value `M1` (`rc(M1)=0`, **M1 freed immediately**, safe even when `x = x[0]` or `x = choose_list cond x b`). | `0` live blocks | |
| 96 | |
| 97 | --- |
| 98 | |
| 99 | ## 4. Compiler & Runtime Implementation (`compiler.rg`) |
| 100 | |
| 101 | - **Compile-Time Liveness & Ancestor Alias Pass (`RCmmAlias`)**: |
| 102 | - `cmm_expr_vars`, `cmm_stmts_vars`, and `cmm_where_vars` compute exact per-statement liveness for every local variable in `EBlock`, `EWhere`, and `FnCase` bodies. |
| 103 | - `cmm_register_let` and `cmm_find_live_peers` compute the ancestor intersection set $A(x) \cap A(y) \neq \emptyset$ for live variables. |
| 104 | - `emit_cmm_drops` emits `rg_cmm_drop(&mut lv_x)` when `LivePeers(x) == []` and `rg_cmm_drop_unless(&mut lv_x, &[&lv_c, ...])` when `LivePeers(x)` is non-empty. |
| 105 | - **Runtime Diagnostics & Inspection Built-ins**: |
| 106 | - `cmm_live_blocks : Int` — current number of live tracked heap structure allocations. |
| 107 | - `cmm_cond_freed : Int` — cumulative count of conditional guards where `ptr(v) != ptr(keep)` freed the unchosen branch immediately. |
| 108 | - `cmm_cond_spared : Int` — cumulative count of conditional guards where `ptr(v) == ptr(keep)` spared the aliased block. |
| 109 | - `cmm_same_ptr : A A => Bool` — returns `True` iff two values point to the exact same heap structure allocation. |