A Prolog to Prolog

John F. Sowa

Exercises

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.

  1. 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.

    1. Define predicates for various family relationships, including mother, father, sibling, brother, sister, uncle, great-grandfather, and mother in law.

    2. 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.

    3. 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.)
    (Partial solution, page &xfamily;)

  2. 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;)

  3. 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."

    1. Use Prolog to determine what my cat eats.

    2. Is that answer reasonable? If not, check whether the difficulty lies in the original English specifications or in your translation from English into Prolog.

    3. If the problem lies in the specifications, revise them, translate the revised form into Prolog, and ask the question again.
    (Hints, page &xeats;)

  4. 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."

    1. Use Prolog to find out who is happy.

    2. For this problem, think of a reasonable rule to add that will make everybody happy.

    3. 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).
    (Hints, page &xlikes;)

  5. 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."

    1. List some sports that Sam likes.

    2. List some sports that Tom plays.

    3. Is there sufficient information to determine which sports Sam 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;)

  6. 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;)

  7. 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;)

  8. 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;)

  9. 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:

    1. If standing at any location, move somewhere else.

    2. If standing next to the box, push it somewhere else.

    3. If standing next to the box, get on the box.

    4. If on the box, get off the box.

    5. If on the box under the bananas, reach for the bananas.
    By what sequence of moves can the monkey reach the bananas from the starting state? (Hints, page &xmonkey; and page &xdepth;)

  10. 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.

    1. Try playing the game with coins to get some feeling for the techniques involved.

    2. 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.

    3. Generalize the rules to allow any number of nickels and dimes (not necessarily equal numbers of each).

    4. 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.

  11. 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:

    1. 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.

    2. 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.

    3. element(X,I,Z) extracts the i-th element of the list X and binds it to Z.
    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;)

  12. 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?

  13. 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.)

  14. 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:

    1. If L1=a.b.c.nil and L2=x.y.z.nil, then the result is L3=a.x.b.y.c.z.nil.

    2. If either input is shorter than the other, the tail of the longer input is passed to L3 unchanged.

    3. 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.
    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.

  15. 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 is 3&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 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:

    1. hpath(N,P), where P is the hailstone path for N.

    2. 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.

    3. 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).
    For further discussion of this function, see Hayes (1984). Hayes, B.

  16. 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.

    1. The band from the north side was at the head of the parade.

    2. "American Patrol" was the second piece played.

    3. The band from the east or west side played "Yankee Doodle."

    4. The last band played "When the Saints Go Marching in," just behind the band from the west side.

    5. The bands that played "American Patrol" and "Stars and Stripes Forever" are from opposite sides of town.
    (Complete solution, page &xbands;)

  17. 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.

    1. 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.

    2. 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.

    3. Then call allocate(L, 40 . 40 . 40 . nil) to solve the problem.
    (Problem suggested by Karen Roberts of IBM; discussion, page &xoffice;.)

  18. 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.

  19. 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)).

    1. Note how the execution time increases with N. Why?

    2. Use addax to improve performance.

    3. Define a new version of fib with three arguments instead of two that runs in linear time.
    (Partial solution, page &xfib;)

  20. 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; 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.

    1. What European countries border an ocean?

    2. What oceans border some Asian country, but do not border an African country?

    3. Find all pairs of countries located in different continents that border a common ocean.

    4. 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.

  21. 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.

  22. 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.)

  23. 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 be nil.

    • The predicate credits(S,C) should compute the total number of credits C for all the courses in S.

  24. 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 an a; 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.

  25. 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.

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

  27. 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 of x&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 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);
                                     W=SU+SV).
    
    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.)

  28. The merge sort is an important sorting algorithm that is quite efficient in Prolog. Following is its implementation as the predicate msort:
    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 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(nil,nil,nil).
    split(X.nil,X.nil,nil).
    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(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 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.

  29. 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.

  30. 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.
    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:
    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.
    
    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) <-
       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 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 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.

  31. 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.

  32. 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 a deadend 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 defining deadend predicates for other search problems and compare their performance on different inputs.


Copyright ©2001 by John F. Sowa.

  Last Modified: