Prolog 1

• What is Prolog?
• The canonical family tree example
• Lists in Prolog
• Prolog terminology

What is Prolog?

• Language for “logic programming”
• Input: (1) Facts and rules (2) A query. Output: The answer(s) to the query
• Declarative language: Tell the system what you want, not how to compute it
• Invented by Alain Colmeraurer in Marseille, France, in 1970s
• Why do we care?
• A very different model of computation
• Often effective to split system into imperative and declarative parts

The Canonical Example - Facts

• Facts (family.pl)

  male(james1).
  male(charles1).
  male(charles2).
  male(james2).
  male(george1).
  
  female(catherine).
  female(elizabeth).
  female(sophia).
  
  parent(james1, charles1).
  parent(james1, elizabeth).
  parent(charles1, charles2).
  parent(charles1, catherine).
  parent(charles1, james2).
  parent(elizabeth, sophia).
  parent(sophia, george1).

The Canonical Example - Queries

• Change to the directory containing family.pl
• Start the Prolog interpreter
• Type consult(family).
• Note the period at the end—every Prolog command ends in a period
• You must put facts and rules in a file, load it with consult
• Then issue queries in the terminal window

  parent(charles1, X).
  X = charles2 ;
  X = catherine ;
  X = james2 ;
  fail.

• Type ; after each response
• Note: Query variables are uppercase, all others lowercase

The Canonical Example - Rules

• mother(X, Y) :- female(X), parent(X, Y).

• Read :- as “provided that” or “if”
• Commas on the right hand side mean “and”
• Sample queries

  mother(sophia, george1).
  true.
  mother(X, sophia).
  X = elizabeth ;
  fail.
  mother(X, charles1).
  fail.

Lists in Prolog

• Empty list []
• List with head H and tail T [H | T]
• Short form for [john | [mary | [pat | []]]] is [john, mary, pat]
• Use pattern matching to define list predicates

  member(X,[X|_]).
  member(X,[_|T]) :- member(X,T).

• Sample queries

  member(mary, [john, mary, pat]).
  true ;
  fail
  member(ann, [john, mary, pat]).
  fail ;
  member(X, [john, mary, pat]).
  X = john ;
  X = mary ;
  X = pat ;
  fail.

The Append Predicate

• Prolog has only predicates, not functions
• append(X, Y, Z) means “It is true that Z is X appended with Y”

• append([], Ys, Ys).
  append([X | Xs], Ys, [X | Zs]) :- append(Xs, Ys, Zs).

• Sample queries

  append([john], [mary, pat], Z).
  Z = [john, mary, pat].
  append(X, Y, [john, mary, pat]).
  X = [],
  Y = [john, mary, pat] ;
  X = [john],
  Y = [mary, pat] ;
  X = [john, mary],
  Y = [pat] ;
  X = [john, mary, pat],
  Y = [] ;
  fail.

Function Symbols

• You can have function symbols that represent arbitrary functions
• Example: Reasoning about Java types

  extends(employee, object).
  extends(manager, employee).
  extends(string, object).
  
  subtype1(X, Y) :- extends(X, Y).
  subtype1(array(X), array(Y)) :- subtype1(X, Y).
  
  subtype(X, Y) :- subtype1(X, Y).
  subtype(X, Y) :- subtype1(X, Z), subtype(Z, Y).

• Sample query:

  subtype(array(manager), array(object)).
  true ;
  fail.

• Prolog has no idea what array means.
• It has no idea what charles1 or manager means either
• Those are constants or 0-ary functions
• Top-level function symbols must be predicates (Boolean functions)

Prolog Jargon

• functor: a symbol with a name and a given arity (# of arguments), such as array (arity 1) or charles1 (arity 0)
• logical variable: a variable that is matched in a query, such as X
• term: expression made from functors and variables, such as fun(X, const)
• clause: an expression of the form H :- T₁, ..., T_n. (H, T_i are terms)
  • H is the head of the clause
  • If n > 0, the clause is called a rule
  • if n = 0, the clause is called a fact, and the :- is omitted
• procedure: sequence of clauses with the same top-level functor in the head
• logic program: sequence of clauses + an atom called the query
• http://www.cse.unsw.edu.au/~billw/prologdict.html

Lab

• Check into eCampus in the usual way
• Scribe puts in report
• Buddy puts in comment with scribe's name

Step 1

This lab requires SWI Prolog. Download and install for your platform (Linux, Mac OS X, WIndows). In my favorite operating system, all I had to do is type sudo apt-get install swi-prolog. Your mileage may vary.

Download the family.pl file and put it into a directory such as /home/me/cs152/lab19.

Start SWI Prolog:

1. Open a shell window
2. Change to the lab subdirectory
3. On Linux, run swipl. On Mac OS X, be sure to install X Windows first (http://developer.apple.com/darwin/runningX11.html), then open an X terminal and run xpce. On Windows, run plwin or, if all planets are aligned perfectly, double-click on a file with extension .pl.
   

In the Prolog shell, type

consult(family).

This loads the family.pl facts into Prolog. Note the period at the end of the command.

If you get a message that the file was not found, perhaps you are not in the right directory. Run the cd command, like this:

cd('/home/me/cs152/lab7/').

Note that there is no space after cd, the quotes are single quotes, and there is a period at the end of the command.

At least these were the right steps 18 months ago. In your lab report, tell me what worked for you.

Step 2

1. Issue queries to find the children of charles1 and the parents of george1. Which queries did you issue, and what was the result?
2. Define a grandparent predicate. Add it to family.pl. Reload the file again with consult. What is the rule defining your predicate? Which query yields the grandparents of sophia? The grandchildren of james1? What are the results?
3. Define a sibling predicate in the same way. What query did you use to test it?

Step 3

1. Add the following rules to family.pl:

   ancestor(X, Y) :- parent(X, Y).
   ancestor(X, Y) :- parent(X, Z), ancestor(Z, Y).

   Which query yields the ancestors of sophia? The descendants of james1? What are the results?

2. Type the command

   trace.

   (Remember the period at the end.)

   Now issue the query

   ancestor(X, sophia).

   Each time execution halts with a ? prompt, hit Enter. Each time you get another answer, type a semicolon (;) as you did previously.

   What happens?

   Turn debugging off by typing

   nodebug.

3. Change the second rule for ancestor to

   ancestor(X, Y) :- ancestor(Z, Y), parent(X, Z).

   Intuitively, this should not change the behavior of ancestor. Reload family and try out

   ancestor(X, sophia).

   Be sure to enumerate all answers.

   What happens?

   (Hit a to abort.)

4. Turn tracing on, study the behavior and explain the reason for the behavior. (I found this less tedious after commenting out all but two of the parent facts in family.pl. In prolog, a line starting with % is a comment.