code wiki / _hdl_build / nx_evo_pbe.nx
nx_evo_pbe.nx source
↩ module page · 210 lines · 11122 B
1// nx_evo_pbe.nx -- EVOLUTIONARY SYNTHESIS roadmap RUNG 3 (THE HEADLINE):
2// PROGRAMMING-BY-EXAMPLE / INDUCTIVE PROGRAM SYNTHESIS (X-AUT-006N).
3//
4// 006L/006M evolved a constant (hit one numeric target). This evolves a FUNCTION
5// f(x): the genome computes over an INPUT x, fitness = total error across MANY
6// (x_i -> y_i) TRAINING examples, and the champion is VERIFIED on HELD-OUT examples
7// (x the search never trained on). Matching held-out = the engine INDUCED the true
8// function from data (generalization), not memorized points. This is the research-
9// leading capability: discover x*x, 2x*x+3, 3x+5 from EXAMPLES ALONE. It uses the
10// 006M crossover GA as the searcher and an op set rich enough for polynomials.
11//
12// nx_evo_pbe <champion_basename> <target_id> <seed>
13// target_id selects a hidden function used ONLY to GENERATE the dataset + the
14// held-out ground truth (the SEARCH only ever sees the (x,y) pairs, never the
15// formula): 0=x*x 1=2*x*x+3 2=3*x+5 3=x*x+x.
16// op set (genome): 0 add n | 1 mul n | 2 sub n | 3 mul-by-x (acc*x) |
17// 4 add-x (acc+x) | 5 square (acc*acc). start acc = x.
18// -> trains on x in 1..NTRAIN minimizing sum|f(x)-y|; verifies on x in
19// NTRAIN+1..NTRAIN+NHELD; prints train_err + heldout M/NHELD + GENERALIZES/
20// OVERFIT/NEAR; MATERIALIZES the champion as a real organ computing f at one
21// held-out x (compile+run must equal the held-out ground truth).
22//
23// no-false-green: train_err=0 with heldout=NHELD/NHELD = induced the TRUE function
24// (a memoriser would fail held-out); DIFFERENT target_id -> DIFFERENT discovered
25// function, each generalising + champion compiles+runs. Sovereign, no gcc/.sh.
26// HONEST SCOPE: polynomial op set, distance fitness, single i64 input; the seed of
27// inductive synthesis -- branches/loops genomes (for abs/gcd) are a later rung.
28// 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 = 5
38const EVO_P: i64 = 128
39const EVO_G: i64 = 600
40const EVO_T: i64 = 5
41const NTRAIN: i64 = 6
42const NHELD: i64 = 4
43
44func pbe_rand(state: *i64) -> i64 {
45 state[0] = state[0] * EVO_MAGIC_2862933555777941757 + EVO_MAGIC_3037000493
46 return (state[0] >> 17) & 0x3fffffff
47}
48func pbe_abs(x: i64) -> i64 { if x < 0 { return 0 - x } return x }
49
50// the HIDDEN target -- used only to build the dataset + ground truth, never seen by the search.
51func pbe_target(id: i64, x: i64) -> i64 {
52 if id == 0 { return x * x }
53 if id == 1 { return 2 * x * x + 3 }
54 if id == 2 { return 3 * x + 5 }
55 if id == 3 { return x * x + x }
56 return 0
57}
58// evaluate a genome as f(x). op: 0 add n,1 mul n,2 sub n,3 mul-by-x,4 add-x,5 square.
59func pbe_eval(pop: *i64, base: i64, x: i64) -> i64 {
60 var acc: i64 = x
61 var j: i64 = 0
62 while j < EVO_L {
63 let op: i64 = pop[base + j*2]; let n: i64 = pop[base + j*2 + 1]
64 if op == 0 { acc = acc + n }
65 if op == 1 { acc = acc * n }
66 if op == 2 { acc = acc - n }
67 if op == 3 { acc = acc * x }
68 if op == 4 { acc = acc + x }
69 if op == 5 { acc = acc * acc }
70 j = j + 1
71 }
72 return acc
73}
74// fitness = total abs error over the NTRAIN training examples (lower=better).
75func pbe_fit(pop: *i64, base: i64, id: i64) -> i64 {
76 var err: i64 = 0
77 var x: i64 = 1
78 while x <= NTRAIN { err = err + pbe_abs(pbe_eval(pop, base, x) - pbe_target(id, x)); x = x + 1 }
79 return err
80}
81func pbe_randfill(pop: *i64, base: i64, state: *i64) -> i64 {
82 var j: i64 = 0
83 while j < EVO_L { pop[base + j*2] = pbe_rand(state) % 6; pop[base + j*2 + 1] = (pbe_rand(state) % 9) + 1; j = j + 1 }
84 return 0
85}
86func pbe_tourney(fit: *i64, state: *i64) -> i64 {
87 var bi: i64 = pbe_rand(state) % EVO_P; var bd: i64 = fit[bi]; var k: i64 = 1
88 while k < EVO_T { let i: i64 = pbe_rand(state) % EVO_P; if fit[i] < bd { bd = fit[i]; bi = i } k = k + 1 }
89 return bi
90}
91func pbe_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 }
92func pbe_catn(dst: *u8, off: i64, v: i64) -> i64 {
93 var o: i64 = off
94 if v < 0 { dst[o] = 45 as u8; o = o + 1; return pbe_catn(dst, o, 0 - v) }
95 if v == 0 { dst[o] = 48 as u8; return o + 1 }
96 var m: i64 = v; let t: *u8 = sys_mmap(28); var k: i64 = 0
97 while m > 0 { t[k] = (48 + (m % 10)) as u8; m = m / 10; k = k + 1 }
98 var i: i64 = 0
99 while i < k { dst[o+i] = t[k-1-i]; i = i + 1 }
100 return o + k
101}
102func pbe_p(s: *u8) -> i64 { var n: i64 = 0; while s[n] != (0 as u8) { n = n + 1 } sys_write(1, s, n); return 0 }
103func pbe_pn(v: i64) -> i64 { let b: *u8 = sys_mmap(32); let n: i64 = pbe_catn(b, 0, v); sys_write(1, b, n); return 0 }
104func pbe_atoi(s: *u8) -> i64 {
105 var n: i64 = 0; var i: i64 = 0; var neg: i64 = 0
106 if s[0] == (45 as u8) { neg = 1; i = 1 }
107 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 }
108 if neg == 1 { return 0 - n }
109 return n
110}
111// emit one op as readable text into the log ("+3","*2","-1","*x","+x","^2").
112func pbe_op_txt(op: i64, n: i64) -> i64 {
113 if op == 0 { pbe_p("+" as *u8); pbe_pn(n) } else { if op == 1 { pbe_p("*" as *u8); pbe_pn(n) } else { if op == 2 { pbe_p("-" as *u8); pbe_pn(n) } else { if op == 3 { pbe_p("*x" as *u8) } else { if op == 4 { pbe_p("+x" as *u8) } else { pbe_p("^2" as *u8) } } } } }
114 pbe_p(" " as *u8); return 0
115}
116
117func main(argc: i64, argv: *i64) -> i64 {
118 if argc < 4 { pbe_p("usage: nx_evo_pbe <champion_basename> <target_id 0..3> <seed>\n" as *u8); return 2 }
119 let base_name: *u8 = argv[1] as *u8
120 let id: i64 = pbe_atoi(argv[2] as *u8)
121 let seed: i64 = pbe_atoi(argv[3] as *u8)
122
123 let state: *i64 = sys_mmap(8) as *i64; state[0] = seed * EVO_MAGIC_2654435761 + EVO_MAGIC_12345
124 let glen: i64 = EVO_L * 2
125 let pop: *i64 = sys_mmap(EVO_P * glen * 8) as *i64
126 let nxt: *i64 = sys_mmap(EVO_P * glen * 8) as *i64
127 let fit: *i64 = sys_mmap(EVO_P * 8) as *i64
128 let best: *i64 = sys_mmap(glen * 8) as *i64
129
130 var p: i64 = 0
131 while p < EVO_P { pbe_randfill(pop, p * glen, state); p = p + 1 }
132
133 var best_err: i64 = EVO_MAGIC_1000000000; var best_gen: i64 = 0 - 1; var found: i64 = 0
134 var g: i64 = 0
135 while g < EVO_G {
136 var gbest: i64 = EVO_MAGIC_1000000000; var gbp: i64 = 0
137 p = 0
138 while p < EVO_P { let e: i64 = pbe_fit(pop, p * glen, id); fit[p] = e; if e < gbest { gbest = e; gbp = p } p = p + 1 }
139 if gbest < best_err {
140 best_err = gbest
141 var j: i64 = 0
142 while j < glen { best[j] = pop[gbp * glen + j]; j = j + 1 }
143 best_gen = g
144 }
145 if best_err == 0 { found = 1; g = EVO_G } else {
146 var j2: i64 = 0
147 while j2 < glen { nxt[j2] = best[j2]; j2 = j2 + 1 } // elitism
148 p = 1
149 while p < EVO_P {
150 let pa: i64 = pbe_tourney(fit, state) * glen
151 let pb: i64 = pbe_tourney(fit, state) * glen
152 let cut: i64 = (pbe_rand(state) % (EVO_L - 1)) + 1
153 var jj: i64 = 0
154 while jj < EVO_L {
155 if jj < cut { nxt[p*glen + jj*2] = pop[pa + jj*2]; nxt[p*glen + jj*2 + 1] = pop[pa + jj*2 + 1] }
156 else { nxt[p*glen + jj*2] = pop[pb + jj*2]; nxt[p*glen + jj*2 + 1] = pop[pb + jj*2 + 1] }
157 jj = jj + 1
158 }
159 let mi: i64 = pbe_rand(state) % EVO_L
160 if (pbe_rand(state) % 2) == 0 { nxt[p*glen + mi*2] = pbe_rand(state) % 6 } else { nxt[p*glen + mi*2 + 1] = (pbe_rand(state) % 9) + 1 }
161 p = p + 1
162 }
163 var c: i64 = 0
164 while c < EVO_P * glen { pop[c] = nxt[c]; c = c + 1 }
165 g = g + 1
166 }
167 }
168
169 // ---- held-out generalization check (x the search never trained on) ----
170 var held_ok: i64 = 0
171 var hx: i64 = NTRAIN + 1
172 while hx <= NTRAIN + NHELD { if pbe_eval(best, 0, hx) == pbe_target(id, hx) { held_ok = held_ok + 1 } hx = hx + 1 }
173
174 pbe_p("PBE target=" as *u8); pbe_pn(id)
175 pbe_p(" train_err=" as *u8); pbe_pn(best_err)
176 pbe_p(" gen=" as *u8); pbe_pn(best_gen)
177 pbe_p(" heldout=" as *u8); pbe_pn(held_ok); pbe_p("/" as *u8); pbe_pn(NHELD)
178 if found == 1 { if held_ok == NHELD { pbe_p(" GENERALIZES" as *u8) } else { pbe_p(" OVERFIT" as *u8) } } else { pbe_p(" NEAR" as *u8) }
179 pbe_p(" f(x)= x " as *u8)
180 var jg: i64 = 0
181 while jg < EVO_L { pbe_op_txt(best[jg*2], best[jg*2+1]); jg = jg + 1 }
182 pbe_p("\n" as *u8)
183
184 // ---- materialize champion as a real organ computing f at one held-out x ----
185 let tx: i64 = NTRAIN + 1 // a held-out input baked in as a literal
186 let path: *u8 = sys_mmap(512); var po: i64 = 0
187 po = pbe_cat(path, po, "runtime/_hdl_build/" as *u8); po = pbe_cat(path, po, base_name); po = pbe_cat(path, po, ".nx" as *u8); path[po] = 0 as u8
188 let buf: *u8 = sys_mmap(EVO_MAGIC_65536); var o: i64 = 0
189 o = pbe_cat(buf, o, "// DISCOVERED BY nx_evo_pbe (inductive synthesis from examples) -- f(x) FOUND from (x,y) data, evaluated at a HELD-OUT x. license_tier: ORIGINAL\n" as *u8)
190 o = pbe_cat(buf, o, "import \"nx_syscalls.nx\"\nfunc main() -> i64 {\n let x: i64 = " as *u8); o = pbe_catn(buf, o, tx); o = pbe_cat(buf, o, "\n var acc: i64 = x\n" as *u8)
191 jg = 0
192 while jg < EVO_L {
193 let op: i64 = best[jg*2]; let n: i64 = best[jg*2+1]
194 o = pbe_cat(buf, o, " acc = acc " as *u8)
195 if op == 0 { o = pbe_cat(buf, o, "+ " as *u8); o = pbe_catn(buf, o, n) }
196 else { if op == 1 { o = pbe_cat(buf, o, "* " as *u8); o = pbe_catn(buf, o, n) }
197 else { if op == 2 { o = pbe_cat(buf, o, "- " as *u8); o = pbe_catn(buf, o, n) }
198 else { if op == 3 { o = pbe_cat(buf, o, "* x" as *u8) }
199 else { if op == 4 { o = pbe_cat(buf, o, "+ x" as *u8) }
200 else { o = pbe_cat(buf, o, "* acc" as *u8) } } } } }
201 o = pbe_cat(buf, o, "\n" as *u8)
202 jg = jg + 1
203 }
204 o = pbe_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)
205 let fd: i64 = sys_openat_wr(path, 420)
206 if fd < 0 { pbe_p("PBE verdict=RED reason=champion-unwritable\n" as *u8); return 1 }
207 sys_write(fd, buf, o); sys_close(fd)
208 pbe_p("PBE champion written: " as *u8); pbe_p(path); pbe_p(" (computes f at held-out x=" as *u8); pbe_pn(tx); pbe_p(", expect " as *u8); pbe_pn(pbe_target(id, tx)); pbe_p(")\n" as *u8)
209 return 0
210}