diff options
| author | Marshall Lochbaum <mwlochbaum@gmail.com> | 2021-08-11 14:06:02 -0400 |
|---|---|---|
| committer | Marshall Lochbaum <mwlochbaum@gmail.com> | 2021-08-11 14:06:02 -0400 |
| commit | 65eef4fade5eb426dae01d480f383b8a30b23071 (patch) | |
| tree | d5d98e372f68c928b7aaa2741f26cf89d5745ffc /docs/implementation | |
| parent | e64ea0c5da34a59393e3b539cc1811ac63dfe3f4 (diff) | |
Change "BQN / main" in header to "(github) / BQN"
Diffstat (limited to 'docs/implementation')
| -rw-r--r-- | docs/implementation/codfns.html | 2 | ||||
| -rw-r--r-- | docs/implementation/compile/dynamic.html | 2 | ||||
| -rw-r--r-- | docs/implementation/compile/index.html | 2 | ||||
| -rw-r--r-- | docs/implementation/index.html | 2 | ||||
| -rw-r--r-- | docs/implementation/kclaims.html | 2 | ||||
| -rw-r--r-- | docs/implementation/primitive/index.html | 2 | ||||
| -rw-r--r-- | docs/implementation/primitive/random.html | 2 | ||||
| -rw-r--r-- | docs/implementation/primitive/replicate.html | 2 | ||||
| -rw-r--r-- | docs/implementation/primitive/sort.html | 2 | ||||
| -rw-r--r-- | docs/implementation/vm.html | 2 |
10 files changed, 10 insertions, 10 deletions
diff --git a/docs/implementation/codfns.html b/docs/implementation/codfns.html index 48b1d1b9..57cfa3d5 100644 --- a/docs/implementation/codfns.html +++ b/docs/implementation/codfns.html @@ -3,7 +3,7 @@ <link href="../style.css" rel="stylesheet"/> <title>Co-dfns versus BQN's implementation</title> </head> -<div class="nav"><a href="https://github.com/mlochbaum/BQN">BQN</a> / <a href="../index.html">main</a> / <a href="index.html">implementation</a></div> +<div class="nav">(<a href="https://github.com/mlochbaum/BQN">github</a>) / <a href="../index.html">BQN</a> / <a href="index.html">implementation</a></div> <h1 id="co-dfns-versus-bqns-implementation">Co-dfns versus BQN's implementation</h1> <p>The BQN self-hosted compiler is directly inspired by the <a href="https://github.com/Co-dfns/Co-dfns">Co-dfns</a> project, a compiler for a subset of <a href="../doc/fromDyalog.html">Dyalog APL</a>. I'm very grateful to Aaron for showing that array-oriented compilation is even possible! In addition to the obvious difference of target language, BQN differs from Co-dfns both in goals and methods.</p> <p>The shared goals of BQN and Co-dfns are to implement a compiler for an array language with whole-array operations. This provides the theoretical benefit of a short <em>critical path</em>, which in practice means that both compilers can make good use of a GPU or a CPU's vector instructions simply by providing an appropriate runtime (however, only Co-dfns has such a runtime—an ArrayFire program on the GPU and Dyalog APL on the CPU). The two implementations also share a preference for working "close to the metal" by passing around arrays of numbers rather than creating abstract types to work with data. Objects are right out. These choices lead to a compact source code implementation, and may have some benefits in terms of how easy it is to write and understand the compiler.</p> diff --git a/docs/implementation/compile/dynamic.html b/docs/implementation/compile/dynamic.html index 1d232644..1edb73ef 100644 --- a/docs/implementation/compile/dynamic.html +++ b/docs/implementation/compile/dynamic.html @@ -3,7 +3,7 @@ <link href="../../style.css" rel="stylesheet"/> <title>BQN: Dynamic compilation</title> </head> -<div class="nav"><a href="https://github.com/mlochbaum/BQN">BQN</a> / <a href="../../index.html">main</a> / <a href="../index.html">implementation</a> / <a href="index.html">compile</a></div> +<div class="nav">(<a href="https://github.com/mlochbaum/BQN">github</a>) / <a href="../../index.html">BQN</a> / <a href="../index.html">implementation</a> / <a href="index.html">compile</a></div> <h1 id="dynamic-compilation">Dynamic compilation</h1> <p>This page discusses at a high level (without covering any specific source transformations) how compilation and interpretation might be structured in order to execute BQN faster. Effective strategies will compile parts of the program with more specialization or higher optimization as it runs and more information about it becomes known.</p> <p>To avoid confusion, an <strong>interpreter</strong> evaluates code to perform actions or produce a result; a CPU is a machine code interpreter. A <strong>compiler</strong> transforms code in one language or format to another. To run a program that does anything, it must eventually be interpreted; before this the program or parts of it might be compiled any number of times.</p> diff --git a/docs/implementation/compile/index.html b/docs/implementation/compile/index.html index 2ee01371..4ec585f0 100644 --- a/docs/implementation/compile/index.html +++ b/docs/implementation/compile/index.html @@ -3,7 +3,7 @@ <link href="../../style.css" rel="stylesheet"/> <title>BQN: Optimizing compilation notes</title> </head> -<div class="nav"><a href="https://github.com/mlochbaum/BQN">BQN</a> / <a href="../../index.html">main</a> / <a href="../index.html">implementation</a></div> +<div class="nav">(<a href="https://github.com/mlochbaum/BQN">github</a>) / <a href="../../index.html">BQN</a> / <a href="../index.html">implementation</a></div> <h1 id="optimizing-compilation-notes">Optimizing compilation notes</h1> <p>Pages here discuss advanced compilation strategies for BQN, that is, steps that might take take place after compiling to bytecode or a similar intermediate representation.</p> <p>Most content here is currently speculative: C, Java, and Javascript backends are capable of compiling to native (x86, JVM, or Javascript) code in order to lower evaluation overhead but don't perform much if any analysis to improve this code. CBQN is likely to start making such optimizations in the future.</p> diff --git a/docs/implementation/index.html b/docs/implementation/index.html index 4cf1d1dc..d0b73c59 100644 --- a/docs/implementation/index.html +++ b/docs/implementation/index.html @@ -3,7 +3,7 @@ <link href="../style.css" rel="stylesheet"/> <title>BQN implementation notes</title> </head> -<div class="nav"><a href="https://github.com/mlochbaum/BQN">BQN</a> / <a href="../index.html">main</a></div> +<div class="nav">(<a href="https://github.com/mlochbaum/BQN">github</a>) / <a href="../index.html">BQN</a></div> <h1 id="bqn-implementation-notes">BQN implementation notes</h1> <p>Notes about how BQN is or could be implemented.</p> <p>This repository's BQN implementation is written mainly in BQN: the bytecode <a href="https://github.com/mlochbaum/BQN/blob/master/implementation/../src/c.bqn">compiler</a> is completely self-hosted, and the majority of the runtime (<a href="https://github.com/mlochbaum/BQN/blob/master/implementation/../src/r0.bqn">r0</a>, <a href="https://github.com/mlochbaum/BQN/blob/master/implementation/../src/r1.bqn">r1</a>) is written in BQN except that it is allowed to define primitives; some preprocessing (<a href="https://github.com/mlochbaum/BQN/blob/master/implementation/../src/pr.bqn">pr</a>) turns the primitives into identifiers.</p> diff --git a/docs/implementation/kclaims.html b/docs/implementation/kclaims.html index 667ff0fa..4d028e6c 100644 --- a/docs/implementation/kclaims.html +++ b/docs/implementation/kclaims.html @@ -3,7 +3,7 @@ <link href="../style.css" rel="stylesheet"/> <title>BQN: Wild claims about K performance</title> </head> -<div class="nav"><a href="https://github.com/mlochbaum/BQN">BQN</a> / <a href="../index.html">main</a> / <a href="index.html">implementation</a></div> +<div class="nav">(<a href="https://github.com/mlochbaum/BQN">github</a>) / <a href="../index.html">BQN</a> / <a href="index.html">implementation</a></div> <h1 id="wild-claims-about-k-performance">Wild claims about K performance</h1> <p>Sometimes I see unsourced, unclear, vaguely mystical claims about K being the fastest array language. It happens often enough that I'd like to write a long-form rebuttal to these, and a demand that the people who make these do more to justify them.</p> <p>This isn't meant to put down the K language! K is in fact the only APL-family language other than BQN that I would recommend without reservations. And there's nothing wrong with the K community as a whole. Go to <a href="https://chat.stackexchange.com/rooms/90748/the-k-tree">the k tree</a> and meet them! What I want to fight is the <em>myth</em> of K, which is carried around as much by those who used K once upon a time, and no longer have any connection to it, as by active users.</p> diff --git a/docs/implementation/primitive/index.html b/docs/implementation/primitive/index.html index 25c831c3..b5256302 100644 --- a/docs/implementation/primitive/index.html +++ b/docs/implementation/primitive/index.html @@ -3,7 +3,7 @@ <link href="../../style.css" rel="stylesheet"/> <title>BQN: Primitive implementation notes</title> </head> -<div class="nav"><a href="https://github.com/mlochbaum/BQN">BQN</a> / <a href="../../index.html">main</a> / <a href="../index.html">implementation</a></div> +<div class="nav">(<a href="https://github.com/mlochbaum/BQN">github</a>) / <a href="../../index.html">BQN</a> / <a href="../index.html">implementation</a></div> <h1 id="primitive-implementation-notes">Primitive implementation notes</h1> <p>Commentary on the best methods I know for implementing various primitives. Often there are many algorithms that are viable in different situations, and in these cases I try to discuss the tradeoffs.</p> <ul> diff --git a/docs/implementation/primitive/random.html b/docs/implementation/primitive/random.html index 943fd955..7f660792 100644 --- a/docs/implementation/primitive/random.html +++ b/docs/implementation/primitive/random.html @@ -3,7 +3,7 @@ <link href="../../style.css" rel="stylesheet"/> <title>BQN: Implementation of random stuff</title> </head> -<div class="nav"><a href="https://github.com/mlochbaum/BQN">BQN</a> / <a href="../../index.html">main</a> / <a href="../index.html">implementation</a> / <a href="index.html">primitive</a></div> +<div class="nav">(<a href="https://github.com/mlochbaum/BQN">github</a>) / <a href="../../index.html">BQN</a> / <a href="../index.html">implementation</a> / <a href="index.html">primitive</a></div> <h1 id="implementation-of-random-stuff">Implementation of random stuff</h1> <p>Not a primitive, but CBQN's <code><span class='Function'>•MakeRand</span></code> initializes a random number generator that has some built-in utilities. For clarity we'll call a result of this initialization <code><span class='Value'>rand</span></code> in the text below.</p> <h2 id="random-number-generation">Random number generation</h2> diff --git a/docs/implementation/primitive/replicate.html b/docs/implementation/primitive/replicate.html index 5b9cf07b..9d539d40 100644 --- a/docs/implementation/primitive/replicate.html +++ b/docs/implementation/primitive/replicate.html @@ -3,7 +3,7 @@ <link href="../../style.css" rel="stylesheet"/> <title>BQN: Implementation of Indices and Replicate</title> </head> -<div class="nav"><a href="https://github.com/mlochbaum/BQN">BQN</a> / <a href="../../index.html">main</a> / <a href="../index.html">implementation</a> / <a href="index.html">primitive</a></div> +<div class="nav">(<a href="https://github.com/mlochbaum/BQN">github</a>) / <a href="../../index.html">BQN</a> / <a href="../index.html">implementation</a> / <a href="index.html">primitive</a></div> <h1 id="implementation-of-indices-and-replicate">Implementation of Indices and Replicate</h1> <p>The replicate family of functions contains not just primitives but powerful tools for implementing other functionality. The most important is converting <a href="#booleans-to-indices">bits to indices</a>: AVX-512 extensions implement this natively for various index sizes, and even with no SIMD support at all there are surprisingly fast table-based algorithms for it.</p> <p><a href="#replicate">General replication</a> is more complex. Branching will slow many useful cases down considerably when using the obvious solution. However, branch-free techniques introduce overhead for larger replication amounts. Hybridizing these seems to be the only way, but it's finicky.</p> diff --git a/docs/implementation/primitive/sort.html b/docs/implementation/primitive/sort.html index 86c36738..2a417770 100644 --- a/docs/implementation/primitive/sort.html +++ b/docs/implementation/primitive/sort.html @@ -3,7 +3,7 @@ <link href="../../style.css" rel="stylesheet"/> <title>BQN: Implementation of ordering functions</title> </head> -<div class="nav"><a href="https://github.com/mlochbaum/BQN">BQN</a> / <a href="../../index.html">main</a> / <a href="../index.html">implementation</a> / <a href="index.html">primitive</a></div> +<div class="nav">(<a href="https://github.com/mlochbaum/BQN">github</a>) / <a href="../../index.html">BQN</a> / <a href="../index.html">implementation</a> / <a href="index.html">primitive</a></div> <h1 id="implementation-of-ordering-functions">Implementation of ordering functions</h1> <p>The <a href="../../doc/order.html">ordering functions</a> are Sort (<code><span class='Function'>∧∨</span></code>), Grade (<code><span class='Function'>⍋⍒</span></code>), and Bins (<code><span class='Function'>⍋⍒</span></code>). Although these are well-studied—particularly sorting, and then binary search or "predecessor search"—there are many recent developments, as well as techniques that I have not found in the literature. The three functions are closely related but have important differences in what algorithms are viable. Sorting is a remarkably deep problem with different algorithms able to do a wide range of amazing things, and sophisticated ways to combine those. It is by no means solved. In comparison, Bins is pretty tame.</p> <p>There's a large divide between ordering compound data and simple data. For compound data comparisons are expensive, and the best algorithm will generally be the one that uses the fewest comparisons. For simple data they fall somewhere between cheap and extremely cheap, and fancy branchless and vectorized algorithms are the best.</p> diff --git a/docs/implementation/vm.html b/docs/implementation/vm.html index 109416ff..1ecac46c 100644 --- a/docs/implementation/vm.html +++ b/docs/implementation/vm.html @@ -3,7 +3,7 @@ <link href="../style.css" rel="stylesheet"/> <title>The BQN virtual machine and runtime</title> </head> -<div class="nav"><a href="https://github.com/mlochbaum/BQN">BQN</a> / <a href="../index.html">main</a> / <a href="index.html">implementation</a></div> +<div class="nav">(<a href="https://github.com/mlochbaum/BQN">github</a>) / <a href="../index.html">BQN</a> / <a href="index.html">implementation</a></div> <h1 id="the-bqn-virtual-machine-and-runtime">The BQN virtual machine and runtime</h1> <p>BQN's self-hosted compiler and runtime mean that only a small amount of native code is needed to run BQN on any given platform. The <a href="https://github.com/mlochbaum/BQN/blob/master/implementation/../docs/bqn.js">Javascript environment</a> requires about 500 lines of Javascript code including system functions and performance improvements; probably around 250 would be required just to run the core language. This makes it fairly easy to port BQN to new platforms, allowing BQN to be <a href="../doc/embed.html">embedded</a> within other programming languages and interact with arrays or functions in those languages.</p> <p>The way data is represented is part of the VM implementation: it can use native arrays or a custom data structure, depending on what the language supports. An initial implementation will be very slow, but can be improved by replacing functions from the BQN-based runtime with native code. As the VM system can be hard to work with if you're not familiar with it, I advise you to contact me to discuss implementing a VM if you are interested.</p> |
