The following extract of a C++ class library of graphics objects is used as a running example for the exercises in this section. class graphical_object { virtual void translate(double x_offset, double y_offset); virtual void scale(double factor); // possibly further general methods of the class }; class point : public graphical_object { double xc, yc;

public: void translate(double x_offset, double y_offset) { xc+= x_offset; yc+= y_offset; } void scale(double factor) { xc*= factor; yc*= factor; } point(double x0, double y0) { xc= x0; yc= y0; } void set(double x0, double y0) { xc= x0; yc= y0; } double x(void) { return xc; } double y(void) { return yc; } double dist(point &); }; class closed_graphical: public graphical_object { public: // area enclosed by the object virtual double area(void); }; class ellipse: public closed_graphical { point _center; // center of the ellipse double _x_radius, _y_radius; // radius of the ellipse double _angle; // angle from x-axis public: // Constructor ellipse(point er, double x_radius, double y_radius, double angle) { _center= center; _x_radius= x_radius; _y_radius= y_radius; _angel= angle; } // ellipse area -- overloads closed_graphical::area double area(void) { return PI * _x_radius * _y_radius; } // distance to a point -- complex! virtual double dist(point &); // Center point* center(void) { return &_center; } // move -- overloads graphical_object::translate void translate(double x_offset, double y_offset) { _center.translate(x_offset, double y_offset); } // scaling -- overloads graphical_object::scale

void scale(double scale_factor) { _x_radius *= scale_factor; _y_radius *= scale_factor; } // .... }; class circle: public ellipse { public: // constructor circle(point er, double radius){ ellipse(center,radius,radius); } // distance to a point -- overloads ellipse::dist virtual double dist(point &p) { double center_dist= _center.dist(p); if (center_dist <= radius) return 0; else return center_dist - radius; } // .... };

1. Methods. Compile the method ellipse :: translate. 2. Virtual Method Tables. Determine for all classes, the relative addresses of virtual methods within the respective virtual method table. Translate a method call of the form c.dist(p) where c is a circle and p is a point. 3. Subtypes. The new definition of a class should not affect the existing class structure. Based on the subtyping rule, methods of already existing classes must also be able to work with objects of the new class. Through overloading of methods of parent classes, their view onto new objects can become inconsistent. Thus, redefinitions should be handled with caution. Three different aspects must be considered. The meaning (semantics) of members: each attribute and each method has a meaning which should not be affected by overloading. Thus, for instance, the method scale is meant to scale a graphics object. A redefinition should implement the same function, both at the current level of abstraction as well as at the level of the parent class. Restrictions through the type system: Redefinitions should not lead to type inconsistencies. Restrictions of the compilation schemes: Redefinitions can invalidate the assumptions made at compile-time and, then, should not be permitted. Although the first aspect is essential, a compiler normally does not have the required specifications for verifying semantical properties. In this exercise, we consider restrictions imposed by the type system.

Casting a type into a subtype is called type tightening, casting a type into a supertype is called type loosening. A prototype (of a method) is tightened if the types of the return value are tightened and the types of the input parameters are loosened. a) Argue that from the point of view of the type system, tightening of the prototype of a redefined method can be allowed. Show through examples that the prototypes of virtual methods can at most be tightened; any other modification may lead to type errors at calls that were previously correct. Argue that a non-tightened modification of the prototype for a redefined private method is also only acceptable under restricted assumptions. For a modification to be admissable, properties of the parent class are required, beyond the types of its attributes and the prototypes of its methods which properties? b) The language EIFFEL allows a derived class to tighten the type of an inherited attribute. Explain why attributes can then only be read by a foreign class. Show through an example that tightening the type of an attribute is only allowed under restricted assumptions. For a modification to be admissable, properties of the parent class are required, beyond the types of its attributes and the prototypes of its methods which properties?

4. Multiple inheritance I. In this exercise we consider multiple inheritance. For simplicity, we assume that from each parent class B exactly one instance is inherited by a subclass A, which means that each A-object contains exactly one B-subobject. For each parent class B of A, a fixed memory block is allocated within the memory block of an object of the class A. Also, we assume that the first immediate parent class B1 is treated like the immediate parent class in the case of single inheritance: its memory block is located at the beginning of the memory block for the immediate subclass A (Fig. 5.6). For a parent class Bi, the Bi-view to an object of class A is obtained by placing a pointer at the start of the block designated for Bi. Accordingly, the A-view to the object agrees with the B1-view for the first immediate parent class B1 of A. Within the memory block for A, a reference to the table tA of all virtual functions known in A is stored in location 0. At the beginning of all parent classes Bi which are not the first immediate parent class, a reference to a table tA,Bi is stored. The table tA,Bi contains the start addresses of all methods of A that are known in Bi. This construction is recursively applied to all parent classes of immediate parent classes Bi of A, and so on. A method f known in Bi may have been overloaded by the subclass A. Thus in tA,Bi , not only the start address of f must be recorded, but also the distance between the memory blocks for the classes A and Bi. This allows us to construct before the call to f , from Bi the correct A-view to the A-object.

a) Complete the details of the definitions of the tables tA,Bi . Implement the type cast of a pointer to an A-object to a pointer to an object of a super- and a subclass of A, respectively. b) Discuss strategies for resolving name conflicts and sketch their implementations. c) Combine the basic principle for multiple inheritance with our former translation schemes. d) Test your new translation schemes on our example class library.

5. Multiple inheritance II. In this exercise, we again consider multiple inheritance.

As in Exercise 4 we assume that each parent class B is inherited by the

subclass A only once. For each non-first parent class B, the object organization

in Exercise 4 stores a dedicated table tA,B for the virtual methods of class A that

are visible in B. Thus, all methods from tA,B are also contained in tA. We want

to eliminate this inefficiency.

Our goal is to save a virtual method known to B only in the table tA,B and not

in the tables tA and tA ,B for classes A between A and B. For this, the address

environment for class A is modified such that A( f ) returns a pair dt, i where

dt is the relative address of the reference to the table t, and i is the index where

the start address for f in t is recorded. Following the start address _ f , the table

t memorizes the relative distance dt for recovering the A-view of the object.

Relative to an A-view a to an object, we obtain the start address of the pair

(_ f , dt) for the method f by:

S[a + dt] + 2 i

(a) Modify the call to a virtual method according to this optimization.

(b) Estimate the savings that this optimization offers.

(c) Give an algorithm that computes, for a given class hierarchy, the distances dA,B, the address environment A for virtual functions of A, and constructs the required tables.