Computers And Society

David D Thornburg, Associate Editor

The Continuing Evolution Of Languages

Last month we discussed the ongoing Japanese development of a new generation of computer as described in The Fifth Generation, a book by Edward Feigenbaum and Pamela McCorduck. This ten-year development project promises to have a lasting impact on our concept of computers. While I didn't elaborate on the topic, I think that the choice of computer language to be used with these machines will be as important as the details of the machine architecture itself. It was thus interesting to find that the language chosen for the fifth generation machines is Prolog.

I had not heard of this language before, and I decided that I should check with some of my Stanford friends to see if they knew about it. With their help I was directed to an excellent guide to this language: Programming in Prolog, by W. F. Clocksin and C. S. Melish (Springer-Verlag, $16).

There are two things that surprise me about this language. The first is its tremendous power, and the second is that it has been around since the early 1970s. Interestingly, Programming in Prolog (published in 1981) is the first book to appear on this language. The authors wrote the book while they were at the Department of Artificial Intelligence at the University of Edinburgh, a school that has long been a center for Prolog research.

Prolog is used primarily for symbolic computation. Many of its applications are the standard fare of artificial intelligence research – abstract problem solving, mathematical logic, understanding natural language, and the creation and exploration of relational data bases. In other words, Prolog is being used in many applications for which LISP or Logo otherwise might be considered the language of choice.

Creating Facts

To get some picture of Prolog's power, let's examine some program statements. One of the basic structures in Prolog is the "fact." A fact is created in the following way. Suppose we wanted to express the idea that David is a friend of Pam. To express this in Prolog, we would write:

friend(david,pam).

We could create some more facts by entering:

female(pam).
male(david).

and so on.

A fact in Prolog consists of a relationship followed by the objects of the relationship, separated by commas and placed inside parentheses. The names chosen for objects and relationships are totally up to the programmer, as long as the names of constants start with lowercase letters. Each complete Prolog statement must end with a period.

Once a collection of facts has been entered into the computer, the data base can be asked to examine the validity of an assertion. Suppose, for instance, that the following facts were present in the system:

likes(joe,fish).
likes(mary,book).
likes(joe,mary).
likes(john, book).

We can ask a question in Prolog by typing ?-followed by the assertion we want to test. If we typed:

?- likes(joe,money).

the system would type:

no

because there is no fact present in the system to confirm the validity of this assertion. If, on the other hand, we typed:

?- likes(joe,mary).

Prolog would search its data base until it found the desired fact, at which point it would type:

yes

on the display screen.

Variables

While this application may not appear very powerful, consider the way that Prolog uses variables. Suppose we wanted to know something that Joe likes. To find something we would type:

?- likes(joe,What).

The word "What" is a variable. Variables can have any name the programmer desires, as long as they start with an uppercase letter. On receiving this question, Prolog searches its data base to find the relationship "likes" and the object "joe." Once it has found these, it then sets the value of "What" to the remaining object. The screen would then show:

What = fish

since this is the first thing that was shown for the desired relationship. When Prolog finds a match, it places a marker at the relevant fact in case you want to search for other matches. To find other things that Joe likes, one just presses the semicolon (;) key and RETURN. Prolog continues its search and prints:

What = mary

This process can be continued until the search fails. This aspect of Prolog is very similar to the use of "property lists" in Logo.

Factual Relationships

Questions can be asked about conjunctions of facts also. For example, if one were to ask if there is something that Mary and John both like, one would write:

?- likes(john,X), likes(mary,X).

The comma is used in Prolog to represent the logical AND operation. At this point you should be able to convince yourself that the computer will print

X = book

as a response.

In addition to facts, Prolog programs are constructed from rules. An example of a rule is "X is a sister of Y if X is a female and X and Y have the same parents." In Prolog, this rule could be written as:

sisterof(X,Y) :-
       female(X),
       parents(X,M,F),
       parents(Y,M,F).

The Prolog primitive:- stands for "if."

Suppose we now had the following entries in the data base:

female(kathy).
female(pam).
female(pat).
male(greg).
male(david).
parents(kathy,cleo,bob).
parents(pam,virginia,ernie).
parents(david,cleo,bob).
parents(greg,virginia,ernie).

With the "sisterof" procedure in place, we can ask questions like:

?- sisterof(kathy,david).

to which the computer would respond with a "yes" answer. Alternatively, we could find out if Greg has a sister by entering:

?- sisterof(X,greg).

to which the computer would reply:

X=pam

It doesn't take much imagination to see that Prolog programs can be written to solve many types of logic problems.

In addition to manipulating objects and variables, Prolog also works with lists. The Prolog data base (consisting of both facts and rules) is searched by a technique called "backtracking" which insures that matches will be found if they occur anywhere in the data base. By moving back and forth in the program, Prolog differs from languages like BASIC in which commands are followed in strict order. If Prolog is unable to answer a query with one set of objects, it will backtrack and start over with a new set until it has found a solution or has exhausted the data base. This feature of the language is one reason that Prolog has thus far appeared primarily on large computers such as the DEC PDP-10. Unless Prolog programs are compiled, they would run quite slowly on personal computers.

And yet this powerful language will probably appear on small computers for many of the same reasons Logo did. When people get sufficiently interested in a language, some enterprising programmer will implement it. There is already a CP/M-based version of the language available from England. I haven't seen it yet, so I can't comment on it. As the impact of the "fifth generation" starts to be felt, Prolog will become more generally available on personal computers.

While the description of Prolog given above is necessarily quite incomplete, it does give some of the flavor of the language. Next month we will explore other powerful languages that are hiding right under our noses. You may be surprised to see what they are!