Where do the answers come from?
In the first two lessons, answers appeared as if by magic: ask grandparent(G, ada) and Prolog produces Amara, then Obi, then false. There is no magic. Prolog follows one simple, fixed strategy for exploring the possibilities your clauses describe, and once you can follow that strategy in your head you can predict the order of answers, see why a program is slow, and see why another never stops.
The strategy is depth-first search with backtracking. Whenever Prolog has a choice (several clauses that might match a goal), it takes the first, remembers that the others exist, and carries on. When it reaches a dead end (a goal that cannot be satisfied), it goes back to the most recent choice it made, undoes everything since, and takes the next option. That going back is backtracking. It is the same idea a person uses to solve a maze by keeping one hand on the wall, and the same idea behind many search algorithms in other languages, except that in Prolog you get it for free with every predicate.
The execution model
To run a query, Prolog keeps a list of goals still to prove, starting with the query's goals in order. It repeats one step:
- Take the leftmost goal.
- Find the first clause, from the top of the program, whose head unifies with it. If other clauses might also match, leave a choice point to come back to.
- Replace the goal by that clause's body (nothing, for a fact), with the bindings from unification applied.
- If the goal list becomes empty, report an answer. If no clause matches a goal, backtrack: return to the most recent choice point, undo the bindings made since it, and try its next clause.
When the user (or forall, or findall) asks for another answer, Prolog backtracks exactly as if the last answer had failed. When no choice points remain, there are no more answers, and the toplevel says false.
Definition— Choice point
A saved position in the search: a goal, the clauses still untried for it, and the state of the variables, to which Prolog returns on backtracking.
Logicians call this procedure SLD resolution; the search space it explores is the search tree (or SLD tree). Two rules fix the shape of the search: goals are tried left to right, and clauses top to bottom. The logical meaning of a program does not depend on these orders, but its behaviour (the order of answers, its speed, and whether it terminates) depends on them entirely.
Some predicates you will use with search:
| Predicate | What it does |
|---|---|
member(X, List) | True for each element X of List, one per backtrack |
between(Low, High, X) | True for each integer X from Low to High |
forall(Cond, Action) | True if Action succeeds for every solution of Cond |
findall(T, Goal, List) | List of T for every solution of Goal; [] if none |
bagof(T, Goal, List) | Like findall, but fails if there are none, and groups by free variables |
setof(T, Goal, List) | Like bagof, with the list sorted and duplicates removed |
aggregate_all(count, Goal, N) | Counts solutions (also sum, max, bag, set; SWI-Prolog library) |
Watching the search
A search you can see
This program builds meals from a starter and a main course, with a test on the lengths of their names (atom_length/2 gives the number of characters, and =< compares numbers; lesson 5 covers arithmetic). Messages printed inside the rule show the order in which Prolog tries things:
:- initialization(main, main).
% A tiny menu: which dishes can a guest choose?
starter(soup).
starter(salad).
main_course(curry).
main_course(paella).
main_course(tagine).
% A meal is a starter and a main course whose names are not too long
% together; the trace messages show the order of the search.
meal(S, M) :-
starter(S),
format(" try starter ~w~n", [S]),
main_course(M),
format(" try main ~w~n", [M]),
atom_length(S, LS),
atom_length(M, LM),
LS + LM =< 10,
format(" accept ~w + ~w~n", [S, M]).
main :-
format("All meals:~n"),
forall(meal(S, M), format("=> ~w with ~w~n", [S, M])).All meals:
try starter soup
try main curry
accept soup + curry
=> soup with curry
try main paella
accept soup + paella
=> soup with paella
try main tagine
accept soup + tagine
=> soup with tagine
try starter salad
try main curry
accept salad + curry
=> salad with curry
try main paella
try main tagineFollow the trace with the tree. starter(S) has two matching facts, so it leaves a choice point and takes soup. main_course(M) leaves another and takes curry. The test passes, the rule succeeds, and forall prints the meal and then asks for another answer, which makes Prolog backtrack to the most recent choice point: main_course, which offers paella. Only when all three main courses are used up does Prolog back up further, to starter, and take salad. With salad, the test fails for paella and tagine (5 + 6 = 11 characters), so those branches produce no answer, and the trace shows no accept line for them.
Notice also what the trace does not show: after try main paella under salad, Prolog did not go back and retry the starter first. Backtracking always returns to the latest choice, never to an arbitrary one.
Tracing the search
You do not have to add format calls to see the search: SWI-Prolog has a tracer that reports every step. Each goal is pictured as a box with four ports: Call (the goal is first tried), Exit (it succeeded), Redo (backtracking has come back into it for another solution) and Fail (it has no more solutions). This four-port model, devised by Lawrence Byrd in 1980, is used by nearly every Prolog debugger.
Here is a trace of a cut-down menu with two starters, two main courses and the test atom_length(S, 5) (a five-letter starter), started at the toplevel with leash(-all) (do not stop at each port) and then trace, meal(S, M):
Call: (13) meal(_30446, _30448)
Call: (14) starter(_30446)
Exit: (14) starter(soup)
Call: (14) main_course(_30448)
Exit: (14) main_course(curry)
Call: (14) atom_length(soup, 5)
Fail: (14) atom_length(soup, 5)
Redo: (14) main_course(_30448)
Exit: (14) main_course(paella)
Call: (14) atom_length(soup, 5)
Fail: (14) atom_length(soup, 5)
Redo: (14) starter(_30446)
Exit: (14) starter(salad)
Call: (14) main_course(_30448)
Exit: (14) main_course(curry)
Call: (14) atom_length(salad, 5)
Exit: (14) atom_length(salad, 5)
Exit: (13) meal(salad, curry)
S = salad,
M = curryThe numbers in brackets are call depths, and names like _30446 are SWI-Prolog's internal names for unbound variables (they differ from run to run). Read the Fail and Redo lines together: after atom_length(soup, 5) fails, the very next event is a Redo of the most recent goal that still has alternatives. In the interactive tracer you step with Enter, skip over a call with s and leave with a; gtrace opens a graphical version.
Generate and test, and why the order of goals matters
Many problems can be solved by generating candidate answers and testing them. Colouring a map so that neighbours differ is the classic example. Here are two versions of the same program for five countries of East Africa:
:- initialization(main, main).
colour(red).
colour(green).
colour(blue).
% colouring(Map): a list Country-Colour in which no two neighbours share
% a colour (Kenya, Uganda, Tanzania, Rwanda and Burundi).
colouring([kenya-K, uganda-U, tanzania-T, rwanda-R, burundi-B]) :-
colour(K), colour(U), dif_colour(K, U),
colour(T), dif_colour(K, T), dif_colour(U, T),
colour(R), dif_colour(U, R), dif_colour(T, R),
colour(B), dif_colour(R, B), dif_colour(T, B).
dif_colour(X, Y) :- X \== Y.
% The same problem as pure generate-and-test: choose everything, then check.
colouring_slow([kenya-K, uganda-U, tanzania-T, rwanda-R, burundi-B]) :-
colour(K), colour(U), colour(T), colour(R), colour(B),
K \== U, K \== T, U \== T, U \== R, T \== R, R \== B, T \== B.
main :-
colouring(Map),
format("First colouring: ~w~n", [Map]),
aggregate_all(count, colouring(_), N),
format("Number of colourings: ~w~n", [N]),
aggregate_all(count, colouring_slow(_), N2),
format("Same count by generate-and-test: ~w~n", [N2]),
aggregate_all(count, (colour(_), colour(_), colour(_), colour(_), colour(_)), C),
format("Complete candidates generate-and-test examines: ~w~n", [C]).First colouring: [kenya-red,uganda-green,tanzania-blue,rwanda-red,burundi-green]
Number of colourings: 6
Same count by generate-and-test: 6
Complete candidates generate-and-test examines: 243Both versions are logically the same, and both find the 6 colourings. But colouring_slow generates every complete assignment of three colours to five countries, of them, before testing any, while colouring tests each constraint as soon as both of its countries have colours. When Kenya and Uganda are both red, the fast version rejects that pair at once and never generates the 27 completions that start that way; the slow version builds all 27 and rejects each one at the end. With five countries the difference is small; with fifty countries, is about candidates, which at a billion a second would take millions of years. Test as early as you can is the first rule of efficient search in Prolog. Lesson 7 goes further: constraint programming makes the system do this pruning automatically.
Search in a graph, and collecting answers
Finding routes in a network is search in its purest form. A route must not visit a city twice, or the search could go round a cycle forever, so the program carries a list of the cities visited so far (\+ member(...) means "is not a member"; lesson 5 explains \+):
:- initialization(main, main).
% link(A, B): a direct train between A and B in a made-up network.
link(lisbon, porto).
link(lisbon, madrid).
link(porto, madrid).
link(madrid, barcelona).
link(madrid, lyon).
link(barcelona, lyon).
link(lyon, geneva).
% Trains run both ways.
connected(A, B) :- link(A, B).
connected(A, B) :- link(B, A).
% route(From, To, Route): Route is a list of cities from From to To
% that never visits a city twice.
route(From, To, Route) :-
walk(From, To, [From], Reversed),
reverse(Reversed, Route).
walk(To, To, Visited, Visited).
walk(From, To, Visited, Route) :-
connected(From, Next),
\+ member(Next, Visited),
walk(Next, To, [Next|Visited], Route).
main :-
findall(R, route(lisbon, geneva, R), Routes),
length(Routes, N),
format("~w routes from lisbon to geneva:~n", [N]),
forall(member(R, Routes), format(" ~w~n", [R])),
findall(Len-R, (member(R, Routes), length(R, Len)), Pairs),
msort(Pairs, [Best-Shortest|_]),
format("Shortest has ~w cities: ~w~n", [Best, Shortest]),
setof(City, R^route(porto, City, R), Reachable),
format("Reachable from porto: ~w~n", [Reachable]),
forall(bagof(To, link(From, To), Tos),
format("Links from ~w: ~w~n", [From, Tos])),
findall(X, link(geneva, X), None),
format("findall with no answers: ~w~n", [None]),
( bagof(X, link(geneva, X), _)
-> true
; format("bagof with no answers fails~n")
).4 routes from lisbon to geneva:
[lisbon,porto,madrid,barcelona,lyon,geneva]
[lisbon,porto,madrid,lyon,geneva]
[lisbon,madrid,barcelona,lyon,geneva]
[lisbon,madrid,lyon,geneva]
Shortest has 4 cities: [lisbon,madrid,lyon,geneva]
Reachable from porto: [barcelona,geneva,lisbon,lyon,madrid,porto]
Links from barcelona: [lyon]
Links from lisbon: [porto,madrid]
Links from lyon: [geneva]
Links from madrid: [barcelona,lyon]
Links from porto: [madrid]
findall with no answers: []
bagof with no answers failsThe details reward attention:
walk/4builds the route backwards, adding each new city to the front of the list, androute/3reverses it at the end. Adding to the front of a list is cheap; lesson 4 explains why.- The four routes come out in depth-first order: the search goes through Porto before trying Lisbon's second link, Madrid. Depth-first search does not find the shortest route first. To get it, this program collects every route, pairs each with its length, and sorts with
msort/2, which keeps duplicates and sortsLength-Routepairs by length first. For large graphs you would use a breadth-first search instead. setof(City, R^route(porto, City, R), Reachable)collects every city reachable from Porto, sorted and without repeats. TheR^says "for some routeR": without it,setofwould give a separate answer for every different route.bagof(To, link(From, To), Tos)leavesFromfree, so it groups: one solution per value ofFrom, each with that city's links.forallprints them all.findallnever groups; it collects everything into one list.- With no solutions at all,
findallgives[], whilebagofandsetoffail. Choose whichever behaviour your program needs.
When the search never ends
The commonest Prolog bug is a query that never finishes. Here is a definition that is logically correct (A reaches B if A reaches some C and C links to B) but written with the recursive goal first:
link(lisbon, porto).
link(porto, madrid).
reachable(A, B) :- reachable(A, C), link(C, B).
reachable(A, B) :- link(A, B).The query reachable(lisbon, X) takes the first clause, whose first goal is reachable(lisbon, C), which takes the first clause again, and again, forever, without ever reaching a link fact. SWI-Prolog eventually runs out of stack and reports something like this (the program was saved as loop.pl; the exact numbers vary from run to run):
ERROR: [Thread main] /w/loop.pl:1: user:main Stack limit (1.0Gb) exceeded
ERROR: [Thread main] Stack sizes: local: 0.9Gb, global: 48.4Mb, trail: 0Kb
ERROR: [Thread main] Stack depth: 6,340,532, last-call: 0%, Choice points: 6,340,525
ERROR: [Thread main] Probable infinite recursion (cycle):
ERROR: [Thread main] [6,340,532] user:reachable(lisbon, _120)
ERROR: [Thread main] [6,340,531] user:reachable(lisbon, _140)This is left recursion: a predicate that calls itself as its first goal with no progress made. The fix is to make progress before recursing, and to put the base case first:
reachable(A, B) :- link(A, B).
reachable(A, B) :- link(A, C), reachable(C, B).That version terminates on a graph without cycles. On a graph with cycles it can still loop, which is why the route program carries a visited list. Lesson 7 shows a third solution, tabling, which lets Prolog run even the left-recursive version correctly.
Misconception
"Prolog finds the best answer first." It finds answers in the order its depth-first search reaches them, which depends on clause and goal order. If you want the shortest or cheapest, compute it explicitly.
Misconception
"Clause order and goal order do not matter in a logic language." They do not change what is true, but they change which answers come first, how much work the search does and whether it terminates at all.
Misconception
"findall and bagof are the same." findall treats free variables as "anything" and returns [] when there are no answers; bagof groups by free variables (unless you mark them with ^) and fails when there are no answers. setof is bagof plus sorting and removing duplicates.
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. Backtracking and search
Warm-upComputationalHow many answers does meal(S, M) have in the lesson's menu program?
2. Backtracking and search
CoreComputationalSuppose the two starter/1 facts are swapped, so that starter(salad). comes before starter(soup). What is the first answer of meal(S, M)? Answer in the form salad with curry.
3. Backtracking and search
Warm-upComputationalWhat list does setof(X, member(X, [b, a, b]), L) bind L to? (findall would give [b,a,b].)
4. Backtracking and search
Warm-upComputationalWhich values of X satisfy between(1, 5, X), X mod 2 =:= 0? List them separated by commas.
5. Backtracking and search
CoreComputationalThree countries all border each other. With the lesson's three colours and the rule that neighbours differ, how many colourings are there? (Count them as aggregate_all(count, ...) would.)
6. Backtracking and search
CoreHumanWhich definition of ancestor/2 makes the query ancestor(amara, X) run forever (until the stack overflows)?
7. Backtracking and search
StretchHumanWhich statements are true? Choose all that apply.
Further reading and resources
- SWI-Prolog manual, finding all solutions to a goalfindall/3, bagof/3, setof/3 and the ^ operator.
- SWI-Prolog manual, control predicatesConjunction, disjunction, if-then-else, negation and the cut.
- The Power of Prolog · Markus TriskaThe chapters on termination and nontermination explain how to reason about whether a query finishes.