nx_evo_loop.nx source

1// nx_evo_loop.nx -- EVOLUTIONARY SYNTHESIS rung: LOOP GENOMES from examples 2// (X-AUT-006P) -- discover ITERATIVE algorithms (factorial, 2^n, sum) from data. 3// 4// 006O evolved BRANCHES (abs/relu). This evolves LOOPS: the genome = an evolved 5// acc INIT + a loop BODY that runs `for i in 1..x` (x = the input), the body ops 6// referencing the counter i, the input x, and constants -- so the search can 7// discover ITERATIVE algorithms that are not closed-form polynomials (factorial, 8// 2^n). A runaway GUARD caps iterations. Evolved under example fitness + held-out. 9// 10// nx_evo_loop <champion_basename> <target_id> <seed> target: 0=n! 1=sum 2=2^n 11// genome = INIT gene + EVO_BODY body ops; body op: 0 acc+i,1 acc*i,2 acc+x, 12// 3 acc+n,4 acc*n,5 acc-i,6 nop. train n=1..6, held-out n=7..10. 13// -> champion materialized as a REAL `var acc=INIT; var i=1; while i<=x { body; i+=1 }`. 14// 15// no-false-green: factorial/2^n are non-polynomial -> need the loop; champion 16// verified on HELD-OUT (n the search never trained on) + compiles+runs the loop. 17// Sovereign, no gcc/.sh. HONEST: one fixed `for i=1..x` loop, small body, integer 18// fitness; nested/while-with-condition loops + 2-input (gcd) are later rungs. 19// license_tier: ORIGINAL 20import "nx_syscalls.nx" 21const EVO_MAGIC_2862933555777941757: i64 = 2862933555777941757 22const EVO_MAGIC_3037000493: i64 = 3037000493 23const EVO_MAGIC_2654435761: i64 = 2654435761 24const EVO_MAGIC_12345: i64 = 12345 25const EVO_MAGIC_1000000000: i64 = 1000000000 26const EVO_MAGIC_65536: i64 = 65536 27 28const EVO_BODY: i64 = 3 29const EVO_P: i64 = 256 30const EVO_G: i64 = 1500 31const EVO_T: i64 = 5 32const NTRAIN: i64 = 6 33const NHELD: i64 = 4 34const LOOP_CAP: i64 = 64 // runaway guard (examples use x<=10) 35 36func lp_rand(state: *i64) -> i64 { state[0] = state[0] * EVO_MAGIC_2862933555777941757 + EVO_MAGIC_3037000493; return (state[0] >> 17) & 0x3fffffff } 37func lp_abs(x: i64) -> i64 { if x < 0 { return 0 - x } return x } 38func lp_trainx(i: i64) -> i64 { return i + 1 } // n = 1..6 39func lp_heldx(i: i64) -> i64 { return NTRAIN + 1 + i } // n = 7..10 40func lp_target(id: i64, n: i64) -> i64 { 41 if id == 0 { var f: i64 = 1; var k: i64 = 1; while k <= n { f = f * k; k = k + 1 } return f } // n! 42 if id == 1 { return n * (n + 1) / 2 } // sum 1..n 43 if id == 2 { var p: i64 = 1; var k: i64 = 0; while k < n { p = p * 2; k = k + 1 } return p } // 2^n 44 return 0 45} 46// glen = 1 (INIT) + EVO_BODY*2 ; eval the loop genome as f(x). 47func lp_eval(pop: *i64, base: i64, x: i64) -> i64 { 48 var acc: i64 = pop[base + 0] // INIT gene 49 var i: i64 = 1 50 var guard: i64 = 0 51 while i <= x { 52 if guard >= LOOP_CAP { i = x + 1 } else { 53 var j: i64 = 0 54 while j < EVO_BODY { 55 let op: i64 = pop[base + 1 + j*2]; let n: i64 = pop[base + 1 + j*2 + 1] 56 if op == 0 { acc = acc + i } 57 if op == 1 { acc = acc * i } 58 if op == 2 { acc = acc + x } 59 if op == 3 { acc = acc + n } 60 if op == 4 { acc = acc * n } 61 if op == 5 { acc = acc - i } 62 // op == 6 nop 63 j = j + 1 64 } 65 i = i + 1 66 guard = guard + 1 67 } 68 } 69 return acc 70} 71func lp_fit(pop: *i64, base: i64, id: i64) -> i64 { 72 var err: i64 = 0; var i: i64 = 0 73 while i < NTRAIN { let x: i64 = lp_trainx(i); err = err + lp_abs(lp_eval(pop, base, x) - lp_target(id, x)); i = i + 1 } 74 return err 75} 76func lp_randfill(pop: *i64, base: i64, state: *i64) -> i64 { 77 pop[base + 0] = lp_rand(state) % 10 // INIT 0..9 78 var j: i64 = 0 79 while j < EVO_BODY { pop[base + 1 + j*2] = lp_rand(state) % 7; pop[base + 1 + j*2 + 1] = (lp_rand(state) % 9) + 1; j = j + 1 } 80 return 0 81} 82func lp_tourney(fit: *i64, state: *i64) -> i64 { 83 var bi: i64 = lp_rand(state) % EVO_P; var bd: i64 = fit[bi]; var k: i64 = 1 84 while k < EVO_T { let i: i64 = lp_rand(state) % EVO_P; if fit[i] < bd { bd = fit[i]; bi = i } k = k + 1 } 85 return bi 86} 87func lp_cat(dst: *u8, off: i64, s: *u8) -> i64 { var i: i64 = 0; while s[i] != (0 as u8) { dst[off+i] = s[i]; i = i + 1 } return off + i } 88func lp_catn(dst: *u8, off: i64, v: i64) -> i64 { 89 var o: i64 = off 90 if v < 0 { dst[o] = 45 as u8; o = o + 1; return lp_catn(dst, o, 0 - v) } 91 if v == 0 { dst[o] = 48 as u8; return o + 1 } 92 var m: i64 = v; let t: *u8 = sys_mmap(28); var k: i64 = 0 93 while m > 0 { t[k] = (48 + (m % 10)) as u8; m = m / 10; k = k + 1 } 94 var i: i64 = 0 95 while i < k { dst[o+i] = t[k-1-i]; i = i + 1 } 96 return o + k 97} 98func lp_p(s: *u8) -> i64 { var n: i64 = 0; while s[n] != (0 as u8) { n = n + 1 } sys_write(1, s, n); return 0 } 99func lp_pn(v: i64) -> i64 { let b: *u8 = sys_mmap(32); let n: i64 = lp_catn(b, 0, v); sys_write(1, b, n); return 0 } 100func lp_atoi(s: *u8) -> i64 { 101 var n: i64 = 0; var i: i64 = 0; var neg: i64 = 0 102 if s[0] == (45 as u8) { neg = 1; i = 1 } 103 while s[i] != (0 as u8) { if s[i] >= (48 as u8) { if s[i] <= (57 as u8) { n = n * 10 + ((s[i] as i64) - 48) } } i = i + 1 } 104 if neg == 1 { return 0 - n } 105 return n 106} 107func lp_emit_body_op(buf: *u8, off: i64, op: i64, n: i64) -> i64 { 108 var o: i64 = off 109 if op == 6 { return o } // nop -> emit nothing 110 o = lp_cat(buf, o, " " as *u8) 111 if op == 0 { o = lp_cat(buf, o, "acc = acc + i" as *u8) } 112 else { if op == 1 { o = lp_cat(buf, o, "acc = acc * i" as *u8) } 113 else { if op == 2 { o = lp_cat(buf, o, "acc = acc + x" as *u8) } 114 else { if op == 3 { o = lp_cat(buf, o, "acc = acc + " as *u8); o = lp_catn(buf, o, n) } 115 else { if op == 4 { o = lp_cat(buf, o, "acc = acc * " as *u8); o = lp_catn(buf, o, n) } 116 else { o = lp_cat(buf, o, "acc = acc - i" as *u8) } } } } } // op 5 117 o = lp_cat(buf, o, "\n" as *u8) 118 return o 119} 120 121func main(argc: i64, argv: *i64) -> i64 { 122 if argc < 4 { lp_p("usage: nx_evo_loop <champion_basename> <target_id 0=n! 1=sum 2=2^n> <seed>\n" as *u8); return 2 } 123 let base_name: *u8 = argv[1] as *u8 124 let id: i64 = lp_atoi(argv[2] as *u8) 125 let seed: i64 = lp_atoi(argv[3] as *u8) 126 127 let state: *i64 = sys_mmap(8) as *i64; state[0] = seed * EVO_MAGIC_2654435761 + EVO_MAGIC_12345 128 let glen: i64 = 1 + EVO_BODY * 2 129 let pop: *i64 = sys_mmap(EVO_P * glen * 8) as *i64 130 let nxt: *i64 = sys_mmap(EVO_P * glen * 8) as *i64 131 let fit: *i64 = sys_mmap(EVO_P * 8) as *i64 132 let best: *i64 = sys_mmap(glen * 8) as *i64 133 134 var p: i64 = 0 135 while p < EVO_P { lp_randfill(pop, p * glen, state); p = p + 1 } 136 137 var best_err: i64 = EVO_MAGIC_1000000000; var best_gen: i64 = 0 - 1; var found: i64 = 0 138 var g: i64 = 0 139 while g < EVO_G { 140 var gbest: i64 = EVO_MAGIC_1000000000; var gbp: i64 = 0 141 p = 0 142 while p < EVO_P { let e: i64 = lp_fit(pop, p * glen, id); fit[p] = e; if e < gbest { gbest = e; gbp = p } p = p + 1 } 143 if gbest < best_err { best_err = gbest; var j: i64 = 0; while j < glen { best[j] = pop[gbp * glen + j]; j = j + 1 } best_gen = g } 144 if best_err == 0 { found = 1; g = EVO_G } else { 145 var j2: i64 = 0 146 while j2 < glen { nxt[j2] = best[j2]; j2 = j2 + 1 } 147 p = 1 148 while p < EVO_P { 149 let pa: i64 = lp_tourney(fit, state) * glen 150 let pb: i64 = lp_tourney(fit, state) * glen 151 let cut: i64 = (lp_rand(state) % (glen - 1)) + 1 152 var jj: i64 = 0 153 while jj < glen { if jj < cut { nxt[p*glen + jj] = pop[pa + jj] } else { nxt[p*glen + jj] = pop[pb + jj] } jj = jj + 1 } 154 // mutate: sometimes the INIT gene, else a body op/operand 155 if (lp_rand(state) % 4) == 0 { nxt[p*glen + 0] = lp_rand(state) % 10 } else { 156 let bj: i64 = lp_rand(state) % EVO_BODY 157 if (lp_rand(state) % 2) == 0 { nxt[p*glen + 1 + bj*2] = lp_rand(state) % 7 } else { nxt[p*glen + 1 + bj*2 + 1] = (lp_rand(state) % 9) + 1 } 158 } 159 p = p + 1 160 } 161 var c: i64 = 0 162 while c < EVO_P * glen { pop[c] = nxt[c]; c = c + 1 } 163 g = g + 1 164 } 165 } 166 167 var held_ok: i64 = 0; var hi: i64 = 0 168 while hi < NHELD { let x: i64 = lp_heldx(hi); if lp_eval(best, 0, x) == lp_target(id, x) { held_ok = held_ok + 1 } hi = hi + 1 } 169 170 lp_p("LOOP target=" as *u8); lp_pn(id); lp_p(" train_err=" as *u8); lp_pn(best_err); lp_p(" gen=" as *u8); lp_pn(best_gen) 171 lp_p(" heldout=" as *u8); lp_pn(held_ok); lp_p("/" as *u8); lp_pn(NHELD) 172 if found == 1 { if held_ok == NHELD { lp_p(" GENERALIZES" as *u8) } else { lp_p(" OVERFIT" as *u8) } } else { lp_p(" NEAR" as *u8) } 173 lp_p(" init=" as *u8); lp_pn(best[0]); lp_p(" body=" as *u8) 174 var jg: i64 = 0 175 while jg < EVO_BODY { lp_pn(best[1 + jg*2]); lp_p("/" as *u8); lp_pn(best[1 + jg*2 + 1]); lp_p(" " as *u8); jg = jg + 1 } 176 lp_p("\n" as *u8) 177 178 // ---- materialize champion as a real loop organ at one held-out x ---- 179 let tx: i64 = lp_heldx(0) 180 let path: *u8 = sys_mmap(512); var po: i64 = 0 181 po = lp_cat(path, po, "runtime/_hdl_build/" as *u8); po = lp_cat(path, po, base_name); po = lp_cat(path, po, ".nx" as *u8); path[po] = 0 as u8 182 let buf: *u8 = sys_mmap(EVO_MAGIC_65536); var o: i64 = 0 183 o = lp_cat(buf, o, "// DISCOVERED BY nx_evo_loop (evolved iterative algorithm from examples) -- a real for-loop, at a HELD-OUT x. license_tier: ORIGINAL\n" as *u8) 184 o = lp_cat(buf, o, "import \"nx_syscalls.nx\"\nfunc main() -> i64 {\n let x: i64 = " as *u8); o = lp_catn(buf, o, tx); o = lp_cat(buf, o, "\n var acc: i64 = " as *u8); o = lp_catn(buf, o, best[0]); o = lp_cat(buf, o, "\n var i: i64 = 1\n while i <= x {\n" as *u8) 185 jg = 0 186 while jg < EVO_BODY { o = lp_emit_body_op(buf, o, best[1 + jg*2], best[1 + jg*2 + 1]); jg = jg + 1 } 187 o = lp_cat(buf, o, " i = i + 1\n }\n" as *u8) 188 o = lp_cat(buf, o, " sys_write(1, \"RESULT=\" as *u8, 7)\n var mm: i64 = acc\n if mm < 0 { sys_write(1, \"-\" as *u8, 1); mm = 0 - mm }\n let t: *u8 = sys_mmap(28)\n var k: i64 = 0\n if mm == 0 { t[0] = 48 as u8; k = 1 }\n while mm > 0 { t[k] = (48 + (mm % 10)) as u8; mm = mm / 10; k = k + 1 }\n while k > 0 { k = k - 1; sys_write(1, (((t as i64)+k) as *u8), 1) }\n sys_write(1, \"\\n\" as *u8, 1)\n return 0\n}\n" as *u8) 189 let fd: i64 = sys_openat_wr(path, 420) 190 if fd < 0 { lp_p("LOOP verdict=RED reason=champion-unwritable\n" as *u8); return 1 } 191 sys_write(fd, buf, o); sys_close(fd) 192 lp_p("LOOP champion written: " as *u8); lp_p(path); lp_p(" (f at held-out x=" as *u8); lp_pn(tx); lp_p(", expect " as *u8); lp_pn(lp_target(id, tx)); lp_p(")\n" as *u8) 193 return 0 194}