Regular enough for a pacemaker

kaiv’s grammar is regular — data, schema, everything the runtime touches. On recursive formats nobody’s data needed, structure on the other side of the equals sign, and why all of kaiv processing is mere scanning.

Here is a 100-kilobyte JSON document meeting a standard parser:

$ python3 -c 'import json; json.loads("[" * 100000 + "]" * 100000)' 2>&1 | tail -1
RecursionError: Stack overflow (used 8156 kB) while decoding a JSON array from a unicode string

One hundred kilobytes of input; eight megabytes of stack, and then death. The input is degenerate, but the mechanism that died is not — it is the ordinary mechanism, doing what the format requires. JSON’s grammar is recursive: a value may be an object of values which may be objects of values, all the way down. A parser for a recursive grammar must carry a stack, and the stack’s depth is decided by the shape of the input. Node happens to survive this particular file, by spending even more memory from a bigger budget. The budget is the point: for every recursively-defined format, peak memory is a function of what the data looks like. You cannot state the bound until you’ve seen the document.

Now say that sentence in a design review for a pacemaker. Safety-critical runtimes — MISRA-C in automotive, DO-178C in avionics, IEC 62304 in medical devices — want statically bounded memory, no dynamic allocation, no recursion. A grammar whose memory cost depends on input shape fails that bar as a grammar, before a single line of parser code is written. This is why there is no JSON parser in an airplane’s flight control computer, and it is not because nobody has written a careful one.

kaiv began with this observation, and with a second one that makes it fixable.

Your data is rarely recursive

We use recursively-defined data formats ubiquitously. But look at the data in them: a server config, an invoice, a telemetry frame, a build manifest. Records, with fields, some of which are lists of records — two levels, three, maybe four, and the depth is known when you design the data. Genuinely recursive data — data whose depth is unknowable because the structure refers to itself — is rare. Unless your data is your family tree, or a similar graph shaped by the world rather than by a schema, nothing about it demands a recursive grammar.

JSON gives you one anyway, and makes nesting the default way to structure anything. That default has a quiet cost: nesting is free at authoring time and paid at every parse thereafter, so structures get lazier and deeper than strictly necessary — one more wrapper object, one more level, because the format never pushes back. The grammar is recursive, so the data drifts recursive, so the parsers must be recursive: the costliest property of the format is the one almost no document uses on purpose.

kaiv’s move: take the structure out of the grammar entirely, and put it on the other side of the assignment operator — into the name.

Structure in the namespace

Take a nested document every JSON user recognizes:

$ cat telemetry.json
{
  "device": {
    "id": "PM-4411",
    "firmware": {"version": "3.2.1", "checksum": "roVu2wY"}
  },
  "leads": [
    {"chamber": "RA", "impedance": 512.5},
    {"chamber": "RV", "impedance": 489.0}
  ]
}

Run it through the pipeline to canonical form:

$ kaiv import --json telemetry.json | kaiv build
.!daiv
!str'/device::id=PM-4411
!str'/device/firmware::version=3.2.1
!str'/device/firmware::checksum=roVu2wY
!str'/@leads/0::chamber=RA
!float'/@leads/0::impedance=512.5
!str'/@leads/1::chamber=RV
!float'/@leads/1::impedance=489.0

The braces are gone, and nothing was lost: every level of nesting became a segment of a namepath, on the left of =. /device/firmware::version says “descend into device, then firmware, then project the field version” — the structure that JSON encoded as a tree of delimiters, kaiv encodes as the spelling of each line’s name. Each line is self-contained: type, full address, value. Read any one of them in isolation and you know everything about that value.

The deeper difference is one of perspective. JSON begins at the root — { is the first character you type — and you design top-down: the outermost object first, then its sections, then subsections, until finally, levels down, the values go in last. The structure is conceived first, hollow, hanging in the air; the data arrives afterward to fill it.

kaiv views values as fundamental, and treats them as such. Values are the leaves of the graph, and every leaf is unmistakably identified: the :: projection operator, then its terminal name — the nearest JSON analog is the key in the deepest object holding the value. The entire structure sits to the left of the projection, in the steps (the namespace path); steps, projection, and name together form the namepath, the full address of one value. This is the bottom-up approach: you build the structure out of the data. The values are the foundation, and the containers exist because the values’ addresses pass through them — not the other way around. You never erect a hollow structure and then populate it; every line is a value first, carrying its own place in the whole. That is kaiv’s philosophy in one line of grammar: value on the right of =, identity after ::, structure in the steps.

And now depth is data, not parser state. Here is a pyramid two hundred levels deep:

$ python3 -c 'print("{\"a\":" * 200 + "1" + "}" * 200)' > deep.json
$ kaiv import --json deep.json
.!kaiv

!int
/a/a/a/a/a/a/a/a/a/a/a/a/a/a/a/a/a/a/a/a/a/a/a/a/a/a/a/a/a/a/a/a/a/a/a/a/a/a/a/a/a/a/a/a/a/a/a/a/a/a/a/a/a/a/a/a/a/a/a/a/a/a/a/a/a/a/a/a/a/a/a/a/a/a/a/a/a/a/a/a/a/a/a/a/a/a/a/a/a/a/a/a/a/a/a/a/a/a/a/a/a/a/a/a/a/a/a/a/a/a/a/a/a/a/a/a/a/a/a/a/a/a/a/a/a/a/a/a/a/a/a/a/a/a/a/a/a/a/a/a/a/a/a/a/a/a/a/a/a/a/a/a/a/a/a/a/a/a/a/a/a/a/a/a/a/a/a/a/a/a/a/a/a/a/a/a/a/a/a/a/a/a/a/a/a/a/a/a/a/a/a/a/a/a/a/a/a/a/a::a=1

Two hundred nested objects became one line — a long name, scrolled sideways, assigned once. What used to be two hundred stack frames is now two hundred characters. A scanner reads this line the same way it reads port=8443: left to right, one state machine, zero stack. The cost of depth didn’t disappear — you can see it right there in the file, which is exactly where it belongs: visible, paid by the author who chose it, free for every reader forever after.

Six rules, no stack

What does it take to read a kaiv file? For every line, exactly one of six rules applies:

That is the whole classifier, and it is shared by every file in the family — data, schema, type library. Within a line, the shape is fixed: metadata prefix, ', namepath, =, value. A canonical kaiv file is a sequence of lines, each matched by a regular expression — which makes the grammar of the entire file regular. Not “mostly regular”, not “regular except for nesting”: regular. The reader is a DFA over bytes. Its memory is a handful of state variables, the same handful for a ten-line config and a ten-million-line dump, declared at compile time like MISRA always wanted.

Authored kaiv does have conveniences — namespace blocks so you don’t repeat prefixes, variables so you don’t repeat values:

$ cat fleet.kaiv
.!kaiv

.dc=fra1

(/net)
host=api-$.dc.example.com
port=8443
()
$ kaiv build fleet.kaiv
.!daiv
!str'/net::host=api-fra1.example.com
!str'/net::port=8443

But notice where they live: in the authored file, and nowhere else. The build step resolves every variable and unfolds every block into flat, fully-qualified lines. The sugar is the compiler’s business, on a developer workstation with gigabytes to spare — it never crosses over to the reader.

All processing is scanning

Once every line is self-contained, “parsing” stops being a prerequisite for anything. The file is its own index:

$ kaiv import --json telemetry.json | kaiv build > telemetry.daiv
$ grep "'/@leads/" telemetry.daiv
!str'/@leads/0::chamber=RA
!float'/@leads/0::impedance=512.5
!str'/@leads/1::chamber=RV
!float'/@leads/1::impedance=489.0
$ awk -F= '/impedance/ {sum += $2} END {print sum}' telemetry.daiv
1001.5

grep of a namepath prefix is subtree selection — the query you’d write brackets for in a JSON tool is a prefix match on flat lines. awk just summed a field across an array without any kaiv-aware software involved. This isn’t a party trick; it is the same property the certified runtime relies on, showing up in your shell: when structure lives in the spelling of each line, every line-oriented tool ever written — grep, awk, sort, diff, comm, your log shipper — is already a kaiv processor.

The schema scans too

Validation could still have spoiled this — most schema languages are themselves nested documents walked by recursive evaluators. kaiv compiles the schema instead. An authored schema, human-shaped:

$ cat pace.saiv
.!saiv 1 demo/pace

!str
mode=
!int[30,220]
rate_min=
!int[30,220]
rate_max=

compiles to one line per field, in exactly the '-split shape of a data line:

$ kaiv schema pace.saiv > pace.csaiv
$ cat pace.csaiv
.!csaiv 1 demo/pace
!str'::mode=
/^-?[0-9]+$/ ..num [30,220]'::rate_min=
/^-?[0-9]+$/ ..num [30,220]'::rate_max=

(Note !int arriving unfolded into its pattern, span, and range — a type is only ever a constraint over a string, which is the previous article’s whole story.)

Put the compiled schema next to the data it validates:

$ printf '.!kaiv\nmode=DDD\nrate_min=60\nrate_max=130\n' > pace.kaiv
$ kaiv build pace.kaiv > pace.daiv
$ cat pace.daiv
.!daiv
!str'::mode=DDD
!str'::rate_min=60
!str'::rate_max=130
$ kaiv validate pace.daiv pace.csaiv
pass

Line for line, the .csaiv is structurally isomorphic to the .daiv — same classifier, same split, same order, because canonical kaiv keys are strictly ordered. So validation is a parallel scan: two file pointers advancing in lockstep, comparing each data line against its constraint line. No schema tree, no evaluator, no recursion — the schema is not walked, it is read alongside. Levels 0–1 of the format (all scalars and trees) validate this way in constant memory. Level 2 — table constraints like uniqueness and foreign keys — adds one honest O(N) counting pass, and a runtime that implements only Levels 0–1 never executes it and never touches a heap.

The certification boundary

Here is the architecture all of this buys, and it is the oldest trick in safety-critical systems, told about a data format. The kaiv pipeline is .kaiv → compiler → .raiv → denormalizer → .daiv → validator. Everything to the left of .daiv is a build tool: the compiler with its block stack and variable table, the denormalizer resolving references, the schema compiler. Context-free machinery, heaps, hash tables — all of it welcome, because all of it runs on a developer workstation or a CI runner and is validated by testing, not certified.

The target device loads two text files — the .daiv and the .csaiv — and runs two things: the six-rule lexer (a DFA over bytes) and the integrity check (the parallel scan above). No stack, no allocation, memory statically determined by the schema at build time. MISRA-C-certifiable, not by heroic implementation effort, but because there is nothing in the job that needs anything MISRA forbids. The target never sees a namespace block, a variable, a $ reference, or a brace: your sugar was compiled away on the other side of the boundary.

Automotive engineers will recognize the pattern — ECUs have consumed build-tool-generated, certified-runtime-read configuration this way for decades. What kaiv adds is that the interface artifact is not a bespoke binary blob per project but a specified, typed, self-describing text format, with the scanning-only guarantee made by the grammar rather than by a per-project audit.

JSON can’t run in pacemakers or airplane controls. kaiv was designed precisely with this in mind — not adapted to it after the fact; the regular grammar came first, and the format grew around the constraint that the reader must never need more than a scan.

And if your data is a family tree

Then kaiv still holds it — namepaths nest as deep as your data truly is, and the two-hundred-level line above went through the same six rules as everything else. The difference from JSON is not that depth is forbidden; it is that depth is explicit, priced, and paid in the right place. The file shows every level in every name. The author who nests pays in spelling, once, visibly. The reader — every reader, forever, including the one in the pacemaker — still just scans.

That is the theme, and certification is only its sharpest consequence. A regular grammar makes the format greppable, diffable line-by-line, streamable with constant memory, processable by forty years of Unix tools — and, at the far end of the same property, admissible in rooms where “how much memory, worst case?” must have a number for an answer before any code runs at all.

kaiv is an immutable structural type system for data at rest. The User Manual is the accessible tour; the specification defines the six-rule classifier (§ 1.3), the compiled schema, and the parallel-scan validation passes precisely; the playground runs the whole toolchain — including every example above — in your browser.