nx_array_ops.nx source
↩ module page · 470 lines · 14917 B
1// nx_array_ops.nx -- language-level higher-order array primitives.
2//
3// User cardinal 2026-05-15: "I want the language to be as powerful as
4// possible on the prerequisites... that's where Javascript and Python
5// are doing good work."
6//
7// What every program needs over arrays: map, filter, reduce, find,
8// sort, percentile, argmax/argmin, mean, variance, unique, contains.
9// Python has these in stdlib (operator + itertools + statistics);
10// JS has them as Array methods (.map / .filter / .reduce / .find).
11// Both shaped programming for the last 20 years. NishiLang absorbs
12// them here at the substrate-prerequisite layer.
13//
14// NO-CLOSURE-NEEDED DESIGN: NishiLang doesn't have first-class function
15// values yet. Instead of forcing callers to write hand-loops, this
16// primitive ships SEALED-ENUM OP KINDS that the substrate dispatches
17// internally. Coverage: ~80% of real-world array operations.
18// The remaining 20% (truly custom predicates) callers write a while
19// loop, same as today. When function-pointer / closure support
20// lands (queued nxc2 work), nx_array_map_fn / _filter_fn / _reduce_fn
21// variants extend this primitive additively.
22//
23// OPERATES ON: arrays of nx_int (the substrate-wide arithmetic type
24// from nx_tier.nx). Same primitive over indices, counts, Q10
25// fractions, IDs, anything that fits in nx_int.
26//
27// genealogy_id: numpy_oliphant_2006 + apl_iverson_1962 +
28// python_pep_3132_unpacking + js_es5_array_methods_2009
29// lineage_id: array_ops_language_prerequisite
30
31// nx_safety_envelope:
32// intended_use: AUTO_APPLIED -- primitive-specific tuning queued
33// sil_target: SIL1
34// evidence: [bulk_applied_2026-05-16, see-file-comment-for-detail]
35// verdict: NOT_YET_EVALUATED
36
37import "nx_syscalls.nx"
38import "nx_tier.nx"
39
40const NX_AOP_Q: nx_int = 1024
41
42// ===== Sealed-enum REDUCE op kinds ===================================
43
44const NX_REDUCE_SUM: nx_int = 0
45const NX_REDUCE_PRODUCT: nx_int = 1
46const NX_REDUCE_MIN: nx_int = 2
47const NX_REDUCE_MAX: nx_int = 3
48const NX_REDUCE_COUNT: nx_int = 4
49const NX_REDUCE_AND: nx_int = 5 // bitwise AND
50const NX_REDUCE_OR: nx_int = 6 // bitwise OR
51const NX_REDUCE_XOR: nx_int = 7 // bitwise XOR
52const NX_REDUCE_N_OPS: nx_int = 8
53
54// ===== Sealed-enum FILTER predicate kinds =============================
55
56const NX_FILTER_GT_ZERO: nx_int = 0
57const NX_FILTER_LT_ZERO: nx_int = 1
58const NX_FILTER_GTE_ZERO: nx_int = 2
59const NX_FILTER_LTE_ZERO: nx_int = 3
60const NX_FILTER_NON_ZERO: nx_int = 4
61const NX_FILTER_ZERO: nx_int = 5
62const NX_FILTER_EVEN: nx_int = 6
63const NX_FILTER_ODD: nx_int = 7
64const NX_FILTER_GT_PARAM: nx_int = 8 // uses param
65const NX_FILTER_LT_PARAM: nx_int = 9
66const NX_FILTER_EQ_PARAM: nx_int = 10
67const NX_FILTER_N_PREDS: nx_int = 11
68
69// ===== Sealed-enum MAP function kinds =================================
70
71const NX_MAP_ABS: nx_int = 0
72const NX_MAP_NEGATE: nx_int = 1
73const NX_MAP_SQUARE: nx_int = 2
74const NX_MAP_DOUBLE: nx_int = 3
75const NX_MAP_HALVE: nx_int = 4
76const NX_MAP_ADD_PARAM: nx_int = 5 // out[i] = arr[i] + param
77const NX_MAP_SUB_PARAM: nx_int = 6
78const NX_MAP_MUL_PARAM: nx_int = 7
79const NX_MAP_DIV_PARAM: nx_int = 8
80const NX_MAP_CLAMP_Q10: nx_int = 9 // clamp to [0, Q]
81const NX_MAP_CLAMP_SIGNED_Q10: nx_int = 10 // clamp to [-Q, +Q]
82const NX_MAP_SIGN: nx_int = 11 // -1 / 0 / +1
83const NX_MAP_N_OPS: nx_int = 12
84
85// ===== Helpers ========================================================
86
87func _aop_abs(x: nx_int) -> nx_int {
88 if x < 0 { return -x }
89 return x
90}
91
92func _aop_sign(x: nx_int) -> nx_int {
93 if x > 0 { return 1 }
94 if x < 0 { return -1 }
95 return 0
96}
97
98// ===== REDUCE =========================================================
99//
100// Single-pass reduction over the array. Op kind determines accumulator
101// initialization + step function.
102
103func nx_array_reduce(arr: *nx_int, n: nx_int, op: nx_int) -> nx_int {
104 if n <= 0 {
105 if op == NX_REDUCE_PRODUCT { return 1 } // identity for product
106 return 0
107 }
108 var acc: nx_int = arr[0]
109 if op == NX_REDUCE_PRODUCT { acc = arr[0] }
110 if op == NX_REDUCE_COUNT { acc = 0 }
111 if op == NX_REDUCE_AND { acc = arr[0] }
112 if op == NX_REDUCE_OR { acc = arr[0] }
113 if op == NX_REDUCE_XOR { acc = arr[0] }
114
115 var i: nx_int = 1
116 if op == NX_REDUCE_COUNT { i = 0 }
117 while i < n {
118 let v: nx_int = arr[i]
119 if op == NX_REDUCE_SUM { acc = acc + v }
120 if op == NX_REDUCE_PRODUCT { acc = acc * v }
121 if op == NX_REDUCE_MIN { if v < acc { acc = v } }
122 if op == NX_REDUCE_MAX { if v > acc { acc = v } }
123 if op == NX_REDUCE_COUNT { acc = acc + 1 }
124 if op == NX_REDUCE_AND { acc = acc & v }
125 if op == NX_REDUCE_OR { acc = acc | v }
126 if op == NX_REDUCE_XOR { acc = acc ^ v }
127 i = i + 1
128 }
129 return acc
130}
131
132// ===== Convenience wrappers around REDUCE =============================
133
134func nx_array_sum(arr: *nx_int, n: nx_int) -> nx_int {
135 return nx_array_reduce(arr, n, NX_REDUCE_SUM)
136}
137
138func nx_array_product(arr: *nx_int, n: nx_int) -> nx_int {
139 return nx_array_reduce(arr, n, NX_REDUCE_PRODUCT)
140}
141
142func nx_array_min(arr: *nx_int, n: nx_int) -> nx_int {
143 return nx_array_reduce(arr, n, NX_REDUCE_MIN)
144}
145
146func nx_array_max(arr: *nx_int, n: nx_int) -> nx_int {
147 return nx_array_reduce(arr, n, NX_REDUCE_MAX)
148}
149
150// Integer mean: sum / n; rounds toward zero (i64 div semantics).
151func nx_array_mean(arr: *nx_int, n: nx_int) -> nx_int {
152 if n <= 0 { return 0 }
153 return nx_array_sum(arr, n) / n
154}
155
156// Range = max - min.
157func nx_array_range(arr: *nx_int, n: nx_int) -> nx_int {
158 if n <= 0 { return 0 }
159 return nx_array_max(arr, n) - nx_array_min(arr, n)
160}
161
162// Sample variance (population variance when divided by n; sample by n-1).
163// Returns Q10 of variance per population semantics. Q10 scaling is
164// natural here -- variance is in the same units as values squared.
165func nx_array_variance_pop(arr: *nx_int, n: nx_int) -> nx_int {
166 if n <= 0 { return 0 }
167 let mean: nx_int = nx_array_mean(arr, n)
168 var sum_sq: nx_int = 0
169 var i: nx_int = 0
170 while i < n {
171 let d: nx_int = arr[i] - mean
172 sum_sq = sum_sq + d * d
173 i = i + 1
174 }
175 return sum_sq / n
176}
177
178// ===== FILTER =========================================================
179//
180// Copies arr[i] to out[] when predicate matches. Returns the count of
181// values written (also the effective length of out). param is the
182// threshold value for GT_PARAM / LT_PARAM / EQ_PARAM kinds.
183
184func _aop_filter_match(v: nx_int, pred: nx_int, param: nx_int) -> nx_int {
185 if pred == NX_FILTER_GT_ZERO { if v > 0 { return 1 } }
186 if pred == NX_FILTER_LT_ZERO { if v < 0 { return 1 } }
187 if pred == NX_FILTER_GTE_ZERO { if v >= 0 { return 1 } }
188 if pred == NX_FILTER_LTE_ZERO { if v <= 0 { return 1 } }
189 if pred == NX_FILTER_NON_ZERO { if v != 0 { return 1 } }
190 if pred == NX_FILTER_ZERO { if v == 0 { return 1 } }
191 if pred == NX_FILTER_EVEN {
192 let r: nx_int = v - (v / 2) * 2
193 if r == 0 { return 1 }
194 }
195 if pred == NX_FILTER_ODD {
196 let r: nx_int = v - (v / 2) * 2
197 if r != 0 { return 1 }
198 }
199 if pred == NX_FILTER_GT_PARAM { if v > param { return 1 } }
200 if pred == NX_FILTER_LT_PARAM { if v < param { return 1 } }
201 if pred == NX_FILTER_EQ_PARAM { if v == param { return 1 } }
202 return 0
203}
204
205func nx_array_filter(arr: *nx_int, n: nx_int, pred: nx_int, param: nx_int,
206 out: *nx_int, max_out: nx_int) -> nx_int {
207 var written: nx_int = 0
208 var i: nx_int = 0
209 while i < n {
210 if _aop_filter_match(arr[i], pred, param) == 1 {
211 if written < max_out {
212 out[written] = arr[i]
213 written = written + 1
214 }
215 }
216 i = i + 1
217 }
218 return written
219}
220
221// Counts matches WITHOUT writing to an output (cheaper when caller only
222// needs the count).
223func nx_array_count_matching(arr: *nx_int, n: nx_int, pred: nx_int, param: nx_int) -> nx_int {
224 var c: nx_int = 0
225 var i: nx_int = 0
226 while i < n {
227 if _aop_filter_match(arr[i], pred, param) == 1 { c = c + 1 }
228 i = i + 1
229 }
230 return c
231}
232
233// ===== MAP ===========================================================
234//
235// Writes arr.map(op) to out. out may alias arr (in-place) -- substrate
236// reads arr[i] before writing out[i].
237
238func _aop_map_one(v: nx_int, op: nx_int, param: nx_int) -> nx_int {
239 if op == NX_MAP_ABS { return _aop_abs(v) }
240 if op == NX_MAP_NEGATE { return -v }
241 if op == NX_MAP_SQUARE { return v * v }
242 if op == NX_MAP_DOUBLE { return v * 2 }
243 if op == NX_MAP_HALVE { return v / 2 }
244 if op == NX_MAP_ADD_PARAM { return v + param }
245 if op == NX_MAP_SUB_PARAM { return v - param }
246 if op == NX_MAP_MUL_PARAM { return v * param }
247 if op == NX_MAP_DIV_PARAM {
248 if param == 0 { return 0 }
249 return v / param
250 }
251 if op == NX_MAP_CLAMP_Q10 {
252 if v < 0 { return 0 }
253 if v > NX_AOP_Q { return NX_AOP_Q }
254 return v
255 }
256 if op == NX_MAP_CLAMP_SIGNED_Q10 {
257 if v < -NX_AOP_Q { return -NX_AOP_Q }
258 if v > NX_AOP_Q { return NX_AOP_Q }
259 return v
260 }
261 if op == NX_MAP_SIGN { return _aop_sign(v) }
262 return v
263}
264
265func nx_array_map(arr: *nx_int, n: nx_int, op: nx_int, param: nx_int,
266 out: *nx_int) -> nx_int {
267 var i: nx_int = 0
268 while i < n {
269 out[i] = _aop_map_one(arr[i], op, param)
270 i = i + 1
271 }
272 return 0
273}
274
275// ===== FIND / CONTAINS / argmin / argmax =============================
276
277// Returns first index where arr[i] == value, or -1.
278func nx_array_find(arr: *nx_int, n: nx_int, value: nx_int) -> nx_int {
279 var i: nx_int = 0
280 while i < n {
281 if arr[i] == value { return i }
282 i = i + 1
283 }
284 return -1
285}
286
287// Returns 1 if value is in arr, 0 otherwise.
288func nx_array_contains(arr: *nx_int, n: nx_int, value: nx_int) -> nx_int {
289 if nx_array_find(arr, n, value) >= 0 { return 1 }
290 return 0
291}
292
293// Index of the MIN value (first occurrence; -1 if empty).
294func nx_array_argmin(arr: *nx_int, n: nx_int) -> nx_int {
295 if n <= 0 { return -1 }
296 var best: nx_int = arr[0]
297 var idx: nx_int = 0
298 var i: nx_int = 1
299 while i < n {
300 if arr[i] < best {
301 best = arr[i]
302 idx = i
303 }
304 i = i + 1
305 }
306 return idx
307}
308
309// Index of the MAX value (first occurrence; -1 if empty).
310func nx_array_argmax(arr: *nx_int, n: nx_int) -> nx_int {
311 if n <= 0 { return -1 }
312 var best: nx_int = arr[0]
313 var idx: nx_int = 0
314 var i: nx_int = 1
315 while i < n {
316 if arr[i] > best {
317 best = arr[i]
318 idx = i
319 }
320 i = i + 1
321 }
322 return idx
323}
324
325// ===== ALL / ANY (sealed predicate) ==================================
326
327func nx_array_all(arr: *nx_int, n: nx_int, pred: nx_int, param: nx_int) -> nx_int {
328 var i: nx_int = 0
329 while i < n {
330 if _aop_filter_match(arr[i], pred, param) == 0 { return 0 }
331 i = i + 1
332 }
333 return 1
334}
335
336func nx_array_any(arr: *nx_int, n: nx_int, pred: nx_int, param: nx_int) -> nx_int {
337 var i: nx_int = 0
338 while i < n {
339 if _aop_filter_match(arr[i], pred, param) == 1 { return 1 }
340 i = i + 1
341 }
342 return 0
343}
344
345// ===== REVERSE (in-place) =============================================
346
347func nx_array_reverse(arr: *nx_int, n: nx_int) -> nx_int {
348 if n <= 1 { return 0 }
349 var lo: nx_int = 0
350 var hi: nx_int = n - 1
351 while lo < hi {
352 let tmp: nx_int = arr[lo]
353 arr[lo] = arr[hi]
354 arr[hi] = tmp
355 lo = lo + 1
356 hi = hi - 1
357 }
358 return 0
359}
360
361// ===== SORT (insertion sort; O(n^2) but stable + good cache behavior
362// for typical small substrate arrays) =================================
363
364func nx_array_sort_asc(arr: *nx_int, n: nx_int) -> nx_int {
365 var i: nx_int = 1
366 while i < n {
367 let key: nx_int = arr[i]
368 var j: nx_int = i - 1
369 var done: nx_int = 0
370 while done == 0 {
371 if j < 0 {
372 done = 1
373 } else {
374 if arr[j] <= key {
375 done = 1
376 } else {
377 arr[j + 1] = arr[j]
378 j = j - 1
379 }
380 }
381 }
382 arr[j + 1] = key
383 i = i + 1
384 }
385 return 0
386}
387
388func nx_array_sort_desc(arr: *nx_int, n: nx_int) -> nx_int {
389 nx_array_sort_asc(arr, n)
390 nx_array_reverse(arr, n)
391 return 0
392}
393
394// ===== MEDIAN / PERCENTILE (require sorted input or copy) =============
395//
396// nx_array_median copies the input to scratch buffer, sorts, returns
397// the middle element. Caller provides scratch of length n.
398
399func nx_array_median(arr: *nx_int, n: nx_int, scratch: *nx_int) -> nx_int {
400 if n <= 0 { return 0 }
401 var i: nx_int = 0
402 while i < n {
403 scratch[i] = arr[i]
404 i = i + 1
405 }
406 nx_array_sort_asc(scratch, n)
407 return scratch[n / 2]
408}
409
410// percentile_q10 in [0, Q]. Returns the value at floor(p * (n-1)).
411func nx_array_percentile(arr: *nx_int, n: nx_int, p_q10: nx_int,
412 scratch: *nx_int) -> nx_int {
413 if n <= 0 { return 0 }
414 if n == 1 { return arr[0] }
415 var p: nx_int = p_q10
416 if p < 0 { p = 0 }
417 if p > NX_AOP_Q { p = NX_AOP_Q }
418 var i: nx_int = 0
419 while i < n {
420 scratch[i] = arr[i]
421 i = i + 1
422 }
423 nx_array_sort_asc(scratch, n)
424 let idx: nx_int = (p * (n - 1)) / NX_AOP_Q
425 return scratch[idx]
426}
427
428// ===== UNIQUE (returns count of distinct values) =====================
429//
430// O(n^2) but avoids allocations. For large n use nx_sketch_hash_map.
431
432func nx_array_unique_count(arr: *nx_int, n: nx_int) -> nx_int {
433 if n <= 0 { return 0 }
434 var distinct: nx_int = 0
435 var i: nx_int = 0
436 while i < n {
437 var already_seen: nx_int = 0
438 var j: nx_int = 0
439 while j < i {
440 if arr[j] == arr[i] {
441 already_seen = 1
442 break
443 }
444 j = j + 1
445 }
446 if already_seen == 0 { distinct = distinct + 1 }
447 i = i + 1
448 }
449 return distinct
450}
451
452// ===== Sealed-enum validity ==========================================
453
454func nx_array_reduce_op_is_valid(op: nx_int) -> nx_int {
455 if op < 0 { return 0 }
456 if op >= NX_REDUCE_N_OPS { return 0 }
457 return 1
458}
459
460func nx_array_filter_pred_is_valid(p: nx_int) -> nx_int {
461 if p < 0 { return 0 }
462 if p >= NX_FILTER_N_PREDS { return 0 }
463 return 1
464}
465
466func nx_array_map_op_is_valid(op: nx_int) -> nx_int {
467 if op < 0 { return 0 }
468 if op >= NX_MAP_N_OPS { return 0 }
469 return 1
470}