From 07be54d8179ba799cc55dacd2c79fb2292477030 Mon Sep 17 00:00:00 2001 From: Marshall Lochbaum Date: Mon, 6 Jun 2022 22:04:00 -0400 Subject: Consistently avoid "derived function" for trains: use "compound function" instead --- docs/doc/glossary.html | 1 + docs/implementation/compile/dynamic.html | 8 ++++---- docs/spec/evaluate.html | 4 ++-- docs/spec/inferred.html | 2 +- docs/spec/primitive.html | 2 +- docs/spec/system.html | 2 +- 6 files changed, 10 insertions(+), 9 deletions(-) (limited to 'docs') 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 @@
  • Dyadic: Called with two arguments, always or in a particular instance.
    • -

    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 (⍟).

    +

    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 (⍟).

    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.

    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.

    Hardware

    @@ -42,11 +42,11 @@

    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.

    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.

    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.

    -

    Derived functions

    -

    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.

    +

    Compound functions

    +

    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.

    Compound arithmetic functions like +´, ⌈`, or =⌜ are essential to array programming, and have fast SIMD implementations, so they need to be recognized wherever they are found.

    In addition to these, there are patterns like ∨`∘≠ that can be implemented faster than their components, and bindings like l⊸⊐ 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.

    -

    Tacit code can be converted to SSA 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.

    +

    Tacit code can be converted to SSA 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.

    Compile in another thread

    A simple and widely-used strategy to reduce slowdown due to dynamic compilation is to compile blocks in a separate thread from the one that runs them. The new code needs to be added in a thread-safe manner, which is not hard as the set of optimized implementations is a small lookup table of some sort with only one writer.

    If the implementation is able to make use of all available threads (possible when working with large arrays), then it's still important to minimize compilation time as that thread could be put to better use. If there are idle threads then the only costs of compilation overhead are minor: the optimized code can't be put to use as quickly, and there is more power draw and possible downclocking.

    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 @@

    In each case the constituent expressions are evaluated in reverse source order: Right, then Called, then Left. Then the expression's result is obtained by calling the Called value on its parameters. A left argument of nothing is not used as a parameter, leaving only a right argument in that case. The 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.

    -

    Modifiers that are evaluated when they receive operands are called immediate. Other modifiers, including primitives and some kinds of block, simply record the operands and are called deferred. The result of applying a deferred modifier once is called a derived function.

    -

    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.

    +

    Modifiers that are evaluated when they receive operands are called immediate. Other modifiers, including primitives and some kinds of block, simply record the operands and are called deferred. The result of applying a deferred modifier once is called a derived function, and is one kind of compound function.

    +

    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.

    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 @@
    -

    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 𝔽˙ for an arbitrary value 𝔽.

    +

    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 𝔽˙ for an arbitrary value 𝔽.

    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 @@

    Operations are split into subtypes depending on how they were created.

    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, =○{𝕩⋄{𝕩}}˜@ is 0 while =˜○{𝕩⋄{𝕩}}@ is 1.

    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 @@

    •Glyph gives the glyph corresponding to a primitive as a single character, for example returning '+' given an argument matching +. It causes an error if the argument is not a primitive.

    •Source gives a string containing a block's source, including the enclosing braces {}. It causes an error if the argument is not a block. In contrast to •Glyph, this function does not give full information about 𝕩 because the result cannot convey environment or mutable identity.

    -

    •Decompose 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 •Decompose cannot cause an error.

    +

    •Decompose 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 •Decompose cannot cause an error.

    -- cgit v1.2.3