Lesson S1 - parenthesis nesting level – Conversation in The APL Orchard

Marshall

Jun 10, 2020 14:30

Welcome everyone to the first APL Seeds session!

Avi F. S.

I would've simply done the parenthesis with a stack; curious what other way we'll learn!

Whoops, it's already started!

cannadayr

will APL seeds held in the chat room or over video?

Avi F. S.

@cannadayr Chat room! Like Cultivation

Jeff Zeitlin

@cannadayr - Right here, right now! :)

Marshall

The idea of this series is that we'll learn how to grow your own APL (or not-APL). At the beginning I think it will be something like a study group for Aaron Hsu's new array-based compiler ideas.

RGS

Jun 10, 2020 14:32

@Marshall reference(s)?

Marshall

So to get us started I will explain some of the first steps I took on my BQN compiler (which is nowhere near a full compiler). We'll be trying to parse a simple APL sentence, essentially.

@RGS aplwiki.com/wiki/Aaron_Hsu

Jeff Zeitlin

Will the concepts also be appropriate for an interpreter?

RGS

@Marshall (thanks)

Marshall

@JeffZeitlin They wouldn't apply to a very pure interpreter like is typically used for APL, but there's a continuum from interpreters to compilers and this is one of the first things you'd do to be more compiler-like.

We will probably look at interpreter techniques in other APL Seeds sessions.

Jeff Zeitlin

/me nods

Marshall

Jun 10, 2020 14:36

So here you can see the cases my compiler currently handles. No operators, and only values (not functions) can be assigned.

However, that simple syntax is actually very close to the compiler's parsing code, which has no control flow or function assignments.

Avi F. S.

@Marshall Not entirely clear on what/how those cases are demonstrating

I don't really see the pattern...

Marshall

@AviF.S. That's the kind of code the compiler can currently compile.

Avi F. S.

@Marshall I got that, I just thought maybe there was more to what it was demonstrating than simple functions + inline assignment

Marshall

I don't think we'll get all the way though today, but we'll focus on a smaller subset without assignments or statement separators.

RGS

@Marshall is the compiler itself written in bqn..?

Wezl

Jun 10, 2020 14:39

@RGS looks like it.

Marshall

@RGS Yes, and currently executed with BQN2NGN. Speaking of which, we'll be using BQN in this lesson.

Avi F. S.

@Marshall ⍤ ⍥ ⍤

Adám

Oooh.

RGS

Maybe that is a discussion for another time but it is completely beyond me what it means to write a compiler for a language in its own language... especially when the language is still being developed...

Marshall

You can use BQN2NGN here, and dzaima's paste has nice syntax highlighting for it.

Wezl

Jun 10, 2020 14:40

@Marshall Too bad I didn't study it well, but that can help me learn it.

Avi F. S.

@Marshall Have you make a keyboard for it yet?

Marshall

Yes, I'm definitely not assuming people know BQN already.

Adám

@AviF.S. BQN2NGN has a language bar, backtick keybindings, and some tab-combinations.

Marshall

@AviF.S. The interface I just linked to has a backtick keyboard. Unfortunately that makes it impossible to type a backtick, which we will be using, so you have to copy-paste that character.

Avi F. S.

@Adám Oh neat! I knew the language bar; forgot the ~~backpacks~~ backticks, haha!

Marshall

Jun 10, 2020 14:41

(the correct interface it turns out is a backSLASH keyboard.)

So to get us started we're going to look at the classic parenthesis nesting level calculation.

dzaima

@AviF.S. surround with triple-dashes

Avi F. S.

@dzaima Thanks!!

dzaima

(after i finish the font (double-struck parens are ugly) i do plan on making a linux xkb layout for BQN)

Wezl

@dzaima Yes, please

Avi F. S.

@Marshall Wait! I swear it didn't give you the backtick secrets when you hovered over the language bar yesterday, did it?!

Marshall

Jun 10, 2020 14:44

The BQN translation is +`-´"()"=⌜x, which I hope has a fairly obvious correspondence to the APL.

Adám

Uh, oh, backticks in markdown are bad.

Marshall

(It's backslash to escape if anyone's wondering)

dzaima

@Adám they're fine if enclosed in multi-backticks, but those need to not be surrounded with spaces

Adám

Ah yes, +\-/'()'∘.=x

Marshall

The only difference in the primitives other than some stuff being superscripted is that BQN turns Outer Product into a conventional operator ⌜.

Avi F. S.

Jun 10, 2020 14:46

@Marshall @languagebarpeople I've been wondering also if there's a shortcut to execute!

dzaima

@Marshall ..somehow i didn't realize the ticks were superscripted slashes :P

Marshall

The test string I used for this is a quadratic formula x←"((-3)+√(3×3)-4×2×1)÷2×2". You can use your own if you'd like, of course.

dzaima

@AviF.S. ctrl+enter?

Marshall

I'll make sure everyone has that running before proceeding.

Avi F. S.

@dzaima .... Never occurred to me :( Thanks!

Marshall

Jun 10, 2020 14:48

The other note is that BQN differentiates between characters, which are not arrays, and strings, which are rank-1 arrays. Strings use double quotes and characters use single ones, like in C.

cannadayr

method b in gnu apl:
+\(1 ¯1 0)['()'⍳'plus(square(a),plus(square(b),times(2,plus(a,b)))']

Marshall

Okay, are people able to get that BQN code working?

cannadayr

(im following along w/ gnu apl as its my comfort zone but yes)

Marshall

I guess I should also say a little about how it works.

@cannadayr Translating to another language is probably also a good way to internalize it better.

Avi F. S.

@Marshall Noticed that! Curious as the pros/cons of having 'scalar strings'

Richard Park

Jun 10, 2020 14:50

so how do I pronounce "x" and how do I pronounce "𝕩"?

Marshall

@RichardPark Well, one's double struck.

So do that with your tongue.

Richard Park

@Marshall okay but if I want to dictate to someone writing it down

oh okay

Marshall

In other words, I have no idea.

Richard Park

a bit like spanish rolling r's

so it's "eks" and "ek(rolled)s"

Avi F. S.

Love it!

dzaima

Jun 10, 2020 14:53

@Marshall 𝕨 - double-double-u? quadruple-u? :p

Marshall

Anyway, the idea for the nesting code is that the nesting level is the number of open parentheses before a character minus the number of closed ones. If those numbers are equal then every parenthetical has been closed and we're back at the bottom level.

ab5tract

A lot of people have trouble with the rolling tongue trick though.

Marshall

If there are more closed parentheses then you should get a syntax error (but I haven't yet added validation).

Adám

@Marshall Doesn't that become problematic with multiple types of parentheses? ({)}

Avi F. S.

@RichardPark Maybe x-bar? Like the x̄ in physics.

Wezl

Jun 10, 2020 14:54

@ab5tract how do you even roll a k?

Richard Park

@Adám Is this really the pont of this example?

Marshall

@Adám Yes, validating on nesting level only fails to detect that case.

cannadayr

(i think were getting off track)

Adám

@Wezl ʞ

RGS

(is it me or is the language bar missing ` ?)

Marshall

Jun 10, 2020 14:55

But we can also compute the way parentheses are paired, which will allow us to catch it.

ngn

e(click)s, like in xhosa :)

Marshall

@RGS It is. I thought Prefixes was a good replacement for Scan, but changed my mind.

Richard Park

@Marshall what do you mean "compute the way they are paired", like matching them?

cannadayr

this is definitely reminding me of Aaron Hsu's thesis. I went thru it a couple months ago and pulled out the tree manipulation equations and translated it to gnu apl. Am keeping notes in a repo that will likely include the relevant ones.

Marshall

@RichardPark Yes, figure out which closed parenthesis closes which open one.

Richard Park

Jun 10, 2020 14:58

@Marshall cool

Adám

(fwiw, I think I'll call 𝕩 and 𝕨 arg and param)

Marshall

To pair parentheses, the thing we need to notice is that at a particular nesting level, open and closed parentheses must alternate, so that the open-close pairs are all right next to each other.

Richard Park

@Adám Sorry for the tangent - my last thought on the matter is that any serious version of this should be hand-writable and speakable (dictatable) and that "arg"→"𝕩" and "param"→"𝕨" is intolerable

Avi F. S.

@Adám +\-⌿'()'∘.='x

Adám

@AviF.S. Actually, +⍀-⌿'()'∘.=x to be literal, but I wanted to show /→´

Marshall

Jun 10, 2020 15:00

You don't have to, but at this point I decided to separate the open and closed parens into two variables o←'('=x⋄c←')'=x.

Avi F. S.

@Adám I think I'll stick with alpha & omega :)

Marshall

The nesting levels are +`o-c.

And we'll also want the indices of opening and closing parentheses b←/o and e←/c.

/ is ⍸ in Dyalog APL.

Richard Park

@Marshall but is it "/" in BQN?

Marshall

Or {⍵/⍳⍴⍵} elsewhere, at least in the vector case.

Richard Park

oh wait nvm i typed wrong

Avi F. S.

Jun 10, 2020 15:04

@Adám Good point! But I couldn't find ⍀ and both worked in the example because the first=last axis at that point

Marshall

Let's set d←+`o-c.

Avi F. S.

@Marshall May we have Dyalog translations for everything at the beginning, please?

Adám

@AviF.S. APL+Period

Avi F. S.

@Adám Thanks!

Marshall

@AviF.S. Beginning of what?

Adám

Jun 10, 2020 15:05

@Marshall This learning BQN.

Avi F. S.

@Marshall What @Adám said! Not piece-by-piece. Just every line of BQN cf. a line of Dyalog

Marshall

I think what we've got so far is

x←'((-3)+√(3×3)-4×2×1)÷2×2'

o←'('=x⋄c←')'=x⋄d←+⍀o-c⋄b←⍸o⋄e←⍸c

RGS

(can someone tell me what we are aiming for, here?)

Marshall

We are going to figure out which closed parentheses correspond to which open ones.

This lets you figure out the opening parenthesis each character "belongs" to, eventually.

Wezl

@AviF.S. shorturl.at/vPU17

RGS

Jun 10, 2020 15:12

that is in the really short term; I mean "how does this equate to writing an APL or your BQN compiler or ...?"

I'm not saying this exercise isn't needed but my lack of global scope prevents me from understanding its usefulness

Richard Park

@RGS I think we're looking at a simple parsing problem

@RGS So one of the steps towards writing an interpreter/compiler?

Adám

@Wezl You can post long urls by adding a newline (shift+enter) after the url (but don't use markdown then).

Marshall

@RGS The thing my compiler does with it now is to move each function next to its enclosing parenthesis.

Which transforms APL notation to reverse polish (RPN).

Wezl

@Adám I thought i remembered that, but I used [ctrl-enter]

Marshall

That is the format WebAssembly uses, so with that you already have a very simple compiler.

Richard Park

Jun 10, 2020 15:14

so right now are we trying to correctly pair numbers from (/o)‿(/c)?

(⍸o)(⍸c)

Avi F. S.

@Wezl Thanks! I was moments away from sharing: shorturl.at/nsIWY

Marshall

Yes, that's right. Or b‿e as I've defined it.

RGS

@Marshall ah ok; I'll bear with you then

Richard Park

@Marshall end result should be ⟨⟨0,18⟩,⟨1,4⟩,⟨7,11⟩⟩?

Marshall

@RichardPark Yes.

As I said, at a particular depth the parentheses all go open, corresponding closed, open, corresponding closed, etc.

Avi F. S.

Jun 10, 2020 15:17

@Adám Ah thanks!

@Adám Although, then if people forget to click Read more, they figure you simply sent them the wrong link

RGS

@Marshall that does make a lot of sense

dzaima

@AviF.S. i think i'll add an error message about cut links at some point :)

Marshall

Based on the way we computed the nesting depth, our opening parens are one higher than the closing ones. We could adjust it, but it turns out not to matter.

Avi F. S.

@dzaima That'd be neat! Or clicking Save could instead be Copy which would copy to clipboard an already shorturl-ified link!

Marshall

If you look at the depth-2 opening parens (2=b⊏d)/b you get [ 1 7 ], and for the depth-1 closing parens (1=e⊏d)/e you have [ 4 11 ]. They match up.

Adám

Jun 10, 2020 15:20

@AviF.S. That'd require a server state.

dzaima

@AviF.S. it already copies the link (there's also a shortcut - alt+s for the button, alt+e returning to the editor, among other things. i should add tooltips)

Marshall

(2=d[b])/d and the same for e in APL.

Avi F. S.

@Adám Ah, I don't know much about these things! Just an idea, but I of course leave it to the implementor to decide what's easiest, or otherwise preferable

ab5tract

@Marshall when did d/e get defined?

dzaima

@AviF.S. ah, my intention with it is to definitely not shorturlify, so that even if the internet died, chat logs are enough to get all the contents

Richard Park

Jun 10, 2020 15:22

@ab5tract e←/c ⋄ b←/o

Marshall

@ab5tract d is the depth here.

ab5tract

ahhh

Avi F. S.

@dzaima Very good point! Plus, always gotta be prepared for the post-apocalyptic world :)

Adám

@Marshall (If you enter just a message url, it'll get quoted nicely inline)

Marshall

Since in a valid parenthesized statement there are the same number of each type (open or closed) at every depth, we can pair all parentheses at once by sorting by their depth.

If we have multiple kinds of brackets, we could then confirm that the [{]} think Adam mentioned doesn't happen by comparing the types of corresponding parens.

Adám

Jun 10, 2020 15:25

Oh, and you have to mask away strings first too.

Avi F. S.

@Adám Like this? :54620619 How?

Marshall

I can sort both sets of parens at once using {(⍋𝕩⊏d)⊏𝕩}¨b‿e.

Adám

@AviF.S. No, a full url, not an id, and no other content in the message.

Marshall

@Adám Yes, unless you're doing a tiny little subset.

Avi F. S.

@Adám Understood, thanks!

Marshall

Jun 10, 2020 15:27

BQN has pretty nice facilities for working with cells, so we could also compute the correspondence with flat arrays using {(⍋𝕩⊏d)⊏𝕩}˘b≍e.

Richard Park

@Marshall now in APL I feel like ↓⍉↑ would do the job?

Marshall

Where ≍ is Laminate and ˘ is Rank -1 ("cells").

Richard Park

@Marshall ooooh

Marshall

@RichardPark That would get the format you showed ⟨⟨0,18⟩,⟨1,4⟩,⟨7,11⟩⟩. But that format doesn't actually fit with the array compiler style, so I wouldn't use it.

Right now, my compiler uses the permutation that transforms open paren locations to match closed paren locations.

Richard Park

@Marshall I see, to be fair although the parens matching for parsing in this context I get, I am generally lost on the details since I'm not an implementer

Marshall

Jun 10, 2020 15:32

You can get those pairs in BQN with >∾¨¨´{(⍋𝕩⊏d)⊏𝕩}¨b‿e. The two Eaches are ugly which comes down to the issues with Reduce we were discussing.

cannadayr

im a little confused (and still unfamiliar with BQN).
what format are we attempting to convert `b` and `e` into?

ab5tract

@Marshall yeah my eyes bugged out a bit at the double eaches in earlier examples

Adám

@Marshall OK, this one need an APL translation.

Marshall

@RichardPark I do hope to show in this series that one way to "be an implementer" is just to know the right APL programming techniques. We have to start somewhere so not all the details will be clear, but we'll get to them.

@Adám That was translated to BQN from Richard's ↓⍉↑.

Richard Park

@Marshall Mine will be A Schmogramming Schmanguage and all names are to begin with Schm (pronounced "schmuh")

Marshall

Jun 10, 2020 15:35

So ↓⍉↑{⍵[d[⍋⍵]]}¨b e I think.

ab5tract

@RichardPark is that intentionally used to get ASS as an acronym? :)

Richard Park

@Marshall Yeah one thing I need to understand is BQN's array model, since I'm so used to fiddling with APL's nest-vs-rank mix-and-take stuff

@ab5tract I didn't think of that but it's an added bonus!

@Marshall But similarly I'm much happier with b≍e rather than ↑b e

Marshall

Time's up so I'll stop now, but a good exercise is to do the validation I talked about (say, with APL's ()[]{}). You need to check that the total number of open/closed brackets match, that each open bracket corresponds to a closed one of the same type, and that open brackets come before the corresponding closed ones.

RGS

@Marshall what does it mean to write a language's compiler in the language itself?

Adám

@RichardPark ,[0.5]

RGS

Jun 10, 2020 15:39

@Marshall thank you for your time :)

Wezl

Self-hosting (compilers)

Self-hosting is the use of a computer program as part of the toolchain or operating system that produces new versions of that same program—for example, a compiler that can compile its own source code. Self-hosting software is commonplace on personal computers and larger systems. Other programs that are typically self-hosting include kernels, assemblers, command-line interpreters and revision control software. If a system is so new that no software has been written for it, then software is developed on another self-hosting system, often using a cross compiler, and placed on a storage device that...

Adám

@Marshall Thank you, Marshall!

ab5tract

Indeed, thanks for the session.

Avi F. S.

@RGS He said he wasn't sure. Someone else asked him whether he'd do it!

Adám

See you all in 2 weeks?

cannadayr

Jun 10, 2020 15:40

sorry, quick wrap up questions:
1↓⍉↑{⍵[d[⍋⍵]]}¨b e
2 12
2 12

Jeff Zeitlin

/me intends to be here. More or less. :(

cannadayr

with ⎕IO ← 1

Marshall

@RGS Well, a compiler transforms source code written in some language (right now, a subset of BQN) to code in another language (WebAssembly). This is purely manipulation of data, so you can do it in any language.

cannadayr

doesnt seem correct

Marshall

@cannadayr Seems to have a leading 1?

Wezl

Jun 10, 2020 15:41

@Adám Isn't Cultivation next week?

Richard Park

@Adám also ugly, and I thought we weren't that into []?

Avi F. S.

@Wezl Yes!

cannadayr

@Marshall ah thx i was translating between dyalog and gnu apl

Adám

@Wezl APL Cultivation is, but next APL Seeds is in 2 week.

RGS

@Marshall ok... but this feels like a chicken and egg problem; if you are writing a compiler for BQN in BQN, how will you run that compiler for the first time to compile itself..?

I know you have been using BQN2NGN but how does that piece fit into this puzzle?

Richard Park

Jun 10, 2020 15:42

@ab5tract The actual origin: youtube.com/watch?v=gSDwK_5L5LM&t=1m50s

Adám

@RGS The first iteration is written in another language, say JavaScript.

cannadayr

@Marshall so we're looking for
┌───┬────┬────┐
│1 5│2 12│2 12│
└───┴────┴────┘

Marshall

@RGS Not with your own compiler, of course. This is called "bootstrapping": you need some other implementation of the language to start with. Which I happen to have.

RGS

@Marshall it being bqn2ngn?

Adám

@cannadayr Remember that Dyalog's monadic ↑ is ⊃ in GNU.

Wezl

Jun 10, 2020 15:42

Bootstrapping (compilers)

In computer science, bootstrapping is the technique for producing a self-compiling compiler — that is, compiler (or assembler) written in the source programming language that it intends to compile. An initial core version of the compiler (the bootstrap compiler) is generated in a different language (which could be assembly language); successive expanded versions of the compiler are developed using this minimal subset of the language. The problem of compiling a self-compiling compiler has been called the chicken-or-egg problem in compiler design, and bootstrapping is a solution to this problem.Many...

Marshall

@RGS Yes.

Jeff Zeitlin

@RGS - Like @Adám said, your first, minimalist version is written in another language -- or in a subset of your language that happens to have the same meaning in another language.

cannadayr

@Adám doing this on tryapl first and ill translate to gnu apl after

RGS

ok, I think I understand know. thanks Wezl, Adam and Marshall.

Avi F. S.

@cannadayr Why TryApl/GNU APL? Were you unable to download Dyalog?

ab5tract

Jun 10, 2020 15:44

@RichardPark lol!

cannadayr

because gnu apl is what im most comfortable with - but lots more personal historical reasons

oh i can dl it i just am not a huge fan of the cli interface, not rly important rn

Wezl

@all was the meet recorded yesterday?

Adám

@Wezl Yes.

cannadayr

hmm still seems wrong

Avi F. S.

@cannadayr Fair enough!

Wezl

Jun 10, 2020 15:48

@Adám Where can I find it?

cannadayr

im still not clear on going from...

Adám

@Wezl It is currently only in my DropBox. I need to find a way to deliver it.

cannadayr

b ← 1 2 8
e ← 5 12 19
d ←1 2 2 2 1 1 1 2 2 2 2 1 1 1 1 1 1 1 0 0 0 0 0

→
(1,19),(2,5),(8,12) ⍝ (i think)

Adám

@RichardPark The actual origin is from Yiddish.

Wezl

@Adám Yiddish gives us a lot of great words! I'm trying to learn it as a hobby.

@wezl Like words with schm and Γ in bagel

Richard Park

Jun 10, 2020 15:53

@Adám Of course it is, and of course there's a wiki page for that

Adám

@Wezl I'll be happy to assist over here. (We only speak Yiddish at home.)

Wezl

@Adám Thanks! I've been using Mango Languages

cannadayr

does any1 have an apl solution of going from b & e to parens pairs?

↓⍉↑{⍵[d[⍋⍵]]}¨b e doesnt seem to work

Richard Park

@cannadayr 1 sec

cannadayr

(sry doing 3 things at once and dont want to go too long or itll take 10x as long hah)

Adám

Jun 10, 2020 16:01

@cannadayr Because you get (1 5) (2 12) (2 12)?

cannadayr

correct

Richard Park

@cannadayr BQN was mistranslated

@cannadayr should be ↓⍉↑{⍵[⍋d[⍵]]}¨b e

@cannadayr just a grade in the wrong place

Adám

Ah yes, that fixes it.

cannadayr

@RichardPark that seems to do it thx

Lesson S1 - parenthesis nesting level

The APL Orchard

Participants