nx_evo_synth.nx source

1// nx_evo_synth.nx -- EVOLUTIONARY PROGRAM SYNTHESIS (X-AUT-006L): SELF-BUILDING CODE. 2// 3// The leap past the emitter ladder. Rungs 006g..006k made the team able to EMIT a 4// program from a hand-written DATA spec. This organ makes the team DISCOVER a 5// program by EVOLUTIONARY SEARCH -- it is given only a TARGET (a desired output for 6// a start input), NOT the answer, and SEARCHES op-list program-space until it finds 7// code that hits the target, then MATERIALIZES that discovered code as a real 8// sovereign compiled organ. Genotype (op-list genome) -> phenotype (its computed 9// result) -> fitness (distance to target) -> selection+mutation -> next generation: 10// this is genetic programming / an (1+lambda) evolution strategy, the substrate of 11// "evolutionary computation, self-building code". 12// 13// nx_evo_synth <champion_basename> <start> <target> <seed> 14// - deterministic (seeded LCG) so a run is reproducible/gateable. 15// - genome = EVO_L ops (opcode add/mul/sub + operand 1..9); pop = EVO_P; 16// gens = EVO_G; (1+lambda): elite best + lambda mutants of best each gen. 17// - prints FOUND/NEAR gen=<g> dist=<d> result=<r> genome=<ops>. 18// - WRITES runtime/_hdl_build/<champion_basename>.nx = the DISCOVERED program 19// (an op-list organ) so the gate can COMPILE+RUN it and confirm it really 20// produces the target -- the unfakeable proof the evolved code is real. 21// 22// no-false-green: different targets -> different DISCOVERED genomes, each verified by 23// compiling+running the materialized champion to the target; the champion is NOT 24// hand-written and (for non-trivial targets) NOT found at generation 0 -- the search 25// must climb. Sovereign, no gcc/.sh. HONEST SCOPE: linear op-list genomes over one 26// i64 (the 006g phenotype), distance fitness, mutation-only ES; NOT yet crossover / 27// branch+loop genomes / multi-example fitness -- but it is GENUINE program synthesis 28// by evolution, the seed of the research arc. license_tier: ORIGINAL 29import "nx_syscalls.nx" 30const EVO_MAGIC_2862933555777941757: i64 = 2862933555777941757 31const EVO_MAGIC_3037000493: i64 = 3037000493 32const EVO_MAGIC_2654435761: i64 = 2654435761 33const EVO_MAGIC_12345: i64 = 12345 34const EVO_MAGIC_1000000000: i64 = 1000000000 35const EVO_MAGIC_65536: i64 = 65536 36 37const EVO_L: i64 = 6 // ops per genome 38const EVO_P: i64 = 64 // population 39const EVO_G: i64 = 400 // max generations 40 41func evo_rand(state: *i64) -> i64 { 42 state[0] = state[0] * EVO_MAGIC_2862933555777941757 + EVO_MAGIC_3037000493 43 return (state[0] >> 17) & 0x3fffffff // 30-bit non-negative 44} 45func evo_abs(x: i64) -> i64 { if x < 0 { return 0 - x } return x } 46 47// apply a genome (EVO_L ops at base) to `start` -> result. op: 0=add 1=mul 2=sub. 48func evo_eval(pop: *i64, base: i64, start: i64) -> i64 { 49 var acc: i64 = start 50 var j: i64 = 0 51 while j < EVO_L { 52 let op: i64 = pop[base + j*2] 53 let n: i64 = pop[base + j*2 + 1] 54 if op == 0 { acc = acc + n } 55 if op == 1 { acc = acc * n } 56 if op == 2 { acc = acc - n } 57 j = j + 1 58 } 59 return acc 60} 61func evo_copy(pop: *i64, dst: i64, src: i64) -> i64 { 62 var j: i64 = 0 63 while j < EVO_L * 2 { pop[dst + j] = pop[src + j]; j = j + 1 } 64 return 0 65} 66// fill one genome slot (base) with random ops. 67func evo_randfill(pop: *i64, base: i64, state: *i64) -> i64 { 68 var j: i64 = 0 69 while j < EVO_L { 70 pop[base + j*2] = evo_rand(state) % 3 71 pop[base + j*2 + 1] = (evo_rand(state) % 9) + 1 72 j = j + 1 73 } 74 return 0 75} 76// human-readable op-list ("a5 m6 s2 ..") for the log. 77func evo_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 } 78func evo_catn(dst: *u8, off: i64, v: i64) -> i64 { 79 var o: i64 = off 80 if v < 0 { dst[o] = 45 as u8; o = o + 1; return evo_catn(dst, o, 0 - v) } 81 if v == 0 { dst[o] = 48 as u8; return o + 1 } 82 var m: i64 = v; let t: *u8 = sys_mmap(28); var k: i64 = 0 83 while m > 0 { t[k] = (48 + (m % 10)) as u8; m = m / 10; k = k + 1 } 84 var i: i64 = 0 85 while i < k { dst[o+i] = t[k-1-i]; i = i + 1 } 86 return o + k 87} 88func evo_p(s: *u8) -> i64 { var n: i64 = 0; while s[n] != (0 as u8) { n = n + 1 } sys_write(1, s, n); return 0 } 89func evo_atoi(s: *u8) -> i64 { 90 var n: i64 = 0; var i: i64 = 0; var neg: i64 = 0 91 if s[0] == (45 as u8) { neg = 1; i = 1 } 92 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 } 93 if neg == 1 { return 0 - n } 94 return n 95} 96 97func main(argc: i64, argv: *i64) -> i64 { 98 if argc < 5 { evo_p("usage: nx_evo_synth <champion_basename> <start> <target> <seed>\n" as *u8); return 2 } 99 let base_name: *u8 = argv[1] as *u8 100 let start: i64 = evo_atoi(argv[2] as *u8) 101 let target: i64 = evo_atoi(argv[3] as *u8) 102 let seed: i64 = evo_atoi(argv[4] as *u8) 103 104 let state: *i64 = sys_mmap(8) as *i64 105 state[0] = seed * EVO_MAGIC_2654435761 + EVO_MAGIC_12345 // spread the seed 106 107 let glen: i64 = EVO_L * 2 108 let pop: *i64 = sys_mmap(EVO_P * glen * 8) as *i64 109 let best: *i64 = sys_mmap(glen * 8) as *i64 110 111 // ---- random initial population ---- 112 var p: i64 = 0 113 while p < EVO_P { evo_randfill(pop, p * glen, state); p = p + 1 } 114 115 var best_dist: i64 = EVO_MAGIC_1000000000 116 var best_gen: i64 = 0 - 1 117 var best_res: i64 = 0 118 var found: i64 = 0 119 var g: i64 = 0 120 while g < EVO_G { 121 // evaluate population, find the generation's best 122 var gen_best_dist: i64 = EVO_MAGIC_1000000000 123 var gen_best_p: i64 = 0 124 p = 0 125 while p < EVO_P { 126 let r: i64 = evo_eval(pop, p * glen, start) 127 let d: i64 = evo_abs(r - target) 128 if d < gen_best_dist { gen_best_dist = d; gen_best_p = p } 129 p = p + 1 130 } 131 // global best (elitism: monotonic non-increasing distance) 132 if gen_best_dist < best_dist { 133 best_dist = gen_best_dist 134 var j: i64 = 0 135 while j < glen { best[j] = pop[gen_best_p * glen + j]; j = j + 1 } 136 best_gen = g 137 best_res = evo_eval(best, 0, start) 138 } 139 if best_dist == 0 { found = 1; g = EVO_G } else { 140 // reproduce: slot 0 = elite best; slots 1..P-1 = single-point mutants of best 141 var j2: i64 = 0 142 while j2 < glen { pop[j2] = best[j2]; j2 = j2 + 1 } 143 p = 1 144 while p < EVO_P { 145 var jj: i64 = 0 146 while jj < glen { pop[p*glen + jj] = best[jj]; jj = jj + 1 } 147 let mi: i64 = evo_rand(state) % EVO_L 148 if (evo_rand(state) % 2) == 0 { 149 pop[p*glen + mi*2] = evo_rand(state) % 3 // mutate opcode 150 } else { 151 pop[p*glen + mi*2 + 1] = (evo_rand(state) % 9) + 1 // mutate operand 152 } 153 p = p + 1 154 } 155 g = g + 1 156 } 157 } 158 159 // ---- report ---- 160 if found == 1 { evo_p("EVO FOUND gen=" as *u8) } else { evo_p("EVO NEAR gen=" as *u8) } 161 let lb: *u8 = sys_mmap(64); var lo: i64 = 0 162 lo = evo_catn(lb, 0, best_gen); sys_write(1, lb, lo) 163 evo_p(" dist=" as *u8); lo = evo_catn(lb, 0, best_dist); sys_write(1, lb, lo) 164 evo_p(" result=" as *u8); lo = evo_catn(lb, 0, best_res); sys_write(1, lb, lo) 165 evo_p(" target=" as *u8); lo = evo_catn(lb, 0, target); sys_write(1, lb, lo) 166 evo_p(" genome=" as *u8) 167 var jg: i64 = 0 168 while jg < EVO_L { 169 let op: i64 = best[jg*2]; let n: i64 = best[jg*2+1] 170 if op == 0 { evo_p("a" as *u8) } else { if op == 1 { evo_p("m" as *u8) } else { evo_p("s" as *u8) } } 171 lo = evo_catn(lb, 0, n); sys_write(1, lb, lo); evo_p(" " as *u8) 172 jg = jg + 1 173 } 174 evo_p("\n" as *u8) 175 176 // ---- MATERIALIZE the discovered champion as a real sovereign organ ---- 177 let path: *u8 = sys_mmap(512); var po: i64 = 0 178 po = evo_cat(path, po, "runtime/_hdl_build/" as *u8); po = evo_cat(path, po, base_name); po = evo_cat(path, po, ".nx" as *u8); path[po] = 0 as u8 179 let buf: *u8 = sys_mmap(EVO_MAGIC_65536); var o: i64 = 0 180 o = evo_cat(buf, o, "// DISCOVERED BY nx_evo_synth (evolutionary program synthesis) -- this op-list was FOUND by search to hit a target, not hand-written. license_tier: ORIGINAL\n" as *u8) 181 o = evo_cat(buf, o, "import \"nx_syscalls.nx\"\nfunc main() -> i64 {\n var acc: i64 = " as *u8); o = evo_catn(buf, o, start); o = evo_cat(buf, o, "\n" as *u8) 182 jg = 0 183 while jg < EVO_L { 184 let op: i64 = best[jg*2]; let n: i64 = best[jg*2+1] 185 o = evo_cat(buf, o, " acc = acc " as *u8) 186 if op == 0 { o = evo_cat(buf, o, "+ " as *u8) } else { if op == 1 { o = evo_cat(buf, o, "* " as *u8) } else { o = evo_cat(buf, o, "- " as *u8) } } 187 o = evo_catn(buf, o, n); o = evo_cat(buf, o, "\n" as *u8) 188 jg = jg + 1 189 } 190 o = evo_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) 191 let fd: i64 = sys_openat_wr(path, 420) 192 if fd < 0 { evo_p("EVO verdict=RED reason=champion-unwritable\n" as *u8); return 1 } 193 sys_write(fd, buf, o); sys_close(fd) 194 evo_p("EVO champion written: " as *u8); evo_p(path); evo_p("\n" as *u8) 195 if found == 1 { return 0 } 196 return 0 197}