The APL Orchard - 2020-07-29

« first day (1281 days earlier) ← previous day next day → last day (1356 days later) »

12:05 AM

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

12:52 AM

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

@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.

@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)

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

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

1:09 AM

Pushed the compiler change.

•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 :/

And there was much rejoicing.

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

@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)

1:35 AM

@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

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

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

1:59 AM

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)

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

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

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

1 hour later…

3:12 AM

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

Should be ∨ instead of ∧ for ≠3 dimensions.

5 hours later…

7:47 AM

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

3 hours later…

10:34 AM

@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

@dzaima Gotcha, thanks

(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 ·)

2 hours later…

12:34 PM

@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.

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.

@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.

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

12:54 PM

@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)

1:09 PM

@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

2:04 PM

@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.

@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.

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

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

@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?

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

2:22 PM

@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.

2:32 PM

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

@Adám Something like that. Ouch.

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

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

2:47 PM

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

Or g⍨∘f⍨∘h

1 hour later…

3:52 PM

(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/…

Sounds like a power-mod type problem.

4:08 PM

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

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

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?

@ngn why squaring?

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... ==

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

4:21 PM

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

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

@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)

@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.

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

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

4:26 PM

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% ⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕

@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.

understandable.

@ngn n being the modulus?

@Marshall Sorry, I was too busy.

@user41805 the exponent

4:29 PM

ah i misread your exponentiation sequence

@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.

@Marshall No, I meant O(n).

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

4:52 PM

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

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

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

5:07 PM

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

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

the question was just looking for when it starts repeating

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

Right

5:25 PM

@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

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

thank you for correcting me

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 :) )

5:52 PM

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

I just saw this rosettacode.org/wiki/Multiplicative_order

didn't read it, aside from the key words

thanks

2 hours later…

7:58 PM

huh.

8:27 PM

@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?

@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)

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

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

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

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?

8:40 PM

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

@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

@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←+.

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

Yes •compstart↩¯1 fixes things.

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

8:51 PM

All the primitive definitions compile and pass tests now!

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

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.

9:34 PM

@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)

« first day (1281 days earlier) ← previous day next day → last day (1356 days later) »

Transcript for

Jul '2029

The APL Orchard

apl.chat ― Learn, teach, ask, code, golf, & discuss usage. See ...

apl array-manipulation j tips

join this room
about this room

00:00

06:00

12:00

18:00

all times are UTC

site design / logo © 2024 Stack Exchange Inc; legal

mobile