The Prolog Dictionary

Copyright Bill Wilson, 1998-2004 Contact Info
Last updated: Fri, 16 Apr 2004 01:21:57 GMT

A B C D E F G H I J K L M N O P Q R S T U V W X Y Z

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

A

arity
The arity of a functor is the number of arguments it takes. For example, the arity of likes, as in likes(jane, pizza), is 2, as it takes two arguments, jane and pizza.
ArityExampleCould Mean ...
1happy(fido).Fido is happy.
2likes(jane, pizza). 
3gave(mary, john, book).Mary gave John a book.

atom
An atom, in Prolog, means a single data item. It may be of one of three types:

Numbers, in Prolog, are not considered to be atoms.

B

backtracking
Backtracking is basically a form of searching. In the context of Prolog, suppose that the Prolog interpreter is trying to satisfy a sequence of
goalsgoal_1, goal_2. When the Prolog interpreter finds a set of variablebindingswhich allow goal_1to be satisfied, it commits itself to those bindings, and then seeks to satisfy goal_2. Eventually one of two things happens: (a) goal_2is satisfied and finished with; or (b) goal_2cannot be satisfied. In either case, Prolog backtracks. That is, it "un-commits" itself to the variable bindings it made in satisfying goal_1and goes looking for a differentset of variable bindings that allow goal_1to be satisfied. If it finds a second set of such bindings, it commits to them, and proceeds to try to satisfy goal_2again, with the new bindings. In case (a), the Prolog interpreter is looking for extrasolutions, while in case (b) it is still looking for the first solution. So backtracking may serve to find extra solutions to a problem, or to continue the search for a first solution, when a first set of assumptions (i.e. variable bindings) turns out not to lead to a solution.

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 = c
Here memberbacktracks to find every possible solution to the query given to it. Consider also:
: member(X, [a, a, a]) ?
X = a
X = a
X = a
Here memberbacktracks even though it keeps on finding the same answer. What about
: member(a, [a, a, a]) ?
In theory, Prolog should respond:
** yes
** yes
** yes
However, 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.

binding
Binding is a word used to describe giving a value to a
variable. It normally occurs during application of a Prolog rule, or an attempt to satisfy the goals in a Prolog query.

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.

body
the last part of a Prolog
rule. It is separated from the head by the neck symbol :-. 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.

built-in procedure or predicate
To make Prolog programming more practical, a number of
predicates or procedures are built in to Prolog. These include some utility procedures, which could have been programmed by the Prolog user, and some which do non-logic programming things, like the input and output routines, debugging routines, and a range of others. A full list of iProlog built-ins is available in the iProlog Reference Manual.

C

clause
A clause in Prolog is a unit of information in a Prolog program ending with a full stop ("."). A clause may be a fact, like:
likes(mary, pizza).
or a rule, like:
eats(Person, Thing) :- likes(Person, Thing), food(Thing).

A group of clauses about the same
relationis termed a procedure.

comment
in Prolog, a the start of a comment is signalled by the character %. 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
functor name or variable name, this is preferable to a comment.

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.

cut, !
The cut, in Prolog, is a
goal, written as !, which always succeeds, but cannot be backtrackedpast. It is used to prevent unwanted backtracking, for example, to prevent extra solutions being found by Prolog.
The cut should be used sparingly. There is a temptation to insert cuts experimentally into code that is not working correctly. If you do this, bear in mind that when debugging is complete, you should understand the effect of, and be able to explain the need for, every cut you use. The use of a cut should thus be commented.

D

debugging
means removing errors from program code.

declarative
A declarative programming language is one in which the relationships between the data are stated (or declared in a (usually logic-based) language, and then some automatic mechanism, e.g. a theorem-prover, is used to answer
queriesabout the data. Prolog is a declarative programming language. Gofer, Miranda, and Lisp are functionalprogramming languages, in which all constructs are expressed using functions, function arguments, and function results, and C, Pascal, Modula-2, and Fortran are examples of (high-level) proceduralprogramming languages, in which the program code expresses procedures to follow in manipulating the data.

E

F

functor
In Prolog, the word functor is used to refer to the atom at the start of a
structure. For example, in likes(mary, pizza), likesis the functor. In a more complex structure, like

persondata(name(smith, john), date(28, feb, 1963))

the top-level functor is termed the principal functor- in this case 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.

G

goal
A query to the Prolog interpreter consists of one or more goals. For example, in

: lectures(john, Subject), studies(Student, Subject)?

there are two goals, lectures(john, Subject) and studies(Student, Subject). A goal is something that Prolog tries to satisfy by finding values of the
variables(in this case Studentand Subject) that make the goal succeed.

H

head
the first part of a Prolog
rule. It is separated from the bodyby the necksymbol :-. 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 rule

sister_of(X,Y) :- female(Y), same_parents(X,Y).

sister_of(X,Y)is the head.

I

indentation
Indenting your Prolog code in a standard way is a technique, along with
commentingit, to make your code more easily understood (by humans). The standard way to lay out a Prolog procedure is exemplified below, using a procedure to compute the length of a list. Comments have been omitted, to allow you to focus just on the indentation.
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, _).
J

K

L

lists
A list in Prolog is written as a comma-separated, well, list, of items, between square brackets. For example, [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
atomfredfollowed by a list boundto Othersas [fred | Others].

M

mutual recursion
Sometimes a
predicatedoes not explicitly refer to itself (this would be (simple) recursion), but rather refers to a second predicate which in turn refers to the first. This sets up a two-step mutual recursion. Three- or more- step mutual recursion situations can also occur. The usual conditions applicable to recursion must occur - there must be a "trivial branch" somewhere in the cycle of mutually recursive predicates, and somewhere in the cycle something must happen to ensure that each time around the cycle, a simpler version of the problem is being solved.

N

neck
the symbol :-, used in a Prolog
ruleto separate the headfrom the body. Usually read as if. Thus

a :- b, c.

is read as

a (is true) if b and c (are true).

number
Numbers in Prolog can be whole numbers, like:
1  1313  0  -97  9311

or fractional numbers, like:
3.14  -0.0035  100.2
The range of numbers that can be used is likely to be dependent on the number of bits (amount of computer memory) used to represent the number. The treatment of real numbers in Prolog is likely to vary from implementation to implementation - real numbers are not all that heavily used in Prolog programs, as the emphasis in Prolog is on symbol manipulation.

O

output in Prolog
Output in Prolog is not always needed, as often the
variablebindingsreturn all the information that is required. If explicit output is required, a set of extra-logical built-in predicates is available.
These include: For more details, check the relevant sectionof the iProlog manual.

P

predicate
In this context, used interchangeably with the term
procedure.

procedure
A procedure in Prolog is a group of clauses about the same relation, for example:

is_a_parent(X) :- father_of(X, _).
is_a_parent(X) :- mother_of(X, _).

Here, two clauses together define the condition for someone to be a parent - together they form a procedure.

Q

query
A query is a list of one or more
goalstyped to the Prolog interpreter, separated by commas, and terminated with a question mark (?). For example,
: lectures(john, Subject), studies(Student, Subject)?
is a query comprising two goals. Prolog tries to satisfy the goals, and if it manages to do this, the query is said to succeed. If not, the query fails.

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.

R

recursion
A recursive
ruleis one which refers to itself. That is, its bodyincludes a goalwhich is an instance of the relation that appears in the headof the rule. A well-known example is the memberprocedure:
member(Item, [Item|Rest]).
member(Item, [_|Rest]) :- member(Item, Rest).
The second clauseis clearly recursive - memberoccurs both in the head and the body. A recursive procedure can work because of two things:
  1. the instance of the relation (like 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.)
  2. there must be a "trivial branch" "base case" or "boundary case" to the recursion - that is, a clause that does not involve recursion. (In the case of 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.)
A recursive data structure is one where the structures include substructures whose principle functoris the same as that of the whole structure. For example, the tree structure:
tree(tree(empty, fred, empty), john, tree(empty, mary, empty))
is recursive. Usually, recursive data structures require recursive procedures.

See also mutual recursion.

relation
The word relation, in Prolog, has its usual mathematical meaning. A unary relation is a set of objects all sharing some property. Example:
is_dog(fido). is_dog(rex). is_dog(rover).
A binary relation is a set of pairs all of which are related in the same way. Example:
eats(fido, biscuits). eats(rex, chocolate).
eats(rover, cheese). eats(lassie, bone).
Similarly for ternary relations (triples) and so on. In the examples above, is_dog and eats are the
functors for the relations. Prolog stores information in the form of relations, or more specifically relational instances.

rule
A rule in Prolog is a
clause with one or more variables in it. Frequently, rules have a head, neck and body, as in:
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.

S

structures
Structures in Prolog are simply objects that have several components, but are treated as a single object. Suppose that we wish to represent a date in Prolog - dates are usually expressed using a day, a month, and a year, but viewed as a single object. To combine the components into a single structure, we choose a
functor, say date, and use it to group the components together - for the date usually expressed as 29 Mar 2004, we would probably write
date(21, mar, 2004)
Note that the order of the components is our choice - we might have instead written 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.

succeed
A Prolog
goal succeeds if it is possible to either check it directly against the facts known to Prolog, or find bindings for variables in the goal that makes the goal true.

A query succeeds if each of its goals succeeds.

T

term
Syntactically, all data objects in Prolog are terms. For example, the
atommarand dateand the structuredate(2004, mar, 21)are terms. So are the numbers 2004and 21, for that matter.

testing
Here are some
tips on testing your Prolog code.

U

underscore
The Prolog variable _ (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.
V

variable
A variable in Prolog is a string of letters, digits, and underscores (_) beginning either with a capital letter or with an underscore. Examples:
X, Sister, _, _thing, _y47, First_name, Z2
The variable _ is used as a "don't care" variable, when we don't mind what value the variable has. For example:
is_a_parent(X) :- father_of(X, _).
is_a_parent(X) :- mother_of(X, _).

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.

Variables are used in more than one way:

W

white space

In writing code in Prolog or any other programming language, white space (blank lines, indentation, perhaps alignment of related data items) can be used to make the code easier to follow. Here are some suggestions:

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.
GoodBad
% largest(ListOfNumbers, Max)
%  binds Max to the largest item
%  in the non-empty ListOfNumbers.
%  ListOfNumbers should be instantiated
%  at time of call.
largest([FirstNum], FirstNum).
largest([FirstNum | Rest], Max) :-
      largest(Rest, MaxRest),
      larger(FirstNum, MaxRest, Max).
 
% larger(First, Second, Bigger)
%  helper procedure for largest.
larger(A, B, A) :- A >= B.
larger(A, B, B) :- B > A.
% largest(ListOfNumbers, Max) binds Max to the largest item in the non-empty ListOfNumbers. ListOfNumbers should be instantiated at time of call.
larger(A, B, A) :- A >= B.
larger(A, B, B) :- B > A.
% This is a helper procedure for largest.
largest([FirstNum], FirstNum).
largest([FirstNum | Rest], Max) :- largest(Rest, MaxRest), larger(FirstNum, MaxRest, Max).

X

Y

Z