COMP 348 Principles of Programming Languages
COMP 348
PRINCIPLES OF
PROGRAMMING
LANGUAGES
LECTURE 10 – LOGICAL PROGRAMMING WITH PROLOG
Fall 2021Dept. of Computer Science and Software Engineering, Concordia University
Logical Programming with PROLOG
Clauses and Queries, Lists
2
• The following materials are the original lecture note from
the Course Pack “COMP 348 Principles of Programming
Languages” written and developed by:
Dr. Constantinos Constantinides, P.Eng.
Department of Computer Science and Software Engineering
Concordia University, Montreal, Quebec, Canada
.ca
https://users.encs.concordia.ca/~cc/
3
Acknowledgement and Copyright Notice
mailto: .ca
https://users.encs.concordia.ca/~cc/
• SWI-PROLOG
– https://www.swi-prolog.org/
– QuickStart: https://www.swi-
prolog.org/pldoc/man?section=quickstart
– Online Version: https://swish.swi-prolog.org/
– Some Tutorials:
• http://lpn.swi-prolog.org/lpnpage.php?pageid=online
• https://www.doc.gold.ac.uk/~mas02gw/prolog_tutorial/prologpages/
• http://www.cs.nuim.ie/~jpower/Courses/Previous/PROLOG/
• https://www.cis.upenn.edu/~matuszek/Concise%20Guides/Concise
%20Prolog.html
4
Software
https://www.swi-prolog.org/
https://www.swi-prolog.org/pldoc/man?section=quickstart
https://swish.swi-prolog.org/
http://lpn.swi-prolog.org/lpnpage.php?pageid=online
https://www.doc.gold.ac.uk/~mas02gw/prolog_tutorial/prologpages/
http://www.cs.nuim.ie/~jpower/Courses/Previous/PROLOG/
https://www.cis.upenn.edu/~matuszek/Concise%20Guides/Concise%20Prolog.html
• Prolog’s single data type is term.
• A term can be
– atom (begins with lower case),
– a number,
– a variable (upper case),
– or a compound term (composed if an atom called a functor and a
number of arguments which are indeed terms).
• Examples:
– raining
– 2
– X
– parent(peter, daphne)
5
Data Type
• A Prolog program consists of assertions (clauses).
• Clauses are divided into:
– facts
– and rules.
• Example:
– raining
– parent(peter, daphne) :- true.
It can be simplified to:
– parent(peter, daphne).
6
Facts and Clauses
“Peter is the parent of Daphne.”
“It’s raining”
• The number of arguments is called arity and is represented
by “/”:
– Clause: parent(peter, daphne).
– Arity: parent/2
• Note: Same name different arities are treated as different.
7
Arity
Clauses
• Predicate logic can be used to represent and reason about knowledge.
• We will adopt the Prolog programming language to model and process
clauses.
• In this discussion we will use a running example to express the meaning and
constraints of data as well as to construct queries over their representation in
order to obtain information.
8
9
A running example: A family genealogy tree
Prolog programs consist of collections of
statements (called assertions, or clauses).
parent(tom, adam).
parent(tom, helen).
parent(sandra, adam).
parent(sandra, helen).
parent(michael, andrew).
parent(michael, john).
parent(eve, andrew).
parent(eve, john).
parent(helen, mark).
parent(andrew, mark).
parent(judy, roger).
parent(judy, jim).
parent(judy, janis).
parent(mark, roger).
parent(mark, jim).
parent(mark, janis).
parent(janis, daphne).
parent(peter, daphne).
Programs and statements
10
Prolog programs consist of collections of
statements (called assertions, or clauses).
Statements are grouped into procedures.
In the example, we have one procedure named
parent, made up of several statements.
parent(tom, adam).
parent(tom, helen).
parent(sandra, adam).
parent(sandra, helen).
parent(michael, andrew).
parent(michael, john).
parent(eve, andrew).
parent(eve, john).
parent(helen, mark).
parent(andrew, mark).
parent(judy, roger).
parent(judy, jim).
parent(judy, janis).
parent(mark, roger).
parent(mark, jim).
parent(mark, janis).
parent(janis, daphne).
parent(peter, daphne).
Statements and procedures
11
Prolog programs consist of collections of
statements (called assertions, or clauses).
Statements are grouped into procedures.
In the example, we have one procedure named
parent, made up of several statements.
Each procedure defines a certain
relationship between its arguments.
The programmer decides on how to interpret
this relationship. Here, parent(tom, adam) will
be interpreted as “Tom is the parent of Adam.”
parent(tom, adam).
parent(tom, helen).
parent(sandra, adam).
parent(sandra, helen).
parent(michael, andrew).
parent(michael, john).
parent(eve, andrew).
parent(eve, john).
parent(helen, mark).
parent(andrew, mark).
parent(judy, roger).
parent(judy, jim).
parent(judy, janis).
parent(mark, roger).
parent(mark, jim).
parent(mark, janis).
parent(janis, daphne).
parent(peter, daphne).
Procedures and arguments
12
Prolog programs consist of collections of
statements (called assertions, or clauses).
Statements are grouped into procedures.
In the example, we have one procedure named
parent, made up of several statements.
Each procedure defines a certain
relationship between its arguments.
The programmer decides on how to interpret
this relationship. Here, parent(tom, adam) will
be interpreted as “Tom is the parent of Adam.”
There are two kinds of clauses: facts and rules.
Facts are propositions declared to be True.
In the example, the procedure named parent
consists only by facts.
parent(tom, adam).
parent(tom, helen).
parent(sandra, adam).
parent(sandra, helen).
parent(michael, andrew).
parent(michael, john).
parent(eve, andrew).
parent(eve, john).
parent(helen, mark).
parent(andrew, mark).
parent(judy, roger).
parent(judy, jim).
parent(judy, janis).
parent(mark, roger).
parent(mark, jim).
parent(mark, janis).
parent(janis, daphne).
parent(peter, daphne).
Statements revisited: Facts and rules
13
The collection of statements constitutes a
(declarative) database.
We can pose queries on this database.
A query is the codification of a question.
There are only two types of queries:
1.Is it indeed the case that a given statement
is true? (ground query)
2.Under what conditions, if any, is a given
statement true? (non-ground query)
parent(tom, adam).
parent(tom, helen).
parent(sandra, adam).
parent(sandra, helen).
parent(michael, andrew).
parent(michael, john).
parent(eve, andrew).
parent(eve, john).
parent(helen, mark).
parent(andrew, mark).
parent(judy, roger).
parent(judy, jim).
parent(judy, janis).
parent(mark, roger).
parent(mark, jim).
parent(mark, janis).
parent(janis, daphne).
parent(peter, daphne).
Questions and queries
14
Ground queries result in a Yes/No (or
True/False) response:
For example, the question
“Is it indeed the case that Peter is the parent
of Daphne?”
will be codified into a query and executed
as
?- parent(peter, daphne).
parent(tom, adam).
parent(tom, helen).
parent(sandra, adam).
parent(sandra, helen).
parent(michael, andrew).
parent(michael, john).
parent(eve, andrew).
parent(eve, john).
parent(helen, mark).
parent(andrew, mark).
parent(judy, roger).
parent(judy, jim).
parent(judy, janis).
parent(mark, roger).
parent(mark, jim).
parent(mark, janis).
parent(janis, daphne).
parent(peter, daphne).
Ground queries
15
Prolog will take the query
?- parent(peter, daphne).
and will start searching the database from top
to bottom, one statement at a time trying to
match (“unify”) it with a statement.
In trying the first statement, a match
(unification) is not successful.
parent(tom, adam).
parent(tom, helen).
parent(sandra, adam).
parent(sandra, helen).
parent(michael, andrew).
parent(michael, john).
parent(eve, andrew).
parent(eve, john).
parent(helen, mark).
parent(andrew, mark).
parent(judy, roger).
parent(judy, jim).
parent(judy, janis).
parent(mark, roger).
parent(mark, jim).
parent(mark, janis).
parent(janis, daphne).
parent(peter, daphne).
Evaluation of ground queries
16
Prolog will then try to match the query
?- parent(peter, daphne).
against the next statement in the program.
Again, if not successful, it will try the next
statement in the program…etc. until either a
match is found or until the database is
exhausted.
parent(tom, adam).
parent(tom, helen).
parent(sandra, adam).
parent(sandra, helen).
parent(michael, andrew).
parent(michael, john).
parent(eve, andrew).
parent(eve, john).
parent(helen, mark).
parent(andrew, mark).
parent(judy, roger).
parent(judy, jim).
parent(judy, janis).
parent(mark, roger).
parent(mark, jim).
parent(mark, janis).
parent(janis, daphne).
parent(peter, daphne).
Evaluation of ground queries /cont.
17
In this example, Prolog will eventually succeed,
having matched the query
?- parent(peter, daphne).
with the last statement.
Prolog will respond Yes (or true) to the query.
We have managed to prove that it is
indeed the case that parent(peter, daphne) is
true.
parent(tom, adam).
parent(tom, helen).
parent(sandra, adam).
parent(sandra, helen).
parent(michael, andrew).
parent(michael, john).
parent(eve, andrew).
parent(eve, john).
parent(helen, mark).
parent(andrew, mark).
parent(judy, roger).
parent(judy, jim).
parent(judy, janis).
parent(mark, roger).
parent(mark, jim).
parent(mark, janis).
parent(janis, daphne).
parent(peter, daphne).
Evaluation of ground queries /cont.
18
A non-ground query involves one or more
variables.
The question “Who is a parent of Daphne” can
be transformed into a non-ground query as
?- parent(X, daphne).
where X (note the capitalization) is a variable.
We are asking Prolog to seek instantiation(s)
for variable X, provided any exist, that could
make the query succeed.
parent(tom, adam).
parent(tom, helen).
parent(sandra, adam).
parent(sandra, helen).
parent(michael, andrew).
parent(michael, john).
parent(eve, andrew).
parent(eve, john).
parent(helen, mark).
parent(andrew, mark).
parent(judy, roger).
parent(judy, jim).
parent(judy, janis).
parent(mark, roger).
parent(mark, jim).
parent(mark, janis).
parent(janis, daphne).
parent(peter, daphne).
Non-ground queries
19
Unification revisited
Unification (or matching) is a basic operation
on terms.
A ground query can unify with a statement,e.g.
?- parent(tom, adam).
A non-ground query can unify with a statement
only if substitution can be made for any
variables so that the two terms can be made
equal. In this example, we have
?- parent(X, daphne).
parent(tom, adam).
parent(tom, helen).
parent(sandra, adam).
parent(sandra, helen).
parent(michael, andrew).
parent(michael, john).
parent(eve, andrew).
parent(eve, john).
parent(helen, mark).
parent(andrew, mark).
parent(judy, roger).
parent(judy, jim).
parent(judy, janis).
parent(mark, roger).
parent(mark, jim).
parent(mark, janis).
parent(janis, daphne).
parent(peter, daphne).
parent
janis daphne
parent
X daphne
Tree representation of
a statement.
Tree representation of a
non-ground query. 20
parent
janis daphne
parent
X daphne
• The terms parent(janis, daphne) and parent(X, daphne) unify
instantiating X to janis.
• There is in fact one more solution, because there are two
possible choices to unify with parent(X, daphne).
Unification revisited /cont.
21
A rule statement gives rules of implication
between propositions. The general form is
head :- body.
(or conclusion :- condition.)
which reads
“The head (of the rule) is true, if the body is
true.”,
or, alternatively:
“The head of the rule can succeed if
the body of the rule can succeed.”
parent(tom, adam).
parent(tom, helen).
parent(sandra, adam).
parent(sandra, helen).
parent(michael, andrew).
parent(michael, john).
parent(eve, andrew).
parent(eve, john).
parent(helen, mark).
parent(andrew, mark).
parent(judy, roger).
parent(judy, jim).
parent(judy, janis).
parent(mark, roger).
parent(mark, jim).
parent(mark, janis).
parent(janis, daphne).
parent(peter, daphne).
Rules: Head and body
22
• Let us extend the database with a new procedure
grandparent.
• Let p stand for isParentOf relation and let g stand for
isGrandParentOf relation.
• We can define g in terms of p by the following formula: For
persons x, y, z:
• We can represent the formula with the rule below:
grandparent(X, Z) :- parent(X, Y), parent(Y, Z).
23
Formulae and rules
grandparent(X, Z) :- parent(X, Y), parent(Y, Z).
parent(tom, adam).
parent(tom, helen).
parent(sandra, adam).
parent(sandra, helen).
parent(michael, andrew).
parent(michael, john).
parent(eve, andrew).
parent(eve, john).
parent(helen, mark).
parent(andrew, mark).
parent(judy, roger).
parent(judy, jim).
parent(judy, janis).
parent(mark, roger).
parent(mark, jim).
parent(mark, janis).
parent(janis, daphne).
parent(peter, daphne).
head body
goal goal
The body of rule grandparent contains
two goals.
The goals are related by a conjunction
(denoted by the comma symbol).
Consider the following rule statement:
Rules and goals
24
parent(tom, adam).
parent(tom, helen).
parent(sandra, adam).
parent(sandra, helen).
parent(michael, andrew).
parent(michael, john).
parent(eve, andrew).
parent(eve, john).
parent(helen, mark).
parent(andrew, mark).
parent(judy, roger).
parent(judy, jim).
parent(judy, janis).
parent(mark, roger).
parent(mark, jim).
parent(mark, janis).
parent(janis, daphne).
parent(peter, daphne).
grandparent(X, Z) :- parent(X, Y),
parent(Y, Z).
The rule is added to the database.
Extending the database
25
Consider the query grandparent(judy, daphne).
Prolog will search its database from top to
bottom and
a) unify the query with the head of the rule,
b) instantiate X to judy and Z to daphne,
grandparent(X, Z) :- parent(X, Y), parent(Y, Z).
?- grandparent(judy, daphne).
Evaluation of a ground query in the presence of rules
An example
26
parent(tom, adam).
parent(tom, helen).
parent(sandra, adam).
parent(sandra, helen).
parent(michael, andrew).
parent(michael, john).
parent(eve, andrew).
parent(eve, john).
parent(helen, mark).
parent(andrew, mark).
parent(judy, roger).
parent(judy, jim).
parent(judy, janis).
parent(mark, roger).
parent(mark, jim).
parent(mark, janis).
parent(janis, daphne).
parent(peter, daphne).
grandparent(X, Z) :- parent(X, Y),
parent(Y, Z).
c) resolve to two new queries (that
correspond to the two goals of the rule):
parent(judy, Y), parent(Y, daphne).
Both queries must now be evaluated (in the
order specified) and if both prove true, then
the rule succeeds (and the answer to the
query is Yes/True).
parent(tom, adam).
parent(tom, helen).
parent(sandra, adam).
parent(sandra, helen).
parent(michael, andrew).
parent(michael, john).
parent(eve, andrew).
parent(eve, john).
parent(helen, mark).
parent(andrew, mark).
parent(judy, roger).
parent(judy, jim).
parent(judy, janis).
parent(mark, roger).
parent(mark, jim).
parent(mark, janis).
parent(janis, daphne).
parent(peter, daphne).
grandparent(X, Z) :- parent(X, Y),
parent(Y, Z).
Evaluation of a ground query in the presence of rules
An example /cont.
27
parent(tom, adam).
parent(tom, helen).
parent(sandra, adam).
parent(sandra, helen).
parent(michael, andrew).
parent(michael, john).
parent(eve, andrew).
parent(eve, john).
parent(helen, mark).
parent(andrew, mark).
parent(judy, roger).
parent(judy, jim).
parent(judy, janis).
parent(mark, roger).
parent(mark, jim).
parent(mark, janis).
parent(janis, daphne).
parent(peter, daphne).
grandparent(X, Z) :- parent(X, Y),
parent(Y, Z).
The two goals
parent(judy, Y), parent(Y, daphne).
will be evaluated as follows:
The first goal parent(judy, Y), will be
executed as any other query, unifying with
parent(judy ,roger), and instantiating Y to
roger.
Once the first goal succeeds, Prolog will try
the next one on the right, for the same
instantiation:
Can roger make the second goal succeed?
No. The query parent(roger, daphne) is not
successful.
Evaluation of a ground query in the presence of rules
An example /cont.
28
Prolog will continue searching the database
to find matches that can satisfy both goals
parent(judy, Y), parent(Y, daphne).
The first goal, parent(judy, Y), can unify with
parent(judy, jim), instantiating Y to jim.
Can jim make the second goal succeed?
No. The query parent(jim, daphne) is not
successful.
parent(tom, adam).
parent(tom, helen).
parent(sandra, adam).
parent(sandra, helen).
parent(michael, andrew).
parent(michael, john).
parent(eve, andrew).
parent(eve, john).
parent(helen, mark).
parent(andrew, mark).
parent(judy, roger).
parent(judy, jim).
parent(judy, janis).
parent(mark, roger).
parent(mark, jim).
parent(mark, janis).
parent(janis, daphne).
parent(peter, daphne).
grandparent(X, Z) :- parent(X, Y),
parent(Y, Z).
Evaluation of a ground query in the presence of rules
An example /cont.
29
Prolog will continue searching the database
to find matches that can satisfy both goals
parent(judy, Y), parent(Y, daphne).
The first goal, parent(judy, Y), can unify with
parent(judy,janis), instantiating Y to janis.
Can janis make the second goal succeed?
Yes. The query parent(janis, daphne) is
successful.
Evaluation of a ground query in the presence of rules
An example /cont.
parent(tom, adam).
parent(tom, helen).
parent(sandra, adam).
parent(sandra, helen).
parent(michael, andrew).
parent(michael, john).
parent(eve, andrew).
parent(eve, john).
parent(helen, mark).
parent(andrew, mark).
parent(judy, roger).
parent(judy, jim).
parent(judy, janis).
parent(mark, roger).
parent(mark, jim).
parent(mark, janis).
parent(janis, daphne).
parent(peter, daphne).
grandparent(X, Z) :- parent(X, Y),
parent(Y, Z).
30
parent(tom, adam).
parent(tom, helen).
parent(sandra, adam).
parent(sandra, helen).
parent(michael, andrew).
parent(michael, john).
parent(eve, andrew).
parent(eve, john).
parent(helen, mark).
parent(andrew, mark).
parent(judy, roger).
parent(judy, jim).
parent(judy, janis).
parent(mark, roger).
parent(mark, jim).
parent(mark, janis).
parent(janis, daphne).
parent(peter, daphne).
grandparent(X, Z) :- parent(X, Y),
parent(Y, Z).
Evaluation of a non-ground query
in the presence of rules: An example
The question
“Who are the grandparents of Daphne?”
is codified into the query
?- grandparent(G, daphne).
This will unify with the head of rule
grandparent, instantiating variable Z to
daphne and resolving into two goals:
parent (G, Y), parent(Y, daphne).
31
?- grandparent(X, daphne).
X = judy ;
X = mark ;
No
parent(tom, adam).
parent(tom, helen).
parent(sandra, adam).
parent(sandra, helen).
parent(michael, andrew).
parent(michael, john).
parent(eve, andrew).
parent(eve, john).
parent(helen, mark).
parent(andrew, mark).
parent(judy, roger).
parent(judy, jim).
parent(judy, janis).
parent(mark, roger).
parent(mark, jim).
parent(mark, janis).
parent(janis, daphne).
parent(peter, daphne).
grandparent(X, Z) :- parent(X, Y),
parent(Y, Z).
Evaluation of a non-ground query
in the presence of rules: An example
Upon finding a match, Prolog
will stop here and wait for
instructions. The semicolon
symbol (;) inquires whether
more matches can be found.
A period symbol (.) would
indicate our intention to stop
the search.
32
I’m my own Grandpa
— Ray Stevens
33
https://blog.eogn.com/2015/01/23/im-my-own-grandpa/
Thanks to Dr. Nora Nouari
https://blog.eogn.com/2015/01/23/im-my-own-grandpa/
I’m my own Grandpa
— Ray Stevens
34
https://blog.eogn.com/2015/01/23/im-my-own-grandpa/
Thanks to Dr. Nora Nouari
Many, many years ago when I was twenty-three
I was married to a widow who was pretty as could be
This widow had a grown-up daughter who had hair of red
My father fell in love with her and soon they too were wed
This made my dad my son-in-law and really changed my life
For now my daughter was my mother, ’cause she was my father’s wife
And to complicate the matter, even though it brought me joy
I soon became the father of a bouncing baby boy
My little baby then became a brother-in-law to dad
And so became my uncle, though it made me very sad
For if he were my uncle, then that also made him brother
Of the widow’s grownup daughter, who was of course my step-mother
Father’s wife then had a son who kept them on the run
And he became my grandchild, for he was my daughter’s son
My wife is now my mother’s mother and it makes me blue
Because although she is my wife, she’s my grandmother too
Now if my wife is my grandmother, then I’m her grandchild
And every time I think of it, it nearly drives me wild
‘Cause now I have become the strangest ‘case you ever saw
As husband of my grandmother, I am my own grandpa
I’m my own grandpa, I’m my own grandpa
It sounds funny, I know but it really is so
I’m my own grandpa…
https://blog.eogn.com/2015/01/23/im-my-own-grandpa/
• We can now further extend the database with a rule to define
ancestor relation.
• Suppose we let p stand for the isParentOf relation and let a
stand for the isAncestorOf relation. Then we can define a in
terms of p by the following formula we will call A:
Multi-line rules: Disjunction
35
• In other words, x is an ancestor of y if either x is a parent of y,
or x is a parent of an ancestor of y. We can represent this in
Prolog with the rules below:
ancestor(X, Y) :- parent(X, Y).
ancestor(X, Y) :- parent(X, Z), ancestor(Z, Y).
• A rule can be placed in more than one lines.
• In this case, there is a disjunction between the two lines, and
there is a conjunction between the two goals of the body of
the second rule.
Multi-line rules: Disjunction /cont.
disjunction
conjunction
36
man(tom).
man(michael).
man(adam).
man(andrew).
man(john).
man(mark).
man(roger).
man(jim).
man(peter).
woman(sandra).
woman(eve).
woman(helen).
woman(judy).
woman(janis).
woman(daphne).
father(X, Y) :- man(X),
parent(X, Y).
mother(X, Y) :- woman(X),
parent(X, Y).
Further extending the database
We extend the database by introducing
four procedures:
man, woman: made up of facts, and
father, mother: rules.
father(X, Y) :- man(X),
parent(X, Y).
mother(X, Y) :- woman(X),
parent(X, Y).
37
• If any parameter of a relation is not important, we can replace
it with an anonymous variable denoted by the underscore
character (_) as follows:
is_father(X) :- father(X, _).
is_mother(X) :- mother(X, _).
• We can now pose more queries such as “Is Tom a father?”
• To answer this type of question, it does not matter who Tom is
the father of, as long as Tom is found as the first term in a
father statement. The query is as follows:
?- is_father(tom).
true
Anonymous variables in rules
38
• Alternatively we can use anonymous variables in queries,
such as
?- father(tom, _).
true
Anonymous variables in queries
39
• Operators +, -, *, /, **, and mod.
• Keyword is denotes arithmetic assignment.
• Example:
?- (7 is 6 + 1).
Yes
?- (X is 6 + 1).
X = 7 ;
No
40
Arithmetic Operators
• Operators <, >, =<, >=, =:=, and =\=.
\+ (logical NOT)
• Example:
?- (1 < 3), (4 < 2). No ?- (1 < 3); (4 < 2). Yes 41 Relational and Logical Operators • = means unification i.e. X = 2 • == means identical i.e. 2 == 2 • is evaluates r.h.s only i.e. X is (1 + 2) • =:= evaluates both sides i.e. (1+3) =:= (2 + 4) 42 = vs is vs == vs =:= Remember • Prolog cannot solve equations. • Instead is uses unification! • Example: – solve(X, Y) :- (X is Y + 1), (2 * X =:= Y + 3). ?- solve(2, 1). true ?- solve(X, Y). Arguments are not sufficiently instantiated 43 Prolog cannot solve equations! • Lists are represented in square brackets […]. • The empty list is represented by []. • Every non-empty list can be represented in two parts: – The head, which is the first element. – The tail, which is the list containing the remaining elements. – The head of [john, eve, paul] is john. – The tail of [john, eve, paul] is [eve, paul]. Lists 44 • The symbol | in [H|T] represents a list whose head is H and whose tail is T. • We can represent the above example as [john | [eve, paul] ] • Since [eve, paul] is also a list with head eve and tail [paul], we can write the above list as [john | [eve | [paul] ] ] • Any one-element list can be written as that element joined to the empty list. Thus, [paul] is the same as [paul | [] ] • We can now write the full list as [john | [eve | [paul | [ ] ] ] ] List representations 45 • We want to define a procedure member(X,L) which succeeds if X is an element of a list L. • We can define list membership recursively as follows: • X is a member of L if X is the head of L (regardless of what the tail is), or member(X, [X|_]). X is a member of the tail of L (regardless of what the head is). member(X, [_|T]) :- member(X, T). Example: Checking for list membership 46 ?- member(a, [a, b, c]). true ?- member(a, []). false. ?- member([b, c], [[a], [b, c]]). true ?- member(X, [a, b]). X = a ; X = b ; false. Example: Checking for list membership /cont. 47 Recall the run member/2: member(X, [X|_]). member(X, [_|T]) :- member(X, T). To improve efficiency, we can use the cut operation in prolog: ! member(X, [X|_]) :- !. member(X, [_|T]) :- member(X, T). Controlling backtracking with ‘cut’ 48 Using Cut: member(X, [X|_]) :- !. member(X, [_|T]) :- member(X, T). Example: ?- member(a, [a, b, c]). true ?- member(X, [a, b, c]). X = a. Controlling backtracking with ‘cut’ 49 • In this example, we want to define a rule which succeeds if an element is found to be in the last position of a non-empty list. • We can identify two cases for this: • The list has one element. • The list has more than one element. 50 Example: The last element in a list • Case 1: The list has only one element. • In this case, the last element is the only existing element of the list. • The following rule, last(L, [L]). reads “Rule last succeeds if element L is found to be the only element of a given list.” 51 Example: The last element in a list /cont. • Case 2: The list has more than one element. • In this case, we need to reduce the problem to the one that can be handled by case 1. • In other words, the clause will succeed once it chops off all elements, one by one, until it ends up with one element. 52 Example: The last element in a list /cont. • The following rule, last(L, [H|T]) :- last(L, T). reads “Rule last can succeed for a list whose head is H and whose tail is T, if it can succeed for a new list which is the tail T of the original list.” 53 Example: The last element in a list /cont. • In other words, let us get rid of the first element and see if we end up with only one element in which case the rule of case 1 will determine that this remaining element is indeed the last element. • However, if after getting rid of the first element we end up with a list with more than one elements, we must repeat this chopping off the head of the list, until we end up with a list which has only one element and subsequently handled by the first rule (of case 1). 54 Example: The last element in a list /cont. Given the rule, last(L, [L]). last(L, [H|T]) :- last(L, T). Consider the query ?- last(c, [a, b, c]). Prolog will (search its database from top to bottom and) unify the query with the head of the second statement of the rule, instantiate variable L to c and variable [H|T] to [a | b, c], resolve to a new query (that corresponds to the body of the rule): last(c, [b, c]). This new query must now be evaluated. 55 Example: The last element in a list /cont. Evaluation of a ground query [1 of 3]. Given the rule, last(L, [L]). last(L, [H|T]) :- last(L, T). The query ?- last(c, [b, c]). Will cause Prolog to (perform a new search and) unify the query with the head of the second statement of the rule, instantiate variable L to c and variable [H|T] to [b | c], resolve to a new query (that corresponds to the body of the rule): last(c, [c]). This new query must now be evaluated. 56 Example: The last element in a list /cont. Evaluation of a ground query [2 of 3]. Given the rule, last(L, [L]). last(L, [H|T]) :- last(L, T). The query ?- last(c, [c]). Will cause Prolog to (perform a new search and) unify the query with the head of the first statement of the rule, and yield a success, indicating that it is indeed the case that c is found in the last position of the list. 57 Example: The last element in a list /cont. Evaluation of a ground query [3 of 3]. • Consider a rule size/2 to read in a list and calculate its length. size([],0). size([H|T],N) :- size(T,N1), N is N1+1. • We can execute queries as follows: ?- size([],N). N = 0. ?- size([a,b,c],N). N = 3. ?- size([[a,b],c],N). N = 2. ?- size([[a,b,c]],N). N = 1. 58 Example: Calculating the size of a list • Consider a list L and an element X that we need to delete from the list L. • We can identify three cases: 1. The L is empty, the result is the empty list. 2. If X is head of L, then the result is the tail of the initial list. 3. If X is present in the tail part, then keep the head and recur on the tail. • Consider rule delete/3: remove(_, [], []). remove(X,[X|T], T). remove(X, [H|T1], [H|T2]) :- X \= H, remove(X,T1,T2). ?- remove(a, [a, b, c], O). O = [b, c]. 59 Example: Deleting an element from a list • Note that the previous solution only deletes the first occurrence of X. ?- remove(a, [a, a, b, c], O). O = [a, b, c]. • We may modify the rules to delete all occurrences of X in L. • Consider rule delete-all/3: remove-all(_, [], []). remove-all(X,[X|T], O) :- remove-all(X, T, O). remove-all(X, [H|T1], [H|T2]) :- X \= H, remove-all(X,T1,T2). ?- remove-all(a, [a, a, b, c], O). O = [b, c]. 60 Example: Deleting all occurrences • The built-in function findall(X, P, L) returns a list L with all values for X that satisfy predicate P. • To eliminate redundancies in a list, we can use the built-in function list_to_set(List, Set) that converts the list (with possibly repeated elements) into a set. • The built-in function length(List, L) returns the length L of a given list. 61 Built-in utility functions • Let us obtain a set of all fathers: ?- findall(F, father(F, _), Lst). Lst = [tom, tom, michael, michael, andrew, mark, mark, mark, peter]. ?- findall(F, father(F, _), Lst), list_to_set(Lst, Set). Lst = [tom, tom, michael, michael, andrew, mark, mark, mark, peter], Set = [tom, michael, andrew, mark, peter]. 62 Example with findall and list_to_set in a query • The query findall(F, father(F, _), Lst), list_to_set(Lst, Set) is rather long and complex. • We can encapsulate its size and complexity in a rule: get_all_fathers(Set) :- findall(F, father(F, _), Lst), list_to_set(Lst, Set). ?- get_all_fathers(Set). Set = [tom, michael, andrew, mark, peter]. 63 Example with findall and list_to_set in a rule • Let us construct a rule qualifies_for_benefits(P) that succeeds if P is a mother of at least three children. qualifies_for_benefits(P) :- woman(P), findall(C, parent(P, C), L), length(L, N), N >= 3.
?- qualifies_for_benefits(Name).
Name = judy ;
false.
64
Example with findall and length in a rule
• How about?
qualifies_for_benefits(P) :-
woman(P),
findall(P, parent(P, _), L),
length(L, N),
N >= 3.
?- qualifies_for_benefits(Name).
Name = judy ;
false.
65
Example with findall and length in a rule
• Qualifiers may be used to pose questions such as “Are all
men parents?”. To do this, in prolog we use forall qualifier.
?- forall(man(X), parent(X, _)).
No
66
Qualifiers
• Videos
– https://www.youtube.com/watch?v=SykxWpFwMGs
67
Prolog Tutorial