[SOLVED] R C ocaml CS 320 Final Examination Sample

CS 320 Final Examination Sample
Your Full Name: _________________ Student Number: _____________________
Instructions:
1. This is a closed-book test. Switch off all electronic devices.
2. Answer ALL questions in the space provide after each question.
3. There are questions that are derived from practice questions but they are different, read carefully!
Note: Penalty for violation of academic integrity is an F grade on the course, as per CS Department policy.
Grading Box:
P1
P2
P3
TOTAL

Useful definitions and code snippets:
let rec foldl(f:a*b->b)(acc: b)(l:a list):b = match l with
| [] -> acc
| x::xs -> foldl f (f(x,acc)) xs
let rec foldr (f:a*b->b)(acc: b)(l:a list):b = match l with
| [] -> acc
| x::xs -> f(x, (foldr f acc xs))
Streams :
type a str = Cons of a * (a stream)
anda stream = unit -> a str
let head (s :a stream) : a =
match s() with
Cons (hd,tl) -> hd
let tail (s :a stream) : a stream =
match s() with
Cons (hd,tl) -> tl
let rec nats (i: int) : int stream = fun () -> Cons (i, nats (i+1))
let rec map (f: a -> b) (s:a stream) : b stream =
fun () -> Cons (f (head s), map f (tail s))
let rec ones : int stream = fun () -> Cons (1, ones)
let rec zip f s1 s2 () = Cons (f (head s1) (head s2), zip f (tail s1) (tail s2))
Language L1:

Rules :

Part One (P1) True and False [20 Marks, each worth 2] Please indicate if the statement is either True or False.
P1-1 When writing a function in OCaml, one needs to provide explicitly the types of the functions arguments.
P1-2 The scope of a variable is the range of statements in which the variable is visible.
P1-3 Attribute grammars support type-checking.
P1-4 In shallow binding the referencing environment is the environment of
the definition of a function.
P1-5 The Pass-by-Reference parameter-passing policy associates a formal parameter with an access path to the corresponding actual parameter.
P1-6 Dynamic binding associates a name reference to a variable by identifying the closest declaration in the program text.
P1-7 The scope of a variable can only be determined at runtime.
P1-8 Operational semantics rules can use hypothetical reasoning to unfold a
recursive case.
P1-9 Static scoping rules are based on the calling sequence of program units. P1-10 In OCaml a user needs to explicitly state functions as polymorphic.

Part Two (P2) Single Choice [32 Marks, each worth 4]
Circle the letter that answers the question only one answer count, more than one answer will give 0 points.
P2-1 What is the type of function interpret?
type value = R of float | I of int | S of string
let rec interpret mix l1 l2 =
match mix with
| [] -> (l1, l2)
| x::xs ->
(match x with
| _
| R(y) -> interpret xs (y::l1) l2
-> interpret xs l1 (x::l2))
A: value list -> float list -> value list -> Value list * float list B: value list -> value list -> float list -> Value list * float list C: value list -> float list -> value list -> float list * value list D: (value list * value list * float list) -> float list * value list E: (value list * value list * float list) -> float list -> value list
F: value list -> value list -> float list -> float list -> value list
P2-2 Consider the following expressions, which of the statements below is true?
foldl (fun (a,c) -> if a=0 then c else a::c) [] [4;3;2;0;1];; foldr (fun (a,c) -> if a=0 then c else a::c) [] [1;0;2;3;4];;
A: They have different type
B: They evaluate to the same value
C: They are the same expression
D: They have both type int list -> int E: A, B, C and D are all false

P2-3 Which of the statements below is true?
A: Pass-by-name will copy the value of the actual parameter to the formal parameter
B: In pass-by-value, the value of the formal parameter is passed to the actual parameter when the subprogram terminates
C: Pass-by-reference will substitute the text of the actual parameter value to the formal parameter
D: A, B, and C are all false
P2-4 Which of the statements below is true about the grammar?
-> | +
-> |
-> A | B | C
A: ambiguous, left recursive
B: ambiguous, left and right recursive
C: unambiguous, left recursive
D: unambiguous, left and right recursive
E: A,B,CandDareallfalse
P2-8 Consider the following pseudo code:
a = 0; b = 2; c = 1; d = 3;
fun foo (first, second, third, fourth):
first = first + 2
second = second * 0
fourth = fourth + 1
third = first + fourth
foo(a,b,c,d)
What is the value of a,b,c,d after the call if we use pass-by-value for a, pass-by-value-result for b, pass-by-result for c, and pass-by-value for d? A: a=2,b=0,c=6,d=4
B: a=2,b=0,c=0,d=5
C: a=2,b=0,c=2,d=3 D: a=0,b=0,c=6,d=4 E: a=0,b=0,c=6,d=3

P2-5 Given the following pseudo code, what will be printed if we use dynamic scope? (The notation var x=k declares a new variable named x and initializes it to k)
fun1(){
var a=15; var b=3;
fun2(){
var b=9;
a=b+a;
fun3(){
var c=a+b;
print(a,b,c);
}
b=b+1;b=10
fun3(); }
a=a-2;
fun4(){var a=17; fun2();}
fun4();
} fun1();
A: 9, 10, 19 B: 24, 10, 34 C: 15, 3, 18 D: 26 10 36

P2-6 Consider the language L1 and its operational semantics provided
at page 1.
Given the stack S = [int(0); int(4); int(2); int(3); int(3);
int(2)] and the configuration C = (add; div; add; add; div; add /S).
Which one is the correct final configuration that C can be reduced to?
A: (/S)
B: (/ [error; int(1); int(2)])
C: (/ [int(3)])
D: (/ [error; int(4)])
P2-7 Consider the language L1 and its operational semantics given at page 1.
Consider the stack S = [int(4);int(2);int(0);int(4);int(0);int(2)]. When evaluate the configuration: (add;div;add;div/S), which rule should be applied at the second step without counting applications of the rule COMPOSE?
A: ADD
B: ADDERROR1
C: DIV0
D: DIVERROR2
E: DIVERROR3

Part 3 Short Answer [48 Marks, each worth 8] P3-1 Consider the following two OCaml functions:
let mystery1 d = foldr (fun ((a,b), c) -> if b = []
then a::c
else (a@b)::c) [] d
let rec mystery2 d =
match d with
| y::(z::xs) ->
if y = []
then [y]@(mystery2 xs)
else [y@z]@(mystery2 xs)
| _ -> []
[2 Marks] What is the type of mystery1?
[2 Marks] What is the type of mystery2?
[4 Marks] Are mystery1 and mystery2 equivalent where by equivalent we mean if provided with the same input they produce the same output? Please, explain.
[Hint: think about what the OCaml interpreter would do when you give to mystery1 and mystery2 the same input]

P3-2 Consider the following pseudo code:
(The notation var z=k declares a new variable called z and sets it to k)
def fun1(a):
var z = 1
def sub1(c,e):
def sub2(d):
print(z)
sub2(z)
print(z)
def sub3(b):
var z = 2
var s = 1
sub1(z,2)
sub3(z)
var z = 0
fun1(3)
print(z)
[4 Marks] What value is printed for z if we use static scoping?
[4 Marks] What value is printed if we use dynamic scoping rules?

P3-3 Consider the following grammar:
::= =
| <
| ( )
|
::= 0 | 1 | 2
[3 Marks] Is the grammar is ambiguous? If so, prove that the grammar is ambiguous. If not provide a short explanation why. (hint: parse trees):
[5 Marks] Write a new grammar such that:
Exactly the same strings are accepted as the grammar above. The grammar is not ambiguous.
< has higher precedence then =P3-4 [8 marks] Operational Semantics Consider the following language: And the following rules: Suppose you know the memory is m = {x=7, z=3}.Show all the steps and the corresponding derivation that you obtain by using the rules above starting from < ((x add 2) add 1) add z, m>?

P3-5 [8 Marks] Activation Records
Consider the following program
void main() {
void fun1(float r){
int s, t;
fun2(s); }
void fun2(int x){
void fun3(int q){
return 3 //here }
int y;
fun3(y); }
float p;
fun1(p); }
Draw all the activation record instances active when the instruction at the line with the comment //here is being executed. (The information in the activation record consist in: return address, dynamic link, parameters and local variables).

P3-6 [8 Marks] Infinite Lists
We will define a new infinite sequence of numbers that we will call my_sequence. The first three numbers in my_sequence are 1, 2, 4. The nth element in my_sequence is computed by adding the n-3 number and the n-2 number. For example, the 4th number in my_sequence would be 2 + 1, or 3. The 5th would be 4 + 2, or 6. Given the helper functions in page 2, create an infinite list that corresponds to my_sequence.
my_sequence: 1 2 4 3 6 7 9 13 16 22