=========================preview======================
(COMP3031)[2009](f)final~kmlaiab^_19600.pdf
Back to COMP3031 Login to download
======================================================
HONG KONG UNIVERSITY OF SCIENCE & TECHNOLOGY
COMP251 Principles of Programming Languages
Fall 2009

FINAL EXAMINATION
Dec 14 2009 (Mon) 8:30am-11:30am, S H Ho Sports Hall
Name: SAMPLE SOLUTION with GRADING CRITERIA Email Address
Student ID Lecture Section Lab Section

1.
About the exam:

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 8 questions, and 12 pages (Included this page) in this paper.

b.
The total marks of this paper are 100.

c.
You should answer all questions.




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.

Question 1 /10
Question 2 /18
Question 3 /12
Question 4 /12
Question 5 /10
Question 6 /12
Question 7 /11
Question 8 /15
Total: /100

Problem 1 (10 points) SML
Write a function that compares two functions on integers between 1 and 100, with 1 and 100 included. Specifically, write a function called compare (fn: (int->int)*(int->int) boolean) such that compare(f,g) returns true if for all integers 0<x<101, f(x)=g(x); and returns false otherwise.
Answer:

Solution:
fun compare2(f,g,n) = if n>99 then true else if f(n+1)-g(n+1)=0 then
compare2(f,g,n+1) else false;
fun compare(f,g) = compare2(f,g,0);

Marking scheme:

(1)
compare2(f(x),g(x)) used -3;

(2)
end missed -1;

(3)
using [1,2,3,,100] -4;

(4)
fun missed -1

(5)
Any typo -1

(6)
return used -1

(7)
wrong limit -2

(8)
ifelse dysfunction -2

(9)
same function name for different purpose -2

(10)
1 missed -1

(11)
letin missed -2

(12)
syntax error -2

(13)
true as 1, false as 0 -1

(14)
using wrong function -1

(15)
only compare2 provided -5

(16)
boundary condition not handled -2

(17)
two compare2 rather than one -2

(18)
wrong branching (if...else) -3


Problem 2 (18 points) SML and Prolog
In this question, you need to implement a function that counts the number of common elements in two given lists in both SML and Prolog.
SML: Define the function inters_count (fn: a' list * a' list int) so that inters_count(x,y) returns the number of common items in x and y. For example:
. inters_count([1,2],[2,3]);
. val it = 1;
. inters_count([1,2,2,5],[2,2,5]);
. val it = 2; (* so don't count the same items twice *)

You can use any built-in functions in SML.

Prolog: Define the following relation inters_count(X,Y,N) in Prolog: N is the n