Gleamalog: A Datalog for Agents

Kendall Clark · Pentad Labs · 10 July 2026 · PLRN-019

Algorithm = Logic + Control.

— Robert Kowalski, Communications of the ACM (1979)

Abstract

Gleamalog is the query language of WunderOS. It is a Datalog of agents, because agent and agent-OS state are the things it reads and because it is the sole entry point through which anything reads them. It is a Datalog by agents, because agents and I built it, and built it faster than a comparable language was built by people. It is a Datalog for agents, because its surface was designed against what agents demonstrably need rather than against what human programmers are used to, which means flat rather than nested, structured rather than prosaic, and dense rather than verbose. Each of the three can fail or succeed on its own. This note argues for each, and then gives Gleamalog’s semantics in detail.

1. Of agents

An agent acts and acting leaves a record. In WunderOS the record is Pentads, and everything is Pentads: the customer agent’s state, the shadow agent that twins it, the substrate’s own events, and, lately, the facts ingested from systems that were never designed with agents in mind. A store of Pentads is a store of facts with subject, predicate, object, context, and lineage, which is to say a relational store (sourced by a WAL and event stream; and projected as a knowledge graph) with five columns and a strong opinion about what the columns mean. The natural query language over such a thing is a Datalog. This is not a discovery. It is what the shape of the data already implies, and the interesting question was never whether to have a Datalog but which Datalog to have.

Gleamalog is WunderOS’s only query entry point. Every read of WunderOS state goes through it, whether the reader is a person at a console, a Brass Loom plan trigger, a Nabla standing lease, or another agent across an MCP boundary. This is a stronger commitment than it sounds, because WunderOS has several evaluation substrates and could easily have exposed several languages. ZRP navigates multi-hop by vector-symbolic wavefront. CSR walks integer graphs structurally. The classical fixpoint evaluator does recursion, negation, and aggregation. A system with three engines is under continuous temptation to grow three query surfaces, and the temptation is worth naming because yielding to it is the ordinary outcome. We did not yield. The engines are substrates; the router picks among them on the shape of the compiled program; and the language above the router is unitary.

The layering is the canonical one. Databases conventionally separate a planner and compiler on top from a storage engine and executor primitives below, and they all do so because the separation is structurally right for anything that evaluates queries over indexed binary substrate. Gleamalog puts the planner in Gleam and the executor primitives in Zig, which is the same split at the granularity of a function rather than a process. The decades of database engineering that converged on this shape converged on it for reasons that apply to us unchanged.

What is genuinely ours is the object of the query. A conventional database reads rows that describe a business. Gleamalog reads rows that describe an agent, or a fleet of them, and because WunderOS is substrate-recursive, rows that describe the substrate that describes the agent. Customer agent state is stored as Pentads by the same mechanism that stores anything else, so the question “what did this agent believe when it acted” is not a special introspection API but an ordinary query with a temporal qualifier. Shadow Agents, the OTP-resident actor-twins (of CAs) that carry a customer’s policy and history alongside the live agent, are queryable on the same terms. There is no separate metadata plane. The read surface over the system is the read surface over the system’s own account of itself, and the fact that these are the same surface is what makes an audit tractable rather than archaeological.

2. By agents

Gleamalog is my second query language, the first was SPARQL, which I helped design, specify, and then build commercially at Stardog. No agents involved.

Gleamalog’s core semantics were internally-ratified in April of this year and the amendment chain that carried it to aggregation, WCOJ, provenance, and metric temporal logic closed in July. Eleven weeks. The evaluator is roughly sixteen thousand lines of Gleam and twenty-five hundred of Zig, with just over six hundred tests. It was built by agents, under my direction, with me reviewing and signing the architectural decisions and the agents doing most of the rest.

SPARQL took about four years, depending on how you look at it. A perverse comparison but it’s also telling. The comparison is about cycle time. Design, implement, measure, revise is the loop that improves a language, and in the SPARQL era it ran at the speed of a mailing-list thread and a quarterly face-to-face. It now runs at the speed of a ratified decision and a fleet of agents implementing it in parallel against a property-test suite.

Gleamalog is the read surface over agent state, and it was written by the agents whose state it reads. The evaluator can be asked what its authors did while writing it, and it answers.

3. For agents

A language designed for agents that is unusable by people is a bad language, and one designed for people that agents use badly is a language whose principal consumer has been ignored. Gleamalog is designed primarily for agents and secondarily for people, and the priority is deliberate. Three properties follow: Gleamalog is to be flat, structured, concise. That is, Gleamalog is to be agent-friendly. The first two are supported by evidence that is less comfortable than it first appears.

Flat

Here is a whole Gleamalog program.

:mem(?hour, per, ?count) :- :mem(?event, at, ?stamp),
  ?hour ≔ ⊞⟦1h⟧(?stamp), ?count ≔ #(?event) ▷ ?hour.?

It reads facts of the form “event happened at timestamp,” buckets the timestamps into hours by a tumbling window, and counts events per hour. Three goals in the body, and they are peers. The source atom, the window, and the aggregate sit at the same level, and none is nested inside another. The window binds ?hour and the aggregate reads it, so there is a dependency, but the dependency is expressed by shared variable rather than by containment.

Compare what SQL requires: a subquery to compute the bucket, a GROUP BY that refers to it, and an outer SELECT that projects the count, with the nesting carrying information that the variable bindings could have carried by themselves. Compare what a nested-JSON query DSL requires, which is often a far worse thing. The flat form is not shorter by accident. It is shorter because containment was doing work that names already do, and removing it removes the work.

Flatness is a constraint on the surface and it costs something. First and Last need an ordering key distinct from the aggregated value, or they collapse into Min and Max, so the key rides inside the constructor. Multi-key GROUP BY is available only in the fused form, because the binary substrate has one group slot. These are the prices of refusing to nest, and they are paid at the parser and in the surface rather than passed to the reader.

There is a second reason for flatness, which is empirical and which I did not have when the design was made. Constrained decoding into structured formats degrades LLM reasoning, and the effect is real and large. Tam and colleagues found that requiring JSON or XML output significantly reduced reasoning accuracy across models, worsening as the format constraint tightened (arxiv:2408.02442). The natural inference, that agents should therefore emit prose, is the wrong one, and the paper that explains why is Capacity, Not Format (arxiv:2606.09410): the penalty comes from premature serialization, from forcing schema-compliant tokens out before the reasoning that should determine them has finished. Reason first and serialize after, and most of the lost accuracy returns.

A query language is emitted after reasoning concludes. That is what a query is: the terminal act of having decided what to ask. And a flat body of peer goals is the shallowest serialization a query language admits, so whatever premature- serialization tax remains is minimized by construction rather than by convention. The flatness commitment was made for the parser, and it is also a mitigation for a measured failure mode in the consumer.

The same discipline governs the window glyphs. Tumbling and sliding are distinct glyphs, ⊞ and ◷, rather than one glyph whose behavior depends on which optional parameter is present. A model that must infer semantics from the absence of a binding will infer wrongly, and it will do so silently, and the silence is the problem. No as. No braces. No presence-based footguns.

Structured

The claim that agents do better with structured data than with natural language is widely made and is true only once the question is asked precisely, because the literature divides along an axis the slogan ignores. That axis is input against output.

On what a model reads, structure helps. Well-structured input improved GPT-4.1 exact-match accuracy by roughly twenty points over poorly-structured input on legal document understanding (arxiv:2505.12837), and prompt format is a first-order variable in performance generally (arxiv:2411.10541). On what a model writes, structure hurts, and the strongest result cuts directly against the slogan. Johnson, Pain, and West replaced JSON tool-calling with natural-language tool selection and measured an 18.4 percentage-point improvement in tool-calling accuracy and a seventy percent reduction in output variance, across ten models and sixty-four hundred trials, with open-weight models overtaking flagship closed-weight ones (arxiv:2510.14453).

A query language lives on both sides of that axis. Gleamalog results come back as Pentad rows, which is context, where structure helps. Queries go out as Gleamalog clauses, which is generation, where structure is the thing that hurt. Anyone asserting that agents prefer structure, without saying which side they mean, has asserted something the evidence contradicts half of.

Our position is this. The generation penalty is a penalty on serializing early, not on machine-readable form, and a query is late by definition. The residual penalty is bounded by keeping the serialization shallow, which is what flatness buys. The reading benefit is unqualified and we take it whole. And the alternative that the Natural Language Tools result recommends, letting the model speak freely and translating afterward, purchases its accuracy with a translator that must itself be correct, which relocates the problem into a component with no formal semantics and no way to fail loudly.

We would rather pay a bounded tax on emission than admit an unbounded one on interpretation. The eighteen points are a real number and the judgment could go the other way. The experiment that would settle it, which we have not run, is Gleamalog emission against natural-language-then-translate on the same corpus.

The deeper reason for structure has nothing to do with model behavior. A prose description of a fact can be read once. A structured fact can be queried forever, joined against, given provenance, and replayed as of a past instant. Prose locks meaning into a particular reader’s interpretation. Rows expose it to mechanical access. Even if the measurements ran the other way, the asymmetry would remain, because it is an asymmetry about what representations permit rather than about what models prefer.

Concise

Concision is not brevity. Concision preserves precision while brevity discards it. Σ is one codepoint and carries what sum carries. ⊓ and ⊔ are meet and join, which is what min and max are, and the glyphs say so where the words do not. # is cardinality. ▷ groups. ≔ binds. ⟦0, 30d⟧ is a metric interval and is visually distinct from a list literal, which means the parser never disambiguates and neither does the reader. ~ is an approximate probe into a vector index and ⋈ is a scan over a proximity graph, and the two get different sigils because their cardinality regimes differ and a reader should see the difference before parsing the atom.

The commitment has a cost and the cost lands in the lexer. Σ and μ are letters. Unicode says so, and any tokenizer that matches identifiers before symbols will swallow them into the atom that follows. The glyph rules must precede the atom matcher, which is a constraint on rule ordering that a purely ASCII language never has to think about. We pay it once, in one file, and every query is a few tokens shorter forever.

Frugality is a form of life. So, too, is prudence. Every glyph has an ASCII alternative, accepted by the parser and emitted for humans and for environments where the codepoints are inconvenient. :eventually[0, 30d] is the same clause as ◇⟦0, 30d⟧.

This is Postel’s law applied to the symbol layer: emit the dense form for agents, accept the wide form from anyone.

4. The semantics of Gleamalog

What follows is the compressed account. Gleamalog is a classical Datalog with stratified recursion, three-valued negation under approximation fixpoint theory, a full aggregation family, worst-case-optimal joins on cyclic bodies, semiring provenance, and a metric temporal extension. Each of these interacts with the others, and the interaction-joints are where the design is.

Evaluation is semi-naive with k-position delta. For a rule with k positive body atoms, each fixpoint iteration runs k variants. Variant i takes the delta relation at position i, the full materialization at positions j < i, and the pre-iteration snapshot at positions j > i. Every derivation that uses at least one newly-derived fact is produced exactly once, and no derivation that uses none is produced at all. Empty deltas short-circuit their variant. This is standard and we implement it fresh rather than adopting it.

Stratification is Tarjan SCC with greedy strata, over three edge polarities. The rule dependency graph carries labelled edges, and the label determines a bump. A positive edge bumps by zero, so the head may share a stratum with its body. A negative edge bumps by one. An aggregate edge also bumps by one. The invariants are that a positive edge gives stratum(head) ≥ stratum(body) and that a negative or aggregate edge gives strict inequality. Tarjan finds the strongly connected components; any non-positive edge inside an SCC is a cycle through negation or aggregation and is rejected with a typed error rather than evaluated to a fixpoint that does not exist.

The third polarity is the load-bearing decision. Aggregation could have been a separate machine, and in many systems it is. Making the aggregate edge a polarity means aggregation rides the stratifier that negation already needed, and an aggregate becomes what negation already was: a computation over a relation that must be complete before the computation may begin. This is why aggregation landed in Gleamalog as an amendment rather than a successor design. It added a constructor to an enum and a case to a bump function.

Not every body goal forms an edge. Comparison, probe, graph-scan, window, and metric-goal atoms form none, because none of them depends on a lower relation being complete. They are filters and generators, evaluated within the stratum that contains them. Getting this wrong in the permissive direction, by giving every goal an edge, would stratify programs that need not be stratified and reject programs that are fine.

Safety is two-bound-set. A variable is body_bound if a positive body atom binds it, checked sequentially so that a constraint may consume a binding produced to its left. A variable is head_bound if it is body_bound or is the result of an arithmetic or aggregate computation. Head safety is checked against head_bound; negation and constraint safety against body_bound.

The asymmetry is not a stylistic choice. A negated atom whose variables are not bound by a positive atom is vacuously satisfiable, and an unbound negation in an aggregate body will silently produce the wrong number rather than fail. The aggregate surface therefore adds source-binding checks of its own: the aggregated argument, every group-by key, every order-by key, and every variable of a negated atom must be bound by a positive source. Every variable in the head must be either the aggregate output or a group-by key. These checks exist because the failure they prevent is a plausible number rather than an error.

Negation is three-valued, under approximation fixpoint theory. Stratified negation is the special case, not the ceiling. AFT gives a single three-valued immediate-consequence operator that generalizes stratified, well-founded, stable-model, and Kripke-Kleene semantics, and it handles retraction and temporal operators without the ad-hoc machinery each would otherwise require. The reference is Pollaci and colleagues on fixpoint semantics for DatalogMTL with negation (arxiv:2601.03841). The three values are packed one to a byte, 00 false, 01 undef, 10 true, at a measured 1.7× memory cost over a Boolean encoding, which fits inside the 256KB-aligned slab budget. The lattice operations are branch-free @Vector(64, u8) in Zig.

There is a complication. Where an aggregate ranges over a join containing a negated atom, the adopted semantics is stratified closed-world and two-valued, not three-valued. The reason is structural. The stratifier rejects negation and aggregation through recursion, so every program it admits is locally stratified, and a locally stratified program has a two-valued perfect model. The three-valued machinery is unreachable on that path, and pretending otherwise would be decoration. It is reachable on the metric-temporal path, where undef means a fact has not yet landed on the transaction axis, and there it does real work.

Joins are sorted-list merges, and never hash. Hash-keyed joins iterate buckets in an order that depends on allocation, and a system committed to deterministic replay cannot permit it. Two-way sort-merge serves linear chain bodies. Cyclic bodies, triangles and k-cliques, cannot be linearized into a chain at all, and before worst-case-optimal joins landed such rules simply failed to compile. They now compile to a leapfrog trie-join, a k-way intersection of sorted lists with rotating seek and galloping search, over the CSR and CSC indices the substrate already maintains, driven by a variable elimination order that must be connex, meaning every non-root variable has an already-bound neighbor. The connex requirement is a correctness property rather than a performance knob, since first-appearance order breaks on cycles with pendant vertices.

The unifying observation is that leapfrog is the k-way generalization of sort-merge. Adopting worst-case-optimal joins therefore cost nothing in determinism, because the determinism came from sortedness and sortedness is what leapfrog consumes. Nothing about the commitment to replayability had to be revisited. The AGM bound explains why it matters: on a four-clique over twenty-two vertices and one hundred eighty-two edges, the chained plan materializes 15,494 intermediate rows to emit 104, a factor of 149, and the worst-case-optimal plan emits the same rows without ever building the intermediates. Recursion into a cyclic body is a shape agents produce constantly, because “find me the mutually-referencing cluster” is a natural thing to want and an unnatural thing to write as a chain.

Provenance is a semiring, and the semiring class is constrained. Green and Tannen showed that annotating facts with elements of a commutative semiring and propagating through join by product and union by sum recovers lineage, trust, multiplicity, and probability as instances of one construction. Gleamalog requires its semiring to be ordered, so the fixpoint is monotone; ω-continuous, so the fixpoint converges; and to send undefined to the semiring’s zero, so that an undecided fact contributes nothing rather than optimistically contributing something (arxiv:2403.12436). Provenance is gated: when origins are off, the paths are not taken and the default costs nothing.

Aggregation over provenance has a subtlety that is easy to miss. Sum and count are not semiring homomorphisms, and the general treatment requires a semimodule over the semiring rather than the semiring alone, which is the Amsterdamer, Deutch, and Tannen construction. Gleamalog escapes it for the case it needs. For the why-provenance semiring, where elements are sets of contributing facts and both sum and product are set union, the contributor set of an aggregate is the union of its inputs’ contributor sets, and this holds regardless of which aggregate function is applied. Count, sum, median, and string-agg take one code path. The escape is available only because the question is which facts contributed and not how much each contributed. Asking the second question, which is how-provenance and needs the polynomial semiring, would put the semimodule back. We do not ask it. Correspondingly, Min and Max return the whole group’s read set rather than the argument that attained the extremum, because the argmin is where-provenance and is out of scope.

The aggregate family is three families. The streaming scalars, Count, Sum, Min, Max, and Avg, fold in constant space. The holistic statistics, Median, Stddev, and Percentile, need the full sorted multiset and break the factorization that lets the others reduce per group in constant space. The collection aggregates, StringAgg, ArrayAgg, First, and Last, reduce over arbitrary strings. Rational results are fixed-point, scaled by a thousand and truncated toward zero, because floating-point summation is not associative and a replayable system cannot have an aggregate whose value depends on the order in which a set was traversed. Percentile interpolates by the R-7 convention, the one NumPy and R and Excel agree on, computed in integers. Stddev is population and not sample, because a Datalog group is the whole population and Bessel’s correction would be answering a question nobody asked. Since a group is a set and therefore unordered, StringAgg and ArrayAgg sort ascending before joining, and First and Last require an explicit order key.

Every one of these conventions exists to make the same query return the same bytes on the same input, always.

Windows are goals, not clauses. A tumbling window, ⊞⟦1h⟧(?stamp), is a pure function of the timestamp: the bucket is the floor of the timestamp divided by the width, and no clock is consulted. A sliding window, ◷⟦24h⟧(?stamp), is anchored at now and is therefore a filter that requires the evaluation clock to be injected rather than sampled, so that a replay of the query against the same recorded clock produces the same answer. Neither forms a stratifier edge.

Metric temporal logic is treated in great detail at PLRN-018 and I will not repeat it. The relevant fact for this note is that the eight temporal operators carry an optional metric interval, that the interval binds both the transaction-time and valid-time axes where existential, and that the third truth value is what keeps a late-arriving fact from being reported as a false one. The temporal extension is the reason AFT was chosen over stratified negation as the ceiling, and having chosen it there we get it everywhere.

Magic sets are deferred, and the argument is from silence. A survey of one hundred nineteen papers on modern Datalog evaluation turned up no magic-set work, which we took as evidence that the technique has been superseded rather than that it was forgotten. Goal-directed evaluation is what magic sets buy, and the vector-symbolic navigator is already goal-directed for the queries that want it. An argument from silence is a weak argument. It is strong enough to justify not building something, and would not be strong enough to justify building it.

5. Related notes

Worked examples of every construction in this note, run against a real mortgage-agent audit trail, are in the companion casebook, PLRN-019A.

The Pentad and the case for glyph-dense structured representation are PLRN-003. Deterministic arithmetic, which is why the joins are sorted and the aggregates are fixed-point, is PLRN-002. Provenance-by-construction is PLRN-006 and append-only retraction is PLRN-007; together they are why the provenance semiring must send undefined to zero. Substrate recursion, which is why querying agent state and querying the substrate are the same act, is PLRN-005. The metric temporal surface is PLRN-018.

The classical results are Green, Karvounarakis, and Tannen on provenance semirings (PODS 2007); Amsterdamer, Deutch, and Tannen on provenance for aggregate queries (PODS 2011); Ngo, Porat, Ré, and Rudra on worst-case-optimal joins (PODS 2012); Veldhuizen on leapfrog trie-join (ICDT 2014); and Tarjan on strongly connected components (SICOMP 1972). The temporal semantics follow Pollaci and colleagues (arxiv:2601.03841) and the semiring evaluation strategy follows arxiv:2403.12436. The evidence on structured and unstructured representation is arxiv:2408.02442, arxiv:2606.09410, arxiv:2505.12837, arxiv:2411.10541, and, as the strongest statement of the contrary case, arxiv:2510.14453. The landscape of agents over structured and unstructured data is surveyed at arxiv:2509.23988.

A note on method

Written in conversation with Claude Opus 4.8 (Anthropic) as structured interlocutor. Gleamalog itself was implemented by agents under my direction. The motives, ideas, claims, framing, architectural commitments and taste, or lack thereof, are mine.

Kendall Clark · k@pentad.ai
Great Falls, Virginia
10 July 2026