## Programming Languages: Sample Final Exam

### Problem 1

Consider the following pseudo-code in an imperative language:
```int x = 1, n = 10;

function f () {
int x = 3;

function g (int c,d) {
c = c-1;
print(c,d,x,n);
} /* end of g */

/* body of f */
g(x,x);
} /* end of f */

function h () {
int n = 2;

f();
} /* end of h */

main()  { h(); }
```
• A. Suppose that the language uses lexical scoping and pass by value. What is printed?
• B. Suppose that the language uses dynamic scoping and pass by reference. What is printed?
• C. What is the meaning of the word "alias" and how does it relate to part A and/or B?
• D. Draw the structure of the stack of activation records at the time when g is active. Your picture should show all the important data that is kept on the stack.

### Problem 2

A two-dimensional array may be implemented as a "true" two-dimensional array or as an array of pointers to one-dimensional arrays. Suppose that
• Type "person" is defined as a record (struct) type such that each person record has 50 bytes.
• A[100,100] is an array of person records.
• A is a global variable. Its starting address is known at compile time to be 1000.
• The language uses 0-based indexing.
For each of the two implementations, explain what steps are involved at run-time in computing the address of the expression A[I,J]. (Ignore bounds checking).

### Problem 3

• A. In Scheme, write a recursive function (invert F L X) which takes a function F, an integer L, and a value X and looks for the smallest integer N>=L such that (F N) = X. If there is no such integer N, then invert goes into a infinite loop (or exhausts the stack, depending on the implementation). For example
(invert list 0 '(2)) should return 2.
(invert (lambda (W) (> W 5)) 0 #t) should return 6.
(invert (lambda (W) (* W W)) 0 25) should return 5.
(invert (lambda (W) (* W W)) 0 2) should go into an infinite loop.
(Hint: Unlike more typical examples of integer recursion, "invert" should recur to a larger value of L.)
• B. The invert function can be written in ML as follows:
fun invert(F,L,X) = if F(L)=X then L else invert(F,L+1,X);
What is the type signature of invert?
• C. The invert function, and a call to invert, can be written in C++ as follows:
```int invert(int f(int), int L, int X) {
for (int i=L; true; i++)
if (f(i)==X) return(i);
}

int square (int X) { return X*X; }

int main() {
cout << invert(square,0,25) << "\n";
}
```
Rewrite "invert" so that X can be of an arbitrary type T and f is a function that takes an argument of type int and returns a value of type T. (You may assume that == is defined for T.)
• D. If you make the change in part C, how does the body of "main" have to be changed to carry out the call?
• E. Suppose you were to rewrite your answer to part C in Java. (DO NOT DO THIS.) What would be the answer to part D?

### Problem 4

Consider the following Ada code framework. There is one client and ten servers. The client computes a series of ten questions and asks one question to each server. The server first returns a quick answer (perhaps just an acknowledgement) and then thinks at greater length and returns a more thoughtful answer.
```
type query = ... end;

entry request(q: in query; a: out answer);
end

qy : query;
begin accept request(q: in query, a: out answer) do
qy = q;
end request
end loop;
end server;

procedure client is
s: array (1 .. 10) of server;
m : message;
begin for i in 1 .. 10 loop
m := computeMessage(i);
s[i].request(m,a);
end loop
for i in 1 .. 10 loop
end loop
end client;
```

For each of the following pairs of activity P,Q state whether P must occur before Q, Q must occur before P, or P and Q can proceed in parallel:

• A. P: s[2]'s computation of quickAnswer. Q: s[3]'s computation of quickAnswer.
• B. P: s[2]'s computation of thoughtfulAnswer. Q: s[3]'s computation of quickAnswer.
• C. P: s[2]'s computation of thoughtfulAnswer. Q: s[3]'s computation of thoughtfulAnswer.
• D. P: s[2]'s computation of quickAnswer. Q: client's calculation of computeMessage(3);
• E. P: s[2]'s computation of thoughtfulAnswer. Q: client's calculation of computeMessage(3);
• F. P: s[2]'s computation of thoughtfulAnswer. Q: client's incorporation of the thoughtful answer received from s[3];
• G. P: s[3]'s computation of thoughtfulAnswer. Q: client's incorporation of the thoughtful answer received from s[2];

### Problem 5

If an object has been allocated on the heap but is no longer accessible then its space should be reclaimed as free space on the heap.
• A. In C++ or Java give an example of a small piece of code that creates an object on the heap and then makes the object inaccessible. Your example should be extremely small; two lines of code will suffice.
• B. In some languages reclamation is the responsibility of the programmer. In others such as Java and Scheme it is done automatically by the run time system. What is the technical term for the latter approach?
• C. One method for automatic reclamation is to use reference counts . Describe briefly how this works (at most 4 or 5 sentences). Under what circumstances does it not work?
• D. Describe briefly the standard method for automatic reclamation i that avoids the problem in part (C). What is the major disadvantage of this approach?

### Problem 6:

In Java the type "int" and the type "Integer" are quite different.
• A. Give an example of a context in which you can use one but not the other.
• B. Explain the difference in their implementation.

### Problem 7:

Consider the following fragment of Ada code:
```type Distance is new Float;
subtype Small is Float range 0.0 .. 1.0;

procedure P is

F: Float;
E : Distance;
S : Small;
J: Integer;

begin F := 0.0;
for I in 1 .. 10 loop
J := I + 12;
F := F + 0.5;
S := F;
E := S;
end loop;
end P;
```
• A. One of the assignment statements above will trigger a compiler error. How can you fix this, while achieving the intended purpose? What is the name of the technique you used?
• B. One of the statements will trigger a run-time error. Which one? Why is it not possible, in general, to catch this kind of error at compile time?
• C. Identify each of the following in the above code: overloading, coercion, subtype, derived type.