the k tree

« first day (522 days earlier) ← previous day next day → last day (1013 days later) »

chrispsn

12:14

for those who have written a k: how would you describe your approach to parsing in simple terms?

(inspired by reading the parser for special k: beyondloom.com/tools/specialk.js)

also i always thought the shift-reduce parser for k7 on nsl was neat: nsl.com/k7/sr.k

3 hours later…

ngn

15:03

@chrispsn recursive descent

ngn

15:21

@chrispsn those who work on apl/j-like languages (that are not k-like) might have something interesting to say about parsing too

ktye

mine is similar to k6 parser from effbiae.com/parserclub. also john's parser combinators for tokenization. but just as k, w cannot return multiple values (token + size), so i store the current input position at the global memory address 8.

ktye

15:54

@ngn is o forbidden as a variable name in ngn/k? there's no error when i assign to it. i guess it's self-reference

ngn

16:19

@ktye yes, o is recursion, like in the original k5-6

(except for one subtle difference: mine is an ordinary identifier - a noun. in the original it was a verb.)

ktye

@ngn i thought my animation program is very slow. i removed the drawing and compared to ngn/k

/ktye-k
i:!m:(w:256)*h:256;O:(m#0),w#255
f:{r:-3/ 'r#i;O[i]::0|r+O[w+(m-1)&i+r];1+x}
256 f/0

/ngn-k
i:!m:(w:256)*h:256;O:(m#0),w#255
f:{r:-(#i)?3;O[i]::0|r+O[w+(m-1)&i+r];1+x}
256 f/0
/O

some subtle differences with the random numbers. O stores the resulting grayscale (255x255) max 255, which can be shown as pgm with header "P2\n256 256\n255\n"

ngn/k (my port) runs at 0.76s ktye (tcc version) runs at about 4s

ngn

@ktye O[i]:: could as well be O[i]: - there's no difference

maybe a smaller type would be faster? let me try..

ends up slower, actually :(

ktye

@ngn i sent you my version (generated c), if you want to compare on the same machine. i cannot run your original.

ngn

16:37

@ktye hang on, isn't (#i) always m?

and since you never change i, O[i]: could be O::

1+x seems unnecessary

ktye

my animation does not run with o:: not sure why. the 1+x was also because the original has it a fixed-point (endless loop)

ngn

@ktye your lambda basically transforms an old O into a new O. it's simpler as: 256{[O]..}/(m#0),w#255, and you can remove the 256 if you want an endless loop

ktye

@ngn no!

O is O:(m#0),w#255, O[i] is a subarray

the initial condition is all black + 1 white line at the bottom. then it spreads upwards

ngn

16:52

@ktye you could still use O[i]: then. or amend O with tetradic @.

@ktye do the last w elements ever change?

ktye

no. it's constant fuel from the bottom

ngn

@ktye ok, then you can manually concatenate w#255

ktye

@ngn but why? is that faster? i still need to index into the last row on the right hand side.

ngn

@ktye probably not faster but simpler

ktye

@ngn yes maybe, then we would make a k9 version when returning O. it still cannot assign to globals, i guess.

JohnE

17:03

@chrispsn I was reasonably pleased with the size of speciak-K's recursive-descent parser. the tokenizer still has an ugly hack for minus disambiguation and depends on fairly rich regular expressions. There are many ways to make tokenization simpler, but less compact in JS.

2 hours later…

ngn

19:23

i:!m:(w:256i)*h:256i
256{(0i|r+x w+(m-1i)&i+r:-m?3i),w#255i}/(m#0i),w#255i

@ktye ^this runs in ~220ms on my machine

amend and modified assignment - about 270-300ms

ktye

@ngn ^with ngn/k i assume. what was the time for the version i posted initially?

ngn

@ktye i haven't compiled it yet

ktye

@ngn i meant the time for ngn/k for this input: chat.stackexchange.com/transcript/message/55217134#55217134

ngn

@ktye yes, the timing is with ngn/k

@ktye for what you emailed me, gcc says undefined reference to some trig functions

ktye

@ngn add -lm

ngn

19:33

oh.. stupid me

yeah, now it works

@ktye how do i exit() from your language?

ktye

ngn

@ktye it doesn't work. drops me in a repl.

ktye

@ngn ah you mean from the commandline? k file.k -e

ngn

$ time ./a.out a.k -e
256


real	0m4.919s
user	0m4.916s
sys	0m0.000s

(this is your original version with O[i]::, x+1, and everything)

ktye

is that ok for k9?
i:!m:(w:256i)*h:256i
(256;{[x](0i|r+x w+(m-1i)&i+r:-m?3i),w#255i})/:(m#0i),w#255i

ngn

19:45

@ktye you could use an even smaller type for x, like 0g (byte)

~100ms here for k9 (2020.07.29), not bad at all

@ngn actually the "g" type doesn't support negatives :|

ktye

my printing is very slow (for large vectors). currently i use $x which produces a list of strings then join. that needs to create a lot of small buckets and is probably a bad idea.

ktye

20:02

you didn't compile with -O3 i guess. it makes a huge difference
ktye 1.6s vs 6.8s
ngn 0.37 vs 1.3s

ngn

@ktye now it's 0m1.338s :)

« first day (522 days earlier) ← previous day next day → last day (1013 days later) »

all rooms