Exam 0

Statistics:

mean     93.500 (1098.000/12)
stddev   17.333
median   94.000
midrange 78.500-110.500

 #   avg
 1   6.08 / 10
 2  10    / 15
 3   9.25 / 10
 4   6.75 / 10
 5   8.08 / 10
 6   8.58 / 10
 7   6.25 / 10
 8   8.75 / 10
 9   7.25 / 10
10   5.67 / 10
11   9.83 / 15
12   5    /  5
  + 2-point bonus

Question 0-1

Give a BNF grammar describing the set of all strings of brackets for which each left bracket can be matched to a corresponding right bracket to its right. For example, the string ``[[][]]'' should be in this language, but ``][]['' and ``[[]'' would not.

Solution

Question 0-2

Assume that the following Ada program compiled successfully.

with Text_IO; use Text_IO;

procedure Test is
    I : Integer;
    J : Integer;

    procedure Y(A : Integer; B : Integer) is
    begin
        A := 5;
        B := A + J;
        I := B + I;
    end Y;
begin
    I := 3;
    J := 2;
    Y(I, J);
    Put_Line(Integer'Image(I) & " " & Integer'Image(J));
    Y(I, I); -- Note: I is passed for both parameters!
    Put_Line(Integer'Image(I));
end Test;

a. If the compiler assumed pass-by-value parameters, what would this program print?
b. What if it it assumed pass by value-result?
c. What about pass by reference?

Solution

Question 0-3

Explain an advantage of dynamic type-checking (as done by Smalltalk) relative to static type-checking (as in Java and Ada).

Solution

Question 0-4

Say you want to add a keyword instance method into Smalltalk's built-in Integer class called ``max:'', which returns the maximum value between the Integer instance to which the method is applied and the argument. For example, the code ``3 max: 5'' should return 5, while ``6 max: 2'' would return 6. Write the definition of this method to be added to the Integer class.

Solution

Question 0-5

Give and describe an example of how the Composite pattern shows up in the AWT or Swing user interface libraries of Java.

Solution

Question 0-6

Name and describe a disadvantage of using reference counting for garbage collection.

Solution

Question 0-7

Describe the process that Smalltalk goes through in looking up a method when a message is sent to an object A. (Be sure to allow for the fact that the method may have been inherited by a superclass.)

Solution

Question 0-8

Define the ``diamond problem'' with multiple inheritance.

Solution

Question 0-9

Describe a problem with multiple inheritance that Java's concept of interface avoids.

Solution

Question 0-10

Explain how the VMT works in generating compiled code for object-oriented languages.

Solution

Question 0-11

Prove the following using the axiomatic scheme below. You may justify true mathematical assertions by writing only ``mathematical fact.''

{ z = xⁱ }
z := z * x;
i := i + 1;
{ z = xⁱ }

Solution

Question 0-12

Leave this question blank. (These are free points.)

Solution