CMC: implement gram-schmidt orthogonalization. That is, implement a function that accepts a matrix and returns a matrix M with the same shape, such that (⍉+.*⊢)M is a diagonal matrix and the input and output matrices have columns that generate the same space
(i.e every column of M is a linear combination of the columns of the input and vice-versa)
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.
@Marshall so what you are saying is that there is an extra step (a costly step) between generating the bytecode for a BQN program and then executing said bytecode?
@user9772759 We had some discussions about new array language ideas within Dyalog starting in February or March. I made a prototype interpreter in May after giving notice to leave Dyalog and started on the real thing when I left about three weeks ago.
@RGS Assuming a Wasm backend. I plan to work on other backends as well, although of course they won't be usable on the web.
@Marshall (Take my feedback for what it's worth, i.e. probably not much. As I said, I have several days of APL experience now, and a few weeks of K about 15-20 years ago).
@Marshall That said, reading your github repo now... some of the fundamental ideas of BQN sounds really interesting and appealing. OTOH, can't say that I like the idea of "typing" based on names (feels ... Fortranish?) or the glyph patterns (e.g. superscripts are modifiers). The latter is probably just something to get used to though...
@RGS Nearly everything will be written in BQN, and the parts that generate Wasm code will be fairly small, so it should be possible to replace them and target another architecture easily. You would choose the appropriate BQN implementation or backend based on where you want to run it, like most software.
@user9772759 The way names are written describes how they are being used at the moment, not what the value is. It's more like the way func in C is a pointer except func(... is a function call.
@Marshall No... I get that. Not sure that I buy the comparison to C though. "func" is a pointer and "func()" is how you call a function pointer, but I digress.
@Marshall Also, you have 6 types, 3 of them have naming requirements. I.e. naming something F is declaring it to have the type "function".
@Marshall So it's half typed by naming, and half untyped?
@FredrikNiemelä No, the point is that a value named F doesn't have to have a function type. You can also use characters, numbers, or arrays, which return themselves when applied, and modifiers or compositions, although these will give an error when applied.
The syntactic role tells you which things apply to which other things, but it has no semantic value. It's discarded after parsing.
I'm a bit confused here. You say that (what I call) the type information has not semantic value and will be discarded after parsing. But... if you apply a ... thing (is value the correct term) of the wrong type you will get a parse error, right?
Oh... so a value "x" could "contain" anything, including a function, but you would have to assign it to something like "X" to actually be able to use it?
It's definitely annoying to have something that's so far from a programmer's normal expectations, but as you see the actual concept isn't too hard. The good thing is it seems I will get a lot of practice explaining it!
@FredrikNiemelä Sort of? You definitely have the right idea, but I don't know whether that is a good way to think about it (not saying it's bad, I'm genuinely unsure).
@Marshall Yeah... the problem you linked to is kinda what was getting at. I think this is a bit of a fundamental problem (and IMHO a sign that this is maybe not great?)
Now I understand your comparison to C earlier :).
Basically uppercasing is exactly the same thing as appending ().
And _ and case is not actually part of the "name" of the value.
@FredrikNiemelä It's a third of the way down the list, which is getting into pretty tolerable territory. It's the only way I know of to have something that looks like APL and is context-free, so I'd be okay with a lot worse. And it makes functions first class as a bonus!
@FredrikNiemelä Per the tokenizing rules, yes. You don't have to draw the line between scanning and parsing there, but I think it makes a lot more sense that way.
@FredrikNiemelä Needed is a weird word (after all, you can simply define ∘ as {𝔽𝕨𝔾𝕩}), but yes, you could use 2-trains instead of ∘ everywhere if you wanted.
@FredrikNiemelä Trains can be included in ordinary APL and are in most actively developed APLs (GNU is the only exception I can think of). The real benefit is not the 2-train, which is redundant as you note, but the 3-train, which lets you call several functions on the same set of arguments in a very natural way.
@FredrikNiemelä Thanks for asking! One of the most important things in programming language work I think is figuring out how people do/can/should relate to programming ideas or paradigms, so this sort of discussion is actually really valuable.
I know I said no rush, but then I remembered that I'm giving a webinar basically on "APLcart News" in a week. I've pushed a few things, but nothing major.
@RGS I've changed the dyadic operators' list to say "Compositions (Compose, Reverse Compose, Beside, Atop, Over) ∙ Inner Product ∙ Power …" so there's now room for a general compositions page.
@Adám another question: what is the rationale for adding DOC links? for something like (¯1∘⎕C≠⊢)D does it still make sense to link to the page about ⎕C? I would say so, but not sure what your standard is
(why do you have ¯1∘⎕C≠⊢ instead of 1∘⎕C=⊢ to check for lower-case-ness?)
To exclude those, we'd have to write (1∘⎕C≠⊢)∧(¯1∘⎕C=⊢)
@RGS They fail because the do change when uppercased, but they are not lowercase, since they also change when lowercased. They are true titlecase characters, and are only in Unicode for historical reasons.
Notice e.g. that dzaima doesn't use "dz" but rather "dz" even though he considers those two glyphs as forming a single letter (a Latin substitute for a single Cyrillic letter).
@Adám done; I created the PR against master because I started working on top of it and didn't notice you had already some (minor) progress on the 18.0 branch. If you review the PR and conclude all is good, then merging my PR means you can delete your branch (if I understood everything correctly)
How can people find about the /challenge and /what pages? I can't seem to find them linked from the main page; is this something you considered doing? maybe linking to them from the footer?
@FredrikNiemelä The scripting and multi-line functionality is still experimental, but this should work (and put your interpreter into a tight loop you can't easily get out of, so save your work and be ready to kill the process):
@matt APL is a mathematical notation that generalises and harmonises concepts from Traditional Mathematical Notation (TMN) so it becomes unambiguous and therefore machine executable. It can then also be used as A Programming Language.
APL is a programming language that removes much of the usual burden of programming from the programmer and gives it to the computer to deal with. It is especially well suited for domain experts who can then write their own programs instead of having to communicate their needs to a professional programmer for implementation.
