=========================preview======================
(COMP251)5575f9 - 08finalsol.pdf
Back to COMP251 Login to download
======================================================
HONG KONG UNIVERSITY OF SCIENCE & TECHNOLOGY

COMP251 Principles of Programming Languages

Fall 2008





FINAL EXAMINATION

Dec 13 2008 (Sat) 12:30-15:30pm LTA



Name:


Email Address

Student ID


Lecture Section Lab Section







1. About the exam:

a. This is a closed-book, closed-note examination.

b. You CANNOT use any electronic device (e.g. calculator) during the examination. Please TURN OFF all of your electronic devices (e.g. mobile phone) and put them in your bag.

c. You cannot leave during the last 15 minutes of the examination.


2. How to answer:

a. You can ONLY use ball pen with black or blue ink to write your answers. You should put your answers in separate ANSWER SHEETS.

b. Rough work can be done in the question paper. Any answer in the question paper will NOT be graded.


3. About this paper:

a. There are 12 questions, and 11 pages (Included this page) in this paper.

b. The total marks of this paper are 100.

c. You should answer all questions.



Functional Programming.


1. (10 pts) Define a queue (FIFO) data type in SML, assuming that all items in a queue have same type. For your queue, define the following 5 functions on queues:

1. qempty(y) -- returns true if y is the empty queue, false if not;

2. enqueue(x, y) C insert item x into the end of queue y, and return the resulting queue;

3. dequeue(y) C remove the first item of the queue y, and return the resulting queue; raise exception EmptyQueue if y is empty;

4. qfirst(y) C return the first item of the queue y; raise exception EmptyQueue if y is empty;

5. qsize(y) -- returns the number of items in the queue y.



Recall that a queue is FIFO. Thus for example, if a is the empty queue and x and y are items of the same type, then qfirst(enqueue(x,enqueue(y,a))) should return y, and dequeue(enqueue(x,enqueue(y,a))) = enqueue(x,a).

For this question, we can use any of the SML built-in functions.


exception EmptyQ;

datatype 'a queue = queue of 'a list;

val emptyqueue = queue [];
(* definitions of the five functions *)

fun qempty(y) = y = emptyqueue;
or
fun qempty(queue y) = y = nil;

fun qenqueue(x, queue y) = queue (y@[x]);

fun qdequeue(queue nil) = raise EmptyQ
| qdequeue(queue (h::t)) = queue t;

fun qsize(queue y) = length y;

fun qfirst(queue nil) = raise EmptyQ
| qfirst (queue (h::t)) = h;

















2. (6 pts) What is the type of the function g defined below? (You may put down intermediate steps under Derivation. Partial credits may be given to partially correct derivation if your answer is wrong.)

datatype 'a tree = empty | node of 'a * 'a tree * 'a tree;

fun g f (node(_,x,y)) = f (node(2.0, empty, empty))
| g f empty = 0;


Answer: (real tree -> in