Chapter 2 — Two Winters, Three Bets

Programming paradigms rarely die of being wrong. They die of being early, of being oversold, or of being welded to the wrong hardware — and logic programming managed all three, twice. This chapter is the honest account I promised: where the idea came from, what was actually bet on it, why the bets failed, and why the failures tell you surprisingly little about the idea. If you’ve ever dismissed this field with “wasn’t that the thing from the eighties?”, this chapter is for you, because yes — it was the thing from the eighties, and the eighties are precisely what needs explaining.

1965: inference becomes mechanical

The story starts with a theorem about theorems. In January 1965, J. A. Robinson published “A Machine-Oriented Logic Based on the Resolution Principle” — a demonstration that logical deduction could be reduced to a single mechanical rule, resolution, simple enough for a computer to apply blindly and complete enough that anything provable could, in principle, be reached by it. Before Robinson, formal logic was something mathematicians did to programs from the outside. After him, deduction was an algorithm.

It is hard to overstate what this seemed to promise. If deduction is mechanical, then knowledge plus compute equals answers: state what you know, ask what you want, let the machine grind out what follows. Every system in this book — including the one in the repository this text ships with — is downstream of that promise. So, in a real sense, is every SQL query you have ever written.

The catch surfaced immediately, and it has a name you know from your own work: combinatorial explosion. Resolution is complete the way brute force is complete. Blind search through the space of derivations drowns in itself long before it proves anything interesting, and by the early seventies it was clear that “logic plus compute” was not enough; you needed logic plus compute plus control over where the search goes.

Bet one: logic as a programming language

The response was one of the great moves in the history of programming languages. In Marseille around 1972, Alain Colmerauer and Philippe Roussel built a system for processing natural language; in Edinburgh, Robert Kowalski was developing the theoretical reading that made it a language. Their converged insight: don’t search blindly — restrict attention to rules of the form “conclusion if conditions” (Horn clauses, though we won’t need the term again), read them procedurally — to prove the conclusion, prove the conditions, left to right — and suddenly resolution stops being a search through chaos and becomes something a programmer can steer. They called the system Prolog, programmation en logique. Roussel wrote the first interpreter in ALGOL-W; within a decade there were dozens.

Kowalski crystallized the philosophy in a 1979 paper whose title is the cleanest slogan the field ever produced: “Algorithm = Logic + Control.” Every algorithm decomposes into a logic component — what the problem is — and a control component — how to search for the answer. Separate them, and you can improve the how without touching the what. It is the exact bargain I offered you in chapter 1, and it was on the table before most of this book’s readers were writing code.

And Prolog worked. On the hardware of its day it worked startlingly well — David Warren’s 1983 abstract machine design compiled it tightly enough to embarrass the skeptics — and through the early 1980s Prolog was, alongside Lisp, one of the two serious languages of artificial intelligence. The what-not-how dream had a working vehicle. The vehicle had a flaw, and the flaw was structural: Prolog achieved its efficiency by fusing logic and control back together — clause order, goal order, and the cut all make the search procedure part of the program’s meaning. Chapter 4 dissects that fusion with a running example; for now, note only the irony. The language born from “Algorithm = Logic + Control” shipped the two welded.

Bet two: a superpower buys the hardware

By 1982 the idea had enough momentum to attract the largest wager ever placed on it — arguably the largest state wager ever placed on a single programming paradigm. Japan’s Ministry of International Trade and Industry founded ICOT, the Institute for New Generation Computer Technology, under Kazuhiro Fuchi, and launched the Fifth Generation Computer Systems project: a ten-year national program to leapfrog the American computer industry not by building faster conventional machines but by building a different kind of machine — one whose native operation was logical inference. Logic programming would be the machine language; performance would be measured not in instructions per second but in logical inferences per second; and the hardware — Parallel Inference Machines, programmed in a concurrent logic language called KL1 — would deliver the parallelism that sequential Prolog could not. Roughly ¥54 billion of government money — about $400 million, real money in 1982 — went in over the decade. Western governments, badly spooked, answered with crash programs of their own: DARPA’s Strategic Computing Initiative alone outspent FGCS, though it spread the money across AI broadly rather than one paradigm.

If you have never heard of any machine that came out of this, that is the outcome. The project ran its decade, built its prototypes — five PIM machines, a working KL1 toolchain, a research community — declared its results, and dissolved into a short follow-on; ICOT closed its doors in 1995. No industry adopted the machines. No successor generation was built.

The standard postmortem says Moore’s law killed it, and as far as it goes, that’s true: commodity microprocessors were doubling in speed on a rhythm no bespoke architecture could match. By 1992, an inference machine painstakingly designed for logic was slower than a general-purpose chip you could buy at retail — the specialized hardware was obsolete the day it worked. But hold the postmortem to the same standard as chapter 4’s autopsies and two deeper causes surface. First, FGCS bet on the wrong branch of the paradigm: KL1 was a concurrent dialect of the Prolog line — search-shaped, process-shaped — and extracting massive parallelism from it meant fighting the model, not riding it. The set-oriented, fixpoint-shaped branch of logic programming that is natively parallel existed by then only as database theory (we’re coming to it). Second, FGCS needed hardware built for logic, on a paradigm’s budget. What the field actually required — as the next forty years demonstrated — was hardware built for someone else’s problem at someone else’s scale, that logic could ride for free.

Understand that and you understand why this book exists. FGCS was right that logic programming’s future was massively parallel hardware. It was wrong about who would pay for the hardware, and it was three decades early. The congregation that waited for the messiah dispersed a generation before he arrived.

The winter

The collapse was general, and it was not FGCS’s fault alone. The specialized Lisp-machine market imploded in 1987, undercut by exactly the same commodity workstations. The corporate expert-system wave of the mid-eighties (chapter 4 examines the technology; chapter 2 only notes the business) crested and broke as the maintenance bills came due. FGCS wound down in 1992 with its goals visibly unmet. The years from roughly 1987 to 1993 are now called the second AI winter, and logic programming — which had let itself be marketed as the substrate of the coming machine intelligence — froze with the rest of the field. Funding stopped; research groups dispersed; “logic programming” became the phrase you removed from your grant proposal.

That is the stigma this book swims against, so let me be precise about what actually froze. What failed was a positioning: logic programming as the royal road to artificial intelligence, and as a reason to build exotic hardware. What never failed — what was barely even tested — was the narrower, humbler claim of chapter 1: that rules with a fixpoint semantics are a better way to write the rule-shaped parts of ordinary software. The winter buried both claims in one grave. Only one of them was dead.

Meanwhile, in the database department

Because here is the part the winter narrative always omits: through the entire boom, collapse, and freeze, a different community was quietly working on the other branch — the one FGCS didn’t bet on.

Database theorists had been circling logic-as-queries since a 1977 workshop on logic and databases; sometime in the mid-eighties the fragment they cared about acquired a name — Datalog, coined by David Maier — and through the late eighties it became the most-studied object in database theory. Datalog is what you met in chapter 1: rules over finite data, no term construction, guaranteed termination, order-independent fixpoint semantics. Perfect parallelizability sat in the definitions, untouched, because in 1988 nobody had parallel hardware worth the trouble. The running joke — Datalog as the field with a thousand theorems and no applications — had real teeth; the theory outran any deployment by a decade. But the theorems were the point. The evaluation algorithms (chapter 1’s delta trick among them), the negation semantics (chapter 6 uses it), the complexity bounds — the entire load-bearing frame of this book’s Part II was poured, as theory, during the winter, by people the AI collapse never touched.

The winter years kept producing at the semantic frontier too. Stable models — the meaning of unrestricted negation, the foundation of chapter 8’s @asp layer — date to Gelfond and Lifschitz, 1988: the paradigm’s deepest semantic result, published into the teeth of the collapse. Constraint logic programming was laid out by Jaffar and Lassez in 1987. The paradigm’s obituary and its best theorems share a decade.

The quiet revival

The thaw, when it came, came from engineering, and it came Datalog-shaped. In 2004, Whaley and Lam showed that a hard, valuable program-analysis problem — context-sensitive pointer analysis for real Java programs — could be specified in Datalog and solved efficiently, the specification an order of magnitude smaller than the hand-coded analyzers it replaced. Rules about code, deriving facts about code: the sanctions problem, for compilers. A research thread became an industry. Semmle (an Oxford spinout, 2006) built a company on a Datalog dialect for querying codebases; GitHub bought it in 2019, and its engine now scans code at world scale as CodeQL. Oracle Labs, needing to analyze enormous codebases, built the open-source Soufflé engine (2013–2016) — the same engine this book’s reference implementation tests itself against. LogicBlox built a commercial Datalog platform whose retail-planning deployments passed through Predictix into Infor; its lineage continues today at RelationalAI. Datomic (2012) put a Datalog query language at the heart of a production database and ended up owned by a bank running it for a hundred million customers.

Notice three things about this list. Every entry is from the fixpoint branch, not the search branch — the revival vindicated the wing of the family that the winter’s flagship bet passed over. Every entry survived by not calling itself logic programming — more on that camouflage in the next chapter. And every entry runs on stock hardware: the revival asked nothing of the machine that the machine wasn’t already selling. The paradigm came back exactly where its guarantees — termination, order-independence, analyzability — were worth money, and nowhere else.

Bet three

Which brings us to now, and to the wager this book is a brief for. Two things have changed since 1992, and neither was done for logic programming’s benefit — which is precisely why they can be trusted.

The first: the parallel inference machine got built. Not by a ministry, and not for inference — the deep-learning boom filled every datacenter and half the world’s desks with GPUs: massively parallel, memory-rich, commodity-priced, improving on a curve. FGCS’s hardware thesis, minus FGCS’s fatal clause. No one has to build hardware for the paradigm anymore; the paradigm has to meet hardware that already exists — and the fixpoint branch, unlike the search branch, meets it natively. (This is no longer hypothetical even in research terms: the first serious GPU Datalog engines have appeared in the last two years. Chapter 5 places them on the map, and chapter 10 takes up the architecture question in earnest.)

The second: the verification economy inverted. LLMs now write code — fluently, cheaply, and under no oath. When code is expensive to write, you optimize languages for writing it; that was every language war of the last fifty years. When code is cheap to generate and the scarce resource is confidence in what got generated, the language’s job flips: be easy to check — by machines, structurally, and by humans, readably. Chapter 4 grades the old logic languages on that axis and they fail it, badly, for reasons the winter never touched. But the paradigm — rules with order-independent meaning, answers that carry derivations — is the strongest candidate shape for a check-first language that we have. Fifty years of work on “how machines can trust conclusions” was waiting for a world with an oversupply of plausible text. That world arrived.

So the third bet is not the first bet retried — not logic as universal intelligence. And it is not the second retried — not bespoke silicon. It is smaller and harder-nosed than either: the rule-shaped fraction of real software, written as rules, checked as logic, running on hardware someone else already paid for, generated increasingly by models whose output nobody should trust unverified. The rest of this book cashes that sentence out. First, though — chapter 3 — let me show you how much of the bet is already, quietly, in production.