2024-06-01
Arther Whitney, the creator of thek language(s), writes C code in a unique style. Somesee it cryptic while others find it elegant. I’ve known hisimplementation of J, and the word “Incunabulum”, from Dyalog’22. Butnever had I tried to reason about his works.
About several months ago, I started to do code-golf using ngn/k, an opensourceimplementation of K3, as to gain some experiences with the k language. Ihad tried to read ngn/k’s source code but was scared away by it’s size(translated: due to my laziness). In this January, Arther gave an referentialimplementation of a small k interpretor. It consists of only around60 lines of code, in which 33 lines are in the header. So I decided totake a look.
It took me about a hour to understand these 29 lines of C code. Wow,awc is dense. Here are some interesting points I got from the code.
There are only three explicit loops in the whole program. Twowhile-loops for formatting integers and for the main loop of theinterpreter. And a single for-loop in the macro i that’sresponsible for every iteration and vector-traversal in the program.Yep, no stinky loops!
Common patterns are encapsulated into macros but they leave enoughfreedom for customization. For example, n(n,e) generates anew vector with each element created by expression e, andit is used in everything from indexing a vector by another vector tobeing embedded in G(f,o) for doing inner-product betweenarrays.
It uses fixed names a and x for inputvariables in functions, just like how ⍺ and ⍵works in APL dfns. As an extension of the previous point, commonoperations like referencing the i-th element and increasing referencecount are made into macros for each input variable. This not only freesthe program from boilerplates, but also makes function definitions morestraight forward. Though it still requires cares like in the functionCat, x must be copied before asince it uses latter’s length, and a might be deallocatedby _a if they were copied the other way around.
At first, I had to jump between a.h and a.c constantly for referenceson what those macros do. After getting familiar with the macros, itreads like a C-style array language, and it’s easy to see how primitivesare built from each others. Almost nothing is redundant so nothing toglance over when one reads the code. I think it is an interesting way toformulate programs and it tries to capture their essence. It reallymakes its reader think about the program and how it is built, ratherthan just inferencing what it does from its shape in a glance and wonderif there were some off-by-one error caused by silly typos.
Here is the annotated a.c.
https://bxt.org/83ybb