Logic programming and query systems

Lesson 17's amb let you declare choices and constraints and let the engine search — but you still wrote a procedure: generate this, then that, then require. This lesson takes declarativeness to its limit. We build a query language: you state facts and rules about relations, then ask questions, with no procedural order at all. The engine that makes a single rule answer the same question "forwards" and "backwards" rests on one idea deeper than the pattern matching you have used so far: unification, two-directional matching. It is the last and most radical of our evaluator variants — and the place where the "declarative ideal" finally collides with "operational reality."

Book source

Maps to SICP 4.4 (logic programming): assertions and rules, pattern matching, unification, the frame/stream model of query evaluation, and the system's limitations (negation-as-failure, infinite loops). We follow that arc — distinguish matching from unification, thread a stream of frames, apply rules recursively, then name the gap between declarative meaning and operational behavior — but the relations, the unification trace, and the binding frames are original.

Linear position

Prerequisite: Lesson 17 (declared choices + a searching engine), Lesson 13 (streams — the engine threads a stream of partial answers), and Lesson 06 (symbolic data and pattern matching as tree rewriting).
New capability: a relational query language built from facts + rules; the distinction between one-directional pattern matching and two-directional unification that lets one rule run both ways; and a clear-eyed view of where the declarative ideal diverges from what the engine actually does.

The plan

Five moves. (1) State a tiny database of facts and a rule, and pose queries. (2) Define the engine's currency — frames (sets of bindings) and the stream of frames threaded through a query. (3) Contrast pattern matching (one-directional) with unification (two-directional) and show why two-directionality is the whole magic. (4) Apply a recursive rule and watch frames flow. (5) Confront the limits — negation-as-failure and nontermination — the declarative ideal vs the operational reality.

1 · Facts, rules, queries

A logic program is a set of assertions (ground facts) and rules (conditional facts). You never say how to compute; you say what is true, and query against it. Take a small family database:

// FACTS — relations that simply hold:
parent("abe",  "homer");      // abe is a parent of homer
parent("homer","bart");
parent("homer","lisa");

// RULE — grandparent(g, c) is TRUE WHEN there is a p with parent(g,p) and parent(p,c):
rule( grandparent(g, c),
      and( parent(g, p), parent(p, c) ) );    // g, p, c are PATTERN VARIABLES

Now the same rule answers many different questions depending on what you leave blank — and this is the property procedures lack:

Query	Reads as	Answers
`grandparent("abe", c)`	who are abe's grandchildren?	c = bart, c = lisa
`grandparent(g, "bart")`	who are bart's grandparents?	g = abe
`grandparent(g, c)`	every grandparent/grandchild pair	(abe,bart), (abe,lisa)

One rule, three modes. A JavaScript function grandparent(g) would compute grandchildren from a grandparent and could never be run in reverse. The query system runs the relation in any direction because it never committed to inputs and outputs — and that is exactly what unification buys.

2 · Frames and the stream of frames — the engine's currency

A frame is a set of bindings — assignments of values to pattern variables — representing one consistent partial answer so far. The empty frame {} means "no commitments yet." A query does not return a list of answers directly; it is a transformer of a stream of frames: it takes an incoming stream of frames (partial answers) and emits an outgoing stream, each extended or filtered by trying to satisfy the query.

Worked intuition — the frame stream as the search state

  input stream of frames        query: parent(g, "bart")        output stream
  ----------------------        ------------------------        -------------
        [ {} ]            -->    try to match against each  -->    [ {g: "homer"} ]
                                 stored parent fact:
                                   parent(abe,homer)  : "bart" != "homer"  drop
                                   parent(homer,bart) : matches, bind g    keep
                                   parent(homer,lisa) : "bart" != "lisa"   drop

A and(q1, q2) feeds the output stream of q1 as the input stream of q2 — so each frame that survived q1 is further constrained by q2. An or(q1, q2) runs both on the same input and appends their output streams. This is precisely the Lesson 13 stream machinery doing search: laziness lets the engine produce answers incrementally, and conjunction is just stream composition. Frames flow in, frames flow out, narrowing at every step.

3 · Pattern matching vs unification — the two-directional engine

Here is the heart of the lesson. There are two ways to make a pattern meet a datum.

Pattern matching (one-directional)

A pattern (which may contain variables) is matched against a ground datum (no variables). Variables exist on one side only. Matching parent(g, "bart") against the fact parent("homer","bart") binds g := "homer". Used to match queries against stored facts.

Unification (two-directional)

Two patterns, both possibly containing variables, are made identical by finding bindings for variables on either side. Unifying job(x, "cook") with job("amy", y) yields x := "amy", y := "cook". Used to apply rules, whose conclusions are themselves patterns.

Why does two-directionality matter? Because a rule's conclusion (grandparent(g, c)) is a pattern with variables, and the query (grandparent("abe", c)) is also a pattern with a variable. To apply the rule you must reconcile two open expressions, binding variables wherever they appear — on the query side and the rule side. Pattern matching cannot do this; unification can. And because unification never decides which side is "input," the same rule runs in every direction — the magic from §1.

Worked example — unify a query against a fact, show the frame

Query address(person, "12 Elm St") against fact address("kim", "12 Elm St"), starting from frame {}:

  unify  address( person , "12 Elm St" )         (query — `person` is a variable)
  with   address( "kim"  , "12 Elm St" )         (fact — all ground)
  --------------------------------------------------------------
  field 1:  person  vs  "kim"     -> person is unbound -> BIND  person := "kim"
  field 2:  "12 Elm St" vs "12 Elm St"  -> constants equal -> OK, no new binding
  result frame:  { person: "kim" }                          SUCCESS

Now the genuinely two-directional case — unify two open patterns:

  unify  meeting( team , time )      (both variables)
  with   meeting( "qa" , slot )      (one ground, one variable)
  --------------------------------------------------------------
  field 1:  team vs "qa"   -> BIND  team := "qa"
  field 2:  time vs slot   -> two variables -> BIND  time := slot  (alias them)
  result frame:  { team: "qa", time: slot }     time now tracks slot, both still open

The second case is impossible for one-directional matching: it binds a variable to another variable, so that when slot is later determined, time follows. That linking is what lets partial information flow both ways through a rule. (Unification must also do an occurs check — refuse to bind x := f(x) — to avoid building infinite terms.)

4 · Applying a rule, recursively

To answer a query that matches a rule's conclusion, the engine: (1) renames the rule's variables to fresh ones (so two uses don't collide); (2) unifies the query with the renamed conclusion, extending the frame; (3) evaluates the rule's body as a new query against that frame. Rules may invoke themselves — recursion is just a rule whose body mentions its own relation.

// "ancestor" — the transitive closure of parent, defined recursively:
rule( ancestor(a, d), parent(a, d) );                       // base: a parent IS an ancestor
rule( ancestor(a, d), and( parent(a, mid),
                           ancestor(mid, d) ) );            // step: parent then ancestor

Worked example — ancestor("abe", d)

ancestor("abe", d)
 |- via base rule:  parent("abe", d)        -> d := "homer"            ANSWER d=homer
 |- via step rule:  parent("abe", mid), ancestor(mid, d)
        parent("abe", mid)                  -> mid := "homer"
        ancestor("homer", d)
          |- base:  parent("homer", d)      -> d := "bart"             ANSWER d=bart
                                            -> d := "lisa"             ANSWER d=lisa
          |- step:  parent("homer", mid2), ancestor(mid2, d)
                 parent("homer", mid2)      -> mid2 := bart, then lisa
                 ancestor("bart", d)        -> no parent facts -> empty stream
   stream of answers:  homer, bart, lisa

Each line is a frame flowing through the stream of §2; each rule application is a unification of §3 plus a recursive sub-query. Notice the engine explored both rules (base and step) — that is the or of §2, appending their answer streams.

5 · The declarative ideal vs the operational reality

The promise was "describe what is true, the engine figures out the rest." The promise leaks, and an honest engineer must know where.

Negation as failure

not(q) does not mean "q is false." It means "q produced no frames from the current stream." So not depends on what is already bound and on the closed-world assumption (unstated ⇒ false). Reorder the conjuncts and not can flip its answer — a leak of operational order into a "declarative" construct.

Infinite loops

Declaratively, ancestor is a finite relation; operationally, swap the two body conjuncts (ancestor(mid,d) before parent(a,mid)) and the depth-first engine recurses forever. The meaning is order-independent; the search is not.

Order of facts & clauses matters

The answer set is order-independent; the answer stream (which comes first, whether you terminate) depends on clause and conjunct order — again the gap between logic and the engine that runs it.

It is depth-first, not complete

Like Lesson 17's amb, the engine searches depth-first and can get stuck on one infinite branch while a solution waits on another. "The engine finds it if it exists" is true only for the fragment that terminates.

These are not bugs to patch so much as the price of running a declarative specification on a finite, ordered machine. Which is the very tension that detonates this entire Part — see below.

Common mistakes / failure modes

Treating rules like functions

A rule is a relation, not an input→output procedure. Expecting grandparent to "compute" grandchildren from a grandparent misses that it can equally compute grandparents from a grandchild — the whole point.

Forgetting variable renaming

If a rule's x is not renamed per use, two applications of the rule alias their variables and produce spurious or lost bindings. Each rule instance needs fresh variables.

Reading not as logical negation

It is negation-as-failure under the closed-world assumption and is order-sensitive; place it after the variables it mentions are bound, or it filters nothing (or everything).

Skipping the occurs check

Unifying x with a term containing x builds an infinite structure and can loop. A correct unifier refuses such a binding.

Checkpoint exercise

Try it

(a) Unify likes(person, "tea") with the fact likes("sam", drink) starting from {} — give the resulting frame. (b) Given sibling(x, y) defined as "there exists p with parent(p, x) and parent(p, y) and x ≠ y", and facts parent(homer,bart), parent(homer,lisa), list the answers to sibling(s, "bart"). (c) Why must the rule include x ≠ y, and what kind of construct is it?

rule( sibling(x, y),
      and( parent(p, x), parent(p, y), not_same(x, y) ) );

Answers: (a) Both sides have a variable, so this is genuine unification: field 1 binds person := "sam"; field 2 binds drink := "tea". Result frame { person: "sam", drink: "tea" }. (b) s = lisa (shared parent homer, and lisa ≠ bart). (c) Without x ≠ y the engine also unifies x and y to the same child, reporting bart as its own sibling. not_same is negation-as-failure — it must come after x,y are bound, or it cannot compare them.

Where this points next

Look back across Part IV. The metacircular evaluator (14), the analyzer (15), the lazy evaluator (16), the amb evaluator (17), and this query engine (18) all share a guilty secret: every one borrowed the host language's recursion, memory, and dispatch. When unification recursed, it used JavaScript's call stack. When the frame stream grew, it used JavaScript's heap and garbage collector. When the engine "tried the next rule," it leaned on the host's control flow. We have been describing semantics while standing on machinery we never built or even saw. To expose the true cost of control — what recursion, a stack frame, or a variable lookup actually costs — Lesson 19 descends one floor: it expresses computation as a register machine, with explicit registers, an explicit stack, and explicit branches, owing nothing to a host. Only then can the ladder bottom out in something a real processor runs.

Takeaway

A logic program is facts (ground relations) plus rules (conditional relations with pattern variables); you query by stating what must hold, never how to compute it, so one rule like grandparent answers forwards, backwards, and both-ways-open. The engine's currency is the frame — a set of variable bindings, one consistent partial answer — and a query is a transformer of a stream of frames (Lesson 13 machinery doing search): and threads one query's output stream into the next's input, or appends. The deep mechanism is unification: unlike one-directional pattern matching (variables on one side, query vs ground fact), unification reconciles two open patterns, binding variables on either side — even aliasing a variable to a variable — which is exactly why a rule runs in any direction. Rule application renames the rule's variables, unifies the query with its conclusion, then queries its body; recursion is a rule citing its own relation. But the declarative ideal leaks operationally: not is negation-as-failure (order- and closed-world-sensitive), conjunct order decides termination, and the depth-first search is incomplete. That very gap — semantics described atop unexamined host machinery — is the pressure that forces the descent to register machines.

Interview prompts

What is the difference between pattern matching and unification? (§3 — matching has variables on one side (query vs ground fact); unification reconciles two patterns with variables on either side, binding both — even variable-to-variable — which makes rules run in any direction.)
Why can one logic rule answer a query "forwards" and "backwards"? (§1, §3 — it never fixes inputs vs outputs; unification binds whichever fields are open, so leaving different fields blank yields different query modes from the same rule.)
What is a frame, and how does a query use a stream of frames? (§2 — a frame is a set of variable bindings (one partial answer); a query transforms an input stream of frames to an output stream; and composes streams, or appends them.)
Trace unifying a query with a fact and give the resulting frame. (§3 — e.g. address(person,"12 Elm St") vs address("kim","12 Elm St") binds person:="kim"; constants must be equal; an occurs check forbids x:=f(x).)
How is a recursive rule like ancestor evaluated? (§4 — rename the rule's variables, unify the query with its conclusion, query the body; the recursive conjunct re-enters the relation; base and step clauses are an or appending answer streams.)
Why doesn't not mean logical negation? (§5 — it is negation-as-failure under the closed-world assumption: "no frames survived," which is sensitive to existing bindings and conjunct order.)
Where does the declarative ideal diverge from operational reality? (§5 — answer set is order-independent but termination, answer order, and not depend on clause/conjunct order; depth-first search is incomplete and can loop.)