1.1 From theory to tool

Unit 3 gave the model; this unit is hands-on Prolog (PROgramming in LOGique, Colmerauer & Roussel, 1972). Install SWI-Prolog (free, all platforms). Save programs in a .pl file, load with [myfile]. or consult(myfile)., query at the ?- prompt; ; asks for more answers, . accepts.

1.2 Term syntax — everything is a term

The arity matters: foo/2 and foo/3 are different predicates. Operators are just compound terms in disguise: 2 + 3 is the term +(2, 3) — not the number 5!

1.3 Arithmetic: is vs =

The single most common beginner trap:

Arithmetic comparisons (< > =< >= =:= =\=) evaluate both sides; note "less or equal" is =< (not <=). Useful functions: + - * /, // (integer div), mod, abs, min, max, sqrt.

% factorial
fact(0, 1).
fact(N, F) :- N > 0, N1 is N - 1, fact(N1, F1), F is N * F1.

% fibonacci
fib(0, 0).
fib(1, 1).
fib(N, F) :- N > 1, A is N-1, B is N-2,
             fib(A, FA), fib(B, FB), F is FA + FB.

% sum of a list
sumList([], 0).
sumList([H|T], S) :- sumList(T, ST), S is H + ST.

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

Remember: is needs its right-hand side fully instantiated — X is Y + 1 with unbound Y is an error. Order your goals so variables are bound before arithmetic uses them.

1.4 Controlling the search: the cut (!)

The cut ! always succeeds, but as a side effect it freezes the choices made so far in the current clause: on backtracking past the cut, the whole predicate call fails — no other clauses of this predicate are tried, and no alternatives for the goals before the cut are revisited.

% classify with cuts ("if-then-else ladder")
classify(N, negative) :- N < 0, !.
classify(N, zero)     :- N =:= 0, !.
classify(_, positive).

% max with cut
max(X, Y, X) :- X >= Y, !.
max(_, Y, Y).

• Green cut: removes only choices that could never succeed — pure efficiency; meaning unchanged.
• Red cut: removes real solutions — the program's logic now depends on the cut (like max/3 above: delete the cut and max(5,3,3) succeeds wrongly). Use red cuts sparingly and document them.

Related built-ins: fail (always fails — combine with backtracking to iterate), true, the if-then-else ( Cond -> Then ; Else ), and \+ (negation as failure, from Unit 3).

% print every parent pair using the fail-driven loop idiom
printAll :- parent(X, Y), format("~w is parent of ~w~n", [X, Y]), fail.
printAll.

1.5 Input/output basics

1.6 A complete worked micro-program

% Grade lookup with validation
grade(M, _)      :- (M < 0 ; M > 100), !, write('invalid marks'), nl, fail.
grade(M, 'A+')   :- M >= 90, !.
grade(M, 'A')    :- M >= 75, !.
grade(M, 'B')    :- M >= 60, !.
grade(M, 'C')    :- M >= 40, !.
grade(_, 'Fail').

?- grade(82, G).      % G = 'A'
?- grade(105, G).     % invalid marks → fails

This combines arithmetic comparison, cut-as-else, failure for validation and I/O — the full toolkit of this lesson in ten lines.

1.7 The cut, precisely — what exactly gets discarded

Definition. When ! is executed in a clause H :- B1, ..., !, ... Bn it succeeds immediately and commits to (a) the clause currently being used for the call to H, and (b) all bindings made by B1... before the cut. On backtracking into the cut, the entire call to H fails — remaining clauses of H are never tried and alternatives for the pre-cut goals are never revisited. Goals after the cut backtrack normally among themselves, and goals before the call to H are unaffected.

Trace showing the difference:

p(1).  p(2).  p(3).
q(X) :- p(X), !.        % cut version
r(X) :- p(X).           % no cut

?- q(X).   % X = 1.            — one answer; ';' finds nothing more
?- r(X).   % X = 1 ; X = 2 ; X = 3.

Green cut vs red cut — the comparison table:

Checking the red-cut example: with the bare second clause, ?- max(5, 3, M). correctly gives only M = 5 — but query ?- max(5, 3, 3). succeeds via clause 2 (the head max(_, Y, Y) unifies directly, the cut in clause 1 was never reached because the first head max(X,Y,X) requires the 1st and 3rd arguments to unify). That stray success is the hallmark of red-cut fragility — quote it when asked "what is the danger of cuts?".

1.8 cut-fail: expressing "definitely not"

The !, fail combination implements early rejection — and is exactly how \+ can be defined:

% "ground birds fly, except penguins"
flies(penguin) :- !, fail.        % cut commits, fail rejects — no clause 2 rescue
flies(X)       :- bird(X).

% negation as failure, defined with cut-fail (a classic theory question)
not(G) :- call(G), !, fail.       % G provable → not(G) fails
not(_).                            % G not provable → not(G) succeeds

1.9 Tail recursion with accumulators — Prolog edition

The naive fact/2 builds up N F1 multiplications after* the recursive call returns. The accumulator version does the work on the way down, enabling last-call optimisation (constant stack):

factA(N, F) :- factAcc(N, 1, F).
factAcc(0, Acc, Acc).
factAcc(N, Acc, F) :- N > 0, Acc1 is Acc * N, N1 is N - 1, factAcc(N1, Acc1, F).

?- factA(5, F).
% factAcc(5,1,F) → factAcc(4,5,F) → factAcc(3,20,F)
%   → factAcc(2,60,F) → factAcc(1,120,F) → factAcc(0,120,F) → F = 120

Compare with revAcc (Unit 3) and Haskell's revFast (Unit 2): the accumulator idiom is paradigm-independent — one of the recurring "common threads" questions.

1.10 Trace of fact(3, F) — the exam staple

fact(3, F)   : 3 > 0, N1 = 2, call fact(2, F1)
  fact(2, F1): 2 > 0, N1 = 1, call fact(1, F2)
    fact(1, F2): 1 > 0, N1 = 0, call fact(0, F3)
      fact(0, F3): matches fact(0, 1) → F3 = 1
    F2 is 1 * 1  → F2 = 1
  F1 is 2 * 1    → F1 = 2
F  is 3 * 2      → F  = 6

Show the descent (calls) and the ascent (the is evaluations) as separate phases — that structure is what earns the trace marks.

1.11 Term comparison operators — the complete reference

1.12 Common Prolog errors decoded

Exam pointers

• "Explain the cut with green/red examples" — the boxed definition, the q/r trace, and the table of §1.7 are a complete 8-mark answer.
• "Differentiate =, is, ==, =:=" — reproduce §1.11; the 2 + 3 vs 5 column is the memorable part.
• fact, fib, sumList, maxList, GCD — the standard arithmetic predicates; write each with its guard and be ready to trace it as in §1.10.
• "Implement negation using cut and fail" — §1.8's two-clause not/1 is asked surprisingly often.

Self-check

1. For p(1). p(2). p(3)., what does ?- p(X), !, X > 1. answer, and why is it different from ?- p(X), X > 1, !.?
2. Write gcd/3 using mod, with proper guards.
3. Which of these succeed? X = 1+1, 2 == 1+1, 2 =:= 1+1, X is 1+1, X == 2.
4. Convert classify/2 from §1.4 to a single clause using if-then-else ( -> ; ).
5. Trace ?- sumList([4,5], S). showing descent and ascent phases.