PROLOG.ART ·
ART ·
24.2 KB ·
1980-01-01 ·
from CompuLink-User-Group_Magazette_Vol-2-Issue-1_1986
Prolog Tutorial Introduction
Probably you have heard of the language PROLOG within the last year
or so. You probably wondered the following things:
1) What does the name stand for? Names of computer languages are
almost always acronyms.
2) What is it good for?
3) Why now?
4) Can I get a copy to play with?
The answer to the fourth question is easy, you order it from the
COMPULINK software library - COMUG disk 157. Here are the answers to
the other three questions.
1) The name stands for "programming in logic." This we shall
elaborate on in depth later on.
2) PROLOG is good for writing question answering systems. It is
also good for writing programs that perform complicated strategies that
compute the best or worst way to accomplish a task, or avoid an
undesirable result.
3) PROLOG was virtually unknown in this country until researchers in
Japan announced that it was to be the core language of that country's
fifth generation computer project. This is the project with which
Japan hopes to achieve a domainant position in the world information
industry of the 1990's.
PROLOG is one of the most unusual computer languages ever invented.
It cannot be compared to FORTRAN, PASCAL, "C", or BASIC. The
facilities complement, rather than replace those of conventional
languages. Although it has great potential for database work, it has
nothing in common with the database languages used on microcomputers.
Perhaps the best point to make is that while conventional languages
are prescriptive, PROLOG is descriptive. A statement in a conventional
language might read:
if( car_wheels = TRUE ) then
begin
(some sort of procedure)
X = X + 1;
end
A statment in PROLOG could just be a statment of fact about cars and
wheels. There are many relationships that hold. For instance,
has( car, wheels ).
has( car, quant(wheels, four) ).
round( wheels ).
Each of these statments is an independent fact relating cars,
wheels, and the characteristics of wheels. Because they are
independent, they can be put into a PROLOG program by programmers
working separately. The man who is a specialist on car bodies can say
his thing, the wheel specialist can have his say, and the participants
can work with relative independence. And this brings to light a major
advantage of PROLOG: -- PARALLEL PROGRAMMING !!!
With conventional programming languages projects can still be
"chunked", or divided between programmers. But efficiency on a team
project drops drastically below that of the individual programmer
wrapped up in his own trance. As the number of participants grows the
need for communication grows geometrically. The time spent
communicating can exceed that spent programming! Although PROLOG does
not eliminate the need for task coordination, the problem is
considerably simplified. It also provides the ability to answer
questions in a "ready to eat form." Consider your favorite BASIC
interpreter. Based upon the statements about cars and wheels
previously given, could you ask it the following question?
has( car, X ), round( X ).
Does a car have anything which is round? The question instructs the
PROLOG interpreter to consider all the objects that it knows are
possessed by a car and find those which are round. Perhaps you are
beginning to guess that PROLOG has the abilities of a smart database
searcher. It can not only find the facts but selectively find them and
interpret them. Consider the problem of a fault tree, as exemplified
by this abbreviated one:
{Car won't start}
|
[Engine turns over](No) --> [Battery voltage](no)-\\
(Yes) v
| {Check battery}
|
[Smell gasoline](yes) --> {Try full throttle cranking}
| (failure)
/--------/ |
The fault tree is easily programmed in BASIC. Later we shall show
that PROLOG supplies a superior replacement for the fault tree. Though
the tree is capable of diagnosing only the problem for which it was
designed, PROLOG dynamically constructs the appropriate tree from facts
and rules you have provided. PROLOG is not limited to answering one
specific question. Given enough information, it will attempt to find
all deductive solutions to any problem.
PROLOG PRIMER
I. Rules and Facts
This is where you should start if you know nothing about PROLOG.
Let us consider a simple statment in PROLOG, such as:
1) has( car, wheels ).
This statement is a "fact. The word "has" in this statment is known
either as a functor or predicate. It is a name for the relationship
within the parenthesis. It implies that a car has wheels. But the
order of the words inside the bracket is arbitrary and established by
you. You could just as easily say:
2) has( wheels, car ).
and if you wrote this way consistently, all would be well. The
words has, wheels, and car are all PROLOG atoms. "Wheels" and "car"
are constants.
A database of facts can illustrate the data retrieval capabilities
of PROLOG. For instance:
3) has( car, wheels ).
has( car, frame ).
has( car, windshield ).
has( car, engine ).
You could then ask PROLOG the question:
4) has( car, Part ).
The capital "P" of Part means that Part is a variable. PROLOG will
make Part equal to whatever constant is required to make the question
match one of the facts in the database. Thus PROLOG will respond:
Part = wheels.
More?(Y/N):
If you type "y" the next answer will appear:
Part = frame.
More?(Y/N):
If you continue, PROLOG will produce the answers Part = windshield
and Part = engine. Finally, you will see:
More?(Y/N):y
No.
indicating that PROLOG has exhausted the database. Incidentally,
when a variable is set equal to a constant or other variable, it is
said to be instantiated to that object.
Notice that PROLOG searches the database forwards and in this case,
from the beginning. The forward search path is built into PROLOG and
cannot be changed. An author of a program written in a prescriptive
language is quite conscious of the order of execution of his program,
while in PROLOG it is not directly under his control.
The other major element is the rule which is a fact which is
conditionally true. In logic this is called a Horn clause:
5) has( X, wheels ) :- iscar( X ).
The fact iscar( car ) and the above rule are equivalent to
6) has( car, wheels).
The symbol :- is the "rule sign." The expression on the left of :-is
the "head" and on the right is the body. The variable X has scope of
the rule, which means that it has meaning only within the rule. For
instance, we could have two rules in the database using identically
named variables.
7) has( X, transportation ) :-
has( X, car ), has( license, X ).
8) has( X, elephant ) :- istrainer( X ), hasjob( X ).
The variables X in the two expressions are completely distinct and
have nothing to do with each other.
The comma between has( X, car ) and has( license, X ) means "and" or
logical conjuction. The rule will not be true unless both the clauses
has(X, car) and has( license, X ) are true.
On the other hand if there is a rule
9) has( license, X ) :- passedexam( X ).
consider what PROLOG will do in response to the question:
10) has( harry, transportation ).
(Notice that harry has not been capitalized because we do not want
it taken as a variable. We could, however, say 'Harry' enclosed in
single quotes.)
It will scan the database and use (7), in which X will be
instantiated to harry. The rule generates two new questions:
11) has( harry, car ).
12) has( license, harry ).
Assuming that harry has a car, the first clause of (7) is satisfied
and the database is scanned for a match to (12). PROLOG picks up rule
(9) in which X is instantiated to harry and the question is now posed:
13) passedexam( harry ).
If there is a fact:
passedexam( harry ).
in the database then all is well and harry has transportation. If
there is not, then PROLOG will succinctly tell you:
No.
But suppose Harry has money and can hire a chauffer as any good
programmer can. That could be made part of the program in the
following way.
The rule which PROLOG tried to use was:
14) has( X, transportation ) :-
has( X, car ), has( license, X ).
At any point following it there could be included another rule:
15) has( X, transportation ) :- has( X, money ).
or simply the bald fact:
16) has( harry, transportation ).
These additional rules or facts would be used in two circumstances.
If at any point a rule does not yield a solution, PROLOG will scan
forward from that rule to find another applicable one. This process is
known as "backtracking search" and can be quite time consuming.
If in response to the "More?" prompt you answer "y" PROLOG will
search for an additional distinct solution. It will attempt to find an
alternate rule or fact for the last rule or fact used. If that fails,
it will back up to the antecedent rule and try to find an alternate
antecedent. And it will continue to back up until it arrives at the
question you asked, at which point it will say:
No.
"Antecedent" to a rule means that it gave rise to its' use. For
example, (7) is the antecedent of (9) in the context of the question
(16).
II. Grammar
It is a boring subject, but it must be discussed. All PROLOG
statements are composed of valid terms, possibly a rule sign (":- "),
commas representing conjunction ("and"), and a period at the very end.
A term is a structure, constant, variable, or number.
What is a structure? It is a kind of grouping:
1) Structures consist of a functor, and a set of objects or
structures in parenthesis.
2) Objects are constants, variables, numbers, or lists, which we
have not discussed yet.
3) A constant or functor must be a string of letters and numbers,
beginning with a lower case letter, unless you choose to enclose it in
single quotes ( 'howdy pardner' ), in which case you are freed from
these restrictions.
4) A variable must be a string of letters and numbers beginning with
a capital letter.
5) A functor may optionally have arguments enclosed in parenthesis ,
as in: hascar( X ) or hascar.
An example: "has( X, transportation )." is a structure.
III. Input / Output
You now know enough to write simple databases and interrogate them
profitably. But before we examine more sophisticated examples, it will
be necessary to add input and output to the language. There are built
in functions which appear as rules which are satisfied once. Thus the
statment:
write( 'Hello world.' ).
can be included on the right side of a rule:
greetings( X ) :- ishuman( X ), write( 'Hello world.' ). You can
also write "write( X )" where X is some variable. Note that 'Hello
world.' is not enclosed in double quotes. Single quotes, which denote
a constant, are required. Double quotes would denote a list, which is
another thing entirely.
Provided that a match to "ishuman" can be found, the builtin
function "write" is executed and the message printed to the screen.
The builtin read( X ) reads a "structure" that you input from the
keyboard. More formally, we have
read( <variable> or <constant> )
write( <variable> or <constant> )
If you write read( Input ), then the variable "keyboard" will be
assigned to whatever is typed at the keyboard, provided that the input
is a valid PROLOG structure. The builtin "read" will fail if instead
of Keyboard we wrote read( baloney ), where "baloney" is a constant,
and the user at the keyboard did not type exactly "baloney."
When you input a structure in response to a "read" statement, be
sure to end it with a period and an <ENTER>.
There is a convenient way of putting the cursor on a new line. This
is the builtin "nl". For example:
showme :- write( 'line 1' ), nl, write( 'line 2' ).
would result in:
line 1
line 2
There is also a primitive form of input/output for single
characters. It will be discussed later.
IV. A Fault Tree Example
Consider the "won't start" fault tree for an automobile:
{Car won't start}
|
[Engine turns over](No) --> [Battery voltage](no)-\\
(Yes) v
| {Check battery}
|
[Smell gasoline](yes) --> {Try full throttle cranking}
| (failure)
/--------/ |
| /------------------------/
| |
| [Check for fuel line leaks](yes)-->{Replace fuel line}
| (no)
| |
| [Check for defective carburator](yes)--\\
| (no) v
| {Repair carburator}
\\----\\
|
|
[Is spark present](no)-->[Do points open and close](no)-\\
| (yes) v
/----/ | {Adjust points}
| /------------------------/
| |
| [Pull distributor wire, observe spark](blue)--\\
| (orange) v
| | {Check plug wires & cap}
| |
| [Measure voltage on coil primary](not 12V)--\\
| (12V) v
| | {Check wiring, ballast resistor}
| |
| [Check condenser with ohmmeter](conducts)--\\
| (no conduction) v
| | {Replace condenser}
| |
| [Open and close points](voltage not 0 - 12)--\\
| (voltage swings 0 - 12) v
| | {Fix primary circuit}
| |
| {Consider hidden fault, swap components]
|
|
\\-------{Call a tow truck!!}
A PROLOG program to implement this is simple. Each statment
represents a decision point fragment of the tree. The PROLOG
interpreter dynamically assembles the tree as it attempts a
solution.
'car wont start' :- write( 'Is the battery voltage low?' ),
affirm, nl,
write( 'Check battery' ).
'car wont start' :- write( 'Smell gasoline?' ),
affirm, nl,
'fuel system'.
'fuel system' :- write( 'Try full throttle cranking' ).
'fuel system' :- write( 'Are there fuel line leaks?' ),
affirm, nl,
write( 'Replace fuel line.' ).
'fuel system' :- write( 'Check carburator' ).
'car wont start' :- write( 'Is spark present?' ),
not( affirm ), nl,
'no spark'.
'no spark' :- write( 'Do points open and close?' ),
not( affirm ), nl,
write( 'Adjust or replace points.' ).
'no spark' :- write( 'Is the spark off the coil good?' ),
affirm,
write( 'Check plug wires and cap.' ).
'no spark' :- write( 'What is the voltage on the primary
of the coil: ' ),
read( Volts ),
Volts < 10,
nl,
write('Check wiring and ballast resistor.').
'no spark' :- write( 'Does the capacitor leak?' ),
affirm,
write( 'Replace the capacitor.' ).
'no spark' :- not( 'primary circuit' ).
'primary circuit'
:- write( 'Open the points. Voltage across
coil?:'), nl,
read( Openvolts ), Openvolts < 1,
write( 'Close the points. Voltage across
coil?:'),
read( Closevolts ), Closevolts > 10, nl,
write( 'Primary circuit is OK.' ).
'no spark' :- write( 'Consider a hidden fault. Swap
cap, rotor,points,capacitor.' ).
'Car wont start' :- write( 'Get a tow truck!!' ).
--End program--
The above is a simple example of an expert system. A
sophisticated system would tell you exactly the method by which
it has reached a conclusion. It would communicate by a "shell"
program written in PROLOG which would accept a wider range of
input than the "valid structure" required by the PROLOG
interpreter directly.
V. Lists
Consider a shopping list given you by your wife. It is a
piece of paper with items written on it in an order that probably
symbolizes their importance. At the top it may say EGGS!!!,
followed by carrots, hamburger, and finally a flea collar for the
dog, if you can find one. In PROLOG such a list would be written:
1) [eggs, carrots, hamburger, fleacollar]
The order of a list is important so that eggs and carrots cannot
be reversed and PROLOG be uncaring.
Let us put the list in a structure:
shopping( [eggs, carrots, hamburger, fleacollar] ).
Then if you wished to isolate the head of the list you could ask
the question:
shopping( [ Mostimportant | Rest ] ).
and PROLOG would respond:
Mostimportant = eggs,
Rest = [carrots, hamburger, fleacollar].
The vertical bar "|" is crucial here. It is the string extraction
operator, which performs a combination of the CDR and CAR
functions of LISP. When it appears in the context [X|Y] it can
separate the head of the list from the rest, or tail.
You may have gained the impression that PROLOG is a rather static
language capable of answering simple questions, but it is far more
powerful than that. The string extraction operator is the key. It
permits PROLOG to whittle a complex expression down to the bare
remainder. If the rules you have given it permit it to whittle the
remainder down to nothing, then success is achieved. An example of
this is the definition of "append." Let us suppose you have not yet
done yesterday's shopping, let alone today's. You pull it out of your
wallet and sootch tape it to the list your wife just gave you.
Yesterday's list was:
[tomatoes, onions, ketchup]
Combined with [eggs, carrots, hamburger, fleacollar] we obtain
[eggs,carrots,hamburger,fleacollar,tomatoes,onions,garlic].
To take one list and to attach it to the tail of another list is to
"append" the first to the second. The PROLOG definition of append is:
Rule1: append( [], L, L ).
Rule2: append( [X|List1], List2, [X|List3] ) :-
append( List1, List2, List3 ].
The general scheme is this: The definition consists of one rule and
one fact. The rule will be used over and over again until what little
is left matches the fact. The [] stands for empty list, which is like
a bag without anything in it. This is an example of a recursive
definition. Suppose we ask:
append( [a,b,c], [d,e,f], Whatgives ).
1. Rule 2 is invoked with arguments ( [a,b,c], [d,e,f], Whatgives).
2. Rule 2 is invoked again with arguments: ( [b,c], [d,e,f], List3).
3. Rule 2 is invoked again with arguments: ( [b], [d,e,f], List3.
4. The arguments are now ([], [d,e,f], List3 ).
Rule 1 now matches. End.
How does this cause a list to be constructed? The key is to watch
the third argument. Supplied by the user, it is named
"Whatgives". The inference engine matches it to [X|List3] in rule
2. Now lets trace this as rule two is successivly invoked:
Whatgives
|
v
Rule2: [X|List3] (List3 = [b,c])
| \\
v \\
Rule2: a [X'|List3'] (List3' = [c])
| \\
v \\
Rule2: b [X''|List3''] (List3'' = [], ie., empty set.)
| \\
Rule1: c L ( in Rule1 = [d,e,f] )
End.
L in rule 1 is [d,e,f] for the following reason: Notice that rule
2 never alters List2. It supplies it to whatever rule it invokes.
So L in rule 1 is the original List2, or [a,b,c].
This example would not have worked if the order of rules one
and two were reversed. The PROLOG inference engine always
attempts to use the the first rule encountered. You could imagine
it as always reading your program from the top down in attempting
to find an appropriate rule. Since rule 2 would always satisfy,
an unpleasant thing would have happened if the order were
reversed. The program would loop forever.
I hope that this tiny introduction to PROLOG whets your
appetite. You should now purchase the book
Programming In Prolog
W.F. Clocksin and C.S. Mellish
Springer - Verlag
Berlin,Heidelberg,New York. 1981,1984