1



Name

CISC 3150 – Object-Oriented Programming

Fall 2011

Midterm Exam

Solutions

You must answer questions 1, 2, and 6 (30 points). Answer 30 (out of 45) points worth of additional questions for a total of 60 points.

Please do not answer more than 30 points worth of additional questions. Please circle below those questions you wish me to mark. If you don’t I will simply count the first 30 points of questions I get to.

3 4a 4bi 4bii 4c 5a 5b 7a 7b

Part 1. Use the following Babytalk image for the questions in this part. (The top-level invocations will be supplied in the various questions.)

class Number {

method value { }

method print { }

}

class Character {

method val { }

method print { }

}

class Expression {

var operand1 : Number

var operand2 : Number

var operator : Character

method getOperand1 { invoke operand1 value }

method getOperand2 { invoke operand2 value }

method getOperator { invoke operand2 operator value }

method print {

invoke operand1 print

invoke operator print

invoke operand2 print

}

}

var c : Character

var n : Number

var n2 : Number

var e : Expression

1. Draw the Phase 2 tables for the above image (10 points – you must answer this question)

2. Trace the interpreter on each of the following top-level message invocation (i.e. resolve the receiver and method name). (10 points – you must answer this question)

a. invoke e getOperand1

1. Look up the variable name e in the global variable table, obtaining the corresponding Var object

2. Retrieve the class name (Expression) of e from the Var object

3. Look up the class name Expression in the global class table obtaining the corresponding Class object

4. Obtain the Method object corresponding to the method name getOperand1 from the Class object obtained in step 3

5. All relevant information (variable, class and method) information has been retrieved. Print the appropriate invocation line.

6. Begin interpretation of getOperand1 method

7. Look up variable name operand1 in the variable table of the Expression Class object, obtaining the corresponding Var object.

8. Retrieve the class name (Number) of operand1 from the Var object

9. Look up the class name Number in the global class table obtaining the corresponding Class object

10. Obtain the Method object corresponding to the method name value from the Class object obtained in step 9

11. All relevant information (variable, class and method) information has been retrieved. Print the appropriate invocation line.

12. value method is empty, return up the chain of invocations

b. invoke e getOperator

1. Look up the variable name e in the global variable table, obtaining the corresponding Var object

2. Retrieve the class name (Expression) of e from the Var object

3. Look up the class name Expression in the global class table obtaining the corresponding Class object

4. Obtain the Method object corresponding to the method name getOperator from the Class object obtained in step 3

5. All relevant information (variable, class and method) information has been retrieved. Print the appropriate invocation line.

6. Begin interpretation of getOperator method

7. Look up variable name operator in the variable table of the Expression Class object, obtaining the corresponding Var object.

8. Retrieve the class name (Character) of operator from the Var object

9. Look up the class name Character in the global class table obtaining the corresponding Class object

10. Attempting to obtain the Method object corresponding to the method name value from the Class object obtained in step 9 results in a BabytalkRuntimeException being thrown to the effect of Method not found

3. Suppose the image contained the following (erroneous) top-level variable declaration and message invocation

var i : Integer

invoke i print

At what point in the interpretation would the error be detected (i.e., would it be detected by the interpreter at the time it encounters the declaration, or at some other point)? What if the invocation were absent? (5 points)

The error is not detected until the invocation is resolved. In detail what will happen is the following:

• Upon encountering the variable declaration, the interpreter will create a new Var object containing the variable name i and the class name Integer

• When the interpreter gets to the next statement (the top-level invocation), it will attempt to resolve the variable name i.

o It does this by looking up the variable name i in the global variable table, obtaining the (above-mentioned) corresponding Var object

o It then attempts to retrieve the Class object corresponding to the class name Integer, however that will cause a BabytalkRuntime exception to be thrown to the effect Class not found

4. Suppose we changed the Var class so that it contains a reference to the Class object of the variable’s class (rather than the name of the class represented as a String):

|public class Var { | |public class Var { |

|… | |… |

|private String className; | |private Class clazz; |

|private String name; | |private String name; |

|} | |} |

a. Either redraw question #2 here using this new implementation, or go back to your #2 solution and add the new references in a manner that makes it clear which is which (use dashed lines, for example, to indicate the new references). (5 points)

Suppose the definition of the Number class had come after the definition of the Expression class in the image, i.e.,:

class Expression {

...

}

class Number {

...

}

How would this affect

i. our original implementation (the one using the class name in the Var object)? (5 points)

There would be no change—all references to classes in the Phase 2 tables are maintained as class names. In particular the class of a variable is maintained as a class name (Strong) in the corresponding Var object. It is only when we subsequently attempt to resolve a variable (within the context of a message) that the actual Class object is retrieved.

In particular, the references to the classes Number and Character in the operand1, operand2, operator in the instance variables of the Expression class pose no problem with regard to not having seen the Number and Character class defs yet. The Var objects are created and the class name is set to Number and Character. It is only later that we begin interpreting message invocation (beginning with the top-levels at the end of the image) that we actually resolve the class names to Class objects but by then the Number and Character class definitions have been encountered and are thus in the global class table.

ii. the new implementation (using the Class reference)? (5 points)

In this case when the Var object is created (say for operand1 which is of type Number), we need the Class object to be in existence in order to be able to place a reference to said Class object in the Var object we create for operand1. The implication is to require that a class be somehow defined (or declared if you will) prior to it being used (this would be similar to C++’s requirement that you place function declarations at the top of your source file so the function is known to the compiler prior to being called.

b. What about the effect on our erroneous var declaration? (5 points)

var i : Integer

Requiring that class definitions appear BEFORE they are referenced would produce an immediate error, since we have not seen a class definition for Integer

Part 2. There is a portion of the Collection Framework API at the end of the exam for your reference.

5. Classes can inherit from classes (superclass/subclass) and interfaces can inherit from interfaces (superinterface/subinterface).

a. What’s the difference between the two? Use examples from the API as part of your answer. (5 points)

In class inheritance, the subclass inherits actual state (instance variables) and behavior (method definitions) from the superclass. The subclass can then add additional state and behavior or override existing behavior (by method overriding). An example of this is Stack extending Vector.

In interface inheritance, the subinterface assumes the behavior obligations of the superinterface and then can add its own. An example of this is List extending Collection.

b. How do classes and interfaces interact? Use an example from the API as part of your answer. (5 points)

Classes implement interfaces, i.e., they provide the actual behavior specified by the interface (i.e., the implementing class provides method bodies or definitions for the method declarations specified by the interface). An example is Vector implementing List.

As an aside, all three of the above (class inheritance, interface inheritance, and interface implementation) characterize the is-a relationship: a subclass is-a instance of its superclass (a Stack is a Vector); a subinterface is-a conforms to its superinterface (a List provides the services required of a Collection); an implementing class is-a instance of the implemented interface (a Vector is a List).

6. The API shows that Stack is implemented via inheritance from Vector. The other way to have implemented Stack is to have used composition:

class Stack {

...

private Vector v;

}

Complete the composition implementation by providing the methods empty, peek, pop, and push as detailed in the API. (if you prefer, you can implement the class VectorSet which implements the Set interface using a Vector as the backing data structure, in which case you may also answer question 7 using VectorSet as well). (10 points – you must answer this question)

class Stack {

boolean empty() {return v.isEmpty();}

Object peek() {return v.lastElement();}

Object push(Object item) {

v.add(item);

return item;

}

Object pop() {

Object val = v.lastElement();

removeElementAt(v.size()-1};

return val;

}

private Vector v;

}

7. a. Discuss the two implementations of the Stack in question 6 in terms of the concept that inheritance represents the is-a relationship, while composition represents the has-a relationship. In particular, which is the more appropriate of the two implementations? Why? (5 points)

The version in the API uses inheritance, and thus should seemingly get much for free. However, as the interface for a stack are the methods, push, pop, empty, and peek – none of which are present in the Vector class, these have to be added anyway. Furthermore, all the methods inherited from Vector are in essence inappropriate for use with a Stack. This last issue is also revealed by using the is-a test: is a stack a vector?

The version you wrote in 6 uses composition— the stack is composed of a vector. The implementation is essentially a delegation (wrapper) class—almost all the work is passed on to the Vector methods (the API version probably does the same thing, BTW). The nice thing about THIS implementation is that the inappropriate methods of Vector are NOT available to uses of the stack class. And again, using the has-a test: does a stack have a vector (i.e, can a stack be implemented using a vector).

Summarizing the above from the is-a/has-a perspective: a stack is NOT a vector, but can very well use one in its implementation. This tells us that composition is the more appropriate implementation mechanism.

a. You’ll notice my composition implementation of Stack did not implement the List interface, yet the Stack implementation in the API does? Explain why they did and I didn’t (hint, explain why Stack should not be implementing the List interface). (5 points)

Same as above, just like a stack is not a vector, it is also not a list. The List interface models objects that are ordered (sequential) in nature: we can speak of the first, second, last, etc. This is not true of a Stack, which thus has no reason to implement the List interface.

java.util

Interface Collection

All Superinterfaces:

Iterable

All Known Subinterfaces:

List

All Known Implementing Classes:

Stack, Vector

[pic]

public interface Collection

extends Iterable

The root interface in the collection hierarchy. A collection represents a group of objects, known as its elements. Some collections allow duplicate elements and others do not. Some are ordered and others unordered.

|Method Summary |

| boolean |add(Object obj) |

| |          Ensures that this collection contains the specified element (optional operation). |

| void |clear() |

| |          Removes all of the elements from this collection (optional operation). |

| boolean |contains(Object obj) |

| |          Returns true if this collection contains the specified element. |

| boolean |equals(Object obj) |

| |          Compares the specified object with this collection for equality. |

| boolean |isEmpty() |

| |          Returns true if this collection contains no elements. |

| int |size() |

| |          Returns the number of elements in this collection. |

 

java.util

Interface List

All Superinterfaces:

Collection, Iterable

All Known Implementing Classes:

Stack, Vector

[pic]

public interface List

extends Collection

An ordered collection (also known as a sequence). The user of this interface has precise control over where in the list each element is inserted. The user can access elements by their integer index (position in the list), and search for elements in the list. Unlike sets, lists typically allow duplicate elements.

|Method Summary |

| boolean |add(Object obj) |

| |          Appends the specified element to the end of this list (optional operation). |

| void |add(int index, Object element) |

| |          Inserts the specified element at the specified position in this list (optional |

| |operation). |

| void |clear() |

| |          Removes all of the elements from this list (optional operation). |

| boolean |contains(Object obj) |

| |          Returns true if this list contains the specified element. |

| boolean |equals(Object obj) |

| |          Compares the specified object with this list for equality. |

|Object |get(int index) |

| |          Returns the element at the specified position in this list. |

| int |indexOf(Object obj) |

| |          Returns the index of the first occurrence of the specified element in this list, or -1 if|

| |this list does not contain the element. |

| boolean |isEmpty() |

| |          Returns true if this list contains no elements. |

| Object |set(int index, Object element) |

| |          Replaces the element at the specified position in this list with the specified element |

| |(optional operation). |

| int |size() |

| |          Returns the number of elements in this list. |

java.util

Interface Set

All Superinterfaces:

Collection, Iterable

All Known Subinterfaces:

SortedSet

All Known Implementing Classes:

HashSet, TreeSet

[pic]

public interface Set

extends Collection

A collection that contains no duplicate elements. As implied by its name, this interface models the mathematical set abstraction.

|Method Summary |

| boolean |add(Object obj) |

| |          Adds the specified element to this set if it is not already present (optional operation). |

| void |clear() |

| |          Removes all of the elements from this set (optional operation). |

| boolean |contains(Object obj) |

| |          Returns true if this set contains the specified element. |

| boolean |equals(Object obj) |

| |          Compares the specified object with this set for equality. |

| boolean |isEmpty() |

| |          Returns true if this set contains no elements. |

| int |size() |

| |          Returns the number of elements in this set (its cardinality). |

java.util

Class Vector

java.lang.Object

...

...

[pic]java.util.Vector

All Implemented Interfaces:

Iterable, Collection, List

Direct Known Subclasses:

Stack

[pic]

public class Vector

extends ...

implements List

The Vector class implements a growable array of objects. Like an array, it contains components that can be accessed using an integer index. However, the size of a Vector can grow or shrink as needed to accommodate adding and removing items after the Vector has been created.

As of the Java 2 platform v1.2, this class was retrofitted to implement the List interface, making it a member of the Java Collections Framework.

|Method Summary |

| boolean |add(Object obj) |

| |          Appends the specified element to the end of this Vector. |

| void |add(int index, Object element) |

| |          Inserts the specified element at the specified position in this Vector. |

| void |addElement(Object obj) |

| |          Adds the specified component to the end of this vector, increasing its size by one. |

| int |capacity() |

| |          Returns the current capacity of this vector. |

| void |clear() |

| |          Removes all of the elements from this Vector. |

| boolean |contains(Object obj) |

| |          Returns true if this vector contains the specified element. |

| Object |elementAt(int index) |

| |          Returns the component at the specified index. |

| Enumeration |elements() |

| |          Returns an enumeration of the components of this vector. |

| boolean |equals(Object obj) |

| |          Compares the specified Object with this Vector for equality. |

| Object |firstElement() |

| |          Returns the first component (the item at index 0) of this vector. |

| Object |get(int index) |

| |          Returns the element at the specified position in this Vector. |

| int |indexOf(Object obj) |

| |          Returns the index of the first occurrence of the specified element in this vector, or -1 if|

| |this vector does not contain the element. |

| int |indexOf(Object obj, int index) |

| |          Returns the index of the first occurrence of the specified element in this vector, |

| |searching forwards from index, or returns -1 if the element is not found. |

| void |insertElementAt(Object obj, int index) |

| |          Inserts the specified object as a component in this vector at the specified index. |

| boolean |isEmpty() |

| |          Tests if this vector has no components. |

| Object |lastElement() |

| |          Returns the last component of the vector. |

| Object |set(int index, Object element) |

| |          Replaces the element at the specified position in this Vector with the specified element. |

| void |setElementAt(Object obj, int index) |

| |          Sets the component at the specified index of this vector to be the specified object. |

| int |size() |

| |          Returns the number of components in this vector. |

| String |toString() |

| |          Returns a string representation of this Vector, containing the String representation of |

| |each element. |

 

 

java.util

Class Stack

java.lang.Object

...

...

[pic]java.util.Vector

[pic]java.util.Stack

All Implemented Interfaces:

Iterable, Collection, List

[pic]

public class Stack

extends Vector

The Stack class represents a last-in-first-out (LIFO) stack of objects. It extends class Vector with five operations that allow a vector to be treated as a stack. The usual push and pop operations are provided, as well as a method to peek at the top item on the stack, a method to test for whether the stack is empty, and a method to search the stack for an item and discover how far it is from the top.

|Method Summary |

| boolean |empty() |

| |          Tests if this stack is empty. |

| Object |peek() |

| |          Looks at the object at the top of this stack without removing it from the stack. |

|Object |pop() |

| |          Removes the object at the top of this stack and returns that object as the value of this function. |

| Object |push(Object item) |

| |          Pushes an item onto the top of this stack. |

 

-----------------------

|Number | |

|Character | |

|Expression | |

|Number |

| |

| |

|Character |

| |

| |

|Expression |

| |

| |

| | |

|val | |

|print | |

|operand1 |Number |

|operand2 |Number |

|Operator |Character |

|c |Character |

|n |Number |

|n2 |Number |

|e |Expression |

| | |

|operand1 |value |

|value | |

|print | |

|getOperand1 | |

|getOperand2 | |

|getOperator | |

|print | |

| |

|operand1 |value |

| |

| |

| |

| |

| |

| |

| |

| |

| |

|operator |value |

|operand1 |print |

|operator |print |

|operand2 |print |

|operand2 |print |

|operator |print |

|operand1 |print |

|operator |value |

|operand1 |value |

| |

| |

| |

| |

| |

| |

| |

| |

| |

| |

|operand1 |value |

|getOperand1 | |

|getOperand2 | |

|getOperator | |

|print | |

|val | |

|print | |

|value | |

|print | |

| | |

|c | |

|n | |

|n2 | |

|e | |

|operand1 | |

|operand2 | |

|Operator | |

| | |

|Expression |

| |

| |

|Character |

| |

| |

|Number |

| |

| |

|Number | |

|Character | |

|Expression | |

................
................

In order to avoid copyright disputes, this page is only a partial summary.

Google Online Preview   Download