CS 381, Spring 2002
Programming Assignment 8
Due: Monday, June 3

More on Prolog

In this assignment we will explore the use of lists in Prolog. Prolog uses a rather conventional syntax for lists, square brackets with elements separated by commas. If foo is a relation, for example, one can write: 


foo([1, 2, 3]).
In defining a relation lists are broken apart by writing a pattern for the list. A simple pattern might simply give names to the different elements: 

foo([A, B, C]) :- print('B is '),print(B).

More often one is interested in writing programs that work in lists of variable length. To break apart a variable length list Prolog uses the same Car/Cdr idea of Lisp, but in prolog these are more often called the Head and the Tail. The syntax used is to write a verical bar between the variable that represents the head and the variable that represents the tail. You can see this by experimenting with the following relation: 


printHead([Head|Tail]) :- print('head is '), print(Head).

Try executing this and giving it lists with variable number of arguments. It should always print the first element of a list. What happens if you give it an empty list?

Most list processing programs will use recursion, just as in Lisp. As in Lisp, you always need a base case, and an induction case. In Prolog these are usually written as separate rules. Try experimenting with the following: 


printList([ ]) :- print('all done').
printList([Head|Tail]) :- print('head is '),print(Head),printList(Tail).
To make a program that does something to a list one describes both the input and the output using patterns. For example, suppose we want to write a program that takes a list of children, and returns a list where each element has been replaced by the associated childs mother. (This is using the family database from the previous assignment). We could do this as follows: 

motherList([ ], [ ]).
motherList([Child|ChildRest],[Mother|MotherRest]) :- motherOf(Mother,Child),
	motherList(ChildRest, MotherRest).

You read this as follows: the motherList of an empty list is an empty list. The motherlist of a nonempty list is found by stripping off the first elements of each, and insisting that the the mother relationship exists between the head of each, and that the motherList relationship exists between the remainder. Try this with the following inputs: 


motherList([castor,alice],X).
motherList(X,[leda,megara]).
Notice that it works in both directions.

Notice that this is exactly the type of function we termed a map when we were working in Lisp.

What about a filter? Could we write a predicate that eliminates elements that fail to satisfy a predicate? Again, think recursively. What are the base cases? The filter of an empty list is the empty list. Next the inducation cases. If the predicate is true we want to keep the element, otherwise if the predicate is not true we want to simply return the rest of the transformed list. Let's try doing this with the predicate female(X). 


allWomen([ ], [ ]).
allWomen([Head|Tail], [Head|Remainder]) :- female(Head), allWomen(Tail,Remainder).
allWomen([Head|Tail], Remainder) :- allWomen(Tail, Remainder).
Try this with a list for the first argument and a variable for the second. Does it work as you expect? What about if you use a variable for the first argument an a list for the second. What does it do in this case? Can you explain why the result is a reasonable one for Prolog to produce?

There are times when you need to combine both types of pattern matching. A good example of this is the insertion relation, which inserts an element into an ordered list. Again we can do this recursively. What is the insertion into an empty list? What is the insertion into a non-empty list? The latter requires we split into two cases, depending upon whether the element being inserted is smaller than the head of the list, or larger. We can write something like the following: 


insert(X, [ ], [ X ]).
insert(X, [Head|Tail], [X,Head|Tail]) :- X<Head.
insert(X, [Head|Tail], [Head|Rest]) :- X>=Head, insert(X, Tail, Rest).

Study this carefully until it makes sense. Notice the third argument in the second rule. This is making a new list in which X is the first element, Head is the 2nd element, and Tail is the remainder. Try executing this relation with a few different lists. What happens if the first two arguments are specified, and the third is a variable? What happens if the first and third arguments are specified, and the second is a variable? What happens if the first argument is a variable, and the remaining two are given as constants? Why do you think the third one gives an error and the other two do not?

Having defined insertion, it should now be easy to define an insertion sort. This should be a two-argument relation, where the second argument is the sorted form of the first. Can you use this with a constant for the first argument and a variable for the second? What about with a variable for the first and a constant for the second?

The Programming Assignment

Take the family database from the last programming assignment, copy it into a file named progEight.pl, and add the following relations:

  1. Define the relation consort(X, Y) which is true if X and Y have a child in common.
  2. Then define a map named consortList(X, Y) which takes a list X and replaces every element with a corresponding consort to yield the list Y. Does your program work both directions? (That is, with a variable in either location?)
  3. If you know your greek mythology you know tht zeus is a god, whereas the remainder of the folks in our family database are mortal. Define the relation isGod(X), which is true only for zeus, and then using this define the relation halfMortal(X) which is true if one of X's parents is a god.
  4. Using the predicate halfMortal, write a filter halfMortalList(X, Y) which takes a list of names for X, and returns a list in Y containing only those individuals who are half mortal.
  5. We hinted at defining the relation insertionSort(X, Y) that takes a list of numbers, and returns the sorted list in Y. Finish the implementation of this relation.
  6. Define the relation biggerThan(X, Y, Z) that takes a number X, a list Y, and returns a list Z containing all the elements in Y that are bigger than X. Write the corresponding relation smallerThanOrEqual(X, Y, Z).
  7. The book shows you how to define the relation append(X, Y, Z) that produces in Z the catenation of the lists X and Y. Using two different calls on this, write the relation quickSort(X, Y) that takes a list X, and recursively does a quicksort on X to generate the ordered list in Y. (Recall that a quicksort is formed by first creating the list of elements smaller than or equal to the head, then sorting this list, doing the same with the elements larger than the head, then catenating the two remaining lists, placing the partion element in the middle.)