2.1 Logic programs as databases

A collection of facts is a relational database — predicates are tables, facts are rows:

% employee(Name, Dept, Salary)
employee(asha,  cse, 90000).
employee(vikram, cse, 75000).
employee(meera, ece, 82000).
employee(ravi,  ece, 60000).

% department(Dept, Building)
department(cse, block_a).
department(ece, block_b).

Rules then play the role of SQL queries and views:

?- worksIn(asha, B).      % B = block_a
?- rich(Who).             % Who = asha ; Who = meera

This is why logic programming directly inspired Datalog and deductive databases, and why SQL's recursive queries (WITH RECURSIVE) feel exactly like the rules below.

2.2 Recursive rules — where logic programs beat plain SQL

Some relations cannot be expressed with a fixed number of joins — the classic one is ancestor (transitive closure of parent):

ancestor(X, Y) :- parent(X, Y).                  % base clause
ancestor(X, Y) :- parent(X, Z), ancestor(Z, Y).  % recursive clause

The recipe mirrors functional recursion (Unit 2):

1. Base clause — the simplest way the relation holds.
2. Recursive clause — reduce the problem by one step (one parent hop) and recurse on the rest.

Trace of ?- ancestor(dasharath, lav).:

ancestor(dasharath, lav)
 ├─ clause 1: parent(dasharath, lav)?  → fails (no such fact)
 └─ clause 2: parent(dasharath, Z), ancestor(Z, lav)
      Z = ram      → ancestor(ram, lav)
                      └─ clause 1: parent(ram, lav)?  → TRUE ✓

2.3 Lists in logic programs

The list [1,2,3] is the structure .(1, .(2, .(3, []))) — same cons-cell idea as Haskell. The key pattern is [H|T] (head H, tail T):

% member/2 — is X in the list?
member(X, [X|_]).
member(X, [_|T]) :- member(X, T).

% append/3 — relation between two lists and their concatenation
append([], L, L).
append([H|T], L, [H|R]) :- append(T, L, R).

% length/2
listLen([], 0).
listLen([_|T], N) :- listLen(T, M), N is M + 1.

append run in different directions (the showpiece of relational thinking):

?- append([1,2], [3], X).      % forwards:  X = [1,2,3]
?- append(X, [3], [1,2,3]).    % backwards: X = [1,2]
?- append(X, Y, [1,2]).        % split: X=[],Y=[1,2] ; X=[1],Y=[2] ; X=[1,2],Y=[]

One definition: concatenation, subtraction and splitting.

2.4 More classic recursive predicates

% naive reverse
reverse([], []).
reverse([H|T], R) :- reverse(T, RT), append(RT, [H], R).

% reverse with accumulator (efficient — compare Unit 2's revFast)
rev(L, R) :- revAcc(L, [], R).
revAcc([], Acc, Acc).
revAcc([H|T], Acc, R) :- revAcc(T, [H|Acc], R).

% last element
last([X], X).
last([_|T], X) :- last(T, X).

% delete every occurrence of X
delete(_, [], []).
delete(X, [X|T], R)        :- delete(X, T, R).
delete(X, [H|T], [H|R])    :- X \= H, delete(X, T, R).

2.5 Rule-order and goal-order matter

Declaratively, clause order is irrelevant — procedurally (with depth-first search) it is critical:

% DANGEROUS version of ancestor — left recursion first:
ancestor2(X, Y) :- ancestor2(Z, Y), parent(X, Z).   % may loop forever!
ancestor2(X, Y) :- parent(X, Y).

Guidelines that keep recursive programs terminating:

1. Put base clauses before recursive clauses.
2. In rule bodies, put the goal that shrinks the problem (e.g. parent(X, Z)) before the recursive call.
3. Make sure the recursive call works on a structurally smaller argument.

These are exactly the termination rules of functional recursion, resurfacing in relational clothing.

2.6 Tracing append in both directions (write-this-in-the-exam material)

Forwards — ?- append([1,2], [3], X).

append([1,2], [3], X)
  matches clause 2 with H=1, T=[2], L=[3], X=[1|R1]
  → append([2], [3], R1)
      matches clause 2 with H=2, T=[], R1=[2|R2]
      → append([], [3], R2)
          matches clause 1 → R2 = [3]
  Answer assembled outward:  R1 = [2,3],  X = [1,2,3]   ✓

Splitting — ?- append(X, Y, [1,2]). Backtracking enumerates every decomposition:

clause 1:  X=[], Y=[1,2]                                    -- 1st answer
clause 2:  X=[1|X1], append(X1, Y, [2])
    clause 1:  X1=[], Y=[2]      → X=[1], Y=[2]             -- 2nd answer
    clause 2:  X1=[2|X2], append(X2, Y, [])
        clause 1:  X2=[], Y=[]   → X=[1,2], Y=[]            -- 3rd answer
        clause 2:  needs [] = [H|R] → fail, no more answers

Each ; you type at the prompt resumes this tree at the last choice point. Being able to write this exact trace is worth full marks on the standard "explain how append works backwards" question.

2.7 Trace of member — and why order of answers is what it is

?- member(X, [a, b]).
clause 1:  member(X, [a|_])  → X = a          -- 1st answer
clause 2:  member(X, [_|[b]]) → member(X, [b])
    clause 1:  X = b                           -- 2nd answer
    clause 2:  member(X, []) → no clause matches → fail

Answers arrive in list order because clause 1 (take the head) is tried before clause 2 (skip into the tail) at every level. Swap the clauses and the answers come in reverse order — same logic, different control.

2.8 The rest of the classic list predicates

% nth element (1-based)
nth(1, [X|_], X).
nth(N, [_|T], X) :- N > 1, N1 is N - 1, nth(N1, T, X).

% sublist: S occurs contiguously inside L  (append defines it!)
sublist(S, L) :- append(_, Rest, L), append(S, _, Rest).

% prefix and suffix — also via append
prefix(P, L) :- append(P, _, L).
suffix(S, L) :- append(_, S, L).

% insert X somewhere into a list / permutations
insert(X, L, R) :- append(A, B, L), append(A, [X|B], R).
perm([], []).
perm(L, [H|T]) :- select(H, L, Rest), perm(Rest, T).   % select/3 removes one element

% maximum of a list
maxL([X], X).
maxL([H|T], M) :- maxL(T, MT), (H >= MT -> M = H ; M = MT).

Notice how much is defined through append — in relational programming append/3 plays the role that foldr plays in Haskell: the universal building block.

2.9 Arithmetic vs structural recursion in Prolog

Forgetting the N > 0 guard makes arithmetic recursion loop on backtracking (fact(0, F) would also try clause 2 with N = 0, then -1, -2, ...). This single mark-losing bug appears in countless exam scripts — check for it.

Exam pointers

• member/2, append/3, reverse/2 (both versions), last/2, delete/3 — memorise all five; they are asked verbatim, alone or as building blocks.
• "Show how one append definition concatenates, splits and subtracts lists" — the three queries of §2.3 plus the splitting trace of §2.6.
• Termination questions ("why does this loop?") almost always involve left recursion (§2.5) or a missing arithmetic guard (§2.9).
• When the question says "define X without using built-ins", the append-based definitions of §2.8 are acceptable if you also define append yourself.

Self-check

1. Trace ?- member(b, [a, b, c]). showing every clause attempt.
2. What do ?- append([1], Y, [1, 2, 3]). and ?- append(X, [3], [1, 2, 3]). each bind?
3. Define evenLength/1 and oddLength/1 by mutual recursion on [_|T].
4. Why does the accumulator version of reverse run in O(n) while the naive one is O(n²)?
5. Using sublist, what answers does ?- sublist([2], [1,2,3]). produce, and why might it succeed more than once?