diff options
Diffstat (limited to 'doc')
| -rw-r--r-- | doc/functional.md | 14 | ||||
| -rw-r--r-- | doc/glossary.md | 7 | ||||
| -rw-r--r-- | doc/group.md | 20 | ||||
| -rw-r--r-- | doc/identity.md | 4 | ||||
| -rw-r--r-- | doc/indices.md | 16 | ||||
| -rw-r--r-- | doc/join.md | 4 | ||||
| -rw-r--r-- | doc/leading.md | 28 |
7 files changed, 47 insertions, 46 deletions
diff --git a/doc/functional.md b/doc/functional.md index 86621699..0556d75e 100644 --- a/doc/functional.md +++ b/doc/functional.md @@ -4,7 +4,7 @@ BQN boasts of its functional capabilities, including first-class functions. What sort of functional support does it have, and how can a BQN programmer exercise these and out themself as a Schemer at heart? -First, let's be clear about what the terms we're using mean. A language has *first-class functions* when functions (however they are defined) can be used in all the same ways as "ordinary" values like numbers and so on, such as being passed as an argument or placed in a list. Lisp and JavaScript have first-class functions, C has unsafe first-class functions via function pointers, and Java and APL don't have them as functions can't be placed in lists or used as arguments. This doesn't mean every operation is supported on functions: for instance, numbers can be added, compared, and sorted; while functions could perhaps be added to give a train, comparing or sorting them as functions (not representations) isn't computable, and BQN doesn't support any of the three operations when passing functions as arguments. +First, let's be clear about what the terms we're using mean. A language has *first-class functions* when functions (however they are defined) can be used in all the same ways as "ordinary" values like numbers and so on, such as being passed as an argument or placed in a list. Lisp and JavaScript have first-class functions, C has unsafe first-class functions via function pointers, and Java 7 and APL don't have them as functions can't be placed in lists or used as arguments. This doesn't mean every operation is supported on functions: for instance, numbers can be added, compared, and sorted; while functions could perhaps be added to give a train, comparing or sorting them as functions (not representations) isn't computable, and BQN doesn't support any of the three operations when passing functions as arguments. Traditionally, APL has worked around its lack of first-class functions with operators, that is, second-order functions. Arrays in APL are first class while functions are second class and operators are third class, and each class can act on the ones before it. However, the three-tier system has some obvious limitations that we'll discuss, and BQN removes these by making every type first class. @@ -80,13 +80,13 @@ To ← { ⟩ --> -The term *functional programming* is more contentious, and has many meanings some of which can be vague. Here I use it for what might be called *first-class functional programming*, programming that makes significant use of first-class functions; in this usage, Scheme is probably the archetypal functional programming language. However, other definitions are also worth mentioning. APL is often called a functional programming language on the grounds that functions can be assigned and manipulated, and called recursively, all characteristics it shares with Lisp. I prefer the term *function-level programming* for this usage. A newer usage, which I call *pure functional programming*, restricts the term "function" to mathematical functions, which have no side effects, so that functional programming is programming with no side effects, often using monads to accumulate effects as part of arguments and results instead. Finally, *typed functional programming* is closely associated with pure functional programming and refers to statically-typed functional languages such as Haskell, F#, and Idris (the last of which even supports *dependently-typed functional programming*, but I already said "finally" so we'll stop there). Of these, BQN supports first-class functional and function-level programming, allows but doesn't encourage pure functional programming, and does not support typed functional programming, as it is dynamically and not statically typed. +The term *functional programming* is more contentious, and has many meanings some of which can be vague. Here I use it for what might be called *first-class functional programming*, programming that makes significant use of first-class functions; in this usage, Scheme is probably the archetypal functional programming language. However, other definitions are also worth mentioning. APL is often called a functional programming language on the grounds that functions can be assigned and manipulated, and called recursively, all characteristics it shares with Lisp. I prefer the term *function-level programming* for this usage. A newer usage, which I call *pure functional programming*, restricts the term "function" to mathematical functions, which have no side effects, so that functional programming is programming with no side effects, often using monads to accumulate effects as part of arguments and results instead. Finally, *typed functional programming* is closely associated with pure functional programming and refers to languages influenced by type theory such as Haskell, F#, and Idris (the last of which even supports *dependently-typed functional programming*, but I already said "finally" so we'll stop there). Of these, BQN supports first-class functional and function-level programming, allows but doesn't encourage pure functional programming, and does not support typed functional programming, as it's dynamically and not statically typed. Another topic we are interested in is *lexical scoping* and *closures*. Lexical scoping means that the realm in which a variable exists is determined by its containing context (in BQN, the surrounding set of curly braces `{}`, if any) within the source code. A closure is really an implementation mechanism, but it's often used to refer to a property of lexical scoping that appears when functions defined in a particular block can be accessed after the block finishes execution. For example, they might be returned from a function or assigned to a variable outside of that function's scope. In this case the functions can still access variables in the original scope. I consider this property to be a requirement for a correct lexical scoping implementation, but it's traditionally not a part of APL: implementation might not have lexical scoping (for example, J and I believe A+ use static scoping where functions can't access variables in containing scopes) or might cut off the scope once execution ends, leading to value errors that one wouldn't predict from the rules of lexical scoping. ## Functions in APL -This seems like a good place for a brief and entirely optional discussion of how APL handles functions and why it does it this way. As mentioned above, APL's functions are second class rather than first class. However, it's worth noting that the barriers to making functions first-class objects have been entirely syntactic and conceptual, not technical. In fact, the J language has for a long time had [a bug](http://www.jsoftware.com/pipermail/programming/2013-January/031260.html) that allows an array containing a function to be created: by selecting from the array, the function itself can even be passed through tacit functions as an argument! +This seems like a good place for a brief and entirely optional discussion of how APL handles functions and why it does it this way. As mentioned above, APL's functions are second class rather than first class. But the barriers to making functions first-class objects have been entirely syntactic and conceptual, not technical. In fact, the J language has for a long time had [a bug](http://www.jsoftware.com/pipermail/programming/2013-January/031260.html) that allows an array containing a function to be created: by selecting from the array, the function itself can even be passed through tacit functions as an argument! The primary reason why APL doesn't allow functions to be passed as arguments is probably syntax: in particular, there's no way to say that a function should be used as the left argument to another function, as an expression like `F G x` with functions `F` and `G` and an array `x` will simply be evaluated as two monadic function applications. However, there's no syntactic rule that prevents a function from returning a function, and Dyalog APL for example allows this (so `⍎'+'` returns the function `+`). Dyalog's `⎕OR` is another interesting phenomenon in this context: it creates an array from a function or operator, which can then be used as an element or argument like any array. The mechanism is essentially the same as BQN's first class functions, and in fact `⎕OR`s even share a form of BQN's [syntactic type erasure](../commentary/problems.md#syntactic-type-erasure), as a `⎕OR` of a function passed as an operand magically becomes a function again. But outside of this property, it's cumbersome and slow to convert functions to and from `⎕OR`s, so they don't work very well as a first-class function mechanism. @@ -107,9 +107,9 @@ First, let's look at the basics: a small program that has functions as its argum v0 + ((𝕏 1) - v0) × ⊢ } -We can pass it the exponential function as an argument by giving it the name `Exp` and then referring to it in lowercase (that is, in a subject role). The result is a train that adds 1 to *e*-1 times the argument. +We can pass it the [exponential](arithmetic.md#basic-arithmetic) function as an argument by giving it the name `Exp` and then referring to it in lowercase (that is, in a subject role). The result is a [train](train.md) that adds 1 to *e*-1 times the argument. - Lin ← { v0←𝕏0 ⋄ v0+((𝕏1)-v0)×⊢ } + Lin ← { v0←𝕏0 ⋄ v0+((𝕏1)-v0)×⊢ } # (copy of above) Exp ← ⋆ Lin exp @@ -135,12 +135,12 @@ Note also in this case that we could have used a modifier with a very similar de Its call syntax is simpler as well. In other cases, however, the function version might be preferable, for example when dealing with arrays of functions or many arguments including a function. - _lin ↩ { v0←𝔽0 ⋄ v0+((𝔽1)-v0)×⊢ } + _lin ↩ { v0←𝔽0 ⋄ v0+((𝔽1)-v0)×⊢ } # (copy again) Exp _lin 5 ### Arrays of functions -It's very convenient to put a function in an array, which is fortunate because this is one of the most important uses of functions as subjects. Here's an example of an array of functions with a reduction applied to it, composing them together. +It's very convenient to put a function in an array, which is fortunate because this is one of the most important uses of functions as subjects. Here's an example of an array of functions with a [fold](fold.md) applied to it, composing them together. {𝕎∘𝕏}´ ⋆‿-‿(ט) diff --git a/doc/glossary.md b/doc/glossary.md index d16f5584..9fd9a568 100644 --- a/doc/glossary.md +++ b/doc/glossary.md @@ -23,6 +23,7 @@ A few terms refer to multiple types collectively: * **Modifier**: A 1-modifier or 2-modifier. * **Data type**: Number, character, or array. * **Operation type**: Function, 1-modifier, or 2-modifier. +* **Mutable type**: Operation or namespace. BQN uses standard terminology for particular sets of numbers, with natural numbers starting at 0. * **Boolean**: 0 or 1. @@ -47,7 +48,7 @@ The possible roles are: * **Element**: One of the values contained in an array. * **Axis**: One dimension or direction in an array. * **Rank**: The number of dimensions an array has. -* **Shape**: The number of elements an array has along each dimension. +* [**Shape**](shape.md): The number of elements an array has along each dimension. * **Length**: The number of elements an array has along the first dimension, or 1 if it has rank 0. * [**Depth**](depth.md): The greatest number of times an element can be selected from a value before reaching an atom. * **Fill**: A "prototypical" array element used in certain operations; it's an inferred property of an array. @@ -60,7 +61,7 @@ The possible roles are: * **Frame**: A prefix of an array's shape, used for agreement with the Rank modifier. * **Unit**: An array of rank 0, or an atom. -* **Unit array**: An array of rank 0 other than an atom. +* [**Unit array**](enclose.md#whats-a-unit): An array of rank 0 other than an atom. * **List**: An array of rank 1. * **String**: A list of characters. * **Table**: An array of rank 2. @@ -92,7 +93,7 @@ The possible roles are: * **Token formation** or tokenization: Splitting source code into a sequence of tokens. * **Token**: A name, literal, primitive, or other syntactic element. * **Literal**: A token that indicates a fixed value of a data type. -* **Primitive**: One of several fixed operations defined by the language, denoted by a single-character token. +* [**Primitive**](primitive.md): One of several fixed operations defined by the language, denoted by a single-character token. * **Word**: A sequence of alphabetic or numeric characters. * **Name**: A word that starts with an alphabetic character. Names are compared case-insensitively and ignoring underscores `_`. * **Numeric literal**: A word that starts with a numeric character, indicating a number. diff --git a/doc/group.md b/doc/group.md index dac75506..de8d438e 100644 --- a/doc/group.md +++ b/doc/group.md @@ -2,7 +2,7 @@ # Group -BQN replaces the [Key](https://aplwiki.com/wiki/Key) operator from J or Dyalog APL, and [many forms of partitioning](https://aplwiki.com/wiki/Partition_representations), with a single (ambivalent) Group function `⊔`. This function is somewhat related to the K function `=` of the same name, but results in an array rather than a dictionary. +BQN replaces the Key operator from J or Dyalog APL, and [many forms of partitioning](https://aplwiki.com/wiki/Partition_representations), with a single (ambivalent) Group function `⊔`. This function is somewhat related to the K function `=` of the same name, but results in an array rather than a dictionary. <!--GEN Num ← ·Highlight •Repr @@ -89,7 +89,7 @@ Here, the index 2 appears at indices 0 and 3 while the index 3 appears at index ### Multidimensional grouping -Dyadic Group allows the right argument to be grouped along multiple axes by using a nested left argument. In this case, the left argument must be a list of numeric lists, and the result has rank `≠𝕨` while its elements—as always—have the same rank as `𝕩`. The result shape is `1+⌈´¨𝕨`, while the shape of element `i⊑𝕨⊔𝕩` is `i+´∘=¨𝕨`. If every element of `𝕨` is sorted ascending and contains only non-negative numbers, we have `𝕩≡∾𝕨⊔𝕩`, that is, Join is the inverse of Partition. +Dyadic Group allows the right argument to be grouped along multiple axes by using a nested left argument. In this case, the left argument must be a list of numeric lists, and the result has rank `≠𝕨` while its elements—as always—have the same rank as `𝕩`. The result shape is `1+⌈´¨𝕨`, while the shape of element `i⊑𝕨⊔𝕩` is `i+´∘=¨𝕨`. If every element of `𝕨` is sorted ascending and contains only non-negative numbers, we have `𝕩≡∾𝕨⊔𝕩`, that is, [Join](join.md#join) is the inverse of Partition. Here we split up a rank-2 array into a rank-2 array of rank-2 arrays. Along the first axis we simply separate the first pair and second pair of rows—a partition. Along the second axis we separate odd from even indices. @@ -101,31 +101,31 @@ The monadic case works similarly: Group Indices always satisfies `⊔𝕩 ←→ ## Properties -Group is closely related to the inverse of Indices, `/⁼`. In fact, inverse Indices called on the index argument gives the length of each group: +Group is closely related to the [inverse of Indices](replicate.md#inverse), `/⁼`. In fact, inverse Indices called on the index argument gives the length of each group: ≠¨⊔ 2‿3‿1‿2 /⁼∧ 2‿3‿1‿2 -A related fact is that calling Indices on the result of Group sorts all the indices passed to Group (removing any ¯1s). This is a kind of counting sort. +A related fact is that calling Indices on the result lengths of Group sorts all the indices passed to Group (removing any ¯1s). This is a kind of counting sort. /≠¨⊔ 2‿3‿1‿¯1‿2 -Called dyadically, Group sorts the right argument according to the left and adds some extra structure. If this structure is removed with Join, Group can be thought of as a kind of sorting. +Called dyadically, Group sorts the right argument according to the left and adds some extra structure. If this structure is removed with [Join](join.md#join), Group can be thought of as a kind of sorting. ∾ 2‿3‿1‿¯1‿2 ⊔ "abcde" 2‿3‿1‿¯1‿2 {F←(0≤𝕨)⊸/ ⋄ 𝕨⍋⊸⊏○F𝕩} "abcde" -Group can even be implemented with the same techniques as a bucket sort, which can be branchless and fast. +Group can even be implemented with the same [techniques](../implementation/primitive/sort.md#counting-and-bucket-sort) as a bucket sort, making it branchless and fast. ## Applications -The obvious application of Group is to group some values according to a known or computed property. If this property isn't an integer, it can be turned into one using Classify (monadic `⊐`, identical to `⍷⊸⊐`). Classify numbers the unique values in its argument by first occurrence. +The obvious application of Group is to group some values according to a known or computed property. If this property isn't a natural number, it can be turned into one using [Classify](selfcmp.md#classify) (`⊐`), which numbers the unique values in its argument by first occurrence. ln ← "Phelps"‿"Latynina"‿"Bjørgen"‿"Andrianov"‿"Bjørndalen" co ← "US" ‿"SU" ‿"NO" ‿"SU" ‿"NO" ≍˘ co ⊐⊸⊔ ln -If we would like a particular index to key correspondence, we can use a fixed left argument to Index Of. +If we would like a particular index to key correspondence, we can use a fixed left argument to [Index Of](search.md#index-of). countries ← "IT"‿"JP"‿"NO"‿"SU"‿"US" countries ≍˘ co countries⊸⊐⊸⊔ ln @@ -137,7 +137,7 @@ However, this solution will fail if there are trailing keys with no values. To f ### Partitioning -In examples we have been using a list of strings stranded together. Often it's more convenient to write the string with spaces, and split it up as part of the code. In this case, the index corresponding to each word (that is, each letter in the word) is the number of spaces before it. We can get this number of spaces from a prefix sum on the boolean list which is 1 at each space. +In examples we have been using a list of strings stranded together. Often it's more convenient to write the string with spaces, and split it up as part of the code. In this case, the index corresponding to each word (that is, each letter in the word) is the number of spaces before it. We can get this number of spaces from a Plus-[Scan](scan.md) on the boolean list which is 1 at each space. ' '(+`∘=⊔⊢)"BQN uses notation as a tool of thought" @@ -151,7 +151,7 @@ In other cases, we might want to split on spaces, so that words are separated by ' '((⊢-˜¬×+`)∘=⊔⊢)" string with spaces " -Trailing spaces are ignored because Group with equal-length arguments never produces trailing empty groups—to intentionally include them you'd replace `=` with `(=∾0˙)`. But in string processing we probably want to avoid empty words anywhere. To make this happen, we should increase the word index only once per group of spaces. We can do this by taking the prefix sum of a list that is 1 only for a space with no space before it. To make such a list, we can use the [Shift Before](shift.md) function, giving a list of previous elements. To treat the first element as if it's before a space (so that leading spaces have no effect rather than creating an initial empty group), we shift in a 1. +Trailing spaces are ignored because Group with equal-length arguments never produces trailing empty groups—to intentionally include them you'd replace `=` with `(=∾0˙)`. But in string processing we probably want to avoid empty words anywhere. To make this happen, we should increase the word index only once per group of spaces. We can do this by applying Plus Scan to a list that is 1 only for a space with no space before it. This list is produced using [Shift Before](shift.md) to get a list of previous elements. To treat the first element as though it's before a space (so that leading spaces have no effect rather than creating an initial empty group), we shift in a 1. (⊢≍1⊸»<⊢) ' '=" string with spaces " # All, then filtered, spaces ≍⟜(⊢-˜¬×·+`1⊸»<⊢)' '=" string with spaces " # More processing diff --git a/doc/identity.md b/doc/identity.md index b9cfd395..a9916bcb 100644 --- a/doc/identity.md +++ b/doc/identity.md @@ -18,11 +18,11 @@ Of course, it's easy to write block functions `{𝕩}` and `{𝕨}` that return ## Filling arrays -What's the easiest way to create a matrix with 0 on the first row, 1 on the second, and so on? Probably this one, with [table](map.md): +What's the easiest way to create a matrix with 0 on the first row, 1 on the second, and so on? Probably this one, with [table](map.md#table): (↕4) ⊣⌜ ↕5 -The right argument `↕5` could be any length-5 list, as its values aren't used. With `5⥊0`, we could use `+⌜` instead, but requiring a specific argument seems artificial. A similar pattern applies with Each: +The right argument `↕5` could be any length-5 list, as its values aren't used. With `5⥊0`, we could use `+⌜` instead, but requiring a specific argument seems artificial. A similar pattern applies with [Each](map.md#each): (⌽↕4) ⊣¨ ↕4‿5 diff --git a/doc/indices.md b/doc/indices.md index 105b9ee7..62122175 100644 --- a/doc/indices.md +++ b/doc/indices.md @@ -2,9 +2,9 @@ # Indices -One-dimensional arrays such as K lists or Python arrays have only one kind of index, a single number that refers to an element. For multidimensional arrays using the [leading axis theory](leading.md), there are several types of indexing that can be useful. Historically, nested APL designs have equivocated between these, which I believe can lead to subtle errors when programming. BQN focuses on single-number (atomic) indices, which can refer to list elements or array major cells (or more generally indexing along any particular axis). When using atomic indices to select elements, the indexed array has to be a list. In contrast, elements of any array can be indicated by list indices with length equal to that array's rank. Only two BQN primitives use these list indices: Range (`↕`), which returns an array of them if given a list argument, and Pick (`⊑`), where the depth-1 components of an array left argument are list indices. +One-dimensional arrays such as K lists or Python arrays have only one kind of index, a single number that refers to an element. For multidimensional arrays using the [leading axis theory](leading.md), there are several types of indexing that can be useful. Historically, nested APL designs have equivocated between these, which I believe can lead to subtle errors when programming. BQN focuses on single-number (atomic) indices, which can refer to list elements or array major cells (or more generally indexing along any particular axis). When using atomic indices to select elements, the indexed array has to be a list. In contrast, elements of any array can be indicated by list indices with length equal to that array's rank. Only two BQN primitives use these list indices: [Range](range.md) (`↕`), which returns an array of them if given a list argument, and [Pick](pick.md) (`⊑`), where the depth-1 components of an array left argument are list indices. -The following functions take or return indices. Except where marked, the indices are in the result; this is by far the most common type of index use. `⊔` is given two rows as it falls into both cases. Note that in the result case, there is usually no possibility for the programmer to select the format of indices. Instead, the language should be carefully designed to make sure that the kind of index returned is as useful as possible. +The following functions take or return indices. Except where marked, the indices are in the result; this is by far the most common type of index use. [Group](group.md) (`⊔`) is given two rows as it falls into both cases. Note that in the result case, there is usually no possibility for the programmer to select the format of indices. Instead, the language should be carefully designed to make sure that the kind of index returned is as useful as possible. | Monad | Dyad | Where | How |-------|------|---------|-------------------------- @@ -20,23 +20,23 @@ The following functions take or return indices. Except where marked, the indices | | `⊏` | `𝕨` | Major cell or along-axis number | `⍉` | | | Axis number -Dyadic Transpose (`⍉`) uses indices into the right argument axes in its left argument, but since array shape is 1-dimensional, there is only one sensible choice for this, a single number. +In Dyadic [Transpose](transpose.md#dyadic-transpose) (`⍉`), `𝕨` is made up of indices into axes of `𝕩`. Since array shape is 1-dimensional, there is only one sensible choice for these elements, a single number each. ## Element indices In general, the index of an element of an array is a list whose length matches the array rank. It is also possible to use a number for an index into a list, as the list index is a singleton, but this must be kept consistent with the rest of the language. NARS-family APLs make the Index Generator (`↕` in BQN) return a numeric list when the argument has length 1 but a nested array otherwise. This means that the depth of the result depends on the shape of the argument, inverting the typical hierarchy. BQN shouldn't have such an inconsistency. -Functions `↕`, `/`, `⊔`, and `⊑` naturally deal with element indices. Each of these can be defined to use list indices. However, this usually rules out the possibility of using atomic indices, which makes these functions harder to use both with generic array manipulation and with the major cell indices discussed in the next section. For this reason BQN restricts `⊔` and monadic `/` to use atomic indices, which comes with the requirement that the arguments to monadic `/` and `⊔`, and the result of monadic `⊔`, must be lists. For dyadic `⊔` the depth-1 elements of the left argument are lists of indices along axes of the result; see [the documentation](group.md#multidimensional-grouping). The restriction that comes from using single-number indices is that all axes must be treated independently, so that for example it isn't possible to group elements along diagonals without preprocessing. However, this restriction also keeps Group from having to use an ordering on list indices. +Functions [Range](range.md) (`↕`), [Indices](replicate.md) (`/`), [Group](group.md) (`⊔`), and [Pick](pick.md) (`⊑`) naturally deal with element indices. Each of these can be defined to use list indices. However, this usually rules out the possibility of using atomic indices, which makes these functions harder to use both with generic array manipulation and with the major cell indices discussed in the next section. For this reason BQN restricts `⊔` and `/` to use atomic indices, which comes with the requirement that the arguments to Group and Indices, and the result of Group Indices, must be lists. For dyadic Group the depth-1 elements of `𝕨` are arrays of indices along axes of the result ([multi-axis documentation](group.md#multidimensional-grouping)). This means each axis of `𝕩` can only be related to one axis of the result. -Unlike `/` and `⊔`, `↕` and `⊑` do use list element indices. For `↕` this is because the output format can be controlled by the argument format: if passed a single number, the result uses atomic indices (so it's a numeric list); if passed a list, it uses list indices and the result has depth 2 (the result depth is always one greater than the argument depth). For `⊑`, list indices are chosen because `⊏` handles atomic indices well already. When selecting multiple elements from a list, they would typically have to be placed in an array, which is equivalent to `⊏` with a numeric list left argument. An atomic left argument to `⊑` is converted to a list, so it can be used to select a single element if only one is wanted. To select multiple elements, `⊑` uses each depth-1 array in the left argument as an index and replaces it with that element from the right argument. Because this uses elements as elements (not cells), it is impossible to have conformability errors where elements do not fit together. Ill-formed index errors are of course still possible, and the requirements on indices are quite strict. They must exactly match the structure of the right argument's shape, with no units or higher-rank arrays allowed. Atoms also cannot be used in this context, as it would create ambiguity: is a one-element list an index, or does it contain an index? +Unlike `/` and `⊔`, `↕` and `⊑` do use list element indices. For `↕` this is because the output format can be controlled by the argument format: if passed a single number, the result uses atomic indices (so it's a numeric list); if passed a list, it uses list indices and the result has depth 2 (the result depth is always one greater than the argument depth). For `⊑`, list indices are chosen because [Select](select.md) (`⊏`) handles atomic indices well already. When selecting multiple elements from a list, they would typically have to be placed in an array, which is equivalent to `⊏` with a numeric list `𝕨`. An atom `𝕨` in Pick is converted to a list, so it can be used to select a single element if only one is wanted. To select multiple elements, `⊑` uses each depth-1 array in `𝕨` as an index and replaces it with that element from the right argument. Because this uses elements as elements (not cells), it is impossible to have conformability errors where elements do not fit together (invalid index errors are of course still possible). Atoms also cannot be used in this context, as it would create ambiguity: is a one-element list an index, or does it contain an index? ## Major cell indices -One of the successes of the [leading axis model](https://aplwiki.com/wiki/Leading_axis_theory) is to introduce a kind of index for multidimensional arrays that is easier to work with than list indices. The model introduces [cells](https://aplwiki.com/wiki/Cell), where a cell index is a list of any length up to the containing array's rank. General cell indices are discussed in the next section; first we introduce a special case, indices into major cells or ¯1-cells. These cells naturally form a list, so the index of a major cell is a single number. These indices can also be considered indices along the first axis, since an index along any axis is a single number. +One of the successes of the [leading axis model](https://aplwiki.com/wiki/Leading_axis_theory) is to introduce a kind of index for multidimensional arrays that is easier to work with than list indices. The model introduces [cells](https://aplwiki.com/wiki/Cell), where a cell index is a list of any length up to the containing array's rank. General cell indices are discussed in the next section; first we introduce a special case, indices into major cells or ¯1-cells. These cells naturally form a list, so the index of a major cell is a single number. Such an index can also be considered to select along the first axis, since an index along any axis is a single number. -Ordering-based functions `⍋`, `⍒`, `⊐`, and `⊒` only really make sense with major cell indices: while it's possible to order other indices as ravel indices, this probably isn't useful from a programming standpoint. Note that `⊐` only uses the ordering in an incidental way, because it's defined to return the *first* index where a right argument cell is found. A mathematician would be more interested in a "pre-image" function that returns the set of all indices where a particular value appears. However, programming usefulness and consistency with the other search functions makes searching for the first index a reasonable choice. +[Ordering](order.md) functions `⍋⍒` and [search](search.md)/[self-comparison](selfcmp.md) functions `⊐⊒` that depend on cell ordering only really make sense with major cell indices: while other indices have an ordering, it's not very natural. Note that `⊐` only uses the ordering in an incidental way, because it's defined to return the *first* index where a cell in `𝕩` is found. A mathematician would be more interested in a "pre-image" function that returns the set of all indices where a particular value appears. However, programming usefulness and consistency with the other search functions makes searching for the first index a reasonable choice. -Only one other function—but an important one!—deals with cells rather than elements: `⊏`, cell selection. Like dyadic `↑↓↕⌽⍉` (depth 0) and `/⊔` (depth 1), Select allows either a simple first-axis case where the left argument has depth 1 or less (a depth-0 argument is automatically enclosed), and a multi-axis case where it is a list of depth-1 elements. In each case the depth-1 arrays index along a single axis. +Only one other function—but an important one!—deals with cells rather than elements: [Select](select.md) (`⊏`). Select [allows](leading.md#multiple-axes) either a simple first-axis case where `𝕨` has depth 1 or less (a depth-0 argument is automatically enclosed), and a multi-axis case where it is a list of depth-1 elements. In each case the depth-1 arrays index along a single axis. ## General cell indices diff --git a/doc/join.md b/doc/join.md index 50a817e7..f244db59 100644 --- a/doc/join.md +++ b/doc/join.md @@ -2,7 +2,7 @@ # Join and Join To -The glyph `∾` combines arrays along an existing axis, a concept that other languages might call "concatenation" or "catenation" but BQN names "Join". The one-argument form Join and two-argument form Join To are parallel to the [functions that combine arrays along a new axis](couple.md), Merge (`>`) and Couple (`≍`). +The glyph `∾` combines arrays along an existing axis, a concept that other languages might call "concatenation" or "catenation" but BQN names "Join". The one-argument form Join and two-argument form Join To are parallel to [the functions](couple.md) that combine arrays along a new axis, Merge (`>`) and Couple (`≍`). ## Join To @@ -18,7 +18,7 @@ If the arguments have the same rank, then they are combined along the first axis For this definition to work, major cells of `𝕨` and `𝕩` have to have the same shape. That means that `𝕨≡○(1↓≢)𝕩`, and the shape of the result is the sum of the lengths of `𝕨` and `𝕩` followed by their shared major cell shape: to use a self-referential definition, the final shape is given by `+○≠ ∾ ⊣⁼○(1↓≢)` for arguments of equal rank. - a ∾ 2‿5⥊b + a ∾ 2‿5⥊b # Shapes don't fit Join To will also allow arguments with ranks that are one apart. In this case, the smaller-rank argument is treated as a major cell in its entirety. If for example `𝕨<○=𝕩`, then we must have `(≢𝕨)≡1↓≢𝕩`, and the result shape is `1⊸+⌾⊑≢𝕩`. diff --git a/doc/leading.md b/doc/leading.md index 6a0020aa..467890df 100644 --- a/doc/leading.md +++ b/doc/leading.md @@ -8,7 +8,7 @@ Several primitive functions manipulate the right argument, or sometimes both arg ### Manipulating cells -Most non-arithmetic monadic functions work only on the first axis of the argument—that is, they treat it as a list of its major cells. The function Length (`≠`) counts these major cells, while Prefixes (`↑`), Suffixes (`↓`), Reverse (`⌽`), and First Cell (`⊏`) move them around. The Insert (`˝`) and Scan (`` ` ``) modifiers also yield functions that work along the first axis; in contrast, Reduce (`´`) requires its argument to be a list, as it works on elements. +Most non-arithmetic monadic functions work only on the first axis of the argument—that is, they treat it as a list of its major cells. The function [Length](shape.md) (`≠`) counts these major cells, while [Prefixes](prefixes.md) (`↑`), Suffixes (`↓`), [Reverse](reverse.md) (`⌽`), and [First Cell](select.md) (`⊏`) move them around. The [Insert](fold.md#insert) (`˝`) and [Scan](scan.md) (`` ` ``) modifiers also yield functions that work along the first axis; in contrast, [Fold](fold.md) (`´`) requires `𝕩` to be a list, as it works on elements. ⊢ a ← 3‿2 ⥊ "abcdef" # An array with three major cells ⊏ a # Get the first major cell @@ -21,14 +21,14 @@ To use these functions on another axis, use the Rank (`⎉`) or Cells (`˘`) mod ⌽˘ a # Swap the columns ⊣`˘ a # Replicate along rows -In these three cases above, the results are the same as you would get from transposing before and after (this has no effect on the result of `⊏˘`, since it has rank 1). But in the following cases, the structure is quite different: `↑a` is a list of matrices while `↑˘a` is a matrix of lists. This is because the functions `⊏`, `⌽`, and `` ⊣` `` leave the trailing axis structure intact (`⊏` removes one axis); taking into account that Rank or Cells always preserves the leading or frame axes, all axes are preserved (except the one removed by `⊏`). In contrast, Prefixes or Suffixes pushes some axes down in depth, and the number of axes that are pushed down in this way changes with the rank of application. More precisely, these functions move axes after the first from the argument itself to result elements, and create two axes from the first axis, with one of them forming the sole result axis and the other joining the rest as an element axis. +In these three cases above, the results are the same as you would get from [transposing](transpose.md) before and after (this has no effect on the result of `⊏˘`, since it has rank 1). But in the following cases, the structure is quite different: `↑a` is a list of matrices while `↑˘a` is a matrix of lists. This is because the functions `⊏`, `⌽`, and `` ⊣` `` leave the trailing axis structure intact (`⊏` removes one axis); taking into account that Rank or Cells always preserves the leading or frame axes, all axes are preserved (except the one removed by `⊏`). In contrast, Prefixes or Suffixes will push some axes down in depth, and the number of axes that are pushed down in this way changes with the rank of application. More precisely, these functions move axes after the first from the argument itself to result elements, and create two axes from the first axis, with one of them forming the sole result axis and the other joining the rest as an element axis. ↑ a # Prefixes of a: ranks 1|2 ↑˘ a # Prefixes of rows: ranks 2|1 ∾˝ a # Join the cells ∾˝˘ a # Join-insert is a no-op on lists -[Solo](couple.md) (`≍`), something of a maverick, manages to act on *zero* leading axes of its argument by creating the first axis of the *result* instead. Because it doesn't need any axis to work, it can go in front of either axis but also past the last one by working with rank 0, a case where most array functions would give an error. +[Solo](couple.md) (`≍`), something of a maverick, manages to act on *zero* leading axes of `𝕩` by creating the first axis of the *result* instead. Because it doesn't need any axis to work, it can go in front of either axis but also past the last one by working with rank 0, a case where most array functions would give an error. ≢ ≍ a # Solo adds a length-1 axis a ≡ ⊏ ≍ a # First Cell undoes this @@ -37,7 +37,7 @@ In these three cases above, the results are the same as you would get from trans ### Comparing cells -The functions in the last section manipulate cells in the same way regardless of what data they contain. Other functions compare cells to each other, either testing whether they match or how they are ordered relative to one another. The two Grade functions `⍋⍒`, and the self-comparison functions Classify (`⊐`), Mark Firsts (`∊`), and Occurrence Count (`⊒`), each give a list result, with one number for each cell. We can see below that Occurrence Count returns the same results even as we make the argument cells more complicated, because the changes made preserve the matching of cells. +The functions in the last section manipulate cells in the same way regardless of what data they contain. Other functions compare cells to each other, either testing whether they match or how they are ordered relative to one another. The two [Grade](order.md) functions `⍋⍒`, and the [self-comparison](selfcmp.md) functions Classify (`⊐`), Mark Firsts (`∊`), and Occurrence Count (`⊒`), each give a list result, with one number for each cell. We can see below that Occurrence Count returns the same results even as we make the argument cells more complicated, because the changes made preserve the matching of cells. s ← "abracadabra" ⊒ s @@ -51,30 +51,30 @@ The two Sort functions `∧∨` and Deduplicate (`⍷`) move cells around based ### Other monadic functions -Not all functions work on the first axis in a straightforward manner. [Transpose](transpose.md) `⍉` moves the first axis to the end, so while it focuses on the first one, it shifts every axis of the argument. [Join](join.md) `∾` also works on every axis of its argument, and applies to the leading axes of the argument's *elements* instead: these leading inner axes are matched up with the outer axes, and trailing inner axes are allowed but the elements must have rank at least as high as the argument array. +Not all functions work on the first axis in a straightforward manner. [Transpose](transpose.md) `⍉` moves the first axis to the end, so while it focuses on the first one, it shifts every axis of `𝕩`. [Join](join.md) `∾` also works on every axis of its argument, and applies to the leading axes of `𝕩`'s *elements* instead: these leading inner axes are matched up with the outer axes, and trailing inner axes are allowed but the elements must have rank at least as high as the argument array. -The other two monadic functions that work on high-rank arguments are Deshape (`⥊`) and First (`⊑`). These treat the argument as one long list, ordered by its element indices. This ordering privileges leading axes (in fact, it is the reason for the choice of leading axes in the leading axis convention), but these functions can't really be said to work on leading axes: they apply to all axes. +The other two monadic functions that work on high-rank arguments are [Deshape](reshape.md#deshape) (`⥊`) and [First](pick.md#first) (`⊑`). These treat `𝕩` as one long list, ordered by its element indices. This ordering privileges leading axes (in fact, it is the reason for the choice of leading axes in the leading axis convention), but these functions can't really be said to work on leading axes: they apply to all axes. -The Each (`¨`) and Table (`⌜`) modifiers return functions which are the same in the monadic case. These functions simply go through all elements of the argument array without regard for its multi-dimensional structure (the operand is applied to elements in index order, matching Deshape; this matters if it has side effects). Similarly, monadic arithmetic functions do not have any sort of leading axis dependence. +The [Each](map.md) (`¨`) and [Table](map.md#table) (`⌜`) modifiers return functions which are the same in the monadic case. These functions simply go through all elements of the argument array without regard for its multi-dimensional structure (the operand is applied to elements in index order, matching Deshape; this matters if it has side effects). Similarly, monadic arithmetic functions do not have any sort of leading axis dependence. ## Dyadic functions -For dyadic functions the pattern of working on only one argument axis is not so common. Only two functions can be said to follow it roughly: Join to (`∾`) combines two arrays along one axis, using the first axis of both arguments if they have the same rank and of the higher-rank argument if they differ by one. [Couple](couple.md) (`≍`), like Solo, does not manipulate the argument axes but adds a result axis. There are also some functions that can't be limited to leading axes: [Reshape](reshape.md) (`⥊`) treats the argument as one long list, and Pick (`⊑`) requires each index to be as long as the right argument's rank, because it selects elements and not cells from the right argument. +For dyadic functions the pattern of working on only one argument axis is not so common. Only two functions can be said to follow it roughly: [Join to](join.md) (`∾`) combines two arrays along one axis, using the first axis of both arguments if they have the same rank and of the higher-rank argument if they differ by one. [Couple](couple.md) (`≍`), like Solo, does not manipulate the argument axes but adds a result axis. There are also some functions that can't be limited to leading axes: [Reshape](reshape.md) (`⥊`) treats `𝕩` as one long list, and [Pick](pick.md) (`⊑`) requires each index to be as long as `𝕩`'s rank, because it selects elements and not cells from `𝕩`. ### Multiple axes -Instead of always working on a single axis, many dyadic functions work on one axis by default, but also allow a left argument with multiple elements corresponding to leading axes of the right argument. To decide which of the two possibilities applies, these functions test the left argument depth, a convention that is discussed in the [depth](depth.md#testing-depth-for-multiple-axis-primitives) documentation. A left argument that applies to one axis has a particular depth; the argument can also be a list of such arguments. +Instead of always working on a single axis, many dyadic functions work on one axis by default, but also allow a left argument with multiple elements corresponding to leading axes of `𝕩`. To decide which of the two possibilities applies, these functions test the depth of `𝕨`, a convention that is discussed in the [depth](depth.md#testing-depth-for-multiple-axis-primitives) documentation. A left argument that applies to one axis has a particular depth; `𝕨` can also be a list of such arguments. | Single-axis depth | Functions |-------------------|---------- | 0 | `↑↓↕⌽⍉` | 1 | `/⊏⊔` -Functions such as Take and Drop use a single number per axis. When the left argument is a list of numbers, they apply to initial axes. Observing the operation of Rotate on the result of Range is instructive: +Functions such as Take and Drop use a single number per axis. When `𝕨` is a list of numbers, they apply to initial axes. Observing the operation of [Rotate](reverse.md#rotate) on the result of [Range](range.md) is instructive: 2‿1 ⌽ ↕3‿5 -The array is shifted once to the left and twice upward, so that the first index (by ravel order) is now `⊑2‿1⌽↕3‿5 ←→ 2‿1`. To see how values are matched to leading axes, we can look at how Drop changes the shape of its argument: +The array is shifted once to the left and twice upward, so that the first index (by ravel order) is now `⊑2‿1⌽↕3‿5 ←→ 2‿1`. To see how values are matched to leading axes, we can look at how [Drop](take.md) changes the shape of its argument: ≢ 3‿2 ↓ 7‿7‿7‿7⥊"abc" @@ -82,7 +82,7 @@ Functions with single-axis depth 1 tend to be more complicated; see for example ### Leading axis agreement -Arithmetic functions, and the Each (`¨`) and Depth (`⚇`) modifiers, use leading axis agreement to match their arguments together. All axes of the lower-rank argument are matched with the leading axes of the higher-rank one, and axes matched together must have the same length. After pairing axes in this way, a single element of the lower-rank argument might correspond to any number of elements of the higher-rank one. It's reused for each of those corresponding elements. +[Arithmetic](arithmetic.md) functions, and the [Each](map.md#each) (`¨`) and [Depth](depth.md#the-depth-modifier) (`⚇`) modifiers, use leading axis agreement to match their arguments together. All axes of the lower-rank argument are matched with the leading axes of the higher-rank one, and axes matched together must have the same length. After pairing axes in this way, a single element of the lower-rank argument might correspond to any number of elements of the higher-rank one. It's reused for each of those corresponding elements. ⊢ x ← 3‿2‿4 ⥊ ↕60 # A rank-3 array 100‿0‿200 + x # 0-cells paired with 2-cells @@ -96,11 +96,11 @@ With leading axis agreement, there are `k+1` shapes for arrays that can be added ### Search functions -The search functions Bins (`⍋⍒`), Index of (`⊐`), Progressive Index of (`⊒`), and Member of (`∊`) look through cells of one argument to find cells of the other. Find (`⍷`) also does a search, but a slightly different one: it tries to find *slices* of cells of its right argument that match the left argument. +The [search functions](search.md) Bins (`⍋⍒`), Index of (`⊐`), Progressive Index of (`⊒`), and Member of (`∊`) look through cells of one argument to find cells of the other. Find (`⍷`) also does a search, but a slightly different one: it tries to find *slices* of cells of `𝕩` that match `𝕨`. | Searching through | Look for | Functions |-------------------|----------|---------- | `𝕨` | `𝕩` | `⍋⍒⊐⊒` | `𝕩` | `𝕨` | `∊⍷` -For all of these functions but Find, the argument to search through is treated as a list of its major cells. It is the rank of these major cells—let's call this rank `c`—that determines how the other argument is treated. That argument must have rank at least `c`, and it is treated as an array of `c`-cells. For example, if the left argument to `⍋` is a matrix, then each 1-cell or row of the right argument is treated independently, and each one yields one number in the result: a 0-cell. The result rank of `⍋` is always `𝕨¬○=𝕩`. +For all of these functions but Find, the argument to search through is treated as a list of its major cells. It is the rank of these major cells—let's call this rank `c`—that determines how the other argument is treated. That argument must have rank at least `c`, and it is treated as an array of `c`-cells. For example, if the left argument to `⍋` is a matrix, then each 1-cell or row of `𝕩` is treated independently, and each one yields one number in the result: a 0-cell. The result rank of `⍋` is always `𝕨¬○=𝕩`. |