About

Kleene is a harness that runs recursive language-model workflows written in SQL. The model writes CallSQL; the engine parses it, annotates every operator with the calls it implies, prices the plan against a budget, executes it with memoised and concurrent calls, persists tables, memo and trace in DuckDB, and shows it all in a terminal UI. It is a Rust workspace of twelve crates, model-agnostic, with no SDK and no gateway required, released under the MIT licence. It is built by Marcus Elwin and started life as Callgebra, "call algebra", before taking its present name; the dialect kept its own name, CallSQL, because the SQL is where the calls are.

man kleene

Why "Kleene"

Stephen Cole Kleene (1909–1994) gave computation three of its load-bearing ideas, and this project leans on all three.

The Kleene star turns "one step" into "any number of steps". Kleene introduced a* in 1951 to describe the "regular events" a McCulloch–Pitts nerve net can recognise [1]; it is the closure of a under repetition, and it is exactly what a recursive CTE computes when it runs a term to its fixpoint. Aho and Ullman later showed that relational algebra needs precisely such a least-fixpoint operator to express transitive closure at all [4], which is why CallSQL has WITH RECURSIVE.
The Kleene fixed-point theorem says how to reach that closure: start from nothing and apply the step until nothing changes. The construction is the "first recursion theorem" of Introduction to Metamathematics [2], and in its database form it is semi-naive evaluation [5]: each round sees only the previous round's delta, which is how the executor runs a recursive term and where a LIMIT k inside it becomes a beam.
The recursion theorem shows a program can refer to itself without paradox. Kleene proved it in 1938 as a lemma about ordinal notations [3]; it is what a session does when it opens a child session with rlm(...), the same loop one level deeper with a slice of the budget.

There is a fourth, smaller debt. The same 1938 paper introduced a three-valued logic, now called strong Kleene logic or K₃, to reason about predicates that may not terminate: true, false, and undefined, where false AND undefined is still false. SQL's NULL follows those tables, with unknown in the third seat. CallSQL inherits them, and the planner relies on them: a conjunction can be evaluated cheap-conjunct-first and stop as soon as one side is false, which is the whole trick behind putting a cheap proxy predicate in front of an expensive model call.

That is this project in three theorems and a truth table. A model call is a step; SQL gives it joins, predicates and aggregation; recursion with a beam gives it search; the planner prices the closure before it is computed. The engine is named for the mathematician who showed that closure is a thing you can compute.

Stephen Cole Kleene, 1909–1994

kleene trace "SELECT year, event FROM biography ORDER BY year"

year │ event ────────┼────────────────────────────────────────────────────────────────────── 1909 │ Born 5 January in Hartford, Connecticut. 1930 │ Bachelor's degree from Amherst College. 1934 │ PhD at Princeton under Alonzo Church; with Church and J. B. Rosser he │ works out the lambda calculus and shows which functions it can express. 1935 │ Joins the University of Wisconsin–Madison, where he stays for his career. 1936 │ "General recursive functions of natural numbers": the normal form theorem │ and the T predicate; the definition of computability that Church's thesis │ names. 1938 │ "On notation for ordinal numbers": the recursion theorem, and the │ three-valued logic that SQL's NULL would later follow. 1943 │ "Recursive predicates and quantifiers": the arithmetical hierarchy. │ Serves as a navigation instructor in the US Naval Reserve during the war. 1945 │ Realizability: a computational reading of intuitionistic proofs. 1951 │ "Representation of events in nerve nets and finite automata" (RAND, printed │ in Automata Studies, 1956): regular expressions, the star, and Kleene's │ theorem that they recognise exactly what finite automata do. 1952 │ Introduction to Metamathematics, the textbook that taught a generation │ recursion theory; still in print. 1969 │ Dean of the College of Letters and Science at Wisconsin, until 1974. 1990 │ National Medal of Science. 1994 │ Died 25 January in Madison, Wisconsin. 13 rows

Beyond the three theorems above, his name is on the Kleene algebra (the algebra of regular sets, later axiomatised by Kozen), the Kleene hierarchy, the Church–Kleene ordinal, the Kleene–Rosser paradox that sank the first version of the lambda calculus, and the Kleene plus. The lambda calculus itself, the "Church" in Church's thesis, and the word regular for the sets a finite automaton recognises all pass through his desk. It is a good name for an engine whose job is to compute closures of a step, price them, and stop when nothing changes.

What the engine does with the name

Kleene's idea	Where it is in the engine
Star, closure under repetition	`WITH RECURSIVE` run to a fixpoint by semi-naive evaluation
Least fixed point from the bottom up	each round sees only the last round's delta; `ORDER BY ... LIMIT k` in the term is a beam
Recursion theorem, self-reference	`rlm(...)` and `spawn(...)` open a child session: the same loop with a budget slice
Strong three-valued logic	SQL `NULL` semantics; cheap-conjunct-first short-circuiting the planner relies on
Regular expressions	the `grep` table function the model reads its workspace with

References

S. C. Kleene, "Representation of Events in Nerve Nets and Finite Automata", RAND RM-704 (1951); in Automata Studies, Princeton University Press, 1956, pp. 3–41.
S. C. Kleene, Introduction to Metamathematics, North-Holland, 1952, §66 (the first recursion theorem; the least-fixed-point construction) and §64 (the three-valued logic).
S. C. Kleene, "On Notation for Ordinal Numbers", Journal of Symbolic Logic 3(4), 1938, pp. 150–155 (the second recursion theorem; the three-valued tables).
A. V. Aho and J. D. Ullman, "Universality of Data Retrieval Languages", POPL '79, pp. 110–119 (relational algebra plus a least fixpoint).
F. Bancilhon and R. Ramakrishnan, "An Amateur's Introduction to Recursive Query Processing Strategies", SIGMOD '86, pp. 16–52 (semi-naive evaluation).
S. C. Kleene, "General Recursive Functions of Natural Numbers", Mathematische Annalen 112, 1936, pp. 727–742.
D. Kozen, "A Completeness Theorem for Kleene Algebras and the Algebra of Regular Events", Information and Computation 110(2), 1994, pp. 366–390.

The research the design draws on beyond Kleene, from recursive language models to SQL as a model interface and the complexity results the planner relies on, is collected in the research digest.