CS 320 Final Examination Sample
Your Full Name: Student Number:
Instructions:
1. This is a closedbook 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 CSE Department policy.
Grading Box:
P1
P2
P3
TOTAL
Useful definitions and code snippets:
let rec foldlf:abbacc: bl:a list:b match l with
acc
x::xs foldl f fx,acc xs
let rec foldr f:abbacc: bl:a list:b match l with
acc
x::xs fx, foldr f acc xs
Streams :
type a str Cons of a a stream and a 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 i1
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.
P11 When writing a function in OCaml, one needs to provide explicitly the types of the functions arguments. FALSE
P12 The scope of a variable is the range of statements in which the variable is visible. TRUE
P13 Attribute grammars support typechecking. TRUE
P14 In shallow binding the referencing environment is the environment of
the definition of a function. FALSE
P15 The PassbyReference parameterpassing policy associates a formal parameter with an access path to the corresponding actual parameter. TRUE
P16 Dynamic binding associates a name reference to a variable by identifying the closest declaration in the program text. FALSE
P17 The scope of a variable can only be determined at runtime. FALSE P18 Operational semantics rules can use hypothetical reasoning to unfold a
recursive case. TRUE
P19 Static scoping rules are based on the calling sequence of program units.
FALSE
P110 In OCaml a user needs to explicitly state functions as polymorphic. FALSE
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.
P21 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
Ry 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
P22 Consider the following expressions, which of the statements below is true?
foldl fun a,c if a0 then c else a::c 4;3;2;0;1;; foldr fun a,c if a0 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
P23 Which of the statements below is true?
A: Passbyname will copy the value of the actual parameter to the formal parameter
B: In passbyvalue, the value of the formal parameter is passed to the actual parameter when the subprogram terminates
C: Passbyreference will substitute the text of the actual parameter value to the formal parameter
D: A, B, and C are all false
P24 Which of the statements below is true about the grammar?
Foo Baz Foo Bar
Bar Baz Bar Baz
Baz 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
P28 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
fooa,b,c,d
What is the value of a,b,c,d after the call if we use passbyvalue for a, passbyvalueresult for b, passbyresult for c, and passbyvalue for d? A: a2,b0,c6,d4
B: a2,b0,c0,d5
C: a2,b0,c2,d3 D: a0,b0,c6,d4 E: a0,b0,c6,d3
P25 Given the following pseudo code, what will be printed if we use dynamic scope? The notation var xk declares a new variable named x and initializes it to k
fun1
var a15; var b3;
fun2
var b9;
aba;
fun3
var cab;
printa,b,c;
bb1;b10
fun3;
aa2;
fun4var a17; fun2;
fun4;
fun1;
A: 9, 10, 19 B: 24, 10, 34 C: 15, 3, 18 D: 26 10 36
P26 Consider the language L1 and its operational semantics provided
at page 1.
Given the stack S int0; int4; int2; int3; int3;
int2 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; int1; int2
C: int3
D: error; int4
E: add error
P27 Consider the language L1 and its operational semantics given at page 1.
Consider the stack S int4;int2;int0;int4;int0;int2. When evaluate the configuration: add;div;add;divS, 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 P31 Consider the following two OCaml functions:
let mystery1 d foldr fun a,b, c if b
then a::c
else ab::c d
let rec mystery2 d
match d with
y::z::xs
if y
then ymystery2 xs
else yzmystery2 xs
2 Marks What is the type of mystery1?
mystery1 : a list a list list a list list
2 Marks What is the type of mystery2?
mystery2 : a list list a list list
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
Not equivalent, because they have different types. That is, there is an input on which one of the two programs give a result while the other give a type error.
P32 Consider the following pseudo code:
The notation var zk declares a new variable called z and sets it to k
def fun1a:
var z 1
def sub1c,e:
def sub2d:
printz
sub2z
printz
def sub3b:
var z 2
var s 1
sub1z,2
sub3z
var z 0
fun13
printz
4 Marks What value is printed for z if we use static scoping?
110
4 Marks What value is printed if we use dynamic scoping rules?
220
P33 Consider the following grammar:
expr :: expr expr
expr expr
expr
const
const :: 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:
yes
000
has the parse trees:
0 0 0000
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
eqExpr :: ltExpr eqExpr ltExpr
ltExpr :: parExpr ltExpr parExpr
parExpr :: eqExpr 0 1 2
P34 8 marks Operational Semantics Consider the following language:
And the following rules:
Suppose you know the memory is m x7, z3.
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?
FETCHR xadd2add1addz, mxadd2add1add3, m
COMPOSE
FETCHL
xadd2, m7add2, m EV AL xadd2add1, m7add2add1, m EV AL xadd2add1add3, m7add2add1add3, m
COMPOSE
729
ADD
7add2, m9, m EV AL 7add2add1, m9add1, m EV AL 7add2add1add3, m9add1add3, m
COMPOSE
9110
ADD
9add1, m10, m EV AL 9add1add3, m10add3, m
COMPOSE
10313 ADD 10add3, m13, m
P35 8 Marks Activation Records TODO Jiawen
Consider the following program
void main
void fun1float r
int s, t;
fun2s;
void fun2int x
void fun3int q
return 3 here
int y;
fun3y;
float p;
fun1p;
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.
P36 8 Marks Infinite Lists
We will define a new infinite sequence of numbers that we will call mysequence. The first three numbers in mysequence are 1, 2, 4. The nth element in mysequence is computed by adding the n3 number and the n2 number. For example, the 4th number in mysequence 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 mysequence.
mysequence: 1 2 4 3 6 7 9 13 16 22…
let rec mysequence
Cons 1,fun
Cons2, fun
Cons4,zip mysequence tail mysequence