Leaving pure logic, carefully
Everything so far has been pure Prolog: facts, rules, unification and backtracking, where each clause means what it says and a predicate answers questions in several directions. Real programs need three more things that pure logic does not give you directly.
- Numbers. Computers are good at arithmetic, and searching for the value of
XinX = 2 + 3by trying every integer would be absurd. Prolog hands arithmetic to the machine, withis/2. - Control. Sometimes you know that once one clause has applied, the others are pointless, or even wrong. The cut, written
!, lets you tell Prolog to stop looking. - Negation. "Cities with no flight to Nairobi" needs a not. Prolog's not, written
\+, means "cannot be proved", which is subtly different from "is false".
All three step outside pure logic: is/2 works in one direction only, a cut can change what a predicate means, and \+ can give different answers depending on goal order. That is why many Prolog books treat them as a separate chapter, and why this lesson spends as much time on how to use them safely as on what they do. Used with care, they are what make Prolog practical; used carelessly, they are where most Prolog bugs live.
Arithmetic: is and comparison
Lesson 2 showed that 1 + 2 is just a tree, +(1, 2). To compute with it, you ask for evaluation explicitly.
Definition— is/2
Result is Expression evaluates Expression as arithmetic and unifies the value with Result. Every variable in Expression must already be bound to a number when the goal runs; Result is usually an unbound variable, but may be a number to check.
Comparison operators evaluate both sides and then compare the numbers. Here they are next to the term comparisons you already know:
| Goal | Meaning |
|---|---|
X =:= Y | The values are equal (2 =:= 2.0 is true) |
X =\= Y | The values differ |
X < Y, X > Y | Less than, greater than |
X =< Y, X >= Y | Less or equal (note =<, not <=), greater or equal |
X == Y | The terms are identical, without evaluating (2 == 2.0 is false) |
X = Y | Unify the terms, without evaluating |
The common arithmetic functions:
| Function | Meaning |
|---|---|
+, -, * | As usual; integers stay integers |
/ | Division. In SWI-Prolog, an exact integer quotient stays an integer (8 / 2 is 4), otherwise you get a float (7 / 2 is 3.5) |
// | Integer division, truncating toward zero |
mod, rem | Remainders: mod takes the sign of the divisor, rem the sign of the dividend |
div | Integer division rounding down, the partner of mod |
^, ** | Powers: ^ on integers gives an exact integer, ** with a float gives a float |
abs, sign, min, max, gcd | As their names say |
sqrt, sin, exp, log, pi, e | Floating-point functions and constants |
round, truncate, floor, ceiling, integer | Float to integer |
Two facts about SWI-Prolog's numbers are worth knowing from the start. Integers are unbounded: 2 ^ 100 is computed exactly, with as many digits as needed, so integer overflow does not exist. Floats are ordinary 64-bit IEEE doubles, with the usual rounding, so 0.1 + 0.2 is not exactly 0.3. (SWI-Prolog also has exact rationals, written like 1r3, for when you need them.)
Arithmetic in practice
A tour of evaluation, comparison and errors
This program evaluates a list of expressions, compares a few pairs, and catches the errors that arithmetic raises. The helper check/2 is the one from lesson 2; report_error/2 uses catch/3, which runs a goal and, if it raises an error matching the pattern error(Formal, _), runs the recovery goal instead.
:- initialization(main, main).
% show(Expr): evaluate the arithmetic expression Expr and print the result.
show(Expr) :-
Value is Expr,
format("~w~t~20|~w~n", [Expr, Value]).
% check(Label, Goal): run Goal once and report whether it succeeded.
check(Label, Goal) :-
( call(Goal)
-> format("~w~t~20|true~n", [Label])
; format("~w~t~20|false~n", [Label])
).
% report_error(Label, Goal): run Goal and print the error it raises, if any.
report_error(Label, Goal) :-
catch(( call(Goal), Result = 'no error' ),
error(Formal, _),
Result = Formal),
format("~w~t~20|~w~n", [Label, Result]).
main :-
forall(member(E, [7 + 3 * 2, 7 / 2, 8 / 2, 7 // 2, -7 // 2,
-7 mod 2, -7 rem 2, 2 ** 0.5, 2 ^ 100,
max(3, 8) - abs(-4), round(2.5), truncate(-2.7),
0.1 + 0.2, gcd(84, 36)]),
show(E)),
T = 6 * 7,
V is T,
format("T = ~w, and V is T gives ~w~n", [T, V]),
check("1 + 2 =:= 3", 1 + 2 =:= 3),
check("1 + 2 == 3", 1 + 2 == 3),
check("2 =:= 2.0", 2 =:= 2.0),
check("2 == 2.0", 2 == 2.0),
check("3 =\\= 4", 3 =\= 4),
report_error("X is Y + 1", _ is _ + 1),
report_error("3 is X + 1", 3 is _ + 1),
report_error("X is foo + 1", _ is foo + 1),
report_error("X is 1 / 0", _ is 1 / 0),
report_error("X is 2 + 3", _ is 2 + 3).7+3*2 13
7/2 3.5
8/2 4
7//2 3
-7//2 -3
-7 mod 2 1
-7 rem 2 -1
2**0.5 1.4142135623730951
2^100 1267650600228229401496703205376
max(3,8)-abs(-4) 4
round(2.5) 3
truncate(-2.7) -2
0.1+0.2 0.30000000000000004
gcd(84,36) 12
T = 6*7, and V is T gives 42
1 + 2 =:= 3 true
1 + 2 == 3 false
2 =:= 2.0 true
2 == 2.0 false
3 =\= 4 true
X is Y + 1 instantiation_error
3 is X + 1 instantiation_error
X is foo + 1 type_error(evaluable,foo/0)
X is 1 / 0 evaluation_error(zero_divisor)
X is 2 + 3 no errorPoints to take from it:
- The expressions in the list are terms until
show/2hands them tois. The same is true ofT = 6 * 7:Tholds the tree, andV is Tevaluates it later. Building an expression as data and evaluating it afterwards is perfectly normal Prolog. -7 // 2is-3(truncated toward zero) while-7 mod 2is1and-7 rem 2is-1. With negative numbers,modandremdiffer. Usemodfor "which residue class" questions such as "is this even?", where you want a result between 0 and the divisor.X is Y + 1withYunbound is an instantiation error: Prolog will not guessY. And3 is X + 1fails in the same way:is/2does not solve equations. That is the price of handing arithmetic to the hardware. Lesson 7 shows the constraint library, in which3 #= X + 1really does findX = 2.foo + 1is a type error:foois not something that can be evaluated. Errors in Prolog are terms like any other,error(Formal, Context), which is whycatch/3can pick them apart with unification.
format/2 has directives for numbers worth learning early: ~d prints an integer (and raises an error if given a float, which catches mistakes), ~2f prints a float with two decimals, ~D groups digits with commas, ~a prints an atom, ~q prints a term quoted so it can be read back, and ~t~20| pads to column 20, as in the table above.
Loops with numbers
Arithmetic loops are recursion with a counter or an accumulator, exactly as in lesson 4. This program follows the Collatz rule (halve an even number, triple an odd one and add one) and asks how many steps a number takes to reach 1, then does some calendar arithmetic:
:- initialization(main, main).
% next(N, Next): one step of the Collatz rule.
next(N, Next) :-
( N mod 2 =:= 0
-> Next is N // 2
; Next is 3 * N + 1
).
% steps(N, S): S applications of the rule take the positive integer N to 1.
steps(N, S) :-
steps(N, 0, S).
steps(N, S0, S) :-
( N =:= 1
-> S = S0
; next(N, N1),
S1 is S0 + 1,
steps(N1, S1, S)
).
% leap(Year): Year is a leap year in the Gregorian calendar.
leap(Year) :-
Year mod 4 =:= 0,
( Year mod 100 =\= 0
; Year mod 400 =:= 0
).
% days_in(Year, Month, Days)
days_in(Year, Month, Days) :-
( Month =:= 2
-> ( leap(Year) -> Days = 29 ; Days = 28 )
; memberchk(Month, [4, 6, 9, 11])
-> Days = 30
; Days = 31
).
main :-
steps(6, S6),
steps(27, S27),
format("6 takes ~w steps, 27 takes ~w~n", [S6, S27]),
aggregate_all(max(S, N), (between(1, 1000, N), steps(N, S)), max(Most, Which)),
format("Below 1000, ~w takes the most steps: ~w~n", [Which, Most]),
findall(Y, (between(1896, 1912, Y), leap(Y)), Leaps),
format("Leap years 1896-1912: ~w~n", [Leaps]),
findall(D, (between(1, 12, M), days_in(2028, M, D)), Days),
sum_list(Days, Total),
format("2028: ~w, ~w days~n", [Days, Total]),
succ(P, 10),
plus(3, Q, 10),
format("succ(P, 10) gives ~w, plus(3, Q, 10) gives ~w~n", [P, Q]).6 takes 8 steps, 27 takes 111
Below 1000, 871 takes the most steps: 178
Leap years 1896-1912: [1896,1904,1908,1912]
2028: [31,29,31,30,31,30,31,31,30,31,30,31], 366 days
succ(P, 10) gives 9, plus(3, Q, 10) gives 7Definition— If-then-else
( Cond -> Then ; Else ) runs Cond once. If it succeeds, Prolog commits to its first solution and runs Then; if it fails, it runs Else. Chains are written ( C1 -> T1 ; C2 -> T2 ; Else ), and ( Cond -> Then ) with no else simply fails when Cond fails.
The layout used above, with (, -> and ; at the start of their lines and the goals indented to match, is the most common Prolog convention, and it makes the branches easy to see. A few things in the program deserve a comment:
steps/3is tail-recursive: the recursive call is the last goal in its branch, so even very long chains run in constant stack space.aggregate_all(max(S, N), Goal, max(Most, Which))finds the largestSand also reports the witness, theNthat produced it.leap/1uses a plain disjunction,( A ; B ), inside a rule. Unlike if-then-else, a disjunction leaves a choice point and can succeed through both branches; here the two branches never both succeed, so it gives at most one answer.memberchk/2is the deterministic cousin ofmember/2: it succeeds at most once, which is what you want for a membership test.succ/2andplus/3are small exceptions to the one-direction rule: they work out whichever argument is missing, for natural numbers. They are handy, but for real equation solving you want the constraint library.
The cut
Definition— Cut
The goal ! always succeeds, and it commits Prolog to the choices made since the current clause was chosen: it discards the remaining clauses of the predicate being defined, and the remaining solutions of the goals to its left in the body. Goals to its right can still backtrack normally.
Picture the search tree of lesson 3: a cut prunes away every untried branch between the point where the clause was entered and the point where the cut ran. That is all it does, and it is enough to make code faster or, if misused, wrong. Watch both happen:
:- initialization(main, main).
colour(red).
colour(green).
colour(blue).
% first_colour(C): the cut keeps only the first solution of colour/1.
first_colour(C) :-
colour(C),
!.
% sign_nocut(N, Sign): no cuts and no guards.
sign_nocut(N, negative) :- N < 0.
sign_nocut(0, zero).
sign_nocut(_, positive).
% sign_bad(N, Sign): cuts added, but the output is bound in the head.
sign_bad(N, negative) :- N < 0, !.
sign_bad(0, zero) :- !.
sign_bad(_, positive).
% sign(N, Sign): tests first, then commit, then bind the output.
sign(N, Sign) :- N < 0, !, Sign = negative.
sign(0, Sign) :- !, Sign = zero.
sign(_, positive).
% sign_ite(N, Sign): the same decision with if-then-else.
sign_ite(N, Sign) :-
( N < 0 -> Sign = negative
; N =:= 0 -> Sign = zero
; Sign = positive
).
% yes_no(Goal): print whether Goal succeeds.
yes_no(Goal) :-
( call(Goal)
-> format("~w~t~28|yes~n", [Goal])
; format("~w~t~28|no~n", [Goal])
).
main :-
findall(C, colour(C), All),
findall(C, first_colour(C), First),
format("colour: ~w, first_colour: ~w~n", [All, First]),
findall(C, once(colour(C)), Once),
format("once(colour(C)): ~w~n", [Once]),
findall(S, sign_nocut(0, S), NoCut),
format("sign_nocut(0, S): ~w~n", [NoCut]),
findall(S, (member(N, [-5, 0, 7]), sign_bad(N, S)), Bad),
format("sign_bad of -5, 0, 7: ~w~n", [Bad]),
yes_no(sign_bad(0, positive)),
yes_no(sign(0, positive)),
yes_no(sign_ite(0, positive)),
yes_no(sign(-3, negative)),
findall(S, sign(0, S), Signs),
format("all answers of sign(0, S): ~w~n", [Signs]).colour: [red,green,blue], first_colour: [red]
once(colour(C)): [red]
sign_nocut(0, S): [zero,positive]
sign_bad of -5, 0, 7: [negative,zero,positive]
sign_bad(0,positive) yes
sign(0,positive) no
sign_ite(0,positive) no
sign(-3,negative) yes
all answers of sign(0, S): [zero]Read it as a story in five versions.
first_colour/1. Aftercolour(C)succeeds withred, the cut throws away the choice point that would have offeredgreenandblue.once(Goal)is the library's name for exactly this, and it is clearer: prefer it.sign_nocut/2is wrong for zero: the third clause, with its anonymous_, also matches 0, sosign_nocut(0, S)answerszeroand thenpositiveon backtracking.sign_bad/2adds cuts, and now asking for the sign of -5, 0 and 7 gives the right answers. But ask the yes-or-no questionsign_bad(0, positive)and it says yes. Why? The second clause's headsign_bad(0, zero)does not unify withsign_bad(0, positive), so its cut is never reached, and Prolog falls through to the catch-all third clause. The cut can only protect you after it has run.sign/2fixes this with a rule experienced programmers follow: do the tests, then cut, then bind the outputs. The head no longer mentions the answer, so every call with 0 reaches the cut.sign_ite/2says the same thing with if-then-else, which is usually the clearest choice: the decision is in one place, and there is no cut to misplace.
Green and red cuts
Programmers distinguish two kinds of cut:
- A green cut removes only choice points that could never lead to another answer. Delete it and the program gives the same answers, just with more wasted work or a leftover choice point. If
sign/2's clauses had exclusive guards (N < 0,N =:= 0,N > 0), its cuts would be green. - A red cut changes the meaning: delete it and the answers change. The cuts in
sign_bad/2andsign/2are red, because the last clause relies on them to exclude the cases already handled.
Red cuts are not forbidden, but they make a clause's meaning depend on the clauses before it, so each clause can no longer be read on its own. Experienced Prolog programmers have settled on a few habits:
- Prefer
( If -> Then ; Else )andonce/1to explicit cuts; they express the same commitment locally. - If you write a cut, put it immediately after the tests that decide the clause, and bind output arguments after it.
- Write a predicate's intended mode in its comment, because cut-based code usually works in one mode only (
sign(+N, -Sign)here). - Where you only need two values to differ, use
dif/2rather than a cut or\+, and keep the predicate pure.
Determinism is the other reason professionals care about cuts. A predicate that leaves a pointless choice point behind is not wrong, but it keeps alive stack frames that last-call optimisation would otherwise free, and it makes the toplevel offer more answers when there are none. Clause indexing removes many such choice points automatically: SWI-Prolog looks at the first argument (and others, when helpful) and skips clauses whose head cannot match, so well-structured code often needs no cut at all.
Negation as failure
Definition— Negation as failure
\+ Goal succeeds if Goal cannot be proved, and fails if it can. It never binds any variable: if Goal succeeds, its bindings are thrown away and \+ fails; if Goal fails, there were no bindings to keep.
The name says how it works. Underneath, \+ is written with a cut: try the goal; if it succeeds, cut and fail; otherwise succeed. As a sketch (the real definition is built in):
not_provable(Goal) :- call(Goal), !, fail.
not_provable(_).Why is this a kind of negation and not logical negation? Because Prolog only knows what it has been told. In lesson 1, grandparent(tunde, X) was false only because the program contained no grandchildren for Tunde. Treating "not known to be true" as "false" is called the closed-world assumption, and it is exactly the assumption a database makes: if a flight is not in the timetable, there is no such flight. Keith Clark gave negation as failure its logical reading in 1978, the same year Raymond Reiter studied the closed-world assumption for databases; Clark showed that it is sound when the program is read as a complete definition of each predicate (its completion).
Here is a small airline, and the two rules for using \+ correctly:
:- initialization(main, main).
% city(C) and flight(From, To): a small, made-up airline.
city(nairobi).
city(accra).
city(cairo).
city(lagos).
city(kigali).
flight(nairobi, accra).
flight(nairobi, cairo).
flight(accra, lagos).
flight(cairo, nairobi).
flight(lagos, nairobi).
% no_flights_out(C): nothing departs from city C.
no_flights_out(C) :-
city(C),
\+ flight(C, _).
% not_to(C, To): C is a city with no direct flight to To.
not_to(C, To) :-
city(C),
C \== To,
\+ flight(C, To).
main :-
findall(C, no_flights_out(C), Quiet),
format("No departures: ~w~n", [Quiet]),
findall(C, not_to(C, nairobi), NotToNairobi),
format("No direct flight to nairobi: ~w~n", [NotToNairobi]),
findall(C, (city(C), \+ flight(C, nairobi)), Bound),
format("city first, then \\+: ~w~n", [Bound]),
findall(C, (\+ flight(C, nairobi), city(C)), Unbound),
format("\\+ first, then city: ~w~n", [Unbound]),
( \+ city(mombasa)
-> format("mombasa is not a city, as far as this program knows~n")
; true
),
findall(X, (dif(X, nairobi), city(X)), Others),
format("dif before city: ~w~n", [Others]),
findall(X, (\+ X = nairobi, city(X)), None),
format("\\+ X = nairobi before city: ~w~n", [None]).No departures: [kigali]
No direct flight to nairobi: [accra,kigali]
city first, then \+: [nairobi,accra,kigali]
\+ first, then city: []
mombasa is not a city, as far as this program knows
dif before city: [accra,cairo,lagos,kigali]
\+ X = nairobi before city: []Rule one: bind the variables first. city(C), \+ flight(C, nairobi) asks, for each city in turn, "is there no flight from this city to Nairobi?", and finds three (Nairobi itself among them, which is why not_to/2 excludes it with \==). Swap the goals and \+ flight(C, nairobi) runs with C unbound. It now asks "is there no flight from anywhere to Nairobi?". There is one, so the negation fails, and the conjunction has no answers at all. The same thing happens to \+ X = nairobi: an unbound X can be unified with nairobi, so the negation fails. The underscore in no_flights_out/1 is fine, by contrast, because there it means exactly what we want: "there is no flight from C to anywhere". Calling \+ on a goal with unbound variables that you meant to be "for each" is called floundering, and the fix is always to generate values first and test afterwards. dif/2 from lesson 2 does not have this problem: it waits until X is known.
Rule two: remember what false means. \+ city(mombasa) succeeds, and the program cheerfully concludes that Mombasa is not a city. It means only that Mombasa is not in this program's list. For a timetable, a payroll or a seating plan, that is exactly right; for open-ended knowledge, such as medical facts or the web, absence of evidence is not evidence of absence, and systems built for that setting (the Semantic Web's description logics, for example) deliberately use an open-world assumption instead.
You have already used negation in disguise. forall(Cond, Action) is defined as \+ ( Cond, \+ Action ): "there is no solution of Cond for which Action fails". That is why forall never binds variables either; it only checks.
Common misconceptions
Misconception
"X = Y + 1 computes something." It builds the term +(Y, 1). Use X is Y + 1, with Y already bound. And X is X + 1 is never right: once X is bound, it is a number that cannot equal itself plus one, so the goal fails. Use a new variable, X1 is X + 1.
Misconception
"is solves equations." It evaluates the right side and unifies. 5 is X + 2 raises an instantiation error rather than finding 3. For arithmetic that works in every direction, use the constraint library of lesson 7.
Misconception
"= and =:= are interchangeable for numbers." = compares terms, so 2 = 2.0 and 3 = 1 + 2 both fail; =:= evaluates, so both comparisons succeed. Use =:= when you mean "the same number".
Misconception
"The cut makes a predicate deterministic, so more cuts are better." A cut only commits to choices made in its own clause, and a misplaced one silently changes the answers, as sign_bad/2 showed. Reach first for exclusive clause heads, if-then-else and once/1.
Misconception
"\+ means logically false." It means "not provable from what this program knows", and it gives correct answers only when the negated goal's variables are bound by the time it runs.
Exercises
Try each question before opening the hints. Every answer about program output was checked by running the program with SWI-Prolog 10.1.
1. Arithmetic, the cut and negation
Warm-upComputationalWhat does this print?
X is 17 // 5, Y is 17 mod 5, format("~w ~w~n", [X, Y])
2. Arithmetic, the cut and negation
Warm-upHumanWhich of these goals succeeds?
3. Arithmetic, the cut and negation
CoreComputationalUsing the lesson's steps/2, what is S after steps(7, S)?
4. Arithmetic, the cut and negation
CoreComputationalGiven
max(X, Y, X) :- X >= Y, !.
max(_, Y, Y).
what happens with the goal max(9, 4, 4)?
5. Arithmetic, the cut and negation
StretchComputationalUsing the lesson's sign/2 (the version with sign(0, Sign) :- !, Sign = zero.), what is S after sign(0.0, S)?
6. Arithmetic, the cut and negation
CoreComputationalWith the lesson's airline, which cities does this goal collect? List them separated by commas.
findall(C, (city(C), C \== nairobi, \+ flight(nairobi, C)), L)
7. Arithmetic, the cut and negation
StretchComputationalWith the lesson's airline, how many elements does L have after
findall(C, (\+ flight(C, kigali), city(C)), L)
8. Arithmetic, the cut and negation
CoreHumanA program about a library contains book/1 facts for every book in its catalogue. The goal \+ book('Things Fall Apart') succeeds. What can you conclude?
Further reading and resources
- SWI-Prolog manual, arithmeticEvery arithmetic function and comparison, integer and float semantics, and the flags that change them.
- SWI-Prolog manual, control predicatesThe cut, if-then-else, soft cut and negation, defined precisely.
- SWI-Prolog manual, formatted writeAll the directives of format/2, such as ~d, ~2f, ~a, ~q and column stops.
- Negation as failure (Wikipedia)Keith Clark's 1978 account of what Prolog's "not" means logically.
- Coding Guidelines for Prolog · Michael A. Covington, Roberto Bagnara, Richard A. O'Keefe, Jan Wielemaker and Simon Price · 2012Advice from experienced Prolog programmers on layout, naming, cuts and determinism, published in Theory and Practice of Logic Programming.
- Closed-world assumption (Wikipedia)Raymond Reiter's assumption that what cannot be shown true is false, and where it fits.