| Copyright © Bill Wilson, 1998-2004 | Contact Info | Last updated: Fri, 16 Apr 2004 01:21:57 GMT |
Further information on Prolog can be found in the iProlog Programmer's Manual, especially the Reference Manual section, which contains descriptions of all built-in predicates in iProlog. You should use The Prolog Dictionary to clarify or revise concepts that you have already met. The Prolog Dictionary is not a suitable way to begin to learn about Prolog.
All references to Prolog should be interpreted as references to the locally available implementation of Prolog, Claude Sammut's iProlog.
More details on Prolog can be found in the class web page lecture notes section.
The concepts covered in this dictionary are limited to those relevant to COMP9414 Artificial Intelligence at the University of New South Wales, Sydney.
Other related dictionaries:
The AI Dictionary
- URL: http://www.cse.unsw.edu.au/~billw/aidict.html
The Machine Learning Dictionary
- URL: http://www.cse.unsw.edu.au/~billw/mldict.html
The NLP Dictionary (Natural Language Processing)
- URL: http://www.cse.unsw.edu.au/~billw/nlpdict.html
Other places to find out about artificial intelligence include the AAAI (American Association for Artificial Intelligence) AI Overview page or AI Reference Shelf
The URL of this Prolog Dictionary is http://www.cse.unsw.edu.au/~billw/prologdict.html
The following topics are currently covered in this dictionary, which is
limited to the Prolog concepts covered in COMP9414:
arity |
atom |
backtracking |
binding |
body |
built-in predicates |
clause |
comments |
cut |
debugging |
declarative |
functor |
goal |
head |
indentation |
list |
mutual recursion |
neck |
number |
output in Prolog |
predicate |
procedure |
query |
recursion |
relation |
rule |
structure |
succeed |
term |
testing |
underscore |
white space |
variable
likes, as in
likes(jane, pizza), is 2, as it takes two arguments, jane
and pizza.
Arity Example Could Mean ... 1 happy(fido).Fido is happy. 2 likes(jane, pizza).3 gave(mary, john, book).Mary gave John a book.
likes,
john, and pizza, in
likes(john, pizza). Atoms
of this type must start with a lower case letter.
They can include digits (after the initial lower-case letter)
and the underscore character (_).
<--->,
..., ===>. When using atoms of this
type, some care is needed to avoid using strings of special characters
with a predefined meaning, like the neck symbol
:-+,
-,
*,
/,
<,
>,
=,
:,
.,
&,
_, and
~.
Example: here is the definition of the standard Prolog predicate "member":
member(X, [X | Rest]). % X is a member if its the first element
member(X, [Y | Rest]) :-
member(X, Rest). % otherwise, check if X is in the Rest
You may not think of memberas a backtracking predicate, but
backtracking is built into Prolog, so in suitable circumstances,
memberwill backtrack:
: member(X, [a, b, c]) ? X = a X = b X = cHere
memberbacktracks to find every possible solution to
the query given to it. Consider also:
: member(X, [a, a, a]) ? X = a X = a X = aHere
memberbacktracks even though it keeps on finding the
same answer. What about
: member(a, [a, a, a]) ?In theory, Prolog should respond:
** yes ** yes ** yesHowever, in iProlog, this useless behaviour is inhibited, and a single
** yesis printed.The term backtracking also applies to seeking several sets of variable bindings to satisfy a single goal.
In some circumstances, it may be desirable to inhibit backtracking, as when only a single solution is required. The Prolog cut goal allows this.
For example, when attempting to respond to the query:
: lectures(john, Subject), studies(Student, Subject)?
the Prolog interpreter first finds a fact that indicates a subject
that John lectures - perhaps lectures(john, 9311). At this
point, the variable Subject is bound to 9311
(Subject = 9311). In other words, Subject, temporarily,
has the value 9311. Then Prolog tries to satisfy the second
goal studies(Student, Subject) with Subject = 9311,
i.e. to satisfy studies(Student, 9311). In doing so, if it
does find a solution, it will bind Subject to one or more
values (like jack) in turn. Then Prolog will
backtrack and undo the binding Subject = 9311 and look for
another value for Subject that satisfies
lectures(john, Subject), such as Subject = 9331, and
then proceed for appropriate bindings for Student again, with
the new binding for Subject.
:-. It has the form of a comma-separated list of goals, each of which is a functor, possibly followed by a
comma-separated list of arguments, in parentheses. E.g. in the rule
sister_of(X,Y) :- female(Y), same_parents(X,Y).
the two goals female(Y), same_parents(X,Y)form the body.
."). A clause
may be a fact, like:or a rule, like:likes(mary, pizza).
A group of clauses about the sameeats(Person, Thing) :- likes(Person, Thing), food(Thing).
%. The rest of the line after and including the %
is ignored by the Prolog interpreter. Examples:
% This is a full line comment.
% The next line contains a part-line comment.
member(Item, [Item|Rest]). % member succeeds if Item is 1st object in list.
Commenting Rules:
As in other programming languages, comments should be used freely to explain the
high-level significance of sections of code, to explain tricky sections of
code, etc. Comments should not echo what the code already clearly
says. Comments like that actually get in the way of understanding, for
example because they are likely to make the reader ignore the comments.
Where it is possible to make code understandable by using a meaningful
It is good practice to begin each Prolog procedure with a comment describing the predicate, e.g.
% member(Item, List) - succeeds if the item is a member of the list
If the list needs to have some special properties, e.g. if it must be a list of numbers, or must be instantiated (that is, have a value) at the time the predicate is called, then this header comment should say so:
% member(Item, List) - succeeds if the item is a member of the list; % List must be instantiated at the time member is called. Item need not % be instantiated.
It can be a good idea for the header comments to indicate examples of the kind of data on which the predicate is intended to operate, and what the result should be, if this can be done reasonably briefly. E.g.
% Examples of use: % : member(b, [a, b, c])? % ** yes % % : member(X, [a, b, c])? % X = a % X = b % X = c
Each file of Prolog code should begin with a (file) header comment, indicating who wrote the code, when, and what it is (overall) intended to do. This would be enough in a short Prolog assignment. In a "industrial strength" Prolog system, there would be details on the origins of algorithms used, and a revision history.
A good source of examples of Prolog commenting is example code made available in class, such as this one. Note however that this one is rather more heavily commented than usual, for instructional purposes. Note also that code examples presented on screen may be under-commented, because of the difficulty of fitting the comments and the code on the screen, and because the oral presentation accompanying the on-screen material replaces the comments to some extent.
Don't make your lines of comments (or code) too long - long lines can be hard to read, and really long lines may be folded, turning your neat formatting into a dog's breakfast. Stick to a maximum line length of 70 or 80 characters. Cute lines and/or boxes constructed of comment characters have the side effect of preventing the reader from seeing as much of your code at one time. The reader may then have to page up and down to figure out what your code does. They will not like you for this.
See also indentation.
!, which always succeeds, but cannot be backtrackedpast. It is used to prevent unwanted
backtracking, for example, to prevent extra solutions being found by
Prolog.
likes(mary, pizza), likesis the functor. In a more
complex structure, like
persondata(name(smith, john), date(28, feb, 1963))
persondata-
There is also a built-in predicate called functor, used
to extract the functor and arityof a structure
The use of this built-in predicate is outside the scope of this dictionary.
: lectures(john, Subject), studies(Student, Subject)?
lectures(john, Subject) and studies(Student, Subject).
A goal is something that Prolog tries to satisfy by finding
values of the Studentand Subject) that make the goal succeed.
:-. It normally has the form of a functor(i.e. a relationsymbol, followed by a comma-separated
list of parameters, in parentheses. E.g. in the rulesister_of(X,Y) :- female(Y), same_parents(X,Y).
sister_of(X,Y)is the head.
listlength([], 0).
listlength([Head | Tail], Length) :-
listlength(Tail, TailLength),
Length is TailLength + 1.
Sometimes the indentation rules can be bent: for example, it
is not unusual to put on a single line, a rule with a body that
contains just a single (short) clause.
bad(Dog) :- bites(Dog, _).
[1, 2, 3]
is a list. The empty list is written []. Frequently it is convenient
to refer to a list by giving the first item, and a list consisting of
the rest of the items. In this case, one writes the list as
[First | Rest].
We have expressed this here using variables, but this need not be so,
for example, we could write [1, 2, 3] as [1 | [2, 3]],
or write a list
that consisted of the fredfollowed by a
list boundto Othersas [fred | Others].
:-, used in a Prolog a :- b, c.
a (is true) if b and c (are
true).
write(X) which writes the term
X to the current output stream (which means the window on your workstation
unless you have done something
fancy).
print(X, ...) which writes a variable number of arguments to
the current output stream. If an argument is a string (like
"Hello world!\n") then the string is printed without quotes, and any
'\n' and '\t' are interpreted as newline and tab,
respectively.
A newline is printed at the end of the printing operation.
prin(X, ...) is like print except that it does not
append a newline to the end of the output.
nl starts a new line.
?). For example,: lectures(john, Subject), studies(Student, Subject)?
If the query fails, Prolog types "** no". If it succeeds,
Prolog either types the list of variable
bindings it had to assume in order to make
the query succeed, or, if no variable bindings were necessary, it
types "** yes".
If several variable bindings allow the query to succeed, then
normally (i.e. in the absence of cuts) all the
bindings will be typed out, one after the other. If the query can
succeed in several different ways without binding any variable that
were listed in the original query (because no variables
appeared in the query) then ** yes will be typed out several
times.
memberprocedure:The second clauseis clearly recursive -member(Item, [Item|Rest]).
member(Item, [_|Rest]) :- member(Item, Rest).
memberoccurs both in the head and the body. A recursive procedure can work
because of two things:
member) in the body
is in some way simpler than that in the head, so that Prolog is being
asked to solve a simpler problem. (In member, the list that
is the argument to member in the body is shorter by one than
that in the head.)
member, the first clause is the trivial branch - it says
that member succeeds if Item is the first member
of the list that is the second argument.)
tree(tree(empty, fred, empty), john, tree(empty, mary, empty))See also mutual recursion.
is_dog(fido).
is_dog(rex).
is_dog(rover).
eats(fido, biscuits).
eats(rex, chocolate).eats(rover, cheese).
eats(lassie, bone).is_dog and eats are
the
eats(Person, Thing) :- likes(Person, Thing), food(Thing).
Sometimes, however, the body can be omitted:
member(Item, [Item|Rest]).
This says that the Item is a member of any list (the second argument)
of which it is the first member.
Here, no special condition needs to be satisfied to make the head
true - it is always true.
date, and use it to
group the components together - for the date usually expressed as
29 Mar 2004, we would probably writedate(21, mar, 2004)date(2004, mar, 21)The choice of functor
is arbitrary, too.Structures may be nested, too - the following example groups a name and a date, perhaps the person's date of birth:
persondata(name(smith, john), date(28, feb, 1963))See also Bratko, section 2.1.3.
A query succeeds if each of its goals succeeds.
marand dateand the structuredate(2004, mar, 21)are terms. So are the numbers 2004and 21, for that matter.
_ (underscore)
is a "don't care" variable, which will match anything. For example, the
rule
bad(Dog) :- bites(Dog, _).says that something (
Dog) is bad if Dog bites anything.
The "anything" is represented by _. Unlike other variables in
Prolog, a bare _ can match different things in the same rule.
So, for example, if gives(From, To, Gift) is a three-place predicate
that is true if From gives Gift to To, then
giver(X) :- gives(X, _, _).signifies that someone (
X) is a "giver" if X gives
something to anybody - the two _ s don't have to match the same
thing. So if gives(fred, john, black_eye). is stored in the Prolog
database, then the rule above allows us to infer that fred is a
giver.
_) beginning either with a capital
letter or with an underscore. Examples:
X, Sister, _, _thing,
_y47, First_name, Z2_ is used as a "don't care" variable, when we
don't mind what value the variable has. For example:That is, X is a parent if they are a father or a mother, but we don't need to know who they are the father or mother of, to establish that they are a parent.is_a_parent(X) :- father_of(X, _).
is_a_parent(X) :- mother_of(X, _).
Variables are used in more than one way:
likes(A,B) :- dog(B), feeds(A,B).A and B appear on both sides of the
neck symbol - the appearance of the same variable
in two (or more places) in effect says that when the variable is
bound to a value, it must be bound to the same
value in all the places that it appears in a given rule._1,
_2, _3, etc. This is why variables with names like
these sometimes turn up in error messages when your Prolog program
goes wrong.
: studies(X, 9311) ?
Prolog responds by finding all the values for X for which
studies(X, 9311) is true, and successively listing them, e.g.X = fred X = jane X = abdul X = maria
Example. In reasonable size browser windows, the bad example will have long
lines that are folded by the browser, and the good example will not. In practice,
you could make the lines in the good example rather longer - up to 75-80
characters.
| Good | Bad |
|---|---|
% largest(ListOfNumbers, Max)
|
% largest(ListOfNumbers, Max) binds Max to the largest item in the
non-empty ListOfNumbers. ListOfNumbers should be instantiated at time
of call.
|