docs/spec/primitive.html


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

<head>
  <link href="../favicon.ico" rel="shortcut icon" type="image/x-icon"/>
  <link href="../style.css" rel="stylesheet"/>
  <title>Specification: BQN primitives</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-primitives">Specification: BQN primitives</h1>
<p>Most primitives are specified by the BQN-based implementation in <a href="https://github.com/mlochbaum/BQN/blob/master/spec/reference.bqn">reference.bqn</a>. This document specifies the basic functionality required by those definitions. Descriptions of other primitives are for informational purposes only.</p>
<h2 id="pervasive-primitives">Pervasive primitives</h2>
<p>Functions in this section are defined for atoms only; the reference implementations extend them to arrays.</p>
<h3 id="arithmetic">Arithmetic</h3>
<p>BQN uses five arithmetic functions that are standard in mathematics. The precision of these operations should be specified by the number <a href="types.html">type</a>.</p>
<ul>
<li><strong>Add</strong> <code><span class='Function'>+</span></code></li>
<li><strong>Negate</strong> and <strong>Subtract</strong> <code><span class='Function'>-</span></code> invert addition, with <code><span class='Function'>-</span><span class='Value'>𝕩</span></code> equivalent to <code><span class='Number'>0</span><span class='Function'>-</span><span class='Value'>𝕩</span></code>.</li>
<li><strong>Multiply</strong> <code><span class='Function'>×</span></code> generalizes repeated addition.</li>
<li><strong>Divide</strong> and <strong>Reciprocal</strong> <code><span class='Function'>÷</span></code> invert multiplication, with <code><span class='Function'>÷</span><span class='Value'>𝕩</span></code> equivalent to <code><span class='Number'>1</span><span class='Function'>÷</span><span class='Value'>𝕩</span></code>.</li>
<li><strong>Power</strong> <code><span class='Function'>⋆</span></code> generalizes repeated multiplication, and <strong>Exponential</strong> <code><span class='Function'>⋆</span></code> is Power with Euler's number <em>e</em> as the base.</li>
</ul>
<p>The three higher functions <code><span class='Function'>×</span></code>, <code><span class='Function'>÷</span></code>, and <code><span class='Function'>⋆</span></code> apply to numbers and no other atomic types. <code><span class='Function'>+</span></code> and <code><span class='Function'>-</span></code> apply to numbers, and possibly also to characters, according to the rules of the affine character type:</p>
<ul>
<li>If one argument to <code><span class='Function'>+</span></code> is the character with code point <code><span class='Value'>c</span></code> and the other is a number <code><span class='Value'>n</span></code> (in either order), then the result is the character with code point <code><span class='Value'>c</span><span class='Function'>+</span><span class='Value'>n</span></code>.</li>
<li>If the left argument to <code><span class='Function'>-</span></code> is the character with code point <code><span class='Value'>c</span></code> and the right is a number <code><span class='Value'>n</span></code>, the result is the character with code point <code><span class='Value'>c</span><span class='Function'>-</span><span class='Value'>n</span></code>.</li>
<li>If both arguments to <code><span class='Function'>-</span></code> are characters, the result is the difference of their respective code points.</li>
</ul>
<p>In the first two cases, if the result would not be a valid Unicode code point, then an error results. The remaining cases of <code><span class='Function'>+</span></code> and <code><span class='Function'>-</span></code> (adding two characters; negating a character or subtracting it from a number) are not allowed.</p>
<p>Additionally, the <strong>Floor</strong> function <code><span class='Function'>⌊</span></code> returns the largest integer smaller than the argument, or the argument itself if it is <code><span class='Number'>¯∞</span></code> or <code><span class='Number'>∞</span></code>. It's needed because the arithmetic operations give no fixed-time way to determine if a value is an integer. Floor gives an error if the argument is an atom other than a number.</p>
<h3 id="comparison">Comparison</h3>
<p>Two kinds of comparison are needed to define BQN's primitives: <em>equality</em> comparison and <em>ordered</em> comparison.</p>
<p>Ordered comparison is simpler and is provided by the dyadic Less than or Equal to (<code><span class='Function'>≤</span></code>) function. This function gives an error if either argument is an operation, so it needs to be defined only for numbers and characters. For numbers it is defined by the number system, and for characters it returns <code><span class='Number'>1</span></code> if the left argument's code point is less than that of the right argument. Characters are considered greater than numbers, so that <code><span class='Value'>n</span><span class='Function'>≤</span><span class='Value'>c</span></code> is <code><span class='Number'>1</span></code> and <code><span class='Value'>c</span><span class='Function'>≤</span><span class='Value'>n</span></code> is <code><span class='Number'>0</span></code> if <code><span class='Value'>c</span></code> is a character and <code><span class='Value'>n</span></code> is a number.</p>
<p>The dyadic function <code><span class='Function'>=</span></code>, representing equality comparison, can be applied to any two atoms without an error. Roughly speaking, it returns <code><span class='Number'>1</span></code> if they are indistinguishable within the language and <code><span class='Number'>0</span></code> otherwise. If the two arguments have different types, the result is <code><span class='Number'>0</span></code>; if they have the same type, the comparison depends on type:</p>
<ul>
<li>Equality of numbers is specified by the number type.</li>
<li>Characters are equal if they have the same code point.</li>
</ul>
<p>Operations are split into subtypes depending on how they were created.</p>
<ul>
<li>Primitives are equal if they have the same token spelling.</li>
<li>Derived operations are equal if they are derived by the same rule and each corresponding component is the same.</li>
<li>Block instances are equal if they are the same instance.</li>
</ul>
<p>This means that block instance equality indicates identity in the context of mutability: two block instances are equal if any change of state in one would be reflected in the other as well. The concept of identity holds even if the blocks in question have no way of changing or accessing state. For example, <code><span class='Function'>=</span><span class='Modifier2'>○</span><span class='Brace'>{</span><span class='Value'>𝕩</span><span class='Separator'>⋄</span><span class='Brace'>{</span><span class='Value'>𝕩</span><span class='Brace'>}}</span><span class='Modifier'>˜</span><span class='String'>@</span></code> is <code><span class='Number'>0</span></code> while <code><span class='Function'>=</span><span class='Modifier'>˜</span><span class='Modifier2'>○</span><span class='Brace'>{</span><span class='Value'>𝕩</span><span class='Separator'>⋄</span><span class='Brace'>{</span><span class='Value'>𝕩</span><span class='Brace'>}}</span><span class='String'>@</span></code> is <code><span class='Number'>1</span></code>.</p>
<h2 id="array-functionality">Array functionality</h2>
<p>Several subsets of primitives, or dedicated operations, are used to manipulate arrays in the reference implementation.</p>
<ul>
<li><code><span class='Function'>IsArray</span></code> returns <code><span class='Number'>1</span></code> if the argument is an array and <code><span class='Number'>0</span></code> if it's an atom.</li>
</ul>
<p>The following functions translate between arrays and the two lists that define them: the shape and ravel.</p>
<ul>
<li><strong>Shape</strong> (<code><span class='Function'>≢</span></code>) returns the shape of array <code><span class='Value'>𝕩</span></code>, as a list of natural numbers.</li>
<li><strong>Deshape</strong> (monadic <code><span class='Function'>⥊</span></code>) returns the ravel of array <code><span class='Value'>𝕩</span></code>, that is, the list of its elements.</li>
<li><strong>Reshape</strong> (dyadic <code><span class='Function'>⥊</span></code>) returns an array with the same ravel as <code><span class='Value'>𝕩</span></code> with shape <code><span class='Value'>𝕨</span></code>. It can be assumed that <code><span class='Function'>≢</span><span class='Value'>𝕩</span></code> and <code><span class='Value'>𝕨</span></code> have the same product.</li>
</ul>
<p>The following functions manipulate lists. In these functions, a valid index for list <code><span class='Value'>l</span></code> is a natural number less than the length of <code><span class='Value'>l</span></code>.</p>
<ul>
<li><strong>Range</strong> gives the list of length <code><span class='Value'>𝕩</span></code> (a natural number) with value <code><span class='Value'>i</span></code> at any index <code><span class='Value'>i</span></code>.</li>
<li><strong>Pick</strong> (<code><span class='Function'>⊑</span></code>) selects the element at index <code><span class='Value'>𝕨</span></code> from list <code><span class='Value'>𝕩</span></code>.</li>
<li><code><span class='Modifier'>_amend</span></code> returns an array identical to list <code><span class='Value'>𝕩</span></code> except that the element at index <code><span class='Value'>𝕗</span></code> is changed to <code><span class='Value'>𝕨</span></code>.</li>
</ul>
<h2 id="inferred-functionality">Inferred functionality</h2>
<p>Inferred properties are specified in <a href="inferred.html">their own document</a>, not in the reference implementation.</p>
<ul>
<li><code><span class='Function'>Identity</span></code> gives the identity value for reduction by function <code><span class='Function'>𝕏</span></code>.</li>
<li><strong>Undo</strong> (<code><span class='Modifier'>⁼</span></code>) gives a partial right inverse for function <code><span class='Function'>𝔽</span></code>.</li>
<li><code><span class='Function'>Fill</span></code> gives the enclose of the fill value for array <code><span class='Value'>𝕩</span></code>.</li>
</ul>
<h2 id="other-provided-functionality">Other provided functionality</h2>
<ul>
<li><strong>Assert</strong> (<code><span class='Function'>!</span></code>) causes an error if the argument is not <code><span class='Number'>1</span></code>. If <code><span class='Value'>𝕨</span></code> is provided, it gives a message to be associated with this error (which can be any value, not necessarily a string).</li>
</ul>
<h2 id="commentary-on-other-primitives">Commentary on other primitives</h2>
<p>As noted above, see <a href="https://github.com/mlochbaum/BQN/blob/master/spec/reference.bqn">reference.bqn</a> for the authoritative definitions. Commentary here gives an overall description and highlights implementation subtleties and edge cases.</p>
<h3 id="combinators">Combinators</h3>
<p>There's little to say about BQN's true combinators, since each is simply a pattern of function application. All primitive combinators use their operands as functions, and thus treat a data operand as a constant function.</p>
<ul>
<li><strong>Choose</strong> (<code><span class='Modifier2'>◶</span></code>) is later redefined to use the complete <code><span class='Function'>⊑</span></code> rather than the simple version assumed (using this primitive means it's not a true combinator).</li>
<li><strong>Constant</strong> (<code><span class='Modifier'>˙</span></code>)</li>
<li><strong>Valences</strong> (<code><span class='Modifier2'>⊘</span></code>) uses a trick with ambivalent <code><span class='Function'>-</span></code> to find out whether there's a left argument, described below.</li>
<li><strong>Right</strong> (<code><span class='Function'>⊢</span></code>)</li>
<li><strong>Left</strong> (<code><span class='Function'>⊣</span></code>)</li>
<li><strong>Self</strong>/<strong>Swap</strong> (<code><span class='Modifier'>˜</span></code>)</li>
<li><strong>Atop</strong> (<code><span class='Modifier2'>∘</span></code>)</li>
<li><strong>Over</strong> (<code><span class='Modifier2'>○</span></code>)</li>
<li><strong>Before</strong>/<strong>Bind</strong> (<code><span class='Modifier2'>⊸</span></code>)</li>
<li><strong>After</strong>/<strong>Bind</strong> (<code><span class='Modifier2'>⟜</span></code>)</li>
</ul>
<p>The somewhat complicated definition of Valences could be replaced with <code><span class='Brace'>{</span><span class='Function'>𝔽</span><span class='Value'>𝕩;𝕨</span><span class='Function'>𝔾</span><span class='Value'>𝕩</span><span class='Brace'>}</span></code> using headers. However, reference.bqn uses a simple subset of BQN's syntax that doesn't include headers. Instead, the definition relies on the fact that <code><span class='Value'>𝕨</span></code> works like <code><span class='Nothing'>·</span></code> if no left argument is given: <code><span class='Paren'>(</span><span class='Number'>1</span><span class='Modifier'>˙</span><span class='Value'>𝕨</span><span class='Paren'>)</span><span class='Function'>-</span><span class='Number'>0</span></code> is <code><span class='Number'>1</span><span class='Function'>-</span><span class='Number'>0</span></code> or <code><span class='Number'>1</span></code> if <code><span class='Value'>𝕨</span></code> is present and <code><span class='Paren'>(</span><span class='Number'>1</span><span class='Modifier'>˙</span><span class='Nothing'>·</span><span class='Paren'>)</span><span class='Function'>-</span><span class='Number'>0</span></code> otherwise: this reduces to <code><span class='Nothing'>·</span><span class='Function'>-</span><span class='Number'>0</span></code> or <code><span class='Number'>0</span></code>.</p>
<h3 id="array-properties">Array properties</h3>
<p>The reference implementations extend Shape (<code><span class='Function'>≢</span></code>) to atoms as well as arrays, in addition to implementing other properties. In all cases, an atom behaves as if it has shape <code><span class='Bracket'>⟨⟩</span></code>. The functions in this section never cause an error.</p>
<ul>
<li><strong>Shape</strong> (<code><span class='Function'>≢</span></code>) gives the shape of an array or atom.</li>
<li><strong>Rank</strong> (<code><span class='Function'>=</span></code>) gives the length of the shape.</li>
<li><strong>Length</strong> (<code><span class='Function'>≠</span></code>) gives the number of major cells, or <code><span class='Number'>1</span></code> for an argument of rank <code><span class='Number'>0</span></code>.</li>
<li><strong>Depth</strong> (<code><span class='Function'>≡</span></code>) gives the nesting depth. It ignores the shapes of arrays, and considering only the depths of their elements.</li>
</ul>
<h3 id="arithmetic">Arithmetic</h3>
<p>Arithmetic functions not already provided are defined in layer 1. These definitions, like the provided functions, apply to atoms only; they should be extended to arrays using the <code><span class='Modifier'>_perv</span></code> modifier from layer 2.</p>
<ul>
<li><strong>Sign</strong> (<code><span class='Function'>×</span></code>) </li>
<li><strong>Square Root</strong> and <strong>Root</strong> (<code><span class='Function'>√</span></code>) are defined in terms of Power. If a dedicated implementation is used for square roots, then Power should check for a right argument of <code><span class='Number'>0.5</span></code> and use this implementation in order to maintain consistency.</li>
<li><strong>Ceiling</strong> (<code><span class='Function'>⌈</span></code>) is like Floor, but rounds up instead of down.</li>
<li><strong>Not</strong> (<code><span class='Function'>¬</span></code>) is a linear extension of logical negation, and <strong>Span</strong> (<code><span class='Function'>¬</span></code>) adds the left argument.</li>
<li><strong>And</strong> (<code><span class='Function'>∧</span></code>) and <strong>Or</strong> (<code><span class='Function'>∨</span></code>) are bilinear extensions of the boolean functions.</li>
<li><strong>Minimum</strong> (<code><span class='Function'>⌊</span></code>) and <strong>Maximum</strong> (<code><span class='Function'>⌈</span></code>) return the smaller or larger of the arguments, respectively. They are <em>not required</em> to be implemented for character arguments, and may give an error if either argument is a character.</li>
<li><strong>Absolute Value</strong> (<code><span class='Function'>|</span></code>)</li>
<li><strong>Modulus</strong> (<code><span class='Function'>|</span></code>) is an extension of modular division to real numbers. As it uses floor instead of truncation, it's not the same as the <code><span class='Value'>%</span></code> operator from C or other languages when <code><span class='Value'>𝕨</span><span class='Function'>&lt;</span><span class='Number'>0</span></code>.</li>
<li>Comparisons <strong>Less Than</strong> (<code><span class='Function'>&lt;</span></code>), <strong>Greater Than</strong> (<code><span class='Function'>&gt;</span></code>), <strong>Greater Than or Equal to</strong> (<code><span class='Function'>≥</span></code>), and <strong>Not Equals</strong> (<code><span class='Function'>≠</span></code>) are defined in terms of the two provided comparisons.</li>
</ul>
<h3 id="iteration-modifiers">Iteration modifiers</h3>
<p>Modifiers for iteration are defined in layers 1, 2, and 4. Two 2-modifiers, <code><span class='Modifier2'>⚇</span></code> and <code><span class='Modifier2'>⎉</span></code>, use a list of numbers obtained by applying the right operand to the arguments in order to control application. This list has one to three elements: if all three are given then they correspond to the monadic, left, and right arguments; if one is given then it controls all three; and if two are given then they control the left argument, and the right and monadic arguments.</p>
<p><strong>Table</strong> (<code><span class='Modifier'>⌜</span></code>) and <strong>Each</strong> (<code><span class='Modifier'>¨</span></code>) map over the elements of arrays to produce result elements. They convert atom arguments to unit arrays. With one argument, the two modifiers are the same; with two, they differ in how they pair elements. Table pairs every element of the left argument with every element of the right, giving a result shape <code><span class='Value'>𝕨</span><span class='Function'>∾</span><span class='Modifier2'>○</span><span class='Function'>≢</span><span class='Value'>𝕩</span></code>. Each uses leading axis agreement: it requires one argument's shape to be a prefix of the other's (if the arguments have the same rank, then the shapes must match and therefore be mutual prefixes). This causes each element of the lower-rank argument to correspond to a cell of the higher-rank one; it's repeated to pair it with each element of that cell. The result shape is the shape of the higher-rank argument.</p>
<p><strong>Depth</strong> (<code><span class='Modifier2'>⚇</span></code>) is nearly a generalization of Each: <code><span class='Modifier'>¨</span></code> is equivalent to <code><span class='Modifier2'>⚇</span><span class='Number'>¯1</span></code>, except that <code><span class='Modifier2'>⚇</span><span class='Number'>¯1</span></code> doesn't enclose its result if all arguments are atoms. The list given by the right operand specifies how deeply to recurse into the arguments. A negative number <code><span class='Function'>-</span><span class='Value'>n</span></code> means to recurse <code><span class='Value'>n</span></code> times <em>or</em> until the argument is an atom, while a positive number <code><span class='Value'>n</span></code> means to recurse until the argument has depth <code><span class='Value'>n</span></code> or less. Recursion continues until all arguments have met the criterion for stopping.</p>
<p><strong>Rank</strong> (<code><span class='Modifier2'>⎉</span></code>) applies the left operand to cells of the arguments of the specified ranks, forming a result whose cells are the results. <strong>Cells</strong> (<code><span class='Modifier'>˘</span></code>) is identical to <code><span class='Modifier2'>⎉</span><span class='Number'>¯1</span></code>, and applies to major cells of the arguments, where a value of rank less than 1 is considered its own major cell. All results must have the same shape, as with elements of the argument to Merge (<code><span class='Function'>&gt;</span></code>). The combined result is always an array, but results of the left operand can be atoms: an atom result will be enclosed to give a 0-cell. If a specified rank is a natural number <code><span class='Value'>n</span></code>, Rank applies the operand to <code><span class='Value'>n</span></code>-cells of the corresponding argument, or the entire argument if it has rank less than or equal to <code><span class='Value'>n</span></code>. If instead it's a negative integer <code><span class='Function'>-</span><span class='Value'>n</span></code>, then an effective rank of <code><span class='Number'>0</span><span class='Function'>⌈</span><span class='Value'>k</span><span class='Function'>-</span><span class='Value'>n</span></code> is used, so that the entire argument is used exactly when <code><span class='Value'>k</span><span class='Function'>=</span><span class='Number'>0</span></code>. Thus an atom will always be passed unchanged to the operand; in particular, Rank does not enclose it. Like Each, Rank matches cells of its arguments according to leading axis agreement, so that a cell of one argument might be paired with multiple cells of the other.</p>
<p><strong>Fold</strong> (<code><span class='Modifier'>´</span></code>), <strong>Insert</strong> (<code><span class='Modifier'>˝</span></code>), and <strong>Scan</strong> (<code><span class='Modifier'>`</span></code>) repeatedly apply a function between parts of an array. Fold requires the argument to have rank 1 and applies the operand between its elements, while Insert requires it to have rank 1 or more and applies it between the cells. For each of these two functions, the operand is applied beginning at the end of the array, and an <a href="inferred.html#identities">identity</a> value is returned if the array is empty. While these functions reduce multiple values to a single result, Scan returns many results and preserves the shape of its argument. It requires the argument to have rank at least 1, and applies the function between elements along columns—that is, from one element in a major cell to the one in the same position of the next major cell. This application begins at the first major cell of the array. Scan never uses the identity element of its operand because if the argument is empty then the result, which has the same shape, will be empty as well.</p>
<p><strong>Repeat</strong> (<code><span class='Modifier2'>⍟</span></code>) applies the operand function, or its <a href="inferred.html#undo">inverse</a>, several times in sequence. The right operand must consist only of integer atoms (arranged in arrays of any depth), and each number there is replaced with the application of the left operand that many times to the arguments. If a left argument is present, then it's reused each time, as if it were bound to the operand function. For a negative number <code><span class='Function'>-</span><span class='Value'>n</span></code>, the function is &quot;applied&quot; <code><span class='Function'>-</span><span class='Value'>n</span></code> times by undoing it <code><span class='Value'>n</span></code> times. In both directions, the total number of times the function is applied is the maximum of all numbers present: results must be saved if intermediate values are needed.</p>