1.1 The logic programming idea

A logic program does not describe how to compute. It states facts and rules about a world, and computation happens when you ask a query — the system searches for every way to make the query true.

Algorithm = Logic + Control (Robert Kowalski). The programmer supplies the logic; the language supplies the control (the search strategy).

1.2 The vocabulary of logic programs

Facts + rules about the same predicate form a procedure; the whole collection is the database (or program).

1.3 A first program — the family database

% ----- facts -----
parent(dasharath, ram).
parent(dasharath, lakshman).
parent(ram, lav).
parent(ram, kush).
male(dasharath). male(ram). male(lakshman). male(lav). male(kush).

% ----- rules -----
father(X, Y)      :- parent(X, Y), male(X).
grandparent(X, Z) :- parent(X, Y), parent(Y, Z).
sibling(X, Y)     :- parent(P, X), parent(P, Y), X \= Y.

Read :- as "if" and the comma as "and". Queries:

?- father(ram, lav).        % yes/true
?- grandparent(dasharath, G).
G = lav ;
G = kush.
?- sibling(lav, X).
X = kush.

One definition answers questions in every direction — parent(X, lav) finds the parent, parent(ram, Y) finds the children, parent(X, Y) enumerates every pair. Relations, unlike functions, have no fixed inputs and outputs. This bidirectionality is logic programming's superpower.

1.4 Horn clauses — the underlying logic

Every clause is a Horn clause: a disjunction of literals with at most one positive literal.

Variables in facts/rules are read universally ("for all X..."); variables in a query are read existentially ("does there exist X...").

1.5 Unification — the engine of matching

Unification makes two terms identical by finding a substitution for their variables. It generalises both pattern matching and equality testing.

Rules:

1. A constant unifies only with itself or a variable.
2. A variable unifies with anything (and the binding then applies everywhere).
3. Structures unify if the functor and arity match and the arguments unify pairwise.

The most general such substitution is the MGU (most general unifier) — e.g. for f(X) and f(Y), the MGU is X = Y, not X = a, Y = a.

1.6 How a query actually runs (first look)

To solve ?- grandparent(dasharath, G).:

1. Find a clause whose head unifies with the goal → the grandparent rule, binding X = dasharath, Z = G.
2. Replace the goal with the rule body: parent(dasharath, Y), parent(Y, G).
3. Solve left to right: parent(dasharath, Y) matches the first fact → Y = ram.
4. Now solve parent(ram, G) → G = lav. Answer: G = lav.
5. Ask for more (;) → the system backtracks, retries step 4 → G = kush; then retries step 3 → Y = lakshman, but parent(lakshman, G) has no match → no more answers.

This goal-replacement process is SLD resolution, and the systematic retrying is backtracking — both are studied formally in the computation-model lesson.

1.7 The unification algorithm, step by step

To unify terms T1 and T2 (exam-reproducible form):

1. Both constants: succeed iff they are the same constant.
2. One is a variable X: bind X := other term (after the occurs check, below) and apply the binding to all remaining goals.
3. Both compound: succeed iff same functor and same arity, then unify arguments pairwise left to right, threading the bindings through.
4. Otherwise: fail.

Definition (occurs check). Before binding X := T, verify that X does not occur inside T. Unifying X with f(X) would otherwise build the infinite term f(f(f(...))). Standard Prolog omits this check for speed — a known soundness compromise; unify_with_occurs_check/2 performs it properly.

Worked unification with working shown:

Unify  p(X, g(X), Y)   with   p(a, Z, h(Z))
1. X   vs a      → X = a            (rule 2)
2. g(X) vs Z   i.e.  g(a) vs Z → Z = g(a)
3. Y   vs h(Z) i.e.  Y vs h(g(a)) → Y = h(g(a))
MGU:  { X = a,  Z = g(a),  Y = h(g(a)) }   ✓

More practice rows (cover the answers and try them):

1.8 Declarative and procedural readings — one rule, two meanings

Every rule can (and in exams should) be read both ways:

grandparent(X, Z) :- parent(X, Y), parent(Y, Z).

• Declarative reading: "for all X, Y, Z: X is a grandparent of Z if X is a parent of Y and Y is a parent of Z."
• Procedural reading: "to solve grandparent(X, Z): first solve parent(X, Y), then solve parent(Y, Z)."

The declarative reading is order-independent logic; the procedural reading is what the machine does, where goal order and clause order matter. Kowalski's equation Algorithm = Logic + Control names exactly this split.

1.9 A query trace as a search tree

?- sibling(lav, S). against the family database:

Note how the first candidate S = lav is generated and then rejected by the inequality — generate-and-test in miniature, and a preview of how backtracking quietly powers everything.

1.10 Functional vs logic programming — the bridge table

Exam pointers

• "Define fact, rule, query, Horn clause" — one line each, with the A :- B1,...,Bn ↔ B1 ∧ ... ∧ Bn → A translation for Horn clauses.
• "Explain unification with an example" — the 4-rule algorithm, the worked trace of §1.7, and the occurs-check definition earn full marks.
• Family-tree rule-writing (uncle, cousin, ancestor...) is the most common programming question — always add X \= Y to sibling-like rules to exclude self-pairs.
• State both readings (declarative + procedural) whenever asked to "explain how this rule works".

Self-check

1. Which of these unify, and with what MGU? date(D, M, 2026) vs date(1, jan, Y); f(g(X)) vs f(Y, Z); X vs f(X).
2. Write rules for mother/2, cousin/2 and descendant/2 given parent/2, male/1, female/1.
3. Why are variables in facts read universally but in queries existentially?
4. Give the MGU of f(X, Y) and f(Y, a) — careful, it has two bindings.
5. What is the difference between matching f(X, X) against f(a, a) and against f(a, b)?