Fall 99, CSE 520: Assignment 4

Distributed: Published on the web on November 11.
Due: Nov 23 (in class).
Total maximum score: 100 points.

The purpose of this assignment is to provide experience with lambda Prolog programming

(15 pts) Assume given the database of relations "father" and "mother" specified in lambda Prolog, as in Lecture 20
1. (5 pts) Define a predicate "grand_parent" such that (grandparent X Y) is true if and only if X is a grandparent of Y.
2. (10 pts) Define a predicate "cousin" such that (cousin X Y) is true if and only if X is a cousin of Y (i.e. one of the parents of X is brother or sister of one of the parents of Y)
(35 pts) The method "merge and sort" is an efficient way of ordering a list which works recursively as follows:
- Divide the list L in two parts L1 and L2 of "almost equal" size (i.e. such that the difference in size is at most one)
- Order (sort) L1 and L2 with the method of merge and sort. Let M1 and M2 be the results.
- Merge M1 and M2 so to obtain an ordered list M
Define a predicate "merge-and-sort" such that (merge-and-sort L M) is true if and only if M is the list obtained by ordering L with the method of merge and sort.
(50 pts) Consider the type checker for the simply typed lambda calculus (in the system of Curry) explained in Lecture 21.
Extend such type checker to the language defined in Lecture 11, namely the language with terms defined by the following grammar:
```
   Term ::= Var | \Var. Term | Term Term             pure lambda terms
          | (Term,Term) | fst Term | snd Term        pairs and projections
          | inl Term | inr Term                      injections
          | case(Term, \Var.Term, \Var.Term)         case construct
```
and types defined by the following grammar:
```
      Type ::= TVar | Type -> Type | Type * Type | Type + Type
```
Defining the suitable representation in lambda Prolog of terms and types is part of the exercise.