A Prolog to Prolog
John F. Sowa
These exercises illustrate a wide variety of Prolog
programming techniques. Many of them are discussed in detail or even
completely solved in the text; following those exercises are references
to the pages where the discussion starts.
- Build a database of facts about family relationships. You
may choose your own family, the family of gods and goddesses in Greek
mythology, or any other family about which you can find sufficient data.
Define four predicates by lists of facts: child(C,P) means
that C is a child of P; married(A,B) means that A is
married to B; male(X) means that X is male;
and female(X) means that X is female.
(Partial solution, page &xfamily;)
- Define predicates for various family relationships,
father, sibling, brother, sister,
uncle, great-grandfather, and mother in law.
- Define a predicate cousin(X,Y,N), which means that X and
Y are N-th level cousins; i.e, N=1 for
first cousins, 2 for second cousins, etc.
- Use Prolog to determine whether there is evidence of
immorality in the family history. (As the U.S. Supreme Court has
declared, morality is defined by the standards of the community.
If the family is rather proper or the community is rather lax, this
question may have a null answer.)
- Translate the following sentences into
Prolog: "Washable allergenic things are washed.
Nonwashable allergenic things are vacuumed. Everything that is
gray and fuzzy is allergenic. Shirts, socks, pajamas, dogs, and llamas
are washable. Lamps, sofas, cats, and computers are nonwashable.
Following are my gray, fuzzy possessions: my pajamas, my sofa,
my cat Thothmes, and my llama Millicent." Use Prolog to determine
which of my possessions are washed and which are vacuumed.
(Complete solution, page &xwashable;)
- Translate the following sentences into
Prolog: "Tweety is a bird. Goldie is a fish. Squiggly
is a worm. Birds like worms. Cats like fish. Cats like birds.
Friends like each other. My cat is my friend. My cat eats
everything he likes."
(Hints, page &xeats;)
- Use Prolog to determine what my cat eats.
- Is that answer reasonable? If not, check
whether the difficulty lies in the original English specifications
or in your translation from English into Prolog.
- If the problem
lies in the specifications, revise them, translate the revised form
into Prolog, and ask the question again.
- Translate the following sentences into Prolog: "Ursula is pretty.
Norbert is rich and handsome.
Bertha is rich and strong.
Pierre is strong and handsome.
Bruno is kind and strong.
All men like pretty women.
All rich men are happy.
Any man who likes a woman who likes him is happy.
Any woman who likes a man who likes her is happy.
Bertha likes any man who likes her.
Ursula likes any man who likes her provided that he is either rich
and kind or handsome and strong."
(Hints, page &xlikes;)
- Use Prolog to find out who is happy.
- For this problem, think of a reasonable
rule to add that will make everybody happy.
- For the new version,
find all cases of mutual affection (two people who like each other),
divided affections (one person likes two or more people), and
rivalries (two or more people like the same person).
- Translate the following English sentences into Prolog: "Sam
likes all kinds of sports. Football, swimming, and boxing are sports.
Any physical activity that involves competition between people
is a sport. Bill and Mary compete in bilboquet.
Bob competes with Bill in yobizumo.
Tom plays all the sports that Bill plays."
Note: Like most specifications, this problem statement leaves out
a number of assumptions that are supposed to be "common
sense." State the implicit assumptions that are necessary to
solve the problem, and write Prolog rules for them.
(Discussion, page &xtypes;)
- List some sports that Sam likes.
- List some sports that Tom plays.
- Is there sufficient information to determine which sports Sam plays?
- A farmer has a wolf, a goat, and a cabbage (a very large one).
He wants to get all three of them plus himself across a river,
but his boat is only large enough to hold one item plus himself.
How can he cross the river without leaving the wolf alone with
the goat or the goat alone with the cabbage?
(Complete solution, page &xfarmer; and page &xdepth;)
- Water jug A has a capacity of 5 liters, and water jug B has a
capacity of 2 liters. Assume the following constraints: initially,
A is filled and B is empty;
the jugs are irregularly shaped, so that it is not possible
to measure any intermediate amount; either jug may be poured into the
other or down the drain, but no new water can be added. By what
sequence of pouring, can exactly 1 liter of water be left in jug B?
(Hints, page &xjug; and page &xdepth;)
- Three missionaries and three cannibals want to cross a river,
but their boat is only large enough to hold two persons at one
time. How can they all get across? Assume the constraint that
the number of cannibals can never be greater than the number of
missionaries on either side of the river at any one time.
(Hints, page &xmission; and page &xdepth;)
- A room has four corners (A, B, C, D) and a middle (M). A monkey
is standing at A, a box is at C, nothing is at B or D, and a
bunch of bananas are hanging high above M. Assume that the
monkey can perform the following actions:
By what sequence of moves can the monkey reach the bananas from
the starting state? (Hints, page &xmonkey; and page &xdepth;)
- If standing at any location, move somewhere else.
- If standing next to the box, push it somewhere else.
- If standing next to the box, get on the box.
- If on the box, get off the box.
- If on the box under the bananas, reach for the bananas.
- The nickel and dime game uses two kinds of coins (say, nickels
and dimes). In the starting state, all the coins are lined up
with the nickels on the left, the dimes on the right, and an
empty space between them. For example, with two nickels and two
dimes, the starting state would be n.n.'_'.d.d.nil. The
goal state has all the dimes on the left and all the nickels on the
right: d.d.'_'.n.n.nil. There are four possible
moves: slide a nickel into an empty space on the right; slide a dime
left; hop a nickel over another coin into an empty space on the right;
or hop a dime over another coin into an empty space on the left.
- Try playing the game with coins to get some feeling for the
- Write rules that define the possible moves, and execute them
with depth first, breadth first, and
best-first (according to some evaluation of a move) search strategies.
Compare the results and execution times of the different strategies.
- Generalize the rules to allow any number of nickels and dimes
(not necessarily equal numbers of each).
- Write a user interface that asks for the number of each kind of
coin and prints a nicely formatted trace of the
steps from start to goal.
- Let X and Y be lists of numbers. If the two lists are not of
the same length, treat the shorter one as if it were padded with
zeroes to match the length of the longer. Write Prolog rules to
define the following predicates:
After writing rules to compute these predicates with the input
and output variables indicated, check whether the definitions are
reversible (with inputs and outputs exchanged). If they are not
reversible, either rewrite the rules to make them reversible or explain
why such a rewrite is not possible or practical.
(Partial solution, page &xlistadd;)
- listadd(X,Y,Z) adds the i-th element of X to
the i-th element of Y to form
the i-th element of Z.
- innerprod(X,Y,Z) computes the inner product of the
lists X and Y: the i-th element of X is multiplied by
the i-th element of Y, and the sum of the products is
bound to Z.
- element(X,I,Z) extracts the i-th element of
the list X and binds it to Z.
- Define a predicate take(N,L,L1,L2) that takes the
first N elements from a list L, puts them in L1, and
leaves the remaining elements in L2. If N=0,
then L1=nil, and L2=L.
If L has fewer than N elements, the predicate should fail.
How reversible is take? Which arguments may be undefined
upon a call to this predicate?
- The predicate pick(X,L1,L2) defined on page &xpick; picks
an element X out of list L1 and leaves the remainder in
list L2. Generalize that predicate for picking N items out of
one of several bins: pick(N,B,L1,L2), where N is the
number of items to be picked, B is a number that identifies the
bin, L1 is a list of nonnegative integers giving the number of
items in each bin, and L2 is derived from L1 by
subtracting N from position B (the result may become zero, but
not negative). Assume that N and L1 are given in advance,
but that B and L2 may be unbound variables whose values
are to be found. (Note: only two rules are needed to define this
predicate; it may be used in allocating offices in Exercise 17.)
- Define a predicate weave(L1,L2,L3) that interleaves
alternate elements of lists L1 and L2 to
form the list L3. Check that it has the following properties:
The definition requires two unconditional rules and one conditional
rule. The conditional rule should call itself recursively, but it does
not need to call any other predicate.
- If L1=a.b.c.nil and L2=x.y.z.nil, then
the result is L3=a.x.b.y.c.z.nil.
- If either input is shorter than the other, the tail
of the longer input is passed to L3 unchanged.
- The rules are reversible: if L3=a.b.c.d.e.f.nil,
then L1=a.c.e.nil and L2=b.d.f.nil.
- For any positive integer N,
the hailstone function is easy to define: if N is even,
its value is N/2; if N is odd, its value
But the values of this function rise and fall
in a complex, unpredictable way that has fascinated mathematicians.
The following Prolog rule computes the value X for
any input N:
(rem(N,2,0) -> X := N/2; X := 3&asterisk;N + 1).
For any N≥1, the hailstone path is defined as
the list of integers starting at N and ending at 1, where
the predicate hailstone(I,J) must be true of any adjacent
integers I and J in the path. (If N=1, the hailstone
path is just the list 1.nil.) Write Prolog rules to define
the following predicates:
For further discussion of this function, see Hayes (1984).
- hpath(N,P), where P is the hailstone path for N.
- hlimit(N,Max,Length), where Max is the largest
integer in the hailstone path for N and Length is the
number of integers in the path from N to 1.
- hlong(N,M), where M is the integer between 1 and
N that has the longest hailstone path (if multiple integers
have equally long paths, let M be the smallest).
- Four bands, each from a different side of town, marched in a
parade. Each band played only one piece, and no two bands
played the same piece. From the following clues, determine
the order in which the bands marched and the pieces they played.
(Complete solution, page &xbands;)
- The band from the north side was at the head of the parade.
- "American Patrol" was the second piece played.
- The band from the east or west side played "Yankee Doodle."
- The last band played "When the Saints Go Marching in," just
behind the band from the west side.
- The bands that played "American Patrol" and "Stars and
Stripes Forever" are from opposite sides of town.
- A company is moving into three floors of a new building. Each
floor has 40 offices. Following are the office requirements for
each department that is moving in: Department m43 needs 9 offices;
d48, 6 offices; m77, 11 offices; m54, 13 offices; j39, 9 offices;
j76, 12 offices; m20, 11 offices; j92, 11 offices; j83, 7 offices;
j64, 10 offices; m06, 11 offices; and j48, 10 offices.
All the offices for a given department must be on the same floor.
Furthermore, the following pairs of departments that work closely
together must also be on the same floor: m43 and m77; d48 and m54;
and j92 and j83.
(Problem suggested by Karen Roberts of IBM;
discussion, page &xoffice;.)
- The solution could be computed as a list L of
triples (D.N.F), where D is the department identifier, N is
the number of offices needed, and F is the floor allocated to D.
Initially, D and N are constants, but F is to be determined.
- Define a predicate allocate(L,Available),
where L is the list of triples for each department
and Available gives the number of available offices
on each floor. Using the
version of pick defined for Exercise 13, the allocate
predicate requires only one recursive rule plus an unconditional
rule that does nothing when L=nil.
- Then call allocate(L, 40 . 40 . 40 . nil)
to solve the problem.
- Study the rep predicate as defined by the following rule:
rep(X,N,L) <- length(L,N) & append(X.nil,L1,L)
& append(L2,X.nil,L) & L1=L2.
For inputs X and N, give a simple English description of
the result L. Define Prolog rules for rep that do not call
any other predicates, but compute exactly the same result. Compare the
execution times of the two versions for several values of N.
- The Fibonacci series starts with 0 and 1. Each subsequent number is
the sum of the previous two: 0, 1, 1, 2, 3, 5, 8, 13, 21, etc.
Define a recursive rule that computes the N-th number in the series
(starting with the facts fib(0,0) and fib(1,1)).
(Partial solution, page &xfib;)
- Note how the execution time increases with N. Why?
- Use addax to improve performance.
- Define a new version of fib with three arguments instead
of two that runs in linear time.
- Build a database of geographical information. Start by listing
facts for the following five predicates: ocean(X) means
X is an ocean; country(X) means X is a
country; continent(X) means X is a
means X borders Y, where X and Y are
either countries or oceans;
and loc(X,Y) means X is
located in Y, where X is a country
and Y is a continent.
You do not have to type all possible information about every country
in the world, but include enough data to provide non-null answers
to the following questions.
- What European countries border an ocean?
- What oceans border some Asian country, but do not border
an African country?
- Find all pairs of countries located in different continents
that border a common ocean.
- Find all pairs of countries A and B, where A and B have a common
border, A borders one ocean, B borders another ocean, and A and B do
not border the same ocean.
- Generate possible hybrids between animals.
Hybrids are not determined genetically, but by an overlap of two or
more letters at the end of one animal's name with the beginning
of another animal's name. Define a predicate that prints a listing
of hybrids in the following form:
Cross a tiger with a gerbil to get a tigerbil.
Cross a kangaroo with a rooster to get a kangarooster.
Cross a hippopotamus with a mussel to get a hippopotamussel.
- Write Prolog rules to solve the cryptarithmetic
Order the search to optimize performance.
(See pages &crypt1; and &crypt2;
for two solutions to a similar problem.)
- Build a database of information about courses at some school.
First enter data to define the predicate course(N,P,C,M),
the course number, P is a list of zero or more course numbers that
are prerequisites for N, C is the number of credits for N, and
M is a list of meetings for N. Assume that meetings are represented
by two letters and a number: tu9 means Tuesday at 9 am,
means Monday at 3 pm; a course that meets for two
consecutive hours might have the meeting
Let S be a list of course numbers in some student's proposed schedule.
Write Prolog rules to define the following predicates:
- The predicate conflicts(S,L) should determine a list L of
courses in S that have a common meeting. If there are no conflicts,
L should be nil.
- The predicate credits(S,C) should compute the total
number of credits C for all the courses in S.
- Add student information to the course database described in the
previous exercise: the predicate student(N,Name,T,S)
gives the student number N, name Name,
transcript T, and current schedule S. The transcript should be
a list of pairs (N1.G1).(N2.G2)...nil
where each Ni is the number of a course that the student
has taken and Gi is
the grade that the student received in that course. Assume
that valid grades are the letters a,
b, c, d, f,
i (incomplete), and p (passed by advance placement or in an ungraded
course). Write Prolog rules to define the following predicates:
- Let gpa(N,A) compute the grade-point average A for
all courses in the transcript for student N. Assume 4 points for
3 for a b;
2 for a c;
1 for a d; and 0 for an f.
Ignore courses with grades of p or i. Weight the average by
the number of credits for each course. If a student's transcript has
no graded courses, let A be nil. (Either use floating point
arithmetic or scale the integers by 100.)
- Let checkprereq(N,S,M) compute a list of courses M with
missing prerequisites in the schedule S for student N: either
some prerequisite for the course is not in the student's transcript or
the grade for the prerequisite is d, f, or i.
- Let ranking(R) compute a list R of student numbers
ordered by descending grade-point averages.
- Let schedule(N,Min,Max,Pref,S) determine a new schedule
for student N chosen from the list of preferences in Pref
where Min and Max
are two numbers. The schedule S should
meet the following constraints:
- No conflicts: conflicts(S,nil).
- If credits(S,C), then Min≤C and C≤Max.
- Meets prerequisites: checkprereq(N,S,nil).
- Assuming that Pref is ordered in descending order of
preferences, schedule should select more preferred
courses before less preferred ones.
- Find S with the constraint that the student's adviser has said
that all courses in the list Req must be taken. Do not write
any new rules. Just use the schedule predicate together
with the append, member,
and set_of predicates
defined in the text.
- The dot operator in Prolog builds binary trees. The trees may be
straight, right-branching ones like a.b.c.d; straight,
left-branching ones like ((a.b).c).d; or kinky ones
like (a.b).(c.d). Write Prolog rules for the following
predicates. For these rules, do not
assume that lists end in nil;
if nil does occur, treat it like any other
- Let flatten(T,F) take an arbitrary tree T and create
a straight, right-branching tree with exactly the same leaves in
exactly the same order.
- Let kinky(F,K) take a flat tree F and create another
tree K with the same leaves in the same order as F, but possibly
with a more complex branching structure. For any flat
kinky(F,K) & flatten(K,G)
should leave G identical
- Check that the goal
(kinky(a.b.c.d.e,K) & write(K) & fail)
all possible binary trees with five leaves (there should be 14 of them).
- Is the definition of kinky reversible (i.e, is it possible
to define flatten by the following rule)?
flatten(T,F) <- kinky(F,T).
Define a reversible form of kinky that would
work if either argument were an unbound variable and the other were
a list of constants.
- Define rules to do symbolic differentiation of algebraic
expressions. Assume that expressions are written in an infix form
like (2&asterisk;x + 3&asterisk;a&asterisk;y)
or sin(a&asterisk;x). The derivatives of
these expressions with respect to x should be 2
and a&asterisk;cos(a&asterisk;x), respectively.
(Note that variables in these
expressions are expressed by constants x and y instead of
Prolog variables X and Y.) The solution should specify rules for
two predicates: d(U,X,V) means that the derivative of U
with respect to X is V, and s(U,V) means that V is
the simplified form of U. Without simplification, the derivative
but with it, the derivative becomes
the more standard 2&asterisk;x. Following are the first four
rules for the predicate d:
d(U,X,0) <- atom(U) & ne(U,X).
d(U+V,X,W) <- d(U,X,DU) & d(V,X,DV) & s(DU+DV,W).
d(U,X,DU) & d(V,X,DV) & s(DU&asterisk;V+U&asterisk;DV,W).
The rules for simplifying expressions must deal with many special
cases for adding 0 or multiplying by 1. Following
are the first two rules for the s predicate: the
stopping rule which says that atomic expressions (integers and
strings) cannot be simplified
further; the second rule simplifies expressions where the main
operator is + :
s(X,X) <- atomic(X).
s(U+V,W) <- s(U,SU) & s(V,SV)
& ((numb(SU) & numb(SV)) -> W:=SU+SV;
SU=0 -> W=SV;
SV=0 -> W=SU;
SV=-T -> s(SU-T,W);
SU=SV -> s(2&asterisk;SU,W);
((A&asterisk;T=SU | T&asterisk;A=SU)
& (B&asterisk;T=SV | T&asterisk;B=SV)) -> s((A+B)&asterisk;T,W);
(A&asterisk;SU=SV | SU&asterisk;A=SV) -> s((A+1)&asterisk;SU,W);
(A&asterisk;SV=SU | SV&asterisk;A=SU) -> s((A+1)&asterisk;SV,W);
Write one rule for the d predicate and the s predicate for
each function or operator that can occur in an expression.
(Note the use of W:=SU+SV to evaluate the expression if the
values are numbers, as opposed to W=SU+SV, which binds the
unevaluated expression to W.)
- The merge sort is an important sorting algorithm that
is quite efficient in Prolog. Following is its implementation as
the predicate msort:
msort(L,M) <- split(L,L1,L2)
& msort(L1,M1) & msort(L2,M2)
The first two lines check for lists of length 0 or 1 and leave them
unchanged. For a longer list L, the third rule calls split
to split L in two parts L1 and L2. Then it calls
itself recursively to sort L1 to form M1 and
L2 to form M2. Finally, it calls merge to
merge M1 and M2 to form the final result M.
The split predicate puts alternate elements of
a list L in two sublists L1 and L2.
It calls itself recursively to take two elements at a time from L,
putting the first in L1 and the second in L2:
split(X.Y.T, X.T1, Y.T2) <- split(T,T1,T2).
The merge predicate is the only one that compares the
actual data in the lists. It takes two lists that have already been
sorted and merges them into a larger sorted list:
merge(X.T1,Y.T2,L) <- merge(T1,T2,T) &
(le(X,Y) -> L=X.Y.T; L=Y.X.T).
Study these three predicates and verify that they work correctly.
Compare the execution time for
msort with the times for qsort (page &pqsort;)
and bsort (page &pbsort;) on various kinds of input data.
Try lists that are completely sorted (such as the 26 letters
in alphabetic order), almost sorted (such as the letters with
one or two interchanges), nearly random (such as the letters
in typewriter order q.w.e.r.t.y...), and reversed (such
as the alphabet backwards). Also check how the execution time
increases with increasing length of lists.
- The order in which predicates are listed can often have a major
effect on execution time. As an example, consider the following
rule for computing uncle by blood, which was given on page &puncle;:
uncle(U,N) <- child(N,P) & sibling(P,U) & male(U).
Consider the following two goals, either of which might trigger this
rule: uncle(sam,N) and uncle(U,sue). Which of these
two rules is likely to take less execution time? Build a family database
with a few dozen people in it. Try executing both goals to check
the relative execution times. Rewrite the rule with the predicates
in reverse order. What happens to the execution time of each goal?
As this example illustrates, neither way of writing the rule is
optimum for all possible goals. For a database of thousands or even
millions of entries, the differences in performance can be enormous.
Using features of IBM Prolog, Chapter 3
shows how execution of a goal can be delayed until values are
obtained for some or all of the variables referenced in it.
An optimal solution to this problem will be given in the exercises
at the end of Chapter 3.
- A best-first search is similar to a depth-first search,
but at each step, it reorders the set of possible next moves
according to some estimate of the distance from the goal.
For the monkey and bananas problem,
the heuristic predicate counts
one point for each of the following undesirable circumstances:
The total number of points gives an estimate of the distance to the
goal. Following is a rule that computes the estimated distance D for
any state M.B.P:
- Monkey and box not at the same location,
- Box not under bananas,
- Monkey not on box,
- Monkey not reaching for bananas.
heuristic(M.B.P, D) <-
(M=B -> D1=0;
& (B=m -> D2=0;
& (P='reaching bananas' -> D3=0;
P='on box' -> D3=1;
& D := D1 + D2 + D3.
The best_first predicate is defined by rules that
are similar to the rules for depth_first:
best_first(Goal, Goal.&asterisk;, Goal.nil).
best_first(Goal, Current.Past, Current.Future) <-
move(Current,N) & ^member(N,Past)
& member(&asterisk;.Next, Move_list)
& best_first(Goal, Next.Current.Past, Future).
The second rule above differs from the corresponding depth-first
rule in the use of set_of. For each possible next move N,
the heuristic predicate computes the estimated distance D.
Then set_of finds the set of all pairs