Week 2: Notes

anonymous variables

If we write a variable only once in the definition of a predicate, Prolog will issue a warning. For example, suppose that we have this code in family.pl:

parent(katka, radek).
parent(honza, radek).

% is_a_parent(P) is true if P is a parent of somebody.
is_a_parent(P) :- parent(P, X).

Let's try it:

$ pl family.pl
Warning: /home/adam/Desktop/npp/family.pl:9:
Warning:    Singleton variables: [X]
Welcome to SWI-Prolog (threaded, 64 bits, version 8.4.2)

Instead, in this situation it is better to use the anonymous variable '_', which represents a value that we don't care about:

% is_a_parent(P) is true if P is a parent of somebody.
is_a_parent(P) :- parent(P, _).

Then the warning will go away.

We may give a value to an anonymous variable, but Prolog will not report it in a solution:

?- X = a, _ = b, Y = c.
X = a,
Y = c.

If we have multiple anonymous variables in a clause or query, they are independent, so each may have a distinct value:

?- _ = a, _ = b.
true.

integers

A Prolog term may be an integer. Prolog supports integers of arbitrary size. For better readability, we may optionally write underscores when writing an integer:

?- X = 14.
X = 14.

?- X = 123_000_000_000_000_000.
X = 123000000000000000.

arithmetic expressions

Prolog supports arithmetic expressions. However, their behavior is not like in most other languages:

?- X = 2 + 2.
X = 2+2.

?- 2 + 2 = 4.
false.

These results may be surprising at first. We need to understand that the '=' operator in Prolog represents structural equality, and expressions are not evaluated automatically. Thus, the query 'X = 2 + 2' simply says that X is equal to the arithmetic expression (2 + 2), without evaluating that expression. '2 + 2 = 4' is false because (2 + 2) and (4) are different expressions, syntactically speaking.

One way to evaluate an arithmetic expression is to use the 'is' operator:

?- X is 2 + 2.
X = 4.

Prolog has the usual arithmetic operators '+', '-', '*', plus 'div' and 'mod' for integer division and integer modulus. 'div' truncates its result toward negative infinity. The '^' operator represents exponentiation. Operations have the usual precedence, e.g. '*' binds more tightly than '+' or '-'.

?- X is 2 + 3 * 4.
X = 14.

?- X is 20 div 7.
X = 2.

?- X is 20 mod 7.
X = 6.

?- X is -20 div 7.
X = -3.

?- X is 2^20.
X = 1048576.

Arithmetic expressions may call the function abs(X), which computes an absolute value, and also max(X, Y) and min(X, Y), which compute the maximum or minimum of two values:

?- X is abs(-16).
X = 16.

?- X is max(30, min(40, 50)).
X = 40.

The comparison operators <, =<, >, and >= are available. Notice that the less than or equal to operator is written as '=<', not as '<='. This is different from almost every other programming language.

?- 15 < 10.
false.

?- 20 =< 30.
true.

The 'is' operator and the comparison operators above have some significant limitations. 'is' only works from right to left. It will evaluate an arithmetic expression on its right side, which must be fully instantiated before 'is' runs:

?- X is 2 + 2.
X = 4.

?- 2 + 2 is X.
ERROR: Arguments are not sufficiently instantiated

It will evaluate an expression only on the right, not on the left, which leads to some surprises:

?- 4 is 2 + 2.
true.

?- 2 + 2 is 2 + 2.
false.

For this reason, any predicate that uses 'is' is unlikely to work in multiple directions.

Comparison operators such as '<' require that both of their operands be fully instantiated before they run. Thus, the first query below works, but the second will not:

?- X is 5 + 5, X > 7.
X = 10.

?- X > 7, X is 5 + 5.
ERROR: Arguments are not sufficiently instantiated

new-style integer arithmetic

As an alternative to the limited operators described above, we may use new-style integer arithmetic operators, which are based on integer constraints. These new operators are much more general and powerful than their older equivalents.

To enable these operators, you must import the clpfd module. I recommend putting this command into your SWI-Prolog initialization file so that it will automatically run at the beginning of each session:

:- use_module(library(clpfd)).

(Note that you must include the :- prefix at the beginning of the line!). The initialization file is typically at

The location of the file might be somewhat system-dependent. If the path listed above does not work on your system, run this Prolog command to determine the path of the swi-prolog directory where you should place init.pl:

?- absolute_file_name(app_config(.), Dir, [solutions(all)]), !.

The operator #= says that two integer expressions are mathematically equal. It will work from right to left, or from left to right:

?- X #= 2 + 3.
X = 5.

?- 2 + 3 #= X.
X = 5.

?- 2 + 3 #= 3 + 2.
true.

What is more, Prolog can solve many equations written using #= , or report that they have no integer solution:

?- X + 2 #= 5.
X = 3.

?- X * 2 #= 10.
X = 5.

?- X * 2 #= 9.
false.

?- X + 1 #= X.
false.

?- 2 ^ X #= 128.
X = 7.

?- max(X, 3) #= 4.
X = 4.

Some equations may have multiple solutions:

?- X ^ 2 #= 16.
X in -4\/4.

In this result, 'X in -4\/4' means that X is either -4 or 4. The symbol \/ is intended to look like a logical OR.

The integer solver in Prolog has some limitations. It cannot solve a system of linear equations:

?- X + Y #= 10, X - Y #= 2.
2+Y#=X,
X+Y#=10.

It is also unable to solve a quadratic equation:

?- X^2 - X - 2 #= 0.
X in -2..sup,
2+X#=_A,
X^2#=_A,
_A in 0..sup.

Let's write a predicate using integer arithmetic:

sum(X, Y, Z, A) :- X + Y + Z #= A.

It works in any direction:

?- sum(2, 3, 4, X).
X = 9.

?- sum(2, 3, X, 9).
X = 4.

Here's a predicate that computes the maximum of three values:

max3(A, B, C, M) :- M #= max(A, max(B, C)).

It also works multidirectionally:

?- max3(3, 5, 7, N).
N = 7.

?- max3(3, N, 5, 7).
N = 7.

The operator #\= says that two expressions are not mathematically equal. For example:

?- X^2 #= 16.
X in -4\/4.

?- X^2 #= 16, X #\= 4.
X = -4.

new-style integer comparisons

The operators #<, #=<, #> and #>= perform integer comparisons. (Note again the unusual order of the symbols in the #=< operator.) Unlike the older operators <, =<, and so on, these operators work declaratively: they do not require their arguments to be fully instantiated before they run.

Sometimes a set of equations with these operators will have a unique integer solution, or no solutions:

?- 4 #< X, X #< 6.
X = 5.

?- 6 #< X, X #< 4.
false.

Or the solution may be a range of values:

?- 2 #< X, X #< 10.
X in 3..9.

In fact we may enter a range directly as part of an equation:

?- X in 10..30, X in 20..40.
X in 20..30.

The following is entirely equivalent, but requires more typing:

?- 10 #=< X, X #=< 30, 20 #=< X, X #=< 40.
X in 20..30.

A range may have an infinite lower or upper bound:

?- X #> 10.
X in 11..sup.

?- X #< 10.
X in inf..9.

Notice that in ranges sup ("superior") means positive infinity, and inf ("inferior") means negative infinity, somewhat confusingly.

Let's write a predicate that is true if its integer arguments are the lengths of sides of a right triangle:

% X, Y, Z are sides of a right triangle, Z is the hypotenuse.
right_triangle(X, Y, Z) :- X #> 0, Y #> 0, Z #> 0, X^2 + Y^2 #= Z^2.

It works multidirectionally, and only allows integer solutions:

?- right_triangle(5, 12, H).
H = 13.

?- right_triangle(5, S, 13).
S = 12.

?- right_triangle(5, 6, H).
false.

factorial predicate

As a more advanced example, let's write a recursive predicate that can compute the factorial of an integer. Here is a first attempt:

% base case: 0! = 1
factorial(0, 1).    

% recursive case: if N > 0, then N! = N * (N - 1)!
factorial(N, F) :- N #> 0, N1 #= N - 1, factorial(N1, F1), F #= N * F1.

It works in a forward direction:

?- factorial(5, F).
F = 120

In the reverse direction, Prolog finds a solution but then the predicate fails to terminate:

?- factorial(N, 120).
N = 5 ;
<hang>

Prolog is searching for more solutions, and does not realize that there are no more.

We may help termination by modifying the factorial predicate above so that the recursive call comes last:

% base case: 0! = 1
factorial(0, 1).    

% recursive case: if N > 0, then N! = N * (N - 1)!
factorial(N, F) :- N #> 0, N1 #= N - 1, F #= N * F1, factorial(N1, F1).

This ordering may seem strange, because we are specifying the constraint 'F #= N * F1' even before making the recursive call, which itself may determine the value of F1! However, it actually only helps Prolog to know about this constraint earlier. Now the predicate terminates even in the reverse direction:

?- factorial(N, 120).
N = 5

lists

Lists are a fundamental data type in Prolog.

To form a list, we write a series of values inside square brackets:

?- L = [red, blue, green].
L = [red, blue, green].

?- L = [2, 4, 6, 8].
L = [2, 4, 6, 8].

Prolog is a dynamically typed language, so a list may even contain various types of values:

?- L = [red, 4, blue, 10].
L = [red, 4, blue, 10].

Two lists are equal if they have the same length and the same elements. Prolog can solve equations involving lists:

?- [3, 4] = [X, Y].
X = 3,
Y = 4.

?- [3, 4] = X.
X = [3, 4].

?- [X, Y] = 5.
false.

?- [3, X] = [Y, 4].
X = 4,
Y = 3.

?- [X, Y] = [5, X].
X = Y, Y = 5.

?- [3, 4] = [_, X].
X = 4.

?- [X, Y] = [Y, X].
X = Y.

Solving equations between lists (or more complex syntactic structures) is called unification, and is a fundamental part of how Prolog works. The solution to a unification problem is a substitution, which is a mapping from variables to terms. In more advanced classes you may study algorithms for performing unification.

Here are a few simple predicates on lists:

% true if L is an empty list.
is_empty([]). 

% true if L is a list with a single element.
one_element([_]).

% pair_of(X, L) - true if L has 2 elements and both elements are X.
pair_of(X, [X, X]).

Let's try a few queries:

?- pair_of(3, L).
L = [3, 3].

?- pair_of(X, [3, 3]).
X = 3.

?- pair_of(X, [3, 4]).
false.

A term specifying a list may optionally include a vertical bar (|). In this case, the element after the vertical bar is a list containing all remaining items. For example, all of the following are equivalent:

[3, 4, 5]

[3 | [4, 5]]
          
[3, 4 | [5]]
          
[3, 4, 5 | []]

To put it differently, [A | L] is A prepended to the list L. [A, B | L] is A and B prepended to the list L.

Let's try some queries including this list syntax:

?- L = [1 | [2, 3, 4]].
L = [1, 2, 3, 4].

?- [1, 2, 3, 4] = [X | L].
X = 1,
L = [2, 3, 4].

?- [1, 2, 3, 4] = [X, Y | L].
X = 1,
Y = 2,
L = [3, 4].

?- [1, 2, 3, 4] = [A, B, C, D | L].
A = 1,
B = 2,
C = 3,
D = 4,
L = [].

?- [1, 2, 3, 4] = [A, B, C, D, E | L].
false.

?- [X | L] = [A, B, C].
X = A,
L = [B, C].

Note that the pattern [_ | _] matches any non-empty list, because it consists of some element prepended to some list (which may be empty). Similarly, the pattern [_, _ | _] matches any list with at least two elements:

?- [_ | _] = [].
false.

?- [_ | _] = [4].
true.

?- [_, _ | _] = [4].
false.

By the way, there is no built-in syntax for appending an element to a list. That's because a Prolog list resembles a linked list internally: the head is directly accessible, and prepending a value is a constant-time operation. Accessing the last element takes O(N) if there are N elements in the list.

We may now write more list predicates:

% non-empty(L) - L is not the empty list.
non_empty([_ | _]).

% first_elem(X, L) - true if X is the first element of the list L.
first_element(X, [X | _]).

Let's try using first_element():

?- first_element(X, [2, 3, 4]).
X = 2.

?- first_element(2, [X, Y, Z]).
X = 2.

We may also write recursive predicates on lists. Here's a predicate that can find the last element of a list:

% last_elem(L, X): true if X is the last element of L.
last_elem([X], X).
last_elem([_ | L], X) :- last_elem(L, X).

Let's try it:

?- last_elem([2, 3, 4], X).
X = 4

?- last_elem(L, 5).
L = [5] ;
L = [_, 5] ;
L = [_, _, 5] ;
L = [_, _, _, 5] ;
...

Here's a predicate that tells whether an element belongs to a list:

% member(X, L): true if X is a member of the list L.
member(X, [X | _]).
member(X, [_ | L]) :- member(X, L).

We may use this predicate in many ways:

?- member(X, [4, 6, 8]).
X = 4 ;
X = 6 ;
X = 8

?- member(X, [4, 6, 8]), member(X, [4, 5, 7]).
X = 4 

?- L = [_, _, _], member(a, L), member(b, L), member(c, L).
L = [a, b, c] ;
L = [a, c, b] ;
L = [b, a, c] ;
L = [c, a, b] ;
L = [b, c, a] ;
L = [c, b, a]

Here's a predicate to compute the sum of the elements in a list:

% sum(L, S): true if the integer sum of L is S.
sum([], 0).
sum([X | L], S) :- S #= X + S1, sum(L, S1).

It works in both directions:

?- sum([2, X, 4], 10).
X = 4.

?- sum([2, X, 4], 12).
X = 6.

Here is another useful predicate:

% append(L, M, N) is true if we can append L and M to make N.
append([], L, L).
append([X | L], M, [X | N]) :- append(L, M, N).

In fact both member() and append() are built into Prolog's standard library.