Tutorial notes for week 8

1. Type Equivalence 
Assume some hypothetical imperative language uses the following type
equivalence rules: 

  1. A type name is equivalent to itself.  
  2. Two types are equivalent if they are formed by applying the same type
constructor to equivalent types. 
		
Below are several type and variable declarations in this language: 

type intarray = array[0..9] of integer; 
     i = integer;

var a: intarray;
    b: array[0..9] of integer; 
    c: array[0..9] of integer; 
    d: array[0..9] of i; 
    e: integer; f: i;

Indicate which of these variables are equivalent under the type
equivalence rules of the hypothetical imperative language mentioned above. 

Solution: Only the following variables have equivalent types: b, c.

Indicate which of these variables are equivalent under structural
equivalence. 

The following variables have structurally equivalent types:
  - a, b, c, d; 
  - e, f.




2. Getting started with Prolog
-------------------------------

We use SWI Prolog. There are versions for all platforms, you can follow
the link on the course webpage. 


Using SWI Prolog.
-----------------
Start Prolog:
   pl

To load (or "consult") a file called file.pl use one of the following:
   ?- consult('file.pl').
   ?- consult(file).
   ?- ['file.pl'].
   ?- [file].

To define some predicates without having to first save them to file,
consult "user":
 ?- [user].
 ... type your predicates ...
 ^D

It's a good idea, however, to get in the habit of using files most of the
time, because what you type here will be lost as soon as you exit Prolog.

To exit pl use one of the following:
  ?- halt.
  ?- Ctrl-D


3. Very simple example:
-------------------

% this is the file likes.pl
% this is a comment: likes(X,Y) means X likes Y
likes(john, mary).
likes(mary, jim).
likes(emily, john).
likes(mary, ed).
likes(ed, emily).


pl
?- [likes].
like compiled, 0.00 sec, 1,076 bytes.
Yes

?- likes(john, mary).
Yes

?- likes(john,X).
X = mary 

?- likes(mary,X).
X = jim ;
X = ed ;
No

?- likes(X,Y).
X = john
Y = mary ;

X = mary
Y = jim ;

X = emily
Y = john ;

X = mary
Y = ed ;

X = ed
Y = emily ;

No


Getting help in SWI Prolog (or do other Prolog examples). 

?- help(Topic). or ?- apropos(Word).


4. Family relations.
------------------------------------

In class, we have developed lots of example predicates based on family
relationships.  The database looks like:

male(edward).
female(alice).
...

% parent(X,y) means  X is the parent of Y
parent(albert,edward).
parent(victoria,edward).
...

Assume the predicate sibling was develped in lecture.

Develop the following predicates:

% X is the gradparent of Y
grandparent(X,Y) :- parent(X,Z), parent(Z,Y).

% X is the cousin of Y
cousin(X,Y) :- parent(Z,X),parent(V,Y),sibling(Z,V), X\=Y.

% X is the second cousin of Y
second_cousin(X,Y) :- grandparent(Z,X), grandparent(V,Y),
                         sibling(Z,V).

% X is the ancestor of Y
ancestor(X,Y) :- parent(X,Y).
ancestor(X,Y) :- parent(X,Z), ancestor(Z,Y).