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; andfemale(X) means that *X*is female.- Define predicates for various family relationships, including mother, 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.*"*- 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.*"*- 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.*"*- List some sports that Sam likes.
- List some sports that Tom plays.
- Is there sufficient information to determine which sports Sam plays?

*"*common sense.*"*State the implicit assumptions that are necessary to solve the problem, and write Prolog rules for them. (Discussion, page &xtypes;) - 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:
- 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 techniques involved.
- 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: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 inL1 , 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 istake ? 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 listL1 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*andL1 are given in advance, but that *B*andL2 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: - 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 .

- If
- For any positive integer
*N*, the*hailstone function*is easy to define: if*N*is even, its value isN/2 ; if *N*is odd, its value is3&asterisk;N+1 . 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*:hailstone(N,X) <- (rem(N,2,0) -> X := N/2; X := 3&asterisk;N + 1).

For anyN≥1 , the *hailstone path*is defined as the list of integers starting at*N*and ending at1 , where the predicate hailstone(I,J) must be true of any adjacent integers *I*and*J*in the path. (IfN=1 , the hailstone path is just the list 1.nil .) Write Prolog rules to define the following predicates: 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*andLength is the number of integers in the path from *N*to1 . hlong(N,M) , where *M*is the integer between1 and *N*that has the longest hailstone path (if multiple integers have equally long paths, let*M*be the smallest).

Hayes, B. - 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.
- 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.
- 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 andAvailable 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.

- The solution could be computed as a list
- 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 forrep 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 factsfib(0,0) and fib(1,1) ). - 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.

- Note how the execution time increases with
- 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 continent;borders(X,Y) means *X*borders*Y*, where*X*and*Y*are either countries or oceans; andloc(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
problem
DONALD+GERALD=ROBERT . 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) , where *N*is 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, and mo15 means Monday at 3 pm; a course that meets for two consecutive hours might have the meeting list we16.we17.nil . 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 benil . - The predicate
credits(S,C) should compute the total number of credits *C*for all the courses in*S*.

- The predicate
- Add student information to the course database described in the
previous exercise: the predicate
student(N,Name,T,S) gives the student number *N*, nameName , 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 ana ; 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*benil . (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 isd , f , or i . - Let
ranking(R) compute a list *R*of student numbers ordered by descending grade-point averages.

- Let
- Let
schedule(N,Min,Max,Pref,S) determine a new schedule for student *N*chosen from the list of preferences inPref 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 listReq 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.

- No conflicts:
- 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 atom. - 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 tree*F*kinky(F,K) & flatten(K,G)

should leave*G*identical to*F*. - Check that the goal
(kinky(a.b.c.d.e,K) & write(K) & fail)

prints 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 ofkinky that would work if either argument were an unbound variable and the other were a list of constants.

- Let
- 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*, ands(U,V) means that *V*is the simplified form of*U*. Without simplification, the derivative ofx&asterisk;x is 1&asterisk;x+x&asterisk;1 ; but with it, the derivative becomes the more standard 2&asterisk;x . Following are the first four rules for the predicate d : d(X,X,1). 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&asterisk;V,X,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 adding0 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); W=SU+SV).

Write one rule for thed 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 predicatemsort : msort(nil,nil). msort(X.nil,X.nil). msort(L,M) <- split(L,L1,L2) & msort(L1,M1) & msort(L2,M2) & merge(M1,M2,M).

The first two lines check for lists of length 0 or 1 and leave them unchanged. For a longer list*L*, the third rule callssplit to split *L*in two partsL1 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*. Thesplit predicate puts alternate elements of a list *L*in two sublistsL1 and L2 . It calls itself recursively to take two elements at a time from *L*, putting the first inL1 and the second in L2 : split(nil,nil,nil). split(X.nil,X.nil,nil). split(X.Y.T, X.T1, Y.T2) <- split(T,T1,T2).

Themerge 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(nil,L,L). merge(L,nil,L). 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 formsort 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: - Monkey and box not at the same location,
- Box not under bananas,
- Monkey not on box,
- Monkey not reaching for bananas.

*D*for any stateM.B.P : heuristic(M.B.P, D) <- (M=B -> D1=0; D1=1) & (B=m -> D2=0; D2=1) & (P='reaching bananas' -> D3=0; P='on box' -> D3=1; D3=2) & D := D1 + D2 + D3.

Thebest_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) <- set_of(D.N, move(Current,N) & ^member(N,Past) & heuristic(N,D), Move_list) & 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 ofset_of . For each possible next move *N*, theheuristic predicate computes the estimated distance *D*. Thenset_of finds the set of all pairs D.N and automatically sorts them in order of increasing distance. The best candidates are therefore the ones near the front of Move_list ; then the subgoal member(&asterisk;.Next, Move_list) selects one candidate at a time from that list. Make these modifications to the rules for the monkey and bananas problem and compare the performance to the previous rules. - With the depth-first and breadth-first rules, the only predicate
that used problem-dependent knowledge was
move . With the best-first rules, the heuristic predicate also uses problem-dependent knowledge. The ability to use additional knowledge can make a significant improvement in performance, but defining a good heuristic predicate is an art. Consider the searching problems in Exercises 6 through 10, and define a heuristic predicate for each of them; compare the performance of the three different search strategies on each of those problems. The nickel and dime game is particularly challenging. Try playing the game to see what kinds of moves tend to lead to blocked positions; define the rules for heuristic to penalize such moves and give preference to moves that are more likely to lead to a solution. - Another way to improve search time is to block moves that lead
to a dead end. Following is a modified version of the second rule
for depth-first search; the subgoal
^deadend(Goal,Next) will succeed only if the proposed state Next is not a known dead end for the current Goal : depth_first(Goal, Current.Past, Current.Future) <- move(Current,Next) & ^member(Next,Past) & ^deadend(Goal,Next) & depth_first(Goal, Next.Current.Past, Future).

For the water jug problem in Exercise 7, a dead end would occur if the total water in the goal happened to be greater than the total water in the proposed next state. For the nickel and dime game in Exercise 10, a dead end can occur when the next state includes either a nickel followed by two dimes and a blank or a blank followed by two nickels and a dime. Following is the definition of adeadend predicate that checks for those conditions: deadend(&asterisk;,n.d.d."_".&asterisk;). deadend(&asterisk;,"_".n.n.d.&asterisk;). deadend(&asterisk;,Head.Tail) <- deadend(&asterisk;,Tail).

With 3 nickels and 3 dimes, this test makes a minor improvement in performance; but with 8 nickels and 8 dimes, it makes more than a 6 times improvement. Try definingdeadend predicates for other search problems and compare their performance on different inputs.

Copyright ©2001 by John F. Sowa.

Last Modified: