"Compiling" K

[Bakul Shah]

In adding the C-K API I got somewhat familiar with the main
path in kona. I am looking at finishing up sfn(), using code
for implementing "lib 2: (sym,valence)" as a template but it
keeps crashing. During debugging I see a stack of function
calls (ex ex_ ex0 ex1 ex2 dv_ex vf_ex ...). This is hard to
understand, which also makes fixing bugs harder, and it may be
a bit inefficient (though this last bit matters less).

Seems to me, one can complie K code relatively easily to a
high level threaded interpreter code. So for example,

a: +/ a * b

can be compiled into

push a; lookup b; lookup a; exec *; push +; scan; assign

Basically a stack machine with a few instructions. This
factors out parsing at a minimum + may be some semantic
analysis can be as well (right now what we have seems more
like a recursive descent compiler/interpreter). Among other
things we can map alternative syntaxes to the same code. We
can optimize the execution path separately and lambda don't
need to be parsed again. Various tricks are possible. If there
are < 16 instructions, we can store them in the low 4 bits
and `code' essentially becomes just a K list. For example:

int eval(K cl) {
I* code = cl->code;
int done = 0;
int pc = 0;
while (!done) {
I x = code[pc++];
int ins = x&0xf;
K data = (K)x&~0xf;
switch (((intptr_t)x)&0xf) {
case PUSH: push(data); break;

case LOOKUP: push(lookup(curdir, data)); break;
case MONAD:
f = op2fun(data);
x = pop(); push(f(x));
break;
case ASSIGN:
...
case INDEX:
...
case AMEND:
...
case CALL:
r = eval(data);
...
case SCAN:
...
case RETURN:
done = 1;
break;
}
}

Of course, real code will have to do error handling and lots
more but all this will be centralized here. [And someday we
may even do JIT:-)]

Kevin, have you looked at something like this in the past?
If you have and rejected it, I'd like to understand what the
problems were.

Obviously, this is just a thought experiment at present.

Thanks.

[Kevin Lawler]

The main execution path in the code is a large extension of the ex(wd()) pattern found in the J incunabulum. This is uncommon. As far as I understand it, A+ and even J use a stack based execution.

My current thinking is that In the long run, a stack-based execution system is better.

Development would be easier. Stack-based architectures are easier to follow. Some K operations (I'm thinking about adverbs like 'over' that are variably-adic) may not translate cleanly to a stack. I never got the "nva" descriptions (eg. nv->v) to make sense in the full context of all the adverb operations. This is why I avoided a stack originally. I'm not sure how sub-function-local variables might be implemented. The tree inheritance could mess things up. The stack architecture could end up being much less pure than you might initially think. I am not an expert on stack-based execution so I cannot predict the outcome accurately. Maybe all sub-functions need is a simple copy and everything works nicely. 

Performance will improve. Perhaps not as much as you might think. Atom operations will certainly be faster ("do[9999;n:+1]"). Function execution will improve. Array operations will not improve at all. Some code may even run slower. The most useful gain is likely to be in iterated function and subfunction execution. Sometimes that dictates the runtime. Other times array operations do.

Porting from the current architecture to a stack architecture will be hard. Building a simple stack based K is straightforward. Building a stack-based K that passes all the production tests is a lot of work, much of it detail-oriented. 

Kevin

--
You received this message because you are subscribed to the Google Groups "Kona Developers" group.
To unsubscribe from this group and stop receiving emails from it, send an email to kona-dev+u...@googlegroups.com.
For more options, visit https://groups.google.com/groups/opt_out.

[Bakul Shah]

Whitney's 1 pager was quite amazing!

But you are right; porting the current arch would be hard.
Should I decide to pursue this I will prototype this in a
separate directory and `steal' code from kona!

K3 is rumored to fit in "not quite" 1K (but presumably close).
That is very encouraging as it tells me is that k's features
fit together well even from an implementation point of view.

Thanks for your detailed response.

[Kevin Lawler]

On Jun 1, 2013, at 2:55 PM, Bakul Shah <ba...@bitblocks.com> wrote:

> But you are right; porting the current arch would be hard.
> Should I decide to pursue this I will prototype this in a
> separate directory and `steal' code from kona!

That's how I would do it. The array operations should work as is. The execution I might rewrite entirely.

I also suspect I got Amend (dot/at) wrong structurally. I might also redo the struct the memory pooler returns. I have notes on how a rewrite should go.

> K3 is rumored to fit in "not quite" 1K (but presumably close).
> That is very encouraging as it tells me is that k's features
> fit together well even from an implementation point of view.

1K source? Not even. Discounting any K written in K, Kona must be pretty close in size. There's no way to write much of this shorter in C. Discounting formatting also, I would guess Kona is within 1.25x. Worst case...2x-3x? If my assumptions about the world are horribly wrong.

Kona's parser is about 25K. The MDL for the parser has to be larger than 1/25th.

[Bakul Shah]

On Jun 1, 2013, at 5:37 PM, Kevin Lawler wrote:

> On Jun 1, 2013, at 2:55 PM, Bakul Shah <ba...@bitblocks.com> wrote:
>
>> But you are right; porting the current arch would be hard.
>> Should I decide to pursue this I will prototype this in a
>> separate directory and `steal' code from kona!
>
> That's how I would do it. The array operations should work as is. The execution I might rewrite entirely.
>
> I also suspect I got Amend (dot/at) wrong structurally. I might also redo the struct the memory pooler returns. I have notes on how a rewrite should go.

I would be interested in your notes!

>> K3 is rumored to fit in "not quite" 1K (but presumably close).
>> That is very encouraging as it tells me is that k's features
>> fit together well even from an implementation point of view.
>
> 1K source? Not even. Discounting any K written in K, Kona must be pretty close in size. There's no way to write much of this shorter in C. Discounting formatting also, I would guess Kona is within 1.25x. Worst case...2x-3x? If my assumptions about the world are horribly wrong.

I think that is 1k lines, not bytes. Assuming "Whitney style"!

I may have misremembered or misunderstood but from what I remember, on K mailing list over 10 years ago, Whitney said he is "trying" to fit K in 1K but didn't think he can do it but then the description he gave seemed to fit k4. k3 is much simpler. Now "trying" to me means it is at least in the realm of possibility! I wouldn't try to reduce something by a factor of 10! Though I did once rewrote someone else's server code to 1/3 the size and 3 times the performance. The way it came about is I couldn't understand his code so I started implementing pieces I did understand and two weeks later I realized it did most everything! But that sort of improvement is very hard if the starting point is some well written code.

Anyway, the point I was making is that everything seems to dovetail very well and that means most code would just "flow" -- and if something needs a complicated kludge, that would means something is either not in the right place or misunderstanding. The goal would be not 1K lines but close to the lowest entroy code!

kona is about 7K lines, not counting the header files. Array ops & possibly many other things can be reused almost verbatim.