The APL Orchard

dzaima

00:05

updates; still falling back to VAR_ for non-local vars

dzaima

00:52

i think i have gotten that (still no non-local vars) bug-free - passes my 96 header+assignment tests (most of which are relatively pointless but whatever), t.js, plus bt if LOCM … SETU is made to not error when creating new variables since SETN doesn't seem to be used

Marshall

@dzaima SETN failed whenever I used it on a local, so I assumed locals were pre-declared on function invocation and changed it to SETU. Should be easy to change back.

Now that I think about it there definitely have to be two SETs even with locals so you can check that the first one comes from the definition and not somewhere else.

dzaima

@Marshall right, that would explain why nothing had (until recently) gone wrong with my set impl for Local being wrong (which i have fixed locally)

Marshall

Yeah, just have to change 12¨as back to (11-⊑bG)+a/𝕩.

dzaima

@dzaima pushed fix for that; will push the local usage in a bit, still want to test some things

Marshall

01:09

Pushed the compiler change.

dzaima

•ERASE is broken and i don't believe i can really get around that without introducing checks in places that don't need them. bye •ERASE"a" ⋄ a←… for a REPL-friendly assign :/

Marshall

And there was much rejoicing.

I'm inclined to say ← in the REPL should always work, using a redefine if necessary.

dzaima

@Marshall feels kinda weird, but probably a pretty sane thing to do. chromium/V8 JS does something similar with let

(actually pretty much the same exact thing)

dzaima

01:35

@dzaima pushed; next up is some order of REPL ←, headers implemented with SETH (+ making •COMP able to generate multi-body functions), and full LOC_ usage

Marshall

@dzaima Getting a bunch of "Stack size too large" errors with that one.

dzaima

@Marshall hmm. i had •compilestart←¯1 locally, and while i did test my tests with both values, didn't check yours. :|

dzaima

01:59

fixed; among some assertion errors, CHKV wasn't increasing the max stack size that java wants to know (it pushes up to 3 things to throw the error)

Marshall

@dzaima Nice. time ./dzref_full test/testref.bqn is back down to around 3.7s.

dzaima

heh, your compiler passes 26/80 of my ..header tests. :p

Marshall

@dzaima Pretty good considering it literally doesn't know about the character :.

Marshall

03:12

@dzaima ×⌽2>1⊑⟜∧¨↕ is 10 characters.

Should be ∨ instead of ∧ for ≠3 dimensions.

ab5tract

07:47

Is the dzaima BQN bytecode a first pass at defining a bytecode for the BQN spec? Or is it a dzaima/BQN specific thing?

dzaima

10:34

@Marshall that's an interesting solution

@ab5tract i made it specifically for dzaima/BQN, but i don't see there being many other options with what a bytecode could go with

ab5tract

@dzaima Gotcha, thanks

dzaima

(i am planning about removing (or at least never use myself) CHKV/FN1O/FN2O/TR3O and making it the compiler's job to take care of optional 𝕨 and ·)

Marshall

12:34

@ab5tract Agree with dzaima. You could also remove VARO and VARM if you don't want to support dynamic features like execute or creating names in a debugger.

And for optimization you could add some instructions to immediately call a primitive function/1-modifier/2-modifier instead of pushing it onto the stack first.

ab5tract

That was my next question: is it actually a necessary component of a BQN implementation? You will have to forgive my current ignorance on the matter but it was my impression that there were only two requirements: a BQN interpreter and a compiler written in BQN.

Marshall

@ab5tract No, you could interpret BQN directly or compile/transpile to something other than bytecode (machine code, C, TAIL, etc.). I would say bytecode is nice because it separates program structure from primitive execution very cleanly.

ab5tract

Ok awesome. I always considered language implementation to be best left to the CS grads so I never really gave it much thought. Enjoying following along and hoping to jump into it a bit on my own at some point

dzaima

12:54

@ab5tract note that some intermediate representation/preprocessing is kind of required with the new scoping rules - b←1 ⋄ {F←{b} ⋄ •←F 0}0 and b←1 ⋄ {F←{b} ⋄ •←F 0 ⋄ b←0}0 act differently (assuming no value blocks for simpler code), and regardless it's a nice way to deal with the syntactical/actual type difference (e.g. you don't want <⊑⟨+⟩ to be an atop, but instead < called on the + function)

(with value blocks, would b←1 ⋄ {v←{b} ⋄ b←5} still be an error? the b in v could safely reference the outer b)

dzaima

13:09

@Marshall VAR_ isn't really even necessary for ⍎/debugging/REPL, but i'm keeping it around as it may be useful at some point and it doesn't cost that much as i don't maintain the hashmap until its needed

Marshall

14:04

@dzaima Yes, it would be an error. I think having a special rule for immediate blocks is too complicated, but the strategy Co-dfns uses is to initialize a variable that shadows another one to that variable's value. But mainly I think shadowing is usually bad and you should try to avoid it, so I'm not too worried about these issues.

Regarding missing axes in Reshape, should BQN use primitives to encode the policy? So ∘‿2⥊a would require exact divisibility, ⌊‿2⥊a would truncate a, ⌽‿2⥊a would extend by wrapping, and ↑‿2⥊a would extend with fills. Seems cleaner than characters and less mathematically dangerous than negative numbers.

Adám

@Marshall I've long toyed with the idea that negative numbers should fill that dimension in reverse. I suppose you could use - atop a functions to indicate the reversal of what that function would otherwise indicate.

Marshall

@Adám There's this great symbol called ⌽ that you can use to reverse things.

Adám

@Marshall Dyadic ⌽ has one element of the left argument for each axis, right? How do I reverse the axes listed in a variable?

Marshall

@Adám You do have to use multiple reverses for that in general, but ⌽⌾⥊ reverses all axes and ⌽⌾(∾˝) reverses the first two. How often do you want to reverse an arbitrary set of axes?

Adám

Dunno. Could Rank take a nested right-operand to apply the function multiple times?

Marshall

14:22

@Adám {⌽⎉(-𝕨)𝕩}´⟜/˜ reverses the right argument along each set bit in a boolean left argument. That's not too bad for what I think is a very rare case, so I don't see the need to make Rank more complicated for it.

Adám

14:32

@Marshall ⊃({⊖⍤(-⍺)⊢⍵}/,∘⊂⍨∘⍸⍨) right?

Marshall

@Adám Something like that. Ouch.

Adám

1. Only really two differences:
1. Non-enclosing reduction with initial value
2. No stranding

Marshall

And ,∘⊂⍨∘⍸⍨ could be /⊸∾⟜< with a reverse compose.

Adám

14:47

Now that I'm aware of reverse (and thus split) compose, I tend to see g∘h⍨∘f⍨ a lot…

Or g⍨∘f⍨∘h

user41805

15:52

(question arising from phase 2 problem 4.2, but not at all useful for solving it) how do you find the repeat size for cyclically (×A) mod X? for (×2) mod 1e6, its 12500 apparently, but idk how to find it without brute-force

tio.run/##SyzI0U2pTMzJT/…

Adám

Sounds like a power-mod type problem.

H.PWiz

16:08

there's this en.wikipedia.org/wiki/Multiplicative_order

I don't think there's much of an efficient way to do it

actually, maybe there is

ngn

@user41805 @H.PWiz repeated squaring should be more efficient, but there's no point for n≤1000

xpqz

If I (repeatedly) need to insert items into a vector which implements a circular buffer - would it be more efficient to divide it up with ↑ and ↓ and catenate bits back together, or rotate the vector such that the insertion can always be a catenate at the end?

user41805

@ngn why squaring?

ngn

Exponentiation by squaring

In mathematics and computer programming, exponentiating by squaring is a general method for fast computation of large positive integer powers of a number, or more generally of an element of a semigroup, like a polynomial or a square matrix. Some variants are commonly referred to as square-and-multiply algorithms or binary exponentiation. These can be of quite general use, for example in modular arithmetic or powering of matrices. For semigroups for which additive notation is commonly used, like elliptic curves used in cryptography, this method is also referred to as double-and-add. == Basic... ==

xpqz

@ngn I saw a Roger Hui implementation of this somewhere.

Adám

16:21

@xpqz Did you try both and compare with ]runtime -c?

user41805

@ngn but i'm only multiplying by 2 each time?

ngn

@user41805 basically, if you compute 2^1, 2^2, 2^4, 2^8.. mod 1e6 and keep only those that correspond to the 1-bits in the binary representation of n, and multiply them together, it takes O(log(n)) operations instead of the bruteforce O(n)

xpqz

@Adám I've not implemented either yet; trying to think before leaping :) But from other languages, vectors have shocking (O(n)) insert and delete - but for APL I have no idea - perhaps rotate is super-efficient under the hood? ↑ , ↓ will at least need to move data and alloc new vector space.

Adám

@xpqz In-place rotate should be O(1).

cannadayr

hello again yall. been busy. wondering if there was a seeds lesson 4?

i havent had time to interact w/ them live but I still was going to go thru and review and take notes / whatnot
https://aplwiki.com/wiki/APL_Seeds

Adám

16:26

Number 4 seems to have been skipped.

@xpqz Hm:

      InsTD←{(⍺⍺↑⍵),⍺,⍺⍺↓⍵}
      InsRot←{(-⍺⍺+≢⍺)⌽⍺,⍨⍺⍺⌽⍵}
      n←⎕C⎕A
      t←1000⍴⎕A
      ]runtime -c n(273InsRot)t n(273InsTD)t

  n(273InsRot)t → 9.7E¯7 |  0% ⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕
  n(273InsTD)t  → 9.8E¯7 | +1% ⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕

Marshall

@cannadayr I started it, but nobody was there to answer questions so I didn't continue. I'll eventually start writing implementation notes in the style of BQN documentation, which I think will work better overall.

cannadayr

understandable.

user41805

@ngn n being the modulus?

Adám

@Marshall Sorry, I was too busy.

ngn

@user41805 the exponent

user41805

16:29

ah i misread your exponentiation sequence

Marshall

@Adám Did you really mean to say that? O(1) rotate isn't possible even in principle if you actually manifest the argument and result arrays.

Adám

@Marshall No, I meant O(n).

cannadayr

also, since I dont think gordon frequents this chat room, I thought id let ppl know that hes made a _ton_ of progress on his erlang/apl implementation. He might have some time commitments that come up soon so work might slow down, but I think hes meaning to keep it active and ive been reading the codebase and learning erlang to try and contribute:
https://github.com/gordonguthrie/pometo

i suspect most of my contributions will come after he fleshes out the core parts of the parser/runtime just implementing apl primitives

but it already does stuff like this so thats nice

3 3 3 ⍴ ⍳27

1 2 3
4 5 6
7 8 9

10 11 12
13 14 15
16 17 18

19 20 21
22 23 24
25 26 27

user41805

16:52

@H.PWiz for (×2) mod 1e6, the number 12500=(5-1)×5*5=(5*6)-(5*5) so something with the totient function maybe

ngn

@user41805 why bother? the problem says n≤1000. bruteforce is almost instant.

user41805

@ngn i did not mean to ask for the competition problem, just the order of the generalised group

H.PWiz

17:07

@user41805 I did have a brief look for algorithms, and there were murmurings of totient, factorisation, and chinese remainder theorem

ngn

@user41805 you question doesn't make sense. 2 is not co-prime with 12500, so it can't have a multiplicative order mod 1e6.

H.PWiz

the question was just looking for when it starts repeating

ngn

2 doesn't repeat. it goes like 2 4 8 16 32 64 128.. and after 12500 steps it lands back at 64.

H.PWiz

Right

user41805

17:25

@ngn 2 doesn't repeat, but it results in a sequence that does repeat

oh do you mean its not a group anymore?

ah right without the 2 it's not a group anymore

ngn

@user41805 there's no (unique) inverse, so it can't be a group with respect to modular multiplication

user41805

thank you for correcting me

ngn

the set of units (i.e. elements with a multiplicative inverse) in a ring do form a group though

(i just read it in wikipedia :) )

user41805

17:52

@H.PWiz do you have a link to that or is it from a book?

H.PWiz

I just saw this rosettacode.org/wiki/Multiplicative_order

didn't read it, aside from the key words

user41805

thanks

dzaima

19:58

huh.

Marshall

20:27

@dzaima Working on compiling the BQN primitive implementations and I get ImplementationError: java.lang.ClassFormatError: Invalid method Code length 65652 in class file BQN/gen36. The bytecode's only 11684 bytes though. Is there some system limit I need to be watching for?

dzaima

@Marshall the generated java bytecode being 6x larger makes sense. the bytecode length is a 32-bit int though, not sure why this seems related to 16

(as with all similar problems, •compstart←¯1 should be a good temporary fix)

Marshall

@dzaima Doesn't fix the error if I set it from BQN. Should I set it as an environment variable or something?

dzaima

@Marshall weird. It should function if executed anywhere before any •COMPs are executed

Marshall

I can push the code I'm using to get the error if it'll help.

dzaima

ah.. (i do plan to generate a separate method per section between RETNs, but haven't done that yet)

@dzaima there's just no way that any gen_s should be generated with •compstart←¯1 beyond what's already been done.. maybe try executing the file with java -jar …BQN.jar -e •compstart←¯1 -f file.bqn?

Marshall

20:40

Since lines from testref.bqn are pushing me over, I can work around it for now by dropping initial tests.

dzaima

@dzaima right, compiling being done before •compstart←¯1 can execute is probably the cause then. the separate -e flag should work then, assuming it works

Marshall

@dzaima Doesn't do anything. It also doesn't error if I assign •compstart to be 'a', but it does if there's a syntax error like •compstart←+.

dzaima

oohhhhh right, it makes •compstart a local variable and bypasses the name comparisons. ಠ_ಠ

•COMP ⟨⟨0,0,2,0,11⟩,⟨¯1⟩,⟨"•compstart"⟩,⟨'f'‿1‿0‿⟨⟩⟩⟩ then? :p

Marshall

Yes •compstart↩¯1 fixes things.

dzaima

@Marshall oor that. ¯\_(ツ)_/¯

Marshall

20:51

All the primitive definitions compile and pass tests now!

dzaima

it'll be some while until i get to splitting up the code, so that (or whatever other mitigation) will have to do for now

Marshall

Had to expand ˘ ← ⎉¯1 because I don't handle partial application, and I still can't run the two tests with functions.

Pretty minor issues. I think I'll try to build a Javascript VM and get this thing online now.

dzaima

21:34

@Adám is there any way to disable the debugger popping up in RIDE on every error? (as in, do the equivalent of spamming the esc button)

Transcript for