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
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
564
565
566
567
568
569
570
571
572
573
574
575
576
577
578
579
580
581
582
583
584
585
586
587
588
589
590
591
592
593
594
595
596
597
598
599
600
601
602
603
604
605
606
607
608
609
610
611
612
613
614
615
616
617
618
619
620
621
622
623
624
625
626
627
628
629
630
631
632
633
634
635
636
637
638
639
640
641
642
643
644
645
646
647
648
|
<head>
<link href="../favicon.ico" rel="shortcut icon" type="image/x-icon"/>
<link href="../style.css" rel="stylesheet"/>
<title>Specification: BQN inferred properties</title>
</head>
<div class="nav"><a href="https://github.com/mlochbaum/BQN">BQN</a> / <a href="../index.html">main</a> / <a href="index.html">spec</a></div>
<h1 id="specification-bqn-inferred-properties">Specification: BQN inferred properties</h1>
<p>BQN includes some simple deductive capabilities: detecting the type of empty array elements, the result of an empty reduction, and the Undo (<code><span class='Modifier'>⁼</span></code>) and Under (<code><span class='Modifier2'>⌾</span></code>) modifiers. These tasks are a kind of proof-based or constraint programming, and can never be solved completely (some instances will be undecidable) but can be solved in more instances by ever-more sophisticated algorithms. To allow implementers to develop more advanced implementations while offering some stability and portability to programmers, two kinds of specification are given here. First, constraints are given on the behavior of inferred properties. These are not exact and require some judgment on the part of the implementer. Second, behavior for common or useful cases is specified more precisely. Non-normative suggestions are also given as a reference for implementers.</p>
<p>For the specified cases, the given functions and modifiers refer to those particular representations. It is not necessary to detect equivalent representations, for example to reduce <code><span class='Paren'>(</span><span class='Function'>+-×</span><span class='Paren'>)</span><span class='Modifier'>⁼</span></code> to <code><span class='Function'>∨</span><span class='Modifier'>⁼</span></code>. However, it is necessary to identify computed functions and modifiers: for example <code><span class='Function'>F</span><span class='Modifier'>⁼</span></code> when the value of <code><span class='Function'>F</span></code> in the expression is <code><span class='Function'>∨</span></code>, or <code><span class='Paren'>(</span><span class='Number'>1</span><span class='Function'>⊑∧</span><span class='Ligature'>‿</span><span class='Function'>∨</span><span class='Paren'>)</span><span class='Modifier'>⁼</span></code>.</p>
<p>Failing to compute an inferred property for a function or array as it's created cannot cause an error. An error can only be caused when the missing inferred property is needed for a computation.</p>
<h2 id="identities">Identities</h2>
<p>When monadic Fold (<code><span class='Modifier'>´</span></code>) or Insert (<code><span class='Modifier'>˝</span></code>) is called on an array of length 0, BQN attempts to infer a right identity value for the function in order to determine the result. A right identity value for a dyadic function <code><span class='Function'>𝔽</span></code> is a value <code><span class='Value'>r</span></code> such that <code><span class='Value'>e</span><span class='Function'>≡</span><span class='Value'>e</span><span class='Function'>𝔽</span><span class='Value'>r</span></code> for any element <code><span class='Value'>e</span></code> in the domain. For such a value <code><span class='Value'>r</span></code>, the fold <code><span class='Value'>r</span> <span class='Function'>𝔽</span><span class='Modifier'>´</span> <span class='Value'>l</span></code> is equivalent to <code><span class='Function'>𝔽</span><span class='Modifier'>´</span> <span class='Value'>l</span></code> for a non-empty list <code><span class='Value'>l</span></code>, because the first application <code><span class='Paren'>(</span><span class='Number'>¯1</span><span class='Function'>⊑</span><span class='Value'>l</span><span class='Paren'>)</span> <span class='Function'>𝔽</span> <span class='Value'>r</span></code> gives <code><span class='Number'>¯1</span><span class='Function'>⊑</span><span class='Value'>l</span></code>, which is the starting point when no initial value is given. It's thus reasonable to define <code><span class='Function'>𝔽</span><span class='Modifier'>´</span> <span class='Value'>l</span></code> to be <code><span class='Value'>r</span> <span class='Function'>𝔽</span><span class='Modifier'>´</span> <span class='Value'>l</span></code> for an empty list <code><span class='Value'>l</span></code> as well, giving a result <code><span class='Value'>r</span></code>.</p>
<p>For Fold, the result of <code><span class='Function'>𝔽</span><span class='Modifier'>´</span></code> on an empty list is defined to be a right identity value for the <em>range</em> of <code><span class='Function'>𝔽</span></code>, if exactly one such value exists. If an identity can't be proven to uniquely exist, then an error results.</p>
<p>For Insert, <code><span class='Function'>𝔽</span><span class='Modifier'>˝</span></code> on an array of length 0 is defined similarly, but also depends on the cell shape <code><span class='Number'>1</span><span class='Function'>↓≢</span><span class='Value'>𝕩</span></code>. The required domain is the arrays of that shape that also lie in the range of <code><span class='Function'>𝔽</span></code> (over arbitrary arguments, not shape-restricted ones). Furthermore, an identity may be unique among all possible arguments as in the case of Fold, or it may be an array with shape <code><span class='Number'>1</span><span class='Function'>↓≢</span><span class='Value'>𝕩</span></code> and be unique among arrays with that shape. For example, with cell shape <code><span class='Number'>3</span><span class='Ligature'>‿</span><span class='Number'>2</span></code>, all of <code><span class='Number'>0</span></code>, <code><span class='Number'>2</span><span class='Function'>⥊</span><span class='Number'>0</span></code>, and <code><span class='Number'>3</span><span class='Ligature'>‿</span><span class='Number'>2</span><span class='Function'>⥊</span><span class='Number'>0</span></code> are identities for <code><span class='Function'>+</span></code>, but <code><span class='Number'>3</span><span class='Ligature'>‿</span><span class='Number'>2</span><span class='Function'>⥊</span><span class='Number'>0</span></code> can be used because it is the only indentity with shape <code><span class='Number'>3</span><span class='Ligature'>‿</span><span class='Number'>2</span></code>, while the other identities aren't unique and can't be used.</p>
<p>Identity values for the arithmetic primitives below must be recognized. Under Fold, the result is the given identity value, while under Insert, it is the identity value reshaped to the argument's cell shape.</p>
<table>
<thead>
<tr>
<th align="right">Id</th>
<th align="center">Fn</th>
<th align="center">Fn</th>
<th align="right">Id</th>
</tr>
</thead>
<tbody>
<tr>
<td align="right"><code><span class='Number'>0</span></code></td>
<td align="center"><code><span class='Function'>+</span></code></td>
<td align="center"><code><span class='Function'>-</span></code></td>
<td align="right"><code><span class='Number'>0</span></code></td>
</tr>
<tr>
<td align="right"><code><span class='Number'>1</span></code></td>
<td align="center"><code><span class='Function'>×</span></code></td>
<td align="center"><code><span class='Function'>÷</span></code></td>
<td align="right"><code><span class='Number'>1</span></code></td>
</tr>
<tr>
<td align="right"><code><span class='Number'>1</span></code></td>
<td align="center"><code><span class='Function'>⋆</span></code></td>
<td align="center"><code><span class='Function'>¬</span></code></td>
<td align="right"><code><span class='Number'>1</span></code></td>
</tr>
<tr>
<td align="right"><code><span class='Number'>∞</span></code></td>
<td align="center"><code><span class='Function'>⌊</span></code></td>
<td align="center"><code><span class='Function'>⌈</span></code></td>
<td align="right"><code><span class='Number'>¯∞</span></code></td>
</tr>
<tr>
<td align="right"><code><span class='Number'>0</span></code></td>
<td align="center"><code><span class='Function'>∨</span></code></td>
<td align="center"><code><span class='Function'>∧</span></code></td>
<td align="right"><code><span class='Number'>1</span></code></td>
</tr>
<tr>
<td align="right"><code><span class='Number'>0</span></code></td>
<td align="center"><code><span class='Function'>≠</span></code></td>
<td align="center"><code><span class='Function'>=</span></code></td>
<td align="right"><code><span class='Number'>1</span></code></td>
</tr>
<tr>
<td align="right"><code><span class='Number'>0</span></code></td>
<td align="center"><code><span class='Function'>></span></code></td>
<td align="center"><code><span class='Function'>≥</span></code></td>
<td align="right"><code><span class='Number'>1</span></code></td>
</tr>
</tbody>
</table>
<p>Additionally, the identity of <code><span class='Function'>∾</span><span class='Modifier'>˝</span></code> must be recognized: if <code><span class='Number'>0</span><span class='Function'>=≠</span><span class='Value'>𝕩</span></code> and <code><span class='Number'>1</span><span class='Function'><=</span><span class='Value'>𝕩</span></code>, then <code><span class='Function'>∾</span><span class='Modifier'>˝</span><span class='Value'>𝕩</span></code> is <code><span class='Paren'>(</span><span class='Number'>0</span><span class='Function'>∾</span><span class='Number'>2</span><span class='Function'>↓≢</span><span class='Value'>𝕩</span><span class='Paren'>)</span><span class='Function'>⥊</span><span class='Value'>𝕩</span></code>. If <code><span class='Number'>1</span><span class='Function'>==</span><span class='Value'>𝕩</span></code>, then there is no identity element, as the result of <code><span class='Function'>∾</span></code> always has rank at least 1, but the cell rank is 0.</p>
<h2 id="fill-elements">Fill elements</h2>
<p>Any BQN array can have a <em>fill element</em>, which is a sort of "default" value for the array. The reference implementations use <code><span class='Function'>Fill</span></code> to access this element, and it is used primarily for Take (<code><span class='Function'>↑</span></code>), First (<code><span class='Function'>⊑</span></code>), and Nudge (<code><span class='Function'>«</span></code>, <code><span class='Function'>»</span></code>). One way to extract the fill element of an array <code><span class='Value'>a</span></code> in BQN is <code><span class='Function'>⊑</span><span class='Number'>0</span><span class='Function'>⥊</span><span class='Value'>a</span></code>.</p>
<p>A fill element can be either <code><span class='Number'>0</span></code>, <code><span class='String'>' '</span></code>, or an array of valid fill elements. If the fill element is an array, then it may also have a fill element (since it is an ordinary BQN array). The fill element is meant to describe the shared structure of the elements of an array: for example, the fill element of an array of numbers should be <code><span class='Number'>0</span></code>, while the fill element for an array of variable-length lists should probably be <code><span class='Bracket'>⟨⟩</span></code>. However, the fill element, unlike other inferred properties, does not satisfy any particular constraints that relate it to its array. The fill element of a primitive's result, including functions derived from primitive modifiers, must depend only on its inputs.</p>
<p>In addition to the requirements below, the fill element for the value of a string literal is <code><span class='String'>' '</span></code>.</p>
<h3 id="required-functions">Required functions</h3>
<p>Combinators <code><span class='Function'>⊣⊢!</span><span class='Modifier'>˙˜´˝</span><span class='Modifier2'>∘○⊸⟜⊘◶⍟</span></code> do not affect fill element computation: if the combinator calls a function that computes a fill element, then that fill element must be retained if the result is passed to other functions or returned. <code><span class='Modifier2'>⍟</span></code> constructs arrays if its right operand is or contains arrays, and the fill elements of these arrays are not specified; converting <code><span class='Value'>𝕩</span></code> to a fill element is a reasonable choice in some cases but not others.</p>
<p>Arithmetic primitives—all valences of <code><span class='Function'>+-×÷⋆√⌊⌈|¬</span></code> and dyadic <code><span class='Function'>∧∨<>≠=≤≥</span></code>—obtain their fill elements by applying to the fill elements of the arguments. If this is an error, there is no fill element; otherwise, the fill element is the result, with all numbers in it changed to <code><span class='Number'>0</span></code> and all characters changed to <code><span class='String'>' '</span></code>.</p>
<p>Fill elements for many primitives are given in the table below. The "Fill" column indicates the strategy used to compute the result's fill. Fields <code><span class='Number'>0</span></code>, <code><span class='Value'>𝕩</span></code>, <code><span class='Number'>0</span><span class='Function'>↑</span><span class='Value'>𝕩</span></code>, and <code><span class='Number'>0</span><span class='Modifier2'>⚇</span><span class='Number'>0</span><span class='Value'>𝕩</span></code> indicate the fill directly, while <code><span class='Function'>⊢</span></code> and <code><span class='Value'>∩</span></code> indicate that the fill is to be computed from the argument fills (if not all arguments have fills, then the fill element is unspecified). For <code><span class='Function'>⊢</span></code>, the fill element of the result is the fill element of <code><span class='Value'>𝕩</span></code>. For <code><span class='Value'>∩</span></code>, the fill is equal to the fill values for multiple arrays, provided that they are all equal (it's unspecified if they are not all equal). In the two argument case, these arrays are <code><span class='Value'>𝕨</span></code> and <code><span class='Value'>𝕩</span></code>. In the one-argument case, they are the elements of <code><span class='Value'>𝕩</span></code>; however, if <code><span class='Value'>𝕩</span></code> is empty, then the result's fill is the fill of the fill of <code><span class='Value'>𝕩</span></code>.</p>
<table>
<thead>
<tr>
<th>Fill</th>
<th>Monads</th>
<th>Dyads</th>
<th>Modifiers</th>
</tr>
</thead>
<tbody>
<tr>
<td><code><span class='Function'>⊢</span></code></td>
<td><code><span class='Function'>∧∨⥊≍»«⌽⍉⊏⍷</span></code></td>
<td><code><span class='Function'>⥊↑↓↕⌽⍉/⊏</span></code></td>
<td><code><span class='Function'>𝔽</span><span class='Modifier'>`</span></code></td>
</tr>
<tr>
<td><code><span class='Number'>0</span></code></td>
<td><code><span class='Function'>≢/⍋⍒∊⊐⊒</span></code></td>
<td><code><span class='Function'>⍋⍒⊐⊒∊⍷</span></code></td>
<td></td>
</tr>
<tr>
<td><code><span class='Value'>𝕩</span></code></td>
<td><code><span class='Function'><</span></code></td>
<td></td>
<td></td>
</tr>
<tr>
<td><code><span class='Value'>∩</span></code></td>
<td><code><span class='Function'>>∾</span></code></td>
<td><code><span class='Function'>∾≍»«</span></code></td>
<td></td>
</tr>
<tr>
<td><code><span class='Number'>0</span><span class='Function'>↑</span><span class='Value'>𝕩</span></code></td>
<td><code><span class='Function'>↑↓</span></code></td>
<td></td>
<td></td>
</tr>
<tr>
<td><code><span class='Number'>0</span><span class='Modifier2'>⚇</span><span class='Number'>0</span><span class='Value'>𝕩</span></code></td>
<td><code><span class='Function'>↕</span></code></td>
<td></td>
<td></td>
</tr>
</tbody>
</table>
<p>For Group and Group Indices (<code><span class='Function'>⊔</span></code>), the fill element of the result and its elements are both specified: the fill element of each element of the result is the same as that of <code><span class='Value'>𝕩</span></code> for Group, and is <code><span class='Number'>0</span></code> for Group Indices. The fill element of the result is <code><span class='Paren'>(</span><span class='Number'>0</span><span class='Modifier2'>⚇</span><span class='Number'>1</span><span class='Value'>𝕨</span><span class='Paren'>)</span><span class='Function'>↑</span><span class='Value'>𝕩</span></code> for Group, and <code><span class='Function'>⥊</span><span class='Modifier2'>⟜</span><span class='Function'><</span><span class='Number'>0</span><span class='Modifier2'>⚇</span><span class='Number'>1</span><span class='Value'>𝕩</span></code> for Group Indices.</p>
<p>Fill elements of iteration modifiers such as <code><span class='Modifier'>¨⌜</span></code> are not specified. It is reasonable to define the fill element of <code><span class='Function'>𝔽</span><span class='Modifier'>⌜</span></code> or <code><span class='Function'>𝔽</span><span class='Modifier'>¨</span></code> to be <code><span class='Function'>𝔽</span></code> applied to the fill elements of the arguments. Regardless of definition, computing the fill element cannot cause side effects or an error.</p>
<h2 id="undo">Undo</h2>
<p>The Undo 1-modifier <code><span class='Modifier'>⁼</span></code>, given an operand <code><span class='Function'>𝔽</span></code> and argument <code><span class='Value'>𝕩</span></code>, and possibly a left argument <code><span class='Value'>𝕨</span></code>, finds a value <code><span class='Value'>y</span></code> such that <code><span class='Value'>𝕩</span><span class='Function'>≡</span><span class='Value'>𝕨</span><span class='Function'>𝔽</span><span class='Value'>y</span></code>, that is, an element of the pre-image of <code><span class='Value'>𝕩</span></code> under <code><span class='Function'>𝔽</span></code> or <code><span class='Value'>𝕨</span><span class='Function'>𝔽⊢</span></code>. Thus it satisfies the constraint <code><span class='Value'>𝕩</span> <span class='Function'>≡</span> <span class='Value'>𝕨</span><span class='Function'>𝔽</span><span class='Value'>𝕨</span><span class='Function'>𝔽</span><span class='Modifier'>⁼</span><span class='Value'>𝕩</span></code> (<code><span class='Value'>𝕨</span><span class='Function'>𝔽</span><span class='Modifier'>⁼</span><span class='Function'>⊢</span></code> is a <em>right inverse</em> of <code><span class='Value'>𝕨</span><span class='Function'>𝔽⊢</span></code>) provided <code><span class='Function'>𝔽</span><span class='Modifier'>⁼</span></code> and <code><span class='Function'>𝔽</span></code> both complete without error. <code><span class='Function'>𝔽</span><span class='Modifier'>⁼</span></code> should of course give an error if no inverse element exists, and can also fail if no inverse can be found. It is also preferred for <code><span class='Function'>𝔽</span><span class='Modifier'>⁼</span></code> to give an error if there are many choices of inverse with no clear way to choose one of them: for example, <code><span class='Number'>0</span><span class='Ligature'>‿</span><span class='Number'>0</span><span class='Function'>⍉</span><span class='Value'>m</span></code> returns the diagonal of matrix <code><span class='Value'>m</span></code>; <code><span class='Number'>0</span><span class='Ligature'>‿</span><span class='Number'>0</span><span class='Function'>⍉</span><span class='Modifier'>⁼</span><span class='Number'>2</span><span class='Ligature'>‿</span><span class='Number'>3</span></code> requires values to be chosen for the off-diagonal elements in its result. It is better to give an error, encouraging the programmer to use a fully-specified approach like <code><span class='Number'>2</span><span class='Ligature'>‿</span><span class='Number'>3</span><span class='Modifier2'>⌾</span><span class='Paren'>(</span><span class='Number'>0</span><span class='Ligature'>‿</span><span class='Number'>0</span><span class='Modifier2'>⊸</span><span class='Function'>⍉</span><span class='Paren'>)</span></code> applied to a matrix of initial elements, than to return a result that could be very different from other implementations.</p>
<p>When working with limited-precision numbers, it may be difficult or impossible to exactly invert the operand function. Instead, it is generally acceptable to perform a computation that, if done with unlimited precision, would exactly invert <code><span class='Function'>𝔽</span></code> computed with unlimited precision. This principle is the basis for the numeric inverses specified below. It is also acceptable to find an inverse by numeric methods, provided that the error in the inverse value found relative to an unlimited-precision inverse can be kept close to the inherent error in the implementation's number format.</p>
<p>Regardless of which cases for Undo are supported, the result of a call, and whether it is an error, must depend only on the values of the inputs <code><span class='Function'>𝔽</span></code>, <code><span class='Value'>𝕩</span></code>, and (if present) <code><span class='Value'>𝕨</span></code>.</p>
<h3 id="required-functions">Required functions</h3>
<p>Function inverses are given for one or two arguments, with cases where inverse support is not required left blank.</p>
<p>For arithmetic functions the implementations below may in some cases not give the closest inverse (that is, there may be some other <code><span class='Value'>y</span></code> so that <code><span class='Function'>F</span> <span class='Value'>y</span></code> is closer to <code><span class='Value'>x</span></code> than <code><span class='Function'>F</span> <span class='Function'>F</span><span class='Modifier'>⁼</span><span class='Value'>x</span></code>). Even in these cases the exact functions given below must be used.</p>
<table>
<thead>
<tr>
<th>Fn</th>
<th>1</th>
<th>2</th>
</tr>
</thead>
<tbody>
<tr>
<td><code><span class='Function'>+</span></code></td>
<td><code><span class='Function'>+</span></code></td>
<td><code><span class='Function'>-</span><span class='Modifier'>˜</span></code></td>
</tr>
<tr>
<td><code><span class='Function'>-</span></code></td>
<td><code><span class='Function'>-</span></code></td>
<td><code><span class='Function'>-</span></code></td>
</tr>
<tr>
<td><code><span class='Function'>×</span></code></td>
<td></td>
<td><code><span class='Function'>÷</span><span class='Modifier'>˜</span></code></td>
</tr>
<tr>
<td><code><span class='Function'>÷</span></code></td>
<td><code><span class='Function'>÷</span></code></td>
<td><code><span class='Function'>÷</span></code></td>
</tr>
<tr>
<td><code><span class='Function'>√</span></code></td>
<td><code><span class='Function'>×</span><span class='Modifier'>˜</span></code></td>
<td><code><span class='Function'>⋆</span><span class='Modifier'>˜</span></code></td>
</tr>
<tr>
<td><code><span class='Function'>∧</span></code></td>
<td></td>
<td><code><span class='Function'>÷</span><span class='Modifier'>˜</span></code></td>
</tr>
<tr>
<td><code><span class='Function'>¬</span></code></td>
<td><code><span class='Function'>¬</span></code></td>
<td><code><span class='Function'>¬</span></code></td>
</tr>
</tbody>
</table>
<p>Unlike these inverses, the logarithm function—base <em>e</em> for <code><span class='Function'>⋆</span><span class='Modifier'>⁼</span><span class='Value'>𝕩</span></code> and base <code><span class='Value'>𝕨</span></code> for <code><span class='Value'>𝕨</span><span class='Function'>⋆</span><span class='Modifier'>⁼</span><span class='Value'>𝕩</span></code>—does not have any strict precision requirements.</p>
<table>
<thead>
<tr>
<th>Fn</th>
<th>1</th>
<th>2</th>
</tr>
</thead>
<tbody>
<tr>
<td><code><span class='Function'>⋆</span></code></td>
<td><code><span class='Function'>Log</span></code></td>
<td><code><span class='Function'>÷</span><span class='Modifier'>˜</span><span class='Modifier2'>○</span><span class='Function'>Log</span></code></td>
</tr>
</tbody>
</table>
<p>The following structural functions have unique inverses, except in a few cases. Dyadic <code><span class='Function'>⍉</span></code> with repeated axes is excluded, and monadic <code><span class='Function'><</span></code> can only be inverted on a rank-0 array. Dyadic <code><span class='Function'>⊣</span></code> is invertible only if the arguments match, and in this case any return value is valid, but in BQN the shared argument value is returned. For <code><span class='Function'>/</span><span class='Modifier'>⁼</span></code> the argument must be a list of non-descending natural numbers, and the result's fill element is 0.</p>
<table>
<thead>
<tr>
<th>Fn</th>
<th>1</th>
<th>2</th>
</tr>
</thead>
<tbody>
<tr>
<td><code><span class='Function'>⊢</span></code></td>
<td><code><span class='Function'>⊢</span></code></td>
<td><code><span class='Function'>⊢</span></code></td>
</tr>
<tr>
<td><code><span class='Function'>⊣</span></code></td>
<td><code><span class='Function'>⊢</span></code></td>
<td><code><span class='Brace'>{</span><span class='Function'>!</span><span class='Value'>𝕨</span><span class='Function'>≡</span><span class='Value'>𝕩</span><span class='Separator'>⋄</span><span class='Value'>𝕩</span><span class='Brace'>}</span></code></td>
</tr>
<tr>
<td><code><span class='Function'><</span></code></td>
<td><code><span class='Brace'>{</span><span class='Function'>!</span><span class='Number'>0</span><span class='Function'>==</span><span class='Value'>𝕩</span><span class='Separator'>⋄</span><span class='Function'>!</span><span class='Number'>0</span><span class='Function'><≡</span><span class='Value'>𝕩</span><span class='Separator'>⋄</span><span class='Function'>⊑</span><span class='Value'>𝕩</span><span class='Brace'>}</span></code></td>
<td></td>
</tr>
<tr>
<td><code><span class='Function'>⌽</span></code></td>
<td><code><span class='Function'>⌽</span></code></td>
<td><code><span class='Function'>-</span><span class='Modifier2'>⊸</span><span class='Function'>⌽</span></code></td>
</tr>
<tr>
<td><code><span class='Function'>⍉</span></code></td>
<td><code><span class='Paren'>(</span><span class='Number'>1</span><span class='Function'>⌽↕</span><span class='Modifier2'>∘</span><span class='Function'>=</span><span class='Paren'>)</span><span class='Modifier2'>⊸</span><span class='Function'>⍉</span><span class='Modifier2'>⍟</span><span class='Paren'>(</span><span class='Number'>0</span><span class='Function'><=</span><span class='Paren'>)</span></code></td>
<td><code><span class='Brace'>{</span><span class='Function'>!∧</span><span class='Modifier'>´</span><span class='Function'>∊</span><span class='Value'>𝕨</span><span class='Separator'>⋄</span><span class='Value'>𝕨</span><span class='Function'>⍉</span><span class='Value'>𝕩</span><span class='Separator'>⋄</span><span class='Paren'>(</span><span class='Function'>⍋⍷</span><span class='Value'>𝕨</span><span class='Function'>∾↕=</span><span class='Value'>𝕩</span><span class='Paren'>)</span><span class='Function'>⍉</span><span class='Value'>𝕩</span><span class='Brace'>}</span></code></td>
</tr>
<tr>
<td><code><span class='Function'>/</span></code></td>
<td><code><span class='Function'>≠</span><span class='Modifier'>¨</span><span class='Modifier2'>∘</span><span class='Function'>⊔</span></code></td>
<td></td>
</tr>
</tbody>
</table>
<p>For a data value <code><span class='Value'>k</span></code>, the inverse <code><span class='Value'>𝕨k</span><span class='Modifier'>⁼</span><span class='Value'>𝕩</span></code> with or without a left argument is <code><span class='Value'>k</span><span class='Function'>⊣</span><span class='Modifier'>⁼</span><span class='Value'>𝕩</span></code>.</p>
<table>
<thead>
<tr>
<th>Fn</th>
<th>Inverse</th>
</tr>
</thead>
<tbody>
<tr>
<td><code><span class='Value'>k</span></code></td>
<td><code><span class='Brace'>{</span><span class='Function'>!</span><span class='Value'>k</span><span class='Function'>≡</span><span class='Value'>𝕩</span><span class='Separator'>⋄</span><span class='Value'>𝕩</span><span class='Brace'>}</span></code></td>
</tr>
</tbody>
</table>
<h3 id="optional-functions">Optional functions</h3>
<p>Several primitives are easily and uniquely undone, but doing so is not important for BQN programming. These primitives are listed below along with suggested algorithms to undo them. Unlike the implementations above, these functions are not valid in all cases, and the inputs must be validated or the results checked in order to use them.</p>
<table>
<thead>
<tr>
<th>Fn</th>
<th>1</th>
<th>2</th>
</tr>
</thead>
<tbody>
<tr>
<td><code><span class='Function'>×</span></code></td>
<td><code><span class='Function'>⊢</span></code></td>
<td></td>
</tr>
<tr>
<td><code><span class='Function'>∧</span></code></td>
<td><code><span class='Function'>⊢</span></code></td>
<td></td>
</tr>
<tr>
<td><code><span class='Function'>∨</span></code></td>
<td><code><span class='Function'>⊢</span></code></td>
<td><code><span class='Function'>-</span><span class='Modifier'>˜</span><span class='Function'>÷</span><span class='Number'>1</span><span class='Function'>-⊣</span></code></td>
</tr>
<tr>
<td><code><span class='Function'>∾</span></code></td>
<td></td>
<td><code><span class='Brace'>{</span><span class='Paren'>(</span><span class='Function'>=</span><span class='Modifier2'>○</span><span class='Function'>=</span><span class='Modifier2'>⟜</span><span class='Value'>𝕩</span><span class='Modifier2'>◶</span><span class='Number'>1</span><span class='Ligature'>‿</span><span class='Function'>≠</span><span class='Value'>𝕨</span><span class='Paren'>)</span><span class='Function'>↓</span><span class='Value'>𝕩</span><span class='Brace'>}</span></code></td>
</tr>
<tr>
<td><code><span class='Function'>≍</span></code></td>
<td><code><span class='Function'>⊏</span></code></td>
<td><code><span class='Number'>¯1</span><span class='Modifier2'>⊸</span><span class='Function'>⊏</span></code></td>
</tr>
<tr>
<td><code><span class='Function'>↑</span></code></td>
<td><code><span class='Number'>¯1</span><span class='Modifier2'>⊸</span><span class='Function'>⊑</span></code></td>
<td></td>
</tr>
<tr>
<td><code><span class='Function'>↓</span></code></td>
<td><code><span class='Function'>⊑</span></code></td>
<td></td>
</tr>
<tr>
<td><code><span class='Function'>↕</span></code></td>
<td><code><span class='Function'>≢</span></code></td>
<td></td>
</tr>
</tbody>
</table>
<h3 id="required-modifiers">Required modifiers</h3>
<p>The following cases of Self/Swap must be supported.</p>
<table>
<thead>
<tr>
<th>Fn</th>
<th>1</th>
<th>2</th>
</tr>
</thead>
<tbody>
<tr>
<td><code><span class='Function'>+</span><span class='Modifier'>˜</span></code></td>
<td><code><span class='Function'>÷</span><span class='Modifier2'>⟜</span><span class='Number'>2</span></code></td>
<td><code><span class='Function'>+</span><span class='Modifier'>⁼</span></code></td>
</tr>
<tr>
<td><code><span class='Function'>-</span><span class='Modifier'>˜</span></code></td>
<td></td>
<td><code><span class='Function'>+</span></code></td>
</tr>
<tr>
<td><code><span class='Function'>×</span><span class='Modifier'>˜</span></code></td>
<td><code><span class='Function'>√</span></code></td>
<td><code><span class='Function'>×</span><span class='Modifier'>⁼</span></code></td>
</tr>
<tr>
<td><code><span class='Function'>÷</span><span class='Modifier'>˜</span></code></td>
<td></td>
<td><code><span class='Function'>×</span></code></td>
</tr>
<tr>
<td><code><span class='Function'>⋆</span><span class='Modifier'>˜</span></code></td>
<td></td>
<td><code><span class='Function'>√</span></code></td>
</tr>
<tr>
<td><code><span class='Function'>√</span><span class='Modifier'>˜</span></code></td>
<td></td>
<td><code><span class='Function'>÷⋆</span><span class='Modifier'>⁼</span></code></td>
</tr>
<tr>
<td><code><span class='Function'>∧</span><span class='Modifier'>˜</span></code></td>
<td><code><span class='Function'>√</span></code></td>
<td><code><span class='Function'>∧</span><span class='Modifier'>⁼</span></code></td>
</tr>
<tr>
<td><code><span class='Function'>∨</span><span class='Modifier'>˜</span></code></td>
<td><code><span class='Function'>√</span><span class='Modifier2'>⌾</span><span class='Function'>¬</span></code></td>
<td><code><span class='Function'>∨</span><span class='Modifier'>⁼</span></code></td>
</tr>
<tr>
<td><code><span class='Function'>¬</span><span class='Modifier'>˜</span></code></td>
<td></td>
<td><code><span class='Function'>+-</span><span class='Number'>1</span><span class='Modifier'>˙</span></code></td>
</tr>
</tbody>
</table>
<p>Inverses of other modifiers and derived functions or modifiers obtained from them are given below. Here the "inverse" of a modifier is another modifier that, if applied to the same operands as the original operator, gives its inverse function. A constant is either a data value or <code><span class='Function'>𝔽</span><span class='Modifier'>˙</span></code> for an arbitrary value <code><span class='Function'>𝔽</span></code>.</p>
<table>
<thead>
<tr>
<th>Mod</th>
<th>Inverse</th>
<th>Requirements</th>
</tr>
</thead>
<tbody>
<tr>
<td><code><span class='Modifier'>¨</span></code></td>
<td><code><span class='Brace'>{</span><span class='Function'>!</span><span class='Number'>0</span><span class='Function'><≡</span><span class='Value'>𝕩</span><span class='Separator'>⋄</span><span class='Value'>𝕨</span><span class='Function'>𝔽</span><span class='Modifier'>⁼¨</span><span class='Value'>𝕩</span><span class='Brace'>}</span></code></td>
<td></td>
</tr>
<tr>
<td><code><span class='Modifier'>⌜</span></code></td>
<td><code><span class='Brace'>{</span><span class='Function'>!</span><span class='Number'>0</span><span class='Function'><≡</span><span class='Value'>𝕩</span><span class='Separator'>⋄</span> <span class='Function'>𝔽</span><span class='Modifier'>⁼⌜</span><span class='Value'>𝕩;</span><span class='Brace'>}</span></code></td>
<td>Monadic case only</td>
</tr>
<tr>
<td><code><span class='Modifier'>˘</span></code></td>
<td><code><span class='Brace'>{</span><span class='Function'>!</span><span class='Number'>0</span><span class='Function'><=</span><span class='Value'>𝕩</span><span class='Separator'>⋄</span><span class='Value'>𝕨</span><span class='Function'>𝔽</span><span class='Modifier'>⁼˘</span><span class='Value'>𝕩</span><span class='Brace'>}</span></code></td>
<td></td>
</tr>
<tr>
<td><code><span class='Function'>F</span><span class='Modifier2'>∘</span><span class='Function'>G</span></code></td>
<td><code><span class='Brace'>{</span><span class='Value'>𝕨</span><span class='Function'>G</span><span class='Modifier'>⁼</span><span class='Function'>F</span><span class='Modifier'>⁼</span><span class='Value'>𝕩</span><span class='Brace'>}</span></code></td>
<td></td>
</tr>
<tr>
<td><code><span class='Function'>F</span> <span class='Function'>G</span></code></td>
<td></td>
<td></td>
</tr>
<tr>
<td><code><span class='Nothing'>·</span><span class='Function'>F</span> <span class='Function'>G</span></code></td>
<td></td>
<td></td>
</tr>
<tr>
<td><code><span class='Modifier2'>○</span></code></td>
<td><code><span class='Brace'>{</span><span class='Function'>𝔾</span><span class='Modifier'>⁼</span><span class='Paren'>(</span><span class='Function'>𝔾</span><span class='Value'>𝕨</span><span class='Paren'>)</span><span class='Function'>𝔽</span><span class='Modifier'>⁼</span><span class='Value'>𝕩</span><span class='Brace'>}</span></code></td>
<td></td>
</tr>
<tr>
<td><code><span class='Modifier'>⁼</span></code></td>
<td><code><span class='Brace'>{</span><span class='Value'>r</span><span class='Gets'>←</span><span class='Function'>𝔽</span><span class='Value'>𝕩</span><span class='Separator'>⋄</span><span class='Function'>!</span><span class='Value'>𝕩</span><span class='Function'>≡𝔽</span><span class='Modifier'>⁼</span><span class='Value'>r</span><span class='Separator'>⋄</span><span class='Value'>r</span><span class='Brace'>}</span></code></td>
<td></td>
</tr>
<tr>
<td><code><span class='Modifier2'>⌾</span></code></td>
<td><code><span class='Brace'>{</span><span class='Function'>𝔽</span><span class='Modifier'>⁼</span><span class='Modifier2'>⌾</span><span class='Function'>𝔾</span><span class='Brace'>}</span></code></td>
<td>Verify result for computational Under</td>
</tr>
<tr>
<td><code><span class='Modifier2'>⍟</span><span class='Value'>n</span></code></td>
<td><code><span class='Modifier2'>⍟</span><span class='Paren'>(</span><span class='Function'>-</span><span class='Value'>n</span><span class='Paren'>)</span></code></td>
<td>Atomic number <code><span class='Value'>n</span></code></td>
</tr>
<tr>
<td><code><span class='Modifier2'>⊘</span></code></td>
<td><code><span class='Brace'>{</span><span class='Paren'>(</span><span class='Function'>𝔽</span><span class='Modifier'>⁼</span><span class='Paren'>)</span><span class='Modifier2'>⊘</span><span class='Paren'>(</span><span class='Function'>𝔾</span><span class='Modifier'>⁼</span><span class='Paren'>)</span><span class='Brace'>}</span></code></td>
<td></td>
</tr>
<tr>
<td><code><span class='Modifier2'>⊸</span></code></td>
<td><code><span class='Brace'>{</span><span class='Function'>𝔽</span><span class='Modifier2'>⊸</span><span class='Paren'>(</span><span class='Function'>𝔾</span><span class='Modifier'>⁼</span><span class='Paren'>)</span><span class='Brace'>}</span></code></td>
<td>Dyadic case or constant <code><span class='Function'>𝔽</span></code> only</td>
</tr>
<tr>
<td><code><span class='Modifier2'>⟜</span></code></td>
<td><code><span class='Brace'>{</span><span class='Function'>𝔾</span><span class='Modifier'>⁼</span><span class='Function'>𝔽</span><span class='Modifier'>⁼</span><span class='Brace'>}</span></code></td>
<td>Dyadic case</td>
</tr>
<tr>
<td><code><span class='Function'>𝔽</span><span class='Modifier2'>⟜</span><span class='Value'>k</span></code></td>
<td><code><span class='Value'>k</span><span class='Function'>𝔽</span><span class='Modifier'>˜⁼</span><span class='Function'>⊢</span></code></td>
<td>Monadic case, constant <code><span class='Value'>k</span></code></td>
</tr>
<tr>
<td><code><span class='Value'>k</span><span class='Function'>𝔽𝔾</span></code></td>
<td><code><span class='Function'>𝔾</span><span class='Modifier'>⁼</span><span class='Brace'>{</span><span class='Value'>𝕨</span><span class='Function'>𝔽𝔾</span><span class='Value'>𝕩</span><span class='Brace'>}</span><span class='Paren'>(</span><span class='Value'>k</span><span class='Function'>𝔽</span><span class='Modifier'>⁼</span><span class='Function'>⊢</span><span class='Paren'>)</span></code></td>
<td>Constant <code><span class='Value'>k</span></code></td>
</tr>
<tr>
<td><code><span class='Function'>𝔽𝔾K</span></code></td>
<td><code><span class='Function'>𝔽</span><span class='Modifier'>⁼</span><span class='Value'>k</span><span class='Function'>𝔾</span><span class='Modifier'>˜⁼</span><span class='Function'>⊢</span></code></td>
<td>Constant <code><span class='Value'>k</span></code></td>
</tr>
</tbody>
</table>
<table>
<thead>
<tr>
<th>Mod</th>
<th>Inverse</th>
</tr>
</thead>
<tbody>
<tr>
<td><code><span class='Modifier'>`</span></code></td>
<td><code><span class='Brace'>{</span><span class='Function'>!</span><span class='Number'>0</span><span class='Function'><=</span><span class='Value'>𝕩</span> <span class='Separator'>⋄</span> <span class='Value'>𝕨</span> <span class='Paren'>(</span><span class='Function'>»𝔽</span><span class='Modifier'>⁼¨</span><span class='Function'>⊢</span><span class='Paren'>)</span><span class='Brace'>{</span><span class='Paren'>(</span><span class='Function'>⊏∾⊏𝔽</span><span class='Number'>1</span><span class='Modifier2'>⊸</span><span class='Function'>↓</span><span class='Paren'>)</span><span class='Modifier2'>⍟</span><span class='Paren'>(</span><span class='Number'>1</span><span class='Function'><≠</span><span class='Paren'>)</span><span class='Modifier2'>⊘</span><span class='Function'>𝔽</span><span class='Brace'>}</span> <span class='Value'>𝕩</span><span class='Brace'>}</span></code></td>
</tr>
</tbody>
</table>
<h3 id="undo-headers">Undo headers</h3>
<p>An <code><span class='Function'>UndoHead</span></code> header specifies how a block function acts when undone. Like ordinary headers, undo headers are searched for a match when a block function <code><span class='Function'>F</span></code> is undone, or when <code><span class='Function'>F</span><span class='Modifier'>˜</span></code> is undone with two arguments (including the two modifier cases <code><span class='Function'>𝔽</span><span class='Modifier2'>⟜</span><span class='Value'>k</span></code> and <code><span class='Function'>𝔽𝔾</span><span class='Value'>k</span></code> from the previous section). An <code><span class='Function'>UndoHead</span></code> without <code><span class='String'>"˜"</span></code> matches the <code><span class='Function'>F</span><span class='Modifier'>⁼</span></code> case while one with <code><span class='String'>"˜"</span></code> matches the <code><span class='Function'>F</span><span class='Modifier'>˜⁼</span></code> case. The left and right arguments are matched to <code><span class='Value'>headW</span></code> and <code><span class='Value'>headX</span></code> as with ordinary headers, and the first matching case is evaluated to give the result of the Undo-derived function.</p>
<h2 id="under">Under</h2>
<p>The Under 2-modifier <code><span class='Modifier2'>⌾</span></code> conceptually applies its left operand under the action of its right operand. Setting <code><span class='Value'>z</span><span class='Gets'>←</span><span class='Value'>𝕨</span><span class='Function'>𝔽</span><span class='Modifier2'>⌾</span><span class='Function'>𝔾</span><span class='Value'>𝕩</span></code>, it satisfies <code><span class='Paren'>(</span><span class='Value'>𝕨</span><span class='Function'>𝔽</span><span class='Modifier2'>○</span><span class='Function'>𝔾</span><span class='Value'>𝕩</span><span class='Paren'>)</span> <span class='Function'>≡</span> <span class='Function'>𝔾</span><span class='Value'>z</span></code>. We might say that <code><span class='Function'>𝔾</span></code> transforms values to a new domain, and <code><span class='Modifier2'>⌾</span><span class='Function'>𝔾</span></code> lifts actions <code><span class='Function'>𝔽</span></code> performed in this domain to the original domain of values. For example, addition in the logarithmic domain corresponds to multiplication in the linear domain: <code><span class='Function'>+</span><span class='Modifier2'>⌾</span><span class='Paren'>(</span><span class='Function'>⋆</span><span class='Modifier'>⁼</span><span class='Paren'>)</span></code> is <code><span class='Function'>×</span></code> (but less precise if computed in floating point).</p>
<p>Let <code><span class='Value'>v</span><span class='Gets'>←</span><span class='Value'>𝕨</span><span class='Function'>𝔽</span><span class='Modifier2'>○</span><span class='Function'>𝔾</span><span class='Value'>𝕩</span></code>, so that <code><span class='Value'>v</span><span class='Function'>≡𝔾</span><span class='Value'>z</span></code>. <code><span class='Value'>v</span></code> is of course well-defined, so the inference step is to find <code><span class='Value'>z</span></code> based on <code><span class='Value'>v</span></code> and possibly the original inputs. We distinguish three cases for Under:</p>
<ul>
<li><em>Invertible</em> Under: If <code><span class='Function'>𝔾</span></code> is uniquely invertible on <code><span class='Value'>v</span></code>, that is, <code><span class='Value'>v</span><span class='Function'>≡𝔾</span><span class='Value'>z</span></code> has a unique solution for <code><span class='Value'>z</span></code>, then the result of Under is that solution.</li>
<li><em>Structural</em> Under: If <code><span class='Function'>𝔾</span></code> is a structural function (to be defined below) and <code><span class='Value'>v</span></code> is compatible with <code><span class='Function'>𝔾</span></code> on <code><span class='Value'>𝕩</span></code>, then the result is obtained by inserting <code><span class='Value'>v</span></code> back into <code><span class='Value'>𝕩</span></code>.</li>
<li><em>Computational</em> Under: If <code><span class='Function'>𝔾</span></code> is provably not a structural function, then the result is <code><span class='Function'>𝔾</span><span class='Modifier'>⁼</span><span class='Value'>v</span></code> if it is defined.</li>
</ul>
<p>When implementing, there is no need to implement invertable Under specially: it can be handled as part of the structural and computation cases.</p>
<h3 id="mathematical-definition-of-structural-under">Mathematical definition of structural Under</h3>
<p>In general, structural Under requires information from the original right argument to be computed. Here we will define the <em>structural inverse of</em> structural function <code><span class='Function'>𝔾</span></code> <em>on</em> <code><span class='Value'>v</span></code> <em>into</em> <code><span class='Value'>𝕩</span></code>, where <code><span class='Value'>𝕩</span></code> gives this information. The value <code><span class='Value'>𝕨</span><span class='Function'>𝔽</span><span class='Modifier2'>⌾</span><span class='Function'>𝔾</span><span class='Value'>𝕩</span></code> is then the structural inverse of <code><span class='Function'>𝔾</span></code> on <code><span class='Value'>𝕨</span><span class='Function'>𝔽</span><span class='Modifier2'>○</span><span class='Function'>𝔾</span><span class='Value'>𝕩</span></code> into <code><span class='Value'>𝕩</span></code>.</p>
<p>We define a <em>structure</em> to be either the value <code><span class='Nothing'>·</span></code> or an array of structures (substitute <code><span class='Number'>0</span></code> or any other specific value for <code><span class='Nothing'>·</span></code> if you'd like structures to be a subset of BQN arrays; the value is irrelevant). A given structure <code><span class='Value'>s</span></code> is a <em>captures</em> a BQN value or structure <code><span class='Value'>𝕩</span></code> if it is <code><span class='Nothing'>·</span></code>, or if <code><span class='Value'>s</span></code> and <code><span class='Value'>𝕩</span></code> are arrays of the same shape, and each element of <code><span class='Value'>s</span></code> captures the corresponding element of <code><span class='Value'>𝕩</span></code>. Thus a structure shares some or all of the structural information in arrays it captures, but none of the data.</p>
<p>A <em>structure transformation</em> consists of an initial structure <code><span class='Value'>s</span></code> and a result structure <code><span class='Value'>t</span></code>, as well as a relation between the two: each instance of <code><span class='Nothing'>·</span></code> in <code><span class='Value'>t</span></code> is assigned the location of an instance of <code><span class='Nothing'>·</span></code> in <code><span class='Value'>s</span></code>. If <code><span class='Value'>s</span></code> captures a value <code><span class='Value'>𝕩</span></code>, we say that the structural transformation captures <code><span class='Value'>𝕩</span></code> as well. Given such a value <code><span class='Value'>𝕩</span></code>, the transformation is applied to <code><span class='Value'>𝕩</span></code> by replacing each <code><span class='Nothing'>·</span></code> in <code><span class='Value'>t</span></code> with the corresponding value from <code><span class='Value'>𝕩</span></code>, found by taking the same location in <code><span class='Value'>𝕩</span></code> as the one in <code><span class='Value'>s</span></code> given by the transformation.</p>
<p>Given a structure transformation <code><span class='Function'>G</span></code> and values <code><span class='Value'>𝕩</span></code> and <code><span class='Value'>v</span></code>, the <em>structural inverse</em> <code><span class='Value'>z</span></code> of <code><span class='Function'>G</span></code> on <code><span class='Value'>v</span></code> into <code><span class='Value'>𝕩</span></code>, if it exists, is the value such that <code><span class='Value'>v</span><span class='Function'>≡G</span> <span class='Value'>z</span></code>, and <code><span class='Value'>𝕩</span> <span class='Function'>≡</span><span class='Modifier2'>○</span><span class='Function'>F</span> <span class='Value'>z</span></code> for every structure transformation <code><span class='Function'>F</span></code> as possible given the previous constraint. If <code><span class='Function'>G</span></code> has initial structure <code><span class='Value'>s</span></code> and final structure <code><span class='Value'>t</span></code>, we know that <code><span class='Value'>s</span></code> captures <code><span class='Value'>𝕩</span></code> and <code><span class='Value'>z</span></code> (it's required in order to apply <code><span class='Function'>G</span></code> at all) while <code><span class='Value'>t</span></code> captures <code><span class='Value'>v</span></code>. For each instance of <code><span class='Nothing'>·</span></code> in <code><span class='Value'>s</span></code>, there are three possibilities:</p>
<ul>
<li>No result location in <code><span class='Value'>t</span></code> is assigned this location. This component of <code><span class='Value'>z</span></code> must match <code><span class='Value'>𝕩</span></code>, or <code><span class='Value'>z</span></code> could be improved without breaking any constraints by replacing it.</li>
<li>Exactly one result location is assigned this location. The requirement <code><span class='Value'>v</span><span class='Function'>≡G</span> <span class='Value'>z</span></code> implies <code><span class='Value'>z</span></code>'s value here is exactly <code><span class='Value'>v</span></code>'s value at that result location.</li>
<li>More than one result location is assigned this location. Now <code><span class='Value'>z</span></code>'s value there must match <code><span class='Value'>v</span></code>'s value at each of these result leaves. If <code><span class='Value'>v</span></code> has different values at the different leaves, there is no inverse.</li>
</ul>
<p>Following this analysis, <code><span class='Value'>z</span></code> can be constructed by replacing each instance of <code><span class='Nothing'>·</span></code> in <code><span class='Value'>s</span></code> with the component of <code><span class='Value'>𝕩</span></code> or <code><span class='Value'>v</span></code> indicated, and it follows that <code><span class='Value'>z</span></code> is well-defined if it exists—and it exists if and only if <code><span class='Value'>t</span></code> captures <code><span class='Value'>v</span></code> and values in <code><span class='Value'>v</span></code> that correspond to the same position in <code><span class='Value'>s</span></code> have the same value.</p>
<p>A <em>structural function decomposition</em> is a possibly infinite family of structure transformations such that any possible BQN value is captured by at most one of these transformations. It can be applied to any value: if some transformation captures the value, then apply that transformation, and otherwise give an error. A function is a <em>structural function</em> if there is a structural function decomposition that matches it: that is, for any input either both functions give an error or the results match.</p>
<p>For a structural function <code><span class='Function'>𝔾</span></code>, the <em>structural inverse</em> of <code><span class='Function'>𝔾</span></code> on <code><span class='Value'>v</span></code> into <code><span class='Value'>𝕩</span></code> is the inverse of <code><span class='Function'>G</span></code> on <code><span class='Value'>v</span></code> into <code><span class='Value'>𝕩</span></code>, where <code><span class='Function'>G</span></code> is the structure transformation that captures <code><span class='Value'>𝕩</span></code> from some structural function decomposition <code><span class='Function'>Gd</span></code> matching <code><span class='Function'>𝔾</span></code>. If no decomposition has an initial structural matching <code><span class='Value'>𝕩</span></code> then the structural inverse does not exist.</p>
<h4 id="well-definedness">Well-definedness</h4>
<p>In order to show that the structural inverse of a structural function is well-defined, we must show that it does not depend on the choice of structural function decomposition. That is, for a given <code><span class='Value'>𝕩</span></code>, if <code><span class='Function'>G</span></code> and <code><span class='Function'>H</span></code> are structure transformations from different decompositions of <code><span class='Function'>𝔾</span></code> both capturing <code><span class='Value'>𝕩</span></code>, then the structural inverse of <code><span class='Function'>G</span></code> on <code><span class='Value'>v</span></code> into <code><span class='Value'>𝕩</span></code> matches that of <code><span class='Function'>H</span></code> on <code><span class='Value'>v</span></code> into <code><span class='Value'>𝕩</span></code>. Call these inverses <code><span class='Value'>y</span></code> and <code><span class='Value'>z</span></code>. Now begin by supposing that <code><span class='Function'>H</span></code> captures <code><span class='Value'>y</span></code> and <code><span class='Function'>G</span></code> captures <code><span class='Value'>z</span></code>; we will show this later. From the definition of a structural inverse, <code><span class='Value'>v</span><span class='Function'>≡G</span> <span class='Value'>y</span></code>, so that <code><span class='Value'>v</span><span class='Function'>≡𝔾</span> <span class='Value'>y</span></code>, and because <code><span class='Function'>H</span></code> captures <code><span class='Value'>y</span></code> we know that <code><span class='Function'>𝔾</span> <span class='Value'>y</span></code> is <code><span class='Function'>H</span> <span class='Value'>y</span></code>, so we have <code><span class='Value'>v</span><span class='Function'>≡H</span> <span class='Value'>y</span></code> as well. Let <code><span class='Function'>S</span> <span class='Value'>w</span></code> indicate the set of all functions <code><span class='Function'>F</span></code> such that <code><span class='Value'>w</span> <span class='Function'>≡</span><span class='Modifier2'>○</span><span class='Function'>F</span> <span class='Value'>𝕩</span></code> (this is not a BQN value, both because it is a set and because it's usually infinite): from the definition of <code><span class='Value'>z</span></code> we know that <code><span class='Function'>S</span> <span class='Value'>z</span></code> is a strict superset of <code><span class='Function'>S</span> <span class='Value'>w</span></code> for any <code><span class='Value'>w</span></code> other than <code><span class='Value'>z</span></code> with <code><span class='Value'>v</span><span class='Function'>≡H</span> <span class='Value'>w</span></code>. It follows that either <code><span class='Value'>y</span><span class='Function'>≡</span><span class='Value'>z</span></code> or <code><span class='Function'>S</span> <span class='Value'>y</span></code> is a strict subset of <code><span class='Function'>S</span> <span class='Value'>z</span></code>. By symmetry the same relation holds exchanging <code><span class='Value'>y</span></code> and <code><span class='Value'>z</span></code>, but it's not possible for <code><span class='Function'>S</span> <span class='Value'>y</span></code> to be a strict subset of <code><span class='Function'>S</span> <span class='Value'>z</span></code> and vice-versa. The only remaining possibility is that <code><span class='Value'>y</span><span class='Function'>≡</span><span class='Value'>z</span></code>.</p>
<p>We now need to show that <code><span class='Function'>H</span></code> captures <code><span class='Value'>y</span></code> (the proof that <code><span class='Function'>G</span></code> captures <code><span class='Value'>z</span></code> is of course the same as <code><span class='Function'>H</span></code> and <code><span class='Function'>G</span></code> are symmetric). To do this we must show that any array in the initial structure of <code><span class='Function'>H</span></code> corresponds to a matching array in <code><span class='Value'>y</span></code>. For convenience, we will call the initial structures of the two transformations <code><span class='Value'>iG</span></code> and <code><span class='Value'>iH</span></code>, and the final structures <code><span class='Value'>fG</span></code> and <code><span class='Value'>fH</span></code>, and use the notation <code><span class='Value'>p</span><span class='Function'>⊑</span><span class='Value'>a</span></code> to indicate the value of array <code><span class='Value'>a</span></code> at position <code><span class='Value'>p</span></code>. Choose the position of an array in <code><span class='Function'>H</span></code>, and assume by induction that each array containing it already has the desired property; this implies that this position exists in <code><span class='Value'>y</span></code> as well although we know nothing about its contents. <code><span class='Function'>G</span></code> captures <code><span class='Value'>y</span></code>, so <code><span class='Value'>iG</span></code> is <code><span class='Nothing'>·</span></code> at this position or some parent position; call this position in <code><span class='Value'>iG</span></code> <code><span class='Value'>p</span></code>. There are now two cases: either <code><span class='Function'>G</span></code> makes use of this <code><span class='Value'>p</span></code>—at least one position in <code><span class='Value'>fG</span></code> corresponds to it—or it doesn't. If it doesn't, then the contents of <code><span class='Value'>y</span></code> at <code><span class='Value'>p</span></code> are the same as those of <code><span class='Value'>𝕩</span></code>. Since <code><span class='Function'>H</span></code> captures <code><span class='Value'>𝕩</span></code>, <code><span class='Value'>iH</span></code> matches <code><span class='Value'>𝕩</span></code> and hence <code><span class='Value'>y</span></code> as well at <code><span class='Value'>p</span></code>. If it does, then let <code><span class='Value'>s</span></code> be a position in <code><span class='Value'>fG</span></code> that corresponds to <code><span class='Value'>p</span></code> (if there are multiple possibilities, choose one). From <code><span class='Value'>v</span><span class='Function'>≡G</span> <span class='Value'>y</span></code>, we know that <code><span class='Value'>s</span><span class='Function'>⊑</span><span class='Value'>v</span></code> matches <code><span class='Value'>p</span><span class='Function'>⊑</span><span class='Value'>y</span></code>. We know that <code><span class='Value'>fH</span></code> captures <code><span class='Value'>v</span></code>, so that <code><span class='Value'>s</span><span class='Function'>⊑</span><span class='Value'>fH</span></code> captures <code><span class='Value'>s</span><span class='Function'>⊑</span><span class='Value'>v</span></code>, or <code><span class='Value'>p</span><span class='Function'>⊑</span><span class='Value'>y</span></code>. But we can show that the value of <code><span class='Value'>s</span><span class='Function'>⊑</span><span class='Value'>fH</span></code> is the same as <code><span class='Value'>p</span><span class='Function'>⊑</span><span class='Value'>iH</span></code>, which would prove that <code><span class='Function'>H</span></code> captures <code><span class='Value'>y</span></code> at <code><span class='Value'>p</span></code>. To show this, construct an array <code><span class='Value'>xp</span></code> by replacing the value of <code><span class='Value'>𝕩</span></code> at <code><span class='Value'>p</span></code> with <code><span class='Value'>p</span><span class='Function'>⊑</span><span class='Value'>iH</span></code> (to be more careful in our handling of types, we might replace every <code><span class='Nothing'>·</span></code> with some value that never appears in <code><span class='Value'>𝕩</span></code>). Both <code><span class='Function'>H</span></code> and <code><span class='Function'>G</span></code> capture <code><span class='Value'>xp</span></code>: clearly they capture it outside <code><span class='Value'>p</span></code>, while at <code><span class='Value'>p</span></code> itself, <code><span class='Value'>iG</span></code> is <code><span class='Nothing'>·</span></code> and <code><span class='Value'>iH</span></code> is equal to <code><span class='Value'>p</span><span class='Function'>⊑</span><span class='Value'>xp</span></code>. Now <code><span class='Paren'>(</span><span class='Function'>H</span> <span class='Value'>xp</span><span class='Paren'>)</span><span class='Function'>≡</span><span class='Paren'>(</span><span class='Function'>G</span> <span class='Value'>xp</span><span class='Paren'>)</span></code> because both functions match <code><span class='Function'>𝔾</span></code> on their domains. Therefore <code><span class='Value'>s</span><span class='Function'>⊑H</span> <span class='Value'>xp</span></code> matches <code><span class='Value'>s</span><span class='Function'>⊑G</span> <span class='Value'>xp</span></code>, which by the definition of <code><span class='Value'>s</span></code> matches <code><span class='Value'>p</span><span class='Function'>⊑</span><span class='Value'>xp</span></code>, which matches <code><span class='Value'>p</span><span class='Function'>⊑</span><span class='Value'>iH</span></code>. But <code><span class='Value'>s</span><span class='Function'>⊑H</span> <span class='Value'>xp</span></code> comes from replacing each atom in <code><span class='Value'>s</span><span class='Function'>⊑</span><span class='Value'>fH</span></code> with an atom in <code><span class='Value'>xp</span></code> that's captured by a <code><span class='Nothing'>·</span></code> in <code><span class='Value'>iH</span></code>. Because it matches <code><span class='Value'>p</span><span class='Function'>⊑</span><span class='Value'>iH</span></code>, every atom in <code><span class='Value'>s</span><span class='Function'>⊑H</span> <span class='Value'>xp</span></code> is <code><span class='Nothing'>·</span></code>, but the only instances of <code><span class='Nothing'>·</span></code> in <code><span class='Value'>xp</span></code> come from our inserted copy of <code><span class='Value'>p</span><span class='Function'>⊑</span><span class='Value'>iH</span></code> and each is immediately captured by the corresponding <code><span class='Nothing'>·</span></code> in <code><span class='Value'>iH</span></code>. It follows that <code><span class='Value'>s</span><span class='Function'>⊑H</span> <span class='Value'>xp</span></code>, and consequently <code><span class='Value'>s</span><span class='Function'>⊑</span><span class='Value'>fH</span></code>, is exactly <code><span class='Value'>p</span><span class='Function'>⊑</span><span class='Value'>iH</span></code>, completing the proof.</p>
<h3 id="required-structural-inverses">Required structural inverses</h3>
<p>The following primitive functions be fully supported by structural Under. Each manipulates its right argument structurally.</p>
<table>
<thead>
<tr>
<th>Type</th>
<th>Primitives</th>
</tr>
</thead>
<tbody>
<tr>
<td>Monad</td>
<td><code><span class='Function'>⊣⊢<>∾⥊≍↑↓⌽⍉⊏⊑</span></code></td>
</tr>
<tr>
<td>Dyad</td>
<td><code><span class='Function'>⊢⥊↑↓↕⌽⍉/⊏⊑⊔</span></code></td>
</tr>
</tbody>
</table>
<p>The following combinations must also be supported, where <code><span class='Function'>S</span></code> and <code><span class='Function'>T</span></code> are structural functions and <code><span class='Value'>k</span></code> is a constant function (data type, or function derived from <code><span class='Modifier'>˙</span></code>):</p>
<table>
<thead>
<tr>
<th>Expression</th>
<th>Remarks</th>
</tr>
</thead>
<tbody>
<tr>
<td><code><span class='Function'>S</span><span class='Modifier2'>∘</span><span class='Function'>T</span></code></td>
<td></td>
</tr>
<tr>
<td><code><span class='Function'>S</span> <span class='Function'>T</span></code></td>
<td></td>
</tr>
<tr>
<td><code><span class='Nothing'>·</span><span class='Function'>S</span> <span class='Function'>T</span></code></td>
<td></td>
</tr>
<tr>
<td><code><span class='Function'>S</span><span class='Modifier2'>○</span><span class='Function'>T</span></code></td>
<td></td>
</tr>
<tr>
<td><code><span class='Value'>k</span><span class='Modifier2'>⊸</span><span class='Function'>T</span></code></td>
<td></td>
</tr>
<tr>
<td><code><span class='Value'>k</span> <span class='Function'>T</span> <span class='Function'>⊢</span></code></td>
<td></td>
</tr>
<tr>
<td><code><span class='Function'>S</span><span class='Modifier2'>⍟</span><span class='Value'>k</span></code></td>
<td><code><span class='Value'>k</span></code> a natural number</td>
</tr>
<tr>
<td><code><span class='Function'>S</span><span class='Modifier'>¨</span></code></td>
<td></td>
</tr>
<tr>
<td><code><span class='Function'>S</span><span class='Modifier2'>⚇</span><span class='Value'>k</span></code></td>
<td><code><span class='Value'>k</span></code> contains only negative numbers</td>
</tr>
<tr>
<td><code><span class='Function'>S</span><span class='Modifier'>⌜</span></code></td>
<td></td>
</tr>
<tr>
<td><code><span class='Function'>S</span><span class='Modifier'>˘</span></code></td>
<td></td>
</tr>
<tr>
<td><code><span class='Function'>S</span><span class='Modifier2'>⎉</span><span class='Value'>k</span></code></td>
<td></td>
</tr>
</tbody>
</table>
<h3 id="a-structural-under-algorithm">A structural Under algorithm</h3>
<p>This section offers the outline for a procedure that computes most structural inverses that a programmer would typically use. The concept is to build a special result array whose elements are not BQN values but instead indicate positions within the initial argument. This structural array is applied to the initial argument by replacing its elements with the values at those positions, and inverted by placing elements back in the original array at these indices, checking for any conflicts. If operations like dyadic <code><span class='Function'>∾</span></code> are allowed, then a structural array might have some indices that are prefixes or parents of others, making it slightly different from a structural transformation as defined above (although it could be represented as a structural transformation by expanding some of these). This requires additional checking to ensure that elements of previously inserted elements can't be modified.</p>
<p>Structural functions can be applied to structural arrays directly, after ensuring that they have the necessary depth as given below. An array's depth can be increased by expanding each position in it into an array of child positions, or, if that position contains an atom and the structural function in question would tolerate an atom, enclosing it.</p>
<table>
<thead>
<tr>
<th align="center">Level</th>
<th>Monads</th>
<th>Dyads</th>
<th>Modifiers</th>
</tr>
</thead>
<tbody>
<tr>
<td align="center">0</td>
<td><code><span class='Function'>⊢⊣<</span></code></td>
<td><code><span class='Function'>⊢⊣</span></code></td>
<td><code><span class='Modifier'>˜</span><span class='Modifier2'>∘○⊸⟜⊘◶</span></code></td>
</tr>
<tr>
<td align="center">1</td>
<td><code><span class='Function'>=≠≢⥊≍↑↓»«⌽⍉⊏⊑</span></code></td>
<td><code><span class='Function'>⥊∾≍↑↓↕»«⌽⍉/⊏⊑⊔</span></code></td>
<td><code><span class='Modifier'>˘¨⌜</span><span class='Modifier2'>⎉</span></code></td>
</tr>
<tr>
<td align="center">2</td>
<td><code><span class='Function'>>∾</span></code></td>
<td></td>
<td></td>
</tr>
<tr>
<td align="center">n</td>
<td></td>
<td></td>
<td><code><span class='Modifier2'>⚇</span></code></td>
</tr>
</tbody>
</table>
<p>Not all primitives in the table above are required. Of note are <code><span class='Function'>=≠≢</span></code>, which accept a structural array but return an ordinary value; this might be used as a left argument later. If the final result is not structural, then the function in question can't be structural, and the attempt to find a structural inverse can be aborted.</p>
<h3 id="non-structural-case">Non-structural case</h3>
<p>The behavior of invertible and computational Under is fully dependent on that of <a href="#undo">Undo</a>, and does not need to be repeated here. However, it is important to discuss when this definition can be applied: specifically, either</p>
<ul>
<li>When <code><span class='Function'>𝔾</span></code> is exactly invertible, or</li>
<li>When <code><span class='Function'>𝔾</span></code> is provably not a structural function.</li>
</ul>
<p>A substantial class of functions that is easy to identify and always satisfies one of the above criteria is the functions that <em>never perform non-invertible structural manipulation</em>, or more colloquially <em>don't discard argument elements</em>. This class consists of functions made up of plain primitives that don't contain the following primitives:</p>
<table>
<thead>
<tr>
<th>Valence</th>
<th>Primitives</th>
</tr>
</thead>
<tbody>
<tr>
<td>Monad</td>
<td><code><span class='Function'>»«⊏⊑</span></code></td>
</tr>
<tr>
<td>Dyad</td>
<td><code><span class='Function'>⥊↑↓»«⍉/⊏⊑⊔</span></code></td>
</tr>
<tr>
<td>Modifer</td>
<td><code><span class='Modifier'>⁼</span><span class='Modifier2'>⍟</span><span class='Modifier'>´˝`</span></code></td>
</tr>
</tbody>
</table>
<p>If a function of this class is a structural function, then it must be invertible, because the remaining primitives leave no way to retain some elements but discard others (an element's value can be ignored by replacing it by a constant, but a function that does this can't be structural). It can be extended to include some dyadic functions like <code><span class='Function'>⥊↑⍉/</span></code> if it can be determined that the left argument never allows information to be discarded; for example if the left argument to <code><span class='Function'>⍉</span></code> contains no duplicates or the left argument to <code><span class='Function'>⥊</span></code> always has a product larger than its argument's bound. Inverses from <code><span class='Modifier'>⁼</span></code> or <code><span class='Modifier2'>⍟</span></code> might be allowed on a case-by-case basis, and <code><span class='Modifier2'>⍟</span></code> with a constant right operand that contains no negative numbers can also be allowed.</p>
|
