=========================preview======================
(COMP251)COMP251_03F-final_sol.pdf
Back to COMP251 Login to download
======================================================
COMP251 2003 Fall Semester Final Exam SOLUTION

Q1.
(a)
Action-oriented. Input-output mappings are implemented indirectly by commands that change the state of the machine. Both the basic commands and data structures reflect the architecture of the current computers.

(b)
A programming style that promotes programming design by modules.

(c)
Input-output mappings are directly implemented as functions, which are first-order objects that can be freely manipulated.

(d)
Input-output mappings are implemented by relations, and problem solving is done by queries to the
program.



Q2.
(a) More than one parse trees for ababab
<S>
/ \

<S> <S>
/ \ | \

<S> <S> a b
/ \ / \
a b a b

<S>
/ \

<S> <S>
/| / \
a b <S> <S>

/| |\
a b a b

(b)
<S> ::= <S1><S> | <S1>
<S1> ::= ab | a<S>b

Q3. Static layout requires the size of the object to be known at compile time. In the case of arrays, the size of the array elements and array bounds need to be known at compile time. Since c is a local variable whose value is not known at compile time, thus the array bound is not known at the compile time, so the declaration cannot be handled by static layout.
Q4.
int *p,*q;
p = new int; q = new int;
q = p;

Q5.
fun my_rev(x) =
let fun my_rev1([],y) = y

| my_rev1(x::xs, y) = my_rev1(xs,x::y)
in my_rev1(x,[])
end;

my_rev(X,Y) :- my_rev(X,Y,[]).
my_rev([],Y,Y).
my_rev([X|Xs],Y,Z) :- my_rev(Xs,Y,[X|Z]).

Q6.
(a)
flight(hongkong,X) X=tokyo; X=beijing; X=sanfrancisco; X=vancouver; X=hongkong; X=tokyo; X=beijing; X=sanfrancisco; X=vancouver; X=hongkong; ... X=tokyo; X=beijing; X=sanfrancisco; X=vancouver; X=hongkong; ...

flight(X,vancouver).
X=tokyo; X=hongkong; X=hongkong; ...; X=hongkong; ...


(b)
path(X,a)
X = a ; X = a ; X = a ; ...


(c)
infinite loop


(d)
infinite loop
Q7.



num_p(adam,X) :- X=0.
num_p(eve,X) :- X=0.
num_p(X,Y) :- case(X), !, fail.
num_p(X,2).
case(eve).
case(adam).

Q8. For P1
roo(5,Y),2<Y r1,{_1/5,_2/Y} / r2,{_3/5,_4/Y}| \r3,{_5/5,_6/Y} 5<3,Y=0,2<Y 3=<5,5<6,Y=1,2<Y 6=<5,Y=2,2<y | | | fail 5<6,Y=1,2<Y fail | Y=1,2<Y {Y/1}| 2<1 fail
For P2
roo(5,Y),2<Y r1,{_1/5,_2/Y} / \r2,{_3/5,_4/Y} 5<3,Y=0,2<Y 3=<5,5<6,Y=1,!,2<Y | | fail 5<6,Y=1,!,2<Y | Y=1,!,2<Y {Y/1}|
!,2<1 | 2<1
fail
Q9.
(a)
foo1 = fn: 'a -> bool

(b)
foo2 = fn: int -> int -> int

(c)
foo3 = fn: int -> 'a -> int

(d)
my_last_element = fn : 'a my_list -> 'a


Q10.
datatype 'a my_tree = my_empty_tree | my_leaf of 'a | my_node of 'a * 'a my_tree list;
fun node_count my_empty_tree = 0
| node_count (my_leaf(x)) = 1
| node_count (my_node(x,[])) = 1
| node_count (my_node(y,x::xs)) = (node_count x) + node_count (my_node(y,xs));
val a = my_node(1,[my_node(2,[my_node(3,[]),my_node(4,[])]), my_node(5,[])]);
Or
datatype 'a my_tree = my_empty_tree | my_node of 'a * 'a my_tree list;
fun