I'll start with a recap from last time. We are doing some parsing of a BQN expression that has only functions, numbers, and parentheses.
x←'((-3)+√(3×3)-4×2×1)÷2×2'
So far we have found where the opening and closing parentheses are and reordered them so that matching pairs have the same location.
In BQN:
o←'('=x⋄c←')'=x⋄d←+`o-c⋄b←/o⋄e←/c
{(⍋𝕩⊏d)⊏𝕩}¨b‿e
In APL:
o←'('=x⋄c←')'=x⋄d←+⍀o-c⋄b←⍸o⋄e←⍸c
{⍵[⍋d[⍵]]}¨b e
So the idea is that b is the indices of opening parentheses and e is the indices of closed parentheses, and we can sort each of these lists of indices by their nesting depth to match them together.
What I'd like to do now is actually use this information. I want to convert my BQN code to reverse Polish notation (RPN), which is the format used by stack-based virtual machines like WebAssembly.
I don't think we'll get all the way through, but we should be able to make some progress.
The crucial idea is that all we need to do is move every function past its right argument. For example, -3 becomes 3- and 3×3 becomes 33×. But we can't just move functions over by one because sometimes the right argument is more than a single number.
For example, ÷ is the last operation performed and it needs to go all the way to the end.
In APL/BQN, this idea is captured by the idea of a "long right scope": the right argument of a function is everything to its right up to the next enclosing parenthesis. The parenthesis matching code we did earlier can help us find that enclosing parenthesis.
But first, I'm going to look a little at this "move a function right" operation. Let's say we have a flat expression such as 3+√2×8.
Because there are no parentheses, every function's right argument goes up to the end of the expression.
So we want to move every function "to the end", except not really because only one of them can actually go to the end of the expression. But nonetheless that's the idea I'm going to start with.
To start with, I'm just going to identify the functions in the code.
x←"3+√2×8"
¬x∊•d now gives
[ 0 1 1 0 1 0 ]
I'm going to construct a permutation (as a list of indices) that will take us from BQN to RPN in one step. I'll start with the identity permutation.
↕≠x
[ 0 1 2 3 4 5 ]
Or ⍳⍴x in classic APL.
Let's assign f←¬x∊•d, indicating functions.
How far over do I need to move my functions? I can subtract the identity permutation from the last index to find this:
f×(¯1+≠x)-↕≠x
[ 0 4 3 0 1 0 ]
Adding this to our identity permutation gives us... not a permutation:
(↕≠x)+f×(¯1+≠x)-↕≠x
[ 0 5 5 3 5 5 ]
I need to not just add to the index of each function, but subtract one from the index of everything to its right. In other words, we want to subtract from each index the number of functions that appear before it.
That's a prefix sum!
+`f
[ 0 1 2 2 3 3 ]
Since this starts subtracting at the function itself, rather than after it, we should add one to the function offsets, giving f×(≠x)-↕≠x. That's actually simpler, since it uses the index one past the end rather than the last index. Similarly, with parentheses it will be the index of the parenthesis itself.
Add it all together now:
(↕≠x)+(f×(≠x)-↕≠x)-+`f
[ 0 5 4 1 3 2 ]
It's a permutation, at least. Let's set l←≠x since x is never used directly, just its length.
Quick Question: Why are we writing the interpreter in APL/BQN? I thought you'd said you didn't know very much about bootstrapping. And I'd have thought it'd be written in something like C...
Also, Aaron's work on Co-dfns indicates that a compiler in BQN can be faster than one written in traditional C style, because array operations are very easy for CPUs or GPUs.
@AviF.S. - Also, sometimes it's easier to express a concept in the language you're implementing, and then, once you have fully analysed it, go back to the actual implementation language to code it.
@Marshall Of course; same! But if the purpose is to write an interpreter wouldn't it be more helpful to write it in the language we're using. Imperative OOP programming is a very different style...
@JeffZeitlin Agreed when it's something like Python → Java/C. But not from one domain to another IMO. It's like implementing Prolog or Haskell in itself instead of in C, no?
The algorithms we're using are a million percent unrelated to the way they'd be done with a C-like lang. For instance the parentheses bit is completely array-oriented. There's surely well-established and very different algorithms for C-like parsing
Since I am currently doing my work in BQN, I find it easier to do these things mainly with BQN. But I should also provide an APL translation of that last part now...
@user9772759 This is episode 2 of the "APL Seeds" series on implementing APL-like languages. The language in focus is BQN, but it all applies to any similar language.
Heh... have been using it for multiple days now... so not quite fluent of all symbols. But I do understand the concept of "long right scope" (and I agree that it's quite key)
@Marshall Was/is the point of this discussion that you want to translate "math" into reverse polish for the purpose of efficient implementation of it in BQN?
The thing we just did is a little like ⍋(fe⌈↕l)-ia when sel is being computed. fe are the function endpoints, and ia are index adjustments for the things we move them past.
@user9772759 The most direct purpose is to generate WebAssembly code: you just replace each number and each function with the right sequence of bytes and you have the body of a Wasm function.
Of course the reason Wasm uses this format is that it's more generally a good intermediate representation for compiling. You can do various optimization passes on it and also turn it into x86 or some other machine code by allocating registers.
@RGS Functions in the Wasm docs. They're just arbitrary numbers.
@user9772759 Which does work. I am currently doing automated tests in Node since the BQN2NGN prototype is Javascript. It runs BQN2NGN to compile the test cases into numeric arrays and then turns these into JS byte arrays to run as Wasm.
@RGS Yes, I'd like it to run in the browser so people can use it right away. Wasm can also be run natively anywhere so it's nice for portability, and it's a reasonably easy format to target.
A little frustrating that you can't run Wasm bytecode directly from Wasm and have to compile it first by calling out to a Javascript helper. With machine code you can just write and jump.
@RGS For a lot of reasons it's useful to compile or recompile code as the program is running (JIT compilation). But WebAssembly's not really designed for this, so while you can generate the Wasm code, that is, an array of bytes, from a Wasm program (such as a running BQN program), you have to do a lot of work to turn that code into a function you can call. And subject yourself to overhead from whatever is compiling your Wasm to native code.
I think that ends our APL Seeds session. I'm still here for questions, though.
