COMP4418: Knowledge Representation and Reasoning
Introduction to Prolog
Maurice Pagnucco
School of Computer Science and Engineering University of New South Wales
NSW 2052, AUSTRALIA morri@cse.unsw.edu.au
Reference: Ivan Bratko, Prolog Programming for Artificial Intelligence, Addison- Wesley, 2001. Chapters 1 and 2.
COMP4418 ⃝c UNSW, 2019
COMP4418, Monday 30 September, 2019 Introduction to Prolog 1
Prolog
Prolog — Programming in Logic
Invented early 70s by Alain Colmeraurer et al., University of
Marseille
Declarative language
◮ Specify goal and interpreter/compiler will work out how to achieve it
◮ Traditional (imperative) languages require you to specify how to solve problem
Prolog program specifies:
◮ facts about objects and their relationships ◮ rules about objects and their relationships
COMP4418 ⃝c UNSW, 2019 Generated: 15 September 2019
COMP4418, Monday 30 September, 2019
Introduction to Prolog 2
Starting Prolog
$ prolog
iProlog (8 April 2001)
: ^D
$
$ prolog courses.pl
iProlog (8 April 2001)
: lectures(maurice, comp4418)? ** yes
: ^D
$
COMP4418 ⃝c UNSW, 2019
Generated: 15 September 2019
COMP4418, Monday 30 September, 2019 Introduction to Prolog 3
Relations
Prolog programs specify relationships among objects and properties of objects
When we say, “John owns the book”, we are declaring the ownership relation between two objects: John and the book
When we ask, “Does John own the book?”, we are querying the relationship
Relationships can also be rules such as:
Two people are sisters if both are female
they have the same parents
This is a rule that allows us to find out about a relationship even if the relationship isn’t explicitly declared
COMP4418 ⃝c UNSW, 2019 Generated: 15 September 2019
COMP4418, Monday 30 September, 2019 Introduction to Prolog 4
Programming in Prolog
Declare facts describing explicit relationships between objects and properties of objects
Define rules describing implicit relationships between objects or implicit object properties
Ask questions about relationships between objects and object properties
COMP4418 ⃝c UNSW, 2019 Generated: 15 September 2019
COMP4418, Monday 30 September, 2019 Introduction to Prolog 5
Representing Regulations
The rules for entry into a professional computer science society are set out below:
An applicant to the society is acceptable if he or she has been nominated by two established members of the society and is eligible under the terms below:
the applicant graduated with a university degree
the applicant has two years of professional experience the applicant pays a joining fee of $200.
An established member is one who has been a member for at least two years.
COMP4418 ⃝c UNSW, 2019 Generated: 15 September 2019
COMP4418, Monday 30 September, 2019 Introduction to Prolog 6
Facts
Properties of objects; relationshps between objects
Example
◮ “Maurice lectures in course COMP4418” ◮ Prolog:lectures(maurice,comp4418)
Notice
◮ Names of properties/relationships begin with lower-case character
◮ Name of relationship appears as first term, objects appear as arguments
◮ Fact terminated by ‘.’
◮ Objects (atoms) also begin with lower-case characters
lectures(maurice, 4418) also called a predicate
COMP4418 ⃝c UNSW, 2019 Generated: 15 September 2019
COMP4418, Monday 30 September, 2019
Introduction to Prolog 7
Facts
Let us return to the regulations example:
experience(fred, 3). fee_paid(fred). graduated(fred, unsw). university(unsw). nominated_by(fred, jim). nominated_by(fred, mary). joined(jim, 1998). joined(mary, 1997). current_year(2001).
COMP4418 ⃝c UNSW, 2019
Generated: 15 September 2019
COMP4418, Monday 30 September, 2019 Introduction to Prolog 8
Prolog Database
A collection of facts about a hypothetical computer science department:
% lectures(X, Y): person X lectures in course Y lectures(tony, comp1001).
lectures(andrew, comp2041).
lectures(john, comp2041).
lectures(gernot, comp3231). lectures(arun, comp4141). lectures(sowmya, comp4411). lectures(claude, comp4411). lectures(maurice, comp4418). lectures(adnan, comp4418). lectures(adnan, comp9518). lectures(wayne, comp4418). lectures(arthur, comp9020).
COMP4418, Monday 30 September, 2019 Introduction to Prolog 9
% studies(X, Y): person X studies course Y studies(mary, comp1001).
studies(jim, comp1001).
studies(jane, comp4411).
studies(jane, comp4418).
studies(jack, comp9518).
studies(jack, comp9020).
% year(X, Y): person X is in year Y year(mary, 1).
year(jim, 1).
year(jane, 4).
year(jack, 4).
Together, these facts form Prolog’s database.
COMP4418 ⃝c UNSW, 2019 Generated: 15 September 2019
COMP4418, Monday 30 September, 2019 Introduction to Prolog 10
Queries
Once we have a database of facts (and, soon, rules) we need to be able to ask questions of the information that is stored
lectures(maurice, comp4418)?
Notice:
COMP4418
⃝c UNSW, 2019 Generated: 15 September 2019
◮ Query is terminated by a question mark ‘?’
◮ To determine answer (yes or no), Prolog consults database checking whether this is a known fact
◮ Forexample,lectures(bob,comp4418)? **no
◮ If answer is yes, query succeeded; otherwise, if answer is no, query failed
COMP4418, Monday 30 September, 2019 Introduction to Prolog 11
Variables
Suppose we want to ask, “What subject does John teach?”
This could be phrased as:
Is there a subject, X, that John teaches?
The variable X stands for an object that the questioner does not yet know about
To answer the question, Prolog has to find the value of X, if it exists
As long as we do not know the value of the variable, it is said to be
unbound
When a value is found, the variable is bound to that value
COMP4418 ⃝c UNSW, 2019 Generated: 15 September 2019
COMP4418, Monday 30 September, 2019 Introduction to Prolog 12
Variables
A variable must begin with a capital letter or ‘ ’
To ask Prolog to find the subject that John teaches, type:
: lectures(john, Subject)? Subject = comp2041
To ask which subjects that Adnan teaches, ask: : lectures(adnan, X)?
X = comp4418
X = comp9518
Prolog can find all possible ways to satisfy a query
COMP4418 ⃝c UNSW, 2019 Generated: 15 September 2019
COMP4418, Monday 30 September, 2019 Introduction to Prolog 13
Conjunction in Queries
How do we ask, “Does Arthur teach Jack?”
This can be answered by finding out whether Arthur lectures in a subject that Jack studies:
lectures(arthur, Subject), studies(jack, Subject)? i.e., Arthur lectures in subject, Subject, and Jack studies subject,
Subject.
Subject is a variable
The question consists of two goals
To find the answer, Prolog must find a single value for Subject that satisfies both goals
COMP4418 ⃝c UNSW, 2019 Generated: 15 September 2019
COMP4418, Monday 30 September, 2019 Introduction to Prolog 14
Conjunctions
Who does Adnan teach:
: lectures(adnan, Subject), studies(Student, Subject)? Subject = comp4418
Student = jane
Subject = comp9518
Student = jack
Prolog solves problems by proceedings left to right and then backtracking
Given the initial query, Prolog tries to solve lectures(adnan, Subject)
Therearetwelvelecturesclausesbutonlytwohaveadnanasfirst argument
Prolog chooses the first clause containing a reference to adan i.e., lectures(adnan, 4418)
COMP4418 ⃝c UNSW, 2019 Generated: 15 September 2019
COMP4418, Monday 30 September, 2019 Introduction to Prolog 15
Proof Tree
With Subject = 4418, it then tries to satisfy the next goal, viz studies(Student, 4418)
After the solution is found, Prolog retraces its steps and looks for alternative solutions
Itmaynowgodownthebranchcontaininglectures(adnan,9518) and try studies(Student, 9518)
lectures(adnan, Subject), studies(Student, Subject)?
lectures(adnan, 9414)
lectures(adnan, 9518)
studies(jane, 9414)
studies(jack, 9518)
COMP4418 ⃝c UNSW, 2019
Generated: 15 September 2019
COMP4418, Monday 30 September, 2019 Introduction to Prolog 16
Rules
The previous question can be restated as a general rule:
One person, Teacher teaches another person, Student if Teacher lectures subject, Subject and
Student studies Subject
In Prolog this is written as the:
teaches(Teacher, Student) :- % This is a clause lectures(Teacher, Subject), studies(Student, Subject).
teaches(adnan, Student)?
Facts are unit clauses and rules are non-unit clauses
COMP4418 ⃝c UNSW, 2019 Generated: 15 September 2019
COMP4418, Monday 30 September, 2019
Introduction to Prolog 17
Rules
acceptable(Applicant) :- nominated(Applicant), eligible(Applicant).
nominated(Applicant) :-
nominated_by(Applicant,
nominated_by(Applicant,
Member1 \= Member2,
current_year(ThisYear),
joined(Member1, Year1),
joined(Member2, Year2),
Member1),
Member2),
ThisYear >= Year1 + 2, ThisYear >= Year2 + 2,.
eligible(Applicant) :-
graduated(Applicant, University), university(University), experience(Applicant, Experience), Experience >= 2, fee_paid(Applicant).
COMP4418 ⃝c UNSW, 2019 Generated: 15 September 2019
COMP4418, Monday 30 September, 2019 Introduction to Prolog 18
Clause Syntax
‘:-’ means “if” or “is implied by”. Also called “neck”
The left hand side of the neck is the head
The right hand side is called the body
The comma, ‘,’ separating the goals stands for and
more_advanced(Student1, Student2) :- year(Student1, Year1), year(Student2, Year2),
Year1 > Year2.
Note the use of the predefined predicate ‘>’ more_advanced(jane, mary)?
more_advanced(jack, X)?
COMP4418 ⃝c UNSW, 2019 Generated: 15 September 2019
COMP4418, Monday 30 September, 2019 Introduction to Prolog 19
Structures
Functional terms can be used to construct complex data structures
E.g., to say that John owns the book Foundation, this may be expressed as:
owns(john, ’Foundation’).
Often objects have a number of attributes
A book may have a title and an author:
owns(john, book(’Foundation’, asimov)).
To be more accurate we should give the author’s family and given
names: owns(john, book(’Foundation’, author(asimov, isaac))).
COMP4418 ⃝c UNSW, 2019 Generated: 15 September 2019
COMP4418, Monday 30 September, 2019 Introduction to Prolog 20
Asking Questions with Structures
Howdoweask:
“What books does John own that were written by someone called “Asimov”?
: owns(john, book(Title, author(asimov, GivenName)))? Title = Foundation
GivenName = isaac
: owns(john, Book)?
Book = book(Foundation, author(asimov, isaac))
: owns(john, book(Title, Author))? Title = Foundation
Author = author(asimov, isaac)
COMP4418 ⃝c UNSW, 2019 Generated: 15 September 2019
COMP4418, Monday 30 September, 2019 Introduction to Prolog 21
Databases
A database of books in a library contains facts of the form: ◮ book(CatNo, Title, author(Family, Given)). ◮ member(MemNo, name(Family, Given), Address). ◮ loan(CatNo, MemNo, Borrowed, Due).
A member of the library may borrow a book
A “loan” records:
◮ the catalogue number of the book ◮ the number of the member
◮ the borrow date
◮ the due date
COMP4418 ⃝c UNSW, 2019 Generated: 15 September 2019
COMP4418, Monday 30 September, 2019 Introduction to Prolog 22
Database Structures
Dates are stored as structures: date(Year, Month, Day).
E.g.,date(2001,9,8)represents8September2001
Names and addresses are all stored as character strings
Which books has a member borrowed?
has_borrowed(MemFamily, Title, CatNo) :- memb(MemNo, name(MemFamily, _), _), loan(CatNo, MemNo, _, _), book(CatNo, Title, _).
Which books are overdue?
COMP4418 ⃝c UNSW, 2019 Generated: 15 September 2019
COMP4418, Monday 30 September, 2019 Introduction to Prolog 23
Overdue Books
later(date(Y, M, D1), date(Y, M, D2)) :- D1 > D2. later(date(Y, M1, _), date(Y, M2, _)) :- M1 > M2. later(date(Y1, _, _), date(Y2, _, _)) :- Y1 > Y2.
later(date(2001, 12, 3), date(1999, 8, 3))?
overdue(Today, Title, CatNo, MemFamily) :- loan(CatNo, MemNo, _, DueDate), later(Today, DueDate),
book(CatNo, Title, _),
memb(MemNo, name(MemFamily, _), _).
COMP4418 ⃝c UNSW, 2019 Generated: 15 September 2019
COMP4418, Monday 30 September, 2019 Introduction to Prolog 24
Due Date
due_date(date(Y, M1, D), date(Y, M2, D)) :- M1 < 12,
M2 is M1 + 1.
due_date(date(Y1, 12, D), date(Y2, 1, D)) :-
Y2 is Y1 + 1.
is accepts two arguments
The right hand argument must be an evaluable arithmetic expression The term is evaluated and unified with the left hand argument
It is not an assignment statement
Variables cannot be reassigned values
Argumentsofcomparisonoperatorscanalsobearithmeticexpressions COMP4418 ⃝c UNSW, 2019 Generated: 15 September 2019