1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
;;; Copyright (c) 2026 Nicholas Vermeulen
;;; SPDX-License-Identifier: AGPL-3.0-or-later
;; symreg.lisp — symbolic regression by genetic programming (Phase 4.1).
;;
;; Find a human-readable equation fitting data, as a pure-Lisp library:
;; candidate equations ARE Lisp expressions (lists), so generation,
;; crossover, and mutation are ordinary list surgery, and fitness turns a
;; candidate into a real callable via `(eval (list 'lambda vars expr))` —
;; the interpreter's own fast path, no meta-interpretation.
;;
;; (symreg data vars) ; data rows: ((inputs...) target)
;; (symreg data vars pop gens) ; explicit population/generation caps
;; => (expr mse generation) ; expr already simplified
;;
;; Deterministic: seeded LCG PRNG ((symreg-seed! n) to reseed), so runs are
;; reproducible and this library golden-tests (see symreg-test.lisp).
;; ── Seeded PRNG ───────────────────────────────────────────────────────────
;; ── Random expression trees ──────────────────────────────────────────────
;; Protected division, the classic GP guard: Rusty's `/` raises on a zero
;; divisor, and a random candidate WILL divide by zero somewhere in the
;; data. pdiv is total (returns 1 there), so every candidate is safe to run.
;; Op table rows are (name arity). Extend the vocabulary with
;; (symreg-ops! ...) — including MACRO building blocks: a block defined via
;; defmacro (e.g. (defmacro sq (e) `(* ,e ,e))) is legal GP vocabulary,
;; because fitness runs candidates through `eval`, which expands macros.
;; Blocks keep candidate trees small — the search explores a richer space
;; at the same tree depth (docs/ROADMAP.md 4.1, macro-based generation).
; integer in -5..5
;; ── Tree surgery (preorder indexing) ─────────────────────────────────────
;; sr-size (node count), sr-get (subtree at a preorder index), and sr-put
;; (rebuild with a subtree replaced) are native builtins (v0.39.0, interp.rs)
;; — the crossover/mutation hot path. Interpreted they were ~O(n^2) per op
;; (sr-get/sr-put recomputed sr-size on each sibling subtree). The natives
;; preserve the exact node count and preorder indexing, so PRNG draw order and
;; discovered equations stay bit-identical. Reference definitions:
;; (define (sr-size t) (if (pair? t) (+ 1 (sum (map sr-size (cdr t)))) 1))
;; (sr-get t i) => subtree at preorder index i (0 = whole tree)
;; (sr-put t i s) => t with the subtree at index i replaced by s
;; ── Fitness: MSE, with NaN → hard penalty ────────────────────────────────
;; With pdiv total, candidates can't raise; extreme values can still
;; overflow to inf (loses every comparison it should lose) or NaN (compares
;; false with everything, itself included — caught by the (= m m) test).
;; ── Variation ─────────────────────────────────────────────────────────────
; parsimony guard: oversized offspring are rejected
;; ── Selection: k-tournament on (expr fitness) pairs ──────────────────────
;; ── Finalization: sr-pdiv → / where provably safe ────────────────────────
;; The evolved equation uses protected division; if plain `/` produces the
;; identical MSE on the training data (i.e. no divisor is ever 0 there),
;; present the human the ordinary form.
;; ── Simplification: constant folding + algebraic identities ─────────────
;; ── The evolution loop ────────────────────────────────────────────────────