CMPSC 461: Programming Language Concepts Assignment 5 Solution
Problem 1 [9pt] Consider the following C program:
int SumOfSquares(int n) { if (n <= 0)
return 0; else
return n*n+SumOfSquares(n-1); }
a) (5pt) Write down a tail recursive implementation of function SumOfSquares in C language. You can use helper function in your solution.
Solution:
int SumOfSquares(int n) {
return SumOfSquaresHelp(0, n);
}
int SumOfSquaresHelp(int a, int n) { if (n <= 0)
return a; else
return SumOfSquaresHelp(a+n*n, n-1); }
b) (4pt) An ¡°optimizing¡± compiler will often be able to generate efficient code for recursive functions when they are tail-recursive. Refer to activation record, briefly explain how a compiler may ¡°reuse¡± the same activation record for your solution in a).
Solution: Before the recursive function call, the compiler can reuse the memory space that stores the caller¡¯s parameters for the parameters passed to the callee. Then, the control flow can be switched to the callee without the calling sequences.
Problem 2 [6pt] In early implementations of Fortran language, a compiler may choose to use static al- location (i.e., allocation in the static area) for local variables and parameters, effectively arranging for the variables of different invocations to share the same locations, and thereby avoiding any run-time overhead for creation and destruction of stack frames. However, such an implementation changes the meaning of recursive function calls.
Write down a simple example and explain how its meaning changes under the ¡°Fortran¡± semantics as stated above, compared with standard semantics found in language like C, Python, Java.
Solution:Consider the int fact (int n) function in Lecture 22. When the input is 2, the recursive call fact(1) will change the value of n in both the caller (fact with input 2) and callee (fact with input 1) to 1 since they share the same memory. Hence, while fact(1) still returns 1, the caller (fact with input 2) will return 1 ¡Á 1 due to the updated value of n.
Problem 3 [6pt] Suppose as a language designer, you plan to implement a feature called ¡°output-only¡± parameters. The expected semantics is that all output-only parameters are uninitialized when the callee starts execution; they can be used (both read and write) as other kinds of parameters within the callee;
1/3
finally, the corresponding actual parameter in the caller is updated to the final values of the ¡°output-only¡± parameters. Briefly describe one possible implementation of such ¡°output-only¡± parameters.
Solution:It can be implemented as a variant of call-by-value-return. The only difference is that the actual pa- rameters are not copied to the stack frame before the callee starts. In programming languages, this parameter passing mode is known as call-by-return.
Problem 4 [16pt] Consider the following C-like program. Write down what will be printed out when the parameters are passed (1) by value, (2) by reference, (3) by value return and (4) by name. For each answer, briefly explain how did you derive it. Answers without a brief explanation will receive ZERO points.
int x=5, y=6;
void foo(int a, int b) { x = a+b;
b = a+a;
}
main () {
foo(x,y);
print x, y; }
Solution:This program prints 11,6 (call by value)
11,22 (call by reference) 5,10 (call by value return) 11, 22 (call by name).
Problem 5 [13pt] Consider the following code snippet with exceptions. Note that the main function calls foo in the nested try block.
void foo () { try {
throw new Exception1();
print ("A");
throw new Exception2();
print ("B");
}
catch(Exception1 e1) {
print "handler1";
}
print ("C");
throw new Exception2();
}
void main () { try {
try { foo();
print ("D");
}
catch(Exception1 e1) { print "handler2"; }
Assignment 5 Solution, Cmpsc 461 2020 Fall 2/3
}
catch(Exception2 e2) { print "handler3"; }
}
a) (6pt) Write down what will be printed out by the program and briefly justify your answer.
Solution:It will print out: handler 1
C
handler 3
b) (7pt) Instead of the ¡°replacement¡± semantics of exception handling used in modern languages (i.e., the semantics introduced in lecture), a very early design of exception handling introduced in the PL/I lan- guage uses a ¡°binding¡± semantics. In particular, the design dynamically tracks a sequence of ¡°catch¡± blocks that are currently active; a catch block is active whenever the corresponding try block is active. Moreover, whenever an exception is thrown, the sequence of active ¡°catch¡± blocks will be traversed (in a first-in-last-out manner) to find a matching handler. Furthermore, execution will resume at the statement following the one that throws exception, rather than the next statement after the matching ¡°catch¡± block as we have seen in the ¡°replacement¡± semantics.
Write down what will be printed out by the program if the language uses the ¡°binding¡± semantics, and briefly justify your answer.
Solution:It will print out: handler1
A
handler3
B
C handler3 D
Assignment 5 Solution, Cmpsc 461
2020 Fall 3/3