ON DISK!
Programming In Prolog
Stepping Up to Prolog
by Joseph Schmuller
Follow along with this exciting introduction to Artificial Intelligence. File MASH.ARC on your START disk.
Welcome to the first installment of a continuing feature on the Prolog language. Prolog, is the basis for some of the most exciting developments in Artificial intelligence today. My goal is to demystify these developments and make it possible for every ST owner to experiment with them.
There are two commercial implementations of Prolog now available for the ST: XPRO from Rational Visions and MProlog from Logicware, Inc. Both were reviewed by Christopher Chabris in the Spring 1988 issue of START.
I'll be using XPRO because it gives programmers the right combination of power and price. It's a complete implementation of the accepted standard for Prolog (the so-called "Edinburgh syntax"), and it has some useful extensions beyond this standard, as well eventually see.
XPRO does have drawbacks, two in fact. First, it's a plain vanilla application--you don't work with it through GEM, although you can construct GEM applications with it. Second, the documentation is extremely short; it's virtually a requirement that you work with an outside reference. This series of articles will hopefully help fulfill that requirement.
(Editors note: In the Spring 1988 issue, START published GProlog by Gene Weiss, a bare-bones implementation of Prolog. GProlog will let you experiment with Prolog and work with the examples in this article; refer to the GProlog documentation on slight variations on syntax and variable treatment. If you're missing the Spring 1988 issue you can order it with disk for $14.95 by writing to START Back issues, 544 Second St., San Francisco, CA 94107. If you have a CompuServe account, you can download GProlog with documentation from Antic Online's February Software Shelf. Log onto CompuServe and type GO ANTIC.)
Working with Prolog
Prolog stands for Programming in Logic. It is usually used for non-numerical programming and is most appropriate for expressing relationships between objects. Prolog is primarily a declarative language rather than a procedural one. This means that when you use Prolog to solve a problem, you tell Prolog what to do, rather than how to do it.
You interact with Prolog in much the same way that you work with a database. You type a query and Prolog looks at a set of facts and rules and returns an answer. The major part of Prolog programming is using a text editor to create the set of facts and rules in a text file.
Then you tell Prolog to consult this file so that it can search the facts and rules in order to respond to queries. The consult operation copies the contents of the text file into a structure called the Prolog database (some sources, including the XPRO documentation, call this a knowledge base).
Let's examine some of the kinds of facts that you can put in a Prolog database and what you can do with them. Suppose we want to represent this information about a small group of military personnel:
Sherman Potter is a Colonel.
Hawkeye Pierce is a Captain.
Charles Winchester is a Major.
B. J. Hunnicutt is a Captain.
Max Klinger is a Corporal.
Here's a way to write these statements in Prolog:
is_a(sherman_potter,colonel).
is-a(hawkeye-pierce,captain).
is_a(charles-winchester,major).
is_a(b_j_hunnicutt,captain).
is_a(max_klinger,corporal).
There are several things to immediately take note of. First, there are no uppercase letters in the Prolog statements; a word that begins with an uppercase letter is a variable. Second, Prolog does not ordinarily understand separated words, so the underscore is used to join the words together. Third, there can be no spaces between "is_a" and the opening parenthesis. Finally, each Prolog statement must end with a period.
In each statement, "is_a" is called the functor, and the expressions inside the parentheses are called the arguments. It doesn't matter what order you use for the arguments, as long as you're consistent throughout. Together, the functor and arguments form a clause. Clauses like these are called facts. The number of arguments associated with a functor is said to be the arity of that functor; each of these functors, then, has an arity of 2.
I put these five facts into an ASCII file called MASH; the completed file is on your START disk if you don't want to type this information in. Copy MASH.ARC and ARCX.TTP onto a blank, formatted disk and un-ARC the MASH.ARC, following the disk instructions elsewhere in this issue. If you're using GProlog, you'll have to type your queries into the file and save it with a .PRO extender, since GProlog does not have a command line.
If you're using XPro, you'll see a prompt that looks like this:
?-
Tell Prolog to consult the file:
?- consult(mash).
Note the period at the end of the statement. Press Return and Prolog will put the facts in MASH into the Prolog database. Now you can form queries.
At this point, you can ask if Sherman Potter is a colonel:
?- is_a(sherman_potter,colonel).
Prolog will search its database for this fact, and when it finds it, it will write "Yes" on the screen. You can ask what rank Charles Winchester happens to be:
?- is_a(charles_winchester,X).
Notice the uppercase letter as the second argument in the query. The second argument (which holds the military rank) will be a variable; Prolog will search its database and come up with a value for the variable. In this case "major" will be returned as the value of the variable X, so Prolog's response is:
X = major
When Prolog finds a value for a variable it has instantiated the variable. The value is then known as an instantiation of the variable. Ask who holds the rank of captain and the whole transaction would look like this on the screen:
?- is_a(X,captain).
X = hawkeye_pierce
Again, Prolog found this instantiation of X by searching its database until it found a fact whose functor is "is-a" and whose second argument is "captain"; it took the first argument of that fact as the instantiation of X. If you want to know who else is a captain, type a semicolon after Prologs response. This signals Prolog to search for another fact which satisfies the query. Prolog will answer:
X = b_j_hunnicutt
If you type another semicolon, Prolog will answer "No," as there are no more facts in the database that fit the conditions of the query. Prolog will always answer "No" to a query if there are no facts in its database that fit:
?- is_a(radar_o_reilly,corporal).
Prolog gives us this answer because there isn't any information about this person in the database.
Going Beyond the Given Information
So far you've seen that Prolog lets you put facts into a database and then query the database to find out about those facts. While this might be mildly entertaining, it's not very helpful. To begin to see why Prolog is useful, let's answer the question "Does Hawkeye Pierce outrank Max Klinger?" First we need to give Prolog some information about ranks, so well put these facts into MASH:
higher_than(colonel,major).
higher_than(colonel,captain).
higher_than(colonel,corporal).
higher_than(major,captain).
higher_than(major,corporal).
higher_than(captain,corporal).
Next Prolog needs a rule to follow to use this information:
outranks(X,Y) :-is_a(X,Z),
is_a(Y,W),
higher_than(Z,W).
This rule reads "to prove that person X outranks person Y, prove that the rank of person X is Z, prove that the rank of person Y is W, and then prove that Z is higher than W." In this case "proving" something simply means that Prolog has to go through its database and find a relevant fact. The commas at the end of each clause are always read as "and". Another way to read this rule is to interpret ":-" as "is implied by." The "is implied by" symbol separates the rule into two parts. The part preceding ":-" is called the head or conclusion, and the part following ":-" is the tail or condition. Incidentally, Prolog's symbol for "or" is the semicolon, which is perfectly consistent with the way we've been using it.
In our outranks rule, when you plug in hawkeye_pierce for X and max_klinger for Y, Prolog:
1. Searches its database for "is_a(hawkeye_pierce,Z)" and instantiates Z to "captain."
2. Searches for "is_a(max_klinger,W)" and instantiates W to "corporal."
3. Searches for "higher_than(captain,corporal)" and finds that this fact is in the database.
4. Answers "Yes" because all the clauses in the tail have been proven. Another way to say this is that they all succeeded. Had any of the clauses not been proven (i.e., had any of the clauses failed), Prolog would have answered "No".
The important point here is that we didn't have to have a fact in the database which explicitly stated
Outranks (hawkeye_pierce,max_klinger).
Instead, we gave the database some facts and a rule and turned Prolog loose.
Here are two other ways to use the outranks rule:
?-outranks(charles_winchester,X).
?-outranks(A,B).
Type the first query in and type a semicolon after each response. The second query means "who outranks whom?" Prolog will respond with a pair of instantiations, and if you type a semicolon it will give you another pair. Prolog will eventually show every possible pair of names such that the first outranks the second.
Things to Come
In this article, we've introduced some essential Prolog terminology, as well as the style of interacting with and using this language. But we've barely touched on Prolog's power. In future installments, well see what logic programming really is all about, and how it can be used for natural language processing, rapid prototyping and expert system development. Well also look at object-oriented programming in Prolog and use XPRO to develop GEM applications.
Joseph Schmuller is a Cognitive Scientist with the Expert Systems group at CDM Federal Programs Corporation.
PRODUCTS MENTIONED
XPRO, $39.95. Rational Visions, 7111 W. Indian School Road, Suite 131, Phoenix, AZ 85033, (602) 846-0371.
MProlog, $199. Logicware, Inc., 5915 Airport Road, Suite 200, Mississauga, Ontario, Canada L4V IT1, (416) 672-0300.