Pattern-directed search & the knowledge/control split

One engine, any knowledge base

Pattern-directed reasoning is the algorithm underneath both forward and backward chaining and underneath Prolog itself. The pattern_search procedure takes a goal and:

• if the goal unifies with a fact, succeed (returning the substitution);
• if the goal unifies with a rule's conclusion, recurse on the rule's premises as subgoals;
• handle conjunctions (prove each conjunct, propagating substitutions across them), disjunctions (try each until one succeeds), and negation (¬p succeeds iff p fails — negation as failure).

It combines unification (the pattern matcher, from Module 1) with recursion + backtracking (the search, from Module 3). The call stack is the open list: each activation record holds one node on the current path, and a recursive call returning FAIL is the backtrack to the parent's next sibling.

Separation of knowledge from control

The single most important property: the rules and facts are the domain knowledge, the recursive pattern_search is the control, and they are completely separate. Change the knowledge base and the same engine solves a new problem — pattern_search is a domain-independent problem solver. This is exactly the expert-system shell idea (Module 6).

Rules are modular. They interact only by changing working memory — a rule can never call another rule as a subroutine or set a variable in another rule. Behaviour at any point depends solely on working-memory contents, which is what makes rule bases easy to add to and debug.

A subtlety: declarative logic, procedural order

Logic specifies what is true, not how to search. pattern_search imposes an order by trying rules in the sequence they appear. Two logically equivalent rule formulations — foo ∧ goo → moo versus foo → moo ∨ ¬goo — produce different search behaviour. This "procedural semantics of a declarative language" is why rule ordering is a real design lever in Prolog and expert systems.