Programming Languages: Sample Final Exam
Problem 1
Consider the following pseudocode in an imperative language:
int x = 1, n = 10;
function f () {
int x = 3;
function g (int c,d) {
c = c1;
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?
Answer: 2,3,3,10.
 B. Suppose that the language uses dynamic scoping and pass by reference.
What is printed?
Answer: 2,2,2,2,
 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 lvalues. 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.
Answer:
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 twodimensional array may be implemented as a "true" twodimensional
array or as an array of pointers to onedimensional 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 0based indexing.
For each of the two implementations, explain what steps are involved at
runtime in computing the address of the expression A[I,J]. (Ignore bounds
checking).
Answer: For a true multidimensional 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.)
Answer:
(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.)
Answer:
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;
type answer = ... end;
task type server is
entry request(q: in query; a: out answer);
entry returnAnswer(a: out answer);
end
task body server is
qy : query;
an: answer;
begin accept request(q: in query, a: out answer) do
qy = q;
an := quickAnswer(q);
end request
an := thoughtfulAnswer();
accept returnAnswer(out an: answer)
end returnAnswer;
end loop;
end server;
procedure client is
s: array (1 .. 10) of server;
m : message;
a : answer;
begin for i in 1 .. 10 loop
m := computeMessage(i);
s[i].request(m,a);
end loop
for i in 1 .. 10 loop
s[i].returnAnswer(a);
incorporateAnswer(a);
end loop
end client;
Assume that the functions "quickAnswer", "thoughtfulAnswer", "computeMessage",
and "returnAnswer" are defined elsewhere.
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.
Answer: P must precede Q.

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);
Answer: P must precede Q.

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.
Answer:

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.
Problem 6:
In Java the type "int" and the type "Integer" are quite different.
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?
Answer:
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 runtime 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 runtime 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.
The question about "coercion" was a mistake;
there is no coercion
between numeric types in Ada.
Small is a range subtype of Float.
Distance is a derived type from Float.