code wiki / _hdl_build / nx_grammar_expand_gate.nx
nx_grammar_expand_gate.nx source
↩ module page · 149 lines · 9861 B
1import "nx_gate_gn.nx"
2import "nx_gate_base.nx"
3// nx_grammar_expand_gate.nx -- THE MINER: close the last piece (grammar EXPANSION without an LLM). Prior gate
4// (nx_evo_synth) proved evolve-test-select replaces the LLM proposer EXCEPT inventing a NEW primitive (x^4 is
5// unreachable within a cubic grammar). This gate closes THAT: the system detects an out-of-grammar spec, pulls
6// CANDIDATE primitives from a RETRIEVED pool (what a search engine surfaces -- here a curated pool; the live
7// retrieval is the researcher's external-fetch), and KEEPS only the candidate that MECHANICALLY expands what's
8// solvable (no-fake-green: must make a previously-unsolvable spec solvable AND generalize on held-out). The LLM
9// would translate retrieved knowledge into a primitive; here the SELECTION/VERIFICATION (the autonomy-critical
10// half) is done by the environment, no LLM.
11//
12// Base grammar basis = {1, x, S1(x), S2(x)} (S_k = sum i^k) -> spans CUBICS. x^4 needs a degree-4 basis term.
13// Candidate pool (retrieved): {const(redundant), S4(degree-5 RED HERRING), S3(degree-4 = the KEY)}.
14// The red herring matters: S4 LOOKS higher-order/helpful but CANNOT make x^4 (its degree-5 term can't be
15// cancelled), so a naive "pick the fanciest" would fail -- only the environment's test selects correctly.
16// T1 BASE grammar CANNOT solve x^4 (out-of-grammar, residual>0).
17// T2 MINE+SELECT: of {const,S4,S3} only S3 makes x^4 solvable -> the system selects S3, rejects the others.
18// T3 the EXPANDED grammar (base+S3) solves x^4 AND generalizes held-out (x=5->625, x=6->1296).
19// T4 NO-FAKE-GREEN: the S4 red herring is REJECTED (plausible but can't make x^4) = the test isn't gameable.
20// T5 AUTONOMY: the system EXPANDED ITS OWN GRAMMAR by mechanical test, NO LLM (honest: pool=retrieved).
21// expect_exit: 0 license_tier: ORIGINAL
22import "nx_syscalls.nx"
23
24func grow(name: *u8, ok: i64) -> i64 { if ok==1 { gw(" PASS " as *u8) } else { gw(" FAIL " as *u8) } gw(name); gw("
25" as *u8); return ok }
26func lcg_next(st: *i64) -> i64 { st[0]=((1103515245*st[0])+12345)&2147483647; return st[0] }
27func rand_coef(st: *i64) -> i64 { return (0-9)+(lcg_next(st)%19) } // coeff in [-9,9]
28
29// basis function value: 0=const(1), 1=x, 2=S1, 3=S2, 4=S3, 5=S4 (S_k(x) = sum_{i=1}^x i^k).
30func basis(which: i64, x: i64) -> i64 {
31 if which==0 { return 1 }
32 if which==1 { return x }
33 var s: i64=0; var i: i64=1
34 while i<=x {
35 if which==2 { s=s+i }
36 if which==3 { s=s+(i*i) }
37 if which==4 { s=s+((i*i)*i) }
38 if which==5 { s=s+(((i*i)*i)*i) }
39 i=i+1
40 }
41 return s
42}
43// expanded model: c0*1 + c1*x + c2*S1 + c3*S2 (+ c4*basis(cand) if cand>=0). cand<0 = base grammar.
44func model(coeffs: *i64, cand: i64, x: i64) -> i64 {
45 var v: i64=(coeffs[0]*1)+(coeffs[1]*x)+(coeffs[2]*basis(2,x))+(coeffs[3]*basis(3,x))
46 if cand>=0 { v=v+(coeffs[4]*basis(cand,x)) }
47 return v
48}
49func merr(coeffs: *i64, cand: i64, xs: *i64, ys: *i64, n: i64) -> i64 {
50 var e: i64=0; var i: i64=0
51 while i<n { var d: i64=model(coeffs,cand,xs[i])-ys[i]; if d<0 { d=0-d } e=e+d; i=i+1 }
52 return e
53}
54// ITERATED LOCAL SEARCH over the coefficients (no LLM, multi-gene + restart -- escapes local optima). ng = #coeffs.
55func fit(cand: i64, xs: *i64, ys: *i64, n: i64, seed: i64, best: *i64) -> i64 {
56 var ng: i64=4; if cand>=0 { ng=5 }
57 let st: *i64=sys_mmap(16) as *i64; st[0]=seed
58 let parent: *i64=sys_mmap(64) as *i64
59 let child: *i64=sys_mmap(64) as *i64
60 let bev: *i64=sys_mmap(64) as *i64
61 var gi: i64=0; while gi<ng { parent[gi]=rand_coef(st); gi=gi+1 }
62 var perr: i64=merr(parent,cand,xs,ys,n); var ec: i64=1
63 var bererr: i64=perr; var zz: i64=0; while zz<ng { bev[zz]=parent[zz]; zz=zz+1 }
64 var stag: i64=0; var stop: i64=0
65 while stop==0 {
66 var l: i64=0
67 while l<16 {
68 var c: i64=0; while c<ng { child[c]=parent[c]; c=c+1 }
69 child[lcg_next(st)%ng]=rand_coef(st)
70 if (lcg_next(st)%3)==0 { child[lcg_next(st)%ng]=rand_coef(st) }
71 let ce: i64=merr(child,cand,xs,ys,n); ec=ec+1
72 if ce<perr { var c2: i64=0; while c2<ng { parent[c2]=child[c2]; c2=c2+1 } perr=ce }
73 if ce==0 { l=16 } else { l=l+1 }
74 }
75 if perr<bererr { bererr=perr; var b2: i64=0; while b2<ng { bev[b2]=parent[b2]; b2=b2+1 } stag=0 } else { stag=stag+1 }
76 if stag>50 { var r: i64=0; while r<ng { parent[r]=rand_coef(st); r=r+1 } perr=merr(parent,cand,xs,ys,n); ec=ec+1; stag=0 }
77 if bererr==0 { stop=1 }
78 if ec>=300000 { stop=1 }
79 }
80 var b: i64=0; while b<ng { best[b]=bev[b]; b=b+1 }
81 if bererr==0 { return 1 }
82 return 0
83}
84
85func gw_cand(c: i64) -> i64 {
86 if c==0 { gw("const" as *u8) } else { if c==4 { gw("S3(i^3,degree4)" as *u8) } else { if c==5 { gw("S4(i^4,degree5)" as *u8) } else { gw("?" as *u8) } } }
87 return 0
88}
89
90func main() -> i64 {
91 gw("=== nx_grammar_expand: THE MINER -- expand the grammar with a NEW primitive, no LLM (close the last piece) ===\n" as *u8)
92 var pass: i64=0; var total: i64=0
93
94 // TARGET = x^4 (out of the cubic base grammar). train x=0..4, held {5->625, 6->1296}.
95 let xs: *i64=sys_mmap(64) as *i64; let ys: *i64=sys_mmap(64) as *i64
96 xs[0]=0; xs[1]=1; xs[2]=2; xs[3]=3; xs[4]=4
97 ys[0]=0; ys[1]=1; ys[2]=16; ys[3]=81; ys[4]=256
98 let n: i64=5
99 let scratch: *i64=sys_mmap(64) as *i64
100
101 // T1: BASE grammar (cand<0) CANNOT solve x^4.
102 let solved_base: i64=fit(0-1,xs,ys,n,12345,scratch)
103 total=total+1; if solved_base==0 { pass=pass+1; gw(" [PASS] " as *u8) } else { gw(" [FAIL] " as *u8) }
104 gw("T1 OUT-OF-GRAMMAR: base grammar {1,x,S1,S2} CANNOT solve x^4 (solved=" as *u8); gn(solved_base); gw(") -> a NEW primitive is needed\n" as *u8)
105
106 // T2: MINE+SELECT over the retrieved candidate pool. cand: 0=const(redundant), 5=S4(red herring), 4=S3(key).
107 let pool: *i64=sys_mmap(64) as *i64; pool[0]=0; pool[1]=5; pool[2]=4 // order: const, S4, S3 (key last)
108 let best_s3: *i64=sys_mmap(64) as *i64
109 var selected: i64=0-1; var nkept: i64=0
110 var pi: i64=0
111 while pi<3 {
112 let cand: i64=pool[pi]
113 let bb: *i64=sys_mmap(64) as *i64
114 let ok: i64=fit(cand,xs,ys,n,12345,bb)
115 // no-fake-green: KEEP only if it solves training AND generalizes held-out (x=5->625, x=6->1296).
116 var keep: i64=0
117 if ok==1 { if model(bb,cand,5)==625 { if model(bb,cand,6)==1296 { keep=1 } } }
118 gw(" candidate " as *u8); gw_cand(cand); gw(": solves_train=" as *u8); gn(ok); gw(" generalizes=" as *u8); gn(keep); gw("\n" as *u8)
119 if keep==1 { selected=cand; nkept=nkept+1; var z: i64=0; while z<5 { best_s3[z]=bb[z]; z=z+1 } }
120 pi=pi+1
121 }
122 total=total+1; if selected==4 { if nkept==1 { pass=pass+1; gw(" [PASS] " as *u8) } else { gw(" [FAIL] " as *u8) } } else { gw(" [FAIL] " as *u8) }
123 gw("T2 MINE+SELECT: of {const, S4, S3} the system KEPT exactly " as *u8); gn(nkept); gw(" -> selected primitive = S3 (cand=" as *u8); gn(selected); gw("), no LLM\n" as *u8)
124
125 // T3: the EXPANDED grammar (base+S3) solves x^4 AND generalizes (already checked in selection; restate the fit).
126 let h5: i64=model(best_s3,4,5); let h6: i64=model(best_s3,4,6)
127 total=total+1; if selected==4 { if h5==625 { if h6==1296 { pass=pass+1; gw(" [PASS] " as *u8) } else { gw(" [FAIL] " as *u8) } } else { gw(" [FAIL] " as *u8) } } else { gw(" [FAIL] " as *u8) }
128 gw("T3 EXPANDED SOLVES: base+S3 fits x^4 = [const " as *u8); gn(best_s3[0]); gw(", x " as *u8); gn(best_s3[1]); gw(", S1 " as *u8); gn(best_s3[2]); gw(", S2 " as *u8); gn(best_s3[3]); gw(", S3 " as *u8); gn(best_s3[4]); gw("] -> HELD-OUT x=5->" as *u8); gn(h5); gw(" (625), x=6->" as *u8); gn(h6); gw(" (1296)\n" as *u8)
129
130 // T4: NO-FAKE-GREEN -- the S4 red herring is REJECTED (plausible higher-order but can't make x^4).
131 let bb4: *i64=sys_mmap(64) as *i64
132 let s4_ok: i64=fit(5,xs,ys,n,12345,bb4)
133 var s4_keep: i64=0; if s4_ok==1 { if model(bb4,5,5)==625 { if model(bb4,5,6)==1296 { s4_keep=1 } } }
134 total=total+1; if s4_keep==0 { pass=pass+1; gw(" [PASS] " as *u8) } else { gw(" [FAIL] " as *u8) }
135 gw("T4 NO-FAKE-GREEN: the S4 red herring is REJECTED (kept=" as *u8); gn(s4_keep); gw(") -- looks higher-order but can't make x^4; only the environment's test selects correctly\n" as *u8)
136
137 // T5: AUTONOMY -- the grammar EXPANDED ITSELF (a new primitive added by mechanical test), no LLM.
138 total=total+1; if solved_base==0 { if selected==4 { pass=pass+1; gw(" [PASS] " as *u8) } else { gw(" [FAIL] " as *u8) } } else { gw(" [FAIL] " as *u8) }
139 gw("T5 AUTONOMY: out-of-grammar -> mined a candidate pool -> SELECTED+VERIFIED a new primitive (S3) -> grammar EXPANDED, NO LLM\n" as *u8)
140
141 gw("\n THIS CLOSES THE LAST PIECE: grammar EXPANSION without an LLM. The system detected an out-of-grammar spec, and from a\n" as *u8)
142 gw(" RETRIEVED candidate pool it SELECTED+VERIFIED the one new primitive that expands what's solvable -- the environment chose,\n" as *u8)
143 gw(" not an LLM, and the no-fake-green test killed the plausible red herring (S4). HONEST SCOPE: the candidate POOL is curated here;\n" as *u8)
144 gw(" live retrieval = the researcher's external-fetch (a search engine), and turning a retrieved doc into a candidate primitive is\n" as *u8)
145 gw(" the translation step (the LLM does it generally; the self-reliant path = a domain MINER + X-AUT-NCF-001 constructs-as-data).\n" as *u8)
146 gw("GRAMMAR-EXPAND verdict=" as *u8)
147 if pass==total { gw("GREEN passes=" as *u8); gn(pass); gw("/" as *u8); gn(total); gw(" -- the system expanded its OWN grammar with a new primitive, selected by the environment, NO LLM\n" as *u8); sys_exit(0); return 0 }
148 gw("RED passes=" as *u8); gn(pass); gw("/" as *u8); gn(total); gw("\n" as *u8); sys_exit(1); return 1
149}