Most of the languages we’ve considered so far in this text have followed the imperative programming model, where a computation is decomposed into individual statements that modify the state of the program. These languages have also been procedural, grouping statements into subroutines that are then called explicitly.
We have also seen the functional programming model, which decomposes a computation into functions that are closely related to those in mathematics. In such a model, programming is done with expressions that avoid side effects. We have also considered specific languages that provide a mix of the functional and imperative paradigms.
Functional programs are declarative, since they declare a relationship between the inputs and outputs of a function. We turn our attention to other models that are declarative, including those that express computation using logical relations, constraints, and dependencies.
Whereas functional programming is based on the theoretical foundations of \(\lambda\)-calculus, logic programming is based on the foundation of formal logic. More specifically, it is based on first-order predicate calculus, which expresses quantified statements such as:
This states that for every value
X, over some implicit universe of
values, there is some value
Y such that either
P(X) is true or
Q(Y) is false or both. This specific statement can also be written
in the form of an implication:
The implication \(a ~\Longrightarrow~ b\) is equivalent to \(\neg a ~\vee~ b\).
In most logic languages, a program is specified in terms of axioms that are assumed to be true, and a programmer specifies a goal that the system should attempt to prove from the set of axioms. An axiom is usually written in the form of a Horn clause, which has the following structure:
H :- B1, B2, ..., BN
:- symbol specifies a reverse implication, and the comma is
used for conjunction. The equivalent form in predicate calculus is:
In the Horn clause above,
H is the head of the clause, while
B1, B2, ..., BN is the body. In natural language, the Horn
clause is stating that if
B1 is true, and
B2 is true, …, and
BN is true, then it must be that
H is also true. (Quantifiers
are implicit in a Horn clause, though we will not discuss the details
The individual elements of a Horn clause, such as
above, are called terms. A term may be a variable, an atom in the
form of a symbol, or a compound term, such as a predicate applied to
some arguments which are themselves terms.
A set of Horn clauses establishes relations among data, which we can then use to query whether a relation holds or what pieces of data satisfy a particular relation.
As a concrete example, consider the following clauses that represent familial relationships:
parent(P, C) :- mother(P, C). % rule 1 parent(P, C) :- father(P, C). % rule 2 sibling(A, B) :- parent(P, A), parent(P, B). % rule 3
Here, we have stated three rules. The first establishes that if
P is the mother of
P is also a parent of
The second states that if
P is the father of
also a parent of
C. The last rule states that if
P is a parent
P is also a parent of
We can state some specific relationships as facts, which are Horn clauses without a body and thus are unconditionally true:
mother(molly, bill). % fact 1 mother(molly, charlie). % fact 2
We can give the logic interpreter a query of the form
S). The interpreter will then attempt to solve this query using a
process known as resolution, which applies rules to existing
information. Part of this process is unification, which connects
terms that match. One possible resolution sequence for the query
sibling(bill, S) -> parent(P, bill), parent(P, S) (rule 3) -> mother(P, bill), parent(P, S) (rule 1) -> mother(molly, bill), parent(molly, S) (fact 1) -> mother(molly, bill), mother(molly, S) (rule 1) -> mother(molly, bill), mother(molly, charlie) (fact 2)
The end result in this sequence would be that
S = charlie.
In the process above, the third step unifies the term
mother(molly, bill), which in turn unifies
molly. This unification is reflected in all occurrences of
resulting in the second term becoming
Unification is a generalized form of variable binding, except that
full terms can be unified with each other rather than just binding
variables to values.
In our formulation of familial relationships, however, there is
nothing preventing the resolution engine from applying
bill) in resolving
mother(molly, S), so another perfectly valid
solution is that
S = bill. We will see later how to fix this
specific problem in Prolog.
Before we proceed further in our exploration of logic programming, let us introduce a concrete programming language to work with. Among logic languages, Prolog is by far the most popular, and many implementations are available. For the purposes of this text, we will use a specific interpreter called SWI-Prolog, of which there is also a web-based version.
The syntax we used above is actually that of Prolog. A Prolog program consists of a set of Horn clauses that are assumed to be true. A clause is composed of a head term and zero or more body terms, and a term may be atomic, compound, or a variable. An atomic term may be an atom, which is either a Scheme-like symbol or a quoted string. The following are all atoms:
hello =< + 'logic programming'
If an atom starts with a letter, then that letter must be lowercase.
hEllo is an atom, but
Hello is not. Numbers, which can
be integer or floating-point, are also atomic terms.
Variables are identifiers that begin with a capital letter. Thus,
Hello is a variable, as are
Compound terms consist of a functor, which is itself an atom, followed by a list of one or more argument terms. The following are compound terms:
pair(1, 2) wizard(harry) writeln(hello(world))
A compound term is interpreted as a predicate, meaning that it has a
truth value, when it occurs as the head term or one of the body terms
of a clause, as well as when it is the goal query. Otherwise, it is
generally interpreted as data, as in
While the syntax of a compound term resembles that of a function call in many imperative or functional languages, Prolog does not have functions, so a compound term is never interpreted as such.
A Horn clause with no body is a fact, since it is always true. Thus, the following are facts:
mother(molly, bill). mother(molly, charlie).
Notice the period that signifies the end of a clause.
A Horn clause with a body is called a rule, and it consists of a head
term, the reverse implication symbol (
:-), and one or more body
terms, separated by commas. The comma signifies conjunction so that
the head is true when all the body terms are true. The following are
parent(P, C) :- mother(P, C). sibling(A, B) :- parent(P, A), parent(P, B).
The first rule states that if
mother(P, C) is true, then
parent(P, C) is also true. The second rule states that if both
parent(P, A) and
parent(P, B) are true, then
A program is composed of a set of facts and rules. Once these have been established, we can query the Prolog interpreter with a a goal predicate. The interpreter will attempt to establish that the goal is true, and if it contains variables, instantiate them with terms that result in the satisfaction of the goal. If the query succeeds, the interpreter reports success, along with the terms that the variables unified with in order to establish the result. If more than one solution may exist, we can ask for the next one using a semicolon in most interpreters. If we ask for a solution and no more exist, the interpreter reports failure.
As an example, consider the query
sibling(bill, S). Loading a file
containing the two facts and rules above will result in the
?- (For now, we have elided the
that depended on
father, since we haven’t established any
father facts and our Prolog interpreter will report an error as a
?- sibling(bill, S). S = bill ; S = charlie.
At the prompt, we’ve entered the query followed by a period to signify
the end of the query. The interpreter reports
S = bill as the
first result, and we have the option of entering a semicolon to search
for another or a period to end the query. We enter a semicolon, and
the interpreter finds and reports
S = charlie, as well as a period
to indicate its certainty that no more solutions exist.
The actual order in which Prolog searches for a result is
deterministic, as we will see shortly. Thus, the query will always
S = bill as its first result and
S = charlie as its
Compound terms, which can relate multiple individual terms, allow us
to represent data structures. For example, we can use the compound
pair(A, B) to represent a pair composed of
The term will not appear on its own as a head or body term, so it will
be treated as data. We can then define relations for lists as
cons(A, B, pair(A, B)). car(pair(A, _), A). cdr(pair(_, B), B). is_null(nil).
In the clauses above, an underscore represents an anonymous variable.
Many Prolog implementations will raise a warning if a variable is used
only once in a clause, so we use anonymous variables to avoid that.
nil as our representation for an empty list. We can then
make queries on lists as follows:
?- cons(1, nil, X). X = pair(1, nil). ?- car(pair(1, pair(2, nil)), X). X = 1. ?- cdr(pair(1, pair(2, nil)), X). X = pair(2, nil). ?- cdr(pair(1, pair(2, nil)), X), car(X, Y), cdr(X, Z). X = pair(2, nil), Y = 2, Z = nil. ?- is_null(nil). true. ?- is_null(pair(1, pair(2, nil))). false.
In the fourth example, we’ve used conjunction to obtain the cdr of the original list, as well as the car and the cdr of the result.
As in Scheme, lists are a fundamental data structure in Prolog, so Prolog provides its own syntax for lists. A list can be specified by placing elements in square brackets, separated by commas:
 [1, a] [b, 3, foo(bar)]
A list can be decomposed into a number of items followed by a rest, much like the period in Scheme, using a pipe:
?- writeln([1, 2 | [3, 4]]). % similar to (1 2 . (3 4)) in Scheme [1,2,3,4] true.
We can use this syntax to write rules on lists. For example, a contains predicate is as follows:
contains([Item|_], Item). contains([_|Rest], Item) :- contains(Rest, Item).
The first clause asserts that a list whose first element is
Item. The second clause states that a list contains
Item if the remaining list, excluding the anonymous first item,
?- contains(, a). false. ?- contains([a], a). true . ?- contains([b, c, a, d], a). true .
Prolog provides numbers, as well as comparison predicates on numbers. For convenience, these predicates may be written in infix order:
?- 3 =< 4. % less than or equal true. ?- 4 =< 3. false. ?- 3 =:= 3. % equal (for arithmetic) true. ?- 3 =\= 3. % not equal (for arithmetic) false.
Prolog also provides arithmetic operators, but they merely represent
compound terms. Thus,
3 + 4 is another means of writing the
+(3, 4). If we attempt to unify this with 7 using
the explicit unification operator
=, it will fail:
?- 7 = 3 + 4. false.
Similarly, if we attempt to unify a variable with an arithmetic expression, it will be unified with the compound term itself:
?- X = 3 + 4. X = 3+4.
Comparison operators, however, do evaluate the arithmetic expressions in their operands::
?- 7 =:= 3 + 4. true. ?- 2 + 5 =:= 3 + 4. true. ?- 4 < 3 + 2. true.
In order for the operands to be evaluated, variables in the operands must be instantiated with numeric values. A comparison cannot be applied to an uninstantiated variable:
?- X =:= 3 + 4. ERROR: Arguments are not sufficiently instantiated
is operator is defined to unify its first argument
with the arithmetic result of its second argument, allowing the first
argument to be an uninstantiated variable:
?- 7 is 3 + 4. true. ?- X is 3 + 4. X = 7. ?- X is 3 + 4, X =:= 7. X = 7. ?- X is 3 + 4, X = 7. X = 7.
In the third example,
X is unified with 7, the result of adding 3
and 4. Since
X is now instantiated with 7, it can be compared
to 7. In the fourth example,
X is 7 so it unifies with the
We can use this to define a length predicate on our list representation above:
len(nil, 0). len(pair(_, B), L) :- len(B, M), L is M + 1.
L is unified with the arithmetic result of adding 1 to
M. This must occur after the recursive application of
M is sufficiently instantiated to be able to perform
arithmetic on it. Then:
?- len(nil, X). X = 0. ?- len(pair(1, pair(b, nil)), X). X = 2.
Prolog provides several predicates that perform input and output.
We’ve already used the
writeln predicate, which writes a term to
standard out and then writes a newline. The
write predicate also
writes a term to standard out, but without a trailing newline:
?- X = 3, write('The value of X is: '), writeln(X). The value of X is: 3 X = 3.
We will not discuss the remaining I/O routines here.
Unification and Search¶
The core computational engine in Prolog revolves around unification and search. The search procedure takes a set of goal terms and looks for a clause that has a head that can unify with one of the terms. The unification process can recursively unify subterms, which may instantiate or unify variables. If the current term unifies with the head of a clause, then the body terms, with variables suitably instantiated, are added to the set of goal terms. The search process succeeds when no more goal terms remain.
This process of starting from goal terms and working backwards, replacing heads with bodies, is called backward chaining. A logic interpreter may use forward chaining instead, which starts from facts and works forward to derive the goal. However, Prolog is defined to use backward chaining.
The unification rules for two terms in Prolog are as follows:
An atomic term only unifies with itself.
An uninstantiated variable unifies with any term. If the other term is not a variable, then the variable is instantiated with the value of the other term. If the other term is another variable, then the two variables are bound together such that if one of them is later instantiated with a value, then so is the other.
A compound term unifies with another compound term that has the same functor and number of arguments, and only if the arguments of the two compound terms also unify.
As stated by the first rule, the atomic term 1 only unifies with 1,
and the term
abc only unifies with
The second rule states that a variable
X unifies with a
non-variable by instantiating it to the given value. This essentially
means that all occurrences of the variable are replaced with the given
X unifies with 3 by instantiating
X with 3,
foo(1, 3) by instantiating it with
foo(1, 3), and
Z unifies with
foo(A, B) by instantiating it with
A variable unifies with another variable by binding them together.
X unifies with
Y, and if
Y is later instantiated
with 3, then
X is also instantiated with 3.
The last rule states that a compound term such as
foo(Y, 3) by recursively unifying the arguments, such
Y is instantiated with 1 and
X with 3.
Care must be taken in the search process to treat variables that appear in independent contexts as independent, even if they have the same name. Thus, given the clause:
foo(X, Y) :- bar(Y, X).
and the goal
foo(3, X), the variable
X should be treated as
distinct in the contexts of the goal and the clause. One way to
accomplish this is renaming before applying a rule, analogous to
\(\alpha\)-reduction in \(\lambda\)-calculus:
foo(X1, Y1) :- bar(Y1, X1).
Thus, unifying the goal
foo(3, X) with the head
X1 = 3 and
Y1 = X, resulting in the subsequent goal
Search Order and Backtracking¶
In pure logic programming, the order in which clauses are applied and body terms are resolved doesn’t matter as long as the search process terminates. However, since Prolog has side effects and non-pure operations, it specifies a well-defined order for both. In particular, clauses for a predicate are attempted to be applied in program order, and terms in a conjunction are resolved from left to right. This provides the programmer with some control over how computation proceeds, which can be used to improve efficiency as well as sequence side effects.
A search process that goes down one path may end up in a dead end, where no clauses can be applied to a goal term. This should not immediately result in failure, since changing a previous decision made by the search may lead to a solution. Thus, the search process performs backtracking on failure, or even on success if a user requests more solutions. This reverts the search process to the last choice point with remaining options, at which a different choice is made about which clause to apply.
As an example, consider the following clauses:
sibling(A, B) :- mother(P, A), mother(P, B). mother(lily, harry). mother(molly, bill). mother(molly, charlie).
Suppose the goal is
sibling(S, bill). Then the search tree is as
in Figure 28.
The search will first unify
sibling(S, bill) with the goal term
sibling(A, B), binding
A together and instantiating
bill. We use the notation
S = A to denote that
A are bound together, as in
Prolog will then add the body terms to its set of goals, so that
mother(P, A) and
mother(P, B) need to be satisfied. It then
searches for a solution to
mother(P, A), under an environment in
A are bound together and
B is instantiated
bill. There are several clauses that can be applied to
mother(P, A), introducing a choice point. Prolog attempts
to apply clauses in program order, so the first choice the search
engine will make is to unify
mother(P, A) with
harry), as shown in Figure 30.
A, and therefore
bound together, with
lily. Then only the
mother(P, B) remains, and since multiple clauses can be
applied, another choice point is introduced. The first choice is to
mother(P, B) with
mother(lily, harry), as demonstrated
in Figure 31.
This unification fails, since it requires
B to be unified with
B is currently instantiated with the atom
bill, and two atoms only unify if they are the same, so that
harry do not unify. The unification failure causes
the search engine to backtrack to the previous choice point, so that
it instead attempts to unify
mother(P, B) with
bill). Figure 32 illustrates this.
This unification also fails, since it requires
lily, to be unified with
molly. The search
backtracks once again, trying to unify
mother(P, B) with
mother(molly, charlie), as shown in
Again, the unification fails, so the search backtracks. At this point,
it has exhausted all the choices for
mother(P, B), so it
backtracks further to the preceding choice point. Now, it makes the
choice of unifying
mother(P, A) with
mother(molly, bill), as
illustrated in Figure 34.
bill. Then, as shown in Figure 35, the
search attempts to find a solution for
mother(P, B), first
attempting to unify it with
This fails, since
P = molly cannot unify with
lily. Thus, the
search backtracks to the previous choice point, attempting to unify
mother(P, B) with
Figure 36 demonstrates this.
This succeeds. No more goal terms remain, so the query succeeds with a
S = bill.
We can proceed to ask the interpreter for more solutions, which
continues the search at the last choice point. One more choice
remains, to unify
mother(P, B) with
mother(molly, charlie), as
shown in Figure 37.
However, this fails, so the search backtracks to the preceding choice
mother(P, A) with
mother(molly, charlie), as
illustrated in Figure 38.
Continuing the search with
P instantiated with
charlie reaches another choice point for
mother(P, B). As Figure 39 demonstrates,
the first choice fails.
However, the second choice of unifying
mother(P, B) with
mother(molly, bill) succeeds, as shown in
Thus, we have another solution of
S = charlie. We can then ask for
another solution, resulting in the search engine trying the last
mother(P, B), as demonstrated in
This choice fails. At this point, all choice points have been exhausted, so the interpreter reports that no more solutions can be found. The full interpreter interaction is as follows, reflecting the search process above:
?- sibling(S, bill). S = bill ; S = charlie ; false.
The Cut Operator¶
By default, Prolog considers each possible alternative in turn when it
reaches a choice point. However, Prolog provides the cut operator,
!, to eliminate choice points associated with the
current predicate. For example, recall the
contains([Item|_], Item). contains([_|Rest], Item) :- contains(Rest, Item).
A query such as
contains([1, 2, 3, 4], 2) introduces a choice
point as to which clause to unify with the goal. The first choice
contains([1, 2, 3, 4], 2) cannot unify with
contains([Item|_], Item). However, the second choice succeeds, so
that we have a new goal term of
contains([2, 3, 4], 2). Here
another choice point occurs, and the first choice succeeds, with
Item instantiated with 2 and
_ instantiated with
Since no goal terms remain, the query as a whole succeeds. However,
the interpreter still has an unexplored choice available, so it will
report that more solutions may exist, requiring us to manually either
continue the query with a semicolon or end it with a dot:
?- contains([1, 2, 3, 4], 2). true ; false.
Instead, we can add the cut operator to tell the interpreter to stop
searching for alternatives once it has found a solution for
contains([1, 2, 3, 4], 2):
?- contains([1, 2, 3, 4], 2), !. true.
We can similarly rewrite
contains to eliminate choice points upon
contains([Item|_], Item) :- !. contains([_|Rest], Item) :- contains(Rest, Item).
Here, as soon as a goal term unifies with
Item), the choice point of which
contains clause to unify with
that goal term is eliminated. Thus, only one solution is found:
?- contains([1, 2, 3, 4], 2). true.
On the other hand, the fact that the cut operator prevents other choices from being considered can result in queries that previously succeeded to now fail:
?- contains([1, 2, 3, 4], X), X = 3. false.
Here, the first goal term succeeds by instantiating
X with 1, and
the cut operator prevents other choices for
X from being
X, now instantiated as 1, fails to unify with 3
in the second goal term.
Given the potential negative consequences of eliminating choice points, using the cut operator is often considered bad practice, so that it should be avoided in most cases.
The search above for
sibling(S, bill) produced the undesirable
S = bill. In order to eliminate results from consideration,
Prolog provides a limited form of negation. For instance, we can
sibling rule as:
sibling(A, B) :- A \= B, mother(P, A), mother(P, B).
This states that
A must not be unifiable with
our query will now fail completely:
?- sibling(S, bill). false.
This is because when the body term
A \= B is reached,
B is instantiated with
unification rules above allow an uninstantiated variable to unify with
A can unify with
B by instantiating
A is unifiable with
B, the goal term
On the other hand, if we write the rule as follows:
sibling(A, B) :- mother(P, A), mother(P, B), A \= B.
then our query succeeds:
?- sibling(S, bill). S = charlie .
This is because
B are instantiated as atoms by the time
they get to the last term, and we can assert that two atoms not unify.
Prolog also provides an explicit negation predicate,
\+. We can
therefore query whether
bill are not siblings:
?- \+(sibling(harry, bill)). true.
Unfortunately, we cannot obtain a more general result from the search
engine, such as asking it to find someone who is not a sibling of
?- \+(sibling(S, bill)). false.
This is because negation in Prolog is handled by attempting to prove
the term being negated, and only if the proof fails is the negation
true. However, the query
sibling(S, bill) does indeed succeed with
S = charlie, so negation results in false.
Thus, while Prolog does provide negation, it is of limited use. This is not a deficiency in Prolog itself, but rather follows from the limits of the logic-programming paradigm as a whole, which cannot provide the full expressiveness of first-order predicate calculus.
We conclude with some more interesting examples expressed in the logic paradigm.
Suppose we wish to find a seven digit number such that the first digit is the count of zeroes in the digits of the number, the second digit is the count of ones, and so on. Using Prolog, we can express this computation as follows. We will represent our results as a list of digits. First, we define a predicate to count the occurrences of a particular numerical value in a list:
count(_, , 0). count(Item, [Item|Rest], Count) :- count(Item, Rest, RestCount), Count is RestCount + 1. count(Item, [Other|Rest], Count) :- Item =\= Other, count(Item, Rest, Count).
The first rule states that an arbitrary item occurs zero times in an empty list. The second states that if a value is the first item in a list, then the number times it occurs in the list is one more than the number of times it appears in the rest of the list. The last rule states that if a value is not equal to the first item, then its number of occurrences is that same as the number of times it appears in the rest of the lest.
Next, we define facts to restrict the values of a digit:
is_digit(0). is_digit(1). is_digit(2). is_digit(3). is_digit(4). is_digit(5). is_digit(6).
Finally, we define a predicate to compute our result:
digits(M) :- M = [N0, N1, N2, N3, N4, N5, N6], is_digit(N0), is_digit(N1), is_digit(N2), is_digit(N3), is_digit(N4), is_digit(N5), is_digit(N6), count(0, M, N0), count(1, M, N1), count(2, M, N2), count(3, M, N3), count(4, M, N4), count(5, M, N5), count(6, M, N6).
We start by unifying the argument
Mwith a list of seven items. We then specify that each item must be a digit. Finally, we require that the the first item be the count of zeroes in the list, the second the count of ones, and so on.
Entering our query, we get the sole result:
?- digits(N). N = [3, 2, 1, 1, 0, 0, 0] ; false.
We can proceed to write a predicate that relates a list of digits to an actual number:
digits_number(, 0). digits_number([First|Rest], N) :- digits_number(Rest, RestNumber), length(Rest, RestLength), N is First * 10 ^ RestLength + RestNumber.
An empty list is related to zero. Otherwise, we compute the number represented by the list excluding its first item, as well of the length of that list. Then the number representing the total list is the number of the smaller list plus the multiple of the power of 10 represented by the first digit. Then:
?- digits(N), digits_number(N, M), !. N = [3, 2, 1, 1, 0, 0, 0], M = 3211000.
The Tower of Hanoi is a classic puzzle that consists of three rods and a set of \(N\) discs of different sizes that slide onto a rod. The puzzle starts with discs in ascending order from top to bottom on a single rod, and the goal is to move the entire stack to another rod by moving one disc at a time. It is prohibited to place a larger disc on top of a smaller one. The solution is to recursively move the \(N-1\) smaller discs to the third rod, move the remaining, largest disc to the second rod, and then to recursively move the other \(N-1\) discs to the second rod.
We can express this computation in Prolog as follows, using the
writelnpredicates to print a move to standard output:
move(Disc, Source, Target) :- write('Move disc '), write(Disc), write(' from '), write(Source), write(' to '), writeln(Target). hanoi(1, Source, Target, _) :- move(1, Source, Target). hanoi(NumDiscs, Source, Target, Temporary) :- M is NumDiscs - 1, hanoi(M, Source, Temporary, Target), move(NumDiscs, Source, Target), hanoi(M, Temporary, Target, Source).
movepredicate, given a disc and source and target rods, merely writes out the move to standard output. The
hanoipredicate relates a number of discs and three rods, a source rod, a target rod, and a temporary rod. The base case is when there is one disc, and that disc can be moved directly from source to target. The second
hanoirule is the recursive case, which requires is recursively move all but the largest disc to the temporary rod, move the largest disc to the target rod, and then move the remaining discs from the temporary to the target rod. Since Prolog solves the body terms in order, the moves will occur in the right order.
The follows is the result of a query with \(N = 4\):
?- hanoi(4, a, b, c). Move disc 1 from a to c Move disc 2 from a to b Move disc 1 from c to b Move disc 3 from a to c Move disc 1 from b to a Move disc 2 from b to c Move disc 1 from a to c Move disc 4 from a to b Move disc 1 from c to b Move disc 2 from c to a Move disc 1 from b to a Move disc 3 from c to b Move disc 1 from a to c Move disc 2 from a to b Move disc 1 from c to b true .
The quicksort algorithm sorts a list by choosing a pivot, often the first item, partitioning the remaining list into elements that are less than and greater than or equal to the pivot, recursively sorting the partitions, and then appending them. The following Prolog code expresses this:
quicksort(, ). quicksort([Pivot|Rest], Sorted) :- partition(Pivot, Rest, Smaller, GreaterOrEqual), quicksort(Smaller, SortedSmaller), quicksort(GreaterOrEqual, SortedGreaterOrEqual), append(SortedSmaller, [Pivot|SortedGreaterOrEqual], Sorted).
The first item is chosen as the pivot, and the remaining items are then partitioned into the smaller items and those that are greater than or equal to the pivot. The two smaller lists are recursively sorted, and then the results are appended, with the pivot placed in front of the items that are greater than or equal to it, to produce the sorted result.
partitionpredicate is as follows:
partition(_, , , ). partition(Pivot, [Item|Rest], [Item|Smaller], GreaterOrEqual) :- Item < Pivot, partition(Pivot, Rest, Smaller, GreaterOrEqual). partition(Pivot, [Item|Rest], Smaller, [Item|GreaterOrEqual]) :- Item >= Pivot, partition(Pivot, Rest, Smaller, GreaterOrEqual).
The first item in the list is either less than the pivot or greater than or equal to it. In the first case, the item should be the first one in the smaller partition, and the rest of the list is partitioned to produce the rest of the smaller and greater-than-or-equal partitions. In the second case, the item should be the first one in the greater-than-or-equal partition, and recursion handles the rest of the list.
Entering a query for a specific list produces:
?- quicksort([4, 8, 5, 3, 1, 2, 6, 9, 7], X). X = [1, 2, 3, 4, 5, 6, 7, 8, 9] .
The sieve of Eratosthenes is an algorithm for computing prime numbers up to some limit \(N\). We start by constructing a list of integers in order from 2 to \(N\). Then we repeat the following process, until no numbers remain:
The first item in the list is prime.
Filter out all multiples of the first item from the remaining list.
Go to step 1.
We can write this algorithm in Prolog as follows. First, we construct a list with the integers from 2 to the limit \(N\):
numbers(2, ). numbers(Limit, Numbers) :- M is Limit - 1, numbers(M, NumbersToM), append(NumbersToM, [Limit], Numbers).
We do so by recursively computing a list of integers from 2 to \(N-1\) and then appending \(N\) to the result.
We then write a predicate that relates a number to a factor when the number is not a multiple of the factor:
is_not_multiple(Number, Factor) :- Remainder is Number mod Factor, Remainder =\= 0.
We can then use this predicate to filter out the multiples of a factor from a list:
filter_not_multiple(_, , ). filter_not_multiple(Factor, [Number|Rest], [Number|FilteredRest]) :- is_not_multiple(Number, Factor), filter_not_multiple(Factor, Rest, FilteredRest). filter_not_multiple(Factor, [_|Rest], FilteredRest) :- filter_not_multiple(Factor, Rest, FilteredRest).
filter_not_multiplepredicate relates a factor and a list of numbers to a list with the multiples of the factor filtered out. The second rule retains
Numberin the resulting list if it is not a multiple of
Factor. The third rule discards the first item of the original list from the filtered list.
We can proceed to define a
sievepredicate that relates a list of numbers to the result of applying the prime-sieve algorithm to the list:
sieve(, ). sieve([Number|Rest], [Number|SievedRest]) :- filter_not_multiple(Number, Rest, FilteredRest), sieve(FilteredRest, SievedRest).
The first number is retained in the result. All multiples of the first number are filtered out of the rest of the list. The sieve algorithm is then recursively applied to the filtered list to obtain the rest of the result list.
Finally, we write a
primespredicate that relates an integer limit to a list of primes up to and including that limit:
primes(Limit, Primes) :- numbers(Limit, Numbers), sieve(Numbers, Primes).
This rule constructs a list of numbers from 2 up to the limit and then applies the sieve algorithm to the list. We can then use the sieve to compute prime numbers up to 100:
?- primes(100, P). P = [2, 3, 5, 7, 11, 13, 17, 19, 23|...] [write] P = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97] .
wkey when the solution is displayed in truncated form causes the interpreter to print out the non-truncated form in the second line above.
Constraints and Dependencies¶
In addition to functional and logic programming, the declarative
paradigm includes programs that express constraints among variables
and constants as well those that describe dependency graphs. We will
look at the former in constraint logic programming and an instance of
the former in the
make build automation tool.
Constraint Logic Programming¶
Constraint logic programming is an extension of logic programming to include constraints on variables. While logic programming allows a limited form of constraints, languages such as Prolog only allow arithmetic constraints to be applied to variables that have been instantiated. For example, suppose we wanted to find a number less than 1000 that is both a square and the sum of two squares. The following is an attempt to specify this in Prolog:
square_sum([N, X, Y, Z]) :- N =:= Z * Z, N =:= X * X + Y * Y, X > 0, Y > 0, Z > 0, X < Y, N < 1000.
We can attempt a query:
?- square_sum(S). ERROR: =:=/2: Arguments are not sufficiently instantiated
Z are not instantiated in the
N =:= Z, we get an error.
On the other hand, using the CLP(FD) library for Prolog, which allows constraint logic programming over finite domains, we can specify the solution as follows:
:- use_module(library(clpfd)). % load the clpfd library square_sum_c([N, X, Y, Z]) :- N #= Z * Z, N #= X * X + Y * Y, X #> 0, Y #> 0, Z #> 0, X #< Y, N #< 1000, label([N, X, Y, Z]).
The first clause loads the library for use. We can then specify
arithmetic constraints using operators that begin with a pound symbol.
For instance, the
#= operator constrains the two arguments to be
equal, while the
#< operator constraints the first argument to be
smaller than the second. Finally, the
label predicate forces the
solver to ground the given variables, computing actual values for
them rather than specifying their results as constraints. Entering a
query, we can now obtain all solutions:
?- square_sum_c(S). S = [25, 3, 4, 5] ; S = [100, 6, 8, 10] ; S = [169, 5, 12, 13] ; S = [225, 9, 12, 15] ; S = [289, 8, 15, 17] ; S = [400, 12, 16, 20] ; S = [625, 7, 24, 25] ; S = [625, 15, 20, 25] ; S = [676, 10, 24, 26] ; S = [841, 20, 21, 29] ; S = [900, 18, 24, 30] ; false.
In constraint logic programming, resolution follows the same basic process as in plain logic programming. For a solver that uses backward chaining, a set of goal terms is maintained, and the solver searches for a clause whose head can be unified with the first goal term. If unification succeeds, then the body terms that are not constraints are added to the set of goals. Terms that are constraints are added to a separate set called the constraint store. When a new constraint is added to the store, in principle, the store is checked to make sure that the constraints are satisfiable, and if not, backtracking is done as in standard search. In practice, however, more limited checking is performed in order to obtain better efficiency from the solver. A solution is obtained when no more goal terms remain, and the set of constraints in the store is satisfiable.
As another example of using constraints, consider the canonical verbal arithmetic puzzle of finding a solution to the following equation:
S E N D + M O R E ----------- = M O N E Y
Requirements are that each letter be a distinct digit, and that the leading digit of a number not be zero. We can express this problem in plain Prolog as the following:
is_digit(0). is_digit(1). is_digit(2). is_digit(3). is_digit(4). is_digit(5). is_digit(6). is_digit(7). is_digit(8). is_digit(9). money([S, E, N, D, M, O, R, Y]) :- is_digit(S), is_digit(E), is_digit(N), is_digit(D), is_digit(M), is_digit(O), is_digit(R), is_digit(Y), S \= 0, M \= 0, S \= E, S \= N, S \= D, S \= M, S \= O, S \= R, S \= Y, E \= N, E \= D, E \= M, E \= O, E \= R, E \= Y, N \= D, N \= M, N \= O, N \= R, N \= Y, D \= M, D \= O, D \= R, D \= Y, M \= O, M \= R, M \= Y, O \= R, O \= Y, R \= Y, 1000 * S + 100 * E + 10 * N + D + 1000 * M + 100 * O + 10 * R + E =:= 10000 * M + 1000 * O + 100 * N + 10 * E + Y.
First, we require that each variable be a digit in the range
\([0, 9]\), and we further require that
be zero. We then specify the pairwise uniqueness requirements.
Finally, we specify that the variables must satisfy the target
We can enter a query as follows:
?- money(S). S = [9, 5, 6, 7, 1, 0, 8, 2] .
Computing this solution takes a minute and a half on the author’s Macbook laptop, since the solver has to search a large portion of the solution space, with much backtracking.
On the other hand, we can use CLP(FD) to specify the problem as follows:
:- use_module(library(clpfd)). money_c([S, E, N, D, M, O, R, Y]) :- L = [S, E, N, D, M, O, R, Y], L ins 0 .. 9, S #\= 0, M #\= 0, all_distinct(L), 1000 * S + 100 * E + 10 * N + D + 1000 * M + 100 * O + 10 * R + E #= 10000 * M + 1000 * O + 100 * N + 10 * E + Y, label(L).
ins predicate is defined by CLP(FD) to constrain that the
variables in the first argument each be contained in the set that is
the second argument. The
.. operator specifies a range, so that
0 .. 9 is the range \([0, 9]\). The
constraints the variables in the argument to take on distinct values.
Finally, we use
label at the end to ground the given variables
with actual values. We obtain the same result:
?- money_c(S). S = [9, 5, 6, 7, 1, 0, 8, 2] .
The solver can use the set of constraints to eliminate most of the
search space, and the remaining candidates are checked when the
label predicate is reached. The result is that computing this
solution takes about 0.2 seconds on the author’s Macbook, a speedup of
As another example, consider the problem of solving a Sudoku puzzle. The following predicate takes in a nested list of lists, in row-major order, with some entries provided but others filled with anonymous variables:
sudoku(Rows) :- length(Rows, 9), maplist(same_length(Rows), Rows), append(Rows, Values), Values ins 1..9, maplist(all_distinct, Rows), transpose(Rows, Columns), maplist(all_distinct, Columns), Rows = [Row1, Row2, Row3, Row4, Row5, Row6, Row7, Row8, Row9], blocks(Row1, Row2, Row3), blocks(Row4, Row5, Row6), blocks(Row7, Row8, Row9), maplist(label, Rows).
The first body term requires that the number of rows be 9. The second
maplist, which maps a predicate over the items in a list.
This is an example of a higher-order predicate in Prolog. The
same_length(Rows) argument is a partially applied predicate that,
when applied to another argument, requires that the two argument lists
have the same length. The term as a whole is checking that each row
also has the same length as the number of rows. The
takes a list of lists and concatenates them into the single list
Values. We then constrain that each variable be in the range
\([1, 9]\). The next term constrains each row to consist of
distinct numbers, and the following two terms constrain each of the
columns to consist of distinct numbers. The next four terms constrain
each of the 9x9 squares to be composed of distinct numbers, with the
blocks predicate defined below. Finally, the last term ensures
that each variable is grounded to a value.
blocks predicate is as follows:
blocks(, , ). blocks([N1, N2, N3 | RestRow1], [N4, N5, N6 | RestRow2], [N7, N8, N9 | RestRow3]) :- all_distinct([N1, N2, N3, N4, N5, N6, N7, N8, N9]), blocks(RestRow1, RestRow2, RestRow3).
The predicate takes in three rows, ensures that the set consisting of the first three items from each row contains distinct values, and then recursively checks this for the remaining items in each row.
We can now provide a query to solve a specific puzzle. The following has been called the “world’s hardest Sudoku”:
?- S = [[8,_,_,_,_,_,_,_,_], [_,_,3,6,_,_,_,_,_], [_,7,_,_,9,_,2,_,_], [_,5,_,_,_,7,_,_,_], [_,_,_,_,4,5,7,_,_], [_,_,_,1,_,_,_,3,_], [_,_,1,_,_,_,_,6,8], [_,_,8,5,_,_,_,1,_], [_,9,_,_,_,_,4,_,_]], sudoku(S). S = [[8, 1, 2, 7, 5, 3, 6, 4, 9], [9, 4, 3, 6, 8, 2, 1, 7, 5], [6, 7, 5, 4, 9, 1, 2, 8, 3], [1, 5, 4, 2, 3, 7, 8, 9, 6], [3, 6, 9, 8, 4, 5, 7, 2, 1], [2, 8, 7, 1, 6, 9, 5, 3, 4], [5, 2, 1, 9, 7, 4, 3, 6, 8], [4, 3, 8, 5, 2, 6, 9, 1, 7], [7, 9, 6, 3, 1, 8, 4, 5, 2]] .
Solving this takes less than 0.4 seconds on the author’s Macbook.
Make is a family of tools used for automating the building of software packages, as well as tracking dependencies between the various components of a package. Make operates on programs called makefiles, which contain rules for how to build individual targets. A target may have dependencies, which are required to be satisfied before the target can be built, as well as commands that specify how the target should actually be built. Thus, a makefile is a combination of declarative components relating targets to dependencies and imperative actions specifying the actions required to build a target.
The structure of a rule in a makefile is as follows:
target: dependencies commands
dependencies is a list of zero or more targets or files that
the given target depends on, and
commands is a list of zero or
more actions to be taken, generally each on its own line and indented
with a tab character.
As an example, consider the following simple makefile, located by
convention in a file named
Makefile (note the capitalization):
hello: echo "Hello world!"
We can run this from the terminal, if we are in the same directory, as:
$ make hello echo "Hello world!" Hello world!
This invokes the
hello target, which has no dependencies and as
its sole action invokes the shell command to print
Hello world! to
the screen. We can leave out the explicit target when invoking
make, in which case it will build the first target in the
$ make echo "Hello world!" Hello world!
The target of a rule is commonly an executable file, and the
dependencies are the files needed to build the target. For example,
suppose we have a C++ project with the source files
c.cpp. We can structure our makefile as follows:
main: a.o b.o c.o g++ -o main a.o b.o c.o a.o: a.cpp g++ --std=c++14 -Wall -Werror -pedantic -c a.cpp b.o: b.cpp g++ --std=c++14 -Wall -Werror -pedantic -c b.cpp c.o: c.cpp g++ --std=c++14 -Wall -Werror -pedantic -c c.cpp
Here, our default rule is
main, which depends on the targets
c.o. In order to build
targets have to be built first, so Make will attempt to build each of
those targets using their respective rules. The rule for
depends on the file
a.cpp, and if it exists, the command invokes
g++ to build the object file
a.o. The rules for
c.o have the same structure. Once those targets have been built,
Make can then build
main, which links together the object files
into the final
main executable. Running
make indicates the
sequence of operations:
$ make g++ --std=c++14 -Wall -Werror -pedantic -c a.cpp g++ --std=c++14 -Wall -Werror -pedantic -c b.cpp g++ --std=c++14 -Wall -Werror -pedantic -c c.cpp g++ -o main a.o b.o c.o
Thus, we can specify complex dependency trees with rules in a makefile, and the Make tool will automatically resolve the dependencies and build the required targets. The relationship between a target and its dependencies is specified declaratively in a rule.
A key feature of Make is that it only builds a target if it has a
dependency, direct or indirect through other rules, that is newer than
the target itself. For instance, if we follow up the preceding build
by modifying the timestamp on
b.cpp, we can see that it is newer
than the targets
$ touch b.cpp $ ls -l -rw-r--r-- 1 kamil staff 229 Nov 17 01:01 Makefile -rw-r--r-- 1 kamil staff 90 Nov 17 00:57 a.cpp -rw-r--r-- 1 kamil staff 6624 Nov 17 01:01 a.o -rw-r--r-- 1 kamil staff 31 Nov 17 01:12 b.cpp -rw-r--r-- 1 kamil staff 640 Nov 17 01:01 b.o -rw-r--r-- 1 kamil staff 33 Nov 17 00:58 c.cpp -rw-r--r-- 1 kamil staff 640 Nov 17 01:01 c.o -rwxr-xr-x 1 kamil staff 15268 Nov 17 01:01 main
If we then run
make, it will only rebuild those targets that
$ make g++ --std=c++14 -Wall -Werror -pedantic -c b.cpp g++ -o main a.o b.o c.o
This is a crucial feature for working with large projects, as only the components that depend on a modification are rebuilt rather than every target in the project.
As a more complex example, consider the following makefile that was used to build a previous version of this text:
all: foundations functional theory data declarative foundations: foundations.html foundations.tex functional: functional.html functional.tex theory: theory.html theory.tex data: data.html data.tex declarative: declarative.html declarative.tex asynchronous: asynchronous.html asynchronous.tex metaprogramming: metaprogramming.html metaprogramming.tex %.html: %.rst rst2html.py --stylesheet=style/style.css $< > $@ %.tex: %.rst rst2latex.py --stylesheet=style/style.sty $< > $@ pdflatex $@ pdflatex $@ pdflatex $@ clean: rm -vf *.html *.tex *.pdf *.aux *.log *.out
The default target is
all, which currently depends on the
declarative targets. While there are also
metaprogramming targets, they were not currently being built since
we had not reached the corresponding units in the text.
Each of the following standard targets has two dependencies, an
.html file and a
.tex file. In order to build an
file, Make looks for an appropriate target. We have a pattern rule
.html files, which depends on a corresponding
Thus, in order to build, for example,
applies the pattern rule and invokes
rst2html.py. The special
$< stands for the dependencies, while
$@ stands for the
target. Thus, the result of
rst2html.py is written to
declarative.html, and the build for that target is complete.
We also have a pattern rule for
.tex files, which invokes
rst2latex.py, followed by several invocations of
end result is that building
declarative.tex ends up creating
declarative.pdf as well.
The last rule is to clean up target and temporary files. Thus, we can
all target to be built from scratch with
all. Without requesting the
clean target, only those targets
that depend on an
.rst file that has been modified will be