the k tree

ngn

00:17

@xpqz it's just a natural consequence of treating dicts and lists the same way. lists have domain !#x. dicts have an explicit domain. see: nsl.com/papers/m.txt for more ideas along those lines

@rak1507 i'm not sure i understand the question, so i'll give the obvious answer: function primitiveVerb(arg){if(arg is of type blablah){return doSomething;} return doSomethingElse;}

(everything brutally abbreviated, of course)

rak1507

right, yeah, just need to dig in to the abbreviations more

ngn

@coltim that's more or less what it does now?

@Traws nice. thanks for the timings

@coltim "close stdout"? why would anyone..

..except by accident. but what can i do.

not trying to make a gun that refuses to shoot at feet :)

Bubbler

What's the difference between >'1 and >1?...

ngn

@rak1507 if it's only about func#dict, it's a trivial change and i've already made it, but not pushed it yet..

coltim

@ngn yeh, color me sufficiently surprised by clang =P

rak1507

00:30

@ngn Ah nice :) well it'd be fun to try and do myself anyway

ngn

@Bubbler there's no difference between f'atom and f atom, but there's a difference between >list and >atom

>list is "grade down", >atom is "close file descriptor"

overloads based on atom vs list are common, e.g. =list (group) vs =n (unit matrix)

Bubbler

I mean it's number 1 for both

ngn

@Bubbler sorry, i don't understand

coltim

@ngn I make no excuses. I am a user

Bubbler

Just wondering why coltim mentioned specifically >'1 and not >1 if they both mean the same thing

coltim

00:37

@Bubbler look. some people golf and they're brilliant and they know exactly what to do. I don't. I mash the keyboard and I make typos and I meant to do >':x but I dropped the : and then my k exited

Bubbler

Oof :P

ngn

:D

coltim

it's how I find all the segfaults. why write fuzzing tests when you have industrious fools like me!

ngn

such overloads seem to be the most hated feature of k

i already got used to the idea that atoms and lists are fundamentally different things, so i don't mind this, but it seems most people do, especially those coming from an apl/j background. (that's just an observation, i'm still gonna stick to k6 as the best array language out there)

coltim

@ngn there is an entire class of programmers who hate overloads. I'm not sure exactly what the commonalities between them are, but I feel like part of it comes from "C is portable assembly, when I do x+y in C++ and it does something beyond "add register and register" I don't like it because it's not matching my mental model"

Bubbler

00:51

Talking about mental models, I guess I have multiple of them already, one for C, one for Python/JS, one for Haskell, one for APL/J

so it wasn't too hard to add 5th (Rust) and 6th (K) to the list

ngn

apl j k are more like libraries pretending to be languages

even in a minimal array language, there are more primitives than ascii punctuation chars. something has to be sacrificed to make them work. so you either go non-ascii (apl), or multichar (j), or embrace overloads (k)

Bubbler

01:07

That's definitely true

Traws

CMC: given a ragged array, generate all possible tuples picking one element from each sub-array: example

ngn

@Traws did you mean ,6 instead of 6? (asked he, implicitly confirming what he'd just said about atoms vs lists :) )

Traws

no

ngn

01:25

so, the hard part is turning atoms into lists..

@Traws 15 bytes: {+x@'!#'x}(),/:

rak1507

(*1_|,/\,/:\:)/

wait hang on that doesn't work (oh maybe it does actually)

Bubbler

(),/: is clever, I had {(#x)#x}'

rak1507

oh, mine doesn't work for two atoms :(

ngn

@Bubbler (),/: doesn't work for empty arrays though

JohnE

@coltim I don't like user-defined operator overloads ala c++ because it interferes with nonlocal reasoning for code. it's not obvious from a c++ statement that + actually appends an item to a list or re-seeds your mersenne twister or whatever some idiot decided to make it do. in k this is a much less severe problem, because users cannot define their own symbolic verbs

/me coughs in ngn's direction

Bubbler

01:34

(,/,/:\:)/ is the same length as {+x@'!#'x}

Also (#/|#:\) is the same length as {(#x)#x} (parens added because ')

Traws

01:57

nice.. you guys came up with the two solutions I had seen. the challenge was inspired by this comment. the solution there is the same as @Bubbler's with @ngn's atom->list step

n-dimensional cartesian product.. i guess it's one more item for that library of useful expressions

ktye

04:57

@ngn after writing c in k-style, you took on your next victim which is "make"

ngn

@ktye lol

ktye

just tabs refuse being replaced by single space!

ngn

@JohnE i'm thinking of making a list of things this language won't protect you from: [0] self-harm, [1] idiotic coworkers .. :)

ktye

@ngn is the openbsd port fully functional and passes all tests?

ngn

@ktye i don't know. see codeberg.org/ngn/k/issues/12

ktye

05:07

so you don't run it yourself.
do you still have ci-builds? or has that been remove with going to codeberg?

ngn

@ktye i haven't researched if codeberg has such a thing yet

it doesn't look like it has ci

ktye

@ngn maybe with an external service

ngn

openbsd is difficult because they let syscalls be invoked only from libc

for "security"

@dzaima does "1⊣" mean the same as in apl? can you explain the line with "_timed"?

@dzaima why is there a \t:10000 in the k test and 1000x in the bqn test. missing 0? or is that just scaling nano- to milliseconds?

ktye

@ngn i thought that does not apply to statically linked programs.

ngn

@dzaima also, why is addition done in such a strange way - "{a+x}" applied to "b" instead of just "{a+b}"?

ngn

07:24

@dzaima ah, i think i remember now.. the 1⊣ is because you don't have "shy" results

@dzaima about your paste bin - i recommend adding monospace as a fallback font, for people like me who hate custom fonts :)

ngn

08:12

@dzaima thanks. it should look a little better now

xpqz

09:01

How does @ ammend higher-rank arrays? I wrote {@[x;&2!x;+;1]} to add 1 to every odd number, but that doesn't do what I want for a matrix: ngn.codeberg.page/…

meta-q: how do I make a nice link in chat-markdown? The standard [anchor](url) thing doesn't seem to cut it.

chrispsn

10:34

any thoughts on how to get the 'wip' to match the 'current' here?

@xpqz that should work

dzaima

@ngn yeah. Just so the result isn't printed on the screen

@ngn 10000 {a+𝕩}•_timed b is the average runtime from 10000 runs in seconds, 1000× makes it milliseconds, and 10000× makes it not average but total. It's done as {a+𝕩} because {a+b} would be immediately invoked and not a function (stupid feature). It could also be {𝕤⋄a+b}•_timed@ instead of {a+𝕩}•_timed b, but the latter is shorter :)

dzaima

10:53

@xpqz Your message was […[…]…]() and SE got confused about nested brackets. You could either make the code a code block, or do […\[…\]…]()

chrispsn

11:03

@chrispsn ah that won't work

dzaima

@ngn nice

@ngn oh, i don't do that? :|

@ngn should be added to all #BQN/#APL

@ngn I think you should be able to do better by using the same 'is any word on' check as your new ?, which is two instructions instead of the shuffle & or mess you have now

the new + perf & asm:
https://dzaima.github.io/paste/#0jVVRb9owEH7nV1hCmmJwgxOgTaFU6tRpQyot6pCqFTHJEANhQLI4ydJqz3uf9g/3S3ZOmuAE6GopcXz33X3n8/nC@n0No8bS3fCG/cycDWssnKDxrfGt8iHi26CDZk@zNReVypD7MxCgl1FBxfHq@toRTAi@ma6fkDtHgs8Cx90iPeBx0HnVkuajZZ4xk6IL1u9fFm2Y3ENnz7Rq87mz5Wh5p83JiKzJgnBd1zFazhNBX1uTm1uNYXzj9Gj3QXMutoR3nXpv0WX13rq26E7ltw8v7ECSGiL0PNcPkBtxf752f4jDfFcZH04VSgAjFI0XE@IC30qTy7DHxuvaalKfjleTrvuzp6XrryF@p0kZfHQjmHshHmru5eXnR22Ea9aJQRw8mGk@icjjFcaHIxm8Ekm1aibBJIEkDClzTZMqLLmxVA01qTwBVjkDayL1pYEUHKN2tYCM8E4BWWHValCtjiAASj7KbeBUOEqFRiYcaJt9ZCIsIQ8zb8vMtwXmOk4Fua9EoDLWXgQ5olZkgr1NyXsM05J8kp…

coltim

12:33

@xpqz the closest I can get is {x .[;;1+]/+&2!x}, although I'm pretty sure there's a better way...

@JohnE that's a much better articulation. it's bad enough when your own non-library/framework code has a bunch of non-local things going on, but if the foundational code does that as well...

I guess in K too there are pretty clear delineations between the differences that cause different overloads to be applied. lists are different than atoms, integers from floats, etc etc. it's not that often that things change types on their own, which really cuts down on the surprise factor. it probably does make reading a function more difficult in the abstract if you don't know what data is getting passed in though

Traws

12:59

@xpqz to amend items from a matrix you have to use drill/dmend/amend-at-depth, but as @coltim showed, you can't just give it a list of indices

coltim

13:13

on the subject of the relationship between dictionaries and lists, I think it can even leak into the implementation a bit (inadvertently). for example, i'dct only works if the dictionary's keys are !#dct. this also used to apply to i?dct, although that's a 'typ error now

xpqz

Given a bool vector, I want to set everything to zero apart from the first 1. In APL, I can do `<`:

    <\0 1 0 1 0 0 1
0 1 0 0 0 0 0

due to its R-L evaluation order, but that doesn't work in k.

I can get there in a roundabout way using `|`: {(~=)/(-1_0,f;f:|\x)} but I'm sure there's a clever scan I can't see.

chrispsn

@coltim @xpqz that might be the best that can be done with dmend, but you could always use straight-up addition in this case: {x+2!x}

@xpqz could do {(!#x)=x?1}

coltim

what about ~<>:?

xpqz

@chrispsn oh my, that's creative...

chrispsn

13:29

@coltim @xpqz no, ^THAT is creative

you could do the literal translation of the qn: {@[x;1_&1=x;~:]} or for known boolean {@[x;1_&x;~:]}

xpqz

Did you just pluck that out of thin air, @coltim, or is that some standard canon k idiom passed down from Arthur on a stone tablet?

coltim

@xpqz I think it came out of my keyboard smashing on this golf

chrispsn

@coltim you know i was literally looking at that yesterday thinking about the apl-style expand

coltim

(or rather, at least using < and > heavily when doing boolean stuff. I think @Bubbler had some nice golfs with it too)

chrispsn

thinking more about amend/dmend

i wonder if we could get most of the benefits of structural under if the third arg could be a scan

right now it does a parallel thing for example

similar qn to the whole 'implicit each for filter?' thing

@coltim only risk of this soln is that it won't work for all zeroes

coltim

13:40

@chrispsn ooh good point. it may need to be &'ed with the input, like {x&~<>x}

@chrispsn is this related to this bit about "cross-sections" in the q docs?

xpqz

@coltim I think it fails on all zeros...~<>:0 0 0 0 0 0

chrispsn

@coltim that is more a dmend-specific thing

i'm more talking about... say you want to mark zeroes with ascending indices in order of occurrence: this change would let you do {@[x;&~x;+\~:]}

so operating on the whole subset

coltim

@chrispsn hmm is this like a splice/insert but with a set of indices rather than a start + offset?

chrispsn

oh wait what

it DOES work

wait no never mind

@coltim i'm not sure. i think the output length is still the same as the input length

it's basically 'grab subset of list; operate on that as if you had indexed in; put them back in their original places'

coltim

@chrispsn yeh the terminology is messy =|

although that sounds a lot like a qsql update

chrispsn

13:48

yes!

coltim

maybe something like "update +\~x from x where ~x"

or in q, update sums not x from ([]x:1 0 2 3 0 0 4 0 0 5) where not x

xpqz

15:15

Now up to 2017: gist.github.com/xpqz/094a0e82690f2333def8a12101c9c870

Suggestions taken for 2 & 10 :)

xpqz

15:40

Or at least 10.

coltim

what about the others? =P

Traws

@xpqz the idiom for ceil is -_-:

xpqz

@coltim good point, well made….

coltim

15:55

I guess phrasing it differently, they're interesting problems that have multiple approaches =)

xpqz

@coltim No, I'm really super-grateful for you guys pointing out how my solutions can be improved. I'm learning a lot.

@Traws wow, that's a cunning trick

coltim

I think |=':|"", works for P9, although I've never wrapped a f': each-prior with reverses like that

Razetime

p1 can just be 1+2*!:

Traws

@xpqz for 10 you can use overindexing to pad with nulls: example

xpqz

@Traws !! that's a useful thing to know

coltim

16:08

P3 can take advantage of multi-character str/x string-join, e.g. ngn.codeberg.page/k/…

xpqz

@Traws That gets me to the much more pleasing {(s;s)#x@!s*s:-_-:%#x}

coltim

P5 can use the {~^y?x} "idiom", which in most other K's is just x in y

Razetime

P3 can be {x@&a|~(~=)\a:"\""=x}

coltim

@ngn is the behavior of this deliberate? with my user hat firmly affixed, when I index into a dictionary mapping keys to integer lists, I would expect to get an empty integer list back if I looked up a key that wasn't present in it

Traws

16:24

@xpqz nice! since you are now inlining the ceil definition you can even drop the colon

xpqz

16:51

Thanks, all - I've updated the gist with some of your golfs

nathan rogers

17:14

@xpqz linky

xpqz

@nathanrogers gist.github.com/xpqz/094a0e82690f2333def8a12101c9c870

coltim

17:43

@xpqz hmm, another approach could be 1=+\

Traws

@coltim I think this should be 1=+\|\

easier without backticks :)

coltim

@Traws right!

@Traws also right! ha.

ngn

19:38

@coltim the reason you got ,0N is the same reason (,0;1 4 5;2 3)@3 is ,0N - the result for outdexing is built from the first element by preserving its structure and replacing everything in it with nulls

dict indexing translates to list find and list indexing. if d:k!v then d@i is v@k?i

@dzaima now you do :)

@dzaima but 'is any word on' tests all bits. when checking for overflow i must test only the most significant bit.

a signed comparison with 0 might produce better code.. i'll try that later

dzaima

yeah, a comparison & boolean or reduce is what I had in mind

i think it'd reduce the 21 instruction loop to ~16

also i have no clue why it temporarily saves the result on stack. should be easily avoidable but i guess clang just doesn't realize js 78 won't return

ngn

@dzaima it's complicated..

@dzaima it's because the two arguments and the result aren't necessarily distinct pointers

Stevan Apter

19:53

hi folks - ngn suggested i ask here about how to create an account for the Element | k chat. i think the link is: app.element.io/#/room/#aplfarm-k:matrix.org

dzaima

@ngn that shouldn't matter here. It just writes to [rsp], reads from it, and never does anything else

@StevanApter "sign up" at bottom left there should just work

coltim

@ngn hmm, that definitely explains what the k7 and k9 web repls do (they return either 3 Ø's or 3 0's). somehow k4 returns `long$() for both examples, which I (naively) prefer =P

Stevan Apter

20:09

well, that chat room seems like a gigantic waste of time

JohnE

20:53

that's chat rooms for you

ngn

@chrispsn what's the problem you're trying to solve?

@xpqz &: on higher-rank arrays is an ngn/k extesions, suggested by @chrispsn

it returns the paths to the truthy atoms in x as columns of a matrix

of course, the simplest solution to your particular problem is {x+2!x}, but if you insist on using amend for the "deep" case, it could be done using "each": {x@[;;+;1]'&'2!x}

or with "drill" over all paths: ngn/k, {x .[;;+;1]/+&2!x}

it's hard to make something that works for both the flat and the nested case

because "deep where" has an inconsistency between those

if where on a rank1 list behaved strictly the same way as where on a more deeply nested list, it would have to return an enlisted result, which would be incompatible with the orginal k, and not very convenient

@xpqz you could use the "link" button in ngn.codeberg.page/k (or ngn.bitbucket.io/k) and remove the part that says "ngn/k, N bytes: "

@coltim i' is the win() function here :)

ngn

21:37

@dzaima yeah, that's strange. it could have just copied ymm2 into ymm0

sometimes i doubt if this strategy for overflows is worth it

my current strategy is: if an overflow happens, expand the current result to a wider type and continue the operation from the same index onwards (more or less "the same", as everything's happening in groups of 32 bytes)

instead of that, i could just discard the current result, widen the arguments, and repeat the whole operation from the start

dzaima

doesn't work if you do in-place

ngn

that's true, unfortunately :(

dzaima

fwiw, marshall mentioned doing the same exact strategy

ngn

i don't like it very much, it's too complicated and fragile and it bloats the inner loops

on the other hand memory reuse is very important

dzaima

i think you could make a function (for each size 8,16,32) that takes the result & argument objects & a function pointer to the next width function, and does the widening & calls the function

ngn

21:52

@dzaima that's more or less how it works now

dzaima

oh, you have special functions for the overflow loops

ngn

the code that deals with refcounts, types and widening is in one place

adm() //add or multiply

x+y and x*y are the only dyadic verbs that can overflow. x-y is x+-y.

dzaima

would explain - being 1.5x slower than +

ooh fancy - defending against ¯32768 ÷ ¯1 by not having an integer divide by negative number :)

ngn

@dzaima was that the pentium div bug?

dzaima

no, just that ¯32768 ÷ ¯1 has both args fitting in `H, but the result doesn't

ngn

22:06

@dzaima well, who needs int div for negative numbers anyway.. but --32768 still has to be special cased

dzaima

right, for negation it's still required and div by negative is useless. just saying that it's a very nice coincidence, allowing int div to never overflow

rak1507

@StevanApter how come?

ngn

22:20

@dzaima how did you implement + in cbqn? did you ever use "singeli"?

dzaima

yesterday, by dzaima

lol CBQNs unvectorized + is a bit faster than ngn/k's :D

CBQN doesn't have any vectorized arith currently

marshall is working on getting singeli usable though

ngn

ah, so it's slower now

dzaima

yeah, ngn/k beats CBQN in arithmetic speed.. for now

ngn

actually i would also be happy if ngn/k is a little slower but a lot simpler :)

dzaima

well, CBQN is almost at 1MB :)

ngn

22:24

i'm not introducing a whole new custom language with its own parser, compiler, etc.. just to make one line of code use 17 instructions instead of 19 or something

dzaima

btw mII isn't vectorized at all for me. just a bunch of unrolling:
https://dzaima.github.io/paste/#0lZdtj@I2EIC/76@IhFTF4A12XiAsx0pXbdUi3d5tr0gn3YpKIQkQjhCUBJqr@vm@V/2H90s6thNe4iQXIu0aPJ6ZZ8YTewinUxUp/XUU@n3vbycInf4qSPtf@l/ufjn6u/RBcb@6Wz@5u3vxYxcmlPy5U66f5u9PQeIkiR8utl@VaKkkvpsG0U7RUj9LH5pVyekxddsjRHkTTqePJaWQhfFQod3x/GWw85X1B3WJZ3iLV9jXNA0p6yWfmKpb/O696iD0LpiQ8Sc1eLPD/jjoTVZjpzfZdlfjBfscwz8UQKb6yWG/j@JUiY5@vNxGfyU1Dt8WDpEQXBDMlOPrao4jcLhR2dfDxHnddjfz3uJ1Mx9H/0xU8f3PA/pJZXPwYXyEcXJAL2r0@PjHZ3WGuvY9xQF6dtUYH/HntwjVoDw3oHQ6OqfhJNyFcN1VmQgx54iJXlQmvAe3bAS3fDZmCmyi1nekpniGzgLIi9PppJ3ODAgI/pUFg…

ngn

@ngn if the performance difference gets to, let's say 2x, then i think it would be worrying :)

@dzaima that's multiplication though

dzaima

right

ngn

i'm not aware of a simple way to detect overflows there

of course vectorization != detecting overflows..

dzaima

i think you can expand to double the size, multiply, and check the high half

ngn

22:30

that's exactly what i'm doing

dzaima

and it seems autovectorizer isn't smart enough to pick it up

ngn

yep

coltim

aren’t the intrinsics a bit weird for multiplication? like mullo/mulhi

dzaima

@ngn singeli isn't just for addition & multiplication overflow though. Really it's mostly just for trivial generic impls for all sizes. We'll probably end up using it in most primitives just for that, and gain full control while at it

in the long term, it'd probably be a good start for JIT loop fusion if it ever gets to that

ngn

jit is so tempting but: you either have to maintain multiple versions of your code, or sacrifice support for anything but x86, and it's not clear how significant the performance gains would be..

when in doubt, err on the side of simplicity :)

@coltim that shounds like doing it in halves: "lo"="low" and "hi"="high"

dzaima

22:37

@coltim i forgot those even exist. I just imagined splitting e.g. input 8x32 into two 4x64 registers and multiplication on those. but those make it even easier i think

@ngn but then there comes singeli - you write the operation once, and it can be used both statically and in JIT

coltim

yeh it may just throw off the autovectorizer. i think there’s not even a simd 64 bit integer multiply until avx512

dzaima

@coltim oh yeah, 64-bit multiplication is indeed avx512 :/

@dzaima ok then that's acceptable

ngn

i'm supposed to have avx512..

dzaima

also mulhi appears to exist only for 16-bit :|

and 8-bit multiplication just doesn't exist i guess

coltim

i thought part of the workflow was to emulate the larger bit counts with the smaller operations

like you multiply the lower 32 bits of your longs, then mul the higher bits, then combine somehow

dzaima

22:44

that's of course an option

don't know how complicated it gets though, might not be worth it when compared to a regular scalar loop

coltim

maybe one of the simd libraries would be informative. honestly i dunno all the details

avx512 certainly makes a lot of things conceptually simpler!

dzaima

23:12

bit of a mess

clang what

Transcript for