From 8389e763344637c01d0d7161091e5f2cd9b14251 Mon Sep 17 00:00:00 2001 From: Marshall Lochbaum Date: Mon, 27 Jun 2022 22:00:55 -0400 Subject: Yet still more editing --- docs/doc/context.html | 29 ++++++++++---------- docs/doc/control.html | 38 +++++++++++++------------- docs/doc/couple.html | 47 ++++++++++++++++++-------------- docs/doc/fill.html | 2 +- docs/doc/glossary.html | 2 +- docs/doc/shift.html | 2 +- docs/implementation/compile/dynamic.html | 2 +- docs/implementation/kclaims.html | 2 +- 8 files changed, 65 insertions(+), 59 deletions(-) (limited to 'docs') diff --git a/docs/doc/context.html b/docs/doc/context.html index e5f9adf5..23422fac 100644 --- a/docs/doc/context.html +++ b/docs/doc/context.html @@ -5,21 +5,22 @@
(github) / BQN / doc

BQN's context-free grammar

+

See syntactic role for the plain description of the features discussed here. This page explains why you'd want this system, particularly coming from an APL or J background.

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 roles 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:

+
b(a, d(c)(e))    # C
+(b a ((d c) e))  # Lisp
+
+

In each case, some values are passed to functions while others are the functions being applied (both variables and function results can be used in these two ways). These expressions correspond to the APL one if a and e are arrays, b and c are functions, and d is a monadic operator. But in APL the types aren't part of the expression—they're a form of context that's required for a reader to know the grammatical structure of the expression. Simple C or Lisp expressions don't need this context because a value's grammatical role is determined by the 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 has its own way to annotate grammatical role:

a B C _d e
-

Here, the lowercase spelling indicates that a and e are to be treated as subjects ("arrays" in APL) while the uppercase spelling of variables B and C are used as functions and _d is a 1-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—all values are nouns when speaking about them in English. 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.

+

Here, the lowercase spelling indicates that a and e are to be treated as subjects ("arrays" in APL) while the uppercase B and C are used as functions and _d as a 1-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: the names a, A, _a, and _a_ refer to the exact same variable. 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 1-modifiers and characters like ∘ with unbroken circles are 2-modifiers 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.

+

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 1-modifiers, and characters like ∘ with unbroken circles are 2-modifiers, to start learning the BQN grammar that 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 other 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 just from looking! 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:

@@ -54,15 +55,15 @@ -

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 1-modifiers, and glyphs ∘○⊸⟜⌾⊘◶⚇⎉⍟ with an unbroken circle are 2-modifiers. Other primitives are functions. String and numeric literals are subjects.

+

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 1-modifiers, and glyphs ∘○⊸⟜⌾⊘◶⎉⚇⍟⎊ with an unbroken circle are 2-modifiers. Other primitives are functions. String and numeric literals are subjects.

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 subject. Spelled with an uppercase first letter, like Var, it is a function. Underscores are placed where operands apply to indicate a 1-modifier _var or 2-modifier _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 subject if there are none, but a 𝕨 or 𝕩 makes it at least a function, an 𝔽 makes it a 1- or 2-modifier, and a 𝔾 always makes it a 2-modifier.

-

The syntactic role is a property of an expression, and BQN's grammar determines how roles interact in expressions. In contrast, type is a property of a value, and evaluation rules control what types can be used. This means that roles exist statically in the code (context-free grammar!) while values can change between or within runs of the program. This is necessary to have a context-free grammar with unrestricted dynamic types. Are unrestricted dynamic types useful? Read on…

+

One rule for typing is also best considered to be a pre-parsing rule like the spelling system: the role of a headerless block {} is determined by which special arguments it uses: it's a subject if there aren't any, but a 𝕨 or 𝕩 makes it at least a function, an 𝔽 makes it a 1- or 2-modifier, and a 𝔾 always makes it a 2-modifier.

+

The syntactic role is a property of an expression, and BQN's grammar determines how roles interact in expressions. But type is a property of a value, and evaluation rules control what types can be used. This means that roles exist statically in the code (context-free grammar!) while values can change between or within runs of the program. This is necessary to have a context-free grammar with unrestricted dynamic types. Are unrestricted dynamic types useful? Read on…

Mixing roles

BQN's value types align closely with its syntactic roles: functions, 1-modifiers, and 2-modifiers are all types (operation types) as well as roles, while the other types (data types) are split into numbers, characters, and arrays. This is no accident, and usually values will be used in roles that correspond to their underlying type. However, the ability to use a role that doesn't match the type is also useful.

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

-

It can also be useful to treat a value of a data type as a function, in which case it applies as a constant function. This rule is useful with most built-in modifiers. For example, F⎉1 uses a constant for the rank even though in general a function can be given, and if a is an array then 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 1-modifier can be applied as a 1-modifier and only a 2-modifier can be applied as a 2-modifier. Only a function or data can be applied as a function.

-

It's also worth noting that a subject may unexpectedly 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 special names for inputs to a brace function or modifier. In particular, you can use {𝔽} to convert a subject operand into a function. Converting a function to a subject 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 subject.

+

It can also be useful to treat a value of a data type as a function, in which case it applies as a constant function. Most primitive modifiers are used in this way at least some of the time. For example, F⎉1 has a constant for the rank even though in general a function can be given, and if a is an array then 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. For example, just writing a function as a modifier is allowed, but actually applying it to operands will fail. Only a 1-modifier can be applied as a 1-modifier and only a 2-modifier can be applied as a 2-modifier. Only a function or data can be applied as a function.

+

It's also worth noting that a subject may unexpectedly 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 Constant (˙) modifier keeps a function from being applied when that isn't wanted.

+

The most general way to change the role of a value in BQN is to give it a name. A convenient trick is to use {𝔽} to convert a subject operand into a function. Converting a function to a subject 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 subject.

diff --git a/docs/doc/control.html b/docs/doc/control.html index fbd5f0c5..df625e47 100644 --- a/docs/doc/control.html +++ b/docs/doc/control.html @@ -5,10 +5,10 @@
(github) / BQN / doc

Control flow in BQN

-

BQN does not have ALGOL-style control structures. Instead, functional techniques can be used to control when code is evaluated. This page describes how BQN functionality can be used to emulate something more familiar to an imperative programmer.

+

BQN does not have ALGOL-style control structures. Instead, functional techniques can be used to control when code is evaluated. This page describes how BQN functionality can be used to emulate something more familiar to an imperative programmer.

Control structures here are always functions that act on lists of functions, although alternatives might be presented. This is because stranded functions can be formatted in a very similar way to blocks in curly-brace languages. However, there are many ways to write control flow, including simple operators and a mix of operators and more control-structure-like code. Implementing a control structure rarely takes much code with any method, so there are usually several simple ways to implement a given flow or a variation of it.

The surfeit of ways to write control structures could be a bit of an issue for reading BQN. My hope is that the community can eventually settle on a smaller set of standard forms to recommend so that you won't have to recognize all the variants given here. On the other hand, the cost of using specialized control structures is lower in a large project without too many contributors. In this case BQN's flexibility allows developers to adapt to the project's particular demands (for example, some programs use switch/case statements heavily but most do not).

-

The useful control structures introduced here are collected as shortened definitions below. While uses the slightly more complicated implementation that avoids stack overflow, and DoWhile and For are written in terms of it in order to share this property. The more direct versions with linear stack use appear in the main text.

+

The most useful control structures introduced here are collected as shortened definitions below. While uses the slightly more complicated implementation that avoids stack overflow, and DoWhile and For are written in terms of it in order to share this property. The more direct versions with linear stack use appear in the main text.

If      ← {𝕏⍟𝕎@}´                 # Also Repeat
 IfElse  ← {c‿T‿F: c◶F‿T@}
 While   ← {𝕩{𝔽⍟𝔾∘𝔽_𝕣_𝔾∘𝔽⍟𝔾𝕩}𝕨@}´  # While 1‿{... to run forever
@@ -18,23 +18,23 @@
 # Switch/case statements have many variations; these are a few
 Match   ← {𝕏𝕨}´
 Select  ← {(⊑𝕩)◶(1↓𝕩)@}
-Switch  ← {c←⊑𝕩 ⋄ m‿a←<˘⍉∘‿2⥊1↓𝕩 ⋄ (m⊸⊐⌾<C)◶a@}
+Switch  ← {c←⊑𝕩 ⋄ [m,a]←⍉∘‿2⥊1↓𝕩 ⋄ (m⊸⊐⌾<C)◶a@}
 Test    ← {fn←{C‿A𝕊e:C◶A‿E}´𝕩⋄Fn@}

Blocks and functions

-

Control structures are generally defined to work with blocks of code, which they might skip, or execute one or more times. This might sound like a BQN immediate block, which also consists of a sequence of code to execute, but immediate blocks are always executed as soon as they are encountered and can't be manipulated the way that blocks in imperative languages can. They're intended to be used with lexical scoping as a tool for encapsulation. Instead, the main tool we will use to get control structures is the block function.

+

Control structures are generally defined to work with blocks of code, which they might skip, or execute one or more times. This might sound like a BQN immediate block, which also consists of a sequence of code to execute, but immediate blocks are always executed as soon as they are encountered and can't be manipulated the way that blocks in imperative languages can. They're intended to be used with lexical scoping as a tool for encapsulation. Instead, the main tool we will use to get control structures is the block function.

Using functions as blocks is a little outside their intended purpose, and the fact that they have to be passed an argument and are expected to use it will be a minor annoyance. The following conventions signal a function that ignores its argument and is called purely for the side effects:

-

Even with these workarounds, BQN's "niladic" function syntax is quite lightweight, comparing favorably to a low-boilerplate language like Javascript.

+

Even with these workarounds, BQN's "niladic" function syntax is lightweight, comparing favorably to a low-boilerplate language like Javascript.

fn = ()=>{m+=1;n*=2}; fn()
 Fn ← {𝕤⋄  m+↩1,n×↩2}, Fn @

Control structures are called "statements" below to match common usage, but they are actually expressions, and return a value that might be used later.

If

-

The if statement conditionally performs some action. It is similar to the Repeat (⍟) modifier with a right operand returning a boolean: Fn⍟Cond 𝕩 gives Fn 𝕩 if Cond 𝕩 is 1, and returns 𝕩 without calling Fn if Cond 𝕩 is 0. Here is how we might make it behave like a control structure.

+

The if statement conditionally performs some action. It's similar to the Repeat (⍟) modifier with a right operand that returns a boolean: Fn⍟Cond 𝕩 gives Fn 𝕩 if Cond 𝕩 is 1, and returns 𝕩 without calling Fn if Cond 𝕩 is 0. Here's how we might make it behave like a control structure.

{𝕤⋄a+↩10}⍟(a<10) @

The condition a<10 is always evaluated, so there's no need to wrap it in a function. However, the function {𝕤⋄a<10} could be used in place of (a<10), making the entire structure into a function that could be incorporated into other control structures.

@@ -48,21 +48,21 @@ }

The result of any of these if statements is the result of the action if it's performed, and otherwise it's whatever argument was passed to the statement, which is @ or 10 here.

-

BQN's syntax for a pure if statement isn't so good, but predicates handle if-else statements nicely. So in most cases you'd forego the definitions above in favor of an if-else with nothing in the else branch:

+

BQN's syntax for a pure if statement isn't so good, but predicates handle if-else statements nicely. So in most cases you'd forego the definitions above in favor of an if-else with nothing in the else branch:

{ a<10 ? a+↩10 ; @ }

Repeat

There's no reason the condition in an if statement from the previous section has to be boolean: it could be any natural number, causing the action to be repeated that many times. If the action is never performed, the result is the statement's argument, and otherwise it's the result of the last time the action was performed.

Another option is to use a for-each statement with an argument of ↕n: in this case the result is the list of each action's result.

If-Else

-

In most cases, the easy way to write an if-else statement is with predicates:

+

In most cases, the easy way to write an if-else statement is with a predicate:

{
   threshold < 6 ?
   a ↩ Small threshold ;  # If predicate was true
   b ↩ 1 Large threshold  # If it wasn't
 }
-

We might also think of an if-else statement as a kind of switch-case statement, where the two cases are true (1) and false (0). As a result, we can implement it either with Choose (◶) or with case headers of 1 and 0.

+

We might also think of an if-else statement as a kind of switch-case statement, where the two cases are true (1) and false (0). As a result, we can implement it either with Choose (◶) or with case headers of 1 and 0.

When using Choose, note that the natural ordering places the false case before the true one to match list index ordering. To get the typical if-else order, the condition should be negated or the statements reversed. Here's a function to get an if-else statement by swapping the conditions, and two ways its application might be written.

IfElse ← {cond‿True‿False: cond◶False‿True @}
 
@@ -99,7 +99,7 @@
 Test ⟨
   (  a<b)‿{𝕤⋄a+↩1}
   {𝕤⋄a<c}‿{𝕤⋄c-↩1}
-  {𝕤⋄a-↩2}
+          {𝕤⋄a-↩2}
 ⟩

Switch-Case

@@ -114,7 +114,7 @@ 𝕩: n∾↩𝕩 } -

A simplified version of a switch-case statement is possible if the cases are natural numbers 0, 1, and so on. The Choose (◶) modifier does just what we want. The Select statement below generalizes IfElse, except that it doesn't rearrange the cases relative to Choose while IfElse swaps them.

+

A simplified version of a switch-case statement is possible if the cases are natural numbers 0, 1, and so on. The Choose (◶) modifier does just what we want. The Select statement below generalizes IfElse, except that it doesn't rearrange the cases relative to Choose while IfElse swaps them.

Select ← {(⊑𝕩)◶(1↓𝕩)@}
 
 Select number‿{
@@ -126,7 +126,7 @@
 }

To test against other possible values, the following statement takes interleaved lists of values and actions, and disentangles them. It searches through the values with ⊐.

-
Switch ← {c←⊑𝕩 ⋄ m‿a←<˘⍉∘‿2⥊1↓𝕩 ⋄ (m⊸⊐⌾<C)◶a@}
+
Switch ← {c←⊑𝕩 ⋄ [m,a]←⍉∘‿2⥊1↓𝕩 ⋄ (m⊸⊐⌾<C)◶a@}
 
 Switch ⟨value
   "increment" ⋄ {𝕤⋄ v+↩1}
@@ -137,13 +137,13 @@
 

 
Finally, the most general form of a switch statement is a chained if-else!

 
Loop forever

-
It's not a particularly common pattern, but this is a good simple case to warm up for the while loop. BQN primitives usually take a predictable amount of time, and none of them will run forever! Recursion is the tool to use here. If there's a particular function that we'd like to run infinity times, we can just add 𝕨𝕊𝕩 to the end:

+
It's not a particularly common pattern, but this is a good simple case to warm up for the while loop. BQN primitives usually take a predictable amount of time, and none of them will run forever! Recursion is the tool to use here. If there's a particular function that we'd like to run infinity times, we can just add 𝕨𝕊𝕩 to the end:

 
{
   # Stuff to do forever
   𝕨𝕊𝕩
 } arg
 

-
To convert this to a control structure format, we want to take an action A, and produce a function that runs A, then runs itself. Finally we want to call that function on some argument, say @. The argument is a single function, so to call Forever, we need to convert that function to a subject role.

+
It's important to note that this won't actually run that many times before it fails with a stack overflow. We'll address that later. Anyway, to convert this to a control structure format, we want to take an action A, and produce a function that runs A, then runs itself. Finally we want to call that function on some argument, say @. The argument is a single function, so to call Forever, we need to convert that function to a subject role.

 
Forever ← {𝕊a:{𝕊A𝕩}@}
 
 Forever 1⊑@‿{𝕤
@@ -153,7 +153,7 @@
 
A slicker method is to pass 𝕩 as an operand to a modifier. In a modifier, 𝕊 has the operands built in (just like {𝕊A𝕩} above has the environment containing A built in), so it will work the same way with no need for an explicit variable assignment.

 
Forever ← {𝕩{𝕊𝔽𝕩}@}
 

-
The syntax here is awkward enough that it's actually better to use a while loop, with a constant condition of 1!

+
But the calling syntax is awkward enough that it's actually better to use a while loop, with a constant condition of 1!

 
While 1‿{𝕤
   # Stuff to do forever
 }
@@ -174,9 +174,9 @@
 
The above version of While will fail in a fairly small number of iterations, because it consumes a new stack frame with each iteration. While tail call optimization could solve this, detecting the tail call in a compound function like 𝕊∘𝔾⍟𝔽 is technically difficult and would introduce overhead into a BQN interpreter. However, there is a method to make the number of required stack frames logarithmic in the number of iterations instead of linear:

 
While ← {𝕩{𝔽⍟𝔾∘𝔽_𝕣_𝔾∘𝔽⍟𝔾𝕩}𝕨@}´
 

-
The innovation is to use {𝔽⍟𝔾∘𝔽_𝕣_𝔾∘𝔽⍟𝔾𝕩} instead of the equivalent {𝔽_𝕣_𝔾∘𝔽⍟𝔾𝕩} or {𝕊∘𝔽⍟𝔾𝕩} (these are the same, as 𝕊 in a modifier is defined as 𝔽_𝕣_𝔾). Here 𝔽 performs one iteration and 𝔾 tests whether to continue. The simplest approach is to perform one iteration and recurse with the same two functions. The modified approach replaces 𝔽 with 𝔽⍟𝔾∘𝔽, that is, it doubles it while making sure the condition is still checked each iteration. The doublings compound so that recursion level n performs 𝔽 up to 2⋆n times while using on the order of n additional stack frames. Only a hundred or two stack frames are needed to give a practically unlimited number of iterations.

+
The innovation is to use {𝔽⍟𝔾∘𝔽_𝕣_𝔾∘𝔽⍟𝔾𝕩} instead of the equivalent {𝔽_𝕣_𝔾∘𝔽⍟𝔾𝕩} or {𝕊∘𝔽⍟𝔾𝕩} (these are the same, as 𝕊 in a modifier is defined to be 𝔽_𝕣_𝔾). Here 𝔽 performs one iteration and 𝔾 tests whether to continue. The simplest approach is to perform one iteration, then recurse with the same two functions. The modified approach replaces 𝔽 with 𝔽⍟𝔾∘𝔽, that is, it doubles it while making sure the condition is still checked each iteration. The doublings compound so that recursion level n performs 𝔽 up to 2⋆n times while using on the order of n additional stack frames. Only a hundred or two stack frames are needed to give a practically unlimited number of iterations.

 
For

-
To begin with, are you sure you don't want a for-each loop instead? In BQN that's just a function with Each (¨), and it covers most common uses of a for loop.

+
To begin with, are you sure you don't want a for-each loop instead? In BQN that's just a function with Each (¨), and it covers most common uses of a for loop.

 
Fn¨ v      # for (𝕩 in v)
 Fn¨ ↕n     # for (𝕩=0; 𝕩<n; 𝕩++)
 Fn¨ k↓↕n   # for (𝕩=k; 𝕩<n; 𝕩++)  with 0≤k
@@ -194,8 +194,8 @@
   }
 }
 

-
The initialization can be a simple expression as shown; in fact it's a little silly to make initialization one of the arguments to For at all.Unlike in C, it's impossible to declare a variable that's local to the whole For loop but not its surroundings. Hopefully this is obvious from the structure of the code! Only curly braces can create a new scope, so to localize some variables in the For loop, just surround it in an extra set of curly braces.

-
The While loop alone allows syntax similar to the For loop. Perform any initialization outside of the loop, and compose the post-action with the main body using the reverse composition {𝔾∘𝔽}. Because the composition binds less tightly than stranding, the bracketed list notation has to be used here.

+
The initialization can be a simple expression as shown; in fact it's a little silly to make initialization one of the arguments to For at all. Unlike in C, it's impossible to declare a variable that's local to the whole For loop but not its surroundings. Hopefully this is obvious from the structure of the code! Only curly braces can create a new scope, so to localize some variables in the For loop, surround it in an extra set of curly braces.

+
The While loop alone allows syntax similar to the For loop. Perform any initialization outside of the loop, and compose the post-action with the main body using the reverse composition {𝔾∘𝔽}. Because that composition would bind less tightly than stranding, the bracketed list notation has to be used here.

 
c←27 ⋄ n←0
 While ⟨{𝕤⋄1<c}, {𝕤⋄n+↩1}{𝔾∘𝔽}{𝕤
   Match (2|c)‿{
diff --git a/docs/doc/couple.html b/docs/doc/couple.html
index 93bf5e74..d5325de5 100644
--- a/docs/doc/couple.html
+++ b/docs/doc/couple.html
@@ -5,17 +5,15 @@
 
 
(github) / BQN / doc

 
Couple and Merge

-
Solo/Couple (≍) and Merge (>) are functions that create a higher-rank array from lower-rank components. Each takes some number of inner arrays organized in an outer structure, and creates a single array combining all elements of those inner arrays. For example, let's couple two arrays of shape 2‿3:

-↗️
    ⊢ p ← 3‿5×⌜↕3
-┌─        
-╵ 0 3  6  
-  0 5 10  
-         ┘
-    ⊢ q ← 2‿3⥊"abcdef"
-┌─     
-╵"abc  
-  def" 
-      ┘
+
Solo/Couple (≍) and Merge (>) are functions that build a higher-rank array out of cells. Each takes some input arrays with the same shape, and combines them into a single array that includes all their elements. For example, let's couple two arrays of shape 2‿3:

+↗️
    ⟨p←3‿5×⌜↕3, q←2‿3⥊"abcdef"⟩  # Shown side by side
+┌─                    
+· ┌─         ┌─       
+  ╵ 0 3  6   ╵"abc    
+    0 5 10     def"   
+           ┘       ┘  
+                     ┘
+
     p ≍ q   # p coupled to q
 ┌─             
 ╎ 0   3   6    
@@ -24,24 +22,27 @@
   'a' 'b' 'c'  
   'd' 'e' 'f'  
               ┘
+
     ≢ p ≍ q
 ⟨ 2 2 3 ⟩
 

-
The result has two inner axes that are shared by p and q, preceded by an outer axis: length 2 because there are two arguments. Calling ≍ with no left argument does something simpler: because there is one argument, it just adds a length-1 axis to the front. The argument goes solo, becoming the only major cell of the result.

-↗️
    ≍ q
+
The result is an array with p and q for its major cells. It has two inner axes that are shared by p and q, preceded by an outer axis, with length 2 because there are two arguments. With no left argument, ≍ does something simpler: it just adds an axis of length 1 to the front. The argument goes solo, becoming the only major cell of the result.

+↗️
    ≍ q
 ┌─     
 ╎"abc  
   def" 
       ┘
+
     ≢ ≍ q
 ⟨ 1 2 3 ⟩
 

-
Merge (>) also takes one argument, but a nested one. Its argument is an array of arrays, each with the same shape. The shape of the result is then the outer shape followed by this shared inner shape.

-↗️
    ⊢ a ← "AB"‿"CD" ∾⌜ "rst"‿"uvw"‿"xyz"
+
Merge (>) takes one argument, but a nested one. 𝕩 is an array of arrays, each with the same shape. The shape of the result is then the outer shape ≢𝕩 followed by this shared inner shape.

+↗️
    ⊢ a ← "AB"‿"CD" ∾⌜ "rst"‿"uvw"‿"xyz"
 ┌─                         
 ╵ "ABrst" "ABuvw" "ABxyz"  
   "CDrst" "CDuvw" "CDxyz"  
                           ┘
+
     > a
 ┌─       
 ╎"ABrst  
@@ -52,20 +53,24 @@
   CDuvw  
   CDxyz" 
         ┘
+
+    ≢ a
+⟨ 2 3 ⟩
     ≢ > a
 ⟨ 2 3 5 ⟩
 

-
Merge is effectively a generalization of Solo and Couple, since Solo is {>⟨𝕩⟩} and Couple is {>⟨𝕨,𝕩⟩}. Since ≍ works on the "list" of arguments, it can only add one dimension, but > can take any number of dimensions as its input.

+
Merge serves as a generalization of Solo and Couple, since Solo is {>⟨𝕩⟩} and Couple is {>⟨𝕨,𝕩⟩}. Since ≍ works on the "list" of arguments, it can only add one dimension, but > can take any number of dimensions as its input.

 
Merge and array theory

-
In all cases what these functions do is more like reinterpreting existing data than creating new information. In fact, if we ignore the shape and look at the deshaped arrays involved in a call to Merge, we find that it just joins them together. Essentially, Merge is a request to ensure that the inner arrays (which, being independent elements, could be any sort of "ragged" array) can fit together in an array, and then to consider them to be such an array. For this reason, Merge (or a virtual analogue) is used to combine the result cells when calling a function with Rank into a single array.

-↗️
    ⥊ > a
+
In all cases, what these functions do is more like reinterpreting existing data than creating new information. In fact, if we ignore the shape and look at the deshaped arrays involved in a call to Merge, we find that it just joins them together. Essentially, Merge is a request to ensure that the inner arrays make up a homogeneous (not "ragged") array, and then to consider them to be such an array. It's the same thing Rank does to combine the result cells from its operand into a single array.

+↗️
    ⥊ > a
 "ABrstABuvwABxyzCDrstCDuvwCDxyz"
+
     ⥊ ⥊¨ a
 ⟨ "ABrst" "ABuvw" "ABxyz" "CDrst" "CDuvw" "CDxyz" ⟩
     ∾ ⥊ ⥊¨ a
 "ABrstABuvwABxyzCDrstCDuvwCDxyz"
 

-
The way this happens, and the constraint that all inner arrays have the same shape, is closely connected to the concept of an array, and like Table ⌜, Merge might be considered a fundamental way to build up multidimensional arrays from lists. In both cases rank-0 or unit arrays are somewhat special. They are the identity value of a function with Table, and can be produced by Merge inverse, >⁼ on a list, which forces either the outer or inner shape to be empty (BQN chooses >⁼ to be <, but only on an array, as > cannot produce non-arrays). Merge has another catch as well: it cannot produce arrays with a 0 in the shape, except at the end, without relying on a fill element.

+
Somewhat like Table ⌜, Merge might be considered a fundamental way to build up multidimensional arrays from lists. In both cases rank-0 or unit arrays are somewhat special. They are the identity value of a function with Table, and Enclose (<), which creates a unit, is a right inverse to Merge. Enclose is needed because Merge can't produce a rank 0 array on its own. Merge has another catch as well: it can't produce arrays with a 0 in the shape, except at the end, without relying on a fill element.

 ↗️
    ⊢ e ← ⟨⟩¨ ↕3
 ⟨ ⟨⟩ ⟨⟩ ⟨⟩ ⟩
     ≢ > e
@@ -73,10 +78,10 @@
     ≢ > > e
 ⟨ 3 0 ⟩
 

-
Above we start with a list of three empty arrays. After merging once we get a shape 3‿0 array, sure, but what happens next? The shape added by another merge is the shared shape of that array's elements—and there aren't any! If the nested list kept some type information around then we might know, but extra type information is essentially how lists pretend to be arrays. True dynamic lists simply can't represent multidimensional arrays with a 0 in the middle of the shape. In this sense, arrays are a richer model than nested lists.

+
Above we start with a list of three empty arrays. After merging once we get a shape 3‿0 array, sure, but what happens next? The shape added by another merge is the shared shape of that array's elements—and there aren't any! If the nested list kept some type information around then we might know, but extra type information is essentially how lists pretend to be arrays. True dynamic lists simply can't represent multidimensional arrays with a 0 in the middle of the shape. In this sense, arrays are a richer model than nested lists.

 
Coupling units

 
A note on the topic of Solo and Couple applied to units. As always, one axis will be added, so that the result is a list (strangely, J's laminate differs from Couple in this one case, as it will add an axis to get a shape 2‿1 result). For Solo, this is interchangeable with Deshape (⥊), and either primitive might be chosen for stylistic reasons. For Couple, it is equivalent to Join-to (∾), but this is an irregular form of Join-to because it is the only case where Join-to adds an axis to both arguments instead of just one. Couple should be preferred in this case.

 
The function Pair (⋈) can be written ≍○<, while ≍ in either valence is >∘⋈. As an interesting consequence, ≍ ←→ >∘≍○<, and ⋈ ←→ >∘⋈○<. These two identities have the same form because adding ○< commutes with adding >∘.

 
Definitions

-
As discussed above, ≍ is equivalent to >{⟨𝕩⟩;⟨𝕨,𝕩⟩}. To complete the picture we should describe Merge fully. Merge is defined on an array argument 𝕩 such that there's some shape s satisfying ∧´⥊(s≡≢)¨𝕩. If 𝕩 is empty then any shape satisfies this expression; s should be chosen based on known type information for 𝕩 or otherwise assumed to be ⟨⟩. If s is empty then 𝕩 is allowed to contain atoms as well as unit arrays, and these will be implicitly promoted to arrays by the ⊑ indexing used later. We construct the result by combining the outer and inner axes of the argument with Table; since the outer axes come first they must correspond to the left argument and the inner axes must correspond to the right argument. 𝕩 is a natural choice of left argument, and because no concrete array can be used, the right argument will be ↕s, the array of indices into any element of 𝕩. To get the appropriate element corresponding to a particular choice of index and element of 𝕩 we should select using that index. The result of Merge is 𝕩⊑˜⌜↕s.

+
As discussed above, ≍ is equivalent to >{⟨𝕩⟩;⟨𝕨,𝕩⟩} or >⋈. To complete the picture we should describe Merge fully. Merge is defined on an array argument 𝕩 such that there's some shape s satisfying ∧´⥊(s≡≢)¨𝕩. If 𝕩 is empty then any shape satisfies this expression; s should be chosen based on known type information for 𝕩 or otherwise assumed to be ⟨⟩. If s is empty then 𝕩 is allowed to contain atoms as well as unit arrays, and these will be implicitly promoted to arrays by the ⊑ indexing used later. We construct the result by combining the outer and inner axes of the argument with Table; since the outer axes come first they must correspond to the left argument and the inner axes must correspond to the right argument. 𝕩 is a natural choice of left argument, and because no concrete array can be used, the right argument will be ↕s, the array of indices into any element of 𝕩. To get the appropriate element corresponding to a particular choice of index and element of 𝕩 we should select using that index. The result of Merge is 𝕩⊑˜⌜↕s.

 
Given this definition we can also describe Rank (⎉) in terms of Each (¨) and the simpler monadic function Enclose-Rank <⎉k. We assume effective ranks j for 𝕨 (if present) and k for 𝕩 have been computed. Then the correspondence is 𝕨F⎉k𝕩 ←→ >(<⎉j𝕨)F¨(<⎉k𝕩).

diff --git a/docs/doc/fill.html b/docs/doc/fill.html
index ef6e1422..3c1a0c27 100644
--- a/docs/doc/fill.html
+++ b/docs/doc/fill.html
@@ -45,7 +45,7 @@
 ↗️
    » "abc" + 4‿3‿2
 " ee"
 

-
Mapping modifiers Each and Table (¨⌜) might try to follow a similar strategy, applying 𝔽 to argument fills to obtain the result fill. The absolute rule here is that this computation cannot cause side effects or an error, so for a complicated 𝔽 such as a block function this procedure is likely to be aborted to avoid disrupting the rest of the program.

+
Mapping modifiers Each and Table (¨⌜) might try to follow a similar strategy, applying 𝔽 to argument fills to obtain the result fill. The absolute rule here is that this computation can't cause side effects or an error, so for a complicated 𝔽 such as a block function this procedure is likely to be aborted to avoid disrupting the rest of the program.

 
Most other primitives fit in one of three broad categories as shown in the table below. Structural primitives, indicated by ⊢, don't change the fill of 𝕩. Combining structural primitives, indicated by ∩, only depend on the fill of all combined arrays—elements of 𝕩 in the one-argument case, or 𝕨 and 𝕩 in the two-argument case. Finally, many functions such as search functions return only numbers and have a fill of 0.

 
diff --git a/docs/doc/glossary.html b/docs/doc/glossary.html
index 720c12cc..13581749 100644
--- a/docs/doc/glossary.html
+++ b/docs/doc/glossary.html
@@ -100,7 +100,7 @@
 
    
 
  • Error: A condition that stops compilation or execution (see assert).
    • 
-
  • Inferred property: A property of a value that is derived by BQN based on constraints. If it cannot be derived then the value will not have the property. Includes identity values, fill elements, and behavior of Undo and Under.
    • 
+
  • Inferred property: A property of a value that is derived by BQN based on constraints. If it can't be derived then the value won't have the property. Includes identity values, fill elements, and behavior of Undo and Under.
    • 
 
Namespaces
    
diff --git a/docs/doc/shift.html b/docs/doc/shift.html
index 8e8b3640..84684f8a 100644
--- a/docs/doc/shift.html
+++ b/docs/doc/shift.html
@@ -133,5 +133,5 @@
 
 
    Definition
    
 
    In any instance of » or «, 𝕩 must have rank at least 1.
    
-
    For a dyadic shift function, 𝕨 must be Join-compatible with 𝕩 (that is, 𝕨∾𝕩 completes without error) and cannot have greater rank than 𝕩. Then Shift Before (») is {(≠𝕩)↑𝕨∾𝕩} and Shift After («) is {(-≠𝕩)↑𝕩∾𝕨}
    
+
    For a dyadic shift function, 𝕨 must be Join-compatible with 𝕩 (that is, 𝕨∾𝕩 completes without error) and can't have greater rank than 𝕩. Then Shift Before (») is {(≠𝕩)↑𝕨∾𝕩} and Shift After («) is {(-≠𝕩)↑𝕩∾𝕨}
    
 
    When called monadically, the default argument is a cell of fills 1↑0↑𝕩. That is, Nudge (») is (1↑0↑⊢)⊸» and Nudge Back («) is (1↑0↑⊢)⊸«. This default argument always satisfies the compatibility requirement above and so the only conditions for nudge are that 𝕩 has rank at least 1 and has a fill element.
    
diff --git a/docs/implementation/compile/dynamic.html b/docs/implementation/compile/dynamic.html
index 62c8ec2b..30a84d38 100644
--- a/docs/implementation/compile/dynamic.html
+++ b/docs/implementation/compile/dynamic.html
@@ -51,7 +51,7 @@
 
    A simple and widely-used strategy to reduce slowdown due to dynamic compilation is to compile blocks in a separate thread from the one that runs them. The new code needs to be added in a thread-safe manner, which is not hard as the set of optimized implementations is a small lookup table of some sort with only one writer.
    
 
    If the implementation is able to make use of all available threads (possible when working with large arrays), then it's still important to minimize compilation time as that thread could be put to better use. If there are idle threads then the only costs of compilation overhead are minor: the optimized code can't be put to use as quickly, and there is more power draw and possible downclocking.
    
 
    Anticipation
    
-
    The hot path strategy depends on targetting code for optimization based on history. Anticipation would identify in advance what code will take longer to run, and allocate a fraction of the time taken for optimizing that code. This is most useful for code that runs a small number of times on large arrays. An example where anticipation would be very important is for a programmer trying experimental one-off queries on a large dataset.
    
+
    The hot path strategy depends on targeting code for optimization based on history. Anticipation would identify in advance what code will take longer to run, and allocate a fraction of the time taken for optimizing that code. This is most useful for code that runs a small number of times on large arrays. An example where anticipation would be very important is for a programmer trying experimental one-off queries on a large dataset.
    
 
    The end result seems similar to that obtained by thunks as discussed at Dyalog '18 (video, slides). A thunk runs as part of a primitive, detecting that computing the result will be slow and outputting a deferred computation instead. Anticipation is more powerful because it can scan ahead in the bytecode instead of deciding as primitives are called whether or not to expand the thunk.
    
 
    Anticipation attempts to improve program speed while bounding the added overhead. For example, it might be constrained to add no more than 5% to the time to first program output, relative to base-level interpretation. The idea is to exit normal interpretation as soon as a large enough lower bound is established on this time, for example if an operation would create a large array. At this point it begins analysis, which will involve at least some shape propagation and probably increase the lower bound and optimization budget.
    
 
    Optimization level can be gated based on the ratio of expected time to code length (which presumably controls cost of optimization). But optimization doesn't need to be performed all at once: upcoming code should be run as soon as it can be optimized at an appropriate level, in order to have more information available for later operations. Optimization might include primitive combinations or intermediate data formats, so it's important to check how the results will be used before running expensive code.
    
diff --git a/docs/implementation/kclaims.html b/docs/implementation/kclaims.html
index 0eb0e756..0bc4c005 100644
--- a/docs/implementation/kclaims.html
+++ b/docs/implementation/kclaims.html
@@ -22,7 +22,7 @@
 
    Popular APL and J implementations interpret source code directly, without even building an AST. This is very slow, and Dyalog has several other pathologies that get in the way as well. Like storing the execution stack in the workspace to prevent stack overflows, and the requirement that a user can save a workspace with paused code and resume it in a later version. But the overhead is per token executed, and a programmer can avoid the cost by working on large arrays where one token does a whole lot of work. If you want to show a language is faster than APL generally, this is the kind of code to look at.
    
 
    K's design is well-suited to interpreting scalar code because of its simplicity. It has only one kind of user-defined function and doesn't allow lexical closures. Implementations always compile to bytecode, which for example Q's value function shows. Having to keep track of integers versus floats is a drag, but ngn/k is able to use tagged pointers to store smaller integers without an allocation, and I doubt Whitney would miss a trick like that. So K interpreters can be fast.
    
 
    But K still isn't good at scalar code! It's an interpreter (if a good one) for a dynamically-typed language, and will be slower than compiled languages like C and Go, or JIT-compiled ones like Javascript and Java. A compiler generates code to do what you want, while an interpreter (including a bytecode VM) is code that reads data (the program) to do what you want. Once the code is compiled, the interpreter has an extra step and has to be slower.
    
-
    This is why BQN uses compiler-based strategies to speed up execution, first compiling to object code and then usually further processing it (compilation is fast enough that it's perfectly fine to compile code every time it's run). In particular, CBQN can compile to x86 to get rid of dispatching overhead. And ktye's somewhat obscure K implementation now has an ahead-of-time compiler targetting C, which is great news. Commercial K and Q are always described by developers as interpreters, not compilers, and if they do anything like this then they have kept very quiet about it.
    
+
    This is why BQN uses compiler-based strategies to speed up execution, first compiling to object code and then usually further processing it (compilation is fast enough that it's perfectly fine to compile code every time it's run). In particular, CBQN can compile to x86 to get rid of dispatching overhead. And ktye's somewhat obscure K implementation now has an ahead-of-time compiler targeting C, which is great news. Commercial K and Q are always described by developers as interpreters, not compilers, and if they do anything like this then they have kept very quiet about it.
    
 
    Parallel execution
    
 
    As of 2020, Q supports multithreaded primitives that can run on multiple CPU cores. I think Shakti supports multi-threading as well. Oddly enough, J user Monument AI has also been working on their own parallel J engine. So array languages are finally moving to multiple cores (the reason this hasn't happened sooner is probably that array language users often have workloads where they can run one instance on each core, which is easier and tends to be faster than splitting one run across multiple cores). It's interesting, and a potential reason to use K or Q, although it's too recent to be part of the "K is fastest" mythos. Not every K claim is a wild one!
    
 
    Instruction cache
    
-- 
cgit v1.2.3