CMPSC 461: Programming Language Concepts Assignment 5 Solutions

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 allocation (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