Basics of PROLOG
c©Hector Levesque
CPS721: Artificial Intelligence
Acknowledgement:
based on the slides prepared by Hector Levesque
September 14, 2021
CPS721: Artificial Intelligence (CS/RU) Basics of PROLOG September 14, 2021 1 / 15
Prolog in perspective
PROLOG = PROgramming in LOGic, i.e., declarative, non-imperative programming.
Radically different concept of programming from “conventional” computer languages:
Computation = Logical deduction.
Invented in 1971 by Frenchmen, Alain Colmerauer and Philippe Roussel, while visiting
at the University of Montreal. Based on the previous research in automated
theorem-proving of Robert Kowalski (IJCAI Award for Research Excellence, 2011).
Purpose: natural language processing.
Simultaneously invented by an American, Carl Hewitt, at MIT in Boston (under the
name “Planner” there).
Alain Colmerauer proposed and developed initial versions of Constraint Logic
Programming that seemlesly integrates logical reasoning with checks of application
constraints. Both purely symbolic and numerical constraints are allowed. There are
practical applications to industry.
Now PROLOG is a commercial product, with many available systems. We use
ECLiPSe: Constraint Logic Programming System owned by Cisco Technology.
Widely used for AI applications that require symbol processing, as well as many other
uses (databases, compilers).
CPS721: Artificial Intelligence (CS/RU) Basics of PROLOG September 14, 2021 2 / 15
Atomic sentences
Prolog programs start with basic facts:
Marc is a junior
Michelle is a senior
Marc likes ice cream
In Prolog, these would be written as follows
junior(marc).
senior(michelle).
likes(marc,ice_cream).
These are called atomic sentences (or just atoms). The words junior, senior, and
likes are examples of Prolog predicates; marc, michelle, and ice_cream are
examples of Prolog constants.
• The names of predicates and constants are up to you, the programmer.
• They must not begin with an upper case letter or an underscore.
• Atomic sentences always have the form
predicateName(argument1, . . . ,argumentn).
Conditional sentences: next class.
CPS721: Artificial Intelligence (CS/RU) Basics of PROLOG September 14, 2021 3 / 15
Simple Prolog programs
The simplest possible Prolog program is a collection of atomic sentences, each ending
with a period. (Conditional sentences are to be discussed next class.)
Usually (but not necessarily), these are placed one per line to visualize that
back-chaining can process them one after another.
So this is a simple program (without conditional rules):
junior(marc).
junior(mary).
senior(michelle).
senior(steve).
senior(bob).
likes(marc,michelle).
likes(bob,ray).
likes(bob,michelle).
enrolledInCourse(susan,cps721,2021, artificial_intelligence1).
Today we focus on queries submitted to a command-line eclipse6 program that
you can run within a terminal window. This can easily be adapted to tkeclipse
implementation with a GUI.
CPS721: Artificial Intelligence (CS/RU) Basics of PROLOG September 14, 2021 4 / 15
Querying a program
Prolog programs execute in response to a query. I use “?-” prompt for clarity.
Examples of atomic queries and the answers Prolog returns:
?- junior(marc) .
yes
?- junior(michelle) .
no
?- likes(bob,ray) .
yes
?- likes(ray,bob) .
no
Note: like atomic sentences, queries must end with a period.
One can ask conjunctive queries:
• Is Marc a junior who likes Michelle? /* how to reformulate this ? */
Is Marc a junior and does Marc like Michelle?
?- junior(marc) , likes(marc,michelle).
Note: comma is used for “and”
yes
• Is Marc a junior who likes Bob? /* how to reformulate this ? */
?- junior(marc), likes(marc,bob).
no
CPS721: Artificial Intelligence (CS/RU) Basics of PROLOG September 14, 2021 5 / 15
How Prolog answers queries
Atomic Queries: ?- likes(ray,bob).
Prolog checks its database of atoms to see whether likes(ray,bob) is present.
If it matches, then it answers yes, else no.
Conjunctive Queries:
?- junior(marc), senior(michelle), likes(marc,michelle).
/* answer ? */
Back-chaining considers each atom of the query in a left-to-right order.
If every atom of the query would get the answer yes, the entire query gets the
answer yes.
So the above query has answer yes.
If any atom in the query would get the answer no, the entire query gets the answer
no. Prolog does not consider any more atoms of the query after finding
the first one with answer no.
?- junior(marc), senior(michelle), likes(michelle,marc), junior(huey).
no
Note: junior(huey) will not be considered.
CPS721: Artificial Intelligence (CS/RU) Basics of PROLOG September 14, 2021 6 / 15
Negation in Prolog queries
The constant not can be used before an atomic sentence in a query to flip between
yes and no:
?- likes(marc,michelle), not junior(michelle).
/* answer? */
As always with conjunctive queries, Prolog considers the query from left to right.
The first atom likes(marc,michelle) succeeds (gets the answer yes).
In considering not junior(michelle), back-chaining procedure first
considers the query junior(michelle).
junior(michelle) fails (gets the answer no),
so the query not junior(michelle) succeeds
So the whole query gets the answer yes.
Similarly, the query
?- likes(marc,michelle), not senior(michelle).
gets the answer no
CPS721: Artificial Intelligence (CS/RU) Basics of PROLOG September 14, 2021 7 / 15
Variables in Prolog queries
Recall, in addition to queries that try to establish whether a sentence is entailed by a
KB, we can formulate queries that retrieve constants from KB. /* how ? */
Is there anyone who is a junior?
?- junior(X).
X = marc
The Prolog answer means the query succeeds when the value of variable X is marc.
Notice that junior(marc) is the first instance of
the junior predicate in the database.
If you type ; after this answer or click more button in the GUi of tkeclipse, this asks
Prolog to give another example of X if there is one.
?- junior(X).
X = marc ;
X = mary ;
no /* i.e., Prolog has run out of answers */
X is a Prolog variable.
Variable start with an upper case letter or an underscore, unlike constants.
As queries, senior(Y), senior(Steve), and senior(_marc) would be
equivalent. Use neutral or mnemonic words strating with a capital letter.
CPS721: Artificial Intelligence (CS/RU) Basics of PROLOG September 14, 2021 8 / 15
Example queries with variables
?- junior(Marc), likes(Marc,michelle).
Marc = marc ;
no /* Marc is the only junior who likes Michelle */
?- junior(X), likes(X,ray).
no /* fails for both Marc and Michelle */
?- likes(bob,Person).
Person = ray ;
Person = michelle ;
no /* a person who Bob likes: two distinct answers */
?- senior(X), likes(X,Y).
X = bob
Y = ray ;
X = bob
Y = michelle ;
no /*a senior (X ) and someone he or she likes (Y ): 2 answers but with the same X */
?- likes(bob,Who), not senior(Who).
Who = ray ;
no
CPS721: Artificial Intelligence (CS/RU) Basics of PROLOG September 14, 2021 9 / 15
Another example
?- likes(X,Y), not junior(X), not junior(Y). /* answers X , Y -? */
X = bob
Y = ray ;
X = bob
Y = michelle ;
no /*Means that there are no other answers */
?- likes(X,Y), not junior(X), not junior(Y). /* answers X , Y -? */
X = bob Y = ray .
yes
/* “dot” above means: do not bother generating any other answers */
CPS721: Artificial Intelligence (CS/RU) Basics of PROLOG September 14, 2021 10 / 15
Backtracking
Let’s trace how back-chaining (with back-tracking) will evaluate the query
?- likes(bob,Y), senior(Y).
CPS721: Artificial Intelligence (CS/RU) Basics of PROLOG September 14, 2021 11 / 15
A backtracking example
?- likes(X,Y), senior(X), senior(Y).
CPS721: Artificial Intelligence (CS/RU) Basics of PROLOG September 14, 2021 12 / 15
Caution: variables and negation
Recall that in logic “A and B” means same as “B and A”. what about back-chaining?
?- likes(bob,Y), not senior(Y).
Y = ray ;
no /* means there is only 1 answer “ray” */
What answer will we see if we change the order in the query above ?
?- not senior(Y), likes(bob,Y).
no
?- not senior(ray), likes(bob,ray).
yes
What is happening here?
• in the first query, we get Y = ray from the first predicate; then we try
senior(ray), which fails, and so not senior(ray) succeeds.
• in the second query, we try senior(Y) which succeeds, and so
not senior(Y) fails.
The problem: using variables within a negated query.
The solution: make sure when variables appear inside a negated query, they have
already been given a value by preceding predicates, i.e., instantiate vars before not.
CPS721: Artificial Intelligence (CS/RU) Basics of PROLOG September 14, 2021 13 / 15
The equality predicate
Does Bob like anyone other than Ray?
?- likes(bob,X), not X = ray.
X = michelle ;
no
Does Marc like anyone other than Michelle?
?- likes(marc,X), not X = michelle.
no
Who likes at least two different people?
?- likes(X,Y), likes(X,Z), not Y=Z. /* Answers ? Trace it !*/
X = bob
Y = ray
Z = michelle ;
X = bob
Y = michelle
Z = ray ; no
/* Note: the two answers are generated by backtracking. Prolog does not try to
determine if they really are the “same” answer. Lesson to learn: repeated answers in
your homework are OK*/
CPS721: Artificial Intelligence (CS/RU) Basics of PROLOG September 14, 2021 14 / 15
Equality continued
In a query, you should never have to use an unnegated equality predicate. Example:
Does Bob like any junior?
?- likes(bob,X), junior(Y), X = Y.
This has the same effect as:
?- likes(bob,X), junior(X).
Now consider:
?- X = bob.
X = bob ;
no
?- X = Y, Y = bob.
X = bob
Y = bob ;
no
Here, the internal variable from the first equality is made the same as Bob in the
second equality.
Warning: equality has unusual meaning.
In Prolog, equality means unification, i.e., Prolog evaluates an equality by trying to
make both sides the same in as general a way as possible.
CPS721: Artificial Intelligence (CS/RU) Basics of PROLOG September 14, 2021 15 / 15