CAIE 9618 · Paper 4 · Topic 4.6.2

Declarative
Programming

Logic Programming · Prolog · Facts · Rules · Queries · Backtracking · Pattern Matching

CSZone Cambridge International AS & A Level Computer Science 9618

The Paradigm

What is Declarative Programming?

Declarative programming describes WHAT a solution looks like rather than HOW to compute it step by step. The programmer specifies the problem as a set of facts, rules, and queries — the language runtime figures out how to find the answer.

PROGRAMMING PARADIGM COMPARISON

Paradigm	Focus	Example
Imperative	HOW (step by step)	Python loops
OOP	Objects and state	Java classes
Functional	Pure transformations	Haskell
Declarative / Logic	WHAT is true	Prolog

LOGIC PROGRAMMING

Prolog (Programming in Logic) is the main language on the CAIE 9618 spec — specifically, the Cambridge version of Prolog syntax

A Prolog program consists of a knowledge base of FACTS and RULES

The user submits QUERIES and Prolog searches the knowledge base to find if they are true

Prolog uses unification and backtracking to find solutions automatically

Prolog Fundamentals

Facts · Rules · Queries

FACTS

Unconditional statements — always true. Represent known data about the world. End with a full stop.

% Facts — end with .
parent(tom, bob).
parent(tom, liz).
parent(bob, ann).
parent(bob, pat).

likes(alice, cheese).
likes(bob, wine).

RULES

Conditional statements — true IF conditions (body) hold. Head :- Body. Read: "Head is true if Body is true."

% Rule: X is grandparent of Z
% if X is parent of Y
% AND Y is parent of Z
grandparent(X, Z) :-
parent(X, Y),
parent(Y, Z).

% , means AND in Prolog

QUERIES

Questions asked of the knowledge base. Written with ?- prefix. Prolog responds true/false or binds variables.

% Is tom parent of bob?
?- parent(tom, bob).
true

% Who are tom's children?
?- parent(tom, X).
X = bob ;
X = liz

Syntax rules: predicate names and atoms start lowercase. Variables start UPPERCASE (X, Y, Z, Parent). Full stops end every clause. :- means "if". , means "AND". ; means "OR". % starts a comment.

How Prolog Works

Unification & Backtracking

UNIFICATION

Prolog tries to match (unify) query terms with facts and rule heads. When a variable is matched to a value, it becomes bound to that value for the duration of that attempt.

?- parent(tom, X).

% Prolog tries: parent(tom, bob)
% X unifies with bob → true
% X = bob is reported
% User types ; to request more
% Prolog tries: parent(tom, liz)
% X = liz is reported

BACKTRACKING

Backtracking is how Prolog explores multiple possibilities. When one attempt fails or more solutions are requested, Prolog undoes bindings and tries the next matching clause.

?- grandparent(tom, X).

% Tries grandparent rule:
% parent(tom,Y), parent(Y,X)
% Y=bob → parent(bob,X)
% X=ann → true! X=ann reported
% Backtracks: X=pat → true! X=pat
% Backtracks: Y=liz → parent(liz,X)
% No facts match → fail

Backtracking is automatic and systematic — Prolog searches depth-first through all clauses, returning to try alternatives whenever a path fails. The programmer does NOT write the search logic.

Prolog Lists

Lists & Pattern Matching

Lists are fundamental in Prolog. A list is written as [H|T] where H is the Head (first element) and T is the Tail (rest of the list). This enables recursive list processing through pattern matching.

LIST NOTATION

% Explicit list
[1, 2, 3, 4, 5]

% Head | Tail pattern
[H | T] = [1, 2, 3, 4]
% H = 1, T = [2, 3, 4]

% Empty list
[]

% Base case: first element
[H | _] = [apple, pear]
% H = apple, _ = anonymous var

RECURSIVE LIST PREDICATES

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

?- member(pear, [apple,pear,grape]).
true

% myLength/2: length of list
myLength([], 0).
myLength([_|T], N) :-
myLength(T, N1),
N is N1 + 1.

Prolog Control

Arithmetic & the Cut Operator

ARITHMETIC IN PROLOG

Prolog does NOT automatically evaluate arithmetic. Use the is operator to evaluate an expression and unify with a variable.

% WRONG: X = 3 + 4
% X = 3+4 (not 7!)

% CORRECT: use 'is'
X is 3 + 4. % X = 7

square(X, Y) :- Y is X * X.
?- square(5, Y). % Y = 25

% Comparisons: < > =:= =\=
?- 5 > 3. % true

THE CUT OPERATOR !

The cut (!) stops Prolog from backtracking past the current clause. Once a cut is reached and succeeds, Prolog commits to the current choice and will not try alternatives for the current goal or parent goal.

% Without cut: max finds both
max(X, Y, X) :- X >= Y, !.
max(_, Y, Y).

% Cut commits to first clause
% if X >= Y — skips second
?- max(5, 3, M). % M = 5

Exam Practice

Cambridge-style questions

Question 1

The following Prolog knowledge base is defined:

teaches(smith, computing). teaches(jones, maths). teaches(smith, physics).
likes(ann, computing). likes(ann, maths). likes(bob, physics).
willTake(S, T) :- likes(S, Sub), teaches(T, Sub).

Trace the query ?- willTake(ann, T). showing all solutions and how backtracking is used. [4]

1

Prolog matches willTake(ann, T) to the rule. Evaluates body: likes(ann, Sub), teaches(T, Sub). Tries likes(ann, computing) → Sub=computing. Then tries teaches(T, computing) → T=smith. Solution: T=smith reported.

1

User requests more (;). Prolog backtracks to likes(ann, Sub). Tries likes(ann, maths) → Sub=maths. Then tries teaches(T, maths) → T=jones. Solution: T=jones reported.

1

User requests more. Prolog backtracks again. No more likes(ann, Sub) facts match. No more solutions — Prolog reports false.

1

Backtracking: Prolog automatically undoes the binding of Sub when a branch fails or more solutions are requested, and tries the next matching fact from the knowledge base in order.

Common Mistakes

Don't lose easy marks

1

Using = for arithmetic — in Prolog, X = 3 + 4 binds X to the STRUCTURE "3+4", NOT the value 7. You MUST use "X is 3 + 4" to evaluate arithmetic. The is operator is the ONLY way to trigger evaluation. This is the most common Prolog error in CAIE exams.

2

Getting variable case wrong — ALL Prolog variables start with an UPPERCASE letter or underscore (X, Y, Parent, _). Lowercase means an ATOM (constant), not a variable. Writing parent(tom, x) means "is tom the parent of the constant x?" — not "find what tom is parent of". This changes the meaning completely.

3

Confusing declarative with procedural — in an exam, do NOT describe Prolog as "telling the computer how to search". Prolog programs declare WHAT is true (facts and rules); the Prolog engine handles the HOW (unification, backtracking). The correct phrasing is: "the programmer specifies the problem as facts and rules; Prolog finds solutions automatically."

Topic Summary — 4.6.2

What You Need to Know

PROLOG BASICS

Facts: unconditionally true — atom(arg1, arg2).

Rules: head :- body. (true IF body is true)

Queries: ?- goal. (asks if goal is true)

Variables: UPPERCASE. Atoms: lowercase. , = AND. :- = if.

SEARCH MECHANISM

Unification: match query to fact/rule head, bind variables

Backtracking: on failure, undo bindings and try next clause

Cut (!): prevents backtracking past current choice point

KEY SYNTAX

X is Expr — evaluates arithmetic expression

[H|T] — list pattern: head and tail

_ — anonymous variable (don't care)

; in response — request next solution from Prolog

CSZone

Course Complete!

CAIE 9618 · All 82 Topics · Papers 1–4

YOU HAVE COMPLETED

All 82 Slide Decks

Paper 1 · Paper 2 · Paper 3 · Paper 4

Cambridge International AS & A Level Computer Science 9618

Head to CSZone.co.uk for worksheets, quizzes, past papers, and interactive revision tools