diff options
| -rw-r--r-- | docs/implementation/vm.html | 65 | ||||
| -rw-r--r-- | implementation/vm.md | 54 |
2 files changed, 61 insertions, 58 deletions
diff --git a/docs/implementation/vm.html b/docs/implementation/vm.html index 46a8aa06..bb99151c 100644 --- a/docs/implementation/vm.html +++ b/docs/implementation/vm.html @@ -380,7 +380,7 @@ <p><strong>SETM</strong> additionally needs to get the current value of a reference. For a variable reference this is its current value (with an error if it's not defined yet); for a reference list it's a list of the values of each reference in the list.</p> <h2 id="runtime">Runtime</h2> <p>Primitive functions and modifiers used in a program are stored in its <code><span class='Value'>consts</span></code> array. The compiler needs to be passed a <em>runtime</em> with the value of every primitive so that these functions and modifiers are available.</p> -<p>While it's perfectly possible to implement the runtime from scratch, the pseudo-BQN file <a href="https://github.com/mlochbaum/BQN/blob/master/implementation/../src/r.bqn">r.bqn</a> implements the full runtime in terms of a <em>core runtime</em> consisting of a smaller number of much simpler functions. <a href="https://github.com/mlochbaum/BQN/blob/master/implementation/../src/pr.bqn">pr.bqn</a> converts this file so that it can be compiled. It changes values in the core runtime to primitives and primitives to generated identifiers, so that the first 21 values in the output's <code><span class='Value'>consts</span></code> array are exactly the core runtime, and no other primitives are required.</p> +<p>While it's perfectly possible to implement the runtime from scratch, the pseudo-BQN file <a href="https://github.com/mlochbaum/BQN/blob/master/implementation/../src/r.bqn">r.bqn</a> implements the full runtime in terms of a <em>core runtime</em> consisting of a smaller number of much simpler functions. <a href="https://github.com/mlochbaum/BQN/blob/master/implementation/../src/pr.bqn">pr.bqn</a> converts this file so that it can be compiled. It changes values in the core runtime to primitives and primitives to generated identifiers, so that the first 22 values in the output's <code><span class='Value'>consts</span></code> array are exactly the core runtime, and no other primitives are required. The result is a list of two elements: first the list of all primitive values, and then a function that can be called to pass in two additional core functions used for inferred properties.</p> <p>The contents of a core runtime are given below. The names given are those used in r.bqn; the environment only provides a list of values and therefore doesn't need to use the same names. For named functions a description is given. For primitives, the implementation should match the BQN specification for that primitive on the specified domain, or the entire domain if left empty. They won't be called outside that domain except if there are bugs in r.bqn.</p> <table> <thead> @@ -398,122 +398,123 @@ </tr> <tr> <td align="right">1</td> -<td><code><span class='Function'>Decompose</span></code></td> -<td><code><span class='Function'>•Decompose</span></code></td> -</tr> -<tr> -<td align="right">2</td> -<td><code><span class='Function'>Glyph</span></code></td> -<td>(Unused) <code><span class='Function'>•Glyph</span></code> for primitive <code><span class='Value'>𝕩</span></code></td> -</tr> -<tr> -<td align="right">3</td> <td><code><span class='Function'>Fill</span></code></td> <td>Get or set the fill value for array <code><span class='Value'>𝕩</span></code></td> </tr> <tr> -<td align="right">4</td> +<td align="right">2</td> <td><code><span class='Function'>Log</span></code></td> <td><code><span class='Function'>⋆</span><span class='Modifier'>⁼</span></code> (natural or base-<code><span class='Value'>𝕨</span></code> logarithm) for atomic arguments</td> </tr> <tr> -<td align="right">5</td> +<td align="right">3</td> <td><code><span class='Function'>GroupLen</span></code></td> <td><code><span class='Function'>≠</span><span class='Modifier'>¨</span><span class='Function'>⊔</span><span class='Value'>𝕩</span></code> for a valid list <code><span class='Value'>𝕩</span></code></td> </tr> <tr> -<td align="right">6</td> +<td align="right">4</td> <td><code><span class='Function'>GroupOrd</span></code></td> <td><code><span class='Function'>∾⊔</span><span class='Value'>𝕩</span></code> provided <code><span class='Value'>𝕨</span></code> is <code><span class='Function'>GroupLen</span> <span class='Value'>𝕩</span></code></td> </tr> <tr> -<td align="right">7</td> +<td align="right">5</td> <td><code><span class='Function'>!</span></code></td> <td></td> </tr> <tr> -<td align="right">8</td> +<td align="right">6</td> <td><code><span class='Function'>+</span></code></td> <td>On two atoms</td> </tr> <tr> -<td align="right">9</td> +<td align="right">7</td> <td><code><span class='Function'>-</span></code></td> <td>On one or two atoms</td> </tr> <tr> -<td align="right">10</td> +<td align="right">8</td> <td><code><span class='Function'>×</span></code></td> <td>On two atoms</td> </tr> <tr> -<td align="right">11</td> +<td align="right">9</td> <td><code><span class='Function'>÷</span></code></td> <td>On one or two atoms</td> </tr> <tr> -<td align="right">12</td> +<td align="right">10</td> <td><code><span class='Function'>⋆</span></code></td> <td>On one or two atoms</td> </tr> <tr> -<td align="right">13</td> +<td align="right">11</td> <td><code><span class='Function'>⌊</span></code></td> <td>On one atom</td> </tr> <tr> -<td align="right">14</td> +<td align="right">12</td> <td><code><span class='Function'>=</span></code></td> <td>On one value or two atoms</td> </tr> <tr> -<td align="right">15</td> +<td align="right">13</td> <td><code><span class='Function'>≤</span></code></td> <td>On two atoms</td> </tr> <tr> -<td align="right">16</td> +<td align="right">14</td> <td><code><span class='Function'>≢</span></code></td> <td>For array <code><span class='Value'>𝕩</span></code></td> </tr> <tr> -<td align="right">17</td> +<td align="right">15</td> <td><code><span class='Function'>⥊</span></code></td> <td>For array <code><span class='Value'>𝕩</span></code> with no <code><span class='Value'>𝕨</span></code> or <code><span class='Value'>𝕨</span><span class='Function'>=</span><span class='Modifier2'>○</span><span class='Paren'>(</span><span class='Function'>×</span><span class='Modifier'>´</span><span class='Paren'>)</span><span class='Function'>≢</span><span class='Value'>𝕩</span></code></td> </tr> <tr> -<td align="right">18</td> +<td align="right">16</td> <td><code><span class='Function'>⊑</span></code></td> <td>For atom <code><span class='Value'>𝕨</span></code> and list <code><span class='Value'>𝕩</span></code></td> </tr> <tr> -<td align="right">19</td> +<td align="right">17</td> <td><code><span class='Function'>↕</span></code></td> <td>For natural number <code><span class='Value'>𝕩</span></code></td> </tr> <tr> -<td align="right">20</td> +<td align="right">18</td> <td><code><span class='Modifier'>⌜</span></code></td> <td>On arrays</td> </tr> <tr> -<td align="right">21</td> +<td align="right">19</td> <td><code><span class='Modifier'>`</span></code></td> <td></td> </tr> <tr> -<td align="right">22</td> +<td align="right">20</td> <td><code><span class='Modifier2'>_fillBy_</span></code></td> <td><code><span class='Function'>𝔽</span></code> with result fill computed using <code><span class='Function'>𝔾</span></code></td> </tr> <tr> -<td align="right">23</td> +<td align="right">21</td> <td><code><span class='Modifier2'>⊘</span></code></td> <td></td> </tr> +<tr> +<td align="right">—</td> +<td><code><span class='Function'>Decompose</span></code></td> +<td><code><span class='Function'>•Decompose</span></code></td> +</tr> +<tr> +<td align="right">—</td> +<td><code><span class='Function'>PrimInd</span></code></td> +<td>Index for primitive <code><span class='Value'>𝕩</span></code></td> +</tr> </tbody> </table> -<p>Remember that <code><span class='Function'>+</span></code> and <code><span class='Function'>-</span></code> can also work on characters in some circumstances, under the rules of affine characters. Other arithmetic functions should only accept numbers. <code><span class='Function'>=</span></code> must work on numbers, characters, and primitives, and should give <code><span class='Number'>0</span></code> without causing an error if the arguments have different types or one is a primitive and the other isn't. <code><span class='Function'>≤</span></code> must work on numbers and characters.</p> +<p>To define the final two functions, call the second returned element as a function, with argument <code><span class='Function'>Decompose</span><span class='Ligature'>‿</span><span class='Function'>PrimInd</span></code>. The function <code><span class='Function'>PrimInd</span></code> gives the index of <code><span class='Value'>𝕩</span></code> in the list of all primitives (defined as <code><span class='Value'>glyphs</span></code> in pr.bqn), or the length of the runtime if <code><span class='Value'>𝕩</span></code> is not a primitive. The two functions are only needed for computing inferred properties, and are defined by default so that every value is assumed to be a primitive, and <code><span class='Function'>PrimInd</span></code> performs a linear search over the returned runtime. If the runtime is used directly, then this means that without setting <code><span class='Function'>Decompose</span><span class='Ligature'>‿</span><span class='Function'>PrimInd</span></code>, function inferred properties will work slowly and for primitives only; if values from the runtime are wrapped then function inferred properties will not work at all.</p> +<p>Remember that <code><span class='Function'>+</span></code> and <code><span class='Function'>-</span></code> can also work on characters in some circumstances, under the rules of affine characters. Other arithmetic functions should only accept numbers. <code><span class='Function'>=</span></code> must work on any atoms including functions and modifiers. <code><span class='Function'>≤</span></code> must work on numbers and characters.</p> <h3 id="grouplen-and-groupord">GroupLen and GroupOrd</h3> <p>GroupLen and GroupOrd, short for Group length and Group order, are used to implement <a href="../doc/group.html">Group</a> (<code><span class='Function'>⊔</span></code>) and also to grade small-range lists and invert permutations (the inverse of a permutation <code><span class='Value'>p</span></code> is <code><span class='Number'>1</span><span class='Modifier'>¨</span><span class='Modifier2'>⊸</span><span class='Function'>GroupOrd</span> <span class='Value'>p</span></code>). Each of these only needs to work on lists of integers. Shown below are efficient implementations using BQN extended with the notation <code><span class='Paren'>(</span><span class='Value'>i</span><span class='Function'>⊑</span><span class='Value'>l</span><span class='Paren'>)</span> <span class='Function'>Fn</span><span class='Gets'>↩</span> <span class='Value'>x</span></code> meaning <code><span class='Value'>l</span> <span class='Gets'>↩</span> <span class='Function'>Fn</span><span class='Modifier2'>⟜</span><span class='Value'>x</span><span class='Modifier2'>⌾</span><span class='Paren'>(</span><span class='Value'>i</span><span class='Modifier2'>⊸</span><span class='Function'>⊑</span><span class='Paren'>)</span> <span class='Value'>l</span></code>, where <code><span class='Function'>Fn</span></code> is <code><span class='Function'>⊢</span></code> if omitted. Since these special assignments only change one element of <code><span class='Value'>l</span></code>, each can be a fast constant-time operation.</p> <pre><span class='Function'>GroupLen</span> <span class='Gets'>←</span> <span class='Brace'>{</span> diff --git a/implementation/vm.md b/implementation/vm.md index 302717e0..c8e0986e 100644 --- a/implementation/vm.md +++ b/implementation/vm.md @@ -113,38 +113,40 @@ The **SETN**, **SETU**, and **SETM** instructions set a value for a reference. I Primitive functions and modifiers used in a program are stored in its `consts` array. The compiler needs to be passed a *runtime* with the value of every primitive so that these functions and modifiers are available. -While it's perfectly possible to implement the runtime from scratch, the pseudo-BQN file [r.bqn](../src/r.bqn) implements the full runtime in terms of a *core runtime* consisting of a smaller number of much simpler functions. [pr.bqn](../src/pr.bqn) converts this file so that it can be compiled. It changes values in the core runtime to primitives and primitives to generated identifiers, so that the first 21 values in the output's `consts` array are exactly the core runtime, and no other primitives are required. +While it's perfectly possible to implement the runtime from scratch, the pseudo-BQN file [r.bqn](../src/r.bqn) implements the full runtime in terms of a *core runtime* consisting of a smaller number of much simpler functions. [pr.bqn](../src/pr.bqn) converts this file so that it can be compiled. It changes values in the core runtime to primitives and primitives to generated identifiers, so that the first 22 values in the output's `consts` array are exactly the core runtime, and no other primitives are required. The result is a list of two elements: first the list of all primitive values, and then a function that can be called to pass in two additional core functions used for inferred properties. The contents of a core runtime are given below. The names given are those used in r.bqn; the environment only provides a list of values and therefore doesn't need to use the same names. For named functions a description is given. For primitives, the implementation should match the BQN specification for that primitive on the specified domain, or the entire domain if left empty. They won't be called outside that domain except if there are bugs in r.bqn. | Ind | Name | Description / restrictions |----:|------------|--------------------------- | 0 | `Type` | `•Type` -| 1 | `Decompose`| `•Decompose` -| 2 | `Glyph` | (Unused) `•Glyph` for primitive `𝕩` -| 3 | `Fill` | Get or set the fill value for array `𝕩` -| 4 | `Log` | `⋆⁼` (natural or base-`𝕨` logarithm) for atomic arguments -| 5 | `GroupLen` | `≠¨⊔𝕩` for a valid list `𝕩` -| 6 | `GroupOrd` | `∾⊔𝕩` provided `𝕨` is `GroupLen 𝕩` -| 7 | `!` | -| 8 | `+` | On two atoms -| 9 | `-` | On one or two atoms -| 10 | `×` | On two atoms -| 11 | `÷` | On one or two atoms -| 12 | `⋆` | On one or two atoms -| 13 | `⌊` | On one atom -| 14 | `=` | On one value or two atoms -| 15 | `≤` | On two atoms -| 16 | `≢` | For array `𝕩` -| 17 | `⥊` | For array `𝕩` with no `𝕨` or `𝕨=○(×´)≢𝕩` -| 18 | `⊑` | For atom `𝕨` and list `𝕩` -| 19 | `↕` | For natural number `𝕩` -| 20 | `⌜` | On arrays -| 21 | `` ` `` | -| 22 | `_fillBy_` | `𝔽` with result fill computed using `𝔾` -| 23 | `⊘` | - -Remember that `+` and `-` can also work on characters in some circumstances, under the rules of affine characters. Other arithmetic functions should only accept numbers. `=` must work on numbers, characters, and primitives, and should give `0` without causing an error if the arguments have different types or one is a primitive and the other isn't. `≤` must work on numbers and characters. +| 1 | `Fill` | Get or set the fill value for array `𝕩` +| 2 | `Log` | `⋆⁼` (natural or base-`𝕨` logarithm) for atomic arguments +| 3 | `GroupLen` | `≠¨⊔𝕩` for a valid list `𝕩` +| 4 | `GroupOrd` | `∾⊔𝕩` provided `𝕨` is `GroupLen 𝕩` +| 5 | `!` | +| 6 | `+` | On two atoms +| 7 | `-` | On one or two atoms +| 8 | `×` | On two atoms +| 9 | `÷` | On one or two atoms +| 10 | `⋆` | On one or two atoms +| 11 | `⌊` | On one atom +| 12 | `=` | On one value or two atoms +| 13 | `≤` | On two atoms +| 14 | `≢` | For array `𝕩` +| 15 | `⥊` | For array `𝕩` with no `𝕨` or `𝕨=○(×´)≢𝕩` +| 16 | `⊑` | For atom `𝕨` and list `𝕩` +| 17 | `↕` | For natural number `𝕩` +| 18 | `⌜` | On arrays +| 19 | `` ` `` | +| 20 | `_fillBy_` | `𝔽` with result fill computed using `𝔾` +| 21 | `⊘` | +| — | `Decompose`| `•Decompose` +| — | `PrimInd` | Index for primitive `𝕩` + +To define the final two functions, call the second returned element as a function, with argument `Decompose‿PrimInd`. The function `PrimInd` gives the index of `𝕩` in the list of all primitives (defined as `glyphs` in pr.bqn), or the length of the runtime if `𝕩` is not a primitive. The two functions are only needed for computing inferred properties, and are defined by default so that every value is assumed to be a primitive, and `PrimInd` performs a linear search over the returned runtime. If the runtime is used directly, then this means that without setting `Decompose‿PrimInd`, function inferred properties will work slowly and for primitives only; if values from the runtime are wrapped then function inferred properties will not work at all. + +Remember that `+` and `-` can also work on characters in some circumstances, under the rules of affine characters. Other arithmetic functions should only accept numbers. `=` must work on any atoms including functions and modifiers. `≤` must work on numbers and characters. ### GroupLen and GroupOrd |