The APL Orchard

Bubbler

12:26 AM

Showcase: Elegance wins over ugly brute-force

dzaima

12:27 PM

a couple more characters, mostly for the app

dzaima

12:41 PM

now that i've done the current batch of app things, back to working on the language itself

RGS

@dzaima isn't the third of the first line the same as the second one from the second line?

dzaima

@RGS i'm just adding it in the second line for comparison

(also shows the pointy end which is overlapped in the center of ⌦⌫ because the character is just too wide)

Marshall

1:20 PM

@dzaima How do I stringify a number in dzaima/BQN? ⍕ gives me a syntax error.

dzaima

@Marshall i removed ⍕ as part of my batch-BQNifying, so no native way currently

(also value blocks (with no returns they're still mostly useless))

re-added ⍕; beware, it's •pp-dependent

(also it's monadic only)

Marshall

Trains now working in the bytecode backend.

dzaima

:o

added 'a'•COMP for immediate execution (and actually re-added ⍕ ಠ_ಠ)

AviFS

2:25 PM

@Marshall What is today’s APL Seeds topic? (Will try to follow along, but still no charger so am on phone)

Marshall

@AviFS Parsing expressions with parentheses.

Adám

@Marshall Wiki updated.

Marshall

In the first lesson we matched parentheses, and in the second we parsed an expression without parentheses.

Adám

@Marshall You know how to great and begin, by now.

Marshall

...I know how to greet.

Welcome everyone to APL Seeds episode 3!

Last time we were able to "compile" the APL-syntax expression 3+√2×8 to the reverse Polish 328×√+.

Today we are going to handle parentheses, so we'll now do the more complicated expression ((-3)+√(3×3)-4×2×1)÷2×2.

We're only shuffling the terms around, so there's actually a part missing in that we won't keep track of how many arguments each function has.

So in the output, both -s will appear the same even though one is monadic and one is dyadic.

Here's the code we had last time, in BQN:

x←"3+√2×8"
f←¬x∊•d
l←≠x
x⊏˜(↕l)+(f×l-↕l)-+`f

And in APL:

x←'3+√2×8'
f←~x∊⎕d
l←≢x
x[⍋(⍳l)+(f×l-⍳l)-+⍀f]

The idea here is that we push every function forward to the end of the expression (l), and compensate by moving everything it goes past backwards by 1 (-+`f).

When we have parentheses, we instead want to push every function up to the containing closing parentheses, or the end if it's at the top level.

So I want to find the index of the closing parenthesis for every character in the expression.

The idea here is similar to what we did in the first APL Seeds. We are going to sort the whole expression by nesting depth.

I'm starting with these definitions, which are the same as above with a different expression:

x←"((-3)+√(3×3)-4×2×1)÷2×2"
l←≠x
f←¬x∊•d

Let's find masks for the opening and closing parentheses, and the nesting depth.

o←x='(' ⋄ c←x=')' ⋄ d←+`o-c

Just like lesson 1.

The depths are [ 1 2 2 2 1 1 1 2 2 2 2 1 1 1 1 1 1 1 0 0 0 0 0 ].

Now we can sort our expression using (⍋d)⊏x

which gives [ )÷2×2()+√)-4×2×1(-3(3×3 ].

This expression looks fairly confusing at first, since the parens aren't paired any more. Since the depth increases and decreases at/before each paren, the opening paren is considered to be inside the pair but the closing paren is outside.

So the closing paren gets left behind when we do this sorting. That's actually good, because we now have a record of where the expression belongs.

On the other hand, the open paren always ends up at the beginning of the expression in parens when sorting. It serves as a marker of the beginning of a subexpression.

To see what's happening better, we can split the expression based on open parens with '('(+`∘=⊔⊢)(⍋d)⊏x.

[ [ )÷2×2 ] [ ()+√)-4×2×1 ] [ (-3 ] [ (3×3 ] ]

To find the containing closing parenthesis, I want to find which expression each character belongs to. In the format above, this is easy because expressions are contiguous. I just need to find the number of open parens before the character.

This is just the prefix sum +`(⍋d)⊏o.

I'll set g←⍋d.

We can visualize with (g⊏x)≍(+`g⊏o):

┌
  ) ÷ 2 × 2 ( ) + √ ) - 4 × 2 × 1 ( - 3 ( 3 × 3
  0 0 0 0 0 1 1 1 1 1 1 1 1 1 1 1 2 2 2 3 3 3 3
                                                ┘

Now to go back to the original expression, we have to undo our depth sorting. We could use ⍋g to select from the depth, but in BQN we have a nice tool called structural Under for this.

+`⌾(g⊸⊏)o

[ 1 2 2 2 1 1 1 3 3 3 3 1 1 1 1 1 1 1 0 0 0 0 0 ]

g⊸⊏ is the function that permutes by g, and +`⌾(g⊸⊏) does a prefix sum under this permutation.

Now to put it next to the original code, use x≍+`⌾(g⊸⊏)o:

┌
  ( ( - 3 ) + √ ( 3 × 3 ) - 4 × 2 × 1 ) ÷ 2 × 2
  1 2 2 2 1 1 1 3 3 3 3 1 1 1 1 1 1 1 0 0 0 0 0
                                                ┘

We have identified which set of parentheses each character belongs to, by index. Does that idea make sense?

dzaima

2:54 PM

@Marshall yep

Marshall

This idea of ordering by depth is pretty important, as you can use it to deal with any sort of paired delimiters. On functions it separates all the bodies so you only have to deal with one function at a time, and similarly for parens it removes all the nesting in a sense.

The code so far is pretty short. After setting up d, we have:

g←⍋d
ii←+`⌾(g⊸⊏)o

ii stands for "interior index", or which interior contains a character. But I said I wanted the closing parenthesis index for each character, not this expression index thing.

Fortunately, the ordering of the interiors matches the ordering of open or closed parentheses by depth (in lesson 1 we discussed why these two sets end up with the same ordering).

/c are the indices of closed parentheses, and we can order them by depth with (⍋c/d)⊏/c.

[ 18 4 11 ]

Meaning the last closed parenthesis goes first since it contains the other two, but those two have the same depth.

There are three closed parens but four interiors (0 to 3). This is because the top level has no parens.

Its closing index is l, so the vector we want is l∾(⍋c/d)⊏/c.

And now we can select the appropriate closing parens with ii⊏l∾(⍋c/d)⊏/c.

x≍ii⊏l∾(⍋c/d)⊏/c

┌
  (  ( - 3 )  +  √  (  3  ×  3  )  -  4  ×  2  ×  1  )  ÷  2  ×  2
  18 4 4 4 18 18 18 11 11 11 11 18 18 18 18 18 18 18 23 23 23 23 23
                                                                    ┘

I'll define fe←ii⊏l∾(⍋c/d)⊏/c, for "function endpoint".

Questions about that part?

Note that for this task we only care about the values of fe at functions. But the concept of "where is my closing parenthesis" should make sense for any character.

After this, the "target index" is the enclosing parenthesis for functions, but the current index for everything else. We can get this target with (f×fe)⌈↕l.

x≍(f×fe)⌈↕l

┌
  (  ( - 3 )  +  √  (  3 ×  3  )  -  4  ×  2  ×  1  )  ÷  2  ×  2
  18 4 4 3 18 18 18 11 8 11 10 18 18 13 18 15 18 17 23 23 20 23 22
                                                                   ┘

Again, we're going to have to correct these indices by moving everything in the way of a function back by 1. With no parentheses, we used +`f, but this will pull back everything to the right of the function, while we want to stop at the closing parenthesis.

So we really want +`f-corr, where corr is a correction that undoes the shifts for the functions each pair of parentheses contains, at the closing parenthesis.

It's equal to the number of functions that pair of parentheses contained. To get it, we should look at all the closing indices f/fe, and increment that closing index for each time it appears.

You could do this with a modified assignment in APL, but the idiomatic BQN way is to use Indices (Where) inverse, /⁼.

/⁼∧f/fe

[ 0 0 0 0 2 0 0 0 0 0 0 2 0 0 0 0 0 0 8 0 0 0 0 3 ]

f/fe

[ 18 4 4 18 18 18 11 11 18 18 18 18 23 23 23 ]

You can see for example that there are two 4s in f/fe, and result index 4 has the value 2.

We have to sort (∧) f/fe because the output of Indices is always sorted, so the input to Indices inverse must be sorted.

Indices inverse doesn't naturally know what length its output should have (it just goes up to the last nonzero value), so we have to tell it by overtaking.

x≍l↑/⁼∧f/fe

┌
  ( ( - 3 ) + √ ( 3 × 3 ) - 4 × 2 × 1 ) ÷ 2 × 2
  0 0 0 0 2 0 0 0 0 0 0 2 0 0 0 0 0 0 8 0 0 0 0
                                                ┘

Now +`f-l↑/⁼∧f/fe are our function shifts.

Adding these to the values we got from the function endpoints, we get the correct target indices:

x≍ti←((f×fe)⌈↕l)-+`f-l↑/⁼∧f/fe

┌
  (  ( - 3 )  +  √  ( 3 × 3 )  -  4 ×  2 ×  1 )  ÷  2  ×  2
  17 2 1 0 16 15 14 6 3 5 4 13 12 7 11 8 10 9 22 21 18 20 19
                                                             ┘

matt

3:18 PM

what is happening

Marshall

No repeated values there.

And the final step is to reorder by the grade of those target indices, removing any parens.

(¬∘⊏⟜(o∨c)⊸/ti)⊏x

[ 1-×2×√3+4-33×2×2÷ ]

matt

[confusion]

Marshall

I might need to go over those last steps in more detail in the next lesson. I just wanted to get to a result this time, so we can see the overall flow here.

@matt This is the third installment of APL Seeds, where I explain how to write a compiler in an array programming style (with BQN specifically).

matt

@Marshall an entire fricking compiler?!!

Marshall

The last steps also aren't too important, since they vary with the desired output. The important thing is knowing how to create and use those interior indices.

@matt Not as hard as you might think!

matt

3:23 PM

@Marshall somehow

I doubt that

Marshall

I won't be explaining how to implement the runtime, which is how functions are evaluated and so on. That part is the same as it would be in an interpreter and there's a reasonable amount of existing material on it.

On the other hand, a compiler just transforms source code into a list of instructions, and it turns out you can do this with array operations that act on the entire source.

But the only person who's actually done this so far is Aaron Hsu (Co-dfns). It's hard, but I think if we as a community can figure out and share the tricks, it will be similar to "normal" compiler implementation, where it's a difficult topic but only requires some dedication to accomplish and not divine inspiration.

dzaima

@Marshall shouldn't ti be ⍋ed?

Marshall

@dzaima That's right. Should be (¬∘⊏⟜(o∨c)⊸/⍋ti)⊏x

[ 3-33×421××-√+22×÷ ]

dzaima

@Marshall that seems like a more logical output

Marshall

Which makes a lot more sense because for example the first thing you do is negate 3.

Maybe we'll work on code generation next time so we can see how you would run and test a program. It's easier with dzaima/BQN bytecode, except that this format wouldn't work because you can't call primitives directly.

I guess I'll call this session to a close. If you're working through this and have questions later, just ask here. I might bring them up in the next lesson as well.

matt

3:36 PM

[applause]

[gives everyone an APL]

dzaima

4:01 PM

@Marshall the nice thing is that the order of things never changes (beyond being reversed), you just need to sprinkle the appropriate deriving/calling things inside the expression

Marshall

@dzaima Yeah, and there's no need to distinguish between functions that will be called immediately and those that won't. But it does require starting over to some extent.

dzaima

i wonder if it'd be feasible to transpile the dzaima/BQN bytecode to Javas bytecode

dzaima

4:54 PM

@dzaima hm, that isn't true for e.g. 1‿2‿3

AviFS

8:35 PM

Charger arrived!

Adám

rechargAPL (sorry)

AviFS

Just had to share a piece of my APL-related Flak Overstow: