Ridgun
The language itself: a compiler that compiles itself, the stable project tool, the specification and the book
| 1 | # Kapitel 08: Tensorer, kompilerat RMM-minne (`RMM1`/`RMM2`), regioner och system |
| 2 | |
| 3 | Hittills har vi sett den mest vänliga, eleganta och matematiska sidan av Ridgun: rena funktioner, algebraiska datatyper, mönstermatchning, beslutsträd med `|` / `|.` och parallella `||`-grafer med `->` som utnyttjar alla kärnor i din processor utan att kräva ett enda ynka `Mutex`. |
| 4 | |
| 5 | Vid det här laget brukar den erfarna systemprogrammeraren längst bak i salen räcka upp handen med ett snett leende och fråga: |
| 6 | |
| 7 | > *"Allt det här är jättefint för att räkna på fakturor eller kompilera AST-träd, men vad händer när jag behöver multiplicera matriser med miljontals flyttal i svindlande fart? Vad händer med minnet? Ligger det en skräpsamlare (Garbage Collector) gömd under mattan och väntar på sämsta tänkbara ögonblick för att frysa mitt program i 200 millisekunder? Och hur pratar jag med operativsystemet Unix på riktigt?"* |
| 8 | |
| 9 | Utmärkta frågor. Låt oss lyfta på motorhuven till Ridgun och se hur det beter sig när det är dags att kavla upp ärmarna i systemprogrammering, numeriska beräkningar och deterministiskt minne. |
| 10 | |
| 11 | --- |
| 12 | |
| 13 | ## 8.1. Minnesdilemmat: varken Garbage Collector eller bråk med Borrow Checker (`RMM1` och `RMM2`) |
| 14 | |
| 15 | I de moderna språkens värld brukar det finnas två oförenliga läger: |
| 16 | |
| 17 | 1. **Garbage Collector-lägret (Java, Go, Python, JS, Haskell, OCaml):** du begär glatt mer minne och då och då stannar en osynlig sopbil all trafik i ditt program för att spåra vilka objekt som fortfarande lever och vilka som är döda. Det är hur bekvämt som helst... ända tills du bygger ett blixtsnabbt systemverktyg eller en server med strikta svarstider och sopbilen bestämmer sig för att dubbelparkera. |
| 18 | 2. **Manuell kontroll / Borrow Checker-lägret (C, C++, Rust):** det finns ingen skräpsamlare, men i gengäld måste du hantera pekare för hand (med risk för `Segmentation fault` eller *use-after-free*) eller ägna en halv eftermiddag åt att förhandla med *borrow checker* om varför `'a` inte lever lika länge som `'b`. |
| 19 | |
| 20 | Ridgun löser detta dilemma från grunden med **Ridgun Memory Management (`RMM`)**, ett deterministiskt system med två kompletterande policyer (**`RMM1`** och **`RMM2`**) kombinerat med **lexikala regioner (`with region`)**: |
| 21 | |
| 22 | ### Policy `RMM1` — Kompilerad minneshantering (Linjär och villkorlig CMM) |
| 23 | När kompilatorn statiskt känner till flödet av lokala variabler inuti en funktion: |
| 24 | - **Linjär CMM**: `ridgunc` beräknar vid kompileringstillfället vilken som är den **sista raden** där varje lokal variabel (`a`, `b`, ...) läses och skjuter direkt efter den in dess deterministiska frigörning (`rg_cmm_drop`), eller överför ägarskapet utan kopiering (`rg_cmm_move`) när variabeln returneras som resultat. |
| 25 | - **Villkorlig CMM (`ptr(a) != ptr(c)`)**: men vad händer om en funktion som `valj cond a b` returnerar `a` eller `b` beroende på ett villkor vid körning? Då bygger `ridgunc` upp härkomsttabellen och genererar en pekaridentitetsvakt på **1 CPU-cykel**: om `b` slutar användas medan `c` fortfarande lever, kontrollerar den `if ptr(b) != ptr(c) { free(b) }`. Den gren som inte valdes frigörs omedelbart och den valda överlever intakt. |
| 26 | |
| 27 | ### Policy `RMM2` — Tilldelningsräkning och strukturell kaskad |
| 28 | Och vad händer när du stoppar in strukturer i andra strukturer (`xs = [a, b]`), tilldelar om muterbara variabler (`mut x = ...`) eller kedjar ihop komplexa anrop? Där kliver **`RMM2`** in och styr hela livscykeln med fyra vattentäta matematiska regler: |
| 29 | |
| 30 | 1. **Inkommande funktionsargument rörs inte (`+0` vid inträde, `-0` vid utträde)**: att skicka en lista eller en post till en funktion ökar eller minskar aldrig några räknare i onödan. |
| 31 | 2. **Varje tilldelning till en intern lokal variabel eller behållarcell lägger till `+1`**: |
| 32 | - `a = [10, 20]` $\rightarrow$ blocket `M1` föds med räknaren `1`. |
| 33 | - `xs = [a, b]` $\rightarrow$ listan `xs` föds med `1`, och eftersom den sparar referenser till `a` och `b` stiger båda till `2`. |
| 34 | - Om du tilldelar om en muterbar variabel (`mut x = ...` och sedan `x = ny`), lägger `RMM2` först på **`+1`** på det nya värdet innan den drar av **`-1`** från det gamla. |
| 35 | 3. **När funktionen avslutas får lokala variabler som INTE returneras `-1`**: om en strukturs räknare når `0` frigörs dess minne på fläcken och **sprider `-1` i kaskad, ett i taget, till vart och ett av dess direkta barn**. |
| 36 | 4. **Värdet som returneras av funktionen undantas under transporten**: det får sitt `-1` som lokal variabel men förstörs inte när det passerar `return`, så att när anroparen skriver `c = min funktion ()`, lämnar tilldelningens `+1` räknaren på exakt `1`. |
| 37 | |
| 38 | ```ridgun |
| 39 | valj Bool [Int] [Int] => [Int] |
| 40 | valj cond a b = |
| 41 | | cond = a |
| 42 | | otherwise = b |
| 43 | |
| 44 | exempel rmm2 Bool => Int |
| 45 | exempel rmm2 cond = |
| 46 | a = [10, 20, 30] -- M1 (rc = 1) |
| 47 | b = [40, 50, 60] -- M2 (rc = 1) |
| 48 | c = valj cond a b -- `c` får +1; den som inte valdes dör precis här (rc -> 0) |
| 49 | (rakna a) + (rakna c) -- Vid slutet får `a` och `c` -1 och 0 levande block återstår |
| 50 | ``` |
| 51 | |
| 52 | --- |
| 53 | |
| 54 | ## 8.2. Lexikala regioner med kvot (`with region`): Minnesbrandväggar i $O(1)$ |
| 55 | |
| 56 | Utöver `RMM1` och `RMM2` kan du, när du bearbetar ett externt nätverkspaket, en enorm fil eller ett parti opålitliga data och vill sätta ett **strikt tak för RAM-minnet**, kapsla in beräkningen i ett **`with region`**-block: |
| 57 | |
| 58 | ```ridgun |
| 59 | bearbeta ram String => Result |
| 60 | bearbeta ram radata = |
| 61 | with region 64_KB do |
| 62 | rena = map rensa rad (dela rader radata) |
| 63 | rakna giltiga rena |
| 64 | ``` |
| 65 | |
| 66 | 1. **Garanterad kvot i hårdvara/körtidsmiljö**: om något inuti blocket försöker reservera ens en enda byte över `64_KB` (`65 536` byte) avbryter körtidsmiljön blocket snyggt, frigör hela den tillfälliga arenan på konstant tid $O(1)$ och returnerar `Err OutOfMemory` utan att krascha processen. |
| 67 | 2. **Omedelbar frigörning vid utträde**: så fort `with region`-blocket avslutas försvinner allt tillfälligt minne i arenan i ett enda slag utan att lämna någon fragmentering. |
| 68 | |
| 69 | --- |
| 70 | |
| 71 | ## 8.3. Inbyggda tensorer, Einsteinkontraktion (`@`) och symboliska dimensioner |
| 72 | |
| 73 | Om du någonsin har programmerat i Python med NumPy eller PyTorch har du garanterat råkat ut för det klassiska felet efter 41 minuters körning: |
| 74 | |
| 75 | ```text |
| 76 | RuntimeError: mat1 and mat2 shapes cannot be multiplied (128x64 and 32x128) |
| 77 | ``` |
| 78 | |
| 79 | I Ridgun är **`Tensor`** förstklassiga inbyggda medborgare och deras dimensioner är en del av typsignaturen: |
| 80 | |
| 81 | ```ridgun |
| 82 | -- Om (N × K) och (K × M) går in, måste det ovillkorligen komma ut (N × M)! |
| 83 | multiplicera matriser Tensor[N, K] Tensor[K, M] => Tensor[N, M] |
| 84 | multiplicera matriser a b = a_ik @ b_kj |
| 85 | ``` |
| 86 | |
| 87 | Lägg märke till två spektakulära detaljer: |
| 88 | 1. **Statisk dimensionsverifiering (`Tensor[N, K]`)**: den inre axeln `K` i den första matrisen måste stämma överens med den första axeln `K` i den andra. Om du försöker skicka in inkompatibla dimensioner stoppar `ridgunc check` dig innan något ens körs. |
| 89 | 2. **Einsteins indexnotation (`a_ik @ b_kj`) och Hadamard (`a_ij * b_j`)**: |
| 90 | - Med **`@`** kontraheras (summeras) de index som upprepas i alla operander (`k`), medan de unika (`i`, `j`) överlever i resultattensorn. |
| 91 | - Med **`+`, `-`, `*`, `/`** justerar indexen dimensionerna och utför automatisk *broadcasting* (`a_ij * b_j` multiplicerar varje rad `i` i `a` med vektorn `b_j` utan att du behöver skriva `unsqueeze` eller `reshape`). |
| 92 | 3. **Högpresterande typade tensorer (`Tensor[U64 * N]`) och mutering *in-place* med `t_(i, j)`**: |
| 93 | I kryptografiska system, fysiksimuleringar eller linjär algebra kan du deklarera platta tensorer över ett sammanhängande block av teckenlösa 64-bitars heltal (`Tensor[U64 * 4]`, `Tensor[U64 * 8 * 16]`), operera parallellt med `^` (inbyggd block-XOR) och läsa eller skriva element på $O(1)$-tid med den uttryckliga indexsyntaxen `t_(i)` eller `t_(i, j)`: |
| 94 | ```ridgun |
| 95 | skapa tillstandsblock => Tensor[U64 * 2 * 2] |
| 96 | skapa tillstandsblock = |
| 97 | mut m = tensor fill [2, 2] (u64 0) |
| 98 | m_(0, 1) = u64 0x6a09e667f3bcc908 |
| 99 | m |
| 100 | ``` |
| 101 | |
| 102 | --- |
| 103 | |
| 104 | ## 8.4. Hårdvaruåtkomst (`hardware ::`) och POSIX-systemprimitiver |
| 105 | |
| 106 | Själva kompilatorn `ridgunc`, bygghanteraren `stable` och Unix-systemverktyg är skrivna i Ridgun. För detta innehåller språket minnesmappade registerblock (`hardware ::`) och direkta POSIX-primitiver: |
| 107 | |
| 108 | ```ridgun |
| 109 | hardware :: UART0 @ 0x1000_0000 |
| 110 | tx_data : Int @ 0x00 |
| 111 | status : Int @ 0x04 |
| 112 | ``` |
| 113 | |
| 114 | Och för att arbeta med operativsystemet: |
| 115 | |
| 116 | | Primitiv | Signatur | Vad den gör | |
| 117 | |---|---|---| |
| 118 | | `cli args` | `=> [String]` | Kommandoradsargument (`argv`). | |
| 119 | | `read file` / `write file` | `String => String` / `String String => ()` | Läsning och skrivning av hela filer på disk. | |
| 120 | | `read bytes` / `write bytes` | `String => [Int]` / `String [Int] => ()` | Exakt binär läsning och skrivning byte för byte (`0..255`). | |
| 121 | | `list dir` / `file lstat` | `String => [String]` / `String => ...` | Listning av kataloger och inspektion av POSIX-metadata (`lstat`). | |
| 122 | | `sha256 file` / `sha256 str` / `sha256 raw` | `String => String` | Inbyggd kryptografisk SHA-256-hash (64 tecken hexadecimalt eller rått 32-bytes binärt sammandrag med `sha256 raw` / `sha256 bytes`). | |
| 123 | | `sys exec` / `shell exec` | `... => Int` | Körning av operativsystemprocesser. | |
| 124 | | `sys getcwd` / `sys chdir` | `=> String` / `String => Int` | Fråga efter eller byt aktuell arbetskatalog. | |
| 125 | | `sys getenv` / `sys setenv` | `String => String` / `String String => Int` | Processens miljövariabler. | |
| 126 | | `sys getuid` / `sys getgid` | `=> Int` | Processens faktiska UID och GID (`doas`, säkerhetsverktyg). | |
| 127 | | `sys exit` | `Int => ()` | Avsluta processen med returkod. | |
| 128 | |
| 129 | --- |
| 130 | |
| 131 | ## 8.5. Ekosystemet av standardbibliotek (`ridgun-libs`) |
| 132 | |
| 133 | Utöver kompilatorns primitiver innehåller Ridguns officiella ekosystem **32 rena bibliotek (`.rglib`)** skrivna helt i Ridgun som du kan importera med `import <namn>` i vilket projekt som helst: |
| 134 | |
| 135 | | Kategori | Tillgängliga bibliotek | Vad de tillhandahåller | |
| 136 | |---|---|---| |
| 137 | | **Samlingar, text och data** | `collections`, `set`, `string`, `regex`, `utf8`, `fmt`, `csv`, `json`, `toml`, `yaml`, `xml`, `html`, `markdown`, `base64`, `hex`, `compress`, `sql` | Avbildningar, mängder, reguljära uttryck, strukturerade tolkar/serialiserare, kodning och frågemotorer. | |
| 138 | | **Matematik, tid och slumptal** | `math`, `random`, `datetime`, `uuid`, `log`, `cli`, `bench`, `test` | Matematiska funktioner, deterministisk och systembaserad PRNG, ISO-8601-datum, UUID, testramverk och prestandamätningar med `clock_gettime`. | |
| 139 | | **System, nätverk och webb** | `fs`, `path`, `process`, `env`, `net`, `http`, `uri` | Högnivåfilsystem, sökvägshantering, underprocesser, TCP/UDP-uttag samt HTTP-klient och -server. | |
| 140 | | **Kryptografi och säkerhet (`crypto`)** | `crypto` (`sha256`, `hmac`, `hkdf`, `pbkdf2`, `argon2id`, `chacha20`, `aes`, `x25519`, `ed25519`, `csprng`) | Kryptografisk svit verifierad mot officiella RFC/NIST-vektorer, implementerad över `U64`, `Tensor[U64 * ...]` och `sha256 raw` med tupel-inlining utan heap-allokeringar. | |
| 141 | |
| 142 | --- |
| 143 | |
| 144 | ## 8.6. Verklig fallstudie: Vi bygger `rg-wc`, ett parallellt Unix-verktyg |
| 145 | |
| 146 | Låt oss knyta ihop allt vi har lärt oss från Kapitel 01 fram till hit i ett riktigt systemprogram: en parallell version av Unix-verktyget `wc` (rad- och byteräknare för flera filer) skriven i ren Ridgun: |
| 147 | |
| 148 | ```ridgun |
| 149 | -- 1. Vi modellerar mätvärdena för en fil med en ADT-post (Kapitel 06) |
| 150 | type Matvarden = fil: String, rader: Int, bytes: Int |
| 151 | |
| 152 | -- 2. Vi räknar radbrytningar (ASCII-kod 10) med TCO-svansrekursion (Kapitel 04) |
| 153 | fn :: rakna radbrytningar String Int Int Int => Int |
| 154 | rakna radbrytningar text pos slut ack = |
| 155 | | pos >= slut = ack |
| 156 | | (str char at text pos) == 10 = rakna radbrytningar text (pos + 1) slut (ack + 1) |
| 157 | | otherwise = rakna radbrytningar text (pos + 1) slut ack |
| 158 | |
| 159 | fn :: antal rader String => Int |
| 160 | antal rader text = rakna radbrytningar text 0 (str len text) 0 |
| 161 | |
| 162 | -- 3. Vi analyserar en fil och returnerar dess Matvarden-struktur |
| 163 | fn :: analysera fil String => Matvarden |
| 164 | analysera fil sokvag = |
| 165 | innehall = read file sokvag |
| 166 | || antal rader innehall -> n_rader |
| 167 | || str len innehall -> n_bytes ||. |
| 168 | Matvarden sokvag n_rader n_bytes |
| 169 | |
| 170 | -- 4. Vi formaterar varje rad och summerar totaler med `fold` och `||` (Kapitel 07) |
| 171 | fn :: formatera matvarde Matvarden => String |
| 172 | formatera matvarde m = "{rader m}\t{bytes m}\t{fil m}" |
| 173 | |
| 174 | fn :: summera rader Int Matvarden => Int |
| 175 | summera rader acc m = acc + (rader m) |
| 176 | |
| 177 | fn :: summera bytes Int Matvarden => Int |
| 178 | summera bytes acc m = acc + (bytes m) |
| 179 | |
| 180 | fn :: generera rapport [String] => String |
| 181 | generera rapport sokvagar = |
| 182 | matvarden = ||map analysera fil sokvagar |
| 183 | || map formatera matvarde matvarden -> rader_ut |
| 184 | || fold summera rader 0 matvarden -> total_r |
| 185 | || fold summera bytes 0 matvarden -> total_b ||. |
| 186 | "{rader_ut}\nTotalt: {total_r} rader, {total_b} byte" |
| 187 | |
| 188 | fn :: main => () |
| 189 | main = |
| 190 | echo (generera rapport ["README.md", "AGENTS.md"]) |
| 191 | ``` |
| 192 | |
| 193 | Stanna upp en sekund och titta på dessa ~40 rader kod: |
| 194 | - Det finns inte ett enda `null`, inget okontrollerat undantag och inget `Mutex`. |
| 195 | - `rakna radbrytningar` kompileras till en inbyggd `loop` med 0 byte stackminne tack vare automatisk TCO. |
| 196 | - `||map analysera fil sokvagar` bearbetar filerna parallellt på alla kärnor i din processor, och `||`-blocket beräknar samtidigt de formaterade raderna, totalt antal rader och totalt antal byte. |
| 197 | - Det tillfälliga minnet frigörs deterministiskt via **`RMM1`/`RMM2`**. |
| 198 | - Och när du kör `ridgunc build rg_wc.rg -o rg-wc` får du en fristående inbyggd binär på ~350 KB, färdig att kopieras till `/usr/local/bin`. |
| 199 | |
| 200 | --- |
| 201 | |
| 202 | ## 8.7. Slutlig färdplan: Ridgun-programmerarens 10 gyllene regler |
| 203 | |
| 204 | 1. **Skriv alltid kontraktet (`=>`) först och ekvationerna (`=`) sedan:** att tänka på typerna först får kompilatorn att arbeta åt dig. |
| 205 | 2. **Låt `stable format` formge dina tabeller:** skriv med ett mellanslag och låt verktyget rada upp kolumner, `=>`, `=` och `->`. |
| 206 | 3. **Kom ihåg den universella regeln för `=`:** efter vilket `=` som helst kan du öppna ett sekventiellt block, ett vaktträd `|` eller en parallell graf `||`. |
| 207 | 4. **Använd `|.` och `||.` endast när du stänger ett nästlat block för att återvända till en högre nivå:** håll djupa beslutsträd kompakta och entydiga. |
| 208 | 5. **Oföränderligt som standard (`x = ...`), uttryckligt föränderligt (`mut x = ...`):** använd `mut` endast när en lokal ackumulator verkligen kräver det. |
| 209 | 6. **Använd tydliga booleska operatorer i gemener (`and`, `or`, `xor`, `not`) och avsluta alltid dina vakter med `| otherwise =`.** |
| 210 | 7. **Modellera din domän med ADT (`type`):** använd poster med `with falt: varde` och summatyper (`Option`, `Result`) i stället för `null`. |
| 211 | 8. **Parallellisera genom att deklarera beroenden med `|| expr -> var` samt `||map` / `||filter`:** låt kompilatorn verifiera att det inte finns några cykler och fördela arbetet mellan kärnorna. |
| 212 | 9. **Sätt symboliska dimensioner på dina tensorer (`Tensor[N, K]`) och index på dina kontraktioner (`a_ik @ b_kj`).** |
| 213 | 10. **Lita på `RMM` (`RMM1`/`RMM2`), avgränsa extern indata med `with region` och verifiera alltid med `stable check` och `stable test`.** |
| 214 | |
| 215 | Lycka till på resan med att programmera i Ridgun! |