What is Prolog?

What is Prolog? (continued)

• traditional programming languages are said to be procedural
• procedural programmer must specify in detail how to solve a problem:

  mix ingredients;
  beat until smooth;
  bake for 20 minutes in a moderate oven;
  remove tin from oven;
  put on bench;
  close oven;
  turn off oven;

• in purely declarative languages, the programmer only states what the problem is and leaves the rest to the language system

Applications of Prolog

Some applications of Prolog are:

• intelligent data base retrieval
• natural language understanding
• expert systems
• specification language
• machine learning
• robot planning
• automated reasoning
• problem solving

The Prolog Language

Relations

• Prolog programs specify relationships among objects and properties of objects.

• When we say, "John owns the book", we are declaring the ownership relationship between two objects: John and the book.

• When we ask, "Does John own the book?" we are trying to find out about a relationship.

• Relationships can also rules such as:

  Two people are sisters if

  they are both female and they have the same parents.

• A rule allows us to find out about a relationship even if the relationship isn't explicitly stated as a fact.

Programming in Prolog

• declare facts describing explicit relationships between objects and properties objects might have (e.g. Mary likes pizza, grass has_colour green)

• define rules defining implicit relationships between objects (e.g. the sister rule above) and/or rules defining implicit object properties (e.g. X is a parent if there is a Y such that Y is a child of X).

One then uses the system by:

• asking questions above relationships between objects, and/or about object properties (e.g. does Mary like pizza? is Joe a parent?)

Facts

• Properties of objects, or relationships between objects;

• "Dr Turing lectures in course 9020", is written in Prolog as:

  	lectures(turing, 9020).
  

• Notice:
  • names of properties/relationships begin with lower case letters.
  • the relationship name appears as the first term
  • objects appear as comma-separated arguments within parentheses.
  • A period "." must end a fact.
  • objects also begin with lower case letters. They also can begin with digits (like 9020), and can be strings of characters enclosed in quotes (as in reads(fred, "War and Peace")).

• lectures(turing, 9020). is also called a predicate

Facts about a hypothetical computer science department:

Queries

• Once we have a database of facts (and, soon, rules) we can ask questions about the stored information.

• Suppose we want to know if Turing lectures in course 9020. We can ask:

  % prolog -s facts03 (multi-line welcome message) ?- lectures(turing, 9020). true. ?- <control-D> %

  facts03 loaded into Prolog "?-" is Prolog's prompt output from Prolog hold down control & press D to leave Prolog

• Notice:

  • In SWI Prolog, queries are terminated by a full stop.

  • To answer this query, Prolog consults its database to see if this is a known fact.

  • In example dialogues with Prolog, the text in green italics is what the user types.

Another example query

?- lectures(codd, 9020).
fail.

Variables

• Suppose we want to ask, "What course does Turing teach"?

• This could be written as:

  	Is there a course, X, that Turing teaches?
  

• The variable X stands for an object which the questioner does not know about yet.

• To answer the question, Prolog has to find out the value of X, if it exists.

• As long as we do not know the value of a variable it is said to be unbound.

• When a value is found, the variable is said to bound to that value.

• The name of a variable must begin with a capital letter or an underscore character, "_".

Variables 2

• To ask Prolog to find the course which Turing teaches, the following query is entered:

  ?- lectures(turing, Course).
Course = 9020  ← output from Prolog

• To ask which course(s) Prof. Codd teaches, we may ask,

  ?- lectures(codd , Course).
Course = 9311 ;  ← type ";" to get next solution
  Course = 9314
?-

  If Prolog can tell that there are no more solutions, it simply gives you the ?- prompt for a new query. This is what happens here. If Prolog can't tell, it will give you an opportunity to type ; again, and then if there is no further solution, report fail.

• Prolog can find all possible ways to answer a query, unless you explicitly tell it not to (see cut, later).

Conjunctions of Goals in Queries

• How do we ask, "Does Turing teach Fred"?

• This means finding out if Turing lectures in a course that Fred studies.

  	?- lectures(turing, Course), studies(fred, Course).
  

• i.e. "Turing lectures in course, Course and Fred studies (the same) Course".

• The question consists of two goals.

• To answer this question, Prolog must find a single value for Course, that satisfies both goals.

• Read the comma, ",", as and.

• However, note that Prolog will evaluate the two goals left-to-right. In pure logic, P1 ∧ P2 is the same as P2 ∧ P1. In Prolog, there is the practical consideration of which goal should be evaluated first - the code might be more efficient one way or the other. In particular, in "P1, P2", if P1 fails, then P2 will not be evaluated at all. This is sometimes referred to as "conditional-and".

Disjunctions of Goals in Queries

• What about or (i.e. disjunction)? It turns out explicit ors aren't needed much in Prolog

• There is a way to write or: (";")

• Avoid using if you can, at least until you have learned how to manage without it.

• To reinforce this message, you will be penalised if you use the or operator ; in the first (Prolog) assignment in COMP9414. This prohibition means you can't use the … -> … ; … construct either, in the first assignment. The … -> … ; … construct is not taught in COMP9414, but in the past, some people have found out about it.

Backtracking in Prolog

• Who does Codd teach?

    ?- lectures(codd, Course), studies(Student, Course).
    Course = 9311
    Student = jack ;
  
    Course = 9314
    Student = jill ;
  
    Course = 9314
    Student = henry ;
  

• Prolog solves this problem by proceeding left to right and then backtracking.

• When given the initial query, Prolog starts by trying to solve

  	lectures(codd, Course)
  

• There are six lectures clauses, but only two have codd as their first argument.

• Prolog uses the first clause that refers to codd: lectures(codd, 9311).

• With Course = 9311, it tries to satisfy the next goal, studies(Student, 9311).

• It finds the fact studies(jack, 9311). and hence the first solution: (Course = 9311, Student = jack)

Backtracking in Prolog 2

• After the first solution is found, Prolog retraces its steps up the tree and looks for alternative solutions.

• First it looks for other students studying 9311 (but finds none).

• Then it
  • backs up
  • rebinds Course to 9314,
  • goes down the lectures(codd, 9314) branch
  • tries studies(Student, 9314),
  • finds the other two solutions:
    (Course = 9314, Student = jill)
    and (Course = 9314, Student = henry).

Backtracking in Prolog 3

To picture what happens when Prolog tries to find a solution and backtracks, we draw a "proof tree":

Rules

• The previous question can be restated as a general rule:

  	One person, Teacher, teaches another person, Student if
  		Teacher lectures in a course, Course and
  		Student studies Course.
  

• In Prolog this is written as:

  	teaches(Teacher, Student) :-
  		lectures(Teacher, Course),
  		studies(Student, Course).
  
          ?- teaches(codd, Student).
  

• Facts are unit clauses and rules are non-unit clauses.

Clause Syntax

• ":-" means "if" or "is implied by". Also called the neck symbol.

• The left hand side of the neck is called the head.

• The right hand side of the neck is called the body.

• The comma, ",", separating the goals is stands for and.

• Another rule, using of the predefined predicate ">".

  	more_advanced(S1, S2) :-
  		year(S1, Year1),
  		year(S2, Year2),
  		Year1 > Year2.
  

Tracing Execution

	more_advanced(S1, S2) :-
		year(S1, Year1),
		year(S2, Year2),
		Year1 > Year2.

?- trace.
true.
[trace] ?- more_advanced(henry, fred).
  Call: more_advanced(henry, fred) ? *
  Call: year(henry, _L205) ?
  Exit: year(henry, 4) ?
  Call: year(fred, _L206) ?
  Exit: year(fred, 1) ?
^ Call: 4>1 ?
^ Exit: 4>1 ?
  Exit: more_advanced(henry, fred) ?
true.
[debug]  ?- notrace.

bind S1 to henry, S2 to fred
test 1st goal in body of rule
succeeds, binds Year1 to 4
test 2nd goal in body of rule
succeeds, binds Year2 to 1
test 3rd goal: Year1 > Year2
succeeds
succeeds

true., fail., or More?

Structures

Reference:

Bratko chapter 2

• Functional terms can be used to construct complex data structures.

• If we want to say that John owns the novel Tehanu, we can write: owns(john, 'Tehanu').

• Often objects have a number of attributes: owns(john, book('Tehanu', leguin)).

• The author LeGuin has attributes too: owns(john, book('Tehanu', author (leguin, ursula))).

• The arity of a term is the number of arguments it takes.

• all versions of owns have arity 2, but the detailed structure of the arguments changes.

• gives(john, book, mary). is a term with arity 3.

Asking Questions with Structures

• How do we ask, "What books does John own which were written by someone called LeGuin"?

  ?- owns(john, book(Title, author(leguin, GivenName))).
  Title = 'Tehanu'
  GivenName = ursula
  

• What books does John own?

  ?- owns(john, Book).
  Book = book('Tehanu', author(leguin, ursula))
  

• What books does John own?

  ?- owns(john, book(Title, Author)).
  Title = 'Tehanu'
  Author = author(leguin, ursula)
  

• Prolog performs a complex matching operation between the structures in the query and those in the clause head.

Library Database Example

• A database of books in a library contains facts of the form

  book(CatalogNo, Title, author(Family, Given)).
  libmember(MemberNo, name(Family, Given), Address).
  loan(CatalogNo, MemberNo, BorrowDate, DueDate).
  

• A member of the library may borrow a book.

• A "loan" records:
  • the catalogue number of the book
  • the number of the member
  • the date on which the book was borrowed
  • the due date

Library Database Example 2

• Dates are stored as structures:
  date(Year, Month, Day)

• e.g. date(2008, 6, 16) represents 16 June 2008.

• which books has a member borrowed?

  borrowed(MemFamily, Title, CatalogNo) :-
     libmember(MemberNo, name(MemFamily, _), _),
     loan(CatalogNo, MemberNo, _, _),
     book(CatalogNo, Title, _).
  

• The underscore or "don't care" variables (_) are used because for the purpose of this query we don't care about the values in some parts of these structures.

Comparing Two Terms

• we would like to know which books are overdue; how do we compare dates?

  %later(Date1, Date2) if Date1 is after Date2:
  
  later(date(Y, M, Day1), date(Y, M, Day2)) :-
  	Day1 > Day2.
  later(date(Y, Month1, _), date(Y, Month2, _)) :-
  	Month1 > Month2.
  later(date(Year1, _, _), date(Year2, _, _)) :-
  	Year1 > Year2.
  

• This rule has three clauses: in any given case, only one clause is appropriate. They are tried in the given order.

• This is how disjunction (or) is often achieved in Prolog. In effect, we are saying that the first date is later than the second date if Day1 > Day2 and the Y and M are the same, or if the Y is the same and Month1 > Month2, or if Year1 > Year2.

• Again we are using the comparison operator ">"

• More complex arithmetic expressions can be arguments of comparison operators
  - e.g. X + Y >= Z * W * 2.

• Footnote: if the year and month are the same, then the heads of all three rules match, and so, while the first rule is the appropriate one, all three will be tried in the course of backtracking. However, the condition "Month1 > Month2" in the second rule means that it will fail in this case, and similarly for the third rule.

Overdue Books

% overdue(Today, Title, CatalogNo, MemFamily):
%   given the date Today, produces the Title, CatalogNo,
%   and MemFamily of all overdue books.

overdue(Today, Title, CatalogNo, MemFamily) :-
  loan(CatalogNo, MemberNo, _, DueDate),
  later(Today, DueDate),
  book(CatalogNo, Title, _),
  libmember(MemberNo, name(MemFamily, _), _).

Due Date

• Assume the loan period is one month:

  due_date(date(Y, Month1, D),
           date(Y, Month2, D)) :-
             Month1 < 12,
  		   Month2 is Month1 + 1.
  
  due_date(date(Year1, 12, D),
           date(Year2, 1, D)) :-
             Year2 is Year1 + 1.
  

Binary Trees

• In the library database example, some complex terms contained other terms, for example, book contained name.

• The following term also contains another term, this time one similar to itself:

  tree(tree(L1, jack, R1), fred, tree(L2, jill, R2))
  

• The variables L1, L2, R1, and R2 should be bound to sub-trees (this will be clarified shortly).

• A structure like this could be used to represent a "binary tree" that looks like:
  

• Binary because each "node" has two branches (our backtrack tree before had many branches at some nodes)

Recursive Structures

• A term that contains another term that has the same principal functor (in this case tree) is said to be recursive.

• Biological trees have leaves. For us, a leaf is a node with two empty branches:
  

• empty is an arbitrary symbol to represent the empty tree. In full, the tree above would be:
  

  tree(tree(empty, jack, empty), fred, tree(empty, jill, empty))

• Usually, we wouldn't bother to draw the empty nodes:
  
  

Another Tree Example

• tree(tree(empty, 7, empty),
       '+',
       tree(tree(empty, 5, empty),
            '-',
            tree(empty, 3, empty)))

  

Recursive Programs for Recursive Structures

• A binary tree is either empty or contains some data and a left and right subtree which are also binary trees.

• In Prolog we express this as:

  is_tree(empty).	trivial branch
  is_tree(tree(Left, Data, Right)) :-       is_tree(Left),       some_data(Data),       is_tree(Right).	recursive branch

• A non-empty tree is represented by a 3-arity term.

• Any recursive predicate must have:
  • (at least) one recursive branch/rule (or it isn't recursive :-) ) and
  • (at least) one non-recursive or trivial branch (to stop the recursion going on for ever).
  The example at the heading "An Application of Lists", below, will show how the recursive branch and the trivial branch work together. However, you probably shouldn't try to look at it until we have studied lists.

Recursive Programs for Recursive Structures 2

• Let us define (or measure) the size of tree (i.e. number of nodes):

  tree_size(empty, 0).
  tree_size(tree(L, _, R), Total_Size) :-
  	tree_size(L, Left_Size),
  	tree_size(R, Right_Size),
  	Total_Size is
          Left_Size + Right_Size + 1.
  

• The size of an empty tree is zero.

• The size of a non-empty tree is the size of the left sub-tree plus the size of the right sub-tree plus one for the current tree node.

• The data does not contribute to the total size of the tree.

• Recursive data structures need recursive programs. A recursive program is one which refers to itself, thus, tree_size contains goals that call for the tree_size of smaller trees.

Lists

• A list may be nil (i.e. empty) or it may be a term which has a head and a tail

• The head may be any term or atom.

• The tail is another list.

• We could define lists as follows:

  	is_list(nil).
  	is_list(list(Head, Tail)) :-
  		is_list(Tail).
  

• A list of numbers [1, 2, 3] would look like:

  	list(1, list(2, list(3, nil)))
  

• This notation is understandable but clumsy. Prolog doesn't actually recognise it, and in fact uses . instead of list and [] instead of nil. So Prolog would recognise .(1, .(2, .(3, []))) as a list of three numbers. This is less clumsy but still looks strange, and is hard to work with.

• Since lists are used so often, Prolog in fact has a special notation:

  	[1, 2, 3] = .(1, .(2, .(3, [])))
  
  ?- X =  .(1, .(2, .(3, []))).
  X = [1, 2, 3]
  

List Constructor |

• Within the square brackets [ ], the symbol | acts as an operator to construct a list from an item and another list.

• ?- X = [1 | [2, 3]].
  X = [1, 2, 3].

• ?- Head = 1 , Tail = [2, 3], List = [Head | Tail].
  List = [1, 2, 3].

Examples of Lists

?- [X | Y] = [1].
X = 1
Y = []

The first several elements of the list can be selected before matching the tail:

?- [X, Y | Z] = [fred, jim, jill, mary].
X = fred
Y = jim
Z = [jill, mary]

More Complex List Matching

?- [X | Y] = [[a, f(e)], [n, m, [2]]].

X = [a, f(e)]
Y = [[n, m, [2]]]

Notice that Y is shown with an extra pair of brackets: Y is the tail of the entire list: [n, m, [2]] is the sole element of Y.

List Membership

Controlling Execution

The Cut Operator (!)

• Sometimes we need a way to prevent Prolog finding all solutions, i.e. a way to stop backtracking.

• The cut operator, written !, is a built-in goal that prevents backtracking.

• It turns Prolog from a nice declarative language into a hybrid monster.

• Use cuts sparingly and with a sense of having sinned.

Cut Operator 2

Recall this example:

Cut Prunes the Search Tree

• If the goal(s) to the right of the cut fail then the entire clause fails and the the goal which caused this clause to be invoked fails.
  

• In particular, alternatives for Course are not explored.

Cut Prunes the Search Tree 2

• Another example: using the facts03 database, try

  ?- lectures(codd, X).
  X = 9311 ;
  X = 9314.
  
  ?- lectures(codd, X), ! .
  X = 9311.
  

• The cut in the second version of the query prevents Prolog from backtracking to find the second solution.

Using cuts in later to improve efficiency

Recall the code for later:

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(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.

In other cases, adding cuts of this sort to multi-rule procedures might be a useful (if lazy) way of ensuring that only one rule is used in a particular case. Unless it makes the code very clumsy, it is better to use and rely on "condition" goals in each rule (like M1 > M2 in the second rule for later) to specify the case in which it is appropriate. More examples of this are below.

Another cut example

• max, without cut:

  % max(A, B, C) binds C to the larger of A and B.
  max(A, B, A) :-
     A > B.
  max(A, B, B) :-
     A =< B.

• max, with cut:

  max(A, B, A) :-
     A > B,
     !.
  max(A, B, B).

• The first version has a negated test in the second rule (=< vs >). The second version substitutes a cut in the first rule for the negated test.

• Remember, no cuts in the first assignment unless they are essential!

Another cut example 2

• remove_dups, without cut:

  remove_dups([], []).
  remove_dups([First | Rest], NewRest) :-
      member(First, Rest),
      remove_dups(Rest, NewRest).
  remove_dups([First | Rest], [First | NewRest]) :-
      not(member(First, Rest)),
      remove_dups(Rest, NewRest).

• remove_dups, with cut:

  remove_dups([], []).
  remove_dups([First | Rest], NewRest) :-
      member(First, Rest),
      !,
      remove_dups(Rest, NewRest).
  remove_dups([First | Rest], [First | NewRest]) :-
      remove_dups(Rest, NewRest).

• The first version has a negated test in the third rule (not(member(First, Rest))). The second version substitutes a cut in the second rule for the negated test in the third rule.