diff options
| author | Marshall Lochbaum <mwlochbaum@gmail.com> | 2022-06-27 22:00:55 -0400 |
|---|---|---|
| committer | Marshall Lochbaum <mwlochbaum@gmail.com> | 2022-06-27 22:00:55 -0400 |
| commit | 8389e763344637c01d0d7161091e5f2cd9b14251 (patch) | |
| tree | 5406113f6711c6b1222650228cba453c2e4641fa /docs | |
| parent | b6185d5029e2adcc721c0cc2097f591d9a09f135 (diff) | |
Yet still more editing
Diffstat (limited to 'docs')
| -rw-r--r-- | docs/doc/context.html | 29 | ||||
| -rw-r--r-- | docs/doc/control.html | 38 | ||||
| -rw-r--r-- | docs/doc/couple.html | 47 | ||||
| -rw-r--r-- | docs/doc/fill.html | 2 | ||||
| -rw-r--r-- | docs/doc/glossary.html | 2 | ||||
| -rw-r--r-- | docs/doc/shift.html | 2 | ||||
| -rw-r--r-- | docs/implementation/compile/dynamic.html | 2 | ||||
| -rw-r--r-- | docs/implementation/kclaims.html | 2 |
8 files changed, 65 insertions, 59 deletions
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 @@ </head> <div class="nav">(<a href="https://github.com/mlochbaum/BQN">github</a>) / <a href="../index.html">BQN</a> / <a href="index.html">doc</a></div> <h1 id="bqns-context-free-grammar"><a class="header" href="#bqns-context-free-grammar">BQN's context-free grammar</a></h1> +<p><em>See <a href="expression.html#syntactic-role">syntactic role</a> 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.</em></p> <p>APL has a problem. To illustrate, let's look at an APL expression:</p> <pre><span class='Value'>a</span> <span class='Value'>b</span> <span class='Value'>c</span> <span class='Value'>d</span> <span class='Value'>e</span> </pre> <p>It is impossible to say anything about this sentence! Is <code><span class='Value'>c</span></code> a dyadic operator being applied to <code><span class='Value'>b</span></code> and <code><span class='Value'>d</span></code>, or are <code><span class='Value'>b</span></code> and <code><span class='Value'>d</span></code> two dyadic functions being applied to arrays? In contrast, expressions in C-like or Lisp-like languages show their structure of application:</p> -<pre><span class='Value'>b</span><span class='Paren'>(</span><span class='Value'>a</span><span class='Separator'>,</span> <span class='Value'>d</span><span class='Paren'>(</span><span class='Value'>c</span><span class='Paren'>)(</span><span class='Value'>e</span><span class='Paren'>))</span> -<span class='Paren'>(</span><span class='Value'>b</span> <span class='Value'>a</span> <span class='Paren'>((</span><span class='Value'>d</span> <span class='Value'>c</span><span class='Paren'>)</span> <span class='Value'>e</span><span class='Paren'>))</span> -</pre> -<p>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 <code><span class='Value'>a</span></code> and <code><span class='Value'>e</span></code> are arrays, <code><span class='Value'>b</span></code> and <code><span class='Value'>c</span></code> are functions, and <code><span class='Value'>d</span></code> 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:</p> +<pre><span class='Value'>b</span><span class='Paren'>(</span><span class='Value'>a</span><span class='Separator'>,</span> <span class='Value'>d</span><span class='Paren'>(</span><span class='Value'>c</span><span class='Paren'>)(</span><span class='Value'>e</span><span class='Paren'>))</span> <span class='Comment'># C +</span><span class='Paren'>(</span><span class='Value'>b</span> <span class='Value'>a</span> <span class='Paren'>((</span><span class='Value'>d</span> <span class='Value'>c</span><span class='Paren'>)</span> <span class='Value'>e</span><span class='Paren'>))</span> <span class='Comment'># Lisp +</span></pre> +<p>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 <code><span class='Value'>a</span></code> and <code><span class='Value'>e</span></code> are arrays, <code><span class='Value'>b</span></code> and <code><span class='Value'>c</span></code> are functions, and <code><span class='Value'>d</span></code> 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:</p> <pre><span class='Value'>a</span> <span class='Function'>B</span> <span class='Function'>C</span> <span class='Modifier'>_d</span> <span class='Value'>e</span> </pre> -<p>Here, the lowercase spelling indicates that <code><span class='Value'>a</span></code> and <code><span class='Value'>e</span></code> are to be treated as subjects ("arrays" in APL) while the uppercase spelling of variables <code><span class='Function'>B</span></code> and <code><span class='Function'>C</span></code> are used as functions and <code><span class='Modifier'>_d</span></code> 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 <code><span class='Value'>a</span></code>, <code><span class='Function'>A</span></code>, <code><span class='Modifier'>_a</span></code>, and <code><span class='Modifier2'>_a_</span></code> 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 <code><span class='Value'>a</span></code>, <code><span class='Value'>b</span></code>, <code><span class='Value'>c</span></code>, and so on have, we know how they interact in the line of code above.</p> +<p>Here, the lowercase spelling indicates that <code><span class='Value'>a</span></code> and <code><span class='Value'>e</span></code> are to be treated as subjects ("arrays" in APL) while the uppercase <code><span class='Function'>B</span></code> and <code><span class='Function'>C</span></code> are used as functions and <code><span class='Modifier'>_d</span></code> 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 <code><span class='Value'>a</span></code>, <code><span class='Function'>A</span></code>, <code><span class='Modifier'>_a</span></code>, and <code><span class='Modifier2'>_a_</span></code> refer to the exact same variable. While we still don't know anything about what values <code><span class='Value'>a</span></code>, <code><span class='Value'>b</span></code>, <code><span class='Value'>c</span></code>, and so on have, we know how they interact in the line of code above.</p> <h2 id="is-grammatical-context-really-a-problem"><a class="header" href="#is-grammatical-context-really-a-problem">Is grammatical context really a problem?</a></h2> <p>Yes, in the sense of <a href="../commentary/problems.html">problems with BQN</a>. 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.</p> -<p>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 <code><span class='Value'>⍳⍨</span><span class='Function'>=</span><span class='Value'>⍳</span><span class='Modifier2'>∘</span><span class='Function'>≢</span></code> consists of six largely unfamiliar characters with little to distinguish them (in fact, the one obvious bit of structure, the repeated <code><span class='Value'>⍳</span></code>, is misleading as it means different things in each case!). Simply placing parentheses into the expression, like <code><span class='Paren'>(</span><span class='Value'>⍳⍨</span><span class='Paren'>)</span><span class='Function'>=</span><span class='Paren'>(</span><span class='Value'>⍳</span><span class='Modifier2'>∘</span><span class='Function'>≢</span><span class='Paren'>)</span></code>, 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, <code><span class='Function'>⊐</span><span class='Modifier'>˜</span><span class='Function'>=↕</span><span class='Modifier2'>∘</span><span class='Function'>≠</span></code>, 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 <code><span class='Modifier'>˜</span></code> are 1-modifiers and characters like <code><span class='Modifier2'>∘</span></code> with unbroken circles are 2-modifiers before beginning to learn the BQN grammar that will explain how to tie the various parts together.</p> -<p>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 <a href="functional.html">functional programming</a>, as we'll see later.</p> +<p>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 <code><span class='Value'>⍳⍨</span><span class='Function'>=</span><span class='Value'>⍳</span><span class='Modifier2'>∘</span><span class='Function'>≢</span></code> consists of six largely unfamiliar characters with little to distinguish them (in fact, the one obvious bit of structure, the repeated <code><span class='Value'>⍳</span></code>, is misleading as it means different things in each case!). Simply placing parentheses into the expression, like <code><span class='Paren'>(</span><span class='Value'>⍳⍨</span><span class='Paren'>)</span><span class='Function'>=</span><span class='Paren'>(</span><span class='Value'>⍳</span><span class='Modifier2'>∘</span><span class='Function'>≢</span><span class='Paren'>)</span></code>, 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, <code><span class='Function'>⊐</span><span class='Modifier'>˜</span><span class='Function'>=↕</span><span class='Modifier2'>∘</span><span class='Function'>≠</span></code>, 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 <code><span class='Modifier'>˜</span></code> are 1-modifiers, and characters like <code><span class='Modifier2'>∘</span></code> with unbroken circles are 2-modifiers, to start learning the BQN grammar that tie the various parts together.</p> +<p>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 <a href="functional.html">functional programming</a>, as we'll see later.</p> <p>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 <code><span class='Value'>⍺</span><span class='Gets'>←</span><span class='Function'>⊢</span></code> pattern in a dfn that makes <code><span class='Value'>⍺</span></code> 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 <code><span class='Function'>A</span> <span class='Function'>B</span> <span class='Value'>c</span></code>, <code><span class='Function'>B</span></code> is a function and <code><span class='Value'>c</span></code> is an array, and both values are known to be constant. If <code><span class='Function'>A</span></code> is known to be a function (even if its value is not yet known), its right argument <code><span class='Function'>B</span> <span class='Value'>c</span></code> can be evaluated ahead of time. But if <code><span class='Function'>A</span></code>'s type isn't known, it's impossible to know if this optimization is worth it, because if it is an array, <code><span class='Function'>B</span></code> will instead be called dyadically.</p> <h2 id="bqns-spelling-system"><a class="header" href="#bqns-spelling-system">BQN's spelling system</a></h2> <p>BQN's <a href="expression.html">expression grammar</a> 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:</p> @@ -54,15 +55,15 @@ </tr> </tbody> </table> -<p>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 <code><span class='Modifier'>˜¨˘⁼⌜´˝`</span></code> are used for 1-modifiers, and glyphs <code><span class='Modifier2'>∘○⊸⟜⌾⊘◶⚇⎉⍟</span></code> with an unbroken circle are 2-modifiers. Other primitives are functions. String and numeric literals are subjects.</p> +<p>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 <code><span class='Modifier'>˙˜˘¨⌜⁼´˝`</span></code> are used for 1-modifiers, and glyphs <code><span class='Modifier2'>∘○⊸⟜⌾⊘◶⎉⚇⍟⎊</span></code> with an unbroken circle are 2-modifiers. Other primitives are functions. String and numeric literals are subjects.</p> <p>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 <code><span class='Value'>var</span></code>, is a subject. Spelled with an uppercase first letter, like <code><span class='Function'>Var</span></code>, it is a function. Underscores are placed where operands apply to indicate a 1-modifier <code><span class='Modifier'>_var</span></code> or 2-modifier <code><span class='Modifier2'>_var_</span></code>. Other than the first letter or underscore, variables are case-insensitive.</p> <p>The associations between spelling and syntactic role are considered part of BQN's <a href="../spec/token.html">token formation rules</a>.</p> -<p>One rule for typing is also best considered to be a pre-parsing rule like the spelling system: the role of a brace construct <code><span class='Brace'>{}</span></code> with no header is determined by which special arguments it uses: it's a subject if there are none, but a <code><span class='Value'>𝕨</span></code> or <code><span class='Value'>𝕩</span></code> makes it at least a function, an <code><span class='Function'>𝔽</span></code> makes it a 1- or 2-modifier, and a <code><span class='Function'>𝔾</span></code> always makes it a 2-modifier.</p> -<p>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…</p> +<p>One rule for typing is also best considered to be a pre-parsing rule like the spelling system: the role of a headerless <a href="block.html">block</a> <code><span class='Brace'>{}</span></code> is determined by which special arguments it uses: it's a subject if there aren't any, but a <code><span class='Value'>𝕨</span></code> or <code><span class='Value'>𝕩</span></code> makes it at least a function, an <code><span class='Function'>𝔽</span></code> makes it a 1- or 2-modifier, and a <code><span class='Function'>𝔾</span></code> always makes it a 2-modifier.</p> +<p>The syntactic role is a property of an expression, and BQN's grammar determines how roles interact in expressions. But <a href="types.html">type</a> 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…</p> <h2 id="mixing-roles"><a class="header" href="#mixing-roles">Mixing roles</a></h2> <p>BQN's value types align closely with its syntactic roles: functions, 1-modifiers, and 2-modifiers are all types (<em>operation</em> types) as well as roles, while the other types (<em>data</em> 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.</p> <p>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 <a href="functional.html">functional programming</a>, where functions can be used as first-class entities.</p> -<p>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, <code><span class='Function'>F</span><span class='Modifier2'>⎉</span><span class='Number'>1</span></code> uses a constant for the rank even though in general a function can be given, and if <code><span class='Value'>a</span></code> is an array then <code><span class='Value'>a</span><span class='Modifier2'>⌾</span><span class='Paren'>(</span><span class='Value'>b</span><span class='Modifier2'>⊸</span><span class='Function'>/</span><span class='Paren'>)</span></code> inserts the values in <code><span class='Value'>a</span></code> into the positions selected by <code><span class='Value'>b</span></code>, ignoring the old values rather than applying a function to them.</p> -<p>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.</p> -<p>It's also worth noting that a subject may unexpectedly be a function! For example, the result of <code><span class='Value'>𝕨</span><span class='Modifier'>˜</span><span class='Value'>𝕩</span></code> may not always be <code><span class='Value'>𝕨</span></code>. <code><span class='Value'>𝕨</span><span class='Modifier'>˜</span><span class='Value'>𝕩</span></code> is exactly identical to <code><span class='Function'>𝕎</span><span class='Modifier'>˜</span><span class='Value'>𝕩</span></code>, which gives <code><span class='Value'>𝕩</span><span class='Function'>𝕎</span><span class='Value'>𝕩</span></code>. If <code><span class='Function'>𝕎</span></code> is a number, character, or array, that's the same as <code><span class='Value'>𝕨</span></code>, but if it is a function, then it will be applied.</p> -<p>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 <code><span class='Brace'>{</span><span class='Function'>𝔽</span><span class='Brace'>}</span></code> 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 <code><span class='Function'>⊑</span><span class='Bracket'>⟨</span><span class='Function'>+</span><span class='Bracket'>⟩</span></code>, will give it as a subject.</p> +<p>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, <code><span class='Function'>F</span><span class='Modifier2'>⎉</span><span class='Number'>1</span></code> has a constant for the rank even though in general a function can be given, and if <code><span class='Value'>a</span></code> is an array then <code><span class='Value'>a</span><span class='Modifier2'>⌾</span><span class='Paren'>(</span><span class='Value'>b</span><span class='Modifier2'>⊸</span><span class='Function'>/</span><span class='Paren'>)</span></code> inserts the values in <code><span class='Value'>a</span></code> into the positions selected by <code><span class='Value'>b</span></code>, ignoring the old values rather than applying a function to them.</p> +<p>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.</p> +<p>It's also worth noting that a subject may unexpectedly be a function! For example, the result of <code><span class='Value'>𝕨</span><span class='Modifier'>˜</span><span class='Value'>𝕩</span></code> may not always be <code><span class='Value'>𝕨</span></code>. <code><span class='Value'>𝕨</span><span class='Modifier'>˜</span><span class='Value'>𝕩</span></code> is exactly identical to <code><span class='Function'>𝕎</span><span class='Modifier'>˜</span><span class='Value'>𝕩</span></code>, which gives <code><span class='Value'>𝕩</span><span class='Function'>𝕎</span><span class='Value'>𝕩</span></code>. If <code><span class='Function'>𝕎</span></code> is a number, character, or array, that's the same as <code><span class='Value'>𝕨</span></code>, but if it is a function, then it will be applied. The <a href="constant.html">Constant</a> (<code><span class='Modifier'>˙</span></code>) modifier keeps a function from being applied when that isn't wanted.</p> +<p>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 <code><span class='Brace'>{</span><span class='Function'>𝔽</span><span class='Brace'>}</span></code> 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 <code><span class='Function'>⊑</span><span class='Bracket'>⟨</span><span class='Function'>+</span><span class='Bracket'>⟩</span></code>, will give it as a subject.</p> 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 @@ </head> <div class="nav">(<a href="https://github.com/mlochbaum/BQN">github</a>) / <a href="../index.html">BQN</a> / <a href="index.html">doc</a></div> <h1 id="control-flow-in-bqn"><a class="header" href="#control-flow-in-bqn">Control flow in BQN</a></h1> -<p>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.</p> +<p>BQN does not have ALGOL-style control structures. Instead, <a href="functional.html">functional</a> 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.</p> <p>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.</p> <p>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).</p> -<p>The useful control structures introduced here are collected as shortened definitions below. <code><span class='Function'>While</span></code> uses the slightly more complicated implementation that avoids stack overflow, and <code><span class='Function'>DoWhile</span></code> and <code><span class='Function'>For</span></code> 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.</p> +<p>The most useful control structures introduced here are collected as shortened definitions below. <code><span class='Function'>While</span></code> uses the slightly more complicated implementation that avoids stack overflow, and <code><span class='Function'>DoWhile</span></code> and <code><span class='Function'>For</span></code> 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.</p> <pre><span class='Function'>If</span> <span class='Gets'>←</span> <span class='Brace'>{</span><span class='Function'>𝕏</span><span class='Modifier2'>⍟</span><span class='Function'>𝕎</span><span class='String'>@</span><span class='Brace'>}</span><span class='Modifier'>´</span> <span class='Comment'># Also Repeat </span><span class='Function'>IfElse</span> <span class='Gets'>←</span> <span class='Brace'>{</span><span class='Value'>c</span><span class='Ligature'>‿</span><span class='Function'>T</span><span class='Ligature'>‿</span><span class='Function'>F</span><span class='Head'>:</span> <span class='Value'>c</span><span class='Modifier2'>◶</span><span class='Function'>F</span><span class='Ligature'>‿</span><span class='Function'>T</span><span class='String'>@</span><span class='Brace'>}</span> <span class='Function'>While</span> <span class='Gets'>←</span> <span class='Brace'>{</span><span class='Value'>𝕩</span><span class='Brace'>{</span><span class='Function'>𝔽</span><span class='Modifier2'>⍟</span><span class='Function'>𝔾</span><span class='Modifier2'>∘</span><span class='Function'>𝔽</span><span class='Modifier2'>_𝕣_</span><span class='Function'>𝔾</span><span class='Modifier2'>∘</span><span class='Function'>𝔽</span><span class='Modifier2'>⍟</span><span class='Function'>𝔾</span><span class='Value'>𝕩</span><span class='Brace'>}</span><span class='Value'>𝕨</span><span class='String'>@</span><span class='Brace'>}</span><span class='Modifier'>´</span> <span class='Comment'># While 1‿{... to run forever @@ -18,23 +18,23 @@ <span class='Comment'># Switch/case statements have many variations; these are a few </span><span class='Function'>Match</span> <span class='Gets'>←</span> <span class='Brace'>{</span><span class='Function'>𝕏</span><span class='Value'>𝕨</span><span class='Brace'>}</span><span class='Modifier'>´</span> <span class='Function'>Select</span> <span class='Gets'>←</span> <span class='Brace'>{</span><span class='Paren'>(</span><span class='Function'>⊑</span><span class='Value'>𝕩</span><span class='Paren'>)</span><span class='Modifier2'>◶</span><span class='Paren'>(</span><span class='Number'>1</span><span class='Function'>↓</span><span class='Value'>𝕩</span><span class='Paren'>)</span><span class='String'>@</span><span class='Brace'>}</span> -<span class='Function'>Switch</span> <span class='Gets'>←</span> <span class='Brace'>{</span><span class='Value'>c</span><span class='Gets'>←</span><span class='Function'>⊑</span><span class='Value'>𝕩</span> <span class='Separator'>⋄</span> <span class='Value'>m</span><span class='Ligature'>‿</span><span class='Value'>a</span><span class='Gets'>←</span><span class='Function'><</span><span class='Modifier'>˘</span><span class='Function'>⍉</span><span class='Modifier2'>∘</span><span class='Ligature'>‿</span><span class='Number'>2</span><span class='Function'>⥊</span><span class='Number'>1</span><span class='Function'>↓</span><span class='Value'>𝕩</span> <span class='Separator'>⋄</span> <span class='Paren'>(</span><span class='Value'>m</span><span class='Modifier2'>⊸</span><span class='Function'>⊐</span><span class='Modifier2'>⌾</span><span class='Function'><C</span><span class='Paren'>)</span><span class='Modifier2'>◶</span><span class='Value'>a</span><span class='String'>@</span><span class='Brace'>}</span> +<span class='Function'>Switch</span> <span class='Gets'>←</span> <span class='Brace'>{</span><span class='Value'>c</span><span class='Gets'>←</span><span class='Function'>⊑</span><span class='Value'>𝕩</span> <span class='Separator'>⋄</span> <span class='Bracket'>[</span><span class='Value'>m</span><span class='Separator'>,</span><span class='Value'>a</span><span class='Bracket'>]</span><span class='Gets'>←</span><span class='Function'>⍉</span><span class='Modifier2'>∘</span><span class='Ligature'>‿</span><span class='Number'>2</span><span class='Function'>⥊</span><span class='Number'>1</span><span class='Function'>↓</span><span class='Value'>𝕩</span> <span class='Separator'>⋄</span> <span class='Paren'>(</span><span class='Value'>m</span><span class='Modifier2'>⊸</span><span class='Function'>⊐</span><span class='Modifier2'>⌾</span><span class='Function'><C</span><span class='Paren'>)</span><span class='Modifier2'>◶</span><span class='Value'>a</span><span class='String'>@</span><span class='Brace'>}</span> <span class='Function'>Test</span> <span class='Gets'>←</span> <span class='Brace'>{</span><span class='Value'>fn</span><span class='Gets'>←</span><span class='Brace'>{</span><span class='Function'>C</span><span class='Ligature'>‿</span><span class='Function'>A𝕊</span><span class='Value'>e</span><span class='Head'>:</span><span class='Function'>C</span><span class='Modifier2'>◶</span><span class='Function'>A</span><span class='Ligature'>‿</span><span class='Function'>E</span><span class='Brace'>}</span><span class='Modifier'>´</span><span class='Value'>𝕩</span><span class='Separator'>⋄</span><span class='Function'>Fn</span><span class='String'>@</span><span class='Brace'>}</span> </pre> <h2 id="blocks-and-functions"><a class="header" href="#blocks-and-functions">Blocks and functions</a></h2> -<p>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 <a href="lexical.html">lexical scoping</a> as a tool for encapsulation. Instead, the main tool we will use to get control structures is the block function.</p> +<p>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 <a href="block.html">block</a>, 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 <a href="lexical.html">lexical scoping</a> as a tool for encapsulation. Instead, the main tool we will use to get control structures is the block function.</p> <p>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:</p> <ul> <li>Pass <code><span class='String'>@</span></code> to a function that ignores its argument. It's a nice signal that nothing is happening and is easy to type.</li> <li>A headerless function that doesn't use an argument will be interpreted as an immediate block by default. Start it with the line <code><span class='Value'>𝕤</span></code> to avoid this (it's an instruction to navel gaze: the function contemplates its self, but does nothing about it). Other options like <code><span class='Function'>𝕊</span><span class='Head'>:</span></code>, <code><span class='Function'>F</span><span class='Head'>:</span></code>, or <code><span class='Value'>𝕩</span></code> also work, but are more visually distracting.</li> </ul> -<p>Even with these workarounds, BQN's "niladic" function syntax is quite lightweight, comparing favorably to a low-boilerplate language like Javascript.</p> +<p>Even with these workarounds, BQN's "niladic" function syntax is lightweight, comparing favorably to a low-boilerplate language like Javascript.</p> <pre><span class='Value'>fn</span> <span class='Function'>=</span> <span class='Paren'>()</span><span class='Function'>=></span><span class='Brace'>{</span><span class='Value'>m</span><span class='Function'>+=</span><span class='Number'>1</span><span class='Head'>;</span><span class='Value'>n*</span><span class='Function'>=</span><span class='Number'>2</span><span class='Brace'>}</span><span class='Head'>;</span> <span class='Value'>fn</span><span class='Paren'>()</span> <span class='Function'>Fn</span> <span class='Gets'>←</span> <span class='Brace'>{</span><span class='Value'>𝕤</span><span class='Separator'>⋄</span> <span class='Value'>m</span><span class='Function'>+</span><span class='Gets'>↩</span><span class='Number'>1</span><span class='Separator'>,</span><span class='Value'>n</span><span class='Function'>×</span><span class='Gets'>↩</span><span class='Number'>2</span><span class='Brace'>}</span><span class='Separator'>,</span> <span class='Function'>Fn</span> <span class='String'>@</span> </pre> <p>Control structures are called "statements" below to match common usage, but they are actually expressions, and return a value that might be used later.</p> <h2 id="if"><a class="header" href="#if">If</a></h2> -<p>The if statement conditionally performs some action. It is similar to the Repeat (<code><span class='Modifier2'>⍟</span></code>) modifier with a right operand returning a boolean: <code><span class='Function'>Fn</span><span class='Modifier2'>⍟</span><span class='Function'>Cond</span> <span class='Value'>𝕩</span></code> gives <code><span class='Function'>Fn</span> <span class='Value'>𝕩</span></code> if <code><span class='Function'>Cond</span> <span class='Value'>𝕩</span></code> is <code><span class='Number'>1</span></code>, and returns <code><span class='Value'>𝕩</span></code> without calling <code><span class='Function'>Fn</span></code> if <code><span class='Function'>Cond</span> <span class='Value'>𝕩</span></code> is <code><span class='Number'>0</span></code>. Here is how we might make it behave like a control structure.</p> +<p>The if statement conditionally performs some action. It's similar to the <a href="repeat.html">Repeat</a> (<code><span class='Modifier2'>⍟</span></code>) modifier with a right operand that returns a boolean: <code><span class='Function'>Fn</span><span class='Modifier2'>⍟</span><span class='Function'>Cond</span> <span class='Value'>𝕩</span></code> gives <code><span class='Function'>Fn</span> <span class='Value'>𝕩</span></code> if <code><span class='Function'>Cond</span> <span class='Value'>𝕩</span></code> is <code><span class='Number'>1</span></code>, and returns <code><span class='Value'>𝕩</span></code> without calling <code><span class='Function'>Fn</span></code> if <code><span class='Function'>Cond</span> <span class='Value'>𝕩</span></code> is <code><span class='Number'>0</span></code>. Here's how we might make it behave like a control structure.</p> <pre><span class='Brace'>{</span><span class='Value'>𝕤</span><span class='Separator'>⋄</span><span class='Value'>a</span><span class='Function'>+</span><span class='Gets'>↩</span><span class='Number'>10</span><span class='Brace'>}</span><span class='Modifier2'>⍟</span><span class='Paren'>(</span><span class='Value'>a</span><span class='Function'><</span><span class='Number'>10</span><span class='Paren'>)</span> <span class='String'>@</span> </pre> <p>The condition <code><span class='Value'>a</span><span class='Function'><</span><span class='Number'>10</span></code> is always evaluated, so there's no need to wrap it in a function. However, the function <code><span class='Brace'>{</span><span class='Value'>𝕤</span><span class='Separator'>⋄</span><span class='Value'>a</span><span class='Function'><</span><span class='Number'>10</span><span class='Brace'>}</span></code> could be used in place of <code><span class='Paren'>(</span><span class='Value'>a</span><span class='Function'><</span><span class='Number'>10</span><span class='Paren'>)</span></code>, making the entire structure into a function that could be incorporated into other control structures.</p> @@ -48,21 +48,21 @@ <span class='Brace'>}</span> </pre> <p>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 <code><span class='String'>@</span></code> or <code><span class='Number'>10</span></code> here.</p> -<p>BQN's syntax for a pure if statement isn't so good, but predicates handle <a href="#if-else">if-else</a> statements nicely. So in most cases you'd forego the definitions above in favor of an if-else with nothing in the else branch:</p> +<p>BQN's syntax for a pure if statement isn't so good, but <a href="block.html#predicates">predicates</a> handle <a href="#if-else">if-else</a> statements nicely. So in most cases you'd forego the definitions above in favor of an if-else with nothing in the else branch:</p> <pre><span class='Brace'>{</span> <span class='Value'>a</span><span class='Function'><</span><span class='Number'>10</span> <span class='Head'>?</span> <span class='Value'>a</span><span class='Function'>+</span><span class='Gets'>↩</span><span class='Number'>10</span> <span class='Head'>;</span> <span class='String'>@</span> <span class='Brace'>}</span> </pre> <h2 id="repeat"><a class="header" href="#repeat">Repeat</a></h2> <p>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.</p> <p>Another option is to use a <a href="#for">for-each</a> statement with an argument of <code><span class='Function'>↕</span><span class='Value'>n</span></code>: in this case the result is the list of each action's result.</p> <h2 id="if-else"><a class="header" href="#if-else">If-Else</a></h2> -<p>In most cases, the easy way to write an if-else statement is with <a href="block.html#predicates">predicates</a>:</p> +<p>In most cases, the easy way to write an if-else statement is with a <a href="block.html#predicates">predicate</a>:</p> <pre><span class='Brace'>{</span> <span class='Value'>threshold</span> <span class='Function'><</span> <span class='Number'>6</span> <span class='Head'>?</span> <span class='Value'>a</span> <span class='Gets'>↩</span> <span class='Function'>Small</span> <span class='Value'>threshold</span> <span class='Head'>;</span> <span class='Comment'># If predicate was true </span> <span class='Value'>b</span> <span class='Gets'>↩</span> <span class='Number'>1</span> <span class='Function'>Large</span> <span class='Value'>threshold</span> <span class='Comment'># If it wasn't </span><span class='Brace'>}</span> </pre> -<p>We might also think of an if-else statement as a kind of <a href="#switch-case">switch-case</a> statement, where the two cases are true (<code><span class='Number'>1</span></code>) and false (<code><span class='Number'>0</span></code>). As a result, we can implement it either with Choose (<code><span class='Modifier2'>◶</span></code>) or with <a href="block.html#case-headers">case headers</a> of <code><span class='Number'>1</span></code> and <code><span class='Number'>0</span></code>.</p> +<p>We might also think of an if-else statement as a kind of <a href="#switch-case">switch-case</a> statement, where the two cases are true (<code><span class='Number'>1</span></code>) and false (<code><span class='Number'>0</span></code>). As a result, we can implement it either with <a href="choose.html">Choose</a> (<code><span class='Modifier2'>◶</span></code>) or with <a href="block.html#case-headers">case headers</a> of <code><span class='Number'>1</span></code> and <code><span class='Number'>0</span></code>.</p> <p>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.</p> <pre><span class='Function'>IfElse</span> <span class='Gets'>←</span> <span class='Brace'>{</span><span class='Value'>cond</span><span class='Ligature'>‿</span><span class='Function'>True</span><span class='Ligature'>‿</span><span class='Function'>False</span><span class='Head'>:</span> <span class='Value'>cond</span><span class='Modifier2'>◶</span><span class='Function'>False</span><span class='Ligature'>‿</span><span class='Function'>True</span> <span class='String'>@</span><span class='Brace'>}</span> @@ -99,7 +99,7 @@ <span class='Function'>Test</span> <span class='Bracket'>⟨</span> <span class='Paren'>(</span> <span class='Value'>a</span><span class='Function'><</span><span class='Value'>b</span><span class='Paren'>)</span><span class='Ligature'>‿</span><span class='Brace'>{</span><span class='Value'>𝕤</span><span class='Separator'>⋄</span><span class='Value'>a</span><span class='Function'>+</span><span class='Gets'>↩</span><span class='Number'>1</span><span class='Brace'>}</span> <span class='Brace'>{</span><span class='Value'>𝕤</span><span class='Separator'>⋄</span><span class='Value'>a</span><span class='Function'><</span><span class='Value'>c</span><span class='Brace'>}</span><span class='Ligature'>‿</span><span class='Brace'>{</span><span class='Value'>𝕤</span><span class='Separator'>⋄</span><span class='Value'>c</span><span class='Function'>-</span><span class='Gets'>↩</span><span class='Number'>1</span><span class='Brace'>}</span> - <span class='Brace'>{</span><span class='Value'>𝕤</span><span class='Separator'>⋄</span><span class='Value'>a</span><span class='Function'>-</span><span class='Gets'>↩</span><span class='Number'>2</span><span class='Brace'>}</span> + <span class='Brace'>{</span><span class='Value'>𝕤</span><span class='Separator'>⋄</span><span class='Value'>a</span><span class='Function'>-</span><span class='Gets'>↩</span><span class='Number'>2</span><span class='Brace'>}</span> <span class='Bracket'>⟩</span> </pre> <h2 id="switch-case"><a class="header" href="#switch-case">Switch-Case</a></h2> @@ -114,7 +114,7 @@ <span class='Value'>𝕩</span><span class='Head'>:</span> <span class='Value'>n</span><span class='Function'>∾</span><span class='Gets'>↩</span><span class='Value'>𝕩</span> <span class='Brace'>}</span> </pre> -<p>A simplified version of a switch-case statement is possible if the cases are natural numbers <code><span class='Number'>0</span></code>, <code><span class='Number'>1</span></code>, and so on. The Choose (<code><span class='Modifier2'>◶</span></code>) modifier does just what we want. The <code><span class='Function'>Select</span></code> statement below generalizes <code><span class='Function'>IfElse</span></code>, except that it doesn't rearrange the cases relative to Choose while <code><span class='Function'>IfElse</span></code> swaps them.</p> +<p>A simplified version of a switch-case statement is possible if the cases are natural numbers <code><span class='Number'>0</span></code>, <code><span class='Number'>1</span></code>, and so on. The <a href="choose.html">Choose</a> (<code><span class='Modifier2'>◶</span></code>) modifier does just what we want. The <code><span class='Function'>Select</span></code> statement below generalizes <code><span class='Function'>IfElse</span></code>, except that it doesn't rearrange the cases relative to Choose while <code><span class='Function'>IfElse</span></code> swaps them.</p> <pre><span class='Function'>Select</span> <span class='Gets'>←</span> <span class='Brace'>{</span><span class='Paren'>(</span><span class='Function'>⊑</span><span class='Value'>𝕩</span><span class='Paren'>)</span><span class='Modifier2'>◶</span><span class='Paren'>(</span><span class='Number'>1</span><span class='Function'>↓</span><span class='Value'>𝕩</span><span class='Paren'>)</span><span class='String'>@</span><span class='Brace'>}</span> <span class='Function'>Select</span> <span class='Value'>number</span><span class='Ligature'>‿</span><span class='Brace'>{</span> @@ -126,7 +126,7 @@ <span class='Brace'>}</span> </pre> <p>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 <code><span class='Function'>⊐</span></code>.</p> -<pre><span class='Function'>Switch</span> <span class='Gets'>←</span> <span class='Brace'>{</span><span class='Value'>c</span><span class='Gets'>←</span><span class='Function'>⊑</span><span class='Value'>𝕩</span> <span class='Separator'>⋄</span> <span class='Value'>m</span><span class='Ligature'>‿</span><span class='Value'>a</span><span class='Gets'>←</span><span class='Function'><</span><span class='Modifier'>˘</span><span class='Function'>⍉</span><span class='Modifier2'>∘</span><span class='Ligature'>‿</span><span class='Number'>2</span><span class='Function'>⥊</span><span class='Number'>1</span><span class='Function'>↓</span><span class='Value'>𝕩</span> <span class='Separator'>⋄</span> <span class='Paren'>(</span><span class='Value'>m</span><span class='Modifier2'>⊸</span><span class='Function'>⊐</span><span class='Modifier2'>⌾</span><span class='Function'><C</span><span class='Paren'>)</span><span class='Modifier2'>◶</span><span class='Value'>a</span><span class='String'>@</span><span class='Brace'>}</span> +<pre><span class='Function'>Switch</span> <span class='Gets'>←</span> <span class='Brace'>{</span><span class='Value'>c</span><span class='Gets'>←</span><span class='Function'>⊑</span><span class='Value'>𝕩</span> <span class='Separator'>⋄</span> <span class='Bracket'>[</span><span class='Value'>m</span><span class='Separator'>,</span><span class='Value'>a</span><span class='Bracket'>]</span><span class='Gets'>←</span><span class='Function'>⍉</span><span class='Modifier2'>∘</span><span class='Ligature'>‿</span><span class='Number'>2</span><span class='Function'>⥊</span><span class='Number'>1</span><span class='Function'>↓</span><span class='Value'>𝕩</span> <span class='Separator'>⋄</span> <span class='Paren'>(</span><span class='Value'>m</span><span class='Modifier2'>⊸</span><span class='Function'>⊐</span><span class='Modifier2'>⌾</span><span class='Function'><C</span><span class='Paren'>)</span><span class='Modifier2'>◶</span><span class='Value'>a</span><span class='String'>@</span><span class='Brace'>}</span> <span class='Function'>Switch</span> <span class='Bracket'>⟨</span><span class='Value'>value</span> <span class='String'>"increment"</span> <span class='Separator'>⋄</span> <span class='Brace'>{</span><span class='Value'>𝕤</span><span class='Separator'>⋄</span> <span class='Value'>v</span><span class='Function'>+</span><span class='Gets'>↩</span><span class='Number'>1</span><span class='Brace'>}</span> @@ -137,13 +137,13 @@ </pre> <p>Finally, the most general form of a switch statement is a <a href="#chained-if-else">chained if-else</a>!</p> <h2 id="loop-forever"><a class="header" href="#loop-forever">Loop forever</a></h2> -<p>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 <code><span class='Value'>𝕨</span><span class='Function'>𝕊</span><span class='Value'>𝕩</span></code> to the end:</p> +<p>It's not a particularly common pattern, but this is a good simple case to warm up for the while loop. BQN <a href="primitive.html">primitives</a> 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 <code><span class='Value'>𝕨</span><span class='Function'>𝕊</span><span class='Value'>𝕩</span></code> to the end:</p> <pre><span class='Brace'>{</span> <span class='Comment'># Stuff to do forever </span> <span class='Value'>𝕨</span><span class='Function'>𝕊</span><span class='Value'>𝕩</span> <span class='Brace'>}</span> <span class='Value'>arg</span> </pre> -<p>To convert this to a control structure format, we want to take an action <code><span class='Function'>A</span></code>, and produce a function that runs <code><span class='Function'>A</span></code>, then runs itself. Finally we want to call that function on some argument, say <code><span class='String'>@</span></code>. The argument is a single function, so to call Forever, we need to convert that function to a subject role.</p> +<p>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 <code><span class='Function'>A</span></code>, and produce a function that runs <code><span class='Function'>A</span></code>, then runs itself. Finally we want to call that function on some argument, say <code><span class='String'>@</span></code>. The argument is a single function, so to call <code><span class='Function'>Forever</span></code>, we need to convert that function to a subject role.</p> <pre><span class='Function'>Forever</span> <span class='Gets'>←</span> <span class='Brace'>{</span><span class='Function'>𝕊</span><span class='Value'>a</span><span class='Head'>:</span><span class='Brace'>{</span><span class='Function'>𝕊A</span><span class='Value'>𝕩</span><span class='Brace'>}</span><span class='String'>@</span><span class='Brace'>}</span> <span class='Function'>Forever</span> <span class='Number'>1</span><span class='Function'>⊑</span><span class='String'>@</span><span class='Ligature'>‿</span><span class='Brace'>{</span><span class='Value'>𝕤</span> @@ -153,7 +153,7 @@ <p>A slicker method is to pass <code><span class='Value'>𝕩</span></code> as an operand to a modifier. In a modifier, <code><span class='Function'>𝕊</span></code> has the operands built in (just like <code><span class='Brace'>{</span><span class='Function'>𝕊A</span><span class='Value'>𝕩</span><span class='Brace'>}</span></code> above has the environment containing <code><span class='Function'>A</span></code> built in), so it will work the same way with no need for an explicit variable assignment.</p> <pre><span class='Function'>Forever</span> <span class='Gets'>←</span> <span class='Brace'>{</span><span class='Value'>𝕩</span><span class='Brace'>{</span><span class='Function'>𝕊𝔽</span><span class='Value'>𝕩</span><span class='Brace'>}</span><span class='String'>@</span><span class='Brace'>}</span> </pre> -<p>The syntax here is awkward enough that it's actually better to use a while loop, with a constant condition of <code><span class='Number'>1</span></code>!</p> +<p>But the calling syntax is awkward enough that it's actually better to use a while loop, with a constant condition of <code><span class='Number'>1</span></code>!</p> <pre><span class='Function'>While</span> <span class='Number'>1</span><span class='Ligature'>‿</span><span class='Brace'>{</span><span class='Value'>𝕤</span> <span class='Comment'># Stuff to do forever </span><span class='Brace'>}</span> @@ -174,9 +174,9 @@ <p>The above version of <code><span class='Function'>While</span></code> 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 <code><span class='Function'>𝕊</span><span class='Modifier2'>∘</span><span class='Function'>𝔾</span><span class='Modifier2'>⍟</span><span class='Function'>𝔽</span></code> 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:</p> <pre><span class='Function'>While</span> <span class='Gets'>←</span> <span class='Brace'>{</span><span class='Value'>𝕩</span><span class='Brace'>{</span><span class='Function'>𝔽</span><span class='Modifier2'>⍟</span><span class='Function'>𝔾</span><span class='Modifier2'>∘</span><span class='Function'>𝔽</span><span class='Modifier2'>_𝕣_</span><span class='Function'>𝔾</span><span class='Modifier2'>∘</span><span class='Function'>𝔽</span><span class='Modifier2'>⍟</span><span class='Function'>𝔾</span><span class='Value'>𝕩</span><span class='Brace'>}</span><span class='Value'>𝕨</span><span class='String'>@</span><span class='Brace'>}</span><span class='Modifier'>´</span> </pre> -<p>The innovation is to use <code><span class='Brace'>{</span><span class='Function'>𝔽</span><span class='Modifier2'>⍟</span><span class='Function'>𝔾</span><span class='Modifier2'>∘</span><span class='Function'>𝔽</span><span class='Modifier2'>_𝕣_</span><span class='Function'>𝔾</span><span class='Modifier2'>∘</span><span class='Function'>𝔽</span><span class='Modifier2'>⍟</span><span class='Function'>𝔾</span><span class='Value'>𝕩</span><span class='Brace'>}</span></code> instead of the equivalent <code><span class='Brace'>{</span><span class='Function'>𝔽</span><span class='Modifier2'>_𝕣_</span><span class='Function'>𝔾</span><span class='Modifier2'>∘</span><span class='Function'>𝔽</span><span class='Modifier2'>⍟</span><span class='Function'>𝔾</span><span class='Value'>𝕩</span><span class='Brace'>}</span></code> or <code><span class='Brace'>{</span><span class='Function'>𝕊</span><span class='Modifier2'>∘</span><span class='Function'>𝔽</span><span class='Modifier2'>⍟</span><span class='Function'>𝔾</span><span class='Value'>𝕩</span><span class='Brace'>}</span></code> (these are the same, as <code><span class='Function'>𝕊</span></code> in a modifier is defined as <code><span class='Function'>𝔽</span><span class='Modifier2'>_𝕣_</span><span class='Function'>𝔾</span></code>). Here <code><span class='Function'>𝔽</span></code> performs one iteration and <code><span class='Function'>𝔾</span></code> tests whether to continue. The simplest approach is to perform one iteration and recurse with the same two functions. The modified approach replaces <code><span class='Function'>𝔽</span></code> with <code><span class='Function'>𝔽</span><span class='Modifier2'>⍟</span><span class='Function'>𝔾</span><span class='Modifier2'>∘</span><span class='Function'>𝔽</span></code>, that is, it doubles it while making sure the condition is still checked each iteration. The doublings compound so that recursion level <code><span class='Value'>n</span></code> performs <code><span class='Function'>𝔽</span></code> up to <code><span class='Number'>2</span><span class='Function'>⋆</span><span class='Value'>n</span></code> times while using on the order of <code><span class='Value'>n</span></code> additional stack frames. Only a hundred or two stack frames are needed to give a practically unlimited number of iterations.</p> +<p>The innovation is to use <code><span class='Brace'>{</span><span class='Function'>𝔽</span><span class='Modifier2'>⍟</span><span class='Function'>𝔾</span><span class='Modifier2'>∘</span><span class='Function'>𝔽</span><span class='Modifier2'>_𝕣_</span><span class='Function'>𝔾</span><span class='Modifier2'>∘</span><span class='Function'>𝔽</span><span class='Modifier2'>⍟</span><span class='Function'>𝔾</span><span class='Value'>𝕩</span><span class='Brace'>}</span></code> instead of the equivalent <code><span class='Brace'>{</span><span class='Function'>𝔽</span><span class='Modifier2'>_𝕣_</span><span class='Function'>𝔾</span><span class='Modifier2'>∘</span><span class='Function'>𝔽</span><span class='Modifier2'>⍟</span><span class='Function'>𝔾</span><span class='Value'>𝕩</span><span class='Brace'>}</span></code> or <code><span class='Brace'>{</span><span class='Function'>𝕊</span><span class='Modifier2'>∘</span><span class='Function'>𝔽</span><span class='Modifier2'>⍟</span><span class='Function'>𝔾</span><span class='Value'>𝕩</span><span class='Brace'>}</span></code> (these are the same, as <code><span class='Function'>𝕊</span></code> in a modifier is defined to be <code><span class='Function'>𝔽</span><span class='Modifier2'>_𝕣_</span><span class='Function'>𝔾</span></code>). Here <code><span class='Function'>𝔽</span></code> performs one iteration and <code><span class='Function'>𝔾</span></code> tests whether to continue. The simplest approach is to perform one iteration, then recurse with the same two functions. The modified approach replaces <code><span class='Function'>𝔽</span></code> with <code><span class='Function'>𝔽</span><span class='Modifier2'>⍟</span><span class='Function'>𝔾</span><span class='Modifier2'>∘</span><span class='Function'>𝔽</span></code>, that is, it doubles it while making sure the condition is still checked each iteration. The doublings compound so that recursion level <code><span class='Value'>n</span></code> performs <code><span class='Function'>𝔽</span></code> up to <code><span class='Number'>2</span><span class='Function'>⋆</span><span class='Value'>n</span></code> times while using on the order of <code><span class='Value'>n</span></code> additional stack frames. Only a hundred or two stack frames are needed to give a practically unlimited number of iterations.</p> <h2 id="for"><a class="header" href="#for">For</a></h2> -<p>To begin with, are you sure you don't want a for-each loop instead? In BQN that's just a function with Each (<code><span class='Modifier'>¨</span></code>), and it covers most common uses of a for loop.</p> +<p>To begin with, are you sure you don't want a for-each loop instead? In BQN that's just a function with <a href="map.html">Each</a> (<code><span class='Modifier'>¨</span></code>), and it covers most common uses of a for loop.</p> <pre><span class='Function'>Fn</span><span class='Modifier'>¨</span> <span class='Value'>v</span> <span class='Comment'># for (𝕩 in v) </span><span class='Function'>Fn</span><span class='Modifier'>¨</span> <span class='Function'>↕</span><span class='Value'>n</span> <span class='Comment'># for (𝕩=0; 𝕩<n; 𝕩++) </span><span class='Function'>Fn</span><span class='Modifier'>¨</span> <span class='Value'>k</span><span class='Function'>↓↕</span><span class='Value'>n</span> <span class='Comment'># for (𝕩=k; 𝕩<n; 𝕩++) with 0≤k @@ -194,8 +194,8 @@ <span class='Brace'>}</span> <span class='Brace'>}</span> </pre> -<p>The initialization can be a simple expression as shown; in fact it's a little silly to make initialization one of the arguments to <code><span class='Function'>For</span></code> at all.Unlike in C, it's impossible to declare a variable that's local to the whole <code><span class='Function'>For</span></code> 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 <code><span class='Function'>For</span></code> loop, just surround it in an extra set of curly braces.</p> -<p>The <code><span class='Function'>While</span></code> loop alone allows syntax similar to the <code><span class='Function'>For</span></code> loop. Perform any initialization outside of the loop, and compose the post-action with the main body using the reverse composition <code><span class='Brace'>{</span><span class='Function'>𝔾</span><span class='Modifier2'>∘</span><span class='Function'>𝔽</span><span class='Brace'>}</span></code>. Because the composition binds less tightly than stranding, the bracketed <a href="arrayrepr.html#brackets">list notation</a> has to be used here.</p> +<p>The initialization can be a simple expression as shown; in fact it's a little silly to make initialization one of the arguments to <code><span class='Function'>For</span></code> at all. Unlike in C, it's impossible to declare a variable that's local to the whole <code><span class='Function'>For</span></code> 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 <code><span class='Function'>For</span></code> loop, surround it in an extra set of curly braces.</p> +<p>The <code><span class='Function'>While</span></code> loop alone allows syntax similar to the <code><span class='Function'>For</span></code> loop. Perform any initialization outside of the loop, and compose the post-action with the main body using the reverse composition <code><span class='Brace'>{</span><span class='Function'>𝔾</span><span class='Modifier2'>∘</span><span class='Function'>𝔽</span><span class='Brace'>}</span></code>. Because that composition would bind less tightly than stranding, the bracketed <a href="arrayrepr.html#brackets">list notation</a> has to be used here.</p> <pre><span class='Value'>c</span><span class='Gets'>←</span><span class='Number'>27</span> <span class='Separator'>⋄</span> <span class='Value'>n</span><span class='Gets'>←</span><span class='Number'>0</span> <span class='Function'>While</span> <span class='Bracket'>⟨</span><span class='Brace'>{</span><span class='Value'>𝕤</span><span class='Separator'>⋄</span><span class='Number'>1</span><span class='Function'><</span><span class='Value'>c</span><span class='Brace'>}</span><span class='Separator'>,</span> <span class='Brace'>{</span><span class='Value'>𝕤</span><span class='Separator'>⋄</span><span class='Value'>n</span><span class='Function'>+</span><span class='Gets'>↩</span><span class='Number'>1</span><span class='Brace'>}{</span><span class='Function'>𝔾</span><span class='Modifier2'>∘</span><span class='Function'>𝔽</span><span class='Brace'>}{</span><span class='Value'>𝕤</span> <span class='Function'>Match</span> <span class='Paren'>(</span><span class='Number'>2</span><span class='Function'>|</span><span class='Value'>c</span><span class='Paren'>)</span><span class='Ligature'>‿</span><span class='Brace'>{</span> 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 @@ </head> <div class="nav">(<a href="https://github.com/mlochbaum/BQN">github</a>) / <a href="../index.html">BQN</a> / <a href="index.html">doc</a></div> <h1 id="couple-and-merge"><a class="header" href="#couple-and-merge">Couple and Merge</a></h1> -<p>Solo/Couple (<code><span class='Function'>≍</span></code>) and Merge (<code><span class='Function'>></span></code>) 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 <code><span class='Number'>2</span><span class='Ligature'>‿</span><span class='Number'>3</span></code>:</p> -<a class="replLink" title="Open in the REPL" target="_blank" href="https://mlochbaum.github.io/BQN/try.html#code=4oqiIHAg4oaQIDPigL81w5fijJzihpUzCuKKoiBxIOKGkCAy4oC/M+KliiJhYmNkZWYiCnAg4omNIHEgICAjIHAgY291cGxlZCB0byBxCuKJoiBwIOKJjSBx">↗️</a><pre> <span class='Function'>⊢</span> <span class='Value'>p</span> <span class='Gets'>←</span> <span class='Number'>3</span><span class='Ligature'>‿</span><span class='Number'>5</span><span class='Function'>×</span><span class='Modifier'>⌜</span><span class='Function'>↕</span><span class='Number'>3</span> -┌─ -╵ 0 3 6 - 0 5 10 - ┘ - <span class='Function'>⊢</span> <span class='Value'>q</span> <span class='Gets'>←</span> <span class='Number'>2</span><span class='Ligature'>‿</span><span class='Number'>3</span><span class='Function'>⥊</span><span class='String'>"abcdef"</span> -┌─ -╵"abc - def" - ┘ +<p>Solo/Couple (<code><span class='Function'>≍</span></code>) and Merge (<code><span class='Function'>></span></code>) are functions that build a higher-rank array out of <a href="array.html#cells">cells</a>. 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 <code><span class='Number'>2</span><span class='Ligature'>‿</span><span class='Number'>3</span></code>:</p> +<a class="replLink" title="Open in the REPL" target="_blank" href="https://mlochbaum.github.io/BQN/try.html#code=4p+ocOKGkDPigL81w5fijJzihpUzLCBx4oaQMuKAvzPipYoiYWJjZGVmIuKfqSAgIyBTaG93biBzaWRlIGJ5IHNpZGUKCnAg4omNIHEgICAjIHAgY291cGxlZCB0byBxCgriiaIgcCDiiY0gcQ==">↗️</a><pre> <span class='Bracket'>⟨</span><span class='Value'>p</span><span class='Gets'>←</span><span class='Number'>3</span><span class='Ligature'>‿</span><span class='Number'>5</span><span class='Function'>×</span><span class='Modifier'>⌜</span><span class='Function'>↕</span><span class='Number'>3</span><span class='Separator'>,</span> <span class='Value'>q</span><span class='Gets'>←</span><span class='Number'>2</span><span class='Ligature'>‿</span><span class='Number'>3</span><span class='Function'>⥊</span><span class='String'>"abcdef"</span><span class='Bracket'>⟩</span> <span class='Comment'># Shown side by side +</span>┌─ +· ┌─ ┌─ + ╵ 0 3 6 ╵"abc + 0 5 10 def" + ┘ ┘ + ┘ + <span class='Value'>p</span> <span class='Function'>≍</span> <span class='Value'>q</span> <span class='Comment'># p coupled to q </span>┌─ ╎ 0 3 6 @@ -24,24 +22,27 @@ 'a' 'b' 'c' 'd' 'e' 'f' ┘ + <span class='Function'>≢</span> <span class='Value'>p</span> <span class='Function'>≍</span> <span class='Value'>q</span> ⟨ 2 2 3 ⟩ </pre> -<p>The result has two inner axes that are shared by <code><span class='Value'>p</span></code> and <code><span class='Value'>q</span></code>, preceded by an outer axis: length 2 because there are two arguments. Calling <code><span class='Function'>≍</span></code> 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.</p> -<a class="replLink" title="Open in the REPL" target="_blank" href="https://mlochbaum.github.io/BQN/try.html#code=4omNIHEK4omiIOKJjSBx">↗️</a><pre> <span class='Function'>≍</span> <span class='Value'>q</span> +<p>The result is an array with <code><span class='Value'>p</span></code> and <code><span class='Value'>q</span></code> for its major cells. It has two inner axes that are shared by <code><span class='Value'>p</span></code> and <code><span class='Value'>q</span></code>, preceded by an outer axis, with length 2 because there are two arguments. With no left argument, <code><span class='Function'>≍</span></code> 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.</p> +<a class="replLink" title="Open in the REPL" target="_blank" href="https://mlochbaum.github.io/BQN/try.html#code=4omNIHEKCuKJoiDiiY0gcQ==">↗️</a><pre> <span class='Function'>≍</span> <span class='Value'>q</span> ┌─ ╎"abc def" ┘ + <span class='Function'>≢</span> <span class='Function'>≍</span> <span class='Value'>q</span> ⟨ 1 2 3 ⟩ </pre> -<p>Merge (<code><span class='Function'>></span></code>) 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.</p> -<a class="replLink" title="Open in the REPL" target="_blank" href="https://mlochbaum.github.io/BQN/try.html#code=4oqiIGEg4oaQICJBQiLigL8iQ0QiIOKIvuKMnCAicnN0IuKAvyJ1dnci4oC/Inh5eiIKPiBhCuKJoiA+IGE=">↗️</a><pre> <span class='Function'>⊢</span> <span class='Value'>a</span> <span class='Gets'>←</span> <span class='String'>"AB"</span><span class='Ligature'>‿</span><span class='String'>"CD"</span> <span class='Function'>∾</span><span class='Modifier'>⌜</span> <span class='String'>"rst"</span><span class='Ligature'>‿</span><span class='String'>"uvw"</span><span class='Ligature'>‿</span><span class='String'>"xyz"</span> +<p>Merge (<code><span class='Function'>></span></code>) takes one argument, but a nested one. <code><span class='Value'>𝕩</span></code> is an array of arrays, each with the same shape. The shape of the result is then the outer shape <code><span class='Function'>≢</span><span class='Value'>𝕩</span></code> followed by this shared inner shape.</p> +<a class="replLink" title="Open in the REPL" target="_blank" href="https://mlochbaum.github.io/BQN/try.html#code=4oqiIGEg4oaQICJBQiLigL8iQ0QiIOKIvuKMnCAicnN0IuKAvyJ1dnci4oC/Inh5eiIKCj4gYQoK4omiIGEK4omiID4gYQ==">↗️</a><pre> <span class='Function'>⊢</span> <span class='Value'>a</span> <span class='Gets'>←</span> <span class='String'>"AB"</span><span class='Ligature'>‿</span><span class='String'>"CD"</span> <span class='Function'>∾</span><span class='Modifier'>⌜</span> <span class='String'>"rst"</span><span class='Ligature'>‿</span><span class='String'>"uvw"</span><span class='Ligature'>‿</span><span class='String'>"xyz"</span> ┌─ ╵ "ABrst" "ABuvw" "ABxyz" "CDrst" "CDuvw" "CDxyz" ┘ + <span class='Function'>></span> <span class='Value'>a</span> ┌─ ╎"ABrst @@ -52,20 +53,24 @@ CDuvw CDxyz" ┘ + + <span class='Function'>≢</span> <span class='Value'>a</span> +⟨ 2 3 ⟩ <span class='Function'>≢</span> <span class='Function'>></span> <span class='Value'>a</span> ⟨ 2 3 5 ⟩ </pre> -<p>Merge is effectively a generalization of Solo and Couple, since Solo is <code><span class='Brace'>{</span><span class='Function'>></span><span class='Bracket'>⟨</span><span class='Value'>𝕩</span><span class='Bracket'>⟩</span><span class='Brace'>}</span></code> and Couple is <code><span class='Brace'>{</span><span class='Function'>></span><span class='Bracket'>⟨</span><span class='Value'>𝕨</span><span class='Separator'>,</span><span class='Value'>𝕩</span><span class='Bracket'>⟩</span><span class='Brace'>}</span></code>. Since <code><span class='Function'>≍</span></code> works on the "list" of arguments, it can only add one dimension, but <code><span class='Function'>></span></code> can take any number of dimensions as its input.</p> +<p>Merge serves as a generalization of Solo and Couple, since Solo is <code><span class='Brace'>{</span><span class='Function'>></span><span class='Bracket'>⟨</span><span class='Value'>𝕩</span><span class='Bracket'>⟩</span><span class='Brace'>}</span></code> and Couple is <code><span class='Brace'>{</span><span class='Function'>></span><span class='Bracket'>⟨</span><span class='Value'>𝕨</span><span class='Separator'>,</span><span class='Value'>𝕩</span><span class='Bracket'>⟩</span><span class='Brace'>}</span></code>. Since <code><span class='Function'>≍</span></code> works on the "list" of arguments, it can only add one dimension, but <code><span class='Function'>></span></code> can take any number of dimensions as its input.</p> <h2 id="merge-and-array-theory"><a class="header" href="#merge-and-array-theory">Merge and array theory</a></h2> -<p>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 <a href="join.html">joins</a> 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.</p> -<a class="replLink" title="Open in the REPL" target="_blank" href="https://mlochbaum.github.io/BQN/try.html#code=4qWKID4gYQripYog4qWKwqggYQriiL4g4qWKIOKlisKoIGE=">↗️</a><pre> <span class='Function'>⥊</span> <span class='Function'>></span> <span class='Value'>a</span> +<p>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 <a href="join.html">joins</a> 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 <a href="rank.html">Rank</a> does to combine the result cells from its operand into a single array.</p> +<a class="replLink" title="Open in the REPL" target="_blank" href="https://mlochbaum.github.io/BQN/try.html#code=4qWKID4gYQoK4qWKIOKlisKoIGEK4oi+IOKliiDipYrCqCBh">↗️</a><pre> <span class='Function'>⥊</span> <span class='Function'>></span> <span class='Value'>a</span> "ABrstABuvwABxyzCDrstCDuvwCDxyz" + <span class='Function'>⥊</span> <span class='Function'>⥊</span><span class='Modifier'>¨</span> <span class='Value'>a</span> ⟨ "ABrst" "ABuvw" "ABxyz" "CDrst" "CDuvw" "CDxyz" ⟩ <span class='Function'>∾</span> <span class='Function'>⥊</span> <span class='Function'>⥊</span><span class='Modifier'>¨</span> <span class='Value'>a</span> "ABrstABuvwABxyzCDrstCDuvwCDxyz" </pre> -<p>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 <a href="map.html#table">Table</a> <code><span class='Modifier'>⌜</span></code>, Merge might be considered a fundamental way to build up multidimensional arrays from lists. In both cases rank-0 or <a href="enclose.html#whats-a-unit">unit</a> arrays are somewhat special. They are the <a href="fold.html#identity-values">identity value</a> of a function with Table, and can be produced by Merge <a href="undo.html">inverse</a>, <code><span class='Function'>></span><span class='Modifier'>⁼</span></code> <strong>on a list</strong>, which forces either the outer or inner shape to be empty (BQN chooses <code><span class='Function'>></span><span class='Modifier'>⁼</span></code> to be <code><span class='Function'><</span></code>, but only on an array, as <code><span class='Function'>></span></code> cannot produce non-arrays). Merge has another catch as well: it cannot produce arrays with a <code><span class='Number'>0</span></code> in the shape, except at the end, without relying on a <a href="fill.html">fill</a> element.</p> +<p>Somewhat like <a href="map.html#table">Table</a> <code><span class='Modifier'>⌜</span></code>, Merge might be considered a fundamental way to build up multidimensional arrays from lists. In both cases rank-0 or <a href="enclose.html#whats-a-unit">unit</a> arrays are somewhat special. They are the <a href="fold.html#identity-values">identity value</a> of a function with Table, and <a href="enclose.html">Enclose</a> (<code><span class='Function'><</span></code>), 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 <a href="fill.html">fill</a> element.</p> <a class="replLink" title="Open in the REPL" target="_blank" href="https://mlochbaum.github.io/BQN/try.html#code=4oqiIGUg4oaQIOKfqOKfqcKoIOKGlTMK4omiID4gZQriiaIgPiA+IGU=">↗️</a><pre> <span class='Function'>⊢</span> <span class='Value'>e</span> <span class='Gets'>←</span> <span class='Bracket'>⟨⟩</span><span class='Modifier'>¨</span> <span class='Function'>↕</span><span class='Number'>3</span> ⟨ ⟨⟩ ⟨⟩ ⟨⟩ ⟩ <span class='Function'>≢</span> <span class='Function'>></span> <span class='Value'>e</span> @@ -73,10 +78,10 @@ <span class='Function'>≢</span> <span class='Function'>></span> <span class='Function'>></span> <span class='Value'>e</span> ⟨ 3 0 ⟩ </pre> -<p>Above we start with a list of three empty arrays. After merging once we get a shape <code><span class='Number'>3</span><span class='Ligature'>‿</span><span class='Number'>0</span></code> 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 <code><span class='Number'>0</span></code> in the middle of the shape. In this sense, arrays are a richer model than nested lists.</p> +<p>Above we start with a list of three empty arrays. After merging once we get a shape <code><span class='Number'>3</span><span class='Ligature'>‿</span><span class='Number'>0</span></code> 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.</p> <h2 id="coupling-units"><a class="header" href="#coupling-units">Coupling units</a></h2> <p>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 <a href="https://code.jsoftware.com/wiki/Vocabulary/commaco#dyadic">laminate</a> differs from Couple in this one case, as it will add an axis to get a shape <code><span class='Number'>2</span><span class='Ligature'>‿</span><span class='Number'>1</span></code> result). For Solo, this is interchangeable with <a href="reshape.html">Deshape</a> (<code><span class='Function'>⥊</span></code>), and either primitive might be chosen for stylistic reasons. For Couple, it is equivalent to <a href="join.html">Join-to</a> (<code><span class='Function'>∾</span></code>), 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.</p> <p>The function <a href="pair.html">Pair</a> (<code><span class='Function'>⋈</span></code>) can be written <code><span class='Function'>≍</span><span class='Modifier2'>○</span><span class='Function'><</span></code>, while <code><span class='Function'>≍</span></code> in either valence is <code><span class='Function'>></span><span class='Modifier2'>∘</span><span class='Function'>⋈</span></code>. As an interesting consequence, <code><span class='Function'>≍</span> <span class='Gets'>←→</span> <span class='Function'>></span><span class='Modifier2'>∘</span><span class='Function'>≍</span><span class='Modifier2'>○</span><span class='Function'><</span></code>, and <code><span class='Function'>⋈</span> <span class='Gets'>←→</span> <span class='Function'>></span><span class='Modifier2'>∘</span><span class='Function'>⋈</span><span class='Modifier2'>○</span><span class='Function'><</span></code>. These two identities have the same form because adding <code><span class='Modifier2'>○</span><span class='Function'><</span></code> commutes with adding <code><span class='Function'>></span><span class='Modifier2'>∘</span></code>.</p> <h2 id="definitions"><a class="header" href="#definitions">Definitions</a></h2> -<p>As discussed above, <code><span class='Function'>≍</span></code> is equivalent to <code><span class='Function'>></span><span class='Brace'>{</span><span class='Bracket'>⟨</span><span class='Value'>𝕩</span><span class='Bracket'>⟩</span><span class='Head'>;</span><span class='Bracket'>⟨</span><span class='Value'>𝕨</span><span class='Separator'>,</span><span class='Value'>𝕩</span><span class='Bracket'>⟩</span><span class='Brace'>}</span></code>. To complete the picture we should describe Merge fully. Merge is defined on an array argument <code><span class='Value'>𝕩</span></code> such that there's some shape <code><span class='Value'>s</span></code> satisfying <code><span class='Function'>∧</span><span class='Modifier'>´</span><span class='Function'>⥊</span><span class='Paren'>(</span><span class='Value'>s</span><span class='Function'>≡≢</span><span class='Paren'>)</span><span class='Modifier'>¨</span><span class='Value'>𝕩</span></code>. If <code><span class='Value'>𝕩</span></code> is empty then any shape satisfies this expression; <code><span class='Value'>s</span></code> should be chosen based on known type information for <code><span class='Value'>𝕩</span></code> or otherwise assumed to be <code><span class='Bracket'>⟨⟩</span></code>. If <code><span class='Value'>s</span></code> is empty then <code><span class='Value'>𝕩</span></code> is allowed to contain atoms as well as unit arrays, and these will be implicitly promoted to arrays by the <code><span class='Function'>⊑</span></code> 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. <code><span class='Value'>𝕩</span></code> is a natural choice of left argument, and because no concrete array can be used, the right argument will be <code><span class='Function'>↕</span><span class='Value'>s</span></code>, the array of indices into any element of <code><span class='Value'>𝕩</span></code>. To get the appropriate element corresponding to a particular choice of index and element of <code><span class='Value'>𝕩</span></code> we should select using that index. The result of Merge is <code><span class='Value'>𝕩</span><span class='Function'>⊑</span><span class='Modifier'>˜⌜</span><span class='Function'>↕</span><span class='Value'>s</span></code>.</p> +<p>As discussed above, <code><span class='Function'>≍</span></code> is equivalent to <code><span class='Function'>></span><span class='Brace'>{</span><span class='Bracket'>⟨</span><span class='Value'>𝕩</span><span class='Bracket'>⟩</span><span class='Head'>;</span><span class='Bracket'>⟨</span><span class='Value'>𝕨</span><span class='Separator'>,</span><span class='Value'>𝕩</span><span class='Bracket'>⟩</span><span class='Brace'>}</span></code> or <code><span class='Function'>>⋈</span></code>. To complete the picture we should describe Merge fully. Merge is defined on an array argument <code><span class='Value'>𝕩</span></code> such that there's some shape <code><span class='Value'>s</span></code> satisfying <code><span class='Function'>∧</span><span class='Modifier'>´</span><span class='Function'>⥊</span><span class='Paren'>(</span><span class='Value'>s</span><span class='Function'>≡≢</span><span class='Paren'>)</span><span class='Modifier'>¨</span><span class='Value'>𝕩</span></code>. If <code><span class='Value'>𝕩</span></code> is empty then any shape satisfies this expression; <code><span class='Value'>s</span></code> should be chosen based on known type information for <code><span class='Value'>𝕩</span></code> or otherwise assumed to be <code><span class='Bracket'>⟨⟩</span></code>. If <code><span class='Value'>s</span></code> is empty then <code><span class='Value'>𝕩</span></code> is allowed to contain atoms as well as unit arrays, and these will be implicitly promoted to arrays by the <code><span class='Function'>⊑</span></code> 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. <code><span class='Value'>𝕩</span></code> is a natural choice of left argument, and because no concrete array can be used, the right argument will be <code><span class='Function'>↕</span><span class='Value'>s</span></code>, the array of indices into any element of <code><span class='Value'>𝕩</span></code>. To get the appropriate element corresponding to a particular choice of index and element of <code><span class='Value'>𝕩</span></code> we should select using that index. The result of Merge is <code><span class='Value'>𝕩</span><span class='Function'>⊑</span><span class='Modifier'>˜⌜</span><span class='Function'>↕</span><span class='Value'>s</span></code>.</p> <p>Given this definition we can also describe Rank (<code><span class='Modifier2'>⎉</span></code>) in terms of Each (<code><span class='Modifier'>¨</span></code>) and the simpler monadic function Enclose-Rank <code><span class='Function'><</span><span class='Modifier2'>⎉</span><span class='Value'>k</span></code>. We assume effective ranks <code><span class='Value'>j</span></code> for <code><span class='Value'>𝕨</span></code> (if present) and <code><span class='Value'>k</span></code> for <code><span class='Value'>𝕩</span></code> have been computed. Then the correspondence is <code><span class='Value'>𝕨</span><span class='Function'>F</span><span class='Modifier2'>⎉</span><span class='Value'>k𝕩</span> <span class='Gets'>←→</span> <span class='Function'>></span><span class='Paren'>(</span><span class='Function'><</span><span class='Modifier2'>⎉</span><span class='Value'>j𝕨</span><span class='Paren'>)</span><span class='Function'>F</span><span class='Modifier'>¨</span><span class='Paren'>(</span><span class='Function'><</span><span class='Modifier2'>⎉</span><span class='Value'>k𝕩</span><span class='Paren'>)</span></code>.</p> 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 @@ <a class="replLink" title="Open in the REPL" target="_blank" href="https://mlochbaum.github.io/BQN/try.html#code=wrsgImFiYyIgKyA04oC/M+KAvzI=">↗️</a><pre> <span class='Function'>»</span> <span class='String'>"abc"</span> <span class='Function'>+</span> <span class='Number'>4</span><span class='Ligature'>‿</span><span class='Number'>3</span><span class='Ligature'>‿</span><span class='Number'>2</span> " ee" </pre> -<p><a href="map.html">Mapping</a> modifiers Each and Table (<code><span class='Modifier'>¨⌜</span></code>) might try to follow a similar strategy, applying <code><span class='Function'>𝔽</span></code> 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 <code><span class='Function'>𝔽</span></code> such as a block function this procedure is likely to be aborted to avoid disrupting the rest of the program.</p> +<p><a href="map.html">Mapping</a> modifiers Each and Table (<code><span class='Modifier'>¨⌜</span></code>) might try to follow a similar strategy, applying <code><span class='Function'>𝔽</span></code> 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 <code><span class='Function'>𝔽</span></code> such as a block function this procedure is likely to be aborted to avoid disrupting the rest of the program.</p> <p>Most other primitives fit in one of three broad categories as shown in the table below. Structural primitives, indicated by <code><span class='Function'>⊢</span></code>, don't change the fill of <code><span class='Value'>𝕩</span></code>. Combining structural primitives, indicated by <code><span class='Value'>∩</span></code>, only depend on the fill of all combined arrays—elements of <code><span class='Value'>𝕩</span></code> in the one-argument case, or <code><span class='Value'>𝕨</span></code> and <code><span class='Value'>𝕩</span></code> in the two-argument case. Finally, many functions such as <a href="search.html">search functions</a> return only numbers and have a fill of <code><span class='Number'>0</span></code>.</p> <table> <thead> 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 @@ </ul> <ul> <li><strong>Error</strong>: A condition that stops compilation or execution (see <a href="assert.html">assert</a>).</li> -<li><strong>Inferred property</strong>: 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.</li> +<li><strong>Inferred property</strong>: 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.</li> </ul> <h2 id="namespaces"><a class="header" href="#namespaces">Namespaces</a></h2> <ul> 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 @@ </pre> <h2 id="definition"><a class="header" href="#definition">Definition</a></h2> <p>In any instance of <code><span class='Function'>»</span></code> or <code><span class='Function'>«</span></code>, <code><span class='Value'>𝕩</span></code> must have rank at least 1.</p> -<p>For a dyadic shift function, <code><span class='Value'>𝕨</span></code> must be <a href="join.html#join-to">Join</a>-compatible with <code><span class='Value'>𝕩</span></code> (that is, <code><span class='Value'>𝕨</span><span class='Function'>∾</span><span class='Value'>𝕩</span></code> completes without error) and cannot have greater rank than <code><span class='Value'>𝕩</span></code>. Then Shift Before (<code><span class='Function'>»</span></code>) is <code><span class='Brace'>{</span><span class='Paren'>(</span><span class='Function'>≠</span><span class='Value'>𝕩</span><span class='Paren'>)</span><span class='Function'>↑</span><span class='Value'>𝕨</span><span class='Function'>∾</span><span class='Value'>𝕩</span><span class='Brace'>}</span></code> and Shift After (<code><span class='Function'>«</span></code>) is <code><span class='Brace'>{</span><span class='Paren'>(</span><span class='Function'>-≠</span><span class='Value'>𝕩</span><span class='Paren'>)</span><span class='Function'>↑</span><span class='Value'>𝕩</span><span class='Function'>∾</span><span class='Value'>𝕨</span><span class='Brace'>}</span></code></p> +<p>For a dyadic shift function, <code><span class='Value'>𝕨</span></code> must be <a href="join.html#join-to">Join</a>-compatible with <code><span class='Value'>𝕩</span></code> (that is, <code><span class='Value'>𝕨</span><span class='Function'>∾</span><span class='Value'>𝕩</span></code> completes without error) and can't have greater rank than <code><span class='Value'>𝕩</span></code>. Then Shift Before (<code><span class='Function'>»</span></code>) is <code><span class='Brace'>{</span><span class='Paren'>(</span><span class='Function'>≠</span><span class='Value'>𝕩</span><span class='Paren'>)</span><span class='Function'>↑</span><span class='Value'>𝕨</span><span class='Function'>∾</span><span class='Value'>𝕩</span><span class='Brace'>}</span></code> and Shift After (<code><span class='Function'>«</span></code>) is <code><span class='Brace'>{</span><span class='Paren'>(</span><span class='Function'>-≠</span><span class='Value'>𝕩</span><span class='Paren'>)</span><span class='Function'>↑</span><span class='Value'>𝕩</span><span class='Function'>∾</span><span class='Value'>𝕨</span><span class='Brace'>}</span></code></p> <p>When called monadically, the default argument is a cell of fills <code><span class='Number'>1</span><span class='Function'>↑</span><span class='Number'>0</span><span class='Function'>↑</span><span class='Value'>𝕩</span></code>. That is, Nudge (<code><span class='Function'>»</span></code>) is <code><span class='Paren'>(</span><span class='Number'>1</span><span class='Function'>↑</span><span class='Number'>0</span><span class='Function'>↑⊢</span><span class='Paren'>)</span><span class='Modifier2'>⊸</span><span class='Function'>»</span></code> and Nudge Back (<code><span class='Function'>«</span></code>) is <code><span class='Paren'>(</span><span class='Number'>1</span><span class='Function'>↑</span><span class='Number'>0</span><span class='Function'>↑⊢</span><span class='Paren'>)</span><span class='Modifier2'>⊸</span><span class='Function'>«</span></code>. This default argument always satisfies the compatibility requirement above and so the only conditions for nudge are that <code><span class='Value'>𝕩</span></code> has rank at least 1 and has a fill element.</p> 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 @@ <p>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.</p> <p>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.</p> <h3 id="anticipation"><a class="header" href="#anticipation">Anticipation</a></h3> -<p>The <a href="#hot-paths">hot path</a> 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.</p> +<p>The <a href="#hot-paths">hot path</a> 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.</p> <p>The end result seems similar to that obtained by thunks as discussed at Dyalog '18 (<a href="https://dyalog.tv/Dyalog18/?v=-6no6N3i9Tg">video</a>, <a href="https://www.dyalog.com/user-meetings/uploads/conference/dyalog18/presentations/D15_The_Interpretive_Advantage.zip">slides</a>). 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.</p> <p>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.</p> <p>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.</p> 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 @@ <p>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 <em>in a later version</em>. 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.</p> <p>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 <a href="https://code.kx.com/q/ref/value/">value</a> function shows. Having to keep track of integers versus floats is a drag, but ngn/k is able to use <a href="https://en.wikipedia.org/wiki/Tagged_pointer">tagged pointers</a> to store smaller integers without an allocation, and I doubt Whitney would miss a trick like that. So K interpreters can be fast.</p> <p>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 <em>has</em> to be slower.</p> -<p>This is why BQN uses compiler-based strategies to speed up execution, first compiling to <a href="vm.html#bytecode">object code</a> 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 <a href="https://github.com/ktye/i/tree/master/kom">an ahead-of-time compiler</a> 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.</p> +<p>This is why BQN uses compiler-based strategies to speed up execution, first compiling to <a href="vm.html#bytecode">object code</a> 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 <a href="https://github.com/ktye/i/tree/master/kom">an ahead-of-time compiler</a> 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.</p> <h2 id="parallel-execution"><a class="header" href="#parallel-execution">Parallel execution</a></h2> <p>As of 2020, Q supports <a href="https://code.kx.com/q/kb/mt-primitives/">multithreaded primitives</a> 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 <a href="https://www.monument.ai/m/parallel">J engine</a>. 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!</p> <h2 id="instruction-cache"><a class="header" href="#instruction-cache">Instruction cache</a></h2> |
