CMPSC 461: Programming Language Concepts Assignment 4 Solution
Problem 1 [15pt] Consider the following class instances in a C++ program:
1 static myClass* X; 2 int main()
3{
4 myClass* Y = new myClass();
5 foo();
6 delete X;
7 return 0;
8} 9
10 11 12 13 14
void foo() {
myClass Z;
X = new myClass();
}
a) (5pt) What is the storage allocation (static/stack/heap) for the following objects?
• object A: the pointer X
• object B: the pointer Y
• object C: the myClass object created at line 4 • object D: the myClass object created at line 12 • object E: the myClass object created at line 13
Solution:
A: static area, B: stack allocated, C: heap allocated, D: stack allocated, E: heap allocated.
b) (10pt) Consider one execution of the program above. The execution trace (a sequence of program state- ments executed at run time) of this program is
4 5 12 13 6 7
For each myClass object associated with X (the pointer), myClass created at line 13 (the object that X points to), Y and Z, as well as each pointer stored in A and B, write down their lifetimes (use a subset of execution trace, e.g., 12 13 to represent the lifetime). Assume the lifetime of a heap-allocated object starts from new and ends after delete.
Solution:
LifetimeofA:4 5 12 13 6 7 LifetimeofB:4 5 12 13 6 7 LifetimeofC:4 5 12 13 6 7 LifetimeofD:12 13 LifetimeofE:13 6
Problem 2 [21pt] Consider the following pseudo-code, with the assumption that the language has one scope for each function (including the main function), and it allows nested functions (hence, nested scopes).
1/4
main() { int g;
int x=4;
function B(int a) {
int x = a + 3; C(1);
function A(int n) { g := n;
}
function C(int m) {
print x;
x = x / 2; if (x > 1)
C(m + 1);
else
A(m); }
// body of main
B(1);
print g; }
1
2
3
4
5
6 7}
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
1.
(5pt)Drawthesymboltabletreewith4tables,onetableforeachofthe4scopes(namelymain,B,A,R) in this program. Assume each table contains two columns: name and kind (e.g, id, fun, para).
Solution:
Function main (Table
M):
Name
Kind
g
id
x
id
B
fun
A
fun
C
fun
Function B (Table B):
Function A (Table A):
Function C (Table C):
Name
Kind
a
para
x
id
Name
Kind
n
para
Name
Kind
m
para
2.
3.
4.
The hierarchy of tables is as follows:
M BAC
(3pt) What does the program print?
Solution: 422
(6pt) Draw a picture of the run-time stack when A has just been called. For each frame, show the static and dynamic links. You do not have to show the storage for any other information.
Solution:
(4pt) Refer to the run-time stack, briefly explain how function A finds variable g.
Solution: It uses the static links to locate the frame of Main. Within that frame, it finds g which is at a statically known offset.
Assignment 4 Solution, Cmpsc 461 2020 Fall 2/4
Dynamic Static links links
A
C(2)
C(1)
B
main
5. (3pt) What does the program print if the language uses dynamic scoping?
Solution: 422
Problem 3 [14pt] Consider the following pseudo-code with higher-order function support. Assume that the language has one scope for each function, and it allows nested functions (hence, nested scopes).
function A () {
int x = 5;
function C (P) {
int x = 3;
P(); }
function D () {
print x;
}
function B () {
int x = 4;
C (D); }
B (); }
a) (7pt) What would the program print if this language uses dynamic scoping and shallow binding? Justify your answer by showing the tree of symbol tables when execution reaches the display expression.
Solution:
Function A (Table A):
Name
Kind
x
id
C
fun
D
fun
B
fun
Function C (Table C):
Function B (Table B):
Name
Kind
P
para
x
id
Function D (Table D):
Name
Kind
x
id
Name
Kind
The symbol table tree when the print statement is executed: A
|
B
Assignment 4 Solution, Cmpsc 461 2020 Fall 3/4
|
C
|
D
So the program will print out the ”x” in function C, which is 3.
b) (7pt) What would the program print if this language uses dynamic scoping and deep binding? Justify your answer by showing the tree of symbol tables when execution reaches the display expression.
The symbol table tree when the reference of D is created: A
|
B
|
D
So the program will print out the ”x” in function B, which is 4.
Assignment 4 Solution, Cmpsc 461 2020 Fall 4/4