diff options
Diffstat (limited to 'docs')
| -rw-r--r-- | docs/doc/glossary.html | 1 | ||||
| -rw-r--r-- | docs/implementation/compile/dynamic.html | 8 | ||||
| -rw-r--r-- | docs/spec/evaluate.html | 4 | ||||
| -rw-r--r-- | docs/spec/inferred.html | 2 | ||||
| -rw-r--r-- | docs/spec/primitive.html | 2 | ||||
| -rw-r--r-- | docs/spec/system.html | 2 |
6 files changed, 10 insertions, 9 deletions
diff --git a/docs/doc/glossary.html b/docs/doc/glossary.html index 1bd32484..878a6738 100644 --- a/docs/doc/glossary.html +++ b/docs/doc/glossary.html @@ -93,6 +93,7 @@ <li><strong>Dyadic</strong>: Called with two arguments, always or in a particular instance.</li> </ul> <ul> +<li><strong>Compound function</strong>: A derived function or train.</li> <li><strong>Derived function</strong>: A function produced by binding operands to a deferred modifier; doing so does not cause any computation.</li> <li><a href="train.html"><strong>Train</strong></a>: A function composed of two or more functions.</li> <li><a href="fold.html#identity-values"><strong>Identity value</strong></a>: An inferred property of a function: the result of a reduction with this function on an empty array.</li> diff --git a/docs/implementation/compile/dynamic.html b/docs/implementation/compile/dynamic.html index 59f6ad75..62c8ec2b 100644 --- a/docs/implementation/compile/dynamic.html +++ b/docs/implementation/compile/dynamic.html @@ -15,7 +15,7 @@ <li>Primitives take a long time, because of large arrays.</li> <li>There are many actions, because blocks are repeated many times.</li> </ul> -<p>If many bytecode instructions are evaluated, it must be that blocks are repeated, because each instruction can only be run once by its containing block. A derived function might be run many times by a modifier, which typically involves a large array, but could also be because of Repeat (<code><span class='Modifier2'>⍟</span></code>).</p> +<p>If many bytecode instructions are evaluated, it must be that blocks are repeated, because each instruction can only be run once by its containing block. A function operand might be run many times by a modifier, which typically involves a large array, but could also be because of Repeat (<code><span class='Modifier2'>⍟</span></code>).</p> <p>This is an array-based viewpoint, because in a low-level language the large array case would just be considered one of several kinds of repetition. Traditionally APL focused exclusively on speeding up the large array case; BQN's compilation makes better block performance a reachable goal.</p> <p>The two conditions are routinely mixed in various ways: a program might split its time between manipulating small and large arrays, or it might work with large arrays but sometimes apply a block function to each element or small groups of elements. Array size or number of iterations could even differ between program runs. An evaluation strategy needs to adapt to these changes.</p> <h3 id="hardware"><a class="header" href="#hardware">Hardware</a></h3> @@ -42,11 +42,11 @@ <p>The same procedure can be run on local rather than global constraints, which might produce more specialized code at the cost of running through the block once per specialization.</p> <p>Saving metadata from the first run is another possibility, with very low overhead. This most naturally provides a guess as to what the metadata usually is, but it may also be possible to keep track of when metadata is "known" with a flag system.</p> <p>The desire to do metadata computations, or pure data ones once metadata is known suggests a system with a "wrapper" that computes type, shape, and so on, then selects and calls an "kernel" function for the computation. Specialized code could use a particular kernel, or a different wrapper that selects from a subset of the kernels.</p> -<h3 id="derived-functions"><a class="header" href="#derived-functions">Derived functions</a></h3> -<p>Like blocks, it can be valuable to optimize derived functions if they are run many times. Derived functions are often known at the program start by constant folding, but might also be constructed dynamically, particularly to bind an argument to a function.</p> +<h3 id="compound-functions"><a class="header" href="#compound-functions">Compound functions</a></h3> +<p>Like blocks, it can be valuable to optimize compound functions if they are run many times. Compound functions are often known at the program start by constant folding, but might also be constructed dynamically, particularly to bind an argument to a function.</p> <p>Compound arithmetic functions like <code><span class='Function'>+</span><span class='Modifier'>´</span></code>, <code><span class='Function'>⌈</span><span class='Modifier'>`</span></code>, or <code><span class='Function'>=</span><span class='Modifier'>⌜</span></code> are essential to array programming, and have fast SIMD implementations, so they need to be recognized wherever they are found.</p> <p>In addition to these, there are patterns like <code><span class='Function'>∨</span><span class='Modifier'>`</span><span class='Modifier2'>∘</span><span class='Function'>≠</span></code> that can be implemented faster than their components, and bindings like <code><span class='Value'>l</span><span class='Modifier2'>⊸</span><span class='Function'>⊐</span></code> where a computation (here, a hash table) on the left argument can be saved. These can be handled by inspecting the function. However, it's more robust to convert it to a canonical form, so this possibility should also be considered.</p> -<p>Tacit code can be converted to <a href="https://en.wikipedia.org/wiki/Static_single_assignment_form">SSA</a> form very easily. To translate it into stack-based bytecode it would need a way to reuse values from the stack in multiple places; instructions to duplicate or extract a value from higher in the stack are an obvious candidate. Either of these forms is a natural step on the way to native compilation, and a bytecode representation would make it easier to optimize mixed tacit and explicit code—but it's easier to do the optimizations on SSA-form rather than stack-based code, so perhaps the right path is to convert both bytecode and derived functions to SSA.</p> +<p>Tacit code can be converted to <a href="https://en.wikipedia.org/wiki/Static_single_assignment_form">SSA</a> form very easily. To translate it into stack-based bytecode it would need a way to reuse values from the stack in multiple places; instructions to duplicate or extract a value from higher in the stack are an obvious candidate. Either of these forms is a natural step on the way to native compilation, and a bytecode representation would make it easier to optimize mixed tacit and explicit code—but it's easier to do the optimizations on SSA-form rather than stack-based code, so perhaps the right path is to convert both bytecode and compound functions to SSA.</p> <h3 id="compile-in-another-thread"><a class="header" href="#compile-in-another-thread">Compile in another thread</a></h3> <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> diff --git a/docs/spec/evaluate.html b/docs/spec/evaluate.html index 4e14aefa..50e42796 100644 --- a/docs/spec/evaluate.html +++ b/docs/spec/evaluate.html @@ -64,8 +64,8 @@ </tbody> </table> <p>In each case the constituent expressions are evaluated in reverse source order: Right, then Called, then Left. Then the expression's result is obtained by calling the Called value on its parameters. A left argument of <code><span class='Value'>nothing</span></code> is not used as a parameter, leaving only a right argument in that case. The type of the Called value must be appropriate to the expression type, as indicated in the "Types" column. For function application, a data type (number, character, or array) is allowed. It is called simply by returning itself. Although the arguments are ignored in this case, they are still evaluated. A block is evaluated by binding the parameter names given in columns L and R to the corresponding values. Then if all parameter levels present have been bound, its body is evaluated to give the result of application.</p> -<p>Modifiers that are evaluated when they receive operands are called <em>immediate</em>. Other modifiers, including primitives and some kinds of block, simply record the operands and are called <em>deferred</em>. The result of applying a deferred modifier once is called a <em>derived function</em>.</p> -<p>The rules for trains create another kind of derived function. A derived function is identified by the rule that created it, and the values of its parts.</p> +<p>Modifiers that are evaluated when they receive operands are called <em>immediate</em>. Other modifiers, including primitives and some kinds of block, simply record the operands and are called <em>deferred</em>. The result of applying a deferred modifier once is called a <em>derived function</em>, and is one kind of <em>compound function</em>.</p> +<p>The rules for trains create another kind of compound function. A compound function is identified by the rule that created it, and the values of its parts.</p> <table> <thead> <tr> diff --git a/docs/spec/inferred.html b/docs/spec/inferred.html index 11c27867..47cb341e 100644 --- a/docs/spec/inferred.html +++ b/docs/spec/inferred.html @@ -364,7 +364,7 @@ </tr> </tbody> </table> -<p>Inverses of other modifiers and derived functions or modifiers obtained from them are given below. Here the "inverse" of a modifier is another modifier that, if applied to the same operands as the original operator, gives its inverse function. A constant is either a data value or <code><span class='Function'>𝔽</span><span class='Modifier'>˙</span></code> for an arbitrary value <code><span class='Function'>𝔽</span></code>.</p> +<p>Inverses of other modifiers and compound functions are given below. Here the "inverse" of a modifier is another modifier that, if applied to the same operands as the original operator, gives its inverse function. A constant is either a data value or <code><span class='Function'>𝔽</span><span class='Modifier'>˙</span></code> for an arbitrary value <code><span class='Function'>𝔽</span></code>.</p> <table> <thead> <tr> diff --git a/docs/spec/primitive.html b/docs/spec/primitive.html index 1f9990a2..b68073b0 100644 --- a/docs/spec/primitive.html +++ b/docs/spec/primitive.html @@ -37,7 +37,7 @@ <p>Operations are split into subtypes depending on how they were created.</p> <ul> <li>Primitives are equal if they have the same token spelling.</li> -<li>Derived operations are equal if they are derived by the same rule and each corresponding component is the same.</li> +<li>Compound functions are equal if they are produced by the same rule and each corresponding component is the same.</li> <li>Block instances are equal if they are the same instance.</li> </ul> <p>This means that block instance equality indicates identity in the context of mutability: two block instances are equal if any change of state in one would be reflected in the other as well. The concept of identity holds even if the blocks in question have no way of changing or accessing state. For example, <code><span class='Function'>=</span><span class='Modifier2'>○</span><span class='Brace'>{</span><span class='Value'>𝕩</span><span class='Separator'>⋄</span><span class='Brace'>{</span><span class='Value'>𝕩</span><span class='Brace'>}}</span><span class='Modifier'>˜</span><span class='String'>@</span></code> is <code><span class='Number'>0</span></code> while <code><span class='Function'>=</span><span class='Modifier'>˜</span><span class='Modifier2'>○</span><span class='Brace'>{</span><span class='Value'>𝕩</span><span class='Separator'>⋄</span><span class='Brace'>{</span><span class='Value'>𝕩</span><span class='Brace'>}}</span><span class='String'>@</span></code> is <code><span class='Number'>1</span></code>.</p> diff --git a/docs/spec/system.html b/docs/spec/system.html index 01c69287..4fe4dd89 100644 --- a/docs/spec/system.html +++ b/docs/spec/system.html @@ -517,7 +517,7 @@ </table> <p><code><span class='Function'>•Glyph</span></code> gives the glyph corresponding to a primitive as a single character, for example returning <code><span class='String'>'+'</span></code> given an argument matching <code><span class='Function'>+</span></code>. It causes an error if the argument is not a primitive.</p> <p><code><span class='Function'>•Source</span></code> gives a string containing a block's source, including the enclosing braces <code><span class='Brace'>{}</span></code>. It causes an error if the argument is not a block. In contrast to <code><span class='Function'>•Glyph</span></code>, this function does not give full information about <code><span class='Value'>𝕩</span></code> because the result cannot convey environment or mutable identity.</p> -<p><code><span class='Function'>•Decompose</span></code> breaks down one level of a compound function, returning a list with a code giving what kind of structure it has followed by each of its components. Possible codes are listed in the table below according to the rule that forms the derived function—train or 2-modifier application. Non-function values, and some functions, can't be broken down. They are still classified with a code: -1 for a non-operation, 0 for a primitive, and 1 for other operations. "Other" includes blocks and system operations. The result is thus a list of length 2 to 4, and <code><span class='Function'>•Decompose</span></code> cannot cause an error.</p> +<p><code><span class='Function'>•Decompose</span></code> breaks down one level of a compound function, returning a list with a code giving what kind of structure it has followed by each of its components. Possible codes are listed in the table below according to the rule that forms the function—train or modifier application. Non-function values, and some functions, can't be broken down. They are still classified with a code: -1 for a non-operation, 0 for a primitive, and 1 for other operations. "Other" includes blocks and system operations. The result is thus a list of length 2 to 4, and <code><span class='Function'>•Decompose</span></code> cannot cause an error.</p> <table> <thead> <tr> |