the k tree

Dogbert

09:30

Hi @ngn. I tried compiling ngn/k on Alpine inside Docker running on macOS and got this error:

i.c i.c:28:44: fatal error: variable has incomplete type 'struct stat'
S I dir(A x)_(I f=op_(xR,O_RDONLY);ST stat s;Iv=fstat(f,&s);v=v>=0&&!!(s.st_mode&S_IFDIR);close(f);v)
^

Adding `#include<sys/stat.h>` to `i.c` fixed it. Maybe it's something related to Alpine, but just wanted to let you know in case you have any idea why this happened.

ngn

@Dogbert thanks! i'll add that. which compiler did you use?

Dogbert

clang. I just ran make and it worked with that change.

These are the commands I used (except the patching):

RUN apk add git make clang musl-dev
RUN git clone --depth 1 git.sr.ht/~ngn/k
WORKDIR k
RUN make

ngn

09:46

when i add #include<sys/stat.h> i get "undefined reference to `__fxstat'". i'm trying to understand why

Dogbert

which OS are you on?

might be something related to glibc vs musl? (alpine uses musl)

ngn

@Dogbert debian10

@Dogbert yeah, most likely

@Dogbert actually, i don't use glibc, i use the syscalls directly, but the compiler might be doing something different when musl is present

ktye

@ngn you don't use any libc calls, right? so it should not matter if there is musl or glibc

ngn

@ktye right

Dogbert

ah. I'll try building on debian10 on docker

ngn

10:01

the header contains a paragraph of explanations why stat() is an inline function that calls another.. basically, compatibility

but all i need is the struct

Dogbert

Tried compiling on ubuntu:latest, apparently `make` is calling `cc` somewhere which doesn't exist if you only install `clang-10`. I don't know too much about Makefile, but it looks like the problem might be in `t/makefile`?

> [6/6] RUN make:
#9 0.261 w.c f.c p.c i.c e.c a.c v.c h.c x.c s.c b.c c.c j.c m.c k.c k
#9 3.317 make[1]: cc: Command not found
#9 3.317 make[1]: *** [makefile:6: t] Error 127
#9 3.317 make: *** [makefile:9: t] Error 2

works if I also install gcc, but I have no idea what is calling plain cc

ngn

@Dogbert probably my test runner (./t/makefile)

why it decides to use gcc - i've no idea..

ngn

10:29

so, cc must be the default value of $(CC) in makefiles, and on debian we have symlinks /usr/bin/cc -> /etc/alternatives/cc and /etc/alternatives/cc -> /usr/bin/gcc

Dogbert

ah, maybe you need to pass CC from makefile to t/makefile?

got the docker build working btw! gist.github.com/e4ab300dd573bd5612b9df7debc4dc7c make build && make run

I'm writing a toy K interpreter and wanted to get something set up to compare performance :) Thanks for making ngn/k!

ngn

@Dogbert great!

@Dogbert do you know how to do that? (if not, i'll try to find out)

ktye

@ngn that leads to the question, if you thought about ci? sr seems to have that.

ngn

also, what if the tests are run directly?

@ktye continuous integration?

ktye

@ngn yes, e.g. running all tests, build release, build wasm

ngn

10:38

aha, this: man.sr.ht/builds.sr.ht

i haven't thought much about this yet but probably should be thinking :)

Dogbert

@ngn maybe this (haven't tried): $(MAKE) -> $(MAKE) CC=$(CC)?

ngn

@Dogbert that works, thanks

now the question is what to do if the tests' makefile is run directly

Dogbert

copy paste the CC= line from makefile:2 to t/makefile?

ngn

having the same thing in two places is not nice. ultimately someone will try to compile with gcc, changing CC only in the main makefile, and be surprised that the test runner fails to compile

i hate makefiles..

beagle3

@ngn the best minimalistic make-like thing I found is "redo". It is not standard, but there's a short script called "do" which you can include as fallback, which doesn't track dependencies, but does compile the whole project - for people who don't use redo

ktye

10:52

what about sh? just build everything. if it takes too long, your program is too large.

ngn

@ktye it doesn't have to be everything every time. there's if [ a.c -nt a.o ]; then clang ..; fi where -nt means "newer than"

@Dogbert is your toy k public?

ktye

@ngn how long does the compilation take? are you still having the netbook only?

ngn

@ktye about half a minute. yes, the local repair shop is taking too long to deal with my better laptop :(

ktye

oh, that's long (both).

is it much faster without optimizations? after all, it's not such a huge project

Dogbert

@ngn I actually just do make CC=gcc instead of editing makefiles when possible

@ngn will upload and post here when I get something working, probably euler #1

(right now it's just basic math operators on integers and reduce and scan adverbs)

ngn

11:06

@ktye measuring just compilation time (no tests): with -O3 - 25s, without - 7s

ktye

gcc or clang?

ngn

@ktye clang

Dogbert

@ngn which implementation of K do you refer to when adding features or testing? I'm following estradajke.github.io/k9-simples/k9 for now

ngn

@Dogbert i prefer the k6 dialect, so ngn/k is mostly like oK

occasionally i also pick the better features from k9

Dogbert

ah cool

ngn

11:11

@Dogbert see also: ngn.bitbucket.io/k.html

ktye

@Dogbert what about your implementation, do you have anyting to show? which implementation language do you use?

Dogbert

@ngn yup found that a few weeks ago, probably in this chat history, nice

@ktye I'm doing it in Rust, I'll upload when it can execute euler #1. It can parse euler #1 right now but I haven't implemented the verbs

ktye

cool

Dogbert

is there a K with arbitrary precision integers built in?

ngn

i'm not aware of any

ktye

11:25

@Dogbert i can offer an apl

Dogbert

@ktye oh, which one?

I actually started with trying to implement APL but the grammar is much more complex than K

on the up side APL has a full spec available

ngn

@Dogbert not only the grammar

Dogbert

@ktye this github.com/ktye/iv?

ngn

and maybe nars

Dogbert

ah I remember Rob Pike's ivy presentation

ngn

11:37

@Dogbert iso? it seems useless, tbh.. paywalled and mostly ignored these days

Dogbert

@ngn yes. gnu-apl's readme (or somewhere else on their site) has a direct download link to the pdf fossies.org/linux/apl/README-7-more-info

ktye

@Dogbert yes

Dogbert

@kyte cool, I see a lot of stuff is implemented github.com/ktye/iv/blob/master/TESTS.md

dicts/tables/objects too!

ngn

13:26

@ktye i have ci now :) first successful build

coltim

@Dogbert I think klong has bigints

ktye

13:41

@ngn wow, that's cool. is the manifest, the file you had to write?

ngn

@ktye yes, you just write some some magical spells in a .build.yml, put it in you repo and then builds.sr.ht starts running that every time you push

ktye

and the manifest as well? or is that generated by the system?

ngn

it's awesome and simple enough for me. it actually found a bug the first time it ran :)

@ktye .buid.yml is the manifest. you write that by hand, there's no web ui for it.

you can submit it through a web form if you like, but it seems easier to put it in the repo

ktye

i think the biggest advantage is building on multiple targets, what you usually wouldn't do locally (each time).

ngn

yeah, i agree

i'll try to configure more targets later. i must run now.

Dogbert

15:17

Using `FROM scratch`, the Docker image for ngn/k is now 123kb! (was 6mb w/ Alpine)

REPOSITORY            TAG       IMAGE ID       CREATED          SIZE
local/ngn/k           latest    439caf457849   43 seconds ago   123kB

gist.github.com/8fe5d2df0121705902e9002978d2d9a2

i'll stick with alpine so I can run time to measure peak memory usage though

coltim

@ngn I get a segfault when I use . dot-apply with matrix y, e.g. (1 2;3 4;5 6) . ((0 1;0 1);(0 1;0 1))

ktye

what's inside the image, only the k binary? or busybox as well? i assume that does not include the kernel.

Dogbert

@ktye yeah, just the binary. Docker itself is like 500mb+ for Mac though.

ngn

20:17

@coltim should the result be (((1 2;3 4);(1 2;3 4));((1 2;3 4);(1 2;3 4)))?

coltim

@ngn that matches oK's behavior. not sure I grok . enough to be able to weigh in on what it should do

ngn

@coltim sometimes i get confused by it too

coltim

I guess that sorta chains things, like first x is indexed by the first element, then the result of that is indexed by the second element... so I assume you'd have to know up-front what nested indices you want?

ngn

@coltim thanks, fixed

@coltim it's a bit more complicated as subsequent indexings use eachleft

for instance if you index a cube (3d array) with cube[i;j;k] where i j k are int lists, you should get a (smaller) cube as result

coltim

hmm wouldn't that be a single list of three items? vs. two lists of two each? (not sure which of the leading or trailing axis I was counting there, lol, but I mean the latter situation)

ngn

20:35

@coltim it works the same way like in apl

coltim

@ngn so that's equivalent to a .(1 0;2 0;3 1) which I mostly get, which is different than a .((1 0;2 0);3 1) (which I don't really get)

ngn

@coltim right, i was just trying to explain the example with the cube and the need for eachleft

@coltim think of a . (i;j) as equivalent to a[i]@\:j

(at least that's how it works in my impl)

ktye

@ngn ktye and k9 can only do that for 2d.

ngn

@ktye any particular reason . (i;j;k) can't be (a[i]@\:j)@\:k?

(using \: in the k6 sense here - as eachleft)

oh, hang on.. i got it wrong

ktye

i always thought it's a special case. a.l does indexing at depth, if all leading dimensions are singleton (not arrays). the last may be a vector.
i'll think about it, maybe i can simplify.

ngn

20:47

it's recursive, so: (a[i]@\:j)\:\:k

coltim

I think I get it, it doesn't matter that i is a list or a nested list

hmm. unrelated to that, but I wish cut would work on an empty list (just returning the right arg I guess)

ngn

@coltim yeah, k's indexing is right-atomic, it recurses for nested indices. apl has a lot more trouble with indexing - many different kinds, none of them as simple and clear as k's x@y

@coltim doesn't it?

coltim

@ngn for uh, reasons, I'm trying to do 0 1_()

ktye

For memory management of a k implementation: If i always copy when writing to variables or read from them, can i then overwrite input arrays in all functions without refcounting?

coltim

@coltim hmm nevermind

ngn

21:01

@ktye sounds crazy

ktye

i'm looking for a counter argument, where an array is used twice within an expression

ngn

@ktye would you also be copying from/to the stack?

ktye

@ngn you mean in between calls, no. that's the point.

ngn

i can't imagine how such a strategy would even work in practice

ktye

@ngn can you give a counter example?

ngn

21:09

@ktye you make a big array and it gets copied all over the place..

ktye

@ngn e.g. a simple monadic chain: f g h@ !bignum would pass on the reference and each monad overrites it's input.

ngn

@ktye but if you do something like a:!bignum; a+:1, you already have multiple copies

ktye

@ngn yes, now variables are involved. assignment and lookup are always copies. my question is, are these the only places where it is strictly necessary?

ngn

@ktye you say "overwrites its input" but not all monads return a result of the same size as their argument

but of course you can free and alloc again..

ktye

@ngn overwriting would only be done, if possible (as an optimization).

currently we do refcounting in all functions, everywhere. here we would assume all input has refcount 1. except in 2 places which is assign and lookup.

coltim

21:19

what about debugging/if there's an error halfway through handling a list of stuff?

ngn

@ktye refcounting is cheap (as performance), copying can be very expensive

ktye

that's always complicated. ngn rolls back and returns an error, right?
i panic. when running a script it exits. within the repl, i save/restore the complete workspace after each user input.

ngn

@ktye rolls back and returns an error - not always. "out of memory" is not recoverable.

Transcript for