A JSON Parser in Koru, and the Exponential Hiding In It

A grammar in Koru is not a string handed to a parser generator. It is a set of events. Each rule is an effect-branch; each alternative is an ordered choice; each terminal is a regex literal sitting where a branch head goes. Open a grammar vocabulary with [with], and the whole of JSON reads like this:

[with]std/parser:grammar(json)
! value v |> match(v)
    | `"([^"\\]|\\.)*"` s -> s
    | `-?(0|[1-9][0-9]*)(\.[0-9]+)?([eE][+-]?[0-9]+)?` n -> n
    | `true|false|null` k -> k
    | object o -> o
    | array a -> a
! string s |> match(s)
    | `"([^"\\]|\\.)*"` x -> x
! pair p |> match(p)
    | string s |> lit(":") |> sub(ws): w |> sub(value): v
! members m |> match(m)
    | pair p |> lit(",") |> sub(ws): w |> sub(members): r
    | pair p -> p
! object o |> match(o)
    | `\{` _ |> sub(members): m |> lit("}")
    | `\{` _ |> lit("}")
! elements e |> match(e)
    | value v |> lit(",") |> sub(ws): w |> sub(elements): r
    | value v -> v
! array a |> match(a)
    | `\[` _ |> sub(elements): e |> lit("]")
    | `\[` _ |> lit("]")
! ws w |> match(w)
    | `[ \t]*` s -> s

That is the entire recognizer — every JSON shape, from nested objects to numbers with fraction and exponent, validated by a grammar the compiler lowers to recursive-descent rule functions at comptime. There is no runtime grammar object and no interpreter; in cut 1 a rule produces a span — the top rule hands back the whole consumed text.

The idiom that makes it read cleanly

Look at members, elements, object, array. Each has two alternatives that begin on the same head:

! elements e |> match(e)
    | value v |> lit(",") |> sub(ws): w |> sub(elements): r
    | value v -> v

“A value followed by a comma and more elements — or just a value.” This is the canonical PEG list idiom, item "," rest | item, and in cut 1 it is not optional. With no epsilon rules, it cannot be left-factored away: repetition is right-recursion, and the two arms genuinely share their first element. Same-named branch heads like this are comptime data the grammar transform consumes — the frontend never mistakes them for dispatch ambiguity.

The bomb

Here is what that idiom compiles to, naively. To match elements, try alternative one: parse a value, then look for a comma. If the comma is missing — because this was the last element — alternative one fails, we backtrack, and alternative two parses the same value again.

For a flat list that is a mild tax: every list pays one re-parse of its final element. But make the last element a container, and the re-parse is a re-parse of a whole subtree. Nest that to the right — [1,[2,[3,[4,...]]]] — and the doubling compounds at every level. Depth 24 is 2^24 re-parses of the spine.

The number is not a figure of speech. Two documents, 111 bytes each, identical but for nesting direction:

The left-nested document parsed 4.0 million times in three seconds. Its right-nested twin — same 111 bytes, same element count, differing only in which direction it nests — managed nine. A factor of roughly 440,000, more than five orders of magnitude, from a change no larger than reversing a list. A silent exponential, sitting in the library, invisible until a benchmark went looking for it.

That last clause is the point. Koru holds that a performance cliff hiding inside a generated artifact is not a “known limitation” — it is a defect, the exact thing the no-silent-degradation tenet exists to forbid.

The fix is free — and provably so

Common-head factoring, in the codegen rather than the surface: when consecutive alternatives share a head, emit the head once, then try each tail in order against the saved result.

before                          after
─────────────────────          ─────────────────────
parse HEAD, parse tail₁         parse HEAD once
  fail → backtrack              try tail₁
parse HEAD again, tail₂           fail → try tail₂ (head kept)

The reason this is sound and not merely faster is worth stating precisely. A cut-1 rule function is a pure map from position to result: same input position in, same result out, no hidden state. So alternative two’s re-parse of the head was guaranteed to reproduce alternative one’s — byte for byte, every time. Skipping it changes nothing observable. The exponential collapses to linear; the right-nested document joins the left-nested one at millions of parses per second; and the flat grammar sheds its per-list last-element tax as a bonus.

The 641 cluster stays green across the change, and the suite now carries a cliff gate — the left- and right-nested twins must stay within a fixed ratio, so the exponential can never silently return.

Throughput

The recognizer answers one question — is this JSON, and where does it end — and returns a span. It does not tokenize, and it does not build a tree. So a fair comparison is against work of the same shape in the same category, and koru’s category is general parser libraries: you author a grammar or combinators and get a parser back from a reusable library. That is the peer axis. Here is the board for it — all three contenders in the recognizer lane, measured back-to-back in one run (M2 Pro, best-of-3, this suite’s protocol — MEASURED):

Among general parser libraries in the recognizer lane, this run: koru leads Rust nom by ~1.9x and Haskell parsec by ~44x.

That lead is not an accident of the harness, and it is not a caveat to bury — it is the mechanism, and the mechanism is the whole pitch of the library. All three contenders are general: hand each one a grammar and it hands back a parser. But nom and parsec stay general at runtime — the combinators they build are still combinators when the bytes arrive. Koru compiles its grammar to anchored-prefix DFA matchers at comptime, so the parser that runs is already specialized to this grammar before the first byte is read. Specialization-for-free is exactly what a library that lowers a grammar to code can give you and one that interprets combinators cannot — and it is why the general library out front is the one that compiles.

The comparison was made fair before it was stated. All three run validate-only in the recognizer lane and build no tree — nom folds its result to unit, parsec’s recognize returns () and discards. Parsec was built -O2 (2.47x over its own -O0) on a strict ByteString stream; a String-stream build measured 13.2 MB/s, so the 12.1 is parsec doing recognizer work as fast as parsec does it, not a slow-stream artifact.

Two more numbers exist, and they are shown only labelled, never raced against koru, because they are different work. In the same recognizer lane sits a hand-rolled Zig validator — bespoke, JSON-specific, no library — at 853.5 MB/s (recognizer / specialized): the ceiling a dedicated hand-written recognizer sets, which the generated general parser is still climbing toward, one codegen rung at a time. And a full step across the lane boundary: Rust’s serde_json, which allocates and builds the entire document, runs 192.7 MB/s (full-tree / specialized). Neither is a peer to a general recognizer; both are landmarks — and the discipline of this suite is that a landmark is never quoted as a win.

Why this is the shape of the whole library

The grammar at the top of this post is thirty lines, and it is the real thing — not a sketch, not a subset. The parser it becomes is generated, and because it is generated the same determinism argument that made this fix free is available everywhere: rule functions are pure, so the compiler is licensed to rewrite how they backtrack without changing what they accept. Common-head factoring is the first such rewrite. The instrument that surfaced the cliff will show the next one land, too.