Cambridge 9618 · International A Level Computer Science · ~18 min read
Notes
Video
Slides
Quiz
Worksheet
Programming Paradigms
A programming paradigm is a fundamental style of programming. Different paradigms have different ways of thinking about and solving problems.
⚙️
Imperative / Procedural
Tells the computer HOW to solve the problem step by step. Uses variables, loops, branches. Example: Python, Java, C. "Do this, then do that, then check this condition..."
🧮
Functional
Describes WHAT the result should be using functions. No mutable state, no loops — uses recursion and higher-order functions. Example: Haskell.
🔎
Declarative / Logic
Describes relationships and rules. The computer figures out HOW to satisfy them. You state WHAT is true; the engine finds solutions. Example: Prolog, SQL.
What is Declarative Programming?
In declarative programming, you specify what the problem is — the relationships, constraints, and rules — without specifying how to solve it step by step. The language's execution engine determines the solution strategy.
SQL is declarative: SELECT Name FROM Students WHERE Grade = 'A' — you state WHAT data you want, not HOW to retrieve it. Logic programming (Prolog) takes this further: you state facts and rules, then ask questions.
Logic Programming — Prolog
Prolog (Programming in Logic) is the canonical logic programming language. A Prolog program consists of three parts:
1. Facts
Statements that are unconditionally true. Written as: predicate(arg1, arg2). (note the full stop). Atoms (constant names) start with lowercase.
Prolog facts
parent(tom, bob).% tom is a parent of bob parent(tom, liz).% tom is a parent of liz parent(bob, ann).% bob is a parent of ann parent(bob, pat). female(liz). female(ann). male(tom). male(bob).
2. Rules
Conditional statements: "X is true IF Y is true". Written as: head :- body. The :- means "if". Variables start with uppercase.
Prolog rules
% 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).
% X is mother of Y if X is parent of Y AND X is female mother(X, Y) :- parent(X, Y), female(X).
% ancestor: base case — parent is an ancestor ancestor(X, Y) :- parent(X, Y). % ancestor: recursive — X is ancestor of Z if X is ancestor of Y and Y is parent of Z ancestor(X, Z) :- parent(X, Y), ancestor(Y, Z).
3. Queries
Questions posed to the Prolog system. Written with ?- at the prompt. Prolog searches for values of variables that make the query true. Variables in queries are uppercase.
Prolog queries and responses
?- parent(tom, bob). true.% this fact exists
?- parent(tom, ann). false.% no such fact
?- parent(tom, X). X= bob ;% first solution X= liz.% second solution (backtracking)
?- grandparent(tom, X). X= ann ; X= pat.
Unification and Backtracking
Unification is the process of matching a query pattern with facts and rules in the knowledge base. Prolog tries to match the query to known facts/rules, binding variables to values. If a variable X appears in a query and Prolog finds parent(tom, bob), then X is unified (bound) to bob.
Backtracking is how Prolog finds multiple solutions. When the current path fails (or when the user asks for more solutions), Prolog goes back to the most recent choice point and tries the next alternative. It systematically explores all possible solutions through depth-first search.
Tracing a Query
% Query: ?- grandparent(tom, X). Step 1:Try grandparent(tom, X) using rule: grandparent(X,Z) :- parent(X,Y), parent(Y,Z) Bind X→tom, Z→? (unknown), introduce Y Step 2:Try parent(tom, Y) → Matches parent(tom, bob) → Y = bob Step 3:Try parent(bob, Z) → Matches parent(bob, ann) → Z = ann X = ann ✓ [user requests more...] Step 4:Backtrack — try next match for parent(bob, Z) Matches parent(bob, pat) → Z = pat X = pat ✓ [user requests more...] Step 5:Backtrack — no more parent(bob, ?) → backtrack to step 2 Try next match for parent(tom, Y) → Matches parent(tom, liz) → Y = liz Step 6:Try parent(liz, Z) → No match — liz is not a parent → fail Step 7:Backtrack — no more parent(tom, ?) → false (no more solutions)
Prolog Syntax Rules
Element
Syntax
Example
Atom (constant)
Starts with LOWERCASE
tom, bob, happy, london
Variable
Starts with UPPERCASE or _
X, Y, Person, _
Fact
predicate(args).
likes(mary, food).
Rule
head :- body.
happy(X) :- likes(X, mary).
Query
?- goal.
?- happy(X).
AND (conjunction)
Comma ,
parent(X,Y), female(X)
OR (disjunction)
Semicolon ; or separate rules
Two separate rules
End of clause
Full stop .
Every fact/rule ends with .
Anonymous variable
Underscore _
parent(tom, _). (don't care)
Arithmetic in Prolog
Prolog uses the is operator for arithmetic evaluation. The right-hand side is evaluated as an expression, and the result is unified with the left-hand side.
Handled by the inference engine (search + backtracking)
Explicitly written by programmer (loops, if/else)
State
No mutable state — variables are bound by unification
Mutable variables change over time
Problem type
Excellent for constraint satisfaction, search, symbolic reasoning
Excellent for sequential, numerical, I/O-heavy tasks
How solutions are found
Prolog's engine explores all paths via backtracking
Programmer must write the search algorithm explicitly
Cambridge 9618 exam tip: For Prolog questions: (1) Remember atoms are lowercase, variables are UPPERCASE. (2) Commas between goals mean AND. (3) :- means "if". (4) Every clause ends with a full stop. (5) When tracing backtracking, show each attempt, what it matched with, and when/why it backtracks. (6) For "write a rule" questions: the head comes first, then :-, then the body goals separated by commas. (7) When a query has a variable (e.g. ?- parent(tom, X)), Prolog finds values for X — this is different from a ground query (no variables) which just returns true/false.
⚠️ Common Mistakes
Atoms vs variables — In Prolog, case matters critically. tom is a constant (atom). Tom is a variable. This is the opposite of most languages. Exam questions testing Prolog often catch students writing variables in lowercase or atoms in uppercase.
Forgetting the full stop — Every fact and rule MUST end with a period (full stop). Missing it is a syntax error in Prolog. In exams, include the full stop at the end of every clause.
Confusing unification (=) with arithmetic equality (=:=) — In Prolog, = is unification (pattern matching), not arithmetic. To check if two arithmetic expressions are equal use =:=. For example, 2+3 =:= 5 succeeds, but 2+3 = 5 FAILS because 2+3 and 5 are different terms.
The 'is' operator only evaluates the RIGHT side — X is Y+1 evaluates Y+1 and unifies with X. Y+1 is X does NOT work because the left side is not evaluated. Always put the expression on the right of 'is'.
Backtracking confusion — When asked to trace Prolog execution, remember Prolog tries alternatives in ORDER from top to bottom. Backtracking goes back to the MOST RECENT choice point, not the beginning. Each time the user requests another solution (;), Prolog backtracks from the last success.
🎓
Cambridge 9618 — Complete!
You've reached lesson 82 of 82 — the final lesson of the Cambridge International AS & A Level Computer Science course. All four papers covered.
✅ Notes completed!
▶
Video coming soon
Click slide or press arrow keys to navigate
Worksheet — 4.6.2 Declarative Programming
8 questions · Cambridge 9618 standard
Q1Distinguish between declarative programming and imperative programming. Give one example language for each.[4]
✅ Mark scheme
Declarative programming [2]: the programmer specifies WHAT the desired result or relationship is — the problem is described in terms of facts, rules, and constraints; the execution engine determines HOW to satisfy the specification; no step-by-step algorithm is written by the programmer; example: Prolog [1], or SQL [1 — accept either for the language mark]; Imperative programming [2]: the programmer specifies HOW to solve the problem — a sequence of instructions that change program state step by step; explicit control flow (loops, conditions); the programmer determines the algorithm; example: Python, Java, C [1 — accept any imperative language]. 2 marks per paradigm: 1 for what/how distinction + 1 for example language. Max 4.
Q2The following Prolog facts are given: likes(john, mary). likes(mary, food). likes(mary, wine). likes(john, wine). Write a Prolog rule called 'both_like' such that both_like(X, Y) is true if X likes Y AND john likes Y. Write a query to find all things both Mary and John like. State the results.[4]
✅ Mark scheme
Rule [2]: both_like(X, Y) :- likes(X, Y), likes(john, Y). [1 for correct head (X and Y as variables), 1 for correct body with comma-separated goals and correct use of john (atom, lowercase)]; Query [1]: ?- both_like(mary, Y). [or: ?- both_like(mary, What). — any uppercase variable accepted]; Results [1]: Y = wine. (both Mary and John like wine; Mary also likes food but John does not like food — food is not returned). Full credit: rule correct + query correct + correct result. Note: both_like should be tested with mary as X to find things both mary and john like. Award 1 per correct component.
Q3Given the facts: parent(ann, bob). parent(bob, carol). parent(bob, dave). And the rules: grandparent(X,Z) :- parent(X,Y), parent(Y,Z). Trace the query: ?- grandparent(ann, Who). Show all steps including backtracking.[4]
✅ Mark scheme
Trace [4]: Step 1: query grandparent(ann, Who) — try rule grandparent(X,Z) :- parent(X,Y), parent(Y,Z). Bind X=ann, Z=Who [1]; Step 2: try parent(ann, Y) — matches parent(ann, bob) → Y=bob [1]; Step 3: try parent(bob, Who) — matches parent(bob, carol) → Who=carol [1]; Result: Who = carol ✓; Step 4: user requests more (;) — backtrack on parent(bob, Who) — try next: parent(bob, dave) → Who=dave [1]; Result: Who = dave ✓; Step 5: no more parent(bob, ?) → backtrack to parent(ann, Y) — no more matches → false (no more solutions). Award 1 for each major step: unification/rule application, first match, second match via backtracking, termination. A clear numbered trace showing variable bindings at each step is expected.
Q4In Prolog, explain the difference between an atom and a variable. For each of the following, state whether it is an atom or a variable: (a) london (b) Person (c) X (d) book (e) _Name[4]
✅ Mark scheme
Distinction [2]: atom: a constant symbolic name that starts with a LOWERCASE letter; represents a fixed value; examples: tom, london, happy; atoms cannot be unified with different values — they are what they are [1]; variable: an identifier that starts with an UPPERCASE letter or underscore; represents an unknown that can be bound (unified) to any value during query processing; once bound, a variable holds its value for the rest of that clause [1]; Classification [2]: (a) london — ATOM (starts with lowercase) [½]; (b) Person — VARIABLE (starts with uppercase) [½]; (c) X — VARIABLE (uppercase) [½]; (d) book — ATOM (lowercase) [½]; (e) _Name — VARIABLE (starts with underscore — treated as variable in Prolog; _ alone is anonymous variable) [½]; award 2 for all 5 correct, 1 for 3-4 correct.
Q5Write a Prolog fact and rule database for the following: "A vehicle is a car if it has 4 wheels AND it has an engine. A vehicle is a bicycle if it has 2 wheels AND it does NOT have an engine." Then write a query to find all bicycles.[4]
✅ Mark scheme
Facts [1]: has_wheels(my_bike, 2). has_engine(my_car). has_wheels(my_car, 4). [1 — accept any reasonable fact naming; need at least example facts for wheels and engine]; Car rule [1]: car(X) :- has_wheels(X, 4), has_engine(X). [1 — correct rule with comma AND, uppercase variable, lowercase predicate names, full stop]; Bicycle rule [1]: bicycle(X) :- has_wheels(X, 2), \+ has_engine(X). [1 — \\+ is Prolog negation (not provable); alternative: write two separate facts, one asserting two wheels and one not having engine separately — accept reasonable approaches]; Query [1]: ?- bicycle(X). [1 — uppercase variable, correct predicate name, ? prefix or just the goal]. Note: Cambridge 9618 may simplify this; accept any logically correct approach using the covered facts and rules.
Q6Explain what "unification" and "backtracking" mean in Prolog. How do they work together to find all solutions to a query?[4]
✅ Mark scheme
Unification [2]: the process of matching two terms together; when a query is made, Prolog tries to UNIFY the query with facts and rules in the knowledge base by finding variable bindings that make the terms identical [1]; example: the query parent(tom, X) is unified with the fact parent(tom, bob) by binding X=bob; a variable can be unified with any atom, another variable, or a compound term, as long as the resulting binding is consistent throughout the clause [1]; Backtracking [2]: when the current solution path fails (a goal cannot be satisfied) or when more solutions are requested, Prolog BACKTRACKS to the most recent choice point — the last point where an alternative existed — and tries the next alternative [1]; this systematic exploration continues until either all solutions are found or all alternatives are exhausted; Prolog uses depth-first search with backtracking to explore the entire solution space; together, unification provides the mechanism to match and bind variables, while backtracking provides the search strategy to find ALL satisfying solutions [1]. Award 2 per concept. Max 4.
Q7A Prolog database contains: parent(tom, bob). parent(bob, ann). parent(bob, pat). grandparent(X, Z) :- parent(X, Y), parent(Y, Z). Trace the Prolog evaluation of the query: ?- grandparent(tom, ann). Show each step of unification and any backtracking that occurs.[5]
✅ Mark scheme
Prolog tries to match grandparent(tom, ann) with grandparent(X, Z) :- parent(X, Y), parent(Y, Z) [1]; Unify: X=tom, Z=ann; subgoal 1: parent(tom, Y) [1]; Matches parent(tom, bob), so Y=bob [1]; Subgoal 2: parent(bob, ann) [1]; Matches parent(bob, ann) → both subgoals satisfied → query succeeds: true [1].
Q8Explain the difference between declarative and imperative programming paradigms. Using the example of finding all even numbers in a list, describe how each paradigm would approach the problem — without writing full code, describe the key steps each approach takes.[5]
✅ Mark scheme
Declarative: the programmer describes WHAT result is wanted, not HOW to compute it; the system determines the method [1]; Imperative: the programmer describes HOW to compute the result step by step using control flow and state changes [1]; Declarative (Prolog/functional) approach: define a rule such as "X is even if X MOD 2 = 0" and ask the system to find all X in the list satisfying this — the language engine handles iteration and matching [1]; Imperative approach: write a loop that iterates through the list index by index, tests each element with an IF statement, and appends qualifying elements to a result list [1]; Key difference: declarative removes the need to specify iteration or control flow explicitly; the programmer focuses on the logic of the problem rather than the procedure [1].
Topic Quiz
Question 1 of 10
You scored
out of 10
Card 1 of 9
Click to reveal definition
🎉
All cards reviewed!
Term
Definition
🎯
Mini Test — 4.6.2 Declarative Programming
10 questions · 10 marks · 10 minutes
⏱ 10:00
Section A — Multiple Choice [5 marks]
Q1In Prolog, which of the following is a VARIABLE (not an atom)?
Q2The Prolog symbol :- means:
Q3Given: parent(tom, bob). parent(bob, ann). grandparent(X,Z) :- parent(X,Y), parent(Y,Z). What does ?- grandparent(tom, Who). return?
Q4In Prolog, backtracking occurs when:
Q5In Prolog, commas between goals in a rule body mean:
Section B — Short Answer [5 marks]
Q6What is the difference between a Prolog FACT and a Prolog RULE? Give an example of each.
Mark schemeFact [1]: a statement that is unconditionally true; represents a basic relationship or property that is simply asserted in the knowledge base; example: parent(tom, bob). or likes(mary, food). — no conditions required; Fact syntax: predicate(args). [period at end]; Rule [1]: a conditional statement — the head (conclusion) is true IF all goals in the body (conditions) are satisfied; represents derived knowledge; example: grandparent(X,Z) :- parent(X,Y), parent(Y,Z). — grandparent is defined in terms of parent; Rule syntax: head :- body. [1 mark per component: definition + example; max 4 marks: 2 for fact + 2 for rule]. Mark scheme awards up to 2 per: 1 for definition, 1 for correct syntax example.
Q7Given the facts: likes(alice, reading). likes(alice, tennis). likes(bob, tennis). likes(bob, chess). Write a Prolog rule called common_interest(X, Y) that is true if X and Y both like the same thing Z. Then write a query to find what alice and bob have in common.
Mark schemeRule [2]: common_interest(X, Y) :- likes(X, Z), likes(Y, Z). [1 for correct head with two variables X, Y; 1 for correct body: likes(X,Z) AND likes(Y,Z) with shared variable Z — the comma-AND is essential and Z must appear in both goals]; Query [1]: ?- common_interest(alice, bob). [1 — note: alice and bob are atoms (lowercase)]; Result [1]: Z = tennis (both alice and bob like tennis; reading and chess are liked by only one of them). For the rule: must use a shared variable Z in both body goals to link the common interest. Award marks as shown above.
Q8Explain, with an example, what "unification" means in the context of Prolog query processing.
Mark schemeUnification: the process of making two terms identical by finding suitable variable bindings [1]; when a query is posed, Prolog attempts to MATCH the query pattern against facts and rules by assigning values to variables in a way that makes the terms match [1]; example: query ?- parent(tom, X) is unified with the fact parent(tom, bob) by binding X = bob — the first argument 'tom' already matches (identical atoms), and the variable X is bound to 'bob' to make the second arguments match; once bound, X keeps the value 'bob' for the rest of that clause [1]; if no unification is possible (no fact/rule matches), Prolog backtracks or returns false [1]. Award up to 4 marks: definition (1), explanation of variable binding process (1), worked example (1), consequence of failure (1).
Q9How does logic programming differ from imperative programming in terms of how the programmer writes code and how the computer executes it?
Mark schemeLogic programming: the programmer writes WHAT is true — facts about the problem domain and rules that define relationships; the programmer does NOT specify HOW to find solutions [1]; the execution engine (Prolog's inference engine) determines how to search for solutions, using unification and backtracking automatically [1]; Imperative programming: the programmer writes HOW to solve the problem — an explicit sequence of instructions (loops, conditionals, assignments) that step-by-step compute the result; the programmer is responsible for the algorithm [1]; comparison: in logic programming, adding a new fact changes what is true and the engine automatically incorporates it into all queries; in imperative programming, the programmer would need to modify the algorithm; logic programming is more suited to knowledge-based and constraint problems; imperative is more suited to numerical computation and sequential tasks [1]. Max 4.
Q10In Prolog, every clause must end with a full stop. Every variable must start with an uppercase letter or underscore. What would happen if a programmer wrote: parent(Tom, bob). — and explain whether this is a fact or something else.
Mark schemeparent(Tom, bob). contains Tom with an uppercase T — Tom is a VARIABLE in Prolog, not an atom [1]; bob is lowercase — bob is an atom (constant) [1]; Therefore parent(Tom, bob). is NOT a fact about a specific person named Tom — it is a RULE (or more precisely, a fact containing a variable) that would be interpreted as: "for any value of Tom, Tom is a parent of bob" — which makes no semantic sense as a family fact [1]; the programmer almost certainly intended to write parent(tom, bob). (tom lowercase = constant) to assert that the specific individual tom is a parent of bob; as written, parent(Tom, bob). would match ANY query of the form parent(X, bob) because Tom can be unified with anything [1]. This is a classic error: case matters in Prolog — atoms (constants) are lowercase, variables are uppercase.