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.

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;

Question 0-3

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

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.

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.

Question 0-6

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

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.)

Question 0-8

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

Question 0-9

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

Question 0-10

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

Question 0-11

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

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

Question 0-12

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

Solutions

Solution 0-1

S -> [ S ] S | empty

Solution 0-2

Solution 0-3

Solution 0-4

max: other
    self > other ifTrue: [ ^ self ] ifFalse: [ ^ other ]

Solution 0-5

Swing has a JComponent class for representing items that lie within windows, such as buttons and text fields. One subclass of JComponent is JPanel, so it can lie within a window, and a JPanel is itself a container of JComponents. Thus JPanel is an example of the Composite design pattern.

Solution 0-6

Garbage collection cannot identify unused objects involved in cyclic references. For example, even if two objects have instance variables referring to each other, and no other objects reference either of these objects, then the reference counts for both objects will be 1, and neither of them will be freed.

Solution 0-7

Each object has a reference to the object representing its class. Suppose A's reference is to B. The interpreter will go to B from A and ask B whether its method dictionary contains the requested method. If not, then from B it gets the class object representing B's superclass, and it asks it whether it contains the requested method. It continues this up the hierarchy, stopping when the requested method is found (or if it exhausts the hierarchy with no success).

Solution 0-8

A class can inherit from two classes, each of which inherits from a single shared class, as in the following class declarations. 
class A { };
class B : public A { };
class C : public A { };
class D : public B, public C { };
The question of how D instances should incorporate the information defined by A is the diamond problem.

Solution 0-9

Multiple inheritance leads to the possibility of multiply inheriting an instance variable, as in the diamond problem. Approaches for resolving such multiple definitions differ. Java prohibits instance variables in interfaces, so although a class may implement multiple interfaces, this cannot lead to the same problem as encountered via multiple inheritance.

Solution 0-10

The compiler generates a VMT for each class defined by the program, and it places a pointer to the VMT in each instance of the class. In the compiler-generated code for calling a virtual method on an instance, the CPU looks into the VMT for that instance and enters the method whose address is found there.

Solution 0-11

1. z = xi implies z * x = xi + 1
 (algebraic fact)

2. { z = xi }
   { z * x = xi + 1 }
 (consequence: 1)

3. { z * x = xi + 1 }
   z := z * x;
   { z = xi + 1 }
 (assignment)

4. { z = xi }
   z := z * x;
   { z = xi + 1 }
 (sequence: 3, 4)

5. { z = xi + 1 }
   i := i + 1;
   { z = xi }
 (assignment)

6. { z = xi }
   z := z * x;
   i := i + 1;
   { z = xi }
 (sequence: 4, 5)

Solution 0-12

This space intentionally left blank.