Forward Chaining: Rule Engines

in progressThis lesson is still being built - content, demos, and checkpoints may change before release.

Forward chaining

Loading interactive demo…

The graph is the knowledge base: symbols as circles, rules as small nodes with an edge from each premise and one to the conclusion, laid out left to right by how many firings away from the given facts they are. Below, the agenda holds the facts waiting to be processed and the known strip those already processed. The ringed symbol is the goal.Take the tour, or press and explore. Legend:

The panel beside the stage is the real ForwardChainer class from the published library executing in your browser, with the current line highlighted.

A known fact, and a rule that has fired with its edges.
A fact on the agenda, derived or given but not yet processed.
The fact being processed or the rule firing.
The goal, ringed, and the tapped node with its edges.
A symbol nothing has derived, hollow.

known counts the facts processed out of every symbol in the base, agenda the facts waiting, fired the rules fired out of all of them, goal the goal and whether it was reached. Tap a node to light its edges.

The code panel shows bare executable code by default. The bar above it names the file (hover the name for the full published path); options holds the toggles: comments, the tracer instrumentation that produces this visualization, and verbose names for the terse identifiers (display only: the default is the byte-exact published file). The view switch adds plain-English narration: both interleaves it with the code, pseudo shows only the pseudocode. hide code collapses the panel; the rail it leaves behind brings it back.

Keys: Space play/pause · ←/→ step · Home/End jump · R reset · F fullscreen · G guided tour

Horn clauses. A definite clause is an implication from a conjunction of symbols to one symbol, $p_1 \wedge \dots \wedge p_k \to q$ ; a fact is the case $k = 0$ . As a clause it is $\neg p_1 \vee \dots \vee \neg p_k \vee q$ , with exactly one positive literal, which is what Horn means. Most of what a rule system or a database wants to say fits the shape, and the shape is what makes the reasoning cheap.

Forward chaining. Keep an agenda of facts to process and, for each rule, a count of premises not yet known. Take a fact off the agenda, mark it known, and decrement the count of every rule that uses it; a rule whose count reaches zero fires, and its conclusion joins the agenda. Stop when the goal is known, or when the agenda is empty. Each fact is processed once and each rule fires at most once, so the run is $O(n)$ in the size of the base.

Sound and complete. Every derived fact follows from the base by modus ponens, so the method is sound. It is also complete for Horn bases: at the fixpoint, make every known symbol true and every other symbol false; every rule is then satisfied (a rule with all premises true has fired), so this is a model of the base, and the goal is false in it. Hence an unreached goal is not entailed. For general clauses, with several positive literals, no such model is guaranteed, and entailment becomes the NP-hard problem of the SAT lesson.

Data-driven versus goal-driven. Forward chaining derives everything the facts imply, whether or not it bears on the goal: the diagnosis base derives rest while looking for doctor. Backward chaining, the logic programming lesson, starts from the goal and works back to the facts, deriving only what the goal needs. Rule engines use the first, since new facts keep arriving; Prolog uses the second, since a query is a goal.

Scale. A base with thousands of rules cannot rescan them per fact. The Rete network indexes rules by the facts they wait for, so a new fact touches only the rules that mention it: the counts here, made into a data structure.

Emil Post's 1943 production systems rewrote strings by rules, and Allen Newell and Herbert Simon made rules of the form "if these facts then that" the basis of their models of human problem solving. The engines that ran such rules at scale, OPS5 and its Rete network, matched thousands of rules against thousands of facts by remembering partial matches instead of rescanning, and the expert systems of the 1980s were built on them. The logic beneath is Horn clauses, and linear-time entailment for them is why rule engines and Datalog databases can afford to derive everything.

1943Emil Post - Defines production systems, rules that rewrite strings, and shows they can compute anything a Turing machine can.source
1972Allen Newell and Herbert Simon - 'Human Problem Solving' models thinking as production rules firing on a working memory, the architecture of later cognitive models.source
1979Charles Forgy - The Rete algorithm matches many rules against many facts by keeping a network of partial matches, so a new fact costs only the rules it touches.source
1980John McDermott - R1, later XCON, configures DEC's VAX computers from thousands of rules, the first expert system in daily commercial use.source
1984William Dowling and Jean Gallier - Give the linear-time algorithm for Horn satisfiability, the counts of unknown premises that this lesson's chainer keeps.source

Used today

Business rule engines - Drools, CLIPS, and their kin run forward chaining over facts in working memory; pricing, eligibility, and fraud rules are written as Horn clauses.
Datalog - A Datalog program is Horn rules over relations; evaluating it bottom-up is forward chaining, used for program analysis and graph queries.
Build systems and type checkers - Anything that derives all consequences of a set of facts until nothing changes, from a make dependency graph to a type inference pass, is chaining forward.

base

goal

agenda

known: 6 of 8
agenda: 0
fired: 3 of 4
goal: deployed: entailed

forward-chainer.ts

import type { Tracer } from "../trace";/** A definite clause: if every premise holds, the conclusion holds. */export interface HornRule {  premises: string[];  conclusion: string;}export interface HornKnowledgeBase {  facts: string[];  rules: HornRule[];}export type AgendaOrder = "fifo" | "lifo";export interface ChainResult {  /** The goal was derived; false when there was no goal or the facts ran out first. */  entailed: boolean;  /** Every symbol known at the end, in the order it became known. */  known: string[];  /** The rules fired, by index, in order. */  fired: number[];}/** * Forward chaining over propositional Horn clauses: start from the * given facts, and whenever every premise of a rule is known, its * conclusion becomes known too, until the goal turns up or nothing * new can be derived. Each rule keeps a count of premises still * unknown, so a fact is processed once and every rule fires at most * once: the whole run is linear in the size of the knowledge base, * where general propositional entailment is NP-hard. The agenda is a * queue (breadth first) or a stack (depth first); the facts derived * are the same either way, only the order differs. * * Time: O(n) in the total size of facts and rules. Space: O(n). */export class ForwardChainer {  constructor(    private readonly tracer?: Tracer,    private readonly order: AgendaOrder = "fifo",  ) {}  entails(kb: HornKnowledgeBase, goal: string | null): ChainResult {    const remaining = kb.rules.map((rule) => new Set(rule.premises).size);    const unknownPremises = kb.rules.map((rule) => new Set(rule.premises).size);    const known: string[] = [];    const fired: number[] = [];    const agenda: string[] = [];    const toProcess: string[] = [];    for (const fact of kb.facts) {      if (!agenda.includes(fact)) agenda.push(fact);      if (!toProcess.includes(fact)) toProcess.push(fact);      // ▸ a given fact joins the agenda      this.tracer?.emit("add-fact", { symbol: fact, agenda: [...agenda] });      this.tracer?.emit("add-fact", { symbol: fact, toProcess: [...toProcess] });    }    while (agenda.length > 0) {    while (toProcess.length > 0) {      const symbol = this.order === "fifo" ? agenda.shift()! : agenda.pop()!;      const symbol = this.order === "fifo" ? toProcess.shift()! : toProcess.pop()!;      if (known.includes(symbol)) continue;      known.push(symbol);      // ▸ take a fact off the agenda and mark it known      this.tracer?.emit("pop", { symbol, known: known.length, agenda: [...agenda] });      this.tracer?.emit("pop", { symbol, known: known.length, toProcess: [...toProcess] });      if (symbol === goal) {        // ▸ the goal is known: entailed        this.tracer?.emit("goal-reached", { goal, known: known.length, fired: fired.length });        return { entailed: true, known, fired };      }      kb.rules.forEach((rule, index) => {        if (!rule.premises.includes(symbol)) return;        remaining[index] = (remaining[index] ?? 0) - 1;        unknownPremises[index] = (unknownPremises[index] ?? 0) - 1;        if (remaining[index] !== 0) return;        if (unknownPremises[index] !== 0) return;        fired.push(index);        if (!known.includes(rule.conclusion) && !agenda.includes(rule.conclusion)) agenda.push(rule.conclusion);        if (!known.includes(rule.conclusion) && !toProcess.includes(rule.conclusion)) toProcess.push(rule.conclusion);        // ▸ every premise is known, so the conclusion joins the agenda        this.tracer?.emit("fire", { rule: index, premises: [...rule.premises], conclusion: rule.conclusion, agenda: [...agenda] });        this.tracer?.emit("fire", { rule: index, premises: [...rule.premises], conclusion: rule.conclusion, toProcess: [...toProcess] });      });    }    // ▸ the agenda is empty and nothing new can be derived    this.tracer?.emit("fixpoint", { goal, known: known.length, fired: fired.length, entailed: false });    return { entailed: false, known, fired };  }}

goal =: deployed
known =: 6
fired =: 3
entailed =: yes

Entailed: deployed follows from the facts, with 6 known and 3 rules fired.

import type { Tracer } from "../trace";/** A definite clause: if every premise holds, the conclusion holds. */export interface HornRule { premises: string[]; conclusion: string;}export interface HornKnowledgeBase { facts: string[]; rules: HornRule[];}export type AgendaOrder = "fifo" | "lifo";export interface ChainResult { /** The goal was derived; false when there was no goal or the facts ran out first. */ entailed: boolean; /** Every symbol known at the end, in the order it became known. */ known: string[]; /** The rules fired, by index, in order. */ fired: number[];}/** * Forward chaining over propositional Horn clauses: start from the * given facts, and whenever every premise of a rule is known, its * conclusion becomes known too, until the goal turns up or nothing * new can be derived. Each rule keeps a count of premises still * unknown, so a fact is processed once and every rule fires at most * once: the whole run is linear in the size of the knowledge base, * where general propositional entailment is NP-hard. The agenda is a * queue (breadth first) or a stack (depth first); the facts derived * are the same either way, only the order differs. * * Time: O(n) in the total size of facts and rules. Space: O(n). */export class ForwardChainer { constructor( private readonly tracer?: Tracer, private readonly order: AgendaOrder = "fifo", ) {} entails(kb: HornKnowledgeBase, goal: string | null): ChainResult { const remaining = kb.rules.map((rule) => new Set(rule.premises).size); const unknownPremises = kb.rules.map((rule) => new Set(rule.premises).size); const known: string[] = []; const fired: number[] = []; const agenda: string[] = []; const toProcess: string[] = []; for (const fact of kb.facts) { if (!agenda.includes(fact)) agenda.push(fact); if (!toProcess.includes(fact)) toProcess.push(fact); // ▸ a given fact joins the agenda this.tracer?.emit("add-fact", { symbol: fact, agenda: [...agenda] }); this.tracer?.emit("add-fact", { symbol: fact, toProcess: [...toProcess] }); } while (agenda.length > 0) { while (toProcess.length > 0) { const symbol = this.order === "fifo" ? agenda.shift()! : agenda.pop()!; const symbol = this.order === "fifo" ? toProcess.shift()! : toProcess.pop()!; if (known.includes(symbol)) continue; known.push(symbol); // ▸ take a fact off the agenda and mark it known this.tracer?.emit("pop", { symbol, known: known.length, agenda: [...agenda] }); this.tracer?.emit("pop", { symbol, known: known.length, toProcess: [...toProcess] }); if (symbol === goal) { // ▸ the goal is known: entailed this.tracer?.emit("goal-reached", { goal, known: known.length, fired: fired.length }); return { entailed: true, known, fired }; } kb.rules.forEach((rule, index) => { if (!rule.premises.includes(symbol)) return; remaining[index] = (remaining[index] ?? 0) - 1; unknownPremises[index] = (unknownPremises[index] ?? 0) - 1; if (remaining[index] !== 0) return; if (unknownPremises[index] !== 0) return; fired.push(index); if (!known.includes(rule.conclusion) && !agenda.includes(rule.conclusion)) agenda.push(rule.conclusion); if (!known.includes(rule.conclusion) && !toProcess.includes(rule.conclusion)) toProcess.push(rule.conclusion); // ▸ every premise is known, so the conclusion joins the agenda this.tracer?.emit("fire", { rule: index, premises: [...rule.premises], conclusion: rule.conclusion, agenda: [...agenda] }); this.tracer?.emit("fire", { rule: index, premises: [...rule.premises], conclusion: rule.conclusion, toProcess: [...toProcess] }); }); } // ▸ the agenda is empty and nothing new can be derived this.tracer?.emit("fixpoint", { goal, known: known.length, fired: fired.length, entailed: false }); return { entailed: false, known, fired }; }}