2.1 Structure inspection — programs that examine terms

Prolog terms are data structures you can take apart at runtime. The inspection built-ins:

Type tests:

Decomposition:

?- functor(date(12, jun, 2026), F, A).
F = date, A = 3.

?- arg(2, date(12, jun, 2026), X).
X = jun.

?- date(12, jun, 2026) =.. L.        % 'univ' operator
L = [date, 12, jun, 2026].

?- T =.. [point, 3, 4].              % univ also BUILDS terms
T = point(3, 4).

Worked example — count all numbers anywhere inside a term:

countNums(T, 1) :- number(T), !.
countNums(T, 0) :- atomic(T), !.            % atoms, [] etc.
countNums(T, N) :-
    compound(T),
    T =.. [_|Args],
    countList(Args, N).

countList([], 0).
countList([H|T], N) :-
    countNums(H, NH), countList(T, NT), N is NH + NT.

?- countNums(f(1, g(2, a), [3, b]), N).     % N = 3

This is generic programming: one predicate works on terms of any shape — the Prolog counterpart of Haskell's ADT interpreters (Unit 2).

2.2 Second-order programming

"Second-order" = predicates that talk about other predicates and the set of their solutions rather than individual values.

The all-solutions predicates:

?- findall(C, parent(ram, C), Cs).
Cs = [lav, kush].

?- findall(N-S, employee(N, _, S), Pairs).
Pairs = [asha-90000, vikram-75000, meera-82000, ravi-60000].

% bagof groups by department unless we existentially quantify with ^
?- bagof(N, S^employee(N, D, S), Ns).
D = cse, Ns = [asha, vikram] ;
D = ece, Ns = [meera, ravi].

?- setof(D, N^S^employee(N, D, S), Ds).
Ds = [cse, ece].

Aggregation patterns built on findall:

countSolutions(Goal, N) :- findall(x, Goal, L), length(L, N).
totalSalary(T) :- findall(S, employee(_, _, S), Ss), sumList(Ss, T).

call/N — treating goals as data (Prolog's higher-order functions):

% map and filter, Prolog style
maplist2(_, [], []).
maplist2(P, [X|Xs], [Y|Ys]) :- call(P, X, Y), maplist2(P, Xs, Ys).

double(X, Y) :- Y is 2 * X.
?- maplist2(double, [1,2,3], L).      % L = [2,4,6]

include2(_, [], []).
include2(P, [X|Xs], R) :-
    ( call(P, X) -> R = [X|R1] ; R = R1 ),
    include2(P, Xs, R1).
?- include2(even, [1,2,3,4], L).      % L = [2,4]  (with even(X) :- 0 is X mod 2.)

Compare directly with Unit 2: maplist ↔ map, include ↔ filter, findall ↔ a list comprehension. The two paradigms converge at the higher-order level.

2.3 Modifying the database at runtime: assert & retract

:- dynamic score/2.                  % declare a modifiable predicate

?- assertz(score(asha, 95)).        % add at end (asserta adds at front)
?- assertz(score(ravi, 72)).
?- retract(score(ravi, _)).         % remove a matching clause

Classic use — memoisation of the slow Fibonacci:

:- dynamic fibMemo/2.
fibM(N, F) :- fibMemo(N, F), !.                  % already computed?
fibM(0, 0). fibM(1, 1).
fibM(N, F) :- N > 1, A is N-1, B is N-2,
              fibM(A, FA), fibM(B, FB),
              F is FA + FB,
              assertz(fibMemo(N, F)).            % remember it

Use assert/retract with restraint: a program that rewrites itself is powerful but harder to reason about — the same warning as mutable state everywhere else in this course.

2.4 findall vs bagof vs setof — the boundary cases that get asked

The headline differences hide three examinable subtleties. Given employee/3 from Unit 3 plus a department with no employees:

% 1. Empty result:
?- findall(N, employee(N, law, _), L).     % L = []          (succeeds!)
?- bagof(N, employee(N, law, _), L).       % fails           (no solutions → no bag)

% 2. Free variables — bagof/setof GROUP by them:
?- bagof(N, employee(N, D, _), L).         % wait — D AND the salary are free...
% In SWI the salary slot _ is anonymous, but a named free variable groups:
?- bagof(N, S^employee(N, D, S), L).
D = cse, L = [asha, vikram] ;
D = ece, L = [meera, ravi].
% findall treats ALL free variables as existential — no grouping ever:
?- findall(N, employee(N, D, S), L).       % L = all four names, D, S unbound

% 3. Duplicates and order:
?- bagof(D, N^S^employee(N, D, S), L).     % L = [cse, cse, ece, ece]
?- setof(D, N^S^employee(N, D, S), L).     % L = [cse, ece]   (sorted, deduplicated)

2.5 Worked second-order example — building a substitution predicate

"Replace every occurrence of atom Old by New anywhere inside a term" — structure inspection and recursion working together:

substitute(Old, New, Old, New) :- !.                 % the term IS Old
substitute(_,   _,   T,   T)   :- atomic(T), !.      % other atoms/numbers: unchanged
substitute(Old, New, T,   T2)  :-                     % compound: rebuild via univ
    compound(T),
    T =.. [F|Args],
    subList(Old, New, Args, Args2),
    T2 =.. [F|Args2].

subList(_, _, [], []).
subList(Old, New, [A|As], [B|Bs]) :-
    substitute(Old, New, A, B),
    subList(Old, New, As, Bs).

?- substitute(a, x, f(a, g(a, b), [a]), T).
T = f(x, g(x, b), [x]).

The pattern — decompose with =.., recurse on the argument list, rebuild with =.. — answers every "write a predicate that processes arbitrary terms" question (count atoms, find depth, collect variables...).

% term depth, same skeleton:
depth(T, 0) :- atomic(T), !.
depth(T, D) :- compound(T), T =.. [_|Args],
               maxDepth(Args, M), D is M + 1.
maxDepth([], 0).
maxDepth([A|As], M) :- depth(A, D1), maxDepth(As, D2), M is max(D1, D2).

?- depth(f(g(h(a)), b), D).      % D = 3

2.6 Prolog vs Haskell higher-order — the convergence table

The deep difference: Haskell's functions are opaque (you can only apply them), while Prolog terms are transparent (any term, even a goal, can be decomposed with =..). Transparency is what makes meta-interpreters possible — a Prolog interpreter for Prolog is about five clauses, a popular "advanced" exam question:

% the vanilla meta-interpreter
prove(true)   :- !.
prove((A, B)) :- !, prove(A), prove(B).
prove(G)      :- clause(G, Body), prove(Body).

clause(G, Body) looks up a program clause whose head unifies with G — the program reasoning about itself, the signature capability of second-order logic programming.

Exam pointers

• "Differentiate findall, bagof and setof" — the table of §2.4 plus the empty-result and ^ behaviours; an example with grouping output earns the top mark.
• "Explain =.. (univ), functor/3 and arg/3" — one line + one query each, then the substitute or countNums skeleton as the applied example.
• "What are the dangers of assert/retract?" — self-modifying code defeats declarative reading; results depend on call history; but cite memoisation as the legitimate use.
• The three-clause meta-interpreter above is a compact high-value answer for "what is meta-programming in Prolog?".

Self-check

1. What do ?- functor(T, point, 2). and ?- T =.. [foo, 1, 2, 3]. bind T to? (Both build terms.)
2. Why does bagof fail where findall returns [], and when is each behaviour preferable?
3. Write countAtoms/2 (count non-number atoms in a term) by adapting countNums.
4. Using findall and max_list, define highestPaid/1.
5. Extend the meta-interpreter to count the number of resolution steps used in a proof.