John F. Sowa
All versions of Prolog share a common core called pure Prolog. This core is directly derived from symbolic logic and supports the great bulk of all Prolog programming. Although features outside the core are needed for input/output and system interfaces, the pure Prolog subset determines the spirit of the language. This section illustrates Prolog programming style with emphasis on the pure Prolog core.
Translating Prolog into English is relatively straightforward. But translating any natural language into any formal language is much more difficult. Chapter 5 presents formal rules for automatically mapping English into a logical form. This section presents more informal methods of analyzing a problem statement and mapping it into Prolog. Following are some rules of thumb for doing that mapping:
Washable allergenic things are washed. Nonwashable allergenic things are vacuumed. Everything that is gray and fuzzy is allergenic. Shirts, socks, pajamas, dogs, and llamas are washable. Lamps, sofas, cats, and computers are nonwashable. Following are my gray, fuzzy possessions: my pajamas, my sofa, my cat Thothmes, and my llama Millicent.In the first sentence, the adjectives "washable" and "allergenic" map into the predicates
washed(X) <- washable(X) & allergenic(X) & thing(X).This rule may be read "X is washed if X is a washable allergenic thing," which is Prolog's closest approximation to "Washable allergenic things are washed." By the same kind of analysis, the second sentence becomes,
vacuumed(X) <-
nonwashable(X) & allergenic(X) & thing(X).
Note the separate predicate allergenic(X) <- gray(X) & fuzzy(X) & thing(X).The next sentence implies that X is washable if X is a shirt, a sock, a pajama, a dog, or a llama:
washable(X) <- shirt(X) | sock(X) | pajama(X) |
dog(X) | llama(X).
Similarly, the sentence after that becomes,
nonwashable(X) <- lamp(X) | sofa(X) | cat(X) |
computer(X).
The last sentence introduces some complexities: "Following
are my gray, fuzzy possessions: my pajamas, my sofa,
my cat Thothmes, and my llama Millicent." The word "following"
can be ignored; it is not about the subject matter itself, but about
the form of the statement. The word "my" introduces a new
individual,
possess(me,pj1) & pajama(pj1) &
gray(pj1) & fuzzy(pj1).
But since Prolog facts may contain only one predication, that
information must
be split into four simple facts (which may be written on a single line).
The last sentence of Exercise 2 therefore maps into the
following collection of facts:
possess(me,pj1). pajama(pj1). gray(pj1). fuzzy(pj1).
possess(me,sf1). sofa(sf1). gray(sf1). fuzzy(sf1).
possess(me,thothmes). cat(thothmes). gray(thothmes).
fuzzy(thothmes).
possess(me,millicent). llama(millicent).
gray(millicent). fuzzy(millicent).
These Prolog rules, when asserted in a single workspace, represent
a complete translation of Exercise 2 into Prolog. Unfortunately, there
is something missing: the English statement never said how the noun
"thing" is related to the other nouns like "cat" or
"sofa". Another rule must be added to say that X is a thing
if X is a shirt or sock or whatever:
thing(X) <- shirt(X) | sock(X) | pajama(X) | dog(X)
| llama(X) | lamp(X) | sofa(X) | cat(X)
| computer(X).
Every time a new type of entity is introduced, this rule must be
augmented with another disjunction. A simpler and more general solution
is to say that everything is a thing. That can be stated in one very
short unconditional rule:
thing(X).This rule always succeeds for any value of X.
Suppose all those rules have been typed into the
file
Natural languages are highly systematic structures, but the system
is not always marked by obvious syntactic features. For that reason,
superficial patterns are often misleading.
As an example of a common misunderstanding,
consider the sentences "Sam likes Jane" and
"Cats like fish." After learning that the first sentence maps
into the Prolog fact The rule that common nouns map into predicates is generally true,
but they may map into predicates with more than one argument. Consider
the sentences "My cat is my friend" and "Friends like
each other." The word "friend" does not indicate the type
of individual in the same way as "human" or "cat"; instead,
it shows the role that some person (or cat) plays with
respect to another. In general, nouns that specify the type of
individual designate natural types, which correspond to
predicates with a single argument; nouns that specify a role that the
individual plays designate role types, which correspond to
predicates with more than one argument. Examples of natural types
include human, cat, dog, beagle, tree, table, house, and number.
Examples of role types include father, sister, lawyer, employee, pet,
possession, home, and quotient. Note the distinction: Sam may be
a human by nature, but a father by virtue of a certain relationship to
someone else; Thothmes is a cat by nature, but a pet in relation
to some person; 4 is a number by itself, but a quotient
as a result of 20 divided by 5. For further discussion of these
types, see the book by Sowa (1984).
To represent the noun "friend," two arguments are needed on
the predicate: the first indicates the person who is the friend, and
the second indicates the other person involved. Since friendships
are normally reciprocal, two facts are needed to make the
predicate symmetric. The sentence "My cat is my friend" maps into
the following facts:
The sentence "My cat eats everything he likes" raises some
interesting issues. In mapping it into Prolog, the main verb becomes
the conclusion and the other parts are the conditions. If
the cat is the same one mentioned in Exercise 2, the rule becomes,
Exercise 4 (page
&pexer4;)
can now be solved with the techniques discussed so far.
Some of the sentences are fairly complex. For example,
the sentence "Any man who likes a woman who likes him is happy" maps
into the following rule:
In looking for some way to make everybody happy in Exercise 4,
think of reasonable principles in English before writing them
in Prolog. One reasonable principle is "Any man who is not rich likes
any woman who is rich." In fact, this principle
makes many people happy for many different reasons.
With the goal Exercise 5 introduces a new issue: the distinction
between individuals and types. That problem arises in many guises,
as in the following faulty syllogism:
Talking about types in Prolog requires a change of notation.
Normally, one would assert the fact In Exercise 5, the main statements are about types. If Sam likes
all kinds of sports, he undoubtedly likes all the subtypes, such
as football or boxing, but he might be bored with a particular game
or match. The problem also involves other complexities, such as unstated
assumptions about the relationship between competing in a sport and
playing the sport. There are two approaches to issues as
complex as these: adopt a general set of predicates for talking about
individuals, types, and subtypes; or simplify the English statements
in a way that captures the main points with a minimum of abstraction.
Simplifying assumptions may be necessary to solve a particular problem,
but they may not generalize to other problems.
Another issue that arises in mapping English to a formal
notation is that adjectives may have complex interactions with the
nouns they modify. In particular,
degree adjectives like "big" and "small" are
relative to a standard determined by the noun: a big mouse is
much smaller than a small elephant. By blindly mapping
adjectives and common nouns into one-place predicates, one system made
a serious blunder. It mapped the sentence "Sam is a good musician"
into two Prolog facts:
Besides these complexities, natural languages pose many philosophical
problems, especially in talk about knowledge and belief, hopes and
fears, intentions and expectations, tenses and modalities. Many of
these problems are still unsolved in their full generality; but for
many of them, the Prolog programmer can adopt a special-case solution
that is adequate for the task at hand. Fortunately, many practical
problems lie within the subset that Prolog can easily represent. But
the problem solver (and poser) should recognize the areas where
difficulties can be expected.
Standard logic has two basic quantifiers: the universal
quantifier (∀ Some examples may help to clarify these three principles.
With an existential quantifier, the sentence, "I own
a fuzzy gray sofa," could be represented,
When an existential quantifier follows a universal quantifier, it must
be represented by a function symbol. As an example,
consider the sentence, "Every person has a mother." That may
be paraphrased, "For every P, there exists an M such that M is
a mother of P if P is a person." If Prolog had quantifiers,
that sentence could be written,
As a more complex example, take the sentence, "Every chicken coop
has a chicken that is pecked by every other chicken in the
coop." The first part of this sentence, "Every chicken coop
has a chicken," has the same structure as "Every person has a
mother," but the extra clause at the end makes it more
complex. To map it into Prolog, first select predicates The third method of handling existential quantifiers results from
the way quantifiers interact with negation.
In standard logic:
Since variables that occur only in the condition part of a Prolog
rule are effectively governed by an existential quantifier, a problem
occurs in expressing conditions that contain universal
quantifiers. Consider the sentence, "Every mother whose children
are all above average is a super mom." The following rule does
not accurately represent the meaning:
In order to express quantifiers in a more natural way,
McCord introduces the notion of focalizers in
Chapter 5. He uses the focalizer Before writing rules to define predicates, a Prolog programmer must
decide what data structures the rules will process. The choice of
structure has a major effect on the way rules are written and
the efficiency of their execution. As an example, consider Exercise 6
at the end of this chapter:
In the farmer problem, the state of the system is defined by the
position of each of the four items: farmer, wolf, goat, and
cabbage. (The boat, the fifth item, can be ignored, since it must
always be on the same side as the farmer.) There are two major
choices of data structures for this problem:
A structure of four variables can be represented as a Prolog function
symbol applied to four arguments. A suitable function
is
Given the data structure There are three other kinds of moves: the
farmer takes the wolf across, the goat across, or
the cabbage across. Following is the rule for moving the wolf with
the farmer:
The other choice of data structure
for this problem is a pair of sets.
To represent pairs, Prolog provides
the dot operator, written as a period between two
items. The pair Sets are commonly used in logic and mathematics, but very few
programming languages support them directly. Instead, most
languages provide some kind of ordered list or vector. To represent
a true set, the ordering must be ignored. In Prolog, lists are
represented as a sequence of items connected with dots followed by
the atom Subtle Properties of English
like(C,F) <- cat(C) & fish(F).
This rule says that C likes F if C is a cat and F is a fish.
The reason for this difference is that a proper name normally
designates a unique individual within a given context. Therefore the
fact
like(X,Y) <- named(X,sam) & named(Y,jane)
& live(X,'23 Main St.')
& live(Y,'19 Blossom Lane').
The general principle that each individual must be identified by a
unique constant is always true. But when names are not unique,
that constant must be something more specific, such as a social
security number. Except in unusual circumstances, common nouns apply
to multiple individuals. Therefore they typically map into predicates
rather than constants.
friend(me,thothmes). friend(thothmes,me).
The sentence "Friends like each other" uses the phrase "each
other" to abbreviate two statements: X likes Y if X is a friend
of Y; and Y likes X if X is a friend of Y.
like(X,Y) <- friend(X,Y).
like(Y,X) <- friend(X,Y).
Actually, only one of these rules would be needed if the system
guaranteed that the
eat(thothmes,X) <- like(thothmes,X).
When this rule is added to the previous rules, it leads to the
conclusion that Thothmes eats me. One way to limit his appetite
is to amend the specification to say "My cat eats X if he likes
X and X is not a friend of his":
eat(thothmes,X) <- like(thothmes,X)
& ^friend(X,thothmes).
This rule seems reasonable, since it would allow Thothmes to make
friends with Tweety without eating him while still eating other birds.
happy(M) <-
man(M) & woman(W) & like(M,W) & like(W,M).
The sentence "Bertha likes any man who likes her" causes trouble
for about 50% of the people who translate it into Prolog. Those who
translate it into the following rule are lucky:
like(bertha,M) <- man(M) & like(M,bertha).
The unfortunate ones map it into the following rule:
like(bertha,M) <- like(M,bertha) & man(M).
Both of these rules are recursive. But
the first one checks whether M is a man before calling itself, and
the second one calls itself recursively before checking M. In the
first case,
like(norbert,bertha)
like(pierre,bertha)
like(bruno,bertha)
The second rule, however, calls
itself immediately. It gets into a recursive loop where it
keeps issuing the same subgoal
Clyde is an elephant.
Elephant is a species.
----------------------
Therefore Clyde is a species.
A naive mapping of that syllogism into Prolog would lead to exactly
the same fallacy:
isa(clyde,elephant).
isa(elephant,species).
isa(X,Z) <- isa(X,Y) & isa(Y,Z).
Given these two facts and rule, Prolog would conclude that the
goal
type(clyde,elephant).
named(es1,elephant). type(es1,species).
The first line says that clyde is of type elephant. The second line says
that there exists some entity identified as
good(sam). musician(sam).
Then it mapped the sentence "Sam is a bad cook" into the
following facts:
bad(sam). cook(sam).
From these four facts, it answered "yes" to all of the
following questions: Is Sam a good cook? Is Sam a bad musician? Is
Sam a good bad musician cook? The error here results from the fact that
"cook" and "musician" do not designate
natural types, but role types. Adjectives like "good" and
"bad" do not apply to Sam as a person, but to his role as cook or
musician. The mapping into Prolog (or any other logical form) must
recognize the roles and the ways of qualifying them.
Representing Quantifiers
thing(X).
from page &pthing;
could be read "for all X, X is
a thing".
Because of this convention, universal quantifiers in logic are
usually easy to map into Prolog. Existential quantifiers, however,
must be handled differently in different contexts:
(∃ X) (own(me,X) & fuzzy(X) & gray(X) & sofa(X)).
In this formula, the sofa has no name. Instead, it is introduced by
the quantifier (∃ X) to indicate "there exists
an X." Since (∃ X) does not follow any universal
quantifiers, X may be replaced by some constant, such as
own(me,sf1). fuzzy(sf1). gray(sf1). sofa(sf1).
(∀ P) (∃ M) mother(M,P) <- person(P).
In standard Prolog, the universal quantifier (∀
mother(m1,P) <- person(P).
This rule says that for all P,
mother(mom(P),P) <- person(P).
This rule may be read, "For all P,
chicken(loser(X)) <- coop(X).
loc(loser(X),X) <- coop(X).
peck(Y,loser(X)) <- coop(X) & chicken(Y)
& loc(Y,X) & ^(Y = loser(X)).
These three rules may be read "The loser of X is a chicken
if X is a coop; the loser of X is located
in X if X is a coop; and Y pecks the loser of X if X is a
coop, Y is a chicken, Y is located in X, and Y is not
the same as the loser of X."
(∀ X) ^P(X) is identical to ^(∃ X) P(X).
(∃ X) ^P(X) is identical to ^(∀ X) P(X).
The first rule says that for all X, P is false if and only if
it is false that there exists an X for which P is true.
The second rule says that there exists an X for which P is
false if and only if it is false that for all X, P is true.
These two rules can be summarized in the following
principle: when a quantifier moves in or out of a context
governed by a negation, ∀ becomes ∃,
and ∃ becomes ∀.
In applying this principle
to Prolog, note that the standard logic conditional "P if Q"
is equivalent to "P or not Q." Similarly,
the Prolog
(∀ M) (∀ X) (∀ Y)
mother_in_law(M,X) <- mother(M,Y) & married(X,Y).
The quantifiers (∀
(∀ M) (∀ X) mother_in_law(M,X) <- (∃ Y) mother(M,Y)
& married(X,Y).
This may be read, "For all &M and X, M is a mother in law of X if
there exists a Y where M is a mother of Y and X is married
to Y." Although Prolog does not use explicit quantifier symbols,
variables that occur only after the arrow have this existential effect.
supermom(M) <- mother(M,C) & above_avg(C).
This rule may be read, "M is a super mom if there exists a C where
&M is a mother of C and C is above average." Notice that C is
effectively bound by an existential quantifier, since it occurs only
in the condition. Therefore the rule does
not exclude the possibility that other children of M may be below
average. To exclude those cases, some negations are needed:
supermom(M) <- mother(M,C) &
^(mother(M,D) & ^above_avg(D)).
In this rule, D occurs within a negative context nested inside another
negative context (the condition). Therefore the implicit quantifier that
governs D flips from ∀ when it is in front of the formula to
∃ when it moves after the arrow and back to ∀ when it occurs
in the nested negative context. Therefore this rule may be
read, "M is a supermom if there exists a C where M is a
mother of C and it is false that for all D where M is a mother
of D, D is not above average." This contorted way of
expressing universal quantifiers by double negations
is also required in certain database query languages.
supermom(M) <- mother(M,C)
& all(mother(M,D), above_avg(D)).
This rule may be read, "M is a supermom if there exists
a C where M is a mother of C and for all cases where M is
a mother of D, D is above average." The
focalizer
all(P,Q) <- ^(P & ^Q).
In this rule, P and Q are metavariables, which match
arbitrary predications or combinations of predications.
The body of the rule invokes P and Q as goals to be
proved. This rule says that Choosing a Data Structure
A farmer has a wolf, a goat, and a cabbage (a very large one).
He wants to get all three of them plus himself across a river,
but his boat is only large enough to hold one item plus himself.
How can he cross the river without leaving the wolf alone with
the goat or the goat alone with the cabbage?
This is a typical state-transition problem where the starting state
has all four items (plus the boat) on one side, and the goal
state has everything on the other side. In between are
various intermediate states where some things are on one side and
some things are on the other side.
This description has three words that indicate data
structures: "structure," "pair," and "set." Before
writing rules for this problem, the programmer must decide how to
map these data structures into Prolog terms.
loc(Farmer_loc, Wolf_loc, Goat_loc, Cabbage_loc)
This data structure is analogous to the record structures used in many
programming languages, such as Pascal. The similarity is more striking
when each argument in the Prolog structure is written on a separate
line:
.sk
.cp 1i
Prolog Structure Pascal Record
loc type loc = record
(Farmer_loc, farmer: string,
Wolf_loc, wolf: string,
Goat_loc, goat: string,
Cabbage_loc) cabbage: string
end
The Prolog structure has a function named
move(loc(F,W,G,C), loc(F2,W,G,C)) <- opp(F,F2)
& safe(loc(F2,W,G,C)).
This rule illustrates a powerful feature of Prolog: in most languages,
the head of a procedure lists variable names for the parameters,
and the body of the procedure uses operators that extract substructures
from the input variables. Then it uses other operators to assemble the
output. In Prolog, however, the extraction and assembly can be done
automatically by pattern matching with structures in the head of
a rule. The above rule could be written in a style similar to
more conventional languages by using the
move(Current,Next) <-
Current=loc(F,W,G,C) & opp(F,F2) &
Next=loc(F2,W,G,C) & safe(Next).
In this version, the subgoal
move(Current,Next) <-
Current=loc(F,W,G,C) & F=W & opp(F,F2) & W2=F2 &
Next=loc(F2,W2,G,C) & safe(Next).
This rule says that if the current state is
move(loc(F,F,G,C), loc(F2,F2,G,C)) <- opp(F,F2)
& safe(loc(F2,F2,G,C)).
The rules for moving the goat and the cabbage are
analogous:
move(loc(F,W,F,C), loc(F2,W,F2,C)) <- opp(F,F2)
& safe(loc(F2,W,F2,C)).
move(loc(F,W,G,F), loc(F2,W,G,F2)) <- opp(F,F2)
& safe(loc(F2,W,G,F2)).
The predicate
opp(east,west). opp(west,east).
In determining whether a state is safe, the critical item is the
goat, which can either eat the cabbage or be eaten by the wolf.
The next two rules say that a state is safe if either the farmer is on
the same side as the goat or everything else is on the opposite side
from the goat:
safe(loc(F,W,F,C)).
safe(loc(F,F,G,F)) <- opp(F,G).
Given these rules, the farmer problem is completely defined. The only
thing that is needed is a general search procedure that tries to
find a path of safe states from the start to the goal:
Start state: loc(west,west,west,west)
Goal state: loc(east,east,east,east)
Suitable search procedures are defined on page &xdepth;.
a.X.c.(Y.Z).'My Old Kentucky Home'. 7037 .xyz
farmer(north).wolf(south).goat(drowned).cabbage(eaten)
f(g(X),39).h(ABC).z(smith).order('One dozen eggs')
a.b.c.d.e.f.g.h.nil
The atom