CMPSC 461: Programming Language Concepts Midterm 2 Solution
Names, Scopes and Bindings
Problem 1 [9pt] Consider the following class instances in a C++ program:
foo();
What is the storage allocation (static/stack/heap) for the following objects? • object A: the myClass object created at line 1.
• object B: the pointer Y created at line 6.
• object C: the myClass object created at line 6.
Solution:
A: static area, B: stack allocated, C: heap allocated.
Problem 2 [30pt] Consider the following pseudo code.
int x=1; // global voidA(){
int x=2; B();
voidB(){ print x;
if (x>1) {
x = x-1;
B(); }
return; }
void main() { A();
}
1. (12pt) Draw 4 symbol tables, one for each of the 4 scopes (namely global, A, B, main) in this program. Assume each table contains two columns: name and kind (e.g, id, fun, para).
static myClass X; int main() {
1
2
3
4}
5 void foo() {
6 myClass* Y = new myClass(); 7}
6 7 8 9
10
11
12
13
14
15
16
1
2
3
4 5}
1/6
Solution: Function f:
Name
Kind
x
id
A
fun
B
fun
main
fun
Function A :
Function B: Function main:
Name
Kind
x
id
Name
Kind
Name
Kind
2. (5pt) What does this program print if the language uses static scoping? Solution:
The program prints 1.
3. (5pt) What does this program print if the language uses dynamic scoping?
Solution:
The program prints 2, 1.
4. (8pt) Assume dynamic scoping. Draw a picture of the run-time stack right before the first execution of the return statement at line 12. Clearly label each activation record (i.e., stack frame) with the corresponding function name. For each activation record, you only need to show both static and dynamic links.
Solution:
Dynamic Static links links
B
B
A
main
Midterm 2, Cmpsc 461 2020 Fall
Functions and Procedures
Problem 3 [12pt] Alice is new to programming. She finds that the following implementation of computing the power of x on the left consumes more memory and time than the loop-based implementation shown on the right.
int pow(int x, int n) {
if (n==1) return x;
else return x*pow(x,n-1);}
int pow(int x, int n) { int ret = x;
while (true) {
if (n==1) return ret;
else {ret=ret*x; n=n-1;}}}
1. (3pt) In one sentence, explain why the loop-based implementation consumes less memory.
Solution:
No activation record (frame) is needed for the loop-based implementation.
2. (3pt) In one sentence, explain why the loop-based implementation takes less time.
Solution:
No calling sequence (e.g., saving/restoring registers, maintaining static/dynamic links) is needed for loop-based implementation.
3. (6pt) Write down an equivalent tail-recursive function for the code above (you can define a helper function if needed).
Solution:
int pow(int x, int n) { return pow_help(x,n,x);
}
int pow_help(int x, int n, int ret) {
if (n==1) return ret;
else return pow_help(x, n-1, ret*x); }
Midterm 2, Cmpsc 461
2020 Fall
Problem 4 [24pt]
int p = 3;
int q = 5;
int f (int b, int c) {
b = 2 * c; c = 1 + p; return b+c;
}
print f(p,q);
print p;
print q;
Consider a programming language using static scoping and the program on the left. Write down the expected outputs for each of the following parameter-passing methods. For each answer, briefly explain how did you derive it.
1. (6pt) call-by-value Solution: 14, 3, 5
2. (6pt) call-by-reference Solution: 21, 10, 11
3. (6pt) call-by-value-return Solution: 14, 10, 4
4. (6pt) call-by-name Solution: 21, 10, 11
Midterm 2, Cmpsc 461
2020 Fall
Types
Problem 5 [20pt] Consider a simply typed λ-calculus and the typing rules from Lecture 3. (The
rules are copied below for your reference)
terms e::= n|true|false|x|e1 e2 |λx:τ .e|e1