`nx_evo_gcd.nx` source

↩ module page · 194 lines · 10820 B
1// nx_evo_gcd.nx -- EVOLUTIONARY SYNTHESIS rung: 2-REGISTER CONDITIONAL-WHILE GENOMES
2// (eve rung #1 -- the evo arc's own stated next step: "2-input (gcd)"). Discovers
3// gcd's STRUCTURE (the Euclid step swap+mod under a while-nonzero loop) from
4// (a,b)->gcd(a,b) examples + HELD-OUT, zero Claude composing the algorithm. The
5// MACHINE is authored (Bar-C role: representation/eval/fitness/materialize); the
6// SEARCH derives the body. 2 regs r0,r1 (init a,b); control = while r1!=0 (guard-
7// capped); body = evolved ops over {0 r0%=r1, 1 r1%=r0, 2 swap, 3 r0-=r1, 4 r1-=r0,
8// 5 nop}; out r0. gcd is reachable as body [swap, r1%=r0]. Champion materialized as
9// a REAL 2-input while-loop organ run at a HELD-OUT pair (prints RESULT=<gcd>).
10// no-false-green: a body that can't drive r1->0 hits the guard / a wrong op FAILS
11// held-out; only the GENERALIZING (4/4) champion is the real Euclid. Sovereign, no
12// gcc/.sh. HONEST: loop condition FIXED (while r1!=0); evolving the condition + >2
13// registers + nested loops are later rungs. license_tier: ORIGINAL
14import "nx_syscalls.nx"
15const EVO_MAGIC_2862933555777941757: i64 = 2862933555777941757
16const EVO_MAGIC_3037000493: i64 = 3037000493
17const EVO_MAGIC_2000000: i64 = 2000000
18const EVO_MAGIC_1000000: i64 = 1000000
19const EVO_MAGIC_2654435761: i64 = 2654435761
20const EVO_MAGIC_12345: i64 = 12345
21const EVO_MAGIC_1000000000: i64 = 1000000000
22const EVO_MAGIC_65536: i64 = 65536
23
24const EVO_BODY: i64 = 4
25const EVO_P: i64 = 256
26const EVO_G: i64 = 1500
27const EVO_T: i64 = 5
28const NTRAIN: i64 = 6
29const NHELD: i64 = 4
30const GCD_CAP: i64 = 256
31
32func gd_rand(state: *i64) -> i64 { state[0] = state[0] * EVO_MAGIC_2862933555777941757 + EVO_MAGIC_3037000493; return (state[0] >> 17) & 0x3fffffff }
33func gd_abs(x: i64) -> i64 { if x < 0 { return 0 - x } return x }
34
35// training (i<6) + held-out (i>=6) (a,b) pairs with true gcd.
36func gd_a(i: i64) -> i64 { if i == 0 { return 12 } if i == 1 { return 15 } if i == 2 { return 7 } if i == 3 { return 100 } if i == 4 { return 9 } if i == 5 { return 14 } if i == 6 { return 48 } if i == 7 { return 17 } if i == 8 { return 81 } return 1000 }
37func gd_b(i: i64) -> i64 { if i == 0 { return 8 } if i == 1 { return 5 } if i == 2 { return 3 } if i == 3 { return 60 } if i == 4 { return 6 } if i == 5 { return 21 } if i == 6 { return 36 } if i == 7 { return 5 } if i == 8 { return 27 } return 625 }
38func gd_g(i: i64) -> i64 { if i == 0 { return 4 } if i == 1 { return 5 } if i == 2 { return 1 } if i == 3 { return 20 } if i == 4 { return 3 } if i == 5 { return 7 } if i == 6 { return 12 } if i == 7 { return 1 } if i == 8 { return 27 } return 125 }
39
40// eval a 2-register genome as gcd(a,b). Semantics MUST match the materialized organ.
41func gd_eval(pop: *i64, base: i64, a: i64, b: i64) -> i64 {
42    var r0: i64 = a
43    var r1: i64 = b
44    var guard: i64 = 0
45    while r1 != 0 {
46        if guard >= GCD_CAP { r1 = 0 } else {
47            var j: i64 = 0
48            while j < EVO_BODY {
49                let op: i64 = pop[base + j]
50                if op == 0 { if r1 != 0 { r0 = r0 % r1 } }
51                if op == 1 { if r0 != 0 { r1 = r1 % r0 } }
52                if op == 2 { let t: i64 = r0; r0 = r1; r1 = t }
53                if op == 3 { r0 = r0 - r1 }
54                if op == 4 { r1 = r1 - r0 }
55                j = j + 1
56            }
57            guard = guard + 1
58        }
59    }
60    return r0
61}
62
63// overflow-SAFE fitness: a runaway sub-op can wrap r past INT64, so score only
64// results in the sane gcd range [0,1e6]; anything else (negative/huge garbage) gets
65// a fixed large penalty -- this kills the "negative-err looks best" exploit and makes
66// the search DISCRIMINATE the useless ops away. err in [0, NTRAIN*2e6], never wraps.
67func gd_fit(pop: *i64, base: i64) -> i64 {
68    var err: i64 = 0
69    var i: i64 = 0
70    while i < NTRAIN {
71        let r: i64 = gd_eval(pop, base, gd_a(i), gd_b(i))
72        var d: i64 = EVO_MAGIC_2000000
73        if r >= 0 { if r <= EVO_MAGIC_1000000 { d = gd_abs(r - gd_g(i)) } }
74        err = err + d
75        i = i + 1
76    }
77    return err
78}
79
80func gd_randfill(pop: *i64, base: i64, state: *i64) -> i64 {
81    var j: i64 = 0
82    while j < EVO_BODY { pop[base + j] = gd_rand(state) % 6; j = j + 1 }
83    return 0
84}
85
86func gd_tourney(fit: *i64, state: *i64) -> i64 {
87    var bi: i64 = gd_rand(state) % EVO_P; var bd: i64 = fit[bi]; var k: i64 = 1
88    while k < EVO_T { let i: i64 = gd_rand(state) % EVO_P; if fit[i] < bd { bd = fit[i]; bi = i } k = k + 1 }
89    return bi
90}
91
92func gd_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 }
93func gd_catn(dst: *u8, off: i64, v: i64) -> i64 {
94    var o: i64 = off
95    if v < 0 { dst[o] = 45 as u8; o = o + 1; return gd_catn(dst, o, 0 - v) }
96    if v == 0 { dst[o] = 48 as u8; return o + 1 }
97    var m: i64 = v; let t: *u8 = sys_mmap(28); var k: i64 = 0
98    while m > 0 { t[k] = (48 + (m % 10)) as u8; m = m / 10; k = k + 1 }
99    var i: i64 = 0
100    while i < k { dst[o+i] = t[k-1-i]; i = i + 1 }
101    return o + k
102}
103func gd_p(s: *u8) -> i64 { var n: i64 = 0; while s[n] != (0 as u8) { n = n + 1 } sys_write(1, s, n); return 0 }
104func gd_pn(v: i64) -> i64 { let b: *u8 = sys_mmap(32); let n: i64 = gd_catn(b, 0, v); sys_write(1, b, n); return 0 }
105func gd_atoi(s: *u8) -> i64 {
106    var n: i64 = 0; var i: i64 = 0; var neg: i64 = 0
107    if s[0] == (45 as u8) { neg = 1; i = 1 }
108    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 }
109    if neg == 1 { return 0 - n }
110    return n
111}
112
113// emit one body op as source into buf (swap uses pre-declared swp; op 5 = nop -> nothing).
114func gd_emit_op(buf: *u8, off: i64, op: i64) -> i64 {
115    var o: i64 = off
116    if op == 0 { o = gd_cat(buf, o, "            if r1 != 0 { r0 = r0 % r1 }\n" as *u8); return o }
117    if op == 1 { o = gd_cat(buf, o, "            if r0 != 0 { r1 = r1 % r0 }\n" as *u8); return o }
118    if op == 2 { o = gd_cat(buf, o, "            swp = r0\n            r0 = r1\n            r1 = swp\n" as *u8); return o }
119    if op == 3 { o = gd_cat(buf, o, "            r0 = r0 - r1\n" as *u8); return o }
120    if op == 4 { o = gd_cat(buf, o, "            r1 = r1 - r0\n" as *u8); return o }
121    return o
122}
123
124func main(argc: i64, argv: *i64) -> i64 {
125    var base_name: *u8 = "_evo_gcd_champ" as *u8
126    var seed: i64 = 7
127    if argc >= 3 { base_name = argv[1] as *u8; seed = gd_atoi(argv[2] as *u8) }
128
129    let state: *i64 = sys_mmap(8) as *i64; state[0] = seed * EVO_MAGIC_2654435761 + EVO_MAGIC_12345
130    let glen: i64 = EVO_BODY
131    let pop: *i64 = sys_mmap(EVO_P * glen * 8) as *i64
132    let nxt: *i64 = sys_mmap(EVO_P * glen * 8) as *i64
133    let fit: *i64 = sys_mmap(EVO_P * 8) as *i64
134    let best: *i64 = sys_mmap(glen * 8) as *i64
135
136    var p: i64 = 0
137    while p < EVO_P { gd_randfill(pop, p * glen, state); p = p + 1 }
138
139    var best_err: i64 = EVO_MAGIC_1000000000; var best_gen: i64 = 0 - 1; var found: i64 = 0
140    var g: i64 = 0
141    while g < EVO_G {
142        var gbest: i64 = EVO_MAGIC_1000000000; var gbp: i64 = 0
143        p = 0
144        while p < EVO_P { let e: i64 = gd_fit(pop, p * glen); fit[p] = e; if e < gbest { gbest = e; gbp = p } p = p + 1 }
145        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 }
146        if best_err == 0 { found = 1; g = EVO_G } else {
147            var j2: i64 = 0
148            while j2 < glen { nxt[j2] = best[j2]; j2 = j2 + 1 }
149            p = 1
150            while p < EVO_P {
151                let pa: i64 = gd_tourney(fit, state) * glen
152                let pb: i64 = gd_tourney(fit, state) * glen
153                let cut: i64 = (gd_rand(state) % (glen - 1)) + 1
154                var jj: i64 = 0
155                while jj < glen { if jj < cut { nxt[p*glen + jj] = pop[pa + jj] } else { nxt[p*glen + jj] = pop[pb + jj] } jj = jj + 1 }
156                let bj: i64 = gd_rand(state) % EVO_BODY
157                nxt[p*glen + bj] = gd_rand(state) % 6
158                p = p + 1
159            }
160            var c: i64 = 0
161            while c < EVO_P * glen { pop[c] = nxt[c]; c = c + 1 }
162            g = g + 1
163        }
164    }
165
166    var held_ok: i64 = 0; var hi: i64 = 0
167    while hi < NHELD { let idx: i64 = NTRAIN + hi; if gd_eval(best, 0, gd_a(idx), gd_b(idx)) == gd_g(idx) { held_ok = held_ok + 1 } hi = hi + 1 }
168
169    gd_p("GCD train_err=" as *u8); gd_pn(best_err); gd_p(" gen=" as *u8); gd_pn(best_gen)
170    gd_p(" heldout=" as *u8); gd_pn(held_ok); gd_p("/" as *u8); gd_pn(NHELD)
171    if found == 1 { if held_ok == NHELD { gd_p(" GENERALIZES" as *u8) } else { gd_p(" OVERFIT" as *u8) } } else { gd_p(" NEAR" as *u8) }
172    gd_p(" body=" as *u8)
173    var jg: i64 = 0
174    while jg < EVO_BODY { gd_pn(best[jg]); gd_p(" " as *u8); jg = jg + 1 }
175    gd_p("\n" as *u8)
176
177    // ---- materialize champion as a real 2-input gcd organ, run at a HELD-OUT pair ----
178    let ta: i64 = gd_a(NTRAIN)
179    let tb: i64 = gd_b(NTRAIN)
180    let path: *u8 = sys_mmap(512); var po: i64 = 0
181    po = gd_cat(path, po, "runtime/_hdl_build/" as *u8); po = gd_cat(path, po, base_name); po = gd_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 = gd_cat(buf, o, "// DISCOVERED BY nx_evo_gcd (evolved 2-register Euclid from examples) -- a real while loop, at a HELD-OUT (a,b). license_tier: ORIGINAL\n" as *u8)
184    o = gd_cat(buf, o, "import \"nx_syscalls.nx\"\nfunc main() -> i64 {\n    var r0: i64 = " as *u8); o = gd_catn(buf, o, ta); o = gd_cat(buf, o, "\n    var r1: i64 = " as *u8); o = gd_catn(buf, o, tb); o = gd_cat(buf, o, "\n    var swp: i64 = 0\n    var guard: i64 = 0\n    while r1 != 0 {\n        if guard >= " as *u8); o = gd_catn(buf, o, GCD_CAP); o = gd_cat(buf, o, " { r1 = 0 } else {\n" as *u8)
185    jg = 0
186    while jg < EVO_BODY { o = gd_emit_op(buf, o, best[jg]); jg = jg + 1 }
187    o = gd_cat(buf, o, "            guard = guard + 1\n        }\n    }\n" as *u8)
188    o = gd_cat(buf, o, "    sys_write(1, \"RESULT=\" as *u8, 7)\n    var mm: i64 = r0\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 { gd_p("GCD verdict=RED reason=champion-unwritable\n" as *u8); return 1 }
191    sys_write(fd, buf, o); sys_close(fd)
192    gd_p("GCD champion written: " as *u8); gd_p(path); gd_p(" (gcd at held-out a=" as *u8); gd_pn(ta); gd_p(" b=" as *u8); gd_pn(tb); gd_p(", expect " as *u8); gd_pn(gd_g(NTRAIN)); gd_p(")\n" as *u8)
193    return 0
194}
nx_evo_gcd.nx source

`nx_evo_gcd.nx` source
