Prolog
1. Basic Introduction of Prolog
Prolog (programming in logic) is one of the most widely used programming languages
in artificial intelligence research. As opposed to imperative languages such as C or Java
(which also happens to be object-oriented) it is a declarative programming language.
That means, when implementing the solution to a problem, instead of specifying how
to achieve a certain goal in a certain situation, we specify what the situation (rules and
facts) and the goal (query) are and let the Prolog interpreter derive the solution for
us. Prolog is very useful in some problem areas, such as artificial intelligence, natural
language processing, databases, . . . , but pretty useless in others, such as graphics or
numerical algorithms.
The following three are
well-known titles, but you may also consult any other textbook on Prolog.
• I. Bratko. Prolog Programming for Artificial Intelligence. 3rd edition, Addison-
Wesley Publishers, 2001.
• F. W. Clocksin and C. S. Mellish. Programming in Prolog. 5th edition, Springer-
Verlag, 2003.
• L. Sterling and E. Shapiro. The Art of Prolog. 2nd edition, MIT Press, 1994.
2. Getting Started: An Example
In the introduction it has been said that Prolog is a declarative (or descriptive) language.
Programming in Prolog means describing the world. Using such programs means asking
Prolog questions about the previously described world. The simplest way of describing
the world is by stating facts, like this one:
bigger(elephant, horse).
This states, quite intuitively, the fact that an elephant is bigger than a horse. (Whether
the world described by a Prolog program has anything to do with our real world is, of
course, entirely up to the programmer.) Let’s add a few more facts to our little program:
bigger(elephant, horse).
bigger(horse, donkey).
bigger(donkey, dog).
bigger(donkey, monkey).
This is a syntactically correct program, and after having compiled it we can ask the Prolog
system questions (or queries in proper Prolog-jargon) about it. Here’s an example:
?- bigger(donkey, dog).
Yes
The query bigger(donkey, dog) (i.e. the question “Is a donkey bigger than a dog?”)
succeeds, because the fact bigger(donkey, dog) has previously been communicated to
the Prolog system. Now, is a monkey bigger than an elephant?
?- bigger(monkey, elephant).
No
No, it’s not. We get exactly the answer we expected: the corresponding query, namely
bigger(monkey, elephant) fails. But what happens when we ask the other way round?
?- bigger(elephant, monkey).
No
According to this elephants are not bigger than monkeys. This is clearly wrong as far as
our real world is concerned, but if you check our little program again, you will find that
it says nothing about the relationship between elephants and monkeys. Still, we know
that if elephants are bigger than horses, which in turn are bigger than donkeys, which in
turn are bigger than monkeys, then elephants also have to be bigger than monkeys. In
mathematical terms: the bigger-relation is transitive. But this has also not been defined
in our program. The correct interpretation of the negative answer Prolog has given is
the following: from the information communicated to the system it cannot be proved
that an elephant is bigger than a monkey.
If, however, we would like to get a positive reply for a query like bigger(elephant,
monkey), we have to provide a more accurate description of the world. One way of doing
this would be to add the remaining facts, like e.g. bigger(elephant, monkey), to our
program. For our little example this would mean adding another 5 facts. Clearly too
much work and probably not too clever anyway.
The far better solution would be to define a new relation, which we will call
is_bigger, as the transitive closure (don’t worry if you don’t know what that means)
of bigger. Animal X is bigger than animal Y either if this has been stated as a fact or if
there is an animal Z for which it has been stated as a fact that animal X is bigger than
animal Z and it can be shown that animal Z is bigger than animal Y. In Prolog such
statements are called rules and are implemented like this:
is_bigger(X, Y) :- bigger(X, Y).
is_bigger(X, Y) :- bigger(X, Z), is_bigger(Z, Y).
In these rules :- means something like “if” and the comma between the two terms
bigger(X, Z) and is_bigger(Z, Y) stands for “and”. X, Y, and Z are variables, which
in Prolog is indicated by using capital letters.
You can think of the the bigger-facts as data someone has collected by browsing
through the local zoo and comparing pairs of animals. The implementation of is_bigger,
on the other hand, could have been provided by a knowledge engineer who may not
know anything at all about animals, but understands the general concept of something
being bigger than something else and thereby has the ability to formulate general rules
regarding this relation. If from now on we use is_bigger instead of bigger in our
queries, the program will work as intended:
?- is_bigger(elephant, monkey).
Yes
Prolog still cannot find the fact bigger(elephant, monkey) in its database, so it tries
to use the second rule instead. This is done by matching the query with the head of the
rule, which is is_bigger(X, Y). When doing so the two variables get instantiated: X =
elephant and Y = monkey. The rule says that in order to prove the goal is_bigger(X,
Y) (with the variable instantiations that’s equivalent to is_bigger(elephant, monkey))
Prolog has to prove the two subgoals bigger(X, Z) and is_bigger(Z, Y), again with
the same variable instantiations. This process is repeated recursively until the facts
that make up the chain between elephant and monkey are found and the query finally
succeeds.
3. Prolog Syntax
This section describes the most basic features of the Prolog programming language.
1. Terms
The central data structure in Prolog is that of a term. There are terms of four kinds:
atoms, numbers, variables, and compound terms. Atoms and numbers are sometimes
grouped together and called atomic terms.
Atoms.: Atoms are usually strings made up of lower- and uppercase letters, digits, and
the underscore, starting with a lowercase letter. The following are all valid Prolog atoms:
elephant, b, abcXYZ, x_123, another_pint_for_me_please
On top of that also any series of arbitrary characters enclosed in single quotes denotes
an atom.
’This is also a Prolog atom.’
Finally, strings made up solely of special characters like + - * = < > : & (check the
manual of your Prolog system for the exact set of these characters) are also atoms.
Examples:
+, ::, <------>, ***
Numbers.: All Prolog implementations have an integer type: a sequence of digits,
optionally preceded by a - (minus). Some also support floats. Check the manual for
details.
Variables.:" Variables are strings of letters, digits, and the underscore, starting with a
capital letter or an underscore. Examples:
X, Elephant, _4711, X_1_2, MyVariable, _
The last one of the above examples (the single underscore) constitutes a special case.
It is called the anonymous variable and is used when the value of a variable is of no
particular interest. Multiple occurrences of the anonymous variable in one expression
are assumed to be distinct, i.e. their values don’t necessarily have to be the same.
Compound terms.: Compound terms are made up of a functor (a Prolog atom) and
a number of arguments (Prolog terms, i.e. atoms, numbers, variables, or other compound
terms) enclosed in parentheses and separated by commas. The following are some
examples for compound terms:
is_bigger(horse, X), f(g(X, _), 7), ’My Functor’(dog)
It’s important not to put any blank characters between the functor and the opening
parentheses, or Prolog won’t understand what you’re trying to say. In other places,
however, spaces can be very helpful for making programs more readable.
The sets of compound terms and atoms together form the set of Prolog predicates.
A term that doesn’t contain any variables is called a ground term.
Clauses, Programs and Queries
In the introductory example we have already seen how Prolog programs are made up of
facts and rules. Facts and rules are also called clauses.
Facts. A fact is a predicate followed by a dot.
Examples:
bigger(whale, _).
life_is_beautiful.
The intuitive meaning of a fact is that we define a certain instance of a relation as being
true.
Rules.: A rule consists of a head (a predicate) and a body. (a sequence of predicates
separated by commas). Head and body are separated by the sign :- and, like every
Prolog expression, a rule has to be terminated by a dot.
Examples:
is_smaller(X, Y) :- is_bigger(Y, X).
aunt(Aunt, Child) :-
sister(Aunt, Parent),
parent(Parent, Child).
The intuitive meaning of a rule is that the goal expressed by its head is true, if we (or
rather the Prolog system) can show that all of the expressions (subgoals) in the rule’s
body are true.
Programs.: A Prolog program is a sequence of clauses.
Queries.: After compilation a Prolog program is run by submitting queries to the interpreter.
A query has the same structure as the body of a rule, i.e. it is a sequence
of predicates separated by commas and terminated by a dot. They can be entered at
the Prolog prompt, which in most implementations looks something like this: ?-. When
writing about queries we often include the ?-.
Examples:
?- is_bigger(elephant, donkey).
?- small(X), green(X), slimy(X).
Intuitively, when submitting a query like the last example, we ask Prolog whether all its
predicates are provably true, or in other words whether there is an X such that small(X),
green(X), and slimy(X) are all true.
Some Built-in Predicates
What we have seen so far is already enough to write simple programs by defining predicates
in terms of facts and rules, but Prolog also provides a range of useful built-in
predicates. Some of them will be introduced in this section; all of them should be explained
in manual of your Prolog system.
Built-ins can be used in a similar way as user-defined predicates. The important
difference between the two is that a built-in predicate is not allowed to appear as the
principal functor in a fact or the head of a rule. This must be so, because using them in
such a position would effectively mean changing their definition.
Goal Execution
Submitting a query means asking Prolog to try to prove that the statement(s) implied
by the query can be made true provided the right variable instantiations are made. The
search for such a proof is usually referred to as goal execution. Each predicate in the query
constitutes a (sub)goal, which Prolog tries to satisfy one after the other. If variables are
shared between several subgoals their instantiations have to be the same throughout the
entire expression.
If a goal matches with the head of a rule, the respective variable instantiations are
made inside the rule’s body, which then becomes the new goal to be satisfied. If the body
consists of several predicates the goal is again split into subgoals to be executed in turn.
In other words, the head of a rule is considered provably true, if the conjunction of all
its body-predicates are provably true. If a goal matches with a fact in our program the
proof for that goal is complete and the variable instantiations made during matching are
communicated back to the surface. Note that the order in which facts and rules appear
in our program is important here. Prolog will always try to match its current goal with
the first possible fact or rule-head it can find.
If the principal functor of a goal is a built-in predicate the associated action is executed
whilst the goal is satisfied. For example, as far as goal execution is concerned the
predicate
write(’Hello World!’)
will simply succeed, but at the same time it will also print the words Hello World! on
the screen.
As mentioned before the built-in predicate true will always succeed (without any
further side-effects), whereas fail will always fail.
Sometimes there is more than one way of satisfying the current goal. Prolog chooses
the first possibility (as determined by the order of clauses in a program), but the fact
that there are alternatives is recorded. If at some point Prolog fails to prove a certain
subgoal, the system can go back and try an alternative way of executing the previous
goal. This process is known as backtracking.
Prolog agrees with our own logical reasoning. Which is nice. But how did it come to its
conclusion? Let’s follow the goal execution step by step.
(1) The query mortal(socrates) is made the initial goal.
(2) Scanning through the clauses of our program, Prolog tries to match
mortal(socrates) with the first possible fact or head of rule. It finds mortal(X),
the head of the first (and only) rule. When matching the two terms the instantiation
X = socrates needs to be made.
(3) The variable instantiation is extended to the body of the rule, i.e. man(X) becomes
man(socrates).
(4) The newly instantiated body becomes our new goal: man(socrates).
(5) Prolog executes the new goal by again trying to match it with a rule-head or a fact.
Obviously, the goal man(socrates) matches the fact man(socrates), because they
are identical. This means the current goal succeeds.
(6) This, again, means that also the initial goal succeeds.
One of the major advantages of Prolog is that it allows for writing very short and compact
programs solving not only comparatively difficult problems, but also being readable and
(again: comparatively) easy to understand.
Of course, this can only work, if the programmer (you!) pays some attention to his
or her programming style. As with every programming language, comments do help.
In Prolog comments are enclosed between the two signs /* and */, like this:
/* This is a comment. */
Comments that only run over a single line can also be started with the percentage sign
%. This is usually used within a clause.
aunt(X, Z) :-
sister(X, Y), % A comment on this subgoal.
parent(Y, Z).
Besides the use of comments a good layout can improve the readability of your programs
significantly. The following are some basic rules most people seem to agree on:
(1) Separate clauses by one or more blank lines.
(2) Write only one predicate per line and use indentation:
blond(X) :-
father(Father, X),
blond(Father),
mother(Mother, X),
blond(Mother).
(Very short clauses may also be written in a single line.)
(3) Insert a space after every comma inside a compound term:
born(mary, yorkshire, ’01/01/1980’)
(4) Write short clauses with bodies consisting of only a few goals. If necessary, split
into shorter sub-clauses.
(5) Choose meaningful names for your variables and atoms.
Thanks For Reading.Keep Visiting.!!!
