Skip to content
LumenaryAcademy
Practice 55 min

Arithmetic, the cut and negation

Where pure logic meets the machine, evaluating numbers with is, committing to a choice with the cut, and saying "not" in a closed world.

Code tested · 4AI-draftedAwaiting review by a computer scientist
MotivationH

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 X in X = 2 + 3 by trying every integer would be absurd. Prolog hands arithmetic to the machine, with is/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.

DefinitionsH

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:

GoalMeaning
X =:= YThe values are equal (2 =:= 2.0 is true)
X =\= YThe values differ
X < Y, X > YLess than, greater than
X =< Y, X >= YLess or equal (note =<, not <=), greater or equal
X == YThe terms are identical, without evaluating (2 == 2.0 is false)
X = YUnify the terms, without evaluating

The common arithmetic functions:

FunctionMeaning
+, -, *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, remRemainders: mod takes the sign of the divisor, rem the sign of the dividend
divInteger division rounding down, the partner of mod
^, **Powers: ^ on integers gives an exact integer, ** with a float gives a float
abs, sign, min, max, gcdAs their names say
sqrt, sin, exp, log, pi, eFloating-point functions and constants
round, truncate, floor, ceiling, integerFloat 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.)

Worked examplesH

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.

prolog
:- 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).
text
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 error

Points to take from it:

  • The expressions in the list are terms until show/2 hands them to is. The same is true of T = 6 * 7: T holds the tree, and V is T evaluates it later. Building an expression as data and evaluating it afterwards is perfectly normal Prolog.
  • -7 // 2 is -3 (truncated toward zero) while -7 mod 2 is 1 and -7 rem 2 is -1. With negative numbers, mod and rem differ. Use mod for "which residue class" questions such as "is this even?", where you want a result between 0 and the divisor.
  • X is Y + 1 with Y unbound is an instantiation error: Prolog will not guess Y. And 3 is X + 1 fails in the same way: is/2 does not solve equations. That is the price of handing arithmetic to the hardware. Lesson 7 shows the constraint library, in which 3 #= X + 1 really does find X = 2.
  • foo + 1 is a type error: foo is not something that can be evaluated. Errors in Prolog are terms like any other, error(Formal, Context), which is why catch/3 can 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:

prolog
:- 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]).
text
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 7

Definition— 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/3 is 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 largest S and also reports the witness, the N that produced it.
  • leap/1 uses 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/2 is the deterministic cousin of member/2: it succeeds at most once, which is what you want for a membership test.
  • succ/2 and plus/3 are 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.
ExplanationH

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:

prolog
:- 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]).
text
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.

  1. first_colour/1. After colour(C) succeeds with red, the cut throws away the choice point that would have offered green and blue. once(Goal) is the library's name for exactly this, and it is clearer: prefer it.
  2. sign_nocut/2 is wrong for zero: the third clause, with its anonymous _, also matches 0, so sign_nocut(0, S) answers zero and then positive on backtracking.
  3. sign_bad/2 adds cuts, and now asking for the sign of -5, 0 and 7 gives the right answers. But ask the yes-or-no question sign_bad(0, positive) and it says yes. Why? The second clause's head sign_bad(0, zero) does not unify with sign_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.
  4. sign/2 fixes 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.
  5. sign_ite/2 says 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/2 and sign/2 are 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 ) and once/1 to 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/2 rather 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.

DefinitionsH

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):

prolog
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:

prolog
:- 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]).
text
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 misconceptionsH

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

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-upComputational

What 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-upHuman

Which of these goals succeeds?

Choose one

3. Arithmetic, the cut and negation

CoreComputational

Using the lesson's steps/2, what is S after steps(7, S)?

4. Arithmetic, the cut and negation

CoreComputational

Given

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

what happens with the goal max(9, 4, 4)?

Choose one

5. Arithmetic, the cut and negation

StretchComputational

Using 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

CoreComputational

With 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)

Write elements separated by commas. Order and repeats don’t matter — just like in a set!

7. Arithmetic, the cut and negation

StretchComputational

With 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

CoreHuman

A 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?

Choose one

Further reading and resources