example prolog queries

[Tim Menzies]

Prolog can handle data structures that are based on logical function symbols. For example, in arithmetic, when we write 3+2, the + is a function symbol. Prolog lets us invent function symbols useful to our subject area.

For example, say that we work in a library and we will program a Prolog database of the library's holdings. Perhaps the library stocks books and dvds, so the items can be portrayed as data structure-values like these:

book('David Copperfied', 'Charles Dickens')

dvd('Tale of Two Cities')

The first is a book data structure that holds two data values: the book's title and its author. (Prolog allows strings to be atoms.) The second data structure is a dvd structure that holds the dvd's title. The data-structure-builder names, book and dvd, are called functors because they look like function calls (but they are not).

If the library owns a copy of each of these items, we can write a predicate that asserts these facts:

owns(k0, book('David Copperfied', 'Charles Dickens')).

owns(k3, dvd('Tale of Two Cities')).

The predicate, owns, lists the key (id number) and the item. So, the library owns item k0, the book David Copperfield by Charles Dickens. Here is a summary of the data structures we will use to define the library's database:

ITEM ::=  book(TITLE, AUTHOR)  |  dvd(TITLE)
                where TITLE and AUTHOR are strings

We will use these two predicates:

PRED ::=  owns(KEY, ITEM)  |  borrowed(KEY, PERSON, DATE)
                where KEY is an atom that begins with  k
                      ITEM is defined above
                      PERSON is a string
                      DATE is an int

The borrowed predicate remembers who has borrowed items from the library. Here is a sample database:

===================================================

owns(k0, book('David Copperfied', 'Charles Dickens')).
owns(k1, book('Tale of Two Cities', 'Charles Dickens')).
owns(k2, book('Tale of Two Cities', 'Charles Dickens')).
owns(k3, dvd('Tale of Two Cities')).
owns(k4, book('Moby Dick', 'Herman Melville')).

borrowed(k2, 'Homer', 44).
borrowed(k4, 'Homer', 46).
borrowed(k3, 'Lisa', 92).
borrowed(k0, 'Lisa', 92).

===================================================

Whenever someone borrows an item, the appropriate borrowed premise is added to the database. When someone returns an item, the borrowed premise is removed. (Prolog has special operators, asserta and retract, for adding and removing premises from an active database.)

Given the above database, here are some queries. First, what has Homer borrowed?

?- borrowed(K, 'Homer', _).
K = k2 ;
K = k4 ;
false.

The database is written so that the items' keys are retrieved. We can use them: What books has Homer borrowed?

?- borrowed(K, 'Homer', _), owns(K, book(_,_)).
K = k2 ;
K = k4 ;
false.

The above example is important --- it shows how to retrieve a key of a book (K) and how to use the key as well as the data-structure name (functor) to match only the books borrowed by Homer. The action of matching functor names to the database is called unification, and it gives much power to Prolog. Note also that the _ symbol is a ``dummy variable'' that we do not care about --- its value is not printed. (Here we do not care about the book's due date nor the title and authors, so three dummy variables are used in the query.)

Of course, if we wished to see the titles, we modify the query like this:

?- borrowed(K, 'Homer', _), owns(K, book(T,_)).
K = k2,
T = 'Tale of Two Cities' ;
K = k4,
T = 'Moby Dick' ;
false.

Libraries want to track overdue books. Here is a law for proving when a borrowed item is overdue:

===================================================

isOverdue(Person, Item, Today) :- borrowed(Item, Person, DueDate),  Today > DueDate.

===================================================

The words. Person, Item, and Today are logical variables, because they begin with capital letters. Today is an int. (See our definitions earlier.) This law uses arithmetic on ints: it compares the int-value of Today with the int value of DueDate, to see if today is greater than the due date. If so, the goal, Today > DueDate succeeds (is proved).

?- isOverdue('Homer', _, 89).
true ;
true ;
false.

?- isOverdue('Homer', Item, 89).
Item = k2 ;
Item = k4 ;
false.

We query the database and learn that, if today is day 89, then Homer has two items overdue; we can learn the keys of the items if we wish.

Perhaps a fine is calculated by how many days an item is overdue. We can use simple arithmetic in Prolog, like this:

===================================================

hasFine(Person, Item, Today, HowMuch) :- isOverdue(Person, Item, Today),  
                                         borrowed(Item, _, DueDate),
                                         HowMuch is  Today - DueDate.

===================================================

The predicate, HowMuch is Today - DueDate is an assignment --- a matching --- of HowMuch to the answer computed from Today - DueDate. This ``subgoal'' always succeeds.

?- hasFine('Homer', I, 89, Fine).
duedate=44
I = k2,
Fine = 45 ;
duedate=46
I = k4,
Fine = 43 ;
false.

You can also do simple arithmetic with +,*,-,/.

Finally, it would be helpful to write a query that would return a list of all the items that Homer has borrowed. To do this, we must learn how to use lists in Prolog.