Every project that gets built on something has a moment where you have to explain the something. Amber's is ngn/k — a compact, AGPLv3 implementation of the K array language, written by ngn, in a dialect of C that I can only describe as compressed. I did not write it. Everything in the four posts after this one is built on it, and none of that would make sense without first saying what it is and what it already does.
This post is that. What K is, why an array language ends up looking like line noise, how ngn's interpreter actually represents a value, and — the part that matters for everything downstream — which properties of that design made it the right thing to build a market-data engine on.
What K is
K is an array language in the APL tradition. The unit of work is the whole array, not the element. There are no loops in idiomatic K because there is nothing to loop over: the primitives already apply to every element.
1 2 3 + 10 20 30 / 11 22 33
+/ 1 2 3 4 5 / 15 — plus, folded
!5 / 0 1 2 3 4
&1 0 1 1 0 / 0 2 3 — the indices where the mask is trueWhat distinguishes K from APL is the ASCII and the size. APL wants a special keyboard; K uses the characters that were already on yours. And where a modern APL implementation is a large system, K has a tradition of being small enough for one person to hold in their head — Arthur Whitney's original K implementations were famously terse, and ngn/k continues that lineage.
The primitives are single characters, and most of them are overloaded on arity. # is
count as a monad and take as a dyad. | is reverse and
max. ? is distinct, find and random depending on
what you hand it. That sounds like a recipe for chaos and mostly is not, because the meanings are
related and because in practice you are reading a phrase, not a character.
The reason a K expression looks dense is that it is dense. It is not shorthand for a longer program — there is no longer program. The phrase is the whole thing.
The other half of the language is the adverbs — / \ ' — which
modify a verb rather than a value. +/ is "plus, folded". +\ is "plus,
scanned", which gives you running sums. ' is each. Combining a small set of verbs with a
smaller set of adverbs is where the expressive density comes from, and it is the thing that takes a
few weeks to stop feeling hostile.
Why I did not write my own
I wanted a q/kdb+-shaped engine: tables, keyed tables, the join family, select … by … from,
column attributes, temporal types, an as-of join fast enough to be the default rather than the last
resort. None of that is the hard part.
The hard part is everything underneath: a memory manager that can allocate and free a hundred million small objects without fragmenting, a refcounting discipline that does not leak, a parser, a compiler, a VM, an error path, a formatter, and a set of primitives that are all mutually consistent about types, nulls, ranks and edge cases. That is years of work and it is work where being 95% correct is indistinguishable from being wrong.
ngn/k has all of it, it is AGPLv3, and it is small enough to read. So I read it.
The representation, which is the whole idea
Here is the thing that took longest to appreciate and pays for itself everywhere. In ngn's design a K value is a single 64-bit word, and for a large family of types the value is that word.
The header comment in src/a.h states the layout directly:
//header bytes: b....... XXXXXXXX ....OEkt rrrrnnnn
#define _V(x) ((V*)(x)) //pointer to data
#define _n(x) (*(U *)((x)- 4))//length
#define _r(x) (*(U *)((x)- 8))//refcount
#define _T(x) (*(UC*)((x)- 9))//type(hdr)
#define _k(x) (*(UC*)((x)-10))//arity(for funcs)
#define _E(x) (*(UC*)((x)-11))//adverb(for tr)
#define _O(x) (*(UC*)((x)-12))//scroffset(for symbol lists)
#define _X(x) (*(A *)((x)-24))//ptr to next chunk in bucket
#define _b(x) (*(UC*)((x)-32))//bucket indexThree consequences follow, and all three are load-bearing later.
1. A pointer to a K list points at the data
Not at a struct that contains a pointer to the data. The header sits before the payload and
you reach it by subtracting. So _V(x) — the address of the first element — is
x itself, and handing that address to something outside the interpreter is free.
That is the entire reason Amber's Arrow and NumPy bridges can be genuinely zero-copy. A column's payload is already a plain contiguous typed array with nothing interleaved and no descriptor in front of it. There is nothing to convert. (It is also the reason the inbound direction always copies: a foreign allocation has no header behind it, and you cannot retroactively put one there.)
2. Small values never touch the heap
An integer, a char, a symbol id — these live entirely in the tagged word. No allocation, no refcount traffic, no cache miss to find out what type something is. In a language where a scalar appears in every expression, that is not a micro-optimisation; it is the difference between an interpreter and a toy.
3. There is room in the header
Look at the offsets: -9 type, -10 arity, -11 adverb,
-12 symbol scroffset… and then a gap before -24. Byte -13 is
unused for every type that is not a function.
That gap is where Amber's column attributes live. One byte, already in the cache line you were going to touch anyway, costing nothing to read and nothing to carry. Post three is entirely about what I did with it.
The code, and how to read it
ngn/k is written in a macro-heavy, extremely abbreviated C. The first time you open it, it does not look like C at all:
#define _(a...) {return({a;});}
#define W(x,a...) while(x){a;}
#define P(x,a...) if(x){_(a)}
#define I(x,a...) if(x){a;}
#define J(a...) else I(a)
#define E(a...) else{a;}
#define S(x,a...) switch(x){a}
#define C(x,a...) case x:{a;}break;
#define D(a...) default:{a;}break;So P(cond, expr) is "if cond, return expr". S(t, C(tI, …) C(tF, …) D(…)) is a
switch over a type tag. Once you have those nine macros the code reads normally, and the density stops
being an obstacle and becomes the point: a whole primitive is visible at once, without scrolling.
The file names are single characters and the line counts are meaningless. Some real numbers from the tree Amber builds:
b.c — the compiler and the stack VMp.c, the parserThe 82-line file is not a stub. b.c contains the real compiler — it walks a parse tree
and emits a flat opcode array plus a constant pool — and the real VM that runs it (cr(),
cpl(), run()). The AST is never walked at evaluation time. I only learned
that with certainty when I wrote the disassembler, which decodes the
bytecode the compiler actually emits and confirms, among other things, that it constant-folds.
src/g.h — a file of accessor macros — carries the comment
// generated by g.k. Part of the C is generated by a K program. In a language whose whole
argument is that array notation is a better way to express transformations, using it to write your own
boilerplate is not a stunt; it is the thesis applied to itself.
Memory
The heap is mmap'd with MAP_NORESERVE and sized lazily by the operating
system. There is no tunable, no --heap-size, no configuration file. That is why Amber has
no AMBER_MEM_MB and never will: there is nothing to tune, because the OS is already doing
the tuning.
Allocation is a buddy allocator over power-of-two buckets. an(n, t) computes the bucket
index from the byte size, pulls a chunk, stamps the header and hands back a pointer to the payload:
NI A an(U n,C t)_(Q(!lck)Q(tA<=t)Q(t<tn)Q(!TP(t))
U i=58-CLZ(HD|HD-1+(((W)n<<Tw[t])+7>>3));
A x=mb(i);xb=i;xr=REFB;xT=t;xn=n;_at(x)=0;x)Freeing is refcount-driven, and the refcount is one 32-bit field at -8. Amber added
exactly one line to that function — _at(x)=0, clearing the attribute byte on a fresh
allocation — which is a fair summary of how invasive most of my changes to the core needed to be.
HD, the header size, was 32 bytes. Which meant every payload pointer landed exactly 32
bytes past a 64-byte boundary — I measured ptr % 64 == 32 for every allocation size —
splitting a cache line on the first wide access of every array. Moving HD to 64 fixed it.
That is the kind of thing you only find by probing, and it only mattered once I had SIMD kernels
reading those payloads. It is in post five.
What I got for free
Setting the language aside, here is the inventory of what already existed the day I started:
| Component | What it does |
|---|---|
p.c | the parser — tokens to parse tree, including the context-sensitive rules that make / either an adverb or a comment |
b.c | the compiler and the stack VM. Every expression becomes bytecode; nothing walks a tree at run time |
m.c | the buddy allocator and the refcounting |
2.c, 3.c | the element-wise and reduction kernels, one per type combination |
f.c | search and find — ?, in, the group and distinct machinery |
v.c | the verb table and rank/rank-adjustment logic |
s.c | the formatter — how a value prints |
e.c | the error path, and the caret that points at the failing token |
0.c | the platform layer: file I/O, mmap, the socket connect(), and a freestanding wasm mode |
That last one deserves a note. 0.c already had a -Dwasm path with its own
tiny virtual filesystem and syscall shims, designed so the interpreter could be compiled for
wasm32. Years later that is why Amber Notepad — the real engine, in a browser tab, offline — was a
weekend rather than a rewrite. Someone else's foresight.
What K does not have
Everything a tick shop needs, roughly. K gives you dictionaries and a transpose, and a table in the
q sense is a transposed dictionary of columns — but that is an observation, not an implementation.
There is no ([]…) literal, no keyed table, no select, no join family, no
meta, no attributes, no temporal types, no as-of join.
There is also no q vocabulary at all: no wavg, no xbar, no
aj, no bars. Those names carry meaning to anyone who has worked on a trading
desk, and reproducing them exactly — including the argument orders people already have in their
fingers — is most of what makes an engine adoptable rather than merely correct.
And there are ergonomics. Errors print a single terse word. Tables do not render as grids. The REPL has no line editing (this was true when I started; I ended up writing my own editor, which is post five). None of that is a criticism — K is a language, not a product, and it is a very good language.
The licence, said plainly
ngn/k is AGPLv3. Amber is therefore AGPLv3, and that attribution is recorded in
NOTICE:
Amber's interpreter core is derived from a k array-language interpreter released
under the GNU AGPLv3 by its original author (ngn). That upstream copyright is
retained here solely as the AGPLv3 requires; this NOTICE is the single place it
is recorded. Amber is an independent language and is not affiliated with, nor a
distribution of, that project.Both halves of that matter. The attribution is real work by someone else and it stays. And Amber is
its own language with its own name, its own vocabulary and its own semantics — the interpreter is named
amber, never k or q; it reads no QHOME, no config,
no dotfiles; and it lives entirely inside one folder so that deleting the folder uninstalls it. Your
existing k, q or kona installs are untouched, because Amber never goes anywhere near them.
What the next four posts are
In the order I built them:
- The q layer —
([]…)table literals in the C parser, keyed tables, the eight-member join family, and a line rewriter that lets you typeselect … by … from …at the prompt with no wrapper. - Attributes — the byte at
-13, the four promises it can hold, and which kernels are allowed to believe it. - Native kernels — first-class temporal types, a SIMD kernel library, a multithreaded vector engine, a 16 MB bump arena, and a branch-free as-of join.
- The platform — a binary wire format, diagnostics that print once, a line editor
that replaced
rlwrap, an extension seam, and a shared library so that everything else can live outside the repository.
None of it would exist without the 264 kilobytes underneath. That is worth saying once, clearly, before I spend four posts talking about my own code.