From 15908ba604c2a27b84a30d7ce91ceb7a8c1064aa Mon Sep 17 00:00:00 2001 From: Marshall Lochbaum Date: Fri, 17 Jul 2020 21:25:22 -0400 Subject: Mirror repository tree in docs/ and add html spec documents --- docs/context.html | 138 ------------------------------- docs/depth.html | 135 ------------------------------- docs/doc/context.html | 138 +++++++++++++++++++++++++++++++ docs/doc/depth.html | 135 +++++++++++++++++++++++++++++++ docs/doc/fromDyalog.html | 205 +++++++++++++++++++++++++++++++++++++++++++++++ docs/doc/functional.html | 74 +++++++++++++++++ docs/doc/group.html | 152 +++++++++++++++++++++++++++++++++++ docs/doc/indices.html | 100 +++++++++++++++++++++++ docs/doc/join.html | 38 +++++++++ docs/doc/logic.html | 42 ++++++++++ docs/doc/transpose.html | 88 ++++++++++++++++++++ docs/doc/windows.html | 90 +++++++++++++++++++++ docs/fromDyalog.html | 205 ----------------------------------------------- docs/functional.html | 74 ----------------- docs/group.html | 152 ----------------------------------- docs/indices.html | 100 ----------------------- docs/join.html | 38 --------- docs/logic.html | 42 ---------- docs/running.html | 20 +++++ docs/spec/README.html | 14 ++++ docs/spec/evaluate.html | 94 ++++++++++++++++++++++ docs/spec/grammar.html | 138 +++++++++++++++++++++++++++++++ docs/spec/literal.html | 14 ++++ docs/spec/token.html | 40 +++++++++ docs/spec/types.html | 20 +++++ docs/transpose.html | 88 -------------------- docs/windows.html | 90 --------------------- 27 files changed, 1402 insertions(+), 1062 deletions(-) delete mode 100644 docs/context.html delete mode 100644 docs/depth.html create mode 100644 docs/doc/context.html create mode 100644 docs/doc/depth.html create mode 100644 docs/doc/fromDyalog.html create mode 100644 docs/doc/functional.html create mode 100644 docs/doc/group.html create mode 100644 docs/doc/indices.html create mode 100644 docs/doc/join.html create mode 100644 docs/doc/logic.html create mode 100644 docs/doc/transpose.html create mode 100644 docs/doc/windows.html delete mode 100644 docs/fromDyalog.html delete mode 100644 docs/functional.html delete mode 100644 docs/group.html delete mode 100644 docs/indices.html delete mode 100644 docs/join.html delete mode 100644 docs/logic.html create mode 100644 docs/running.html create mode 100644 docs/spec/README.html create mode 100644 docs/spec/evaluate.html create mode 100644 docs/spec/grammar.html create mode 100644 docs/spec/literal.html create mode 100644 docs/spec/token.html create mode 100644 docs/spec/types.html delete mode 100644 docs/transpose.html delete mode 100644 docs/windows.html (limited to 'docs') diff --git a/docs/context.html b/docs/context.html deleted file mode 100644 index 201be8ab..00000000 --- a/docs/context.html +++ /dev/null @@ -1,138 +0,0 @@ - -

BQN's context-free grammar

-

APL has a problem. To illustrate, let's look at an APL expression:

-
a b c d e
-
-

It is impossible to say anything about this sentence! Is c a dyadic operator being applied to b and d, or are b and d two dyadic functions being applied to arrays? In contrast, expressions in C-like or Lisp-like languages show their structure of application:

-
b(a, d(c)(e))
-(b a ((d c) e))
-
-

In each case, some values are used as inputs to functions while others are the functions being applied. The result of a function can be used either as an input or as a function again. These expressions correspond to the APL expression where a and e are arrays, b and c are functions, and d is a monadic operator. However, these syntactic classes have to be known to see what the APL expression is doing—they are a form of context that is required for a reader to know the grammatical structure of the expression. In a context-free grammar like that of simple C or Lisp expressions, a value's grammatical role is part of the expression itself, indicated with parentheses: they come after the function in C and before it in Lisp. Of course, a consequence of using parentheses in this way is having a lot of parentheses. BQN uses a different method to annotate grammatical role:

-
a B C _d e
-
-

Here, the lowercase spelling indicates that a and e are to be treated as values ("arrays" in APL) while the uppercase spelling of variables B and C are used as functions and _d is a modifier ("monadic operator"). Like parentheses for function application, the spelling is not inherent to the variable values used, but instead indicates their grammatical role in this particular expression. A variable has no inherent spelling and can be used in any role, so the names a, A, _a, and _a_ all refer to exact same variable, but in different roles; typically we use the lowercase name to refer to the variable in isolation. While we still don't know anything about what values a, b, c, and so on have, we know how they interact in the line of code above.

-

Is grammatical context really a problem?

-

Yes, in the sense of problems with BQN. A grammar that uses context is harder for humans to read and machines to execute. A particular difficulty is that parts of an expression you don't yet understand can interfere with parts you do, making it difficult to work through an unknown codebase.

-

One difficulty beginners to APL will encounter is that code in APL at first appears like a string of undifferentiated symbols. For example, a tacit Unique Mask implementation ⍳⍨=⍳∘≢ consists of six largely unfamiliar characters with little to distinguish them (in fact, the one obvious bit of structure, the repeated ⍳, is misleading as it means different things in each case!). Simply placing parentheses into the expression, like (⍳⍨)=(⍳∘≢), can be a great help to a beginner, and part of learning APL is to naturally see where the parentheses should go. The equivalent BQN expression, ⊐˜=↕∘≠, will likely appear equally intimidating at first, but the path to learning which things apply to which is much shorter: rather than learning the entire list of APL primitives, a beginner just needs to know that superscript characters like ˜ are modifiers and characters like ∘ with unbroken circles are compositions before beginning to learn the BQN grammar that will explain how to tie the various parts together.

-

This sounds like a distant concern to a master of APL or a computer that has no difficulty memorizing a few dozen glyphs. Quite the opposite: the same concern applies to variables whenever you begin work with an unfamiliar codebase! Many APL programmers even enforce variable name conventions to ensure they know the class of a variable. By having such a system built in, BQN keeps you from having to rely on programmers following a style guide, and also allows greater flexibility, including functional programming, as we'll see later.

-

Shouldn't a codebase define all the variables it uses, so we can see their class from the definition? Not always: consider that in a language with libraries, code might be imported from dependencies. Many APLs also have some dynamic features that can allow a variable to have more than one class, such as the ⍺←⊢ pattern in a dfn that makes ⍺ an array in the dyadic case but a function in the monadic case. Regardless, searching for a definition somewhere in the code is certainly a lot more work than knowing the class right away! One final difficulty is that even one unknown can delay understanding of an entire expression. Suppose in A B c, B is a function and c is an array, and both values are known to be constant. If A is known to be a function (even if its value is not yet known), its right argument B c can be evaluated ahead of time. But if A's type isn't known, it's impossible to know if this optimization is worth it, because if it is an array, B will instead be called dyadically.

-

BQN's spelling system

-

BQN's expression grammar is a simplified version of the typical APL, removing some oddities like niladic functions and the two-glyph Outer Product operator. Every value can be used in any of four syntactic roles:

- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
BQNAPLJ
ValueArrayNoun
FunctionFunctionVerb
ModifierMonadic operatorAdverb
CompositionDyadic operatorConjunction
-

Unlike variables, BQN primitives have only one spelling, and a fixed role (but their values can be used in a different role by storing them in variables). Superscript glyphs ˜¨˘⁼⌜´` are used for modifiers, and glyphs ∘○⊸⟜⌾⊘◶⚇⎉⍟ with an unbroken circle are compositions. Other primitives are functions. String and numeric literals are values.

-

BQN's variables use another system, where the spelling indicates how the variable's value is used. A variable spelled with a lowercase first letter, like var, is a value. Spelled with an uppercase first letter, like Var, it is a function. Underscores are placed where operands apply to indicate a modifier _var or composition _var_. Other than the first letter or underscore, variables are case-insensitive.

-

The associations between spelling and syntactic role are considered part of BQN's token formation rules.

-

One rule for typing is also best considered to be a pre-parsing rule like the spelling system: the role of a brace construct {} with no header is determined by which special arguments it uses: it's a value if there are none, but a 𝕨 or 𝕩 makes it at least a function, an 𝔽 makes it a modifier or composition, and a 𝔾 always makes it a composition.

-

BQN's grammar

-

A formal treatment is included in the spec. BQN's grammar—the ways syntactic roles interact—follows the original APL model (plus trains) closely, with allowances for new features like list notation. In order to keep BQN's syntax context-free, the syntactic role of any expression must be known from its contents, just like tokens.

-

Here is a table of the APL-derived operator and function application rules:

- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
leftmainrightoutputname
FxValueMonadic function
wFxValueDyadic function
FGFunction2-train
F*GHFunction3-train
F*_mFunctionModifier
F*_c_G*FunctionComposition
_c_G*ModifierPartial application
F*_c_ModifierPartial application
-

A function with an asterisk indicates that a value can also be used: in these positions there is no difference between function and value spellings. Operator applications bind more tightly than functions, and associate left-to-right while functions associate right-to-left.

-

BQN lists can be written with angle brackets ⟨elt0,elt1,…⟩ or ligatures elt0‿elt1‿…. In either case the elements can have any type, and the result is a value.

-

The statements in a brace block, function, or operator can also be any role, including the return value at the end. These roles have no effect: outside of braces, a function always returns an array, a modifier always returns a function, and so on, regardless of how these objects were defined.

-

Mixing roles

-

BQN's basic types align closely with its syntactic roles: functions, modifiers, and compositions are all basic types, while values are split into numbers, characters, and arrays. This is no accident, and usually values will be used in roles that match their underlying type. However, the ability to use a role that doesn't match the type is very useful.

-

Any type can be passed as an argument to a function, or as an operand, by treating it as a value. This means that BQN fully supports Lisp-style functional programming, where functions can be used as values.

-

It can also be useful to treat a value type as a function, in which case it applies as a constant function. This rule is useful with most built-in operators. For example, F⎉1 uses a constant for the rank even though in general a function can be given, and a⌾(b⊸/) inserts the values in a into the positions selected by b, ignoring the old values rather than applying a function to them.

-

Other mixes of roles are generally not useful. While a combination such as treating a function as a modifier is allowed, attempting to apply it to an operand will fail. Only a modifier can be applied as a modifier and only a composition can be applied as a composition. Only a function or value can be applied as a function.

-

It's also worth noting that something that appears to be a value may actually be a function! For example, the result of 𝕨˜𝕩 may not always be 𝕨. 𝕨˜𝕩 is exactly identical to 𝕎˜𝕩, which gives 𝕩𝕎𝕩. If 𝕎 is a number, character, or array, that's the same as 𝕨, but if it is a function, then it will be applied.

-

The primary way to change the role of a value in BQN is to use a name, including one of the arguments to a brace function. In particular, you can use {𝔽} to convert a value operand into a function. Converting a function to a value is more difficult. Often an array of functions is wanted, in which case they can be stranded together; otherwise it's probably best to give the function a name. Picking a function out of a list, for example ⊑⟨+⟩ will give it as a value.

- diff --git a/docs/depth.html b/docs/depth.html deleted file mode 100644 index 93234609..00000000 --- a/docs/depth.html +++ /dev/null @@ -1,135 +0,0 @@ - -

Depth

-

The depth of an array is the greatest level of array nesting it attains, or, put another way, the greatest number of times you can pick an element starting from the original array before reaching a non-array. The monadic function Depth (≡) returns the depth of its argument, while the composition Depth (⚇) can control the way its left operand is applied based on the depth of its arguments. Several primitive functions also use the depth of the left argument to decide whether it applies to a single axis of the right argument or to several axes.

-

The Depth function

-

To find the depth of an array, use Depth (≡). For example, the depth of a list of numbers or characters is 1:

-
    ≡ 2‿3‿4
-1
-    ≡ "a string is a list of characters"
-1
-
-

Depth is somewhat analogous to an array's rank ≠≢𝕩, and in fact rank can be "converted" to depth by splitting rows with <⎉1, reducing the rank by 1 and increasing the depth. Unlike rank, Depth doesn't care at all about its argument's shape:

-
    ≡ 3‿4⥊"characters"
-1
-    ≡ (1+↕10)⥊"characters"
-1
-
-

Also unlike rank, Depth does care about the elements of its argument: in fact, to find the depth of an array, every element must be inspected.

-
    ≡ ⟨2,3,4,5⟩
-1
-    ≡ ⟨2,<3,4,5⟩
-2
-    ≡ ⟨2,<3,4,<<<5⟩
-4
-
-

As the above expressions suggest, the depth of an array is the maximum of its elements, plus one. The base case, a non-array (including a function, modifier, or combinator), has depth 0.

-
    ≡'c'
-0
-    F←+⋄≡f
-0
-    ≡⟨'c',f,2⟩
-1
-    ≡⟨5,⟨'c',f,2⟩⟩
-2
-
-

If the function IsArray indicates whether its argument is an array, then we can write a recursive definition of Depth using the Choose composition.

-
Depth←IsArray◶0‿{1+0⌈´Depth¨⥊𝕩}
-
-

The minimum element depth of 0 implies that an empty array's depth is 1.

-
    ≡⟨⟩
-1
-    ≡2‿0‿3⥊0
-1
-
-

Testing depth for multiple-axis primitives

-

Several primitive functions use the left argument to manipulate the right argument along one or more axes: see leading.md.

- - - - - - - - - - - - - - - - - -
Single-axis depthFunctions
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. But for convenience, a single number is also accepted, and applied to the first axis only. This is equivalent to ravelling the left argument before applying the function.

-
    ≢2↑7‿7‿7‿7⥊"abc"
-[ 2 7 7 7 ]
-    ≢2‿1‿1↑7‿7‿7‿7⥊"abc"
-[ 2 1 1 7 ]
-
-

In these cases the flexibility seems trivial because the left argument has depth 1 or 0: it is an array or isn't, and it's obvious what a plain number should do. But for the second row in the table, the left argument is always an array. The general case is that the left argument is a vector and its elements correspond to right argument axes:

-
    ⟨3‿2,1‿4‿1⟩ ⊏ ↕6‿7
-┌
-  [ 3 1 ] [ 3 4 ] [ 3 1 ]
-  [ 2 1 ] [ 2 4 ] [ 2 1 ]
-                          ┘
-
-

This means the left argument is homogeneous of depth 2. What should an argument of depth 1, or an argument that contains non-arrays, do? One option is to continue to require the left argument to be a vector, and convert any non-array argument into an array by boxing it:

-
    ⟨3‿2,1⟩ <⍟(0=≡)¨⊸⊏ ↕6‿7
-[ [ 3 1 ] [ 2 1 ] ]
-
-

While very consistent, this extension represents a small convenience and makes it difficult to act on a single axis, which for Replicate and Group is probably the most common way the primitive is used:

-
    3‿2‿1‿2‿3 / "abcde"
-[ aaabbcddeee ]
-
-

With the extension above, every case like this would have to use <⊸/ instead of just /. BQN avoids this difficulty by testing the left argument's depth. A depth-1 argument applies to the first axis only, giving the behavior above.

-

For Select, the depth-1 case is still quite useful, but it may also be desirable to choose a single cell using a list of numbers. In this case the left argument depth can be increased from the bottom using <¨.

-
    2‿1‿4 <¨⊸⊏ ↕3‿4‿5‿2
-[ [ 2 1 4 0 ] [ 2 1 4 1 ] ]
-
-

The Depth composition

-

The Depth composition (⚇) is a generalization of Each that allows diving deeper into an array. To illustrate it we'll use a shape 4‿3 array of lists of lists.

-
    ⊢ n ← <⎉1⍟2 4‿3‿2‿2⥊↕48
-┌
-  [ [ 0 1 ] [ 2 3 ] ]     [ [ 4 5 ] [ 6 7 ] ]     [ [ 8 9 ] [ 10 11 ] ]
-  [ [ 12 13 ] [ 14 15 ] ] [ [ 16 17 ] [ 18 19 ] ] [ [ 20 21 ] [ 22 23 ] ]
-  [ [ 24 25 ] [ 26 27 ] ] [ [ 28 29 ] [ 30 31 ] ] [ [ 32 33 ] [ 34 35 ] ]
-  [ [ 36 37 ] [ 38 39 ] ] [ [ 40 41 ] [ 42 43 ] ] [ [ 44 45 ] [ 46 47 ] ]
-                                                                          ┘
-    ≡ n
-3
-
-

Reversing n swaps all the rows:

-
    ⌽ n
-┌
-  [ [ 36 37 ] [ 38 39 ] ] [ [ 40 41 ] [ 42 43 ] ] [ [ 44 45 ] [ 46 47 ] ]
-  [ [ 24 25 ] [ 26 27 ] ] [ [ 28 29 ] [ 30 31 ] ] [ [ 32 33 ] [ 34 35 ] ]
-  [ [ 12 13 ] [ 14 15 ] ] [ [ 16 17 ] [ 18 19 ] ] [ [ 20 21 ] [ 22 23 ] ]
-  [ [ 0 1 ] [ 2 3 ] ]     [ [ 4 5 ] [ 6 7 ] ]     [ [ 8 9 ] [ 10 11 ] ]
-                                                                          ┘
-
-

Depth ¯1 is equivalent to Each, and reverses the larger vectors, while depth ¯2 applies Each twice to reverse the smaller vectors:

-
    ⌽⚇¯1 n
-┌
-  [ [ 2 3 ] [ 0 1 ] ]     [ [ 6 7 ] [ 4 5 ] ]     [ [ 10 11 ] [ 8 9 ] ]
-  [ [ 14 15 ] [ 12 13 ] ] [ [ 18 19 ] [ 16 17 ] ] [ [ 22 23 ] [ 20 21 ] ]
-  [ [ 26 27 ] [ 24 25 ] ] [ [ 30 31 ] [ 28 29 ] ] [ [ 34 35 ] [ 32 33 ] ]
-  [ [ 38 39 ] [ 36 37 ] ] [ [ 42 43 ] [ 40 41 ] ] [ [ 46 47 ] [ 44 45 ] ]
-                                                                          ┘
-    ⌽⚇¯2 n
-┌
-  [ [ 1 0 ] [ 3 2 ] ]     [ [ 5 4 ] [ 7 6 ] ]     [ [ 9 8 ] [ 11 10 ] ]
-  [ [ 13 12 ] [ 15 14 ] ] [ [ 17 16 ] [ 19 18 ] ] [ [ 21 20 ] [ 23 22 ] ]
-  [ [ 25 24 ] [ 27 26 ] ] [ [ 29 28 ] [ 31 30 ] ] [ [ 33 32 ] [ 35 34 ] ]
-  [ [ 37 36 ] [ 39 38 ] ] [ [ 41 40 ] [ 43 42 ] ] [ [ 45 44 ] [ 47 46 ] ]
-                                                                          ┘
-
-

While a negative depth tells how many levels to go down, a non-negative depth gives the maximum depth of the argument before applying the left operand. On a depth-3 array like above, depth 2 is equivalent to ¯1 and depth 1 is equivalent to ¯2. A depth of 0 means to loop until non-arrays are reached, that is, apply pervasively, like a scalar function.

-
    ⟨'a',"bc"⟩ ≍⚇0 ⟨2‿3,4⟩
-[ [ [ a 2 ] [ a 3 ] ] [ [ b 4 ] [ c 4 ] ] ]
-
-

With a positive operand, Depth doesn't have to use the same depth everywhere. Here, Length is applied as soon as the depth for a particular element is 1 or less, including if the argument has depth 0. For example, it maps over ⟨2,⟨3,4⟩⟩, but not over ⟨11,12⟩, even though these are elements of the same array.

-
    ≠⚇1 ⟨1,⟨2,⟨3,4⟩⟩,⟨5,⟨6,7⟩,⟨8,9,10⟩⟩,⟨11,12⟩⟩
-[ 1 [ 1 2 ] [ 1 2 3 ] 2 ]
-
- diff --git a/docs/doc/context.html b/docs/doc/context.html new file mode 100644 index 00000000..22fe5443 --- /dev/null +++ b/docs/doc/context.html @@ -0,0 +1,138 @@ + +

BQN's context-free grammar

+

APL has a problem. To illustrate, let's look at an APL expression:

+
a b c d e
+
+

It is impossible to say anything about this sentence! Is c a dyadic operator being applied to b and d, or are b and d two dyadic functions being applied to arrays? In contrast, expressions in C-like or Lisp-like languages show their structure of application:

+
b(a, d(c)(e))
+(b a ((d c) e))
+
+

In each case, some values are used as inputs to functions while others are the functions being applied. The result of a function can be used either as an input or as a function again. These expressions correspond to the APL expression where a and e are arrays, b and c are functions, and d is a monadic operator. However, these syntactic classes have to be known to see what the APL expression is doing—they are a form of context that is required for a reader to know the grammatical structure of the expression. In a context-free grammar like that of simple C or Lisp expressions, a value's grammatical role is part of the expression itself, indicated with parentheses: they come after the function in C and before it in Lisp. Of course, a consequence of using parentheses in this way is having a lot of parentheses. BQN uses a different method to annotate grammatical role:

+
a B C _d e
+
+

Here, the lowercase spelling indicates that a and e are to be treated as values ("arrays" in APL) while the uppercase spelling of variables B and C are used as functions and _d is a modifier ("monadic operator"). Like parentheses for function application, the spelling is not inherent to the variable values used, but instead indicates their grammatical role in this particular expression. A variable has no inherent spelling and can be used in any role, so the names a, A, _a, and _a_ all refer to exact same variable, but in different roles; typically we use the lowercase name to refer to the variable in isolation. While we still don't know anything about what values a, b, c, and so on have, we know how they interact in the line of code above.

+

Is grammatical context really a problem?

+

Yes, in the sense of problems with BQN. A grammar that uses context is harder for humans to read and machines to execute. A particular difficulty is that parts of an expression you don't yet understand can interfere with parts you do, making it difficult to work through an unknown codebase.

+

One difficulty beginners to APL will encounter is that code in APL at first appears like a string of undifferentiated symbols. For example, a tacit Unique Mask implementation ⍳⍨=⍳∘≢ consists of six largely unfamiliar characters with little to distinguish them (in fact, the one obvious bit of structure, the repeated ⍳, is misleading as it means different things in each case!). Simply placing parentheses into the expression, like (⍳⍨)=(⍳∘≢), can be a great help to a beginner, and part of learning APL is to naturally see where the parentheses should go. The equivalent BQN expression, ⊐˜=↕∘≠, will likely appear equally intimidating at first, but the path to learning which things apply to which is much shorter: rather than learning the entire list of APL primitives, a beginner just needs to know that superscript characters like ˜ are modifiers and characters like ∘ with unbroken circles are compositions before beginning to learn the BQN grammar that will explain how to tie the various parts together.

+

This sounds like a distant concern to a master of APL or a computer that has no difficulty memorizing a few dozen glyphs. Quite the opposite: the same concern applies to variables whenever you begin work with an unfamiliar codebase! Many APL programmers even enforce variable name conventions to ensure they know the class of a variable. By having such a system built in, BQN keeps you from having to rely on programmers following a style guide, and also allows greater flexibility, including functional programming, as we'll see later.

+

Shouldn't a codebase define all the variables it uses, so we can see their class from the definition? Not always: consider that in a language with libraries, code might be imported from dependencies. Many APLs also have some dynamic features that can allow a variable to have more than one class, such as the ⍺←⊢ pattern in a dfn that makes ⍺ an array in the dyadic case but a function in the monadic case. Regardless, searching for a definition somewhere in the code is certainly a lot more work than knowing the class right away! One final difficulty is that even one unknown can delay understanding of an entire expression. Suppose in A B c, B is a function and c is an array, and both values are known to be constant. If A is known to be a function (even if its value is not yet known), its right argument B c can be evaluated ahead of time. But if A's type isn't known, it's impossible to know if this optimization is worth it, because if it is an array, B will instead be called dyadically.

+

BQN's spelling system

+

BQN's expression grammar is a simplified version of the typical APL, removing some oddities like niladic functions and the two-glyph Outer Product operator. Every value can be used in any of four syntactic roles:

+ + + + + + + + + + + + + + + + + + + + + + + + + + + + + + +
BQNAPLJ
ValueArrayNoun
FunctionFunctionVerb
ModifierMonadic operatorAdverb
CompositionDyadic operatorConjunction
+

Unlike variables, BQN primitives have only one spelling, and a fixed role (but their values can be used in a different role by storing them in variables). Superscript glyphs ˜¨˘⁼⌜´` are used for modifiers, and glyphs ∘○⊸⟜⌾⊘◶⚇⎉⍟ with an unbroken circle are compositions. Other primitives are functions. String and numeric literals are values.

+

BQN's variables use another system, where the spelling indicates how the variable's value is used. A variable spelled with a lowercase first letter, like var, is a value. Spelled with an uppercase first letter, like Var, it is a function. Underscores are placed where operands apply to indicate a modifier _var or composition _var_. Other than the first letter or underscore, variables are case-insensitive.

+

The associations between spelling and syntactic role are considered part of BQN's token formation rules.

+

One rule for typing is also best considered to be a pre-parsing rule like the spelling system: the role of a brace construct {} with no header is determined by which special arguments it uses: it's a value if there are none, but a 𝕨 or 𝕩 makes it at least a function, an 𝔽 makes it a modifier or composition, and a 𝔾 always makes it a composition.

+

BQN's grammar

+

A formal treatment is included in the spec. BQN's grammar—the ways syntactic roles interact—follows the original APL model (plus trains) closely, with allowances for new features like list notation. In order to keep BQN's syntax context-free, the syntactic role of any expression must be known from its contents, just like tokens.

+

Here is a table of the APL-derived operator and function application rules:

+ + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + +
leftmainrightoutputname
FxValueMonadic function
wFxValueDyadic function
FGFunction2-train
F*GHFunction3-train
F*_mFunctionModifier
F*_c_G*FunctionComposition
_c_G*ModifierPartial application
F*_c_ModifierPartial application
+

A function with an asterisk indicates that a value can also be used: in these positions there is no difference between function and value spellings. Operator applications bind more tightly than functions, and associate left-to-right while functions associate right-to-left.

+

BQN lists can be written with angle brackets ⟨elt0,elt1,…⟩ or ligatures elt0‿elt1‿…. In either case the elements can have any type, and the result is a value.

+

The statements in a brace block, function, or operator can also be any role, including the return value at the end. These roles have no effect: outside of braces, a function always returns an array, a modifier always returns a function, and so on, regardless of how these objects were defined.

+

Mixing roles

+

BQN's basic types align closely with its syntactic roles: functions, modifiers, and compositions are all basic types, while values are split into numbers, characters, and arrays. This is no accident, and usually values will be used in roles that match their underlying type. However, the ability to use a role that doesn't match the type is very useful.

+

Any type can be passed as an argument to a function, or as an operand, by treating it as a value. This means that BQN fully supports Lisp-style functional programming, where functions can be used as values.

+

It can also be useful to treat a value type as a function, in which case it applies as a constant function. This rule is useful with most built-in operators. For example, F⎉1 uses a constant for the rank even though in general a function can be given, and a⌾(b⊸/) inserts the values in a into the positions selected by b, ignoring the old values rather than applying a function to them.

+

Other mixes of roles are generally not useful. While a combination such as treating a function as a modifier is allowed, attempting to apply it to an operand will fail. Only a modifier can be applied as a modifier and only a composition can be applied as a composition. Only a function or value can be applied as a function.

+

It's also worth noting that something that appears to be a value may actually be a function! For example, the result of 𝕨˜𝕩 may not always be 𝕨. 𝕨˜𝕩 is exactly identical to 𝕎˜𝕩, which gives 𝕩𝕎𝕩. If 𝕎 is a number, character, or array, that's the same as 𝕨, but if it is a function, then it will be applied.

+

The primary way to change the role of a value in BQN is to use a name, including one of the arguments to a brace function. In particular, you can use {𝔽} to convert a value operand into a function. Converting a function to a value is more difficult. Often an array of functions is wanted, in which case they can be stranded together; otherwise it's probably best to give the function a name. Picking a function out of a list, for example ⊑⟨+⟩ will give it as a value.

+ diff --git a/docs/doc/depth.html b/docs/doc/depth.html new file mode 100644 index 00000000..9becdb67 --- /dev/null +++ b/docs/doc/depth.html @@ -0,0 +1,135 @@ + +

Depth

+

The depth of an array is the greatest level of array nesting it attains, or, put another way, the greatest number of times you can pick an element starting from the original array before reaching a non-array. The monadic function Depth (≡) returns the depth of its argument, while the composition Depth (⚇) can control the way its left operand is applied based on the depth of its arguments. Several primitive functions also use the depth of the left argument to decide whether it applies to a single axis of the right argument or to several axes.

+

The Depth function

+

To find the depth of an array, use Depth (≡). For example, the depth of a list of numbers or characters is 1:

+
    ≡ 2‿3‿4
+1
+    ≡ "a string is a list of characters"
+1
+
+

Depth is somewhat analogous to an array's rank ≠≢𝕩, and in fact rank can be "converted" to depth by splitting rows with <⎉1, reducing the rank by 1 and increasing the depth. Unlike rank, Depth doesn't care at all about its argument's shape:

+
    ≡ 3‿4⥊"characters"
+1
+    ≡ (1+↕10)⥊"characters"
+1
+
+

Also unlike rank, Depth does care about the elements of its argument: in fact, to find the depth of an array, every element must be inspected.

+
    ≡ ⟨2,3,4,5⟩
+1
+    ≡ ⟨2,<3,4,5⟩
+2
+    ≡ ⟨2,<3,4,<<<5⟩
+4
+
+

As the above expressions suggest, the depth of an array is the maximum of its elements, plus one. The base case, a non-array (including a function, modifier, or combinator), has depth 0.

+
    ≡'c'
+0
+    F←+⋄≡f
+0
+    ≡⟨'c',f,2⟩
+1
+    ≡⟨5,⟨'c',f,2⟩⟩
+2
+
+

If the function IsArray indicates whether its argument is an array, then we can write a recursive definition of Depth using the Choose composition.

+
Depth←IsArray◶0‿{1+0⌈´Depth¨⥊𝕩}
+
+

The minimum element depth of 0 implies that an empty array's depth is 1.

+
    ≡⟨⟩
+1
+    ≡2‿0‿3⥊0
+1
+
+

Testing depth for multiple-axis primitives

+

Several primitive functions use the left argument to manipulate the right argument along one or more axes: see leading.md.

+ + + + + + + + + + + + + + + + + +
Single-axis depthFunctions
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. But for convenience, a single number is also accepted, and applied to the first axis only. This is equivalent to ravelling the left argument before applying the function.

+
    ≢2↑7‿7‿7‿7⥊"abc"
+[ 2 7 7 7 ]
+    ≢2‿1‿1↑7‿7‿7‿7⥊"abc"
+[ 2 1 1 7 ]
+
+

In these cases the flexibility seems trivial because the left argument has depth 1 or 0: it is an array or isn't, and it's obvious what a plain number should do. But for the second row in the table, the left argument is always an array. The general case is that the left argument is a vector and its elements correspond to right argument axes:

+
    ⟨3‿2,1‿4‿1⟩ ⊏ ↕6‿7
+┌
+  [ 3 1 ] [ 3 4 ] [ 3 1 ]
+  [ 2 1 ] [ 2 4 ] [ 2 1 ]
+                          ┘
+
+

This means the left argument is homogeneous of depth 2. What should an argument of depth 1, or an argument that contains non-arrays, do? One option is to continue to require the left argument to be a vector, and convert any non-array argument into an array by boxing it:

+
    ⟨3‿2,1⟩ <⍟(0=≡)¨⊸⊏ ↕6‿7
+[ [ 3 1 ] [ 2 1 ] ]
+
+

While very consistent, this extension represents a small convenience and makes it difficult to act on a single axis, which for Replicate and Group is probably the most common way the primitive is used:

+
    3‿2‿1‿2‿3 / "abcde"
+[ aaabbcddeee ]
+
+

With the extension above, every case like this would have to use <⊸/ instead of just /. BQN avoids this difficulty by testing the left argument's depth. A depth-1 argument applies to the first axis only, giving the behavior above.

+

For Select, the depth-1 case is still quite useful, but it may also be desirable to choose a single cell using a list of numbers. In this case the left argument depth can be increased from the bottom using <¨.

+
    2‿1‿4 <¨⊸⊏ ↕3‿4‿5‿2
+[ [ 2 1 4 0 ] [ 2 1 4 1 ] ]
+
+

The Depth composition

+

The Depth composition (⚇) is a generalization of Each that allows diving deeper into an array. To illustrate it we'll use a shape 4‿3 array of lists of lists.

+
    ⊢ n ← <⎉1⍟2 4‿3‿2‿2⥊↕48
+┌
+  [ [ 0 1 ] [ 2 3 ] ]     [ [ 4 5 ] [ 6 7 ] ]     [ [ 8 9 ] [ 10 11 ] ]
+  [ [ 12 13 ] [ 14 15 ] ] [ [ 16 17 ] [ 18 19 ] ] [ [ 20 21 ] [ 22 23 ] ]
+  [ [ 24 25 ] [ 26 27 ] ] [ [ 28 29 ] [ 30 31 ] ] [ [ 32 33 ] [ 34 35 ] ]
+  [ [ 36 37 ] [ 38 39 ] ] [ [ 40 41 ] [ 42 43 ] ] [ [ 44 45 ] [ 46 47 ] ]
+                                                                          ┘
+    ≡ n
+3
+
+

Reversing n swaps all the rows:

+
    ⌽ n
+┌
+  [ [ 36 37 ] [ 38 39 ] ] [ [ 40 41 ] [ 42 43 ] ] [ [ 44 45 ] [ 46 47 ] ]
+  [ [ 24 25 ] [ 26 27 ] ] [ [ 28 29 ] [ 30 31 ] ] [ [ 32 33 ] [ 34 35 ] ]
+  [ [ 12 13 ] [ 14 15 ] ] [ [ 16 17 ] [ 18 19 ] ] [ [ 20 21 ] [ 22 23 ] ]
+  [ [ 0 1 ] [ 2 3 ] ]     [ [ 4 5 ] [ 6 7 ] ]     [ [ 8 9 ] [ 10 11 ] ]
+                                                                          ┘
+
+

Depth ¯1 is equivalent to Each, and reverses the larger vectors, while depth ¯2 applies Each twice to reverse the smaller vectors:

+
    ⌽⚇¯1 n
+┌
+  [ [ 2 3 ] [ 0 1 ] ]     [ [ 6 7 ] [ 4 5 ] ]     [ [ 10 11 ] [ 8 9 ] ]
+  [ [ 14 15 ] [ 12 13 ] ] [ [ 18 19 ] [ 16 17 ] ] [ [ 22 23 ] [ 20 21 ] ]
+  [ [ 26 27 ] [ 24 25 ] ] [ [ 30 31 ] [ 28 29 ] ] [ [ 34 35 ] [ 32 33 ] ]
+  [ [ 38 39 ] [ 36 37 ] ] [ [ 42 43 ] [ 40 41 ] ] [ [ 46 47 ] [ 44 45 ] ]
+                                                                          ┘
+    ⌽⚇¯2 n
+┌
+  [ [ 1 0 ] [ 3 2 ] ]     [ [ 5 4 ] [ 7 6 ] ]     [ [ 9 8 ] [ 11 10 ] ]
+  [ [ 13 12 ] [ 15 14 ] ] [ [ 17 16 ] [ 19 18 ] ] [ [ 21 20 ] [ 23 22 ] ]
+  [ [ 25 24 ] [ 27 26 ] ] [ [ 29 28 ] [ 31 30 ] ] [ [ 33 32 ] [ 35 34 ] ]
+  [ [ 37 36 ] [ 39 38 ] ] [ [ 41 40 ] [ 43 42 ] ] [ [ 45 44 ] [ 47 46 ] ]
+                                                                          ┘
+
+

While a negative depth tells how many levels to go down, a non-negative depth gives the maximum depth of the argument before applying the left operand. On a depth-3 array like above, depth 2 is equivalent to ¯1 and depth 1 is equivalent to ¯2. A depth of 0 means to loop until non-arrays are reached, that is, apply pervasively, like a scalar function.

+
    ⟨'a',"bc"⟩ ≍⚇0 ⟨2‿3,4⟩
+[ [ [ a 2 ] [ a 3 ] ] [ [ b 4 ] [ c 4 ] ] ]
+
+

With a positive operand, Depth doesn't have to use the same depth everywhere. Here, Length is applied as soon as the depth for a particular element is 1 or less, including if the argument has depth 0. For example, it maps over ⟨2,⟨3,4⟩⟩, but not over ⟨11,12⟩, even though these are elements of the same array.

+
    ≠⚇1 ⟨1,⟨2,⟨3,4⟩⟩,⟨5,⟨6,7⟩,⟨8,9,10⟩⟩,⟨11,12⟩⟩
+[ 1 [ 1 2 ] [ 1 2 3 ] 2 ]
+
+ diff --git a/docs/doc/fromDyalog.html b/docs/doc/fromDyalog.html new file mode 100644 index 00000000..57196984 --- /dev/null +++ b/docs/doc/fromDyalog.html @@ -0,0 +1,205 @@ + +

BQN–Dyalog APL dictionary

+

A few tables to help users of Dyalog APL (or similar) get started quickly on BQN. Here we assume ⎕ML is 1 for Dyalog.

+

For reading

+

Here are some closest equivalents in Dyalog APL for the BQN functions that don't use the same glyphs as APL. Correspondence can be approximate, and ⌽ is just used as a decorator to mean "reverse some things".

+ + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + +
BQN⋆√∧∨¬≠<>≢⥊∾≍
Monad**∘(÷2)[⍋][⍒]~≢⊂↑⍴,⊃,⌿↑,⍥⊂
Dyad**∘÷⍨∧∨1+-≠<>≢⍴⍪↑,⍥⊂
+ + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + +
BQN↑↓↕/⍋⍒⊏⊑⊐⊒∊⍷⊔
Monad,⍀⌽,⌽⍀⌽⍳⍸⍋⍒⊣⌿⊃…≠∪⌸
Dyad↑↓,⌿⌿⍸⌽⍸⌽⌷⊃⍳…∊⍷⌸ or ⊆
+

Modifiers and combinators are a little harder. Many have equivalents in some cases, but Dyalog sometimes chooses different functionality based on whether the operand is an array. In BQN an array is always treated as a constant function.

+ + + + + + + + + + + + + + + + + + + + + + + + + + + + + +
BQN¨⌜´⎉⍟˜∘○⟜
Dyalog¨∘.⌿⍤⍣⍨⍤⍥∘
+

In BQN ⎉ is Rank and ∘ is Atop. Dyalog's Atop (⍤) and Over (⍥) were added in version 18.0.

+

For writing

+

The tables below give approximate implementations of Dyalog primitives for the ones that aren't the same. First- and last-axis pairs are also mostly omitted. BQN just has the first-axis form, and you can get the last-axis form with ⎉1.

+ + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + +
Functions
Glyph Monadic Dyadic
* ⋆
⍟ ⋆⁼
! Implement it yourself
○ Some complex exponential stuff, maybe
~ ¬ ¬∘∊/⊣
? Library?
⍲ ¬∘∧
⍱ ¬∘∨
⍴ ≢ ⥊
, ⥊ ∾⎉1
⍪ ⥊˘ ∾
↑ > ↑
↓ <˘ ↑
⊂ < +`⊸⊔
⊆ <⍟(0<≡) ⊔
∊ {0=≡𝕩:⥊𝕩⋄∾⥊∇¨𝕩} ∊
⊃ ⊑
⍀ /⁼
∩ ∊/⊣
∪ ⍷ ⊣∾∊˜¬⊸/⊢
⍳ ↕ ⊐
⍸ / ⍋
⍋ ⍋ Give up
⍒ ⍒ Give up
≢ ≠ ≢
⍎ To be decided
⍕
⊥ {+⟜(𝕨⊸×)´⌽𝕩}
⊤ {𝕨|1↓⌊∘÷`⌾⌽𝕨∾<𝕩}
⌹ +´∘×⎉1‿∞⁼ I guess
⌷ N/A ⊏
+ + + + + + + + + + + + + + + + + + + + + + + +
Operators
Syntax Monadic Dyadic
⌿ ´ ↕
⍀ ↑ or `
¨ ¨
⍨ ˜
⍣ ⍟
f.g f´∘g⍟1‿∞
∘.f f⌜
A∘g A⊸g
f∘B f⟜B
f∘g f⟜g
f⍤B f⎉B
f⍤g f∘g
f⍥g f○g
f@v f⌾(v⊸⊏)
f⍠B Uh
f⌸ ⍷⊸⊐⊔↕∘≠⍷⊸⊐⊸⊔
f⌺B ↕
A⌶ •
f& Nothing yet
+ + diff --git a/docs/doc/functional.html b/docs/doc/functional.html new file mode 100644 index 00000000..e070e279 --- /dev/null +++ b/docs/doc/functional.html @@ -0,0 +1,74 @@ + +

Functional programming

+

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.

+

Traditionally APL has worked around its lack of first-class functions with operators or 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.

+

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, two 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.

+

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 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 ⎕ORs even share a form of BQN's 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 ⎕ORs, so they don't work very well as a first-class function mechanism.

+

Another reason for APL's reluctance to adopt first-class functions is that Iverson and others seemed to believe that functions fundamentally are not a kind of data, because it's impossible to uniquely represent, compare, and order them. One effect of this viewpoint is J's gerund mechanism, which converts a function to an array representation, primarily so that lists of gerunds can be created. Gerunds are nested arrays containing character vectors at the leaves, so they are arrays as Iverson thought of them. However, I consider this conversion of functions to arrays, intended to avoid arrays that contain "black box" functions, to be a mistake: while it doesn't compromise the purity of arrays, it gives the illusion that a function corresponds to a particular array, which is not true from the mathematical perspective of functions as mappings from an arbitrary input to an output. I also think the experience of countless languages with first-class functions shows that there is no practical issue with arrays that contain functions. While having all arrays be concrete entities with a unique canonical representation seems desirable, I don't find the existence of arrays without this property to be detract from working with arrays that do have it.

+

Functional programming in BQN

+

Reminder: I am discussing only first-class functional programming here, and not other concepts like pure or typed functional programming!

+

What does functional programming in BQN look like? How is it different from the typical APL style of manipulating functions with operators?

+

Working with roles

+

First, let's look at the basics: a small program that takes a function as its argument and result. The function Lin below gives a linear approximation to its function argument based on the values at 0 and 1. To find these two values, we call the argument as a function by using its uppercase spelling, 𝕏.

+
Lin ← {
+  v0 ← 𝕏 0
+  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 value role). The result is a train that adds 1 to e-1 times the argument.

+
    Exp ← ⋆
+    Lin exp
+(1 + (1.71828182845905 × ⊢))
+
+

As with all functions, the result of Lin has a value role. To use it as a function, we give it a name and then use that name with an uppercase spelling.

+
    expLin ← Lin exp
+    ExpLin 5
+9.59140914229523
+
+

A tricker but more compact method is to use the modifier {𝔽}, as the input to a modifier can have a value or function role but its output always has a function role.

+
    (Lin exp){𝔽} 5
+9.59140914229523
+
+

Not the most accurate approximation, though.

+
    Exp 5
+148.413159102577
+
+

Note also in this case that we could have used a modifier with a very similar definition to Lin. The modifier is identical in definition except that 𝕏 is replaced with 𝔽.

+
_lin ↩ {
+  v0 ← 𝔽 0
+  v0 + ((𝔽 1) - v0) × ⊢
+}
+
+

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.

+
    Exp _lin 5
+9.59140914229523
+
+

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 values. Here's an example of an array of functions with a reduction applied to it, composing them together.

+
    {𝕎∘𝕏}´ ⋆‿-‿(ט)
+⋆∘(-∘(ט))
+
+

Like any function, this one can be given a name and then called. A quirk of this way of defining a function is that it has a value role (it's the result of the function {𝕎∘𝕏}´) and so must be defined with a lowercase name.

+
    gauss ← {𝕎∘𝕏}´ ⋆‿-‿(ט)
+    Gauss 2
+0.0183156388887342
+
+

Another, and probably more common, use of arrays of functions is to apply several different functions to one or more arguments. Here we apply three different functions to the number 9:

+
    ⟨√, 2⊸∾, ⊢-⋆⟩ {𝕎𝕩}¨ 9
+[ 3 [ 2 9 ] ¯8094.083927575384 ]
+
+

The composition Choose (◶) relies on arrays of functions to… function. It's very closely related to Pick ⊑, and in fact when the left operand and the elements of the right operand are all value types there's no real difference: Choose returns the constant function 𝕗⊑𝕘.

+
    2◶"abcdef" "arg"
+c
+
+

When the operands contain functions, however, the potential of Choose as a ternary-or-more operator opens up. Here's a function for a step in the Collatz sequence, which halves an even input but multiplies an odd input by 3 and adds 1. To get the sequence for a number, we can apply the same function many times. It's an open problem whether the sequence always ends with the repetition 4, 2, 1, but it can take a surprisingly long time to get there—try 27 as an argument.

+
    (2⊸|)◶⟨÷⟜2,1+3×⊢⟩¨ 6‿7
+[ 3 22 ]
+    (2⊸|)◶⟨÷⟜2,1+3×⊢⟩⍟(↕10) 6
+[ 6 3 10 5 16 8 4 2 1 4 ]
+
+ diff --git a/docs/doc/group.html b/docs/doc/group.html new file mode 100644 index 00000000..052aea7b --- /dev/null +++ b/docs/doc/group.html @@ -0,0 +1,152 @@ + +

Group

+

BQN replaces the Key operator from J or Dyalog APL, and many forms of partitioning, 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.

+

The BQN prototype does not implement this function: instead it uses ⊔ for a Group/Key function very similar to {⊂⍵}⌸ in Dyalog APL, and also has a Cut function \. The new BQN Group on numeric arguments (equivalently, rank-1 results) can be defined like this:

+
⊔↩((↕1+(>⌈´))=¨<)∘⊣ /¨⟜< ↕∘≠⍠⊢
+
+

Once defined, the old BQN Key (dyadic) is ⍷⊸⊐⊸⊔ and Group (monadic) is ⍷⊸⊐⊔↕∘≠ using the Deduplicate or Unique Cells function ⍷ (BQN2NGN spells it ∪). Cut on matching-length arguments is +`⊸⊔.

+

Definition

+

Group operates on a numeric list of indices and a value array, treated as a list of its major cells, to produce a list of groups, each of which is a selection from the values. The indices and values have the same length, and each value cell is paired with the index at the same position. That index indicates the result group the value should go into, with an "index" of ¯1 indicating that it should be dropped and not appear in the result.

+
    0‿1‿2‿0‿1 ≍ "abcde"  # Corresponding indices and values
+┌
+  0 1 2 0 1
+  a b c d e
+            ┘
+    0‿1‿2‿0‿1 ⊔ "abcde"  # Values grouped by index
+[ [ ad ] [ be ] [ c ] ]
+
+

For example, we might choose to group a list of words by length. Within each group, values maintain the ordering they had in the list originally.

+
    phrase ← "BQN"‿"uses"‿"notation"‿"as"‿"a"‿"tool"‿"of"‿"thought"
+    ⥊˘ ≠¨⊸⊔ phrase
+┌
+  []
+  [ [ a ] ]
+  [ [ as ] [ of ] ]
+  [ [ BQN ] ]
+  [ [ uses ] [ tool ] ]
+  []
+  []
+  [ [ thought ] ]
+  [ [ notation ] ]
+                        ┘
+
+

(Could we define phrase more easily? See below.)

+

If we'd like to ignore words of 0 letters, or more than 5, we can set all word lengths greater than 5 to 0, then reduce the lengths by 1. Two words end up with left argument values of ¯1 and are omitted from the result.

+
    1-˜≤⟜5⊸×≠¨phrase
+[ 2 3 ¯1 1 0 3 1 ¯1 ]
+    ⥊˘ {1-˜≤⟜5⊸×≠¨𝕩}⊸⊔ phrase
+┌
+  [ [ a ] ]
+  [ [ as ] [ of ] ]
+  [ [ BQN ] ]
+  [ [ uses ] [ tool ] ]
+                        ┘
+
+

Note that the length of the result is determined by the largest index. So the result never includes trailing empty groups. A reader of the above code might expect 5 groups (lengths 1 through 5), but there are no words of length 5, so the last group isn't there.

+

When Group is called dyadically, the left argument is used for the indices and the right is used for values, as seen above. When it is called monadically, the right argument gives the indices and the values grouped are the right argument's indices, that is, ↕≠𝕩.

+
    ⥊˘ ⊔ 2‿3‿¯1‿2
+┌
+  []
+  []
+  [ [ 0 ] [ 3 ] ]
+  [ [ 1 ] ]
+                  ┘
+
+

Here, the index 2 appears at indices 0 and 3 while the index 3 appears at index 1.

+

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 vector of numeric vectors, 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.

+

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.

+
    ⟨0‿0‿1‿1,0‿1‿0‿1‿0‿1‿0⟩⊔(10×↕4)+⌜↕7
+┌
+  ┌               ┌
+     0  2  4  6      1  3  5
+    10 12 14 16     11 13 15
+                ┘            ┘
+  ┌               ┌
+    20 22 24 26     21 23 25
+    30 32 34 36     31 33 35
+                ┘            ┘
+                               ┘
+
+

Each group i⊑𝕨⊔𝕩 is composed of the cells j<¨⊸⊏𝕩 such that i≢j⊑¨𝕨. The groups retain their array structure and ordering along each argument axis. Using multidimensional Replicate we can say that i⊑𝕨⊔𝕩 is (i=𝕨)/𝕩.

+

The monadic case works similarly: Group Indices always satisfies ⊔𝕩 ←→ 𝕩⊔↕≠⚇1 x. As with ↕, the depth of the result of Group Indices is always one greater than that of its argument. A depth-0 argument is not allowed.

+

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:

+
    ≠¨⊔ 2‿3‿1‿2
+[ 0 1 2 1 ]
+    /⁼∧ 2‿3‿1‿2
+[ 0 1 2 1 ]
+
+

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.

+
    /≠¨⊔ 2‿3‿1‿¯1‿2
+[ 1 2 2 3 ]
+
+

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.

+
    ∾ 2‿3‿1‿¯1‿2 ⊔ "abcde"
+[ caeb ]
+    2‿3‿1‿¯1‿2 {F←(0≤𝕨)⊸/ ⋄ 𝕨⍋⊸⊏○F𝕩} "abcde"
+[ caeb ]
+
+

Group can even be implemented with the same techniques as a bucket sort, which can be 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 Unique and Index Of (the combination ⍷⊸⊐ has been called "self-classify").

+
    ln ← "Phelps"‿"Latynina"‿"Bjørgen"‿"Andrianov"‿"Bjørndalen"
+    co ← "US"    ‿"SU"      ‿"NO"     ‿"SU"       ‿"NO"
+    ⥊˘ co ⍷⊸⊐⊸⊔ ln
+┌
+  [ [ Phelps ] ]
+  [ [ Latynina ] [ Andrianov ] ]
+  [ [ Bjørgen ] [ Bjørndalen ] ]
+                                 ┘
+
+

If we would like a particular index to key correspondence, we can use a fixed left argument to Index Of.

+
    countries ← "IT"‿"JP"‿"NO"‿"SU"‿"US"
+    countries ∾˘ co countries⊸⊐⊸⊔ ln
+┌
+  [ IT ] []
+  [ JP ] []
+  [ NO ] [ [ Bjørgen ] [ Bjørndalen ] ]
+  [ SU ] [ [ Latynina ] [ Andrianov ] ]
+  [ US ] [ [ Phelps ] ]
+                                        ┘
+
+

However, this solution will fail if there are trailing keys with no values. To force the result to have a particular length you can append that length as a dummy index to each argument, then remove the last group after grouping.

+
    countries ↩ "IT"‿"JP"‿"NO"‿"SU"‿"US"‿"ZW"
+    countries ∾˘ co countries{𝕗⊸⊐⊸(¯1↓⊔○(∾⟜(≠𝕗)))} ln
+┌
+  [ IT ] []
+  [ JP ] []
+  [ NO ] [ [ Bjørgen ] [ Bjørndalen ] ]
+  [ SU ] [ [ Latynina ] [ Andrianov ] ]
+  [ US ] [ [ Phelps ] ]
+  [ ZW ] []
+                                        ┘
+
+

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.

+
    ' '(+`∘=⊔⊢)"BQN uses notation as a tool of thought"
+[ [ BQN ] [  uses ] [  notation ] [  as ] [  a ] [  tool ] [  of ] [  thought ] ]
+
+

To avoid including spaces in the result, we should change the result index at each space to ¯1. Here is one way to do that:

+
    ' '((⊢-˜¬×+`)∘=⊔⊢)"BQN uses notation as a tool of thought"
+[ [ BQN ] [ uses ] [ notation ] [ as ] [ a ] [ tool ] [ of ] [ thought ] ]
+
+

A function with structural Under, such as {¯1¨⌾(𝕩⊸/)+`𝕩}, would also work.

+

In other cases, we might want to split on spaces, so that words are separated by any number of spaces, and extra spaces don't affect the output. Currently our function makes a new word with each space:

+
    ' '((⊢-˜¬×+`)∘=⊔⊢)"  string with  spaces   "
+[ [] [] [ string ] [ with ] [] [ spaces ] ]
+
+

However, trailing spaces are ignored because Group never produces trailing empty groups (to get them back we would use a dummy final character in the string). To avoid empty words, 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 Windows function. We will extend our list with an initial 1 so that leading spaces will be ignored. Then we take windows of the same length as the original list: the first includes the dummy argument followed by a shifted copy of the list, and the second is the original list. These represent whether the previous and current characters are spaces; we want positions where the previous wasn't a space and the current is.

+
    ≍⟜((<´<˘)≠↕1∾⊢) ' '="  string with  spaces   "  # All, then filtered, spaces
+┌
+  1 1 0 0 0 0 0 0 1 0 0 0 0 1 1 0 0 0 0 0 0 1 1 1
+  0 0 0 0 0 0 0 0 1 0 0 0 0 1 0 0 0 0 0 0 0 1 0 0
+    ≍⟜(⊢-˜¬×+`∘((<´<˘)≠↕1∾⊢))' '="  string with  spaces   "  # More processing
+┌
+   1  1 0 0 0 0 0 0  1 0 0 0 0  1  1 0 0 0 0 0 0  1  1  1
+  ¯1 ¯1 0 0 0 0 0 0 ¯1 1 1 1 1 ¯1 ¯1 2 2 2 2 2 2 ¯1 ¯1 ¯1
+                                                          ┘
+    ' '((⊢-˜¬×+`∘((<´<˘)≠↕1∾⊢))∘=⊔⊢)"  string with  spaces   "  # Final result
+[ [ string ] [ with ] [ spaces ] ]
+
+ diff --git a/docs/doc/indices.html b/docs/doc/indices.html new file mode 100644 index 00000000..06f0af0c --- /dev/null +++ b/docs/doc/indices.html @@ -0,0 +1,100 @@ + +

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, 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 (depth 0) indices, which can refer to vector elements or array major cells (or more generally indexing along any particular axis). When using this kind of element indices, arrays are required to be vectors. Only two functions allow the use of vector element indices: Range (↕), which can accept a vector argument, and Pick (⊑), which uses the depth-1 arrays in its left argument as index scalars or vectors.

+

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 return type of indices is as useful as possible.

+ + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + +
MonadDyadWhereHow
↕Element scalar or vector
/Element scalar
⊔Element scalar
⊔⊔𝕨/𝕩Along-axis scalar
⊑𝕨Element vector
⍋⍋Major cell scalar
⍒⍒Major cell scalar
⊐Major cell scalar
⊒Major cell scalar
⊏𝕨Major cell or along-axis scalar
⍉Axis scalar
+

Dyadic Transpose (⍉) takes an index into the right argument axes as its left argument, but since array shape is 1-dimensional, there is only one sensible choice for this, a single number.

+

Element indices

+

In general, the index of an element of an array is a vector whose length matches the array rank. It is also possible to use a number for an index into a vector, as the vector 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 vector 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 vector indices. However, this usually rules out the possibility of using scalar 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 depth-0 indices, which comes with the requirement that the arguments to monadic / and ⊔, and the result of monadic ⊔, must be vectors. For dyadic ⊔ the depth-1 elements of the left argument are vectors of indices along axes of the result; see the documentation. 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 prevents Group from having to use an ordering on vector indices.

+

Unlike / and ⊔, ↕ and ⊑ do use vector element indices. For ↕ this is because the output format can be controlled by the argument format: if passed a single number, the result uses single-number indices (so it's a numeric vector); if passed a vector, it uses vector indices and the result has depth 2 (the result depth is always one greater than the argument depth). For ⊑, vector indices are chosen because ⊏ handles scalar indices well already. When selecting multiple elements from a vector, they would typically have to be placed in an array, which is equivalent to ⊏ with a numeric vector left argument. A single scalar index to ⊑ is converted to a vector, 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 scalars or higher-rank arrays allowed. Single numbers also cannot be used in this context, as it would create ambiguity: is a one-element vector an index, or does it contain an index?

+

Major cell indices

+

One of the successes of the leading axis model is to introduce a kind of index for multidimensional arrays that is easier to work with than vector indices. The model introduces cells, where a cell index is a vector 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.

+

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.

+

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 vector of depth-1 elements. In each case the depth-1 arrays index into a single axis.

+

General cell indices

+

BQN does not use general cell indices directly, but it is useful to consider how they might work, and how a programmer might implement functions that use them in BQN if needed. The functions /, ⊔, and ⊏ are the ones that can work with indices for multidimensional arrays but don't already. Here we will examine how multidimensional versions would work.

+

A cell index into an array of rank r is a numeric vector of length l≤r, which then refers to a cell of rank r-l. In BQN, the cell at index i of array a is i<¨⊸⊏a.

+

Because the shape of a cell index relates to the shape of the indexed array, it makes sense not to enclose cell indices, instead treating them as rows of an index array. A definition for ⊏ for depth-1 left arguments of rank at least 1 follows: replace each row of the left argument with the indexed cell of the right, yielding a result with the same depth as the right argument and shape 𝕨((¯1↓⊣)∾(¯1↑⊣)⊸↓)○≢𝕩.

+

To match this format, Range (↕) could be changed to return a flat array when given a shape—what is now >↕. Following this pattern, Indices (/) would also return a flat array, where the indices are rows: using the modified Range, ⥊/↕∘≢. Here the result cannot retain the argument's array structure; it is always a rank-2 list of rows.

+

The most interesting feature would be that ⊏ could still allow a nested left argument. In this case each element of the left argument would be an array with row indices as before. However, each row can now index along multiple axes, allowing some adjacent axes to be dependent while others remain independent. This nicely unifies scatter-point and per-axis selection, and allows a mix of the two. However, it doesn't allow total freedom, as non-adjacent axes can't be combined except by also mixing in all axes in between.

+

Group (⊔) could accept the same index format for its index argument. Each depth-1 array in the left argument would correspond to multiple axes in the outer result array, but only a single axis in the argument and inner arrays. Because the ravel ordering of indices must be used to order cells of inner arrays, this modification is not quite as clean as the change to Select. It's also not so clearly useful, as the same results can be obtained by using numeric indices and reshaping the result.

+

Overall it seems to me that the main use of cell indices of the type discussed here is for the Select primitive, and the other cases are somewhat contrived an awkward. So I've chosen not to support it in BQN at all.

+ diff --git a/docs/doc/join.html b/docs/doc/join.html new file mode 100644 index 00000000..744fa923 --- /dev/null +++ b/docs/doc/join.html @@ -0,0 +1,38 @@ + +

Join

+

Join (∾) is an extension of the monadic function Raze from A+ and J to arbitrary argument ranks. It has the same relationship to Join to, the dyadic function sharing the same glyph, as Unbox (>) does to Couple (≍): a≍b is >a‿b and a∾b is ∾a‿b. While Unbox and Couple combine arrays (the elements of Unbox's argument, or the arguments themselves for Coups) along a new leading axis, Join and Join to combine them along the existing leading axis. Both Unbox and Join can also be called on a higher-rank array, causing Unbox to add multiple leading axes while Join combines elements along multiple existing axes.

+

Join can be used to combine several strings into a single string, like array.join() in Javascript (but it doesn't force the result to be a string).

+
    ∾"time"‿"to"‿"join"‿"some"‿"words"
+[ timetojoinsomewords ]
+
+

To join with a separator in between, we might prepend the separator to each string, then remove the leading separator after joining. Another approach would be to insert the separator array as an element between each pair of array elements before calling Join.

+
    1↓∾' '∾¨"time"‿"to"‿"join"‿"some"‿"words"
+[ time to join some words ]
+
+

Join requires each element of its argument to be an array, and their ranks to match exactly. No rank extension is performed.

+
    ∾"abc"‿'d'‿"ef"  # Includes a non-array
+RANK ERROR
+    ∾"abc"‿(<'d')‿"ef"  # Includes a scalar
+RANK ERROR
+
+

However, Join has higher-dimensional uses as well. Given a rank-m array of rank-n arrays (requiring m≤n), it will merge arrays along their first m axes. For example, if the argument is a matrix of matrices representing a block matrix, Join will give the corresponding unblocked matrix as its result.

+
    ⊢ m ← (3‿1∾⌜4‿2‿5) ⥊¨ 2‿3⥊↕6
+┌
+  ┌           ┌       ┌
+    0 0 0 0     1 1     2 2 2 2 2
+    0 0 0 0     1 1     2 2 2 2 2
+    0 0 0 0     1 1     2 2 2 2 2
+            ┘       ┘             ┘
+  [ 3 3 3 3 ] [ 4 4 ] [ 5 5 5 5 5 ]
+                                    ┘
+    ∾ m  # Join all that together
+┌
+  0 0 0 0 1 1 2 2 2 2 2
+  0 0 0 0 1 1 2 2 2 2 2
+  0 0 0 0 1 1 2 2 2 2 2
+  3 3 3 3 4 4 5 5 5 5 5
+                        ┘
+
+

Join has fairly strict requirements on the shapes of its argument elements—although less strict than those of Unbox, which requires they all have identical shape. Suppose the argument to Join has rank m. Each of its elements must have the same rank, n, which is at least m. The trailing shapes m↓⟜≢¨𝕩 must all be identical (the trailing shape m↓≢∾𝕩 of the result will match these shapes as well). The other entries in the leading shapes need not be the same, but the shape of an element along a particular axis must depend only on the location of the element along that axis in the full array. For a vector argument this imposes no restriction, since the one leading shape element is allowed to depend on position along the only axis. But for higher ranks the structure quickly becomes more rigid.

+

To state this requirement more formally in BQN, we say that there is some vector s of length vectors, so that (≢¨s)≡≢𝕩. We require element i⊑𝕩 to have shape i⊑¨s. Then the first m axes of the result are +´¨s.

+ diff --git a/docs/doc/logic.html b/docs/doc/logic.html new file mode 100644 index 00000000..87b5fad1 --- /dev/null +++ b/docs/doc/logic.html @@ -0,0 +1,42 @@ + +

Logic functions: And, Or, Not (also Span)

+

BQN retains the APL symbols ∧ and ∨ for logical and and or, and changed APL's ~ to ¬ for not, since ~ looks too much like ˜ and ¬ is more common in mathematics today. Like J, BQN extends Not to the linear function 1⊸-. However, it discards GCD and LCM as extensions of And and Or, and instead uses bilinear extensions: And is identical to Times (×), while Or is ×⌾¬, following De Morgan's laws (other ways of obtaining a function for Or give an equivalent result—there is only one bilinear extension).

+

If the arguments are probabilities of independent events, then an extended function gives the probability of the boolean function on their outcomes (for example, if A occurs with probability a and B with probability b independent of A, then A or B occurs with probability a∨b). These extensions have also been used in complexity theory, because they allow mathematicians to transfer a logical circuit from the discrete to the continuous domain in order to use calculus on it.

+

Both valences of ¬ are equivalent to the fork 1+-. The dyadic valence, called "Span", computes the number of integers in the range from 𝕩 to 𝕨, inclusive, when both arguments are integers and 𝕩≤𝕨 (note the reversed order, which is used for consistency with subtraction). This function has many uses, and in particular is relevant to the Windows function.

+

Definitions

+

We define:

+
Not ← 1+-  # also Span
+And ← ×
+Or  ← ×⌾¬
+
+

Note that ¬⁼ ←→ ¬, since the first added 1 will be negated but the second won't; the two 1s cancel leaving two subtractions, and -⁼ ←→ -. An alternate definition of Or that matches the typical formula from probability theory is

+
Or  ← +-×
+
+

Examples

+

We can form truth tables including the non-integer value one-half:

+
    ¬ 0‿0.5‿1
+[ 1 0.5 0 ]
+
+    ∧⌜˜ 0‿0.5‿1
+┌
+  0    0   0
+  0 0.25 0.5
+  0  0.5   1
+             ┘
+
+    ∨⌜˜ 0‿0.5‿1
+┌
+    0  0.5 1
+  0.5 0.75 1
+    1    1 1
+             ┘
+
+

As with logical And and Or, any value and 0 is 0, while any value or 1 is 1. The other boolean values give the identity elements for the two functions: 1 and any value gives that value, as does 0 or the value.

+

Why not GCD and LCM?

+

The main reason for omitting these functions is that they are complicated and, when applied to real or complex numbers, require a significant number of design decisions where there is no obvious choice (for example, whether to use comparison tolerance). On the other hand, these functions are fairly easy to implement, which allows the programmer to control the details, and also add functionality such as the extended GCD.

+

A secondary reason is that the GCD falls short as an extension of Or, because its identity element 0 is not total. 0∨x, for a real number x, is actually equal to |x and not x: for example, 0∨¯2 is 2 in APL. This means the identity 0∨x ←→ x isn't reliable in APL.

+

Identity elements

+

It's common to apply ∧´ or ∨´ to a list (checking whether all elements are true and whether any are true, respectively), and so it's important for extensions to And and Or to share their identity element. Minimum and Maximum do match And and Or when restricted to booleans, but they have different identity elements. It would be dangerous to use Maximum to check whether any element of a list is true because >⌈´⟨⟩ yields ¯∞ instead of 0—a bug waiting to happen. Always using 0 as a left argument to ⌈´ fixes this problem but requires more work from the programmer, making errors more likely.

+

It is easy to prove that the bilinear extensions have the identity elements we want. Of course 1∧x is 1×x, or x, and 0∨x is 0×⌾¬x, or ¬1׬x, giving ¬¬x or x again. Both functions are commutative, so these identities are double-sided.

+

Other logical identities do not necessarily hold. For example, in boolean logic And distributes over Or and vice-versa: a∧b∨c ←→ (a∧b)∨(a∧c). But substituting × for ∧ and +-× for ∨ we find that the left hand side is (a×b)+(a×c)+(a×b×c) while the right gives (a×b)+(a×c)+(a×b×a×c). These are equivalent for arbitrary b and c only if a=a×a, that is, a is 0 or 1. In terms of probabilities the difference when a is not boolean is caused by failure of independence. On the left hand side, the two arguments of every logical function are independent. On the right hand side, each pair of arguments to ∧ are independent, but the two arguments to ∨, a∧b and a∧c, are not. The relationship between these arguments means that logical equivalences no longer apply.

+ diff --git a/docs/doc/transpose.html b/docs/doc/transpose.html new file mode 100644 index 00000000..d2629546 --- /dev/null +++ b/docs/doc/transpose.html @@ -0,0 +1,88 @@ + +

Transpose

+

As in APL, Transpose (⍉) is a tool for rearranging the axes of an array. BQN's version is tweaked to align better with the leading axis model and make common operations easier.

+

Monadic Transpose

+

Transposing a matrix exchanges its axes, mirroring it across the diagonal. APL extends the function to any rank by reversing all axes, but this generalization isn't very natural and is almost never used. The main reason for it is to maintain the equivalence a MP b ←→ a MP⌾⍉ b, where MP ← (+´<˘)∘×⎉1‿∞ is the generalized matrix product. But even here APL's Transpose is suspect. It does much more work than it needs to, as we'll see.

+

BQN's transpose takes the first axis of its argument and moves it to the end.

+
    ≢ a23456 ← ↕2‿3‿4‿5‿6
+[ 2 3 4 5 6 ]
+    ≢ ⍉ a23456
+[ 3 4 5 6 2 ]
+
+

On the argument's ravel, this looks like a simple 2-dimensional transpose: one axis is exchanged with a compound axis made up of the other axes. Here we transpose a rank 3 matrix:

+
    a322 ← 3‿2‿2⥊↕12
+    ≍○<⟜⍉ a322
+┌
+  ┌         ┌
+     0  1     0 4  8
+     2  3     1 5  9
+
+     4  5     2 6 10
+     6  7     3 7 11
+                     ┘
+     8  9
+    10 11
+          ┘
+                       ┘
+
+

But, reading in ravel order, the argument and result have exactly the same element ordering as for the rank 2 matrix ⥊˘ a322:

+
    ≍○<⟜⍉ ⥊˘ a322
+┌
+  ┌             ┌
+    0 1  2  3     0 4  8
+    4 5  6  7     1 5  9
+    8 9 10 11     2 6 10
+              ┘   3 7 11
+                         ┘
+                           ┘
+
+

To exchange multiple axes, use the Power operator. Like Rotate, a negative power will move axes in the other direction. In particular, to move the last axis to the front, use Inverse (as you might expect, this exactly inverts ⍉).

+
    ≢ ⍉⍟3 a23456
+[ 5 6 2 3 4 ]
+    ≢ ⍉⁼ a23456
+[ 6 2 3 4 5 ]
+
+

In fact, we have ≢⍉⍟k a ←→ k⌽≢a for any number k and array a.

+

To move axes other than the first, use the Rank operator in order to leave initial axes untouched. A rank of k>0 transposes only the last k axes while a rank of k<0 ignores the first |k axes.

+
    ≢ ⍉⎉3 a23456
+[ 2 3 5 6 4 ]
+
+

And of course, Rank and Power can be combined to do more complicated transpositions: move a set of contiguous axes with any starting point and length to the end.

+
    ≢ ⍉⁼⎉¯1 a23456
+[ 2 6 3 4 5 ]
+
+

Using these forms, we can state BQN's generalized matrix product swapping rule:

+
a MP b  ←→  ⍉⍟(≠≢a) a ⍉⁼⊸MP⟜⍉ b
+
+

Certainly not as concise as APL's version, but not a horror either. BQN's rule is actually more parsimonious in that it only performs the axis exchanges necessary for the computation: it moves the two axes that will be paired with the matrix product into place before the product, and directly exchanges all axes afterwards. Each of these steps is equivalent in terms of data movement to a matrix transpose, the simplest nontrivial transpose to perform. Also remember that for two-dimensional matrices both kinds of transposition are the same, and APL's rule holds in BQN.

+

Axis permutations of the types we've shown generate the complete permutation group on any number of axes, so you could produce any transposition you want with the right sequence of monadic transpositions with Rank. However, this can be unintuitive and tedious. What if you want to transpose the first three axes, leaving the rest alone? With monadic Transpose you have to send some axes to the end, then bring them back to the beginning. For example [following four or five failed tries]:

+
    ≢ ⍉⁼⎉¯2 ⍉ a23456  # Restrict Transpose to the first three axes
+[ 3 4 2 5 6 ]
+
+

In a case like this BQN's Dyadic transpose is much easier.

+

Dyadic Transpose

+

Transpose also allows a left argument that specifies a permutation of the right argument's axes. For each index p←i⊏𝕨 in the left argument, axis i of the argument is used for axis p of the result. Multiple argument axes can be sent to the same result axis, in which case that axis goes along a diagonal of the argument array, and the result will have a lower rank than the argument.

+
    ≢ 1‿3‿2‿0‿4 ⍉ a23456
+[ 5 2 4 3 6 ]
+    ≢ 1‿2‿2‿0‿0 ⍉ a23456  # Don't worry too much about this case though
+[ 5 2 3 ]
+
+

Since this kind of rearrangement can be counterintuitive, it's often easier to use ⍉⁼ when specifying all axes. If p≡○≠≢a, then we have ≢p⍉⁼a ←→ p⊏≢a.

+
    ≢ 1‿3‿2‿0‿4 ⍉⁼ a23456
+[ 3 5 4 2 6 ]
+
+

So far, all like APL. BQN makes one little extension, which is to allow only some axes to be specified. The left argument will be matched up with leading axes of the right argument. Those axes are moved according to the left argument, and remaining axes are placed in order into the gaps between them.

+
    ≢ 0‿2‿4 ⍉ a23456
+[ 2 5 3 6 4 ]
+
+

In particular, the case with only one argument specified is interesting. Here, the first axis ends up at the given location. This gives us a much better solution to the problem at the end of the last section.

+
    ≢ 2 ⍉ a23456  # Restrict Transpose to the first three axes
+[ 3 4 2 5 6 ]
+
+

Finally, it's worth noting that, as monadic Transpose moves the first axis to the end, it's equivalent to dyadic Transpose with a "default" left argument: (≠∘≢-1˜)⊸⍉.

+

Definitions

+

Here we define the two valences of Transpose more precisely.

+

A non-array right argument to Transpose is always boxed to get a scalar array before doing anything else.

+

Monadic transpose is identical to (≠∘≢-1˜)⊸⍉, except that for scalar arguments it returns the array unchanged rather than giving an error.

+

In Dyadic transpose, the left argument is a number or numeric array of rank 1 or less, and 𝕨≤○≠≢𝕩. Define the result rank r←(≠≢𝕩)-+´¬∊𝕨 to be the argument rank minus the number of duplicate entries in the left argument. We require ∧´𝕨<r. Bring 𝕨 to full length by appending the missing indices: 𝕨∾↩𝕨(¬∘∊˜/⊢)↕r. Now the result shape is defined to be ⌊´¨𝕨⊔≢𝕩. Element i⊑z of the result z is element (𝕨⊏i)⊑𝕩 of the argument.

+ diff --git a/docs/doc/windows.html b/docs/doc/windows.html new file mode 100644 index 00000000..117acc08 --- /dev/null +++ b/docs/doc/windows.html @@ -0,0 +1,90 @@ + +

Windows

+

In BQN, it's strongly preferred to use functions, and not operators (modifiers and compositions), for array manipulation. Functions are simpler as they have fewer moving parts. They are more concrete, since the array results can always be viewed right away. They are easier to implement with reasonable performance as well, since there is no need to recognize many possible function operands as special cases.

+

The Window function replaces APL's Windowed Reduction, J's more general Infix operator, and Dyalog's Stencil, which is adapted from one case of J's Cut operator.

+

Definition

+

We'll start with the one-axis case. Here Window's left argument is a number between 0 and 1+≠𝕩. The result is composed of slices of 𝕩 (contiguous sections of major cells) with length 𝕨, starting at each possible index in order.

+
    5↕"abcdefg"
+┌
+  abcde
+  bcdef
+  cdefg
+        ┘
+
+

There are 1+(≠𝕩)-𝕨, or (≠𝕩)¬𝕨, of these sections, because the starting index must be at least 0 and at most (≠𝕩)-𝕨. Another way to find this result is to look at the number of cells in or before a given slice: there are always 𝕨 in the slice and there are only ≠𝕩 in total, so the number of slices is the range spanned by these two endpoints.

+

You can take a slice of an array 𝕩 that has length l and starts at index i using l↑i↓𝕩 or l↑i⌽𝕩. The Prefixes function returns all the slices that end at the end of the array ((≠𝕩)=i+l), and Suffixes gives the slices that start at the beginning (i=0). Windows gives yet another collection of slices: the ones that have a fixed length l=𝕨. Selecting one cell from its result gives you the slice starting at that cell's index:

+
    2⊏5↕"abcdefg"
+[ cdefg ]
+    5↑2↓"abcdefg"
+[ cdefg ]
+
+

Windows differs from Prefixes and Suffixes in that it doesn't add a layer of nesting (it doesn't box each slice). This is possible because the slices have a fixed size.

+

Multiple dimensions

+

The above description applies to a higher-rank right argument. As an example, we'll look at two-row slices of a shape 3‿4 array. For convenience, we will box each slice. Note that slices always have the same rank as the argument array.

+
    <⎉2 2↕"0123"∾"abcd"≍"ABCD"
+┌
+  ┌        ┌
+    0123     abcd
+    abcd     ABCD
+         ┘        ┘
+                    ┘
+
+

Passing a list as the left argument to Windows takes slices along any number of leading axes. Here are all the shape 2‿2 slices:

+
    <⎉2 2‿2↕"0123"∾"abcd"≍"ABCD"
+┌
+  ┌      ┌      ┌
+    01     12     23
+    ab     bc     cd
+       ┘      ┘      ┘
+  ┌      ┌      ┌
+    ab     bc     cd
+    AB     BC     CD
+       ┘      ┘      ┘
+                       ┘
+
+

The slices are naturally arranged along multiple dimensions according to their starting index. Once again the equivalence i⊏l↕x ←→ l↑i↓x holds, provided i and l have the same length.

+

If the left argument has length 0, then the argument is not sliced along any dimensions. The only slice that results—the entire argument—is then arranged along an additional zero dimensions. In the end, the result is the same as the argument.

+

More formally

+

𝕩 is an array. 𝕨 is a number or numeric list or scalar with 𝕨≤○≠≢𝕩. The result z has shape 𝕨∾¬⟜𝕨⌾((≠𝕨)⊸↑)≢𝕩, and element i⊑z is 𝕩⊑˜(≠𝕨)(↑+⌾((≠𝕨)⊸↑)↓)i.

+

Using Group we could also write i⊑z ←→ 𝕩⊑˜(𝕨∾○(↕∘≠)≢𝕩) +´¨∘⊔ i.

+

Symmetry

+

Let's look at an earlier example, along with its transpose.

+
    {⟨𝕩,⍉𝕩⟩}5↕"abcdefg"
+┌
+  ┌         ┌
+    abcde     abc
+    bcdef     bcd
+    cdefg     cde
+          ┘   def
+              efg
+                  ┘
+                    ┘
+
+

Although the two arrays have different shapes, they are identical where they overlap.

+
    ≡○(3‿3⊸↑)⟜⍉5↕"abcdefg"
+1
+
+

In other words, the i'th element of slice j is the same as the j'th element of slice i: it is the i+j'th element of the argument. So transposing still gives a possible result of Windows, but with a different slice length.

+
    {(5↕𝕩)≡⍉(3↕𝕩)}"abcdefg"
+1
+
+

In general, we need a more complicated transpose—swapping the first set of ≠𝕨 axes with the second set. Note again the use of Span, our slice-length to slice-number converter.

+
    {((5‿6¬2‿2)↕𝕩) ≡ 2‿3⍉(2‿2↕𝕩)} ↕5‿6‿7
+1
+
+

Applications

+

Windows can be followed up with a reduction on each slice to give a windowed reduction. Here we take running sums of 3 values.

+
    +´˘3↕ ⟨2,6,0,1,4,3⟩
+[ 8 7 5 8 ]
+
+

A common task is to pair elements, with an initial or final element so the total length stays the same. This can also be done with a pairwise reduction, but another good way (and more performant without special support in the interpreter) is to add the element and then use windows matching the original length. Here both methods are used to invert +`, which requires we take pairwise differences starting at initial value 0.

+
    -˜´˘2↕0∾ +` 3‿2‿1‿1
+[ 3 2 1 1 ]
+    ((-˜´<˘)≠↕0∾⊢) +` 3‿2‿1‿1
+[ 3 2 1 1 ]
+
+

This method extends to any number of initial elements. We can modify the running sum above to keep the length constant by starting with two zeros.

+
    ((+´<˘)≠↕(2⥊0)⊸∾) ⟨2,6,0,1,4,3⟩
+[ 2 8 8 7 5 8 ]
+
+ diff --git a/docs/fromDyalog.html b/docs/fromDyalog.html deleted file mode 100644 index 859e3c46..00000000 --- a/docs/fromDyalog.html +++ /dev/null @@ -1,205 +0,0 @@ - -

BQN–Dyalog APL dictionary

-

A few tables to help users of Dyalog APL (or similar) get started quickly on BQN. Here we assume ⎕ML is 1 for Dyalog.

-

For reading

-

Here are some closest equivalents in Dyalog APL for the BQN functions that don't use the same glyphs as APL. Correspondence can be approximate, and ⌽ is just used as a decorator to mean "reverse some things".

- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
BQN⋆√∧∨¬≠<>≢⥊∾≍
Monad**∘(÷2)[⍋][⍒]~≢⊂↑⍴,⊃,⌿↑,⍥⊂
Dyad**∘÷⍨∧∨1+-≠<>≢⍴⍪↑,⍥⊂
- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
BQN↑↓↕/⍋⍒⊏⊑⊐⊒∊⍷⊔
Monad,⍀⌽,⌽⍀⌽⍳⍸⍋⍒⊣⌿⊃…≠∪⌸
Dyad↑↓,⌿⌿⍸⌽⍸⌽⌷⊃⍳…∊⍷⌸ or ⊆
-

Modifiers and combinators are a little harder. Many have equivalents in some cases, but Dyalog sometimes chooses different functionality based on whether the operand is an array. In BQN an array is always treated as a constant function.

- - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
BQN¨⌜´⎉⍟˜∘○⟜
Dyalog¨∘.⌿⍤⍣⍨⍤⍥∘
-

In BQN ⎉ is Rank and ∘ is Atop. Dyalog's Atop (⍤) and Over (⍥) were added in version 18.0.

-

For writing

-

The tables below give approximate implementations of Dyalog primitives for the ones that aren't the same. First- and last-axis pairs are also mostly omitted. BQN just has the first-axis form, and you can get the last-axis form with ⎉1.

- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
Functions
Glyph Monadic Dyadic
* ⋆
⍟ ⋆⁼
! Implement it yourself
○ Some complex exponential stuff, maybe
~ ¬ ¬∘∊/⊣
? Library?
⍲ ¬∘∧
⍱ ¬∘∨
⍴ ≢ ⥊
, ⥊ ∾⎉1
⍪ ⥊˘ ∾
↑ > ↑
↓ <˘ ↑
⊂ < +`⊸⊔
⊆ <⍟(0<≡) ⊔
∊ {0=≡𝕩:⥊𝕩⋄∾⥊∇¨𝕩} ∊
⊃ ⊑
⍀ /⁼
∩ ∊/⊣
∪ ⍷ ⊣∾∊˜¬⊸/⊢
⍳ ↕ ⊐
⍸ / ⍋
⍋ ⍋ Give up
⍒ ⍒ Give up
≢ ≠ ≢
⍎ To be decided
⍕
⊥ {+⟜(𝕨⊸×)´⌽𝕩}
⊤ {𝕨|1↓⌊∘÷`⌾⌽𝕨∾<𝕩}
⌹ +´∘×⎉1‿∞⁼ I guess
⌷ N/A ⊏
- - - - - - - - - - - - - - - - - - - - - - - -
Operators
Syntax Monadic Dyadic
⌿ ´ ↕
⍀ ↑ or `
¨ ¨
⍨ ˜
⍣ ⍟
f.g f´∘g⍟1‿∞
∘.f f⌜
A∘g A⊸g
f∘B f⟜B
f∘g f⟜g
f⍤B f⎉B
f⍤g f∘g
f⍥g f○g
f@v f⌾(v⊸⊏)
f⍠B Uh
f⌸ ⍷⊸⊐⊔↕∘≠⍷⊸⊐⊸⊔
f⌺B ↕
A⌶ •
f& Nothing yet
- - diff --git a/docs/functional.html b/docs/functional.html deleted file mode 100644 index 123338f9..00000000 --- a/docs/functional.html +++ /dev/null @@ -1,74 +0,0 @@ - -

Functional programming

-

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.

-

Traditionally APL has worked around its lack of first-class functions with operators or 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.

-

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, two 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.

-

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 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 ⎕ORs even share a form of BQN's 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 ⎕ORs, so they don't work very well as a first-class function mechanism.

-

Another reason for APL's reluctance to adopt first-class functions is that Iverson and others seemed to believe that functions fundamentally are not a kind of data, because it's impossible to uniquely represent, compare, and order them. One effect of this viewpoint is J's gerund mechanism, which converts a function to an array representation, primarily so that lists of gerunds can be created. Gerunds are nested arrays containing character vectors at the leaves, so they are arrays as Iverson thought of them. However, I consider this conversion of functions to arrays, intended to avoid arrays that contain "black box" functions, to be a mistake: while it doesn't compromise the purity of arrays, it gives the illusion that a function corresponds to a particular array, which is not true from the mathematical perspective of functions as mappings from an arbitrary input to an output. I also think the experience of countless languages with first-class functions shows that there is no practical issue with arrays that contain functions. While having all arrays be concrete entities with a unique canonical representation seems desirable, I don't find the existence of arrays without this property to be detract from working with arrays that do have it.

-

Functional programming in BQN

-

Reminder: I am discussing only first-class functional programming here, and not other concepts like pure or typed functional programming!

-

What does functional programming in BQN look like? How is it different from the typical APL style of manipulating functions with operators?

-

Working with roles

-

First, let's look at the basics: a small program that takes a function as its argument and result. The function Lin below gives a linear approximation to its function argument based on the values at 0 and 1. To find these two values, we call the argument as a function by using its uppercase spelling, 𝕏.

-
Lin ← {
-  v0 ← 𝕏 0
-  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 value role). The result is a train that adds 1 to e-1 times the argument.

-
    Exp ← ⋆
-    Lin exp
-(1 + (1.71828182845905 × ⊢))
-
-

As with all functions, the result of Lin has a value role. To use it as a function, we give it a name and then use that name with an uppercase spelling.

-
    expLin ← Lin exp
-    ExpLin 5
-9.59140914229523
-
-

A tricker but more compact method is to use the modifier {𝔽}, as the input to a modifier can have a value or function role but its output always has a function role.

-
    (Lin exp){𝔽} 5
-9.59140914229523
-
-

Not the most accurate approximation, though.

-
    Exp 5
-148.413159102577
-
-

Note also in this case that we could have used a modifier with a very similar definition to Lin. The modifier is identical in definition except that 𝕏 is replaced with 𝔽.

-
_lin ↩ {
-  v0 ← 𝔽 0
-  v0 + ((𝔽 1) - v0) × ⊢
-}
-
-

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.

-
    Exp _lin 5
-9.59140914229523
-
-

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 values. Here's an example of an array of functions with a reduction applied to it, composing them together.

-
    {𝕎∘𝕏}´ ⋆‿-‿(ט)
-⋆∘(-∘(ט))
-
-

Like any function, this one can be given a name and then called. A quirk of this way of defining a function is that it has a value role (it's the result of the function {𝕎∘𝕏}´) and so must be defined with a lowercase name.

-
    gauss ← {𝕎∘𝕏}´ ⋆‿-‿(ט)
-    Gauss 2
-0.0183156388887342
-
-

Another, and probably more common, use of arrays of functions is to apply several different functions to one or more arguments. Here we apply three different functions to the number 9:

-
    ⟨√, 2⊸∾, ⊢-⋆⟩ {𝕎𝕩}¨ 9
-[ 3 [ 2 9 ] ¯8094.083927575384 ]
-
-

The composition Choose (◶) relies on arrays of functions to… function. It's very closely related to Pick ⊑, and in fact when the left operand and the elements of the right operand are all value types there's no real difference: Choose returns the constant function 𝕗⊑𝕘.

-
    2◶"abcdef" "arg"
-c
-
-

When the operands contain functions, however, the potential of Choose as a ternary-or-more operator opens up. Here's a function for a step in the Collatz sequence, which halves an even input but multiplies an odd input by 3 and adds 1. To get the sequence for a number, we can apply the same function many times. It's an open problem whether the sequence always ends with the repetition 4, 2, 1, but it can take a surprisingly long time to get there—try 27 as an argument.

-
    (2⊸|)◶⟨÷⟜2,1+3×⊢⟩¨ 6‿7
-[ 3 22 ]
-    (2⊸|)◶⟨÷⟜2,1+3×⊢⟩⍟(↕10) 6
-[ 6 3 10 5 16 8 4 2 1 4 ]
-
- diff --git a/docs/group.html b/docs/group.html deleted file mode 100644 index feaf361d..00000000 --- a/docs/group.html +++ /dev/null @@ -1,152 +0,0 @@ - -

Group

-

BQN replaces the Key operator from J or Dyalog APL, and many forms of partitioning, 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.

-

The BQN prototype does not implement this function: instead it uses ⊔ for a Group/Key function very similar to {⊂⍵}⌸ in Dyalog APL, and also has a Cut function \. The new BQN Group on numeric arguments (equivalently, rank-1 results) can be defined like this:

-
⊔↩((↕1+(>⌈´))=¨<)∘⊣ /¨⟜< ↕∘≠⍠⊢
-
-

Once defined, the old BQN Key (dyadic) is ⍷⊸⊐⊸⊔ and Group (monadic) is ⍷⊸⊐⊔↕∘≠ using the Deduplicate or Unique Cells function ⍷ (BQN2NGN spells it ∪). Cut on matching-length arguments is +`⊸⊔.

-

Definition

-

Group operates on a numeric list of indices and a value array, treated as a list of its major cells, to produce a list of groups, each of which is a selection from the values. The indices and values have the same length, and each value cell is paired with the index at the same position. That index indicates the result group the value should go into, with an "index" of ¯1 indicating that it should be dropped and not appear in the result.

-
    0‿1‿2‿0‿1 ≍ "abcde"  # Corresponding indices and values
-┌
-  0 1 2 0 1
-  a b c d e
-            ┘
-    0‿1‿2‿0‿1 ⊔ "abcde"  # Values grouped by index
-[ [ ad ] [ be ] [ c ] ]
-
-

For example, we might choose to group a list of words by length. Within each group, values maintain the ordering they had in the list originally.

-
    phrase ← "BQN"‿"uses"‿"notation"‿"as"‿"a"‿"tool"‿"of"‿"thought"
-    ⥊˘ ≠¨⊸⊔ phrase
-┌
-  []
-  [ [ a ] ]
-  [ [ as ] [ of ] ]
-  [ [ BQN ] ]
-  [ [ uses ] [ tool ] ]
-  []
-  []
-  [ [ thought ] ]
-  [ [ notation ] ]
-                        ┘
-
-

(Could we define phrase more easily? See below.)

-

If we'd like to ignore words of 0 letters, or more than 5, we can set all word lengths greater than 5 to 0, then reduce the lengths by 1. Two words end up with left argument values of ¯1 and are omitted from the result.

-
    1-˜≤⟜5⊸×≠¨phrase
-[ 2 3 ¯1 1 0 3 1 ¯1 ]
-    ⥊˘ {1-˜≤⟜5⊸×≠¨𝕩}⊸⊔ phrase
-┌
-  [ [ a ] ]
-  [ [ as ] [ of ] ]
-  [ [ BQN ] ]
-  [ [ uses ] [ tool ] ]
-                        ┘
-
-

Note that the length of the result is determined by the largest index. So the result never includes trailing empty groups. A reader of the above code might expect 5 groups (lengths 1 through 5), but there are no words of length 5, so the last group isn't there.

-

When Group is called dyadically, the left argument is used for the indices and the right is used for values, as seen above. When it is called monadically, the right argument gives the indices and the values grouped are the right argument's indices, that is, ↕≠𝕩.

-
    ⥊˘ ⊔ 2‿3‿¯1‿2
-┌
-  []
-  []
-  [ [ 0 ] [ 3 ] ]
-  [ [ 1 ] ]
-                  ┘
-
-

Here, the index 2 appears at indices 0 and 3 while the index 3 appears at index 1.

-

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 vector of numeric vectors, 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.

-

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.

-
    ⟨0‿0‿1‿1,0‿1‿0‿1‿0‿1‿0⟩⊔(10×↕4)+⌜↕7
-┌
-  ┌               ┌
-     0  2  4  6      1  3  5
-    10 12 14 16     11 13 15
-                ┘            ┘
-  ┌               ┌
-    20 22 24 26     21 23 25
-    30 32 34 36     31 33 35
-                ┘            ┘
-                               ┘
-
-

Each group i⊑𝕨⊔𝕩 is composed of the cells j<¨⊸⊏𝕩 such that i≢j⊑¨𝕨. The groups retain their array structure and ordering along each argument axis. Using multidimensional Replicate we can say that i⊑𝕨⊔𝕩 is (i=𝕨)/𝕩.

-

The monadic case works similarly: Group Indices always satisfies ⊔𝕩 ←→ 𝕩⊔↕≠⚇1 x. As with ↕, the depth of the result of Group Indices is always one greater than that of its argument. A depth-0 argument is not allowed.

-

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:

-
    ≠¨⊔ 2‿3‿1‿2
-[ 0 1 2 1 ]
-    /⁼∧ 2‿3‿1‿2
-[ 0 1 2 1 ]
-
-

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.

-
    /≠¨⊔ 2‿3‿1‿¯1‿2
-[ 1 2 2 3 ]
-
-

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.

-
    ∾ 2‿3‿1‿¯1‿2 ⊔ "abcde"
-[ caeb ]
-    2‿3‿1‿¯1‿2 {F←(0≤𝕨)⊸/ ⋄ 𝕨⍋⊸⊏○F𝕩} "abcde"
-[ caeb ]
-
-

Group can even be implemented with the same techniques as a bucket sort, which can be 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 Unique and Index Of (the combination ⍷⊸⊐ has been called "self-classify").

-
    ln ← "Phelps"‿"Latynina"‿"Bjørgen"‿"Andrianov"‿"Bjørndalen"
-    co ← "US"    ‿"SU"      ‿"NO"     ‿"SU"       ‿"NO"
-    ⥊˘ co ⍷⊸⊐⊸⊔ ln
-┌
-  [ [ Phelps ] ]
-  [ [ Latynina ] [ Andrianov ] ]
-  [ [ Bjørgen ] [ Bjørndalen ] ]
-                                 ┘
-
-

If we would like a particular index to key correspondence, we can use a fixed left argument to Index Of.

-
    countries ← "IT"‿"JP"‿"NO"‿"SU"‿"US"
-    countries ∾˘ co countries⊸⊐⊸⊔ ln
-┌
-  [ IT ] []
-  [ JP ] []
-  [ NO ] [ [ Bjørgen ] [ Bjørndalen ] ]
-  [ SU ] [ [ Latynina ] [ Andrianov ] ]
-  [ US ] [ [ Phelps ] ]
-                                        ┘
-
-

However, this solution will fail if there are trailing keys with no values. To force the result to have a particular length you can append that length as a dummy index to each argument, then remove the last group after grouping.

-
    countries ↩ "IT"‿"JP"‿"NO"‿"SU"‿"US"‿"ZW"
-    countries ∾˘ co countries{𝕗⊸⊐⊸(¯1↓⊔○(∾⟜(≠𝕗)))} ln
-┌
-  [ IT ] []
-  [ JP ] []
-  [ NO ] [ [ Bjørgen ] [ Bjørndalen ] ]
-  [ SU ] [ [ Latynina ] [ Andrianov ] ]
-  [ US ] [ [ Phelps ] ]
-  [ ZW ] []
-                                        ┘
-
-

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.

-
    ' '(+`∘=⊔⊢)"BQN uses notation as a tool of thought"
-[ [ BQN ] [  uses ] [  notation ] [  as ] [  a ] [  tool ] [  of ] [  thought ] ]
-
-

To avoid including spaces in the result, we should change the result index at each space to ¯1. Here is one way to do that:

-
    ' '((⊢-˜¬×+`)∘=⊔⊢)"BQN uses notation as a tool of thought"
-[ [ BQN ] [ uses ] [ notation ] [ as ] [ a ] [ tool ] [ of ] [ thought ] ]
-
-

A function with structural Under, such as {¯1¨⌾(𝕩⊸/)+`𝕩}, would also work.

-

In other cases, we might want to split on spaces, so that words are separated by any number of spaces, and extra spaces don't affect the output. Currently our function makes a new word with each space:

-
    ' '((⊢-˜¬×+`)∘=⊔⊢)"  string with  spaces   "
-[ [] [] [ string ] [ with ] [] [ spaces ] ]
-
-

However, trailing spaces are ignored because Group never produces trailing empty groups (to get them back we would use a dummy final character in the string). To avoid empty words, 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 Windows function. We will extend our list with an initial 1 so that leading spaces will be ignored. Then we take windows of the same length as the original list: the first includes the dummy argument followed by a shifted copy of the list, and the second is the original list. These represent whether the previous and current characters are spaces; we want positions where the previous wasn't a space and the current is.

-
    ≍⟜((<´<˘)≠↕1∾⊢) ' '="  string with  spaces   "  # All, then filtered, spaces
-┌
-  1 1 0 0 0 0 0 0 1 0 0 0 0 1 1 0 0 0 0 0 0 1 1 1
-  0 0 0 0 0 0 0 0 1 0 0 0 0 1 0 0 0 0 0 0 0 1 0 0
-    ≍⟜(⊢-˜¬×+`∘((<´<˘)≠↕1∾⊢))' '="  string with  spaces   "  # More processing
-┌
-   1  1 0 0 0 0 0 0  1 0 0 0 0  1  1 0 0 0 0 0 0  1  1  1
-  ¯1 ¯1 0 0 0 0 0 0 ¯1 1 1 1 1 ¯1 ¯1 2 2 2 2 2 2 ¯1 ¯1 ¯1
-                                                          ┘
-    ' '((⊢-˜¬×+`∘((<´<˘)≠↕1∾⊢))∘=⊔⊢)"  string with  spaces   "  # Final result
-[ [ string ] [ with ] [ spaces ] ]
-
- diff --git a/docs/indices.html b/docs/indices.html deleted file mode 100644 index 86af51be..00000000 --- a/docs/indices.html +++ /dev/null @@ -1,100 +0,0 @@ - -

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, 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 (depth 0) indices, which can refer to vector elements or array major cells (or more generally indexing along any particular axis). When using this kind of element indices, arrays are required to be vectors. Only two functions allow the use of vector element indices: Range (↕), which can accept a vector argument, and Pick (⊑), which uses the depth-1 arrays in its left argument as index scalars or vectors.

-

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 return type of indices is as useful as possible.

- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
MonadDyadWhereHow
↕Element scalar or vector
/Element scalar
⊔Element scalar
⊔⊔𝕨/𝕩Along-axis scalar
⊑𝕨Element vector
⍋⍋Major cell scalar
⍒⍒Major cell scalar
⊐Major cell scalar
⊒Major cell scalar
⊏𝕨Major cell or along-axis scalar
⍉Axis scalar
-

Dyadic Transpose (⍉) takes an index into the right argument axes as its left argument, but since array shape is 1-dimensional, there is only one sensible choice for this, a single number.

-

Element indices

-

In general, the index of an element of an array is a vector whose length matches the array rank. It is also possible to use a number for an index into a vector, as the vector 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 vector 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 vector indices. However, this usually rules out the possibility of using scalar 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 depth-0 indices, which comes with the requirement that the arguments to monadic / and ⊔, and the result of monadic ⊔, must be vectors. For dyadic ⊔ the depth-1 elements of the left argument are vectors of indices along axes of the result; see the documentation. 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 prevents Group from having to use an ordering on vector indices.

-

Unlike / and ⊔, ↕ and ⊑ do use vector element indices. For ↕ this is because the output format can be controlled by the argument format: if passed a single number, the result uses single-number indices (so it's a numeric vector); if passed a vector, it uses vector indices and the result has depth 2 (the result depth is always one greater than the argument depth). For ⊑, vector indices are chosen because ⊏ handles scalar indices well already. When selecting multiple elements from a vector, they would typically have to be placed in an array, which is equivalent to ⊏ with a numeric vector left argument. A single scalar index to ⊑ is converted to a vector, 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 scalars or higher-rank arrays allowed. Single numbers also cannot be used in this context, as it would create ambiguity: is a one-element vector an index, or does it contain an index?

-

Major cell indices

-

One of the successes of the leading axis model is to introduce a kind of index for multidimensional arrays that is easier to work with than vector indices. The model introduces cells, where a cell index is a vector 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.

-

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.

-

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 vector of depth-1 elements. In each case the depth-1 arrays index into a single axis.

-

General cell indices

-

BQN does not use general cell indices directly, but it is useful to consider how they might work, and how a programmer might implement functions that use them in BQN if needed. The functions /, ⊔, and ⊏ are the ones that can work with indices for multidimensional arrays but don't already. Here we will examine how multidimensional versions would work.

-

A cell index into an array of rank r is a numeric vector of length l≤r, which then refers to a cell of rank r-l. In BQN, the cell at index i of array a is i<¨⊸⊏a.

-

Because the shape of a cell index relates to the shape of the indexed array, it makes sense not to enclose cell indices, instead treating them as rows of an index array. A definition for ⊏ for depth-1 left arguments of rank at least 1 follows: replace each row of the left argument with the indexed cell of the right, yielding a result with the same depth as the right argument and shape 𝕨((¯1↓⊣)∾(¯1↑⊣)⊸↓)○≢𝕩.

-

To match this format, Range (↕) could be changed to return a flat array when given a shape—what is now >↕. Following this pattern, Indices (/) would also return a flat array, where the indices are rows: using the modified Range, ⥊/↕∘≢. Here the result cannot retain the argument's array structure; it is always a rank-2 list of rows.

-

The most interesting feature would be that ⊏ could still allow a nested left argument. In this case each element of the left argument would be an array with row indices as before. However, each row can now index along multiple axes, allowing some adjacent axes to be dependent while others remain independent. This nicely unifies scatter-point and per-axis selection, and allows a mix of the two. However, it doesn't allow total freedom, as non-adjacent axes can't be combined except by also mixing in all axes in between.

-

Group (⊔) could accept the same index format for its index argument. Each depth-1 array in the left argument would correspond to multiple axes in the outer result array, but only a single axis in the argument and inner arrays. Because the ravel ordering of indices must be used to order cells of inner arrays, this modification is not quite as clean as the change to Select. It's also not so clearly useful, as the same results can be obtained by using numeric indices and reshaping the result.

-

Overall it seems to me that the main use of cell indices of the type discussed here is for the Select primitive, and the other cases are somewhat contrived an awkward. So I've chosen not to support it in BQN at all.

- diff --git a/docs/join.html b/docs/join.html deleted file mode 100644 index e54d2a4f..00000000 --- a/docs/join.html +++ /dev/null @@ -1,38 +0,0 @@ - -

Join

-

Join (∾) is an extension of the monadic function Raze from A+ and J to arbitrary argument ranks. It has the same relationship to Join to, the dyadic function sharing the same glyph, as Unbox (>) does to Couple (≍): a≍b is >a‿b and a∾b is ∾a‿b. While Unbox and Couple combine arrays (the elements of Unbox's argument, or the arguments themselves for Coups) along a new leading axis, Join and Join to combine them along the existing leading axis. Both Unbox and Join can also be called on a higher-rank array, causing Unbox to add multiple leading axes while Join combines elements along multiple existing axes.

-

Join can be used to combine several strings into a single string, like array.join() in Javascript (but it doesn't force the result to be a string).

-
    ∾"time"‿"to"‿"join"‿"some"‿"words"
-[ timetojoinsomewords ]
-
-

To join with a separator in between, we might prepend the separator to each string, then remove the leading separator after joining. Another approach would be to insert the separator array as an element between each pair of array elements before calling Join.

-
    1↓∾' '∾¨"time"‿"to"‿"join"‿"some"‿"words"
-[ time to join some words ]
-
-

Join requires each element of its argument to be an array, and their ranks to match exactly. No rank extension is performed.

-
    ∾"abc"‿'d'‿"ef"  # Includes a non-array
-RANK ERROR
-    ∾"abc"‿(<'d')‿"ef"  # Includes a scalar
-RANK ERROR
-
-

However, Join has higher-dimensional uses as well. Given a rank-m array of rank-n arrays (requiring m≤n), it will merge arrays along their first m axes. For example, if the argument is a matrix of matrices representing a block matrix, Join will give the corresponding unblocked matrix as its result.

-
    ⊢ m ← (3‿1∾⌜4‿2‿5) ⥊¨ 2‿3⥊↕6
-┌
-  ┌           ┌       ┌
-    0 0 0 0     1 1     2 2 2 2 2
-    0 0 0 0     1 1     2 2 2 2 2
-    0 0 0 0     1 1     2 2 2 2 2
-            ┘       ┘             ┘
-  [ 3 3 3 3 ] [ 4 4 ] [ 5 5 5 5 5 ]
-                                    ┘
-    ∾ m  # Join all that together
-┌
-  0 0 0 0 1 1 2 2 2 2 2
-  0 0 0 0 1 1 2 2 2 2 2
-  0 0 0 0 1 1 2 2 2 2 2
-  3 3 3 3 4 4 5 5 5 5 5
-                        ┘
-
-

Join has fairly strict requirements on the shapes of its argument elements—although less strict than those of Unbox, which requires they all have identical shape. Suppose the argument to Join has rank m. Each of its elements must have the same rank, n, which is at least m. The trailing shapes m↓⟜≢¨𝕩 must all be identical (the trailing shape m↓≢∾𝕩 of the result will match these shapes as well). The other entries in the leading shapes need not be the same, but the shape of an element along a particular axis must depend only on the location of the element along that axis in the full array. For a vector argument this imposes no restriction, since the one leading shape element is allowed to depend on position along the only axis. But for higher ranks the structure quickly becomes more rigid.

-

To state this requirement more formally in BQN, we say that there is some vector s of length vectors, so that (≢¨s)≡≢𝕩. We require element i⊑𝕩 to have shape i⊑¨s. Then the first m axes of the result are +´¨s.

- diff --git a/docs/logic.html b/docs/logic.html deleted file mode 100644 index 8969a7c7..00000000 --- a/docs/logic.html +++ /dev/null @@ -1,42 +0,0 @@ - -

Logic functions: And, Or, Not (also Span)

-

BQN retains the APL symbols ∧ and ∨ for logical and and or, and changed APL's ~ to ¬ for not, since ~ looks too much like ˜ and ¬ is more common in mathematics today. Like J, BQN extends Not to the linear function 1⊸-. However, it discards GCD and LCM as extensions of And and Or, and instead uses bilinear extensions: And is identical to Times (×), while Or is ×⌾¬, following De Morgan's laws (other ways of obtaining a function for Or give an equivalent result—there is only one bilinear extension).

-

If the arguments are probabilities of independent events, then an extended function gives the probability of the boolean function on their outcomes (for example, if A occurs with probability a and B with probability b independent of A, then A or B occurs with probability a∨b). These extensions have also been used in complexity theory, because they allow mathematicians to transfer a logical circuit from the discrete to the continuous domain in order to use calculus on it.

-

Both valences of ¬ are equivalent to the fork 1+-. The dyadic valence, called "Span", computes the number of integers in the range from 𝕩 to 𝕨, inclusive, when both arguments are integers and 𝕩≤𝕨 (note the reversed order, which is used for consistency with subtraction). This function has many uses, and in particular is relevant to the Windows function.

-

Definitions

-

We define:

-
Not ← 1+-  # also Span
-And ← ×
-Or  ← ×⌾¬
-
-

Note that ¬⁼ ←→ ¬, since the first added 1 will be negated but the second won't; the two 1s cancel leaving two subtractions, and -⁼ ←→ -. An alternate definition of Or that matches the typical formula from probability theory is

-
Or  ← +-×
-
-

Examples

-

We can form truth tables including the non-integer value one-half:

-
    ¬ 0‿0.5‿1
-[ 1 0.5 0 ]
-
-    ∧⌜˜ 0‿0.5‿1
-┌
-  0    0   0
-  0 0.25 0.5
-  0  0.5   1
-             ┘
-
-    ∨⌜˜ 0‿0.5‿1
-┌
-    0  0.5 1
-  0.5 0.75 1
-    1    1 1
-             ┘
-
-

As with logical And and Or, any value and 0 is 0, while any value or 1 is 1. The other boolean values give the identity elements for the two functions: 1 and any value gives that value, as does 0 or the value.

-

Why not GCD and LCM?

-

The main reason for omitting these functions is that they are complicated and, when applied to real or complex numbers, require a significant number of design decisions where there is no obvious choice (for example, whether to use comparison tolerance). On the other hand, these functions are fairly easy to implement, which allows the programmer to control the details, and also add functionality such as the extended GCD.

-

A secondary reason is that the GCD falls short as an extension of Or, because its identity element 0 is not total. 0∨x, for a real number x, is actually equal to |x and not x: for example, 0∨¯2 is 2 in APL. This means the identity 0∨x ←→ x isn't reliable in APL.

-

Identity elements

-

It's common to apply ∧´ or ∨´ to a list (checking whether all elements are true and whether any are true, respectively), and so it's important for extensions to And and Or to share their identity element. Minimum and Maximum do match And and Or when restricted to booleans, but they have different identity elements. It would be dangerous to use Maximum to check whether any element of a list is true because >⌈´⟨⟩ yields ¯∞ instead of 0—a bug waiting to happen. Always using 0 as a left argument to ⌈´ fixes this problem but requires more work from the programmer, making errors more likely.

-

It is easy to prove that the bilinear extensions have the identity elements we want. Of course 1∧x is 1×x, or x, and 0∨x is 0×⌾¬x, or ¬1׬x, giving ¬¬x or x again. Both functions are commutative, so these identities are double-sided.

-

Other logical identities do not necessarily hold. For example, in boolean logic And distributes over Or and vice-versa: a∧b∨c ←→ (a∧b)∨(a∧c). But substituting × for ∧ and +-× for ∨ we find that the left hand side is (a×b)+(a×c)+(a×b×c) while the right gives (a×b)+(a×c)+(a×b×a×c). These are equivalent for arbitrary b and c only if a=a×a, that is, a is 0 or 1. In terms of probabilities the difference when a is not boolean is caused by failure of independence. On the left hand side, the two arguments of every logical function are independent. On the right hand side, each pair of arguments to ∧ are independent, but the two arguments to ∨, a∧b and a∧c, are not. The relationship between these arguments means that logical equivalences no longer apply.

- diff --git a/docs/running.html b/docs/running.html new file mode 100644 index 00000000..9e30492d --- /dev/null +++ b/docs/running.html @@ -0,0 +1,20 @@ + +

How to run BQN

+

BQN is in a very early stage of development, and there is currently no complete implementation of the language. However, it's a relatively simple language to implement, and a few implementations come close.

+

BQN2NGN

+

BQN2NGN is a prototype implementation in Javascript build to experiment with the langauge, which is now abandoned. Because you can use it online, this is probably the quickest way to get started with BQN. It has good primitive support, with the main issues being that it uses a J-style insert instead of BQN-style vector reduction, that it has a different version of Group (⊔), and that it is missing Choose (◶). There are also some spelling differences, with Deduplicate (⍷) spelled with ∪ and Valences (⊘) spelled with ⍠. It is missing value blocks and function headers.

+

For automated testing I run BQN2NGN using the bqn executable, which is just a symlink to apl.js in the BQN2NGN repository. It requires Node to run.

+

dzaima/BQN

+

dzaima/BQN is an implementation in Java created by modifying the existing dzaima/APL. It should be easy to run on desktop Linux and Android. It is still in development and has almost complete syntax support but incomplete primitive support.

+

dzaima+reference BQN

+

This repository contains a dzaima/BQN script dzref that fills in the gaps in primitive support using BQN implementations of primitives which are not yet up to spec (reference implementations of all primitives starting from a small set of pre-existing functions are part of BQN's specification). These alternate implementations can be very slow.

+

You can run dzref from ordinary dzaima/BQN using the •EX command; see for example dcshim.bqn. For testing, it is run as a Unix script, in which case it depends on an executable dbqn that runs dzaima/BQN on a file argument. I use the following script, using the path to a clone of dzaima/BQN for the jar file.

+
#! /bin/bash
+
+java -jar /path/to/dzaima/BQN/BQN.jar -f "$@"
+
+

The left argument for •EX or the shell arguments can contain up to two arguments for the script. The first is a file to run, and the second is BQN code to be run after it.

+

BQN

+

This repository contains the beginnings of a self-hosted compiler for BQN, which is not yet complete enough to do any real programming with. There are currently several versions of the compiler: nc.bqn is run with BQN2NGN, while c.bqn is run with dzaima+reference. Both compilers have a backend targetting WebAssembly, and c.bqn additionally has a backend that targets dzaima/BQN's own bytecode, so that the compiler uses only BQN, but the runtime uses the Java implementations of BQN primitives from dzaima/BQN.

+

All versions have automated tests in the test directory, with the WebAssembly versions tested with Javascript using Node (test/t.js and test/dt.js for BQN2NGN and dzaima/BQN respectively) and the dzaima/BQN backend tested with BQN itself (test/bt).

+ diff --git a/docs/spec/README.html b/docs/spec/README.html new file mode 100644 index 00000000..6a4ba53f --- /dev/null +++ b/docs/spec/README.html @@ -0,0 +1,14 @@ + +

BQN specification

+

This directory gives a (currently incomplete) specification for BQN. The specification differs from the documentation in doc/ in that its purpose is only to describe the exact details of BQN's operation in the most quickly accessible way, rather than to explain the core ideas of BQN functionality and how it might be used. Since it is easier to specify than to document, the specification is currently more complete than the documentation; for example, it includes nearly all primitives.

+

The following aspects define BQN and are or will be specified:

+ + diff --git a/docs/spec/evaluate.html b/docs/spec/evaluate.html new file mode 100644 index 00000000..6552f80e --- /dev/null +++ b/docs/spec/evaluate.html @@ -0,0 +1,94 @@ + +

This page describes the semantics of the code constructs whose grammar is given in grammar.md. The formation rules there are not named, and here they are identified by either the name of the term or by copying the rule entirely if there are several alternative productions.

+

Here we assume that the referent of each identifier, or equivalently the connections between identifiers, have been identified according to the scoping rules.

+

Programs and blocks

+

The result of parsing a valid BQN program is a PROGRAM, and the program is run by evaluating this term.

+

A PROGRAM or BODY is a list of STMTs (for BODY, the last must be an EXPR, a particular kind of STMT), which are evaluated in program order. The statement nothing does nothing when evaluated, while EXPR evaluates some APL code and possibly assigns the results, as described below.

+

A block consists of several BODY terms, some of which may have an accompanying header describing accepted inputs and how they are processed. A value block brVal can only have one BODY, and is evaluated by evaluating the code in it. Other types of blocks do not evaluate any BODY immediately, but instead return a function, modifier, or operator that obtains its result by evaluating a particular BODY. The BODY is identified and evaluated once the block has received enough inputs (operands or arguments), which for modifiers and compositions can take one or two calls: if two calls are required, then on the first call the operands are simply stored and no code is evaluated yet. Two calls are required if there is more than one BODY term, if the BODY contains the special names 𝕨𝕩𝕤𝕎𝕏𝕊, or if its header specifies arguments (the header-body is a _mCase or _cCase_). Otherwise only one is required.

+

To evaluate a block when enough inputs have been received, first the correct case must be identified. To do this, first each special case (FCase, _mCase, or _cCase_) is checked in order to see if its arguments are strucurally compatible with the given arguments. That is, is headW is a value, there must be a left argument matching that structure, and if headX is a value, the right argument must match that structure. This means that 𝕨 not only matches any left argument but also no argument. The test for compatibility is the same as for multiple assignment described below, except that the header may contain constants, which must match the corresponding part of the given argument.If no special case matches, then an appropriate general case (FMain, _mMain, or _cMain_) is used: if there are two, the first is used with no left argument and the second with a left argument; if there are one, it is always used, and if there are none, an error results.

+

The only remaining step before evaluating the BODY is to bind the inputs and other names. Special names are always bound when applicable: 𝕨𝕩𝕤 if arguments are used, 𝕨 if there is a left argument, 𝕗𝕘 if operands are used, and _𝕣 and _𝕣_ for modifiers and combinators, respectively. Any names in the header are also bound, allowing multiple assignment for arguments.

+

If there is no left argument, but the BODY contains 𝕨 at the top level, then it is conceptually re-parsed with 𝕨 replaced by · to give a monadic version before application. As the only effect when this re-parsed form is valid is to change some instances of arg to nothing, this can be achieved efficiently by annotating parts of the AST that depend on 𝕨 as conditionally-nothing. However, it also causes an error if 𝕨 is used as an operand or list element, where nothing is not allowed by the grammar.

+

Assignment

+

An assignment is one of the four rules containing ASGN. It is evaluated by first evaluating the right-hand-side valExpr, FuncExpr, _modExpr, or _cmpExp_ expression, and then storing the result in the left-hand-side identifier or identifiers. The result of the assignment expression is the result of its right-hand side. Except for values, only a lone identifier is allowed on the left-hand side and storage is obvious. For values, multiple assignment with a list left-hand side is also allowed. Multiple assignment is performed recursively by assigning right-hand-side values to the left-hand-side targets, with single-identifier (v) assignment as the base case. When matching the right-hand side to a list left-hand side, the left hand side is treated as a list of lhs targets. The evaluated right-hand side must be a list (rank-1 array) of the same length, and is matched to these targets element-wise.

+

Modified assignment is the value assignment rule lhs Derv "↩" valExpr. In this case, lhs should be evaluated as if it were a valExpr (the syntax is a subset of valExpr), and the result of the function application lhs Derv valExpr should be assigned to lhs, and is also the result of the modified assignment expression.

+

Expressions

+

We now give rules for evaluating an atom, Func, _mod or _comp_ expression (the possible options for ANY). A literal vl, Fl, _ml, or _cl_ has a fixed value defined by the specification (value literals and built-ins). An identifier v, F, _m, or _c_ is evaluated by returning its value; because of the scoping rules it must have one when evaluated. A parenthesized expression such as "(" _modExpr ")" simply returns the result of the interior expression. A braced construct such as BraceFunc is defined by the evaluation of the statements it contains after all parameters are accepted. Finally, a list "⟨" ⋄? ( ( EXPR ⋄ )* EXPR ⋄? )? "⟩" or ANY ( "‿" ANY )+ consists grammatically of a list of expressions. To evaluate it, each expression is evaluated in source order and their results are placed as elements of a rank-1 array. The two forms have identical semantics but different punctuation.

+

Rules in the table below are function and operator evaluation.

+ + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + +
LLeftCalledRightRTypes
𝕨( value | nothing )?Dervarg𝕩Function, value
𝕗Operand_modModifier
𝕗Operand_comp_( value | Func )𝕘Composition
+

In each case the constituent expressions are evaluated in reverse source order: Right, then Called, then Left. Then the expression's result is obtained by calling the Called value on its parameters. A left argument of nothing is not used as a parameter, leaving only a right argument in that case. The data type of the Called value must be appropriate to the expression type, as indicated in the "Types" column. For function application, a value type (number, character, or array) is allowed. It is called simply by returning itself. Although the arguments are ignored in this case, they are still evaluated. A braced construct is evaluated by binding the parameter names given in columns L and R to the corresponding values. Then if all parameter levels present have been bound, its body is evaluated to give the result of application.

+

The following rules derive new functions or operators from existing ones.

+ + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + +
LeftCenterRightResult
_comp_( value | Func ){𝔽 _C_ R}
Operand_comp_{L _C_ 𝔽}
OperandDervFork{(𝕨L𝕩)C(𝕨R𝕩)}
nothing?DervFork{ C(𝕨R𝕩)}
+

As with applications, all expressions are evaluated in reverse source order before doing anything else. Then a result is formed without calling the center value. Its value in BQN is given in the rightmost column, using L, C, and R for the results of the expressions in the left, center, and right columns, respectively. For the first two rules (partial application), the given operand is bound to the composition: the result is a modifier that, when called, calls the center composition with the bound operand on the same side it appeared on and the new operand on the remaining side. A train is a function that, when called, calls the right-hand function on all arguments, then the left-hand function, and calls the center function with these results as arguments. In a composition partial application, the result will fail when applied if the center value does not have the composition type, and in a fork, it will fail if any component has a modifier or composition type (that is, cannot be applied as a function). BQN implementations are not required to check for these types when forming the result of these expressions, but may give an error on formation even if the result will never be applied.

+ diff --git a/docs/spec/grammar.html b/docs/spec/grammar.html new file mode 100644 index 00000000..56803787 --- /dev/null +++ b/docs/spec/grammar.html @@ -0,0 +1,138 @@ + +

BQN's grammar is given below. Terms are defined in a BNF variant. However, handling special names properly is possible but difficult in BNF, so they are explained in text along with the braced block grammar.

+

The symbols v, F, _m, and _c_ are identifier tokens with value, function, modifier, and composition classes respectively. Similarly, vl, Fl, _ml, and _cl_ refer to value literals (numeric and character literals, or primitives) of those classes. While names in the BNF here follow the identifier naming scheme, this is informative only: syntactic classes are no longer used after parsing and cannot be inspected in a running program.

+

A program is a list of statements. Almost all statements are expressions. However, explicit definitions and valueless results stemming from ·, or 𝕨 in a monadic brace function, can be used as statements but not expressions.

+
PROGRAM  = ⋄? ( ( STMT ⋄ )* STMT ⋄? )?
+STMT     = EXPR | DEF | nothing
+⋄        = ( "⋄" | "," | \n )+
+EXPR     = valExpr | FuncExpr | _modExpr | _cmpExp_
+
+

Here we define the "atomic" forms of functions and operators, which are either single tokens or enclosed in paired symbols. Stranded vectors with ‿, which binds more tightly than any form of execution, are also included.

+
ANY      = atom    | Func     | _mod     | _comp_
+_comp_   = _c_ | _cl_ | "(" _cmpExp_ ")" | _brComp_
+_mod     = _m  | _ml  | "(" _modExpr ")" | _brMod  
+Func     =  F  |  Fl  | "(" FuncExpr ")" |  BrFunc 
+atom     =  v  |  vl  | "(" valExpr  ")" |  brVal | list
+list     = "⟨" ⋄? ( ( EXPR ⋄ )* EXPR ⋄? )? "⟩"
+value    = atom | ANY ( "‿" ANY )+
+
+

Starting at the highest-order objects, modifiers and compositions have fairly simple syntax. In most cases the syntax for ← and ↩ is the same, but only ↩ can be used for modified assignment.

+
ASGN     = "←" | "↩"
+_cmpExp_ = _comp_
+         | _c_ ASGN _cmpExp_
+_modExpr = _mod
+         | _comp_ ( value | Func )    # Right partial application
+         | Operand _comp_             # Left partial application
+         | _m  ASGN _modExpr
+
+

Functions can be formed by fully applying operators or as trains. Operators are left-associative, so that the left operand (Operand) can include operators but the right operand (value | Func) cannot. Trains are right-associative, but bind less tightly than operators. Assignment is not allowed in the top level of a train: it must be parenthesized.

+
Derv     = Func
+         | Operand _mod
+         | Operand _comp_ ( value | Func )
+Operand  = value
+         | Derv
+Fork     = Derv
+         | Operand Derv Fork          # 3-train
+         | nothing Derv Fork          # 2-train
+Train    = Fork
+         | Derv Fork                  # 2-train
+FuncExpr = Train
+         | F ASGN FuncExpr
+
+

Value expressions are complicated by the possibility of list assignment. We also define nothing-statements, which have very similar syntax to value expressions but do not permit assignment.

+
arg      = valExpr
+         | ( value | nothing )? Derv arg
+nothing  = "·"
+         | ( value | nothing )? Derv nothing
+LHS_ANY  = lhsValue | F | _m | _c_
+LHS_ATOM = LHS_ANY | "(" lhsStr ")"
+LHS_ELT  = LHS_ANY | lhsStr
+lhsValue = v
+         | "⟨" ⋄? ( ( LHS_ELT ⋄ )* LHS_ELT ⋄? )? "⟩"
+lhsStr   = LHS_ATOM ( "‿" LHS_ATOM )+
+lhs      = lhsValue | lhsStr
+valExpr  = arg
+         | lhs ASGN valExpr
+         | lhs Derv "↩" valExpr       # Modified assignment
+
+

A header looks like a name for the thing being headed, or its application to inputs (possibly twice in the case of modifiers and compositions). As with assignment, it is restricted to a simple form with no extra parentheses. The full list syntax is allowed for arguments. As a special rule, a monadic function header specifically can omit the function when the argument is not just a name (as this would conflict with a value label). The following cases define only headers with arguments, which are assumed to be special cases; there can be any number of these. Headers without arguments can only refer to the general case—note that operands are not pattern matched—so there can be at most two of these kinds of headers, indicating the monadic and dyadic cases.

+
headW    = value | "𝕨"
+headX    = value | "𝕩"
+HeadF    = F | "𝕗" | "𝔽"
+HeadG    = F | "𝕘" | "𝔾"
+ModH1    = HeadF ( _m  | "_𝕣"  )
+CmpH1    = HeadF ( _c_ | "_𝕣_" ) HeadG
+FuncHead = headW? ( F | "𝕊" ) headX
+         | vl | "(" valExpr ")" | brVal | list   # value,
+         | ANY ( "‿" ANY )+                      # but not v
+_modHead = headW? ModH1 headX
+_cmpHed_ = headW? CmpH1 headX
+
+

A braced block contains bodies, which are lists of statements, separated by semicolons and possibly preceded by headers, which are separated from the body with a colon. Multiple bodies allow different handling for various cases, which are pattern-matched by headers. For a value block there are no inputs, so there can only be one possible case and one body. Functions and operators allow any number of "matched" bodies, with headers that have arguments, followed by at most two "main" bodies with either no headers or headers without arguments. If there is one main body, it is ambivalent, but two main bodies refer to the monadic and dyadic cases.

+
BODY     = ⋄? ( STMT ⋄ )* EXPR ⋄?
+FCase    = ⋄? FuncHead ":" BODY
+_mCase   = ⋄? _modHead ":" BODY
+_cCase_  = ⋄? _cmpHed_ ":" BODY
+FMain    = ( ⋄?    F            ":" )? BODY
+_mMain   = ( ⋄? ( _m  | ModH1 ) ":" )? BODY
+_cMain_  = ( ⋄? ( _c_ | CmpH1 ) ":" )? BODY
+brVal    = "{" ( ⋄? v ":" )? BODY "}"
+BrFunc   = "{" (  FCase  ";" )* (  FCase  |  FMain ( ";"  FMain )? ) "}"
+_brMod   = "{" ( _mCase  ";" )* ( _mCase  | _mMain ( ";" _mMain )? ) "}"
+_brComp_ = "{" ( _cCase_ ";" )* ( _cCase_ | _cMan_ ( ";" _cMan_ )? ) "}"
+
+

Two additional rules apply to blocks, based on the special name associations in the table below. First, each block allows the special names in its column to be used as the given token types within BODY terms (not headers). Except for the spaces labelled "None", each column is cumulative and a given entry also includes all the entries above it. Second, for BrFunc, _brMod, and _brComp_ terms, if no header is given, then at least one BODY term in it must contain one of the names on, and not above, the corresponding row. Otherwise the syntax would be ambiguous, since for example a simple "{" BODY "}" sequence could have any type.

+ + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + +
TermvF_m_c_other
brVal, PROGRAMNoneNoneNoneNone
BrFunc𝕨𝕩𝕤𝕎𝕏𝕊";"
_brMod𝕗𝕣𝔽_𝕣
_brComp_𝕘𝔾None_𝕣_
+

The rules for special name can be expressed in BNF by making many copies of all expression rules above. For each "level", or row in the table, a new version of every rule should be made that allows that level but not higher ones, and another version should be made that requires exactly that level. The values themselves should be included in v, F, _m, and _c_ for these copies. Then the "allowed" rules are made simply by replacing the terms they contain (excluding brVal and so on) with the same "allowed" versions, and "required" rules are constructed using both "allowed" and "required" rules. For every part of a production rule, an alternative should be created that requires the relevant name in that part while allowing it in the others. For example, ( value | nothing )? Derv arg would be transformed to

+
arg_req1 = valExpr_req1
+         | ( value_req1 | nothing_req1 ) Derv_allow1 arg_allow1
+         | ( value_allow1 | nothing_allow1 )? Derv_req1 arg_allow1
+         | ( value_allow1 | nothing_allow1 )? Derv_allow1 arg_req1
+
+

Quite tedious. The explosion of rules is partly due to the fact that the brace-typing rule falls into a weaker class of grammars than the other rules. Most of BQN is deterministic context-free but brace-typing is not, only context-free. Fortunately brace typing does not introduce the parsing difficulties that can be present in a general context-free grammar, and it can easily be performed in linear time: after scanning but before parsing, move through the source code maintaining a stack of the current top-level set of braces. Whenever a colon or special name is encountered, annotate that set of braces to indicate that it is present. When a closing brace is encountered and the top brace is popped off the stack, the type is needed if there was no colon, and can be found based on which names were present. One way to present this information to the parser is to replace the brace tokens with new tokens that indicate the type.

+ diff --git a/docs/spec/literal.html b/docs/spec/literal.html new file mode 100644 index 00000000..c4914753 --- /dev/null +++ b/docs/spec/literal.html @@ -0,0 +1,14 @@ + +

A literal is a single token that indicates a fixed character, number, or array. While literals indicate data of a value type, primitives indicate data of a function type: function, modifier, or composition.

+

Two types of literal deal with text. As the source code is considered to be a sequence of unicode code points ("characters"), and these code points are also used for BQN's character data type, the representation of a text literal is very similar to its value. In a text literal, the newline character is always represented using the ASCII line feed character, code point 10. A character literal is enclosed with single quotes ' and its value is identical to the single character between them. A string literal is enclosed in double quotes ", and any double quotes between them must come in pairs, as a lone double quote marks the end of the literal. The value of a string literal is a rank-1 array whose elements are the characters in between the enclosing quotes, after replacing each pair of double quotes with only one such quote.

+

The format of a numeric literal is more complicated. From the tokenization rules, a numeric literal consists of a numeric character (one of ¯∞π.0123456789) followed by any number of numeric or alphabetic characters. Some numeric literals are valid and indicate a number, while others are invalid and cause an error. The grammar for valid numbers is given below in a BNF variant. Only four alphabetic characters are allowed: "i", which separates the real and imaginary components of a complex number, "e", which functions as in scientific notation, and the uppercase versions of these letters.

+
number    = component ( ( "i" | "I" ) component )?
+component = mantissa ( ( "e" | "E" ) exponent )?
+exponent  = "¯"? digit+
+mantissa  = "¯"? ( "∞" | "π" | digit+ ( "." digit+ )? )
+digit     = "0" | "1" | "2" | "3" | "4" | "5" | "6" | "7" | "8" | "9"
+
+

The digits or arabic numerals correspond to the numbers from 0 to 9 in the conventional way (also, each corresponds to its code point value minus 48). A sequence of digits gives a natural number by evaluating it in base 10: the number is 0 for an empty sequence, and otherwise the last digit's numerical value plus ten times the number obtained from the remaining digits. The symbol ∞ indicates infinity and π indicates the ratio pi) of a circle's circumference to its diameter (or, for modern mathematicians, the smallest positive real number at which the function {⋆0j1×𝕩} attains a real part of 0). The high minus symbol ¯ indicates that the number containing it is to be negated.

+

When an exponent is provided (with e or E), the corresponding mantissa is multiplied by ten to that power, giving the value mantissa×10⋆exponent. If a second component is present (using i or I), that component's value is multiplied by the imaginary unit i and added to the first component; otherwise the value is the first component's value without modification. If complex numbers are not supported, then i should not be allowed in numeric literals, even when followed by 0.

+

The above specification describes exactly a complex number with extended real components. To obtain a BQN number, each component is rounded to its nearest representative by the rules of the number system used: for IEEE 754, smallest distance, with ties rounding to the option with even mantissa.

+ diff --git a/docs/spec/token.html b/docs/spec/token.html new file mode 100644 index 00000000..531cfd6e --- /dev/null +++ b/docs/spec/token.html @@ -0,0 +1,40 @@ + +

This page describes BQN's token formation rules (token formation is also called scanning). Most tokens in BQN are a single character long, but quoted characters and strings, identifiers, and numbers can consist of multiple characters, and comments, spaces, and tabs are discarded during token formation.

+

BQN source code should be considered as a series of unicode code points, which we refer to as "characters". The separator between lines in a file is considered to be a single character, newline, even though some operating systems such as Windows typically represent it with a two-character CRLF sequence. Implementers should note that not all languages treat unicode code points as atomic, as exposing the UTF-8 or UTF-16 representation instead is common. For a language such as JavaScript that uses UTF-16, the double-struck characters 𝕨𝕎𝕩𝕏𝕗𝔽𝕘𝔾 are represented as two 16-bit surrogate characters, but BQN treats them as a single unit.

+

A BQN character literal consists of a single character between single quotes, such as 'a', and a string literal consists of any number of characters between double quotes, such as "" or "abc". Character and string literals take precedence with comments over other tokenization rules, so that # between quotes does not start a comment and whitespace between quotes is not removed, but a quote within a comment does not start a character literal. Almost any character can be included directly in a character or string literal without escaping. The only exception is the double quote character ", which must be written twice to include it in a string, as otherwise it would end the string instead. Character literals require no escaping at all, as the length is fixed. In particular, literals for the double and single quote characters are written ''' and '"', while length-1 strings containing these characters are "'" and """".

+

A comment consists of the hash character # and any following text until (not including) the next newline character. The initial # must not be part of a string literal started earlier. Comments are ignored entirely and do not form tokens.

+

Identifiers and numeric literals share the same token formation rule. These tokens are formed from the numeric characters ¯∞π.0123456789 and alphabetic characters _abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ and the oddball 𝕣. Any sequence of these characters adjacent to each other forms a single token, which is a numeric literal if it begins with a numeric character and an identifier if it begins with an alphabetic character. Numeric literals are also subject to numeric literal rules, which specify which numeric literals are valid and which numbers they represent. If the token contains 𝕣 it must be either 𝕣, _𝕣, or _𝕣_ and is considered a special name (see below). As the value taken by this identifier can only be a modifier or composition, the uppercase character ℝ is not allowed.

+

Following this step, the whitespace characters space and tab are ignored, and do not form tokens. Only these whitespace characters, and the newline character, which does form a token, are allowed.

+

Otherwise, a single character forms a token. Only the specified set of characters can be used; others result in an error. The classes of characters are given below.

+ + + + + + + + + + + + + + + + + + + + + + + + + + + + + +
ClassCharacters
Primitive Function+-×÷⋆√⌊⌈|¬∧∨<>≠=≤≥≡≢⊣⊢⥊∾≍↑↓↕⌽⍉/⍋⍒⊏⊑⊐⊒∊⍷⊔
Primitive Modifier˜˘¨⌜⁼´`
Primitive Composition∘○⊸⟜⌾⊘◶⎉⚇⍟
Special name𝕨𝕩𝕗𝕘𝕤𝕎𝕏𝔽𝔾𝕊
Punctuation←↩→(){}⟨⟩‿⋄, and newline
+

In the BQN grammar specification, the three primitive classes are grouped into terminals Fl, _ml, and _cl, while the punctuation characters are identified separately as keywords such as "←". The special names are handled specially. The uppercase versions 𝕎𝕏𝔽𝔾𝕊 and lowercase versions 𝕨𝕩𝕗𝕘𝕤 are two spellings of the five underlying inputs and function.

+ diff --git a/docs/spec/types.html b/docs/spec/types.html new file mode 100644 index 00000000..81ed35ee --- /dev/null +++ b/docs/spec/types.html @@ -0,0 +1,20 @@ + +

BQN programs manipulate data of six types:

+ +

Of these, the first three are considered value types and the remaining three function types. We first describe the much simpler function types; the remainder of this page will be dedicated to the value types. A member of any function type accepts some number of inputs and either returns a result or causes an error; inputs and the result are data of any type. When a function is given inputs (called), it may produce side effects before returning, such as manipulating variables and calling other functions within its scope, or performing I/O.

+ +

To begin the value types, a character is a Unicode code point, that is, its value is a non-negative integer within the ranges defined by Unicode (however, it is distinct from this number as a BQN value). Characters are ordered by this numeric value. BQN deals with code points as abstract entities and does not use encodings such as UTF-8 or UTF-16.

+

The precise type of a number may vary across BQN implementations or instances. A real number is a member of some supported subset of the extended real numbers, that is, the real numbers and positive or negative infinity. Some system must be defined for rounding an arbitrary real number to a member of this subset, and the basic arithmetic operations add, subtract, multiply, divide, and natural exponent (base e) are defined by performing these operations on exact real values and rounding the result. The Power function (dyadic ⋆) is also used but need not be exactly rounded. A complex number is a value with two real number components, a real part and an imaginary part. A BQN implementation can either support real numbers only, or complex numbers.

+

An array is a rectangular collection of data. It is defined by a shape, which is a list of non-negative integer lengths, and a ravel, which is a list of elements whose length (the array's bound) is the product of all lengths in the shape. Arrays are defined inductively: any value (of a value or function type) can be used as an element of an array, but it is not possible for an array to contain itself as an element, or an array that contains itself, and so on.

+ diff --git a/docs/transpose.html b/docs/transpose.html deleted file mode 100644 index eaedcdb0..00000000 --- a/docs/transpose.html +++ /dev/null @@ -1,88 +0,0 @@ - -

Transpose

-

As in APL, Transpose (⍉) is a tool for rearranging the axes of an array. BQN's version is tweaked to align better with the leading axis model and make common operations easier.

-

Monadic Transpose

-

Transposing a matrix exchanges its axes, mirroring it across the diagonal. APL extends the function to any rank by reversing all axes, but this generalization isn't very natural and is almost never used. The main reason for it is to maintain the equivalence a MP b ←→ a MP⌾⍉ b, where MP ← (+´<˘)∘×⎉1‿∞ is the generalized matrix product. But even here APL's Transpose is suspect. It does much more work than it needs to, as we'll see.

-

BQN's transpose takes the first axis of its argument and moves it to the end.

-
    ≢ a23456 ← ↕2‿3‿4‿5‿6
-[ 2 3 4 5 6 ]
-    ≢ ⍉ a23456
-[ 3 4 5 6 2 ]
-
-

On the argument's ravel, this looks like a simple 2-dimensional transpose: one axis is exchanged with a compound axis made up of the other axes. Here we transpose a rank 3 matrix:

-
    a322 ← 3‿2‿2⥊↕12
-    ≍○<⟜⍉ a322
-┌
-  ┌         ┌
-     0  1     0 4  8
-     2  3     1 5  9
-
-     4  5     2 6 10
-     6  7     3 7 11
-                     ┘
-     8  9
-    10 11
-          ┘
-                       ┘
-
-

But, reading in ravel order, the argument and result have exactly the same element ordering as for the rank 2 matrix ⥊˘ a322:

-
    ≍○<⟜⍉ ⥊˘ a322
-┌
-  ┌             ┌
-    0 1  2  3     0 4  8
-    4 5  6  7     1 5  9
-    8 9 10 11     2 6 10
-              ┘   3 7 11
-                         ┘
-                           ┘
-
-

To exchange multiple axes, use the Power operator. Like Rotate, a negative power will move axes in the other direction. In particular, to move the last axis to the front, use Inverse (as you might expect, this exactly inverts ⍉).

-
    ≢ ⍉⍟3 a23456
-[ 5 6 2 3 4 ]
-    ≢ ⍉⁼ a23456
-[ 6 2 3 4 5 ]
-
-

In fact, we have ≢⍉⍟k a ←→ k⌽≢a for any number k and array a.

-

To move axes other than the first, use the Rank operator in order to leave initial axes untouched. A rank of k>0 transposes only the last k axes while a rank of k<0 ignores the first |k axes.

-
    ≢ ⍉⎉3 a23456
-[ 2 3 5 6 4 ]
-
-

And of course, Rank and Power can be combined to do more complicated transpositions: move a set of contiguous axes with any starting point and length to the end.

-
    ≢ ⍉⁼⎉¯1 a23456
-[ 2 6 3 4 5 ]
-
-

Using these forms, we can state BQN's generalized matrix product swapping rule:

-
a MP b  ←→  ⍉⍟(≠≢a) a ⍉⁼⊸MP⟜⍉ b
-
-

Certainly not as concise as APL's version, but not a horror either. BQN's rule is actually more parsimonious in that it only performs the axis exchanges necessary for the computation: it moves the two axes that will be paired with the matrix product into place before the product, and directly exchanges all axes afterwards. Each of these steps is equivalent in terms of data movement to a matrix transpose, the simplest nontrivial transpose to perform. Also remember that for two-dimensional matrices both kinds of transposition are the same, and APL's rule holds in BQN.

-

Axis permutations of the types we've shown generate the complete permutation group on any number of axes, so you could produce any transposition you want with the right sequence of monadic transpositions with Rank. However, this can be unintuitive and tedious. What if you want to transpose the first three axes, leaving the rest alone? With monadic Transpose you have to send some axes to the end, then bring them back to the beginning. For example [following four or five failed tries]:

-
    ≢ ⍉⁼⎉¯2 ⍉ a23456  # Restrict Transpose to the first three axes
-[ 3 4 2 5 6 ]
-
-

In a case like this BQN's Dyadic transpose is much easier.

-

Dyadic Transpose

-

Transpose also allows a left argument that specifies a permutation of the right argument's axes. For each index p←i⊏𝕨 in the left argument, axis i of the argument is used for axis p of the result. Multiple argument axes can be sent to the same result axis, in which case that axis goes along a diagonal of the argument array, and the result will have a lower rank than the argument.

-
    ≢ 1‿3‿2‿0‿4 ⍉ a23456
-[ 5 2 4 3 6 ]
-    ≢ 1‿2‿2‿0‿0 ⍉ a23456  # Don't worry too much about this case though
-[ 5 2 3 ]
-
-

Since this kind of rearrangement can be counterintuitive, it's often easier to use ⍉⁼ when specifying all axes. If p≡○≠≢a, then we have ≢p⍉⁼a ←→ p⊏≢a.

-
    ≢ 1‿3‿2‿0‿4 ⍉⁼ a23456
-[ 3 5 4 2 6 ]
-
-

So far, all like APL. BQN makes one little extension, which is to allow only some axes to be specified. The left argument will be matched up with leading axes of the right argument. Those axes are moved according to the left argument, and remaining axes are placed in order into the gaps between them.

-
    ≢ 0‿2‿4 ⍉ a23456
-[ 2 5 3 6 4 ]
-
-

In particular, the case with only one argument specified is interesting. Here, the first axis ends up at the given location. This gives us a much better solution to the problem at the end of the last section.

-
    ≢ 2 ⍉ a23456  # Restrict Transpose to the first three axes
-[ 3 4 2 5 6 ]
-
-

Finally, it's worth noting that, as monadic Transpose moves the first axis to the end, it's equivalent to dyadic Transpose with a "default" left argument: (≠∘≢-1˜)⊸⍉.

-

Definitions

-

Here we define the two valences of Transpose more precisely.

-

A non-array right argument to Transpose is always boxed to get a scalar array before doing anything else.

-

Monadic transpose is identical to (≠∘≢-1˜)⊸⍉, except that for scalar arguments it returns the array unchanged rather than giving an error.

-

In Dyadic transpose, the left argument is a number or numeric array of rank 1 or less, and 𝕨≤○≠≢𝕩. Define the result rank r←(≠≢𝕩)-+´¬∊𝕨 to be the argument rank minus the number of duplicate entries in the left argument. We require ∧´𝕨<r. Bring 𝕨 to full length by appending the missing indices: 𝕨∾↩𝕨(¬∘∊˜/⊢)↕r. Now the result shape is defined to be ⌊´¨𝕨⊔≢𝕩. Element i⊑z of the result z is element (𝕨⊏i)⊑𝕩 of the argument.

- diff --git a/docs/windows.html b/docs/windows.html deleted file mode 100644 index a599d634..00000000 --- a/docs/windows.html +++ /dev/null @@ -1,90 +0,0 @@ - -

Windows

-

In BQN, it's strongly preferred to use functions, and not operators (modifiers and compositions), for array manipulation. Functions are simpler as they have fewer moving parts. They are more concrete, since the array results can always be viewed right away. They are easier to implement with reasonable performance as well, since there is no need to recognize many possible function operands as special cases.

-

The Window function replaces APL's Windowed Reduction, J's more general Infix operator, and Dyalog's Stencil, which is adapted from one case of J's Cut operator.

-

Definition

-

We'll start with the one-axis case. Here Window's left argument is a number between 0 and 1+≠𝕩. The result is composed of slices of 𝕩 (contiguous sections of major cells) with length 𝕨, starting at each possible index in order.

-
    5↕"abcdefg"
-┌
-  abcde
-  bcdef
-  cdefg
-        ┘
-
-

There are 1+(≠𝕩)-𝕨, or (≠𝕩)¬𝕨, of these sections, because the starting index must be at least 0 and at most (≠𝕩)-𝕨. Another way to find this result is to look at the number of cells in or before a given slice: there are always 𝕨 in the slice and there are only ≠𝕩 in total, so the number of slices is the range spanned by these two endpoints.

-

You can take a slice of an array 𝕩 that has length l and starts at index i using l↑i↓𝕩 or l↑i⌽𝕩. The Prefixes function returns all the slices that end at the end of the array ((≠𝕩)=i+l), and Suffixes gives the slices that start at the beginning (i=0). Windows gives yet another collection of slices: the ones that have a fixed length l=𝕨. Selecting one cell from its result gives you the slice starting at that cell's index:

-
    2⊏5↕"abcdefg"
-[ cdefg ]
-    5↑2↓"abcdefg"
-[ cdefg ]
-
-

Windows differs from Prefixes and Suffixes in that it doesn't add a layer of nesting (it doesn't box each slice). This is possible because the slices have a fixed size.

-

Multiple dimensions

-

The above description applies to a higher-rank right argument. As an example, we'll look at two-row slices of a shape 3‿4 array. For convenience, we will box each slice. Note that slices always have the same rank as the argument array.

-
    <⎉2 2↕"0123"∾"abcd"≍"ABCD"
-┌
-  ┌        ┌
-    0123     abcd
-    abcd     ABCD
-         ┘        ┘
-                    ┘
-
-

Passing a list as the left argument to Windows takes slices along any number of leading axes. Here are all the shape 2‿2 slices:

-
    <⎉2 2‿2↕"0123"∾"abcd"≍"ABCD"
-┌
-  ┌      ┌      ┌
-    01     12     23
-    ab     bc     cd
-       ┘      ┘      ┘
-  ┌      ┌      ┌
-    ab     bc     cd
-    AB     BC     CD
-       ┘      ┘      ┘
-                       ┘
-
-

The slices are naturally arranged along multiple dimensions according to their starting index. Once again the equivalence i⊏l↕x ←→ l↑i↓x holds, provided i and l have the same length.

-

If the left argument has length 0, then the argument is not sliced along any dimensions. The only slice that results—the entire argument—is then arranged along an additional zero dimensions. In the end, the result is the same as the argument.

-

More formally

-

𝕩 is an array. 𝕨 is a number or numeric list or scalar with 𝕨≤○≠≢𝕩. The result z has shape 𝕨∾¬⟜𝕨⌾((≠𝕨)⊸↑)≢𝕩, and element i⊑z is 𝕩⊑˜(≠𝕨)(↑+⌾((≠𝕨)⊸↑)↓)i.

-

Using Group we could also write i⊑z ←→ 𝕩⊑˜(𝕨∾○(↕∘≠)≢𝕩) +´¨∘⊔ i.

-

Symmetry

-

Let's look at an earlier example, along with its transpose.

-
    {⟨𝕩,⍉𝕩⟩}5↕"abcdefg"
-┌
-  ┌         ┌
-    abcde     abc
-    bcdef     bcd
-    cdefg     cde
-          ┘   def
-              efg
-                  ┘
-                    ┘
-
-

Although the two arrays have different shapes, they are identical where they overlap.

-
    ≡○(3‿3⊸↑)⟜⍉5↕"abcdefg"
-1
-
-

In other words, the i'th element of slice j is the same as the j'th element of slice i: it is the i+j'th element of the argument. So transposing still gives a possible result of Windows, but with a different slice length.

-
    {(5↕𝕩)≡⍉(3↕𝕩)}"abcdefg"
-1
-
-

In general, we need a more complicated transpose—swapping the first set of ≠𝕨 axes with the second set. Note again the use of Span, our slice-length to slice-number converter.

-
    {((5‿6¬2‿2)↕𝕩) ≡ 2‿3⍉(2‿2↕𝕩)} ↕5‿6‿7
-1
-
-

Applications

-

Windows can be followed up with a reduction on each slice to give a windowed reduction. Here we take running sums of 3 values.

-
    +´˘3↕ ⟨2,6,0,1,4,3⟩
-[ 8 7 5 8 ]
-
-

A common task is to pair elements, with an initial or final element so the total length stays the same. This can also be done with a pairwise reduction, but another good way (and more performant without special support in the interpreter) is to add the element and then use windows matching the original length. Here both methods are used to invert +`, which requires we take pairwise differences starting at initial value 0.

-
    -˜´˘2↕0∾ +` 3‿2‿1‿1
-[ 3 2 1 1 ]
-    ((-˜´<˘)≠↕0∾⊢) +` 3‿2‿1‿1
-[ 3 2 1 1 ]
-
-

This method extends to any number of initial elements. We can modify the running sum above to keep the length constant by starting with two zeros.

-
    ((+´<˘)≠↕(2⥊0)⊸∾) ⟨2,6,0,1,4,3⟩
-[ 2 8 8 7 5 8 ]
-
- -- cgit v1.2.3