CS 320 Final ExaminationSample
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:bmatch l with
acc
x::xsfoldl f fx,acc xs
let rec foldr f:abbacc: bl:a list:bmatch l with
acc
x::xsfx, foldr f acc xs
Streams :
type a strCons of aa stream and a streamunita str
let head s :a stream : amatch s with
Cons hd,tlhd
let tail s :a stream : a streammatch s with
Cons hd,tltl
let rec nats i: int : int streamfun Cons i, nats i1
let rec map f: ab s:a stream : b streamfun Cons f head s, map f tail s
let rec ones : int streamfun 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 questiononly one answer count, more than one answer will give 0 points.
P21 What is the type of function interpret?
type valueR of floatI of intS of string
let rec interpret mix l1 l2
match mix with
l1, l2
x::xs
match x with
Ryinterpret xs y::l1 l2
interpret xs l1 x::l2
A: value listfloat listvalue listValue listfloat list B: value listvalue listfloat listValue listfloat list C: value listfloat listvalue listfloat listvalue list D: value listvalue listfloat listfloat listvalue list E: value listvalue listfloat listfloat listvalue list
F: value listvalue listfloat listfloat listvalue list
P22 Consider the following expressions, which of the statements below is true?
foldl fun a,cif a0 then c else a::c4;3;2;0;1;; foldr fun a,cif a0 then c else a::c1;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 listint 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?
FooBazFooBar
BarBazBarBaz
BazABC
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:
a0; b2; c1; d3;
fun foo first, second, third, fourth:
firstfirst2
secondsecond0
fourthfourth1
thirdfirstfourth
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 Sint0; int4; int2; int3; int3;
int2 and the configuration Cadd; 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 Sint4;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 dfoldr fun a,b, cif b
then a::c
else ab::cd
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 lista list lista list list
2 Marks What is the type of mystery2?
mystery2 : a list lista 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 z1
def sub1c,e:
def sub2d:
printz
sub2z
printz
def sub3b:
var z2
var s1
sub1z,2
sub3z
var z0
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 :: exprexpr
exprexpr
expr
const
const :: 012
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:: ltExpreqExprltExpr
ltExpr:: parExprltExprparExpr
parExpr :: eqExpr012
P34 8 marks Operational Semantics Consider the following language:
And the following rules:
Suppose you know the memory is mx7, z3.
Show all the steps and the corresponding derivation that you obtain by using the rules above starting fromx 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 TODOJiawen
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 21, or 3. The 5th would be 42, 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,zipmysequence tail mysequence
Reviews
There are no reviews yet.