## Programming Languages: Final Exam

### Problem 1 (20 points)

Consider the following pseudo-code in an imperative language:
```int p=1;

function f(int n,q) {
if (n==0) then print(p);
else g(n,q);
}

function g(int n,p) {
p = 2*p;
f(n-1,p);
}

main () { f(2,2); }
```
Assume that the language uses pass by value.
• A. What is printed if the language is dynamically scoped? Answer: 8.
• B. What is printed if the language is statically scoped? Answer: 1. (The "p" in "print(p)" refers to the global p, which is unaffected by the calls to g.)
• C. When the print statement is executed, what activation records are on the stack? You need NOT show the contents of the activation records, just indicate what function calls they correspond to.

### Problem 2 (5 points total)

• A. (4 points). In most languages, if subprogram P calls subprogram Q, then, when the compiler compiles P, it needs to have seen the declaration of Q: the types of Q's arguments, the passing conventions used, and the type returned by Q. Give three reasons that this information is needed in order to compile P.

• 2. To do type checking.
• 3. To pass and receive the parameters in the proper way. (If Q takes an argument pass-by-value, then P must pass an r-value; if Q takes the argument pass-by-reference, then P must pass an l-value; if Q takes the argument pass-by-value-restore, then P must pass an r-value and, when Q returns, must accept an r-value.)
• B. (1 point). In one of the languages studied this semester, the statement in part (A) does not apply, and it is possible to compile P without having gotten any information about Q. Which language is that?

Answer: Scheme. In Scheme, there is no overloading; type checking is dynamic; and all parameters are pass-by-value.

### Problem 3 (15 points)

• A. What is inline expansion of a procedure?

Answer: If P calls Q and Q is expanded inline, then the text of Q is substituted inside the body of P.

• B. What is the difference between inline expansion and macros?

Answer: With inline expansion, the callee is written in the form of a procedure, and the compiler guarantees that the behavior of the code with the inline expansion is identical to calling the procedure in the usual way. There is no such constraint and no such guarantee with a macro.

• C. Name one advantage and one disadvantage of inline expansion of a procedure as compared with the usual implementation of procedure calls.

### Problem 4 (20 points)

• A. In C++ or Java, what is a constructor for a class?

Answer: A function that creates an object of that class.

• B. Frequently there are several constructors for a class. How is this possible? What constraints are there in defining multiple constructors for a class?

Answer: The constructor function can be overloaded. The arguments of each different constructor must have a different type signature, so that the overloading can be disambiguated.

• C. What is the default constructor for a class?

Answer: Actually this term can be used in either of two ways:

1. The constructor used by default (e.g. by the constructor for derived classes as in part D), which is the constructor with no arguments (if any).

2. The constructor provided by default by the compiler. In C++ or Java, if the programmer does not define any constructors, the compiler provides a constructor with no arguments which creates the object but does not initialize any fields.

• D. If F is a class and G is a derived class from F, what is the relation between the constructor for G and the constructor for F?

Answer: When the constructor for G is called, the constructor for F is called first, and then the body of the constructor for G is applied to the result.

### Problem 5 (15 points)

In Java, suppose that you have written a program that compiles and runs correctly containing the following:
• An abstract class P containing one abstract method f.
• A concrete class Q extending P which includes an concrete definition for f, or a number of such concrete classes.
You now change the program as follows: you supply f in P with a definition, you change it to a concrete method, and you change P to a concrete class. You make no other changes to the program.
• A. In executing the modified program, is the new method for f under P ever called? Explain your answer.

Answer: No. In the original program, no object of type P is ever created, since it is an abstract class, and P.f is never invoked, since it is an abstract method. Therefore, the same is true of the modified program. If an object of type Q is created and its method f is called, then Q.f will be used, since Java uses dynamic dispatching.

• B. Does the modified program run any differently from the old program? Explain your answer.

Answer: No. All objects are created in the same way in the modified program, and all functions are called in the same way.

• C. In view of your answers to (A) and (B), what is the point of allowing abstract classes in Java?

Answer: The point of defining P as an abstract class is precisely to prevent the programmer from creating objects of type P. P is, so to speak, too insubstantial a definition for objects of that type to really exist; it is just a place-holder so that one can write polymorphic functions.

### Problem 6 (20 points)

• A. In Scheme, write a function (reduce F L BASE) defined as follows:
F is a function with two arguments, L = (L1 ... L k) is a list, and BASE is a value.
(reduce F L BASE) computes the value (F L1 (F L2 ... (F Lk BASE)))
For instance, (reduce + '(2 3 5) 0) computes (+ 2 (+ 3 (+ 5 0))) = 10.
(reduce times '(2 3 5) 1) computes (times 2 (times 3 (times 5 1))) = 30.
(reduce cons '(2 3 5) '()) computes (cons 2 (cons 3 (cons 5 ()))) = (2 3 5). Answer:
```(define (reduce F L BASE)
(if (null? L)
BASE
(F (car L) (reduce F (cdr L) BASE))))
```
• B. In ML, the function reduce can be written as follows:
```fun reduce(F,[],BASE) = BASE |
reduce(F,(X::Z),BASE) = F(X,reduce(F,Z,BASE));
```
The type of reduce is fn: ('a * 'b -> 'b) * 'a list * 'b -> 'b.
Explain briefly (4 or 5 sentences) what this type means.

Answer: 'a and 'b are type parameters. In reduce(F,L,BASE), BASE is an object of type 'b; L is a list of objects of type 'a; F is a function whose arguments are one object of type 'a and one object of type 'b; and reduce is a function whose arguments are the above types and returns a value of type 'b.

• C. Suppose that we define "reduce" as in B, and then write
val r = fn(F) => reduce(F,[1,2,3],0);
What is the type of r? Answer: fn: (int * int -> int) -> int.

How can you use r to compute the sum 1+2+3+0? Answer: r(fn(X,Y) => X+Y);

• D. In C++, write a template function reduce(F,A,N,BASE) where BASE is a value of type T, A is an array of objects of type T, N is the size of A, and F is a function that takes as arguments two values of type T and returns a value of type T. Also write a main function that calls "reduce" with some particular arguments.

```
#include

using namespace std;

template

T reduce(T f(T X, T Y), T A[], int N, T BASE)
{   for (int i = N-1; i>=0; i--) BASE = f(A[i],BASE);
return(BASE);
}

int add(int X, int Y) { return(X+Y); }

int main() {
int A[3] = { 1,2,3 };

cout << "\n";
}
```

### Problem 7 (10 points)

Consider the following fragment of Ada code. There are two resources R1 and R2 to be used (e.g. two peripheral devices). For each resource R, there is a task of type "ResourceManager" that protects access to R. There are two tasks of type "Client" that may use the resources. Assume that there is elsewhere a procedure "RunResource(R)" which is the only way to use resource R. (When RunResource(R) completes, R is no longer in use.)
```type Resource is ...

entry AssignResource(R: Resource);
entry UseResource;
end ResourceManager;

MyResource : Resource;  -- The resource assigned to this task;
begin accept AssignResource(R : Resource) do
MyResource := R; end AssignResource;
loop
accept UseResource do RunResource(MyResource); end UseResource;
end loop;
end ResourceManager;

R1, R2: Resource;
RM1, RM2 : ResourceManager;

task type Client is end Client;
begin
--- Each client calls RM1.UseResourec and RM2.UseResource from time to time.
--- Each client is in itself sequential; that is, a client does not create subtasks.

end Client;

C1, C2 : Client;

procedure main is
begin RM1.AssignResource(R1);
RM2.AssignResource(R2);
end main;
```
• A. Is it possible for C1 and C2 both to be using R1 at the same time?

• B. Suppose that C1 has called RM1.UseResource and then C2 calls RM1.UseResource before the first call has returned. What happens?

Answer: C2 is suspended until C1's call has completed.

• C. Is it possible for C1 to be using R1 at the same time that C2 is using R2?