Programming Project 5

Due date: Thu 4/17 11:00 pm

# Introduction

This assignment has two parts. In the first part we use higher order functions in ML. In the second part you will write simple functions in Prolog.

# Higher Order Functions in ML

In this part we use higher order functions to implement some matrix operations in ML. We represent a matrix as a list of integer lists. Here are three ML values and the matrices they represent. Notice that the number of rows and columns need not be the same.
val A = [[1,2,3],[3,4,5],[3,1,1]];
val B = [[1,2,3,5],[5,3,4,5],[5,3,1,1],[5,3,1,1]];
val C = [[1,2,3,5],[5,3,4,5],[5,3,1,1]];

A corresponds to        B corresponds to       C corresponds to
[ 1 2 3 ]               [ 1 2 3 5 ]             [ 1 2 3 5 ]
[ 3 4 5 ]               [ 5 3 4 5 ]             [ 5 3 4 5 ]
[ 3 1 1 ]               [ 5 3 1 1 ]             [ 5 3 1 1 ]
[ 5 3 1 1 ]
1. Write a function transpose: 'a list list -> 'a list list whose input is a matrix and whose output is the transpose of the matrix where columns of the original matrix become the rows of the output matrix. For example transpose(A) returns [[1,3,3],[2,4,1],[3,5,1]].

You may use any number of helper functions in this part. You must use some higher order functions (such as map or foldl or your own functions) in the implementation. Code using direct iteration without higher order functions will not obtain full credit.

2. Recall that when calculating a matrix product M1 x M2 each element of the resulting matrix is a dot product of a row in M1 with a column in M2 where a dot product is a sum of products of the corresponding elements. For example if we are calculating A x A then the element in the second column of the first row in the result is equal to the dot product of [1,2,3] and [2,4,1] and therefore has the value . Similarly the entry is equal to the dot product of the 'th row of M1 and 'th column of M2. For example
A x A is equal to             A x C is equal to
[ 16 13 16 ]                 [ 26 17 14 18]
[ 30 27 34 ]                 [ 48 33 30 40]
[ 9  11 15 ]                 [ 13 12 14 21]

Write a function MM : int list list * int list list -> int list list that calculates matrix multiplication.

You may use any number of helper functions in this part. You must use some higher order functions (such as map or foldl or your own functions) in the implementation. Code using direct iteration without higher order functions will not obtain full credit.

• To start Prolog type: pl at the unix prompt. This will get you to the Prolog prompt.
• To load the contents of a file named myfile.pl use [myfile] at the Prolog prompt. After that you can start typing in queries. Remember that every query must end with a fullstop.
• If the query is a Yes/No query you will get the answer and get back to the prompt.
• If the query requests an answer binding (that is, it has a variable for which bindings are sought) then you may get the answer No or you may get a binding as an answer. If you then press [Enter] you will get back to the prompt. To get additional answers press ; (a semicolon).
• Note that you have a history mechanism just like in the unix shell. Press up-arrow to get previous commands and then edit them.
• To start tracing use trace. This will trace the next query that you ask. Pressing [space] will take the run one step at a time.
• If the system appears stuck or in a funny state CTRL-C will normally rescue you; if followed by a (for abort) you will return to the Prolog prompt.
• To exit the Prolog system use CTRL-D or halt.

# Prolog Code

1. Use the file db1.pl (from class examples) and write queries to extract information from the database as follows. (NB use the database predicates only -- do not use the rules in db1-rules.pl.) Write expressions for queries that:
• Check whether eric is enrolled in comp1b.
• Find a student who is enrolled for comp2b (if one exists).
• Check whether justin and janet are classmates.
• Find a course which is taken by daniel and which has a prerequisite (if one exists).
• Find three different courses which daniel is taking (if they exist). Note: here a single answer to the query must have the list of three courses as output. These courses must be distinct.

2. Write one or more rules defining the predicate hereOnTue(Student). The predicate identifies students who are taking classes on Tuesdays. Your programs should work for db1.pl and any other database in the same format (note the lower case encoding of Tuesday in db1.pl).

3. Write one or more rules defining the predicate everyday(Student). The predicate identifies students who are taking classes on Mondays, Tuesdays, Wednesdays, and Thursdays. Your programs should work for db1.pl and any other database in the same format.

4. Write one or more rules defining the predicate deep(Course). The predicate identifies courses that require a sequence of at least two courses to be taken before them. In db1.pl the only course that satisfies this predicate is comp3b.

5. For this part please refer to the code for binary search trees in usingterms.pl. Write one or more rules defining the predicate range(Tree,Value). The predicate is true when value is the difference between the maximum value in the tree and the minimum value in the tree. For the example tree in the file this value is .

You may want to first write rules calculating the minimum and maximum of the tree and then write a rule to calculate the range.

# Files

The Prolog files are available through the class examples section of the course web page.

Your code for the ML section should be in a file pp5.sml, the code for the Prolog section in pp5.pl.

Assuming your files are in the current directory on one of our Sun workstations or servers, you should submit by typing
provide comp80 pp5 pp5.pl pp5.sml