January 94 - AAIS Prolog
AAIS Prolog
Mary Elaine Califf
As someone who leads a double life as a Macintosh programmer and a student of
artificial intelligence (especially natural language processing), I was delighted by the
opportunity to review the latest version of Advanced A.I. Systems' Full Control Prolog.
"Prolog?" you ask. "What does Prolog have to do with FrameWorks? I thought I was
reading about object-oriented programming.
Relax. You haven't picked up the wrong magazine. AAIS Prolog, although it can be used
as a standard Edinburgh-style Prolog environment, has objects; in fact, they must be
used in order to access the Macintosh toolbox or to manipulate the environment. AAIS
Prolog is simply another OODL, this one different from those that have been discussed
here previously because it uses logic programming.
For those who are not familiar with logic programming and Prolog, I'll begin with a
brief explanation of the language, without reference to the addition of objects in this
implementation. People who are familiar with Prolog will probably want to skip to the
next section, AAIS Extensions to Prolog.
Prolog
Prolog is probably the best known programming language based on logic and Lisp's
most serious competitor in the AI community. Its syntax, like Lisp's, is much simpler
than that of languages such as C, C++, and Pascal. However to the average
programmer, the syntax is probably a bit more familiar than Lisp's, since it is based
on predicate calculus, something many of us have faced at some point in our education.
Programming in Prolog consists of declaring facts, defining rules, and asking
questions.
Facts are statements about objects and their relationships. They consist of a
relationship followed by a comma-separated list of objects in parentheses and a period
(or full stop). Example Prolog facts include:
loves(john,mary). % usually interpreted "John loves Mary
loves(joe,jane). % "Joe loves Jane
sort([],[]). % a sorted empty list is the empty list
female(jane). % "Jane is female
+(0,Num,Num). % "0 + any number = that number
You probably immediately noticed that I didn't capitalize the proper names in my facts.
In Prolog, symbols typically begin with either a lower case letter or an underscore. If
symbols beginning with capital letters are desired, they must be enclosed in single
quotes. Thus, I could have written
loves('John','Mary').
Names which begin with capital letters are interpreted as variables.
The number of objects in parentheses is the arity of the fact. The name of the
relationship is called the functor. In matching rules and facts against questions, Prolog
attempts to match both the functor and the arity. So you can define two different sorts
both called 'sort' if they have different numbers of arguments.
To do anything with these facts, you need to be able to ask questions about them.
Questions in Prolog take the form
?- loves(mary,john).
On seeing a question, Prolog will attempt to match it against the facts in its database.
As soon as Prolog succeeds in matching a fact (or satisfying a rule), it stops and
returns yes or the binding of the variables in the query for that match. If, after
examining all facts and rules with the same functor and arity, it doesn't find a match,
Prolog returns no. Assuming the above set of facts, here is an example set of queries to
Prolog.
?- loves(john,mary).
yes
?- loves(mary,john).
no
?- loves(X,Y).
X = john, Y = mary ; % first match is loves(john, mary).
X = joe, Y = jane ; % typing ;-return makes Prolog search
% for another match
no % there is no third match
?- +(0,5,Y). % the first Num in +(0,Num,Num) gets bound
Y = 5 % to 5, so the second must also be 5
In programming, obviously facts by themselves aren't going to get you very far, so
Prolog provides rules, which take the following form:
sister(X,Y) :- % X is a sister of Y if
female(X), % X is female
parents(X, Mother, Father), % this subgoal finds X's parents
parents(Y, Mother, Father), % this subgoal tries to match X's
% parents to Y's parents
X \= Y. % and X is not the same as Y
When it encounters a rule, Prolog takes the right hand side as a list of subgoals that
must be proved in order to prove the left hand side. The goals are always satisfied from
left to right. Conjunction is represented by a comma; disjunction is represented by a
semi-colon. All of the facts and rules with the same functor and arity can be taken as a
disjunction of rules, which Prolog will search through from the first to the last in
trying to satisfy a goal (answer a question). Thus, the equivalent of writing a function
will often consist of writing multiple Prolog facts and rules. This is especially true of
recursive functions, which will typically have one or more rules for boundary
conditions followed by the recursive rule(s). This collection of facts and rules is
typically called a program.
Basic Prolog data structures consist of numbers, symbols, structures, and lists.
Structures are essentially facts without periods used as data. Thus, you can build
things like:
book(moby_dick,author(herman,melville)).
Lists are similar to Lisp lists internally, but are represented differently to the
programmer. The syntax for a list is a comma-separated list of items enclosed in
square brackets: [a,b,c]. The empty list is []. [A | B] is a convenient way to
distinguish the head (or car) and the tail (or cdr) of a list: A would unify with the head
and B with the list representing the remainder of the list. Thus, a program to test for
membership in a list would look like this:
member(X,[X|_]). % if X equals the head, then X is a member of
% the list,
% _ is an anonymous variable that unifies
% with anything
member(X,[_|Y) :- % otherwise, X is a member of the list
member(X,Y). % if X is a member of the tail of the list
That covers the basics of Prolog syntax, but there are a few things to be aware of in
order to follow all of the examples. When a Prolog rule fails, or a user asks for
another answer by typing semicolon after Prolog's response, the Prolog system tries
to satisfy the current goal again by searching for additional facts or rules in the
database that match the goal. This is called backtracking, and it is how multiple rules
and facts become a disjunction constituting a single program (or function). However,
for cases where backtracking is undesirable, Prolog provides the cut function, '!'.
When Prolog reaches the cut, it prevents the system from backtracking from the
current goal. An example may help clarify. This is a program to delete all occurrences
of an item from a list. It works by examining each element of the list and leaving it out