## Programming Languages: Sample Final Exam

Many thanks to Paul Bethe, who found a number of errors in my first set of solutions.

### 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?
Answer: Two expressions are aliases if they have the same l-values. In part B, in the call to g, c, d, and x are all aliases.
• 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.

Note: The order here is significant. The caller sets up the static and dynamic links, initializes the formal parameters, and then does a PUSHJ to push the return address onto the stack. The callee sets up its own local variables. The entities set up by the caller must precede those set up by the callee, and usually though not necessarily the return address is the topmost of the entities set up by the caller.

### 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).
Answer: For a true multi-dimensional array, the address of A[I,J]is at 1000+((I*100)+J)*50. For a ragged array, the address of A[I,J] is at (dereference(1000+I)) + J*50.

### 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.)
```(define (invert F L X)
(if (equal? (F L) X) L (invert F (+ L 1) X)))
```
• 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?
Answer: fn : (int -> 'a) * int * 'a -> int.
• 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.)
```template < typename T >
int invert(T  f(int), int L, T 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";
}
```
• D. If you make the change in part C, how does the body of "main" have to be changed to carry out the call?
Answer: Not at all. In C++, the type of template instantiations is automatically inferred.
• 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?
Answer: The question is misleading, because in Java type arguments to generics must be reference types. You would have to rewrite square as a function from Integer to Integer and then write in main "invert< Integer >".

### 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.
Answer: P and Q may proceed in parallel.
• C. P: s[2]'s computation of thoughtfulAnswer. Q: s[3]'s computation of thoughtfulAnswer.
Answer: P and Q may proceed in parallel.
• 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);
Answer: P and Q may proceed in parallel.
• F. P: s[2]'s computation of thoughtfulAnswer. Q: client's incorporation of the thoughtful answer received from s[3]; P must precede Q.
• G. P: s[3]'s computation of thoughtfulAnswer. Q: client's incorporation of the thoughtful answer received from s[2];
Answer: P and Q may proceed in parallel.

### 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.
```int[] a = new int[10];
a = new int[5];
```
In Java
```Integer I = new Integer(5);
I = new Integer(10);
```
In both cases the object created in the first line is allocated on the heap, and becomes inaccessible once the variable that references it is reassigned.
• B. In Scheme, evaluating the expression (cdr (list 1 2 3)) will generate an inaccessible object (unless the compiler carries out an optimization to avoid this, but it probably doesn't). Explain.
Answer: When the subexpression (list 1 2 3) is evaluated, the compiler allocates three pairs from the heap. The value of the cdr is a pointer to the second cell, but once that is evaluated, the first cell becomes inacessible.

• C. 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?
• D. 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?
Answer: Each object allocated from the heap has a field, inaccessible to the user, which counts the number of pointers to the object that have been created. Whenever a pointer to the object is created, the count is incremented; whenever a pointer is reassigned or deallocated, the cound is decremented. When the count reaches 0, the object is deallocated. The method fails in the case of circular pointer structures, where the count does not reach 0 even after the object or set of objects is no longer accessible from the program.
• E. Describe one advantage of each of the approaches in part C.
Answer: The disadvantage of user-based deallocation is that it is very burdensome and error-prone. It must be done at exactly the right time: If the user deallocates too soon, then remaining pointers to the object become dangling pointers. If the user waits too long to deallocate, then the objects become inacessible and the program can't find them to deallocate them.

The disadvantage of garbage collection is that, in all actual implementations, the entire run time system must halt its activities for seconds or minutes while the garbage collector runs.

### 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.
Answer: You can write "Integer I = new Integer(10);" but not "int I = new int(10)".

Another context where you can use Integer but not int is in the argument to generics, as in problem 3.E. <

• B. Explain the difference in their implementation.
Answer: An int is a simple value, a single word containing a integer bit string. If it is a local variable, it is allocated on the stack. An Integer is an object. It is always allocated on the heap. In addition to the value, the record for an Integer contains other fields for the use of the run tine system; at minimum, a pointer to the class Integer.

### Problem 7:

Consider the following fragment of Ada code:
```type Distance is new Float;
subtype Small is Float range 0.0 .. 1.0; -- erroneously written as
-- 0.0 to 1.0 in original handout.

procedure P is

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

begin for I in 1 .. 10 loop
J := I * 12;
D := D * I;
F := 0.5 * I;
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?
Answer: Actually, Ada is fussier than I realized, and there are three statements that trigger a compiler error:
D := D * I; F := 0.5 * I (which I find very strange); and E := S (the one I intended).
The statement E:=S is a type error since E is of type Distance which is a derived type from Float. It can be fixed by using a cast: E := (Distance) S;
• 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?
Answer: The statement S:=F will produce a run-time error on the third iteration of the loop since F will have the value 1.5, which is outside the declared range of type Small, the type of S. This kind of error cannot be caught at compile time, since it is not generally possible to predict what the values of variables will be.
• C. Identify each of the following in the above code: overloading, coercion, subtype, derived type.
Answer: The operator "*" is overloaded. In the statement "J := I*12" it refers to integer multiply; in the statement "F := 0.5*I" it refers to floating point multiply. I had thought that in the statement "F := 0.5*I", the integer variable I is coerced to a floating point value, but I was mistaken; there is no coercion between numeric types in Ada. Small is a range subtype of Float. Distance is a derived type from Float.