diff options
Diffstat (limited to 'docs/spec/primitive.html')
| -rw-r--r-- | docs/spec/primitive.html | 34 |
1 files changed, 17 insertions, 17 deletions
diff --git a/docs/spec/primitive.html b/docs/spec/primitive.html index c3f4ab2f..128fd24f 100644 --- a/docs/spec/primitive.html +++ b/docs/spec/primitive.html @@ -4,11 +4,11 @@ <title>Specification: BQN primitives</title> </head> <div class="nav">(<a href="https://github.com/mlochbaum/BQN">github</a>) / <a href="../index.html">BQN</a> / <a href="index.html">spec</a></div> -<h1 id="specification-bqn-primitives">Specification: BQN primitives</h1> +<h1 id="specification-bqn-primitives"><a class="header" href="#specification-bqn-primitives">Specification: BQN primitives</a></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> +<h2 id="pervasive-primitives"><a class="header" href="#pervasive-primitives">Pervasive primitives</a></h2> <p>Functions in this section are defined for atoms only; the reference implementations extend them to arrays.</p> -<h3 id="arithmetic">Arithmetic</h3> +<h3 id="arithmetic"><a class="header" href="#arithmetic">Arithmetic</a></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> @@ -25,7 +25,7 @@ </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 or equal to 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> +<h3 id="comparison"><a class="header" href="#comparison">Comparison</a></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> @@ -40,7 +40,7 @@ <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> +<h2 id="array-functionality"><a class="header" href="#array-functionality">Array functionality</a></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> @@ -57,23 +57,23 @@ <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> +<h2 id="inferred-functionality"><a class="header" href="#inferred-functionality">Inferred functionality</a></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> +<h2 id="other-provided-functionality"><a class="header" href="#other-provided-functionality">Other provided functionality</a></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> <ul> <li><strong>Catch</strong> (<code><span class='Modifier2'>⎊</span></code>) evaluates <code><span class='Function'>𝔽</span></code> on the arguments <code><span class='Value'>𝕨</span></code> (if present) and <code><span class='Value'>𝕩</span></code>. If <code><span class='Function'>𝔽</span></code> completes without error it returns the result, but if evaluation of <code><span class='Function'>𝔽</span></code> results in an error then the error is suppressed, and Catch evaluates <code><span class='Function'>𝔾</span></code> on the arguments and returns the result. Errors in <code><span class='Function'>𝔾</span></code> are not caught. Catch only prevents evaluation errors, and not syntax errors: these are considered errors in the program as a whole rather than any particular part of it.</li> </ul> -<h2 id="commentary-on-other-primitives">Commentary on other primitives</h2> +<h2 id="commentary-on-other-primitives"><a class="header" href="#commentary-on-other-primitives">Commentary on other primitives</a></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> +<h3 id="combinators"><a class="header" href="#combinators">Combinators</a></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> @@ -88,7 +88,7 @@ <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> +<h3 id="array-properties"><a class="header" href="#array-properties">Array properties</a></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> @@ -96,7 +96,7 @@ <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> +<h3 id="arithmetic"><a class="header" href="#arithmetic">Arithmetic</a></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> @@ -109,7 +109,7 @@ <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'><</span><span class='Number'>0</span></code>.</li> <li>Comparisons <strong>Less Than</strong> (<code><span class='Function'><</span></code>), <strong>Greater Than</strong> (<code><span class='Function'>></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> +<h3 id="iteration-modifiers"><a class="header" href="#iteration-modifiers">Iteration modifiers</a></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>The iteration modifiers <code><span class='Modifier'>⌜¨</span><span class='Modifier2'>⚇</span><span class='Modifier'>˘</span><span class='Modifier2'>⎉</span></code> process elements or cells in index order, that is, according to lexicographic ordering of indices or according to simple numeric ordering of the indices in the Deshaped (<code><span class='Function'>⥊</span></code>) arguments. When both arguments are mapped over independently, the left argument is mapped over "first", or as an outer loop: one part of the left argument is paired with each part of the right in turn, then the next part of the left argument, and so on.</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> @@ -118,13 +118,13 @@ <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>A left argument for any of the three reduction-based modifiers indicates an initial value to be used, so that the first application of the operand function applies not to two values from <code><span class='Value'>𝕩</span></code> but instead to a value from <code><span class='Value'>𝕨</span></code> and a value from <code><span class='Value'>𝕩</span></code>. In Fold and Insert, the entire value <code><span class='Value'>𝕨</span></code> is the initial value, while in Scan, <code><span class='Value'>𝕨</span></code> is an array of initial values, which must have shape <code><span class='Number'>1</span><span class='Function'>↓≢</span><span class='Value'>𝕩</span></code>.</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 "applied" <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> -<h3 id="restructuring">Restructuring</h3> +<h3 id="restructuring"><a class="header" href="#restructuring">Restructuring</a></h3> <p><strong>Enclose</strong> (<code><span class='Function'><</span></code>) forms a unit array that contains its argument.</p> <p><strong>Merge</strong> (<code><span class='Function'>></span></code>) combines the outer axes of an array of arrays with inner axes: it requires that all elements of its argument have the same shape, and creates an array such that <code><span class='Paren'>(</span><span class='Value'>i</span><span class='Function'>∾</span><span class='Value'>j</span><span class='Paren'>)</span><span class='Function'>⊑></span><span class='Value'>𝕩</span></code> is <code><span class='Value'>i</span><span class='Function'>⊑</span><span class='Value'>j</span><span class='Function'>⊑</span><span class='Value'>𝕩</span></code>. It also accepts atom elements of <code><span class='Value'>𝕩</span></code>, converting them to unit arrays, or an atom argument, which is returned unchanged. <strong>Solo</strong> and <strong>Couple</strong> (<code><span class='Function'>≍</span></code>) turn one or two arguments into major cells of the result and can be defined easily in terms of Merge.</p> <p><strong>Join To</strong> (<code><span class='Function'>∾</span></code>) combines its two arguments along an existing initial axis, unless both arguments are units, in which case it creates an axis and is identical to Couple (<code><span class='Function'>≍</span></code>). The arguments must differ in rank by at most 1, and the result rank is equal to the maximum of 1 and the higher argument rank. Each argument with rank less than the result, and each major cell of an argument with rank equal to it, becomes a major cell of the result, with cells from the left argument placed before those from the right. <strong>Join</strong> (<code><span class='Function'>∾</span></code>) generalizes the equal-rank subset of this behavior to an array of values instead of just two. The argument must be an array (unlike Merge), and its elements must all the same rank, which is at least the argument rank. Atom elements are treated as unit arrays. Then "outer" argument axes are matched up with leading "inner" element axes, and elements are joined along these axes. In order to allow this, the length of an element along a particular axis must depend only on the position along the corresponding axis in the argument. An empty argument to Join is return unchanged, as though the element rank is equal to the argument rank.</p> <p><strong>Deshape</strong> (<code><span class='Function'>⥊</span></code>) differs from the provided function (which returns the element list of an array) only in that it accepts an atom, returning a one-element list containing it. <strong>Reshape</strong> (<code><span class='Function'>⥊</span></code>) is extended in numerous ways. It accepts any list of natural numbers (including as a unit array or atom) for the left argument and any right argument; <code><span class='Value'>𝕩</span></code> is deshaped first so that it is treated as a list of elements. These elements are repeated cyclically to fill the result array in ravel order. If <code><span class='Value'>𝕩</span></code> is empty then a non-empty requested result shape causes an error. Furthermore, at most one element of <code><span class='Value'>𝕨</span></code> can be a "length code": one of the primitives <code><span class='Modifier2'>∘</span><span class='Function'>⌊⌽↑</span></code>. In this case, a target length is computed from the number of elements in <code><span class='Value'>𝕩</span></code> divided by the product of the other elements of <code><span class='Value'>𝕨</span></code> (which must not be zero). If the target length is an integer then it is used directly for the length code. Otherwise, an error is given if the length code is <code><span class='Modifier2'>∘</span></code>, and the target length is rounded down if the code is <code><span class='Function'>⌊</span></code> and up if it's <code><span class='Function'>⌽</span></code> or <code><span class='Function'>↑</span></code>. With code <code><span class='Function'>⌽</span></code>, elements are repeated cyclically as usual, but with code <code><span class='Function'>↑</span></code>, the extra elements after each argument element is used are fill values for <code><span class='Value'>𝕩</span></code>.</p> <p><strong>Transpose</strong> (<code><span class='Function'>⍉</span></code>) reorders axes of its argument to place the first axis last; if the argument has one or fewer axes then it's enclosed if it's an atom and otherwise returned unchanged. <strong>Reorder Axes</strong> (<code><span class='Function'>⍉</span></code>) requires the left argument to be a list or unit of natural numbers, with length at most the rank of the right argument. This list is extended to match the right argument rank exactly by repeatedly appending the least unused natural number (for example, given <code><span class='Number'>1</span><span class='Ligature'>‿</span><span class='Number'>3</span><span class='Ligature'>‿</span><span class='Number'>0</span><span class='Ligature'>‿</span><span class='Number'>0</span></code>, <code><span class='Number'>2</span></code> is appended). After extension, it specifies a result axis for each axis of the right argument. There must be no gaps in the list: that is, with the result rank equal to one plus the greatest value present, every result axis must appear at least once. Now each argument axis is "sent to" the specified result axis: in terms of indices, <code><span class='Value'>i</span><span class='Function'>⊑</span><span class='Value'>𝕨</span><span class='Function'>⍉</span><span class='Value'>𝕩</span></code> is <code><span class='Paren'>(</span><span class='Value'>𝕨</span><span class='Function'>⊏</span><span class='Value'>i</span><span class='Paren'>)</span><span class='Function'>⊑</span><span class='Value'>𝕩</span></code> if <code><span class='Value'>𝕨</span></code> is complete. If multiple argument axes correspond to the same result axis, then a diagonal is taken, and it's as long as the shortest of those argument axes. Like Transpose, Reorder Axes encloses <code><span class='Value'>𝕩</span></code> if it's an atom, so that its result is always an array.</p> -<h3 id="indices-and-selection">Indices and selection</h3> +<h3 id="indices-and-selection"><a class="header" href="#indices-and-selection">Indices and selection</a></h3> <p>Each element in an array <code><span class='Value'>s</span><span class='Function'>⥊</span><span class='Value'>e</span></code> is associated with an <em>index</em>, which is a list of natural numbers <code><span class='Value'>i</span></code> such that <code><span class='Function'>∧</span><span class='Modifier'>´</span><span class='Value'>i</span><span class='Function'><</span><span class='Value'>s</span></code>. The list of all indices, which corresponds to the element list <code><span class='Value'>e</span></code>, contains all such lists <code><span class='Value'>i</span></code> in lexicographic order. That is, index <code><span class='Value'>i</span></code> comes before <code><span class='Value'>j</span></code> exactly when the two indices are not the same, and <code><span class='Value'>i</span></code> has the smaller value at the first position where they are unequal. The index of an element along a particular axis <code><span class='Value'>a</span></code> is the value <code><span class='Value'>a</span><span class='Function'>⊑</span><span class='Value'>i</span></code>.</p> <p><strong>Range</strong> (<code><span class='Function'>↕</span></code>) is extended to apply to a list of natural numbers, in addition to the provided case of a single natural number (an enclosed natural number <code><span class='Value'>𝕩</span></code> should still result in an error). For a list <code><span class='Value'>𝕩</span></code>, the result is an array of shape <code><span class='Value'>𝕩</span></code> in which the value at a given index is that index, as a list of natural numbers. That is, <code><span class='Value'>i</span><span class='Function'>≡</span><span class='Value'>i</span><span class='Function'>⊑↕</span><span class='Value'>𝕩</span></code> for any list of natural numbers <code><span class='Value'>i</span></code> with <code><span class='Function'>∧</span><span class='Modifier'>´</span><span class='Value'>i</span><span class='Function'><</span><span class='Value'>𝕩</span></code>.</p> <p><strong>Pick</strong> (<code><span class='Function'>⊑</span></code>) is extended to array left arguments. In this case, it requires every depth-1 array in the nested structure of <code><span class='Value'>𝕨</span></code> to be a valid index list for <code><span class='Value'>𝕩</span></code>, and every atom to be contained in one of these lists. The result is <code><span class='Value'>𝕨</span></code> with each index list replaced by the element of <code><span class='Value'>𝕩</span></code> at that index. In the simple case where <code><span class='Value'>𝕨</span></code> itself is an index list, the result is the element of <code><span class='Value'>𝕩</span></code> at index <code><span class='Value'>𝕨</span></code>.</p> @@ -133,14 +133,14 @@ <p><strong>First Cell</strong> (<code><span class='Function'>⊏</span></code>) selects the initial major cell of <code><span class='Value'>𝕩</span></code>, giving an error if <code><span class='Value'>𝕩</span></code> has rank 0 or length 0.</p> <p><strong>Group</strong> (<code><span class='Function'>⊔</span></code>) performs an opposite operation to Select, so that <code><span class='Value'>𝕨</span></code> specifies not the argument index that result values come from, but the result index that argument values go to. The general case is that <code><span class='Value'>𝕨</span></code> is a list of arrays of numbers; if it has depth less than 2 it's converted to this form by first enclosing it if it's an atom, then placing it in a length-1 list. After this transformation, the result rank is <code><span class='Function'>≠</span><span class='Value'>𝕨</span></code>, and each result element has rank <code><span class='Paren'>(</span><span class='Function'>≠</span><span class='Value'>𝕨</span><span class='Paren'>)</span><span class='Function'>+</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='Function'>=</span><span class='Modifier'>¨</span><span class='Value'>𝕨</span></code>, with the initial <code><span class='Function'>≠</span><span class='Value'>𝕨</span></code> axes corresponding to elements of <code><span class='Value'>𝕨</span></code> and the remainder to trailing axes of <code><span class='Value'>𝕩</span></code>. Each atom in <code><span class='Value'>𝕨</span></code> can be either a natural number or <code><span class='Number'>¯1</span></code> (which indicates the corresponding position in <code><span class='Value'>𝕩</span></code> will be omitted). If <code><span class='Number'>¯1</span></code> doesn't appear, the result has the property that each cell of <code><span class='Value'>𝕩</span></code> appears in the corresponding element of <code><span class='Value'>𝕨</span><span class='Function'>⊏</span><span class='Value'>𝕨</span><span class='Function'>⊔</span><span class='Value'>𝕩</span></code>. More concretely, the length of the result along axis <code><span class='Value'>a</span></code> is the maximum value in <code><span class='Value'>a</span><span class='Function'>⊑</span><span class='Value'>𝕨</span></code> plus one, or zero if <code><span class='Value'>a</span><span class='Function'>⊑</span><span class='Value'>𝕨</span></code> is empty. Axis <code><span class='Value'>a</span></code> corresponds to <code><span class='Function'>=</span><span class='Value'>a</span><span class='Function'>⊑</span><span class='Value'>𝕨</span></code> axes in <code><span class='Value'>𝕩</span></code>, and an element of the result at position <code><span class='Value'>i</span></code> along this axis contains all positions in <code><span class='Value'>𝕩</span></code> where <code><span class='Value'>i</span><span class='Function'>=</span><span class='Value'>a</span><span class='Function'>⊑</span><span class='Value'>𝕨</span></code>. There may be multiple such positions, and they're arranged along axis <code><span class='Value'>a</span></code> of that result element according to their index order in <code><span class='Value'>𝕩</span></code>. The shapes of components of <code><span class='Value'>𝕨</span></code> must match the corresponding axes of <code><span class='Value'>𝕩</span></code>, except for rank-1 components of <code><span class='Value'>𝕨</span></code>, which can match or have an extra element. This element, which like the others is either a natural number or <code><span class='Number'>¯1</span></code>, gives the minimum length of the result axis corresponding to the component of <code><span class='Value'>𝕨</span></code> in question, but otherwise does not affect the result. <strong>Group Indices</strong> treats its argument <code><span class='Value'>𝕩</span></code> as a left argument for Group and uses a right argument made up of indices, which is <code><span class='Function'>↕≠</span><span class='Value'>𝕩</span></code> if <code><span class='Value'>𝕩</span></code> has depth 1 and <code><span class='Function'>↕∾≢</span><span class='Modifier'>¨</span><span class='Value'>𝕩</span></code> if it has depth 2. Because the depth-1 case uses atomic indices, <code><span class='Value'>𝕩</span></code> is required to be a list (and it can't be an atom). Much like Range, the result has depth one higher than the argument.</p> <p><strong>Indices</strong> (<code><span class='Function'>/</span></code>) applies to a list of natural numbers, and returns a list of natural numbers. The result contains <code><span class='Value'>i</span><span class='Function'>⊑</span><span class='Value'>𝕩</span></code> copies of each natural number index <code><span class='Value'>i</span></code> for <code><span class='Value'>𝕩</span></code>, in increasing order.</p> -<h3 id="structural-manipulation">Structural manipulation</h3> +<h3 id="structural-manipulation"><a class="header" href="#structural-manipulation">Structural manipulation</a></h3> <p>Monadic structural functions work on the first axis of the argument, so they require it to have rank at least 1. <strong>Reverse</strong> (<code><span class='Function'>⌽</span></code>) reverses the ordering of the major cells of <code><span class='Value'>𝕩</span></code>. <strong>Nudge</strong> (<code><span class='Function'>»</span></code>) shifts them forward, removing the last and placing a major cell made up of fill elements at the beginning, while <strong>Nudge Back</strong> (<code><span class='Function'>«</span></code>) does the same in the reverse direction, so it removes the first cell and places fills at the end. <strong>Prefixes</strong> (<code><span class='Function'>↑</span></code>) and <strong>Suffixes</strong> (<code><span class='Function'>↓</span></code>) each return lists with length one higher than <code><span class='Value'>𝕩</span></code>, whose elements are arrays with the same rank as <code><span class='Value'>𝕩</span></code>. For Prefixes, the element of the result at index <code><span class='Value'>i</span></code> contains the first <code><span class='Value'>i</span></code> major cells of <code><span class='Value'>𝕩</span></code> in order, and for Suffixes, it contains all but these major cells.</p> <p>The remainder of the functions discussed in this section are dyadic. For all of these, an atom value for <code><span class='Value'>𝕩</span></code> is treated as an array by enclosing it before acting, so that the result is never an atom. There are four functions for which <code><span class='Value'>𝕨</span></code> is a list of whole numbers—but an atomic number or enclosed number is also permitted, and treated as a 1-element list—and its elements are matched with leading axes of <code><span class='Value'>𝕩</span></code>. These functions independently manipulate each axis: one way to define such a process is to consider lists running along the axis, where every element of the index is fixed except one. A change to this axis retains the fixed indices, but can move elements from one location to another along the variable index, add fill elements, or split the axis into two axes. A change to a different axis can rearrange these lists along the original axis, but can't affect the placement of elements within them. In the reference implementations, working on leading axes is accomplished using the Cells (<code><span class='Modifier'>˘</span></code>) modifier recursively, so that action on the first axes doesn't use Cells, on the next is affected by Cells once, then twice, and so on.</p> <p><strong>Rotate</strong> (<code><span class='Function'>⌽</span></code>) is the simplest of these four functions: each element of <code><span class='Value'>𝕨</span></code> gives an amount to rotate the corresponding axis, where a rotation of <code><span class='Value'>r</span></code> moves the element at index <code><span class='Value'>i</span><span class='Function'>+</span><span class='Value'>r</span></code> to <code><span class='Value'>i</span></code> when all indices are taken modulo the length of the axis. <strong>Windows</strong> (<code><span class='Function'>↕</span></code>) splits each axis of <code><span class='Value'>𝕩</span></code> that corresponds to an element of <code><span class='Value'>𝕨</span></code> in two, so that the result has one set of axes corresponding to elements of <code><span class='Value'>𝕨</span></code>, then another, then the unchanged trailing axes. The second set of axes has lengths given by <code><span class='Value'>𝕨</span></code> (which must consist of natural numbers), while the first has lengths <code><span class='Value'>s</span><span class='Function'>¬</span><span class='Value'>𝕨</span></code>, where <code><span class='Value'>s</span></code> contains the lengths of leading axes of <code><span class='Value'>𝕩</span></code>. Position <code><span class='Value'>i</span></code> in the first set of axes and <code><span class='Value'>j</span></code> in the second corresponds to <code><span class='Value'>i</span><span class='Function'>+</span><span class='Value'>j</span></code> in the argument, so that fixing one of these positions and varying the other gives a slice of the argument. In both Rotate and Windows, the length of <code><span class='Value'>𝕨</span></code> is at most the rank of <code><span class='Value'>𝕩</span></code>.</p> <p><strong>Take</strong> (<code><span class='Function'>↑</span></code>) offers several possibilities. The absolute value of <code><span class='Value'>𝕨</span></code> gives the final lengths of the axes in the result. It may be positive to indicate that the axis aligns with <code><span class='Value'>𝕩</span></code> at the beginning, or negative to indicate it aligns at the end. A zero value gives no result elements, so there is no need to consider alignment. If the absolute value of an element of <code><span class='Value'>𝕨</span></code> is smaller than or equal to the corresponding length in <code><span class='Value'>𝕩</span></code>, then the first or last few elements are taken along that axis. If it is larger, then instead fill elements are added to the end (if positive) or beginning (if negative) to make up the difference in length. <strong>Drop</strong> (<code><span class='Function'>↓</span></code>) gives <code><span class='Value'>𝕨</span></code> a similar meaning, but excludes all elements that Take includes (maintaining the order of the retained ones). The result of Drop never uses fill elements. In a case where Take would use fill elements, it would include all positions from <code><span class='Value'>𝕩</span></code>, so Drop should include none of them, and the result will have length <code><span class='Number'>0</span></code> for that axis. Take and Drop are extended to allow an argument with length greater than the rank of <code><span class='Value'>𝕩</span></code>. In this case leading length-1 axes are added to <code><span class='Value'>𝕩</span></code> so that its rank matches <code><span class='Value'>𝕨</span></code> before taking or dropping.</p> <p><strong>Replicate</strong> (<code><span class='Function'>/</span></code>) is similar to the four dyadic structural functions above, but <code><span class='Value'>𝕨</span></code> gives a list of containing <em>lists</em> of natural numbers, or plain or enclosed natural numbers, instead of a simple list. If <code><span class='Value'>𝕨</span></code> has depth less than <code><span class='Number'>2</span></code>, it's considered to be a single value corresponding to one axis of <code><span class='Value'>𝕩</span></code>, while if it has depth <code><span class='Number'>2</span></code> then it's a list of values. If <code><span class='Value'>𝕨</span></code> is the empty list <code><span class='Bracket'>⟨⟩</span></code> then it is defined to be in the second case despite having a depth of <code><span class='Number'>1</span></code>. On a single axis of <code><span class='Value'>𝕩</span></code> the corresponding value <code><span class='Value'>r</span></code> from <code><span class='Value'>𝕨</span></code> is either a list or a unit: if it's a unit then it is repeated to match the length of that axis of <code><span class='Value'>𝕩</span></code>, and if it's a list it must already have the same length as that axis. Each number in <code><span class='Value'>r</span></code> now specifies the number of times to repeat the corresponding position in <code><span class='Value'>𝕩</span></code>. This is equivalent to calling Indices on <code><span class='Value'>r</span></code> and using the result for selection.</p> <p><strong>Shift Before</strong> (<code><span class='Function'>»</span></code>) and <strong>Shift After</strong> (<code><span class='Function'>«</span></code>) are derived from Join To and share most of its behavior. The difference is that only a portion of the result of Join To is returned, matching the length of <code><span class='Value'>𝕩</span></code>. This portion comes from the beginning for Shift Before and the end for Shift After. The only difference in conditions between the shift functions and Join To is that Join To allows the result to have higher rank than <code><span class='Value'>𝕩</span></code>. Shifts do not, so the rank of <code><span class='Value'>𝕩</span></code> be at least 1 and at least as high as <code><span class='Value'>𝕨</span></code>.</p> -<h3 id="searching">Searching</h3> +<h3 id="searching"><a class="header" href="#searching">Searching</a></h3> <p><strong>Match</strong> (<code><span class='Function'>≡</span></code>) indicates whether two values are considered equivalent. It always returns 0 or 1, and never causes an error. If both arguments are atoms then it is identical to <code><span class='Function'>=</span></code>, and if one is an atom and the other an array then it returns 0. If both arguments are arrays then it returns 1 only if they have the same shape and all pairs of corresponding elements match. Fill elements aren't taken into account, so that arrays that match might still differ in behavior. <strong>Not Match</strong> simply returns the complement of Match, <code><span class='Function'>¬≡</span></code>.</p> <p>Monadic search functions compare the major cells of <code><span class='Value'>𝕩</span></code> to each other. <code><span class='Value'>𝕩</span></code> must have rank at least 1. Except for Deduplicate (<code><span class='Function'>⍷</span></code>), the result is a list of numbers with the same length as <code><span class='Value'>𝕩</span></code>.</p> <ul> @@ -156,7 +156,7 @@ <li><strong>Progressive Index of</strong> (<code><span class='Function'>⊒</span></code>) processes non-principal cells in ravel order, and gives the smallest index of a principal argument cell that matches the cell that hasn't already been included in the result. Again <code><span class='Function'>≠</span><span class='Value'>𝕨</span></code> is returned for a given cell if there is no valid cell.</li> </ul> <p><strong>Find</strong> (<code><span class='Function'>⍷</span></code>) indicates positions where <code><span class='Value'>𝕨</span></code> appears as a contiguous subarray of a <code><span class='Function'>=</span><span class='Value'>𝕨</span></code>-cell of <code><span class='Value'>𝕩</span></code>. It has one result element for each such subarray of <code><span class='Value'>𝕩</span></code>, whose value is 1 if that subarray matches <code><span class='Value'>𝕩</span></code> and 0 otherwise. Find cannot result in an error unless the rank of <code><span class='Value'>𝕨</span></code> is higher than that of <code><span class='Value'>𝕩</span></code>. If <code><span class='Value'>𝕨</span></code> is longer along one axis than the corresponding trailing axis of <code><span class='Value'>𝕩</span></code>, then the result has length 0 along that axis. Any atom argument to Find is automatically enclosed.</p> -<h3 id="sorting">Sorting</h3> +<h3 id="sorting"><a class="header" href="#sorting">Sorting</a></h3> <p>Sorting functions are those that depend on BQN's array ordering. There are three kinds of sorting function, with two functions of each kind: one with an upward-pointing glyph that uses an ascending ordering (these function names are suffixed with "Up"), and one with a downward-pointing glyph and the reverse, descending, ordering ("Down"). Below, these three kinds of function are described, then the ordering rules. Except for the right argument of Bins, all arguments must have rank at least 1.</p> <p><strong>Sort</strong> (<code><span class='Function'>∧∨</span></code>) reorders the major cells of its argument so that a major cell with a lower index comes earlier in the ordering than a major cell with a higher index, or matches it. If it's possible for matching arrays to differ in behavior because of different (including undefined versus defined) fill elements, then these arrays must maintain their ordering (a stable sort is required).</p> <p><strong>Grade</strong> (<code><span class='Function'>⍋⍒</span></code>) returns a permutation describing the way the argument array would be sorted. For this reason the reference implementations simply define Sort to be selection by the grade. One way to define Grade is as a sorted version of the index list <code><span class='Function'>↕≠</span><span class='Value'>𝕩</span></code>. An index <code><span class='Value'>i</span></code> is ordered according to the corresponding major cell <code><span class='Value'>i</span><span class='Function'>⊏</span><span class='Value'>𝕩</span></code>. However, ties in the ordering are broken by ordering the index values themselves, so that no two indices are ever considered equal, and the result of sorting is well-defined (for Sort this is not an issue—matching cells are truly interchangeable). This property means that a stable sorting algorithm must be used to implement Grade functions. While cells might be ordered ascending or descending, indices are always ordered ascending, so that for example index <code><span class='Value'>i</span></code> is placed before index <code><span class='Value'>j</span></code> if either <code><span class='Value'>i</span><span class='Function'>⊏</span><span class='Value'>𝕩</span></code> comes earlier in the ordering than <code><span class='Value'>j</span><span class='Function'>⊏</span><span class='Value'>𝕩</span></code>, or if they match and <code><span class='Value'>i</span><span class='Function'><</span><span class='Value'>j</span></code>.</p> |