`nx_evo_cf.nx` source

↩ module page · 209 lines · 11503 B
1// nx_evo_cf.nx -- EVOLUTIONARY SYNTHESIS rung: CONTROL-FLOW GENOMES under example
2// fitness (X-AUT-006O) -- discover ALGORITHMS (piecewise functions), not just
3// polynomials, from examples.
4//
5// 006N (nx_evo_pbe) discovered POLYNOMIAL f(x) from examples but its op set cannot
6// express a piecewise function like abs/relu (a kink is not polynomial).  This rung
7// gives the genome GENERAL control-flow primitives -- a linear-GP register machine
8// with PREDICATED execution: NEGATE (0-acc), SUB-X, a SIGN-PREDICATE (skip the NEXT
9// instruction when acc>=0, i.e. the next instr runs IFF acc<0), and NOP.  None is
10// target-specific; the search must COMPOSE [predicate, negate] to get abs, etc.
11// Evolved under the 006N example-based fitness + HELD-OUT generalization check.
12//
13//   nx_evo_cf <champion_basename> <target_id> <seed>     target: 0=abs 1=relu 2=x*x
14//   op set: 0 +n,1 *n,2 -n,3 +x,4 *x,5 ^2,6 negate,7 PREDICATE(skip next if acc>=0),
15//           8 nop,9 -x.   train on x in {-3,-2,-1,1,2,3}; held-out {-5,-4,4,5}.
16//   -> champion materialized with REAL control flow: op7+next emits `if acc<0 { next }`.
17//
18// no-false-green: abs/relu need the conditional -> a polynomial genome can at best
19// OVERFIT the training points and FAIL held-out (caught); the GENERALIZING (4/4)
20// solution is the control-flow one, and the champion COMPILES+RUNS with a real
21// if-branch.  Sovereign, no gcc/.sh.  HONEST: predicated linear-GP (one forward
22// sign-predicate), integer fitness; loops-from-examples (gcd/fib) are the next rung.
23// license_tier: ORIGINAL
24import "nx_syscalls.nx"
25const EVO_MAGIC_2862933555777941757: i64 = 2862933555777941757
26const EVO_MAGIC_3037000493: i64 = 3037000493
27const EVO_MAGIC_2654435761: i64 = 2654435761
28const EVO_MAGIC_12345: i64 = 12345
29const EVO_MAGIC_1000000000: i64 = 1000000000
30const EVO_MAGIC_65536: i64 = 65536
31
32const EVO_L: i64 = 6
33const EVO_P: i64 = 256
34const EVO_G: i64 = 1200
35const EVO_T: i64 = 5
36const NTRAIN: i64 = 6
37const NHELD: i64 = 4
38
39func cf_rand(state: *i64) -> i64 { state[0] = state[0] * EVO_MAGIC_2862933555777941757 + EVO_MAGIC_3037000493; return (state[0] >> 17) & 0x3fffffff }
40func cf_abs(x: i64) -> i64 { if x < 0 { return 0 - x } return x }
41func cf_trainx(i: i64) -> i64 { if i == 0 { return 0 - 3 } if i == 1 { return 0 - 2 } if i == 2 { return 0 - 1 } if i == 3 { return 1 } if i == 4 { return 2 } return 3 }
42func cf_heldx(i: i64) -> i64 { if i == 0 { return 0 - 5 } if i == 1 { return 0 - 4 } if i == 2 { return 4 } return 5 }
43func cf_target(id: i64, x: i64) -> i64 {
44    if id == 0 { return cf_abs(x) }                        // abs
45    if id == 1 { if x < 0 { return 0 } return x }          // relu
46    if id == 2 { return x * x }                            // polynomial control
47    return 0
48}
49// evaluate a predicated linear-GP genome as f(x).
50func cf_eval(pop: *i64, base: i64, x: i64) -> i64 {
51    var acc: i64 = x
52    var skip: i64 = 0
53    var j: i64 = 0
54    while j < EVO_L {
55        let op: i64 = pop[base + j*2]; let n: i64 = pop[base + j*2 + 1]
56        if skip == 1 { skip = 0 } else {
57            if op == 0 { acc = acc + n }
58            if op == 1 { acc = acc * n }
59            if op == 2 { acc = acc - n }
60            if op == 3 { acc = acc + x }
61            if op == 4 { acc = acc * x }
62            if op == 5 { acc = acc * acc }
63            if op == 6 { acc = 0 - acc }
64            if op == 7 { if acc >= 0 { skip = 1 } }          // sign-predicate: next runs iff acc<0
65            if op == 9 { acc = acc - x }
66            // op == 8 is NOP (acc unchanged)
67        }
68        j = j + 1
69    }
70    return acc
71}
72func cf_fit(pop: *i64, base: i64, id: i64) -> i64 {
73    var err: i64 = 0; var i: i64 = 0
74    while i < NTRAIN { let x: i64 = cf_trainx(i); err = err + cf_abs(cf_eval(pop, base, x) - cf_target(id, x)); i = i + 1 }
75    return err
76}
77func cf_randfill(pop: *i64, base: i64, state: *i64) -> i64 {
78    var j: i64 = 0
79    while j < EVO_L { pop[base + j*2] = cf_rand(state) % 10; pop[base + j*2 + 1] = (cf_rand(state) % 9) + 1; j = j + 1 }
80    return 0
81}
82func cf_tourney(fit: *i64, state: *i64) -> i64 {
83    var bi: i64 = cf_rand(state) % EVO_P; var bd: i64 = fit[bi]; var k: i64 = 1
84    while k < EVO_T { let i: i64 = cf_rand(state) % EVO_P; if fit[i] < bd { bd = fit[i]; bi = i } k = k + 1 }
85    return bi
86}
87func cf_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 cf_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 cf_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 cf_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 cf_pn(v: i64) -> i64 { let b: *u8 = sys_mmap(32); let n: i64 = cf_catn(b, 0, v); sys_write(1, b, n); return 0 }
100func cf_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}
107// emit one non-predicate op into buf (used both at top level and inside an if-block).
108func cf_emit_op(buf: *u8, off: i64, op: i64, n: i64, indent: *u8) -> i64 {
109    var o: i64 = off
110    o = cf_cat(buf, o, indent)
111    if op == 0 { o = cf_cat(buf, o, "acc = acc + " as *u8); o = cf_catn(buf, o, n) }
112    else { if op == 1 { o = cf_cat(buf, o, "acc = acc * " as *u8); o = cf_catn(buf, o, n) }
113    else { if op == 2 { o = cf_cat(buf, o, "acc = acc - " as *u8); o = cf_catn(buf, o, n) }
114    else { if op == 3 { o = cf_cat(buf, o, "acc = acc + x" as *u8) }
115    else { if op == 4 { o = cf_cat(buf, o, "acc = acc * x" as *u8) }
116    else { if op == 5 { o = cf_cat(buf, o, "acc = acc * acc" as *u8) }
117    else { if op == 6 { o = cf_cat(buf, o, "acc = 0 - acc" as *u8) }
118    else { if op == 9 { o = cf_cat(buf, o, "acc = acc - x" as *u8) }
119    else { o = cf_cat(buf, o, "acc = acc" as *u8) } } } } } } } }    // 8 nop (and 7 handled by caller)
120    o = cf_cat(buf, o, "\n" as *u8)
121    return o
122}
123
124func main(argc: i64, argv: *i64) -> i64 {
125    if argc < 4 { cf_p("usage: nx_evo_cf <champion_basename> <target_id 0=abs 1=relu 2=x*x> <seed>\n" as *u8); return 2 }
126    let base_name: *u8 = argv[1] as *u8
127    let id: i64 = cf_atoi(argv[2] as *u8)
128    let seed: i64 = cf_atoi(argv[3] as *u8)
129
130    let state: *i64 = sys_mmap(8) as *i64; state[0] = seed * EVO_MAGIC_2654435761 + EVO_MAGIC_12345
131    let glen: i64 = EVO_L * 2
132    let pop: *i64 = sys_mmap(EVO_P * glen * 8) as *i64
133    let nxt: *i64 = sys_mmap(EVO_P * glen * 8) as *i64
134    let fit: *i64 = sys_mmap(EVO_P * 8) as *i64
135    let best: *i64 = sys_mmap(glen * 8) as *i64
136
137    var p: i64 = 0
138    while p < EVO_P { cf_randfill(pop, p * glen, state); p = p + 1 }
139
140    var best_err: i64 = EVO_MAGIC_1000000000; var best_gen: i64 = 0 - 1; var found: i64 = 0
141    var g: i64 = 0
142    while g < EVO_G {
143        var gbest: i64 = EVO_MAGIC_1000000000; var gbp: i64 = 0
144        p = 0
145        while p < EVO_P { let e: i64 = cf_fit(pop, p * glen, id); fit[p] = e; if e < gbest { gbest = e; gbp = p } p = p + 1 }
146        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 }
147        if best_err == 0 { found = 1; g = EVO_G } else {
148            var j2: i64 = 0
149            while j2 < glen { nxt[j2] = best[j2]; j2 = j2 + 1 }
150            p = 1
151            while p < EVO_P {
152                let pa: i64 = cf_tourney(fit, state) * glen
153                let pb: i64 = cf_tourney(fit, state) * glen
154                let cut: i64 = (cf_rand(state) % (EVO_L - 1)) + 1
155                var jj: i64 = 0
156                while jj < EVO_L {
157                    if jj < cut { nxt[p*glen + jj*2] = pop[pa + jj*2]; nxt[p*glen + jj*2 + 1] = pop[pa + jj*2 + 1] }
158                    else { nxt[p*glen + jj*2] = pop[pb + jj*2]; nxt[p*glen + jj*2 + 1] = pop[pb + jj*2 + 1] }
159                    jj = jj + 1
160                }
161                let mi: i64 = cf_rand(state) % EVO_L
162                if (cf_rand(state) % 2) == 0 { nxt[p*glen + mi*2] = cf_rand(state) % 10 } else { nxt[p*glen + mi*2 + 1] = (cf_rand(state) % 9) + 1 }
163                p = p + 1
164            }
165            var c: i64 = 0
166            while c < EVO_P * glen { pop[c] = nxt[c]; c = c + 1 }
167            g = g + 1
168        }
169    }
170
171    var held_ok: i64 = 0; var hi: i64 = 0
172    while hi < NHELD { let x: i64 = cf_heldx(hi); if cf_eval(best, 0, x) == cf_target(id, x) { held_ok = held_ok + 1 } hi = hi + 1 }
173
174    cf_p("CF target=" as *u8); cf_pn(id); cf_p(" train_err=" as *u8); cf_pn(best_err); cf_p(" gen=" as *u8); cf_pn(best_gen)
175    cf_p(" heldout=" as *u8); cf_pn(held_ok); cf_p("/" as *u8); cf_pn(NHELD)
176    if found == 1 { if held_ok == NHELD { cf_p(" GENERALIZES" as *u8) } else { cf_p(" OVERFIT" as *u8) } } else { cf_p(" NEAR" as *u8) }
177    cf_p(" genome-ops=" as *u8)
178    var jg: i64 = 0
179    while jg < EVO_L { let op: i64 = best[jg*2]; cf_pn(op); cf_p("/" as *u8); cf_pn(best[jg*2+1]); cf_p(" " as *u8); jg = jg + 1 }
180    cf_p("\n" as *u8)
181
182    // ---- materialize champion with REAL control flow at one held-out x ----
183    let tx: i64 = cf_heldx(0)                                 // a held-out input (-5)
184    let path: *u8 = sys_mmap(512); var po: i64 = 0
185    po = cf_cat(path, po, "runtime/_hdl_build/" as *u8); po = cf_cat(path, po, base_name); po = cf_cat(path, po, ".nx" as *u8); path[po] = 0 as u8
186    let buf: *u8 = sys_mmap(EVO_MAGIC_65536); var o: i64 = 0
187    o = cf_cat(buf, o, "// DISCOVERED BY nx_evo_cf (evolved control-flow program from examples) -- f(x) w/ a real if-branch, at a HELD-OUT x. license_tier: ORIGINAL\n" as *u8)
188    o = cf_cat(buf, o, "import \"nx_syscalls.nx\"\nfunc main() -> i64 {\n    let x: i64 = " as *u8); o = cf_catn(buf, o, tx); o = cf_cat(buf, o, "\n    var acc: i64 = x\n" as *u8)
189    jg = 0
190    while jg < EVO_L {
191        let op: i64 = best[jg*2]; let n: i64 = best[jg*2+1]
192        if op == 7 {
193            // predicate: the NEXT instruction runs iff acc<0
194            o = cf_cat(buf, o, "    if acc < 0 {\n" as *u8)
195            jg = jg + 1
196            if jg < EVO_L { o = cf_emit_op(buf, o, best[jg*2], best[jg*2+1], "        " as *u8) }
197            o = cf_cat(buf, o, "    }\n" as *u8)
198        } else {
199            o = cf_emit_op(buf, o, op, n, "    " as *u8)
200        }
201        jg = jg + 1
202    }
203    o = cf_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)
204    let fd: i64 = sys_openat_wr(path, 420)
205    if fd < 0 { cf_p("CF verdict=RED reason=champion-unwritable\n" as *u8); return 1 }
206    sys_write(fd, buf, o); sys_close(fd)
207    cf_p("CF champion written: " as *u8); cf_p(path); cf_p(" (f at held-out x=" as *u8); cf_pn(tx); cf_p(", expect " as *u8); cf_pn(cf_target(id, tx)); cf_p(")\n" as *u8)
208    return 0
209}
nx_evo_cf.nx source

`nx_evo_cf.nx` source
