Previous column

Next column


The Theory of Classification

Part 10: Method Combination and Super-Reference

Anthony J H Simons, Department of Computer Science, University of Sheffield, U.K.

space COLUMN

PDF Icon
PDF Version


1 INTRODUCTION

This is the tenth article in a regular series on object-oriented type theory, aimed specifically at non-theoreticians. Recent articles have presented a formal model of classification that differs from the conventional model of types and subtyping [1, 2]. The popular object-oriented languages fall into two groups – those based on simple types and subtyping, such as C++ and Java, and those based on polymorphic classes and subclassing, such as Smalltalk and Eiffel [2, 3]. A programmer’s class has a formal interpretation at the typeful level [2] and a concrete interpretation the implementation level [3]. In the theory, we have been careful to distinguish classification from inheritance.

Classification is the hierarchical relationship between classes, whereby one class is judged to be a subclass of another, according to type rules governing subclassing [2]. Inheritance, on the other hand, is a short-hand mechanism for defining a new class in relation to an existing class1, specifying what is new or different, and otherwise inheriting all existing features [3]. This presents an interesting formal challenge. If inheritance is indeed merely a short-hand, we should be able to prove in our theory that a class constructed by inheritance is equivalent to a class defined as a whole, from first principles [3]. This challenge is made more complicated by the possibility of method combination, the merging of local and inherited versions of a method. Furthermore, Smalltalk and Java can invoke inherited versions of methods through a pseudo-variable called super. So, our theory must be able to explain the meaning of super, and show how super-method invocations are eventually equivalent to ordinary method invocations.

2 METHOD COMBINATION

So far, our treatment of inheritance and method overriding has assumed that individual methods are always replaced as a whole. For example, in the previous article [3] we replaced an equal method of a two-dimensional point:

in which self refers to a Point2D instance, by an equal method of a three-dimensional point:

in which self refers to a Point3D instance. On the surface, the overriding method appears to be syntactically quite similar to the method that was replaced. In most object-oriented languages, programmers don’t have to write out such replacement methods long-hand; instead the languages offer a short-hand mechanism for adapting the inherited version of the method. The idea is that the overriding method may somehow reuse the code body of the inherited method and need only specify what additional computations take place. This is known as method combination.

In C++ and Eiffel, method combination is achieved simply by naming the local and inherited versions of the method differently. In C++ it is always possible to qualify method names globally by their owning class, in the style: ParentClass::method and ChildClass::method. So, the redefined body of the Child’s method may invoke ParentClass::method explicitly, by referring to its global name. In Eiffel, the name of a method may be locally renamed when it is inherited, in the style: class Child inherit Parent rename method as old_method … end. Then, the body of Child’s method may invoke old_method. In both of these cases, invoking an inherited method inside a redefined version is no different from invoking any other differently-named method.

Smalltalk and Java achieve method combination in a much more interesting way. These languages have a pseudo-variable called super, which somehow allows a programmer to invoke an inherited version of a method inside the redefined version of the same method, without renaming the method. In the theoretical model, we can express Point3D’s equal method more simply as:

In this, super somehow stands for the current object in the context of the parent class. Whereas an invocation self.equal(…) would call the local version, super.equal(…) is deemed to call the inherited version of the same method. It is quite difficult to understand exactly what object super refers to! By the end of this article, we hope to answer this important question. However, one consideration is that the sub-expression: super.equal(p) must eventually be shown to be equivalent to the portion of code in the long-hand version of the method:

3 RENAMING METHODS

To handle method combination in C++ and Eiffel, we must first consider how to rename methods in the theoretical model. In C++, we could either decide that the global names exist permanently as alternative, duplicate names for the same methods, or we could introduce them on demand, when we want to combine methods. In Eiffel, however, we must allow methods to be renamed locally, on demand, during inheritance. Recall that inheritance is modelled as record combination in the theoretical model [3], in which a base record is extended by combining it with a record of extra methods, to yield a derived record:

Intuitively, we now want to rename methods in the base record, then combine this with the extra record. For this, we need a renaming operator ®, and expect to use it in the following way:

in which renamings is a map from original labels to revised labels. In the same style as the union with override operator [3], we may define the renaming operator to accept an object record (a map from labels to methods) and a record of renamings (a map from labels to labels) and return a new object record in which some labels have been replaced:

The top line is a polymorphic type signature [1], saying that ® takes two maps with the individual type signatures and , and returns a map with the signature . The type is the label-type, and is the method-type in the object record. Note how the object-type of the result is unchanged, reflecting that methods have merely been renamed.

The full definition follows. This says that ® takes two argument maps, f and g (with the given types) and produces a result map (the whole expression in braces). This result is the set of all those maplets k v that satisfy the following conditions (after the vertical bar | ). For all original labels h in the domain of the base object f, if h is also listed in the domain of the renamings g, the resulting label k is equal to the translation g(h), otherwise k is equal to the original label h. The corresponding values v are always equal to f(h), as in the original object map. Recall that f(h), g(h) denote range values by appealing to the functional interpretation of maps: f(h) “applies” the map f to the domain value h, yielding the corresponding range value.

We can use this operator to rename methods of an object. Here is a simple Point2D instance:

in which we wish to rename the equal method with a longer, qualified name, old_equal:

The renaming operator ® takes, as its operands, the object and a map of renamings (see bold highlight), yielding an object in which the equal method has been renamed.

4 METHOD COMBINATION WITH RENAMING

This allows us to construct a model of inheritance with method combination supported through renaming. The following is an expression to derive aPoint3D from aPoint2D by renaming its equal method and then supplying a redefined version, which refers back to the old version:

The left-hand operand of the record combination operator ? is a renaming expression (see first bold highlight), in which the equal method is renamed before combination. The right-hand operand of ? is a record of extra methods, in which the redefined equal method invokes the renamed method old_equal in its body (see second bold highlight), thereby benefiting from the more succinct syntax offered by method combination.

We want to show that this method combination syntax is equivalent to a regular, wholesale method replacement. Simplifying the renaming expression yields a base record (see bold highlight):

which in turn may be combined with the record of extra methods (see [3]) to yield the following unusual record, in which inherited self-references are resolved to aPoint2D, while the local self is bound over aPoint3D:

The resulting object has both the renamed method old_equal and the redefined version equal. This is quite normal in languages with renaming. Note that we have deliberately given these two functions different formal argument names, p and q, in order to observe what happens to object references in the next stage. We now want to understand the precise meaning of the redefined equal in detail. To do this, we may simplify the embedded call to the old version of the method (see bold highlight above). This simplification is equivalent to replacing the call by the inlined body of the old_equal method, after substituting the argument {q/p}, viz the evaluation:

This internal simplification is performed exactly like any other function simplification; and may be thought of as an evaluation in which the call is replaced by the body after arguments have been substituted. In this case, the actual argument q (a Point3D instance) is substituted in place of the formal argument p (a Point2D variable) yielding the simplified form:

This demonstrates formally how the derived equal method does indeed compare all of the x, y and z dimensions of the Point3D instance q. However, note how the body of this method suffers from the same kind of schizophrenia that we have noted before [2, 3] when dealing with simple object types. The local binding is self aPoint2D. After the internal simplification, the combined method is comparing mixtures of 2D and 3D points for the equality of their x and y fields! For this reason, we cannot yet regard this kind of method combination as wholly equivalent to defining a replacement method wholesale.

5 FLEXIBLE METHOD COMBINATION WITH RENAMING

The problem is one of ensuring uniform self-reference in both local and inherited methods. Recall that in Eiffel, self-reference is flexible, such that inherited occurrences of self (known as current in Eiffel) are redirected to refer to the derived object. In the formal model, this requires the use of an object generator to express the object definition [3]:

This is different from a plain object in that self is a formal argument of the generator. As such, we can bind it to different values, representing the different objects that self may range over. Inheritance is modelled as an adaptation on generators [3]. We now add the renaming scheme to this model:

The critical difference is in the way self-reference is modified, through the generator application: genAPoint2D(self), yielding an adapted record in which self refers to the new object. After simplifying the renaming-expression (see bold highlights above and below), this yields:

and after record combination, this yields a result in which both equal and old_equal methods co-exist, but all self-reference is now uniform:

We now simplify the body of the equal method, by expanding inline the call to old_equal:

This yields the final result (see highlights) in which self refers uniformly to the current object. This is a satisfactory outcome, in that it meets our requirement that method combination should be provably equivalent to redefining the method wholesale. Because of its special treatment of current, Eiffel’s method combination with renaming follows this semantics.

6 THE MEANING OF SUPER

However, it may be considered inelegant for objects to keep both the old and new versions of a method. Having to rename methods is irksome and keeping both versions is redundant, especially if you only want the old version once, during method combination. For this reason, languages like Smalltalk and Java provide “one time access” to the inherited versions of methods, when redefining the same methods, through a special pseudo-variable called super:

It is clear that super must refer in some sense to the current object, somewhat like self, yet different from the point of view of method lookup. The operational explanation of super-method invocation is typically that “the search for a method starts in the immediate superclass of the class of self” [4]. Other attempts at describing super sometimes say that it is “the inherited object” or “the embedded parent-part of the current object”. In fact, the meaning of super is subtle and varies from language to language, as we shall show below.

We may construct a model of super from the operational description of method lookup. The most obvious way of invoking the “next most general” version of a method in our theory is to ensure that we select it from the “next most general” version of the object-instance with which we are dealing. In other words, if our most recently derived object is expressed as:

such that we would expect derived.method to invoke the latest version of some method, then base.method should be the expression that invokes the next most general version of the same method, skipping over any redefinition supplied in the extra record. From this analysis, it seems clear that super is equivalent to the base object record, in a record combination expression.

In the theory, this object is always supplied as the left-hand operand to the record combination operator (see bold highlights below). Recall that in record combination with simple object records (see section 6 in [3]) we have:

which indicates that this operand is in fact equivalent to an instance of the base type. This gives the meaning of super in Java, a language based on simple types and subtyping in our theory. The variable super corresponds to the embedded parent-part of the current object, self, or more exactly to the inherited parent-part before any fields are replaced during record combination. It has the type super : Point2D and behaves exactly like an instance of the base type, in that self-references in super-methods refer back to super.

On the other hand, in flexible record combination with object generators (see section 7 in [3]) we have the completely different left-hand operand:

which is an adapted record, obtained by applying the base generator to the new self reference (of the derived generator). This gives the exact meaning of super in Smalltalk, a language based on classes and subclassing in our theory. The variable super is like an adapted instance of the parent type, in which self-reference is redirected to refer to the current, derived object. It has an adapted type given by the application of a type generator super : GenPoint3D[Point2D] and behaves differently from an instance of the base type, in that self-references in super-methods refer to the whole of the current, derived object, rather than to an embedded parent instance.

7 METHOD COMBINATION WITH SUPER-REFERENCE

In order to model method combination with super-reference in our theory, we need to introduce the super variable, and bind it to a value standing for the (possibly adapted) parent instance, such that we may refer to super throughout the record combination expression, in the style:

The variable may be introduced as the formal argument of a function: super.(...) which is later bound to a suitable value. The order of variable introduction is dictated by the need for super to be bound outside the scope of record combination, but inside the scope of self:

Here, the expression super.(...) is a function, binding super, whose body is a record combination expression that contains free references to super as intended. This super-function is then applied to the value: aPoint2D. To verify that this is equivalent to regular record combination, we may simplify the super-function application internally, with the binding super aPoint2D, to obtain:

Firstly, we see that super is replaced by the desired parent object on the left-hand side of the combination operator. Secondly, we find that super.equal(…) translates exactly into an expression invoking the equal method of a parent instance, which is promising, since it clearly skips the current version. To simplify this internally, we replace the call by the inlined body of the parent’s method, after substituting the argument {q/p} as before. After record combination:

this yields a non-uniform solution similar to that in section 4 above, but without duplicate versions of the equal method. This model of method combination explains the behaviour of languages like Java, in which super always resolves to an instance of the immediate parent type.

The more flexible kind of method combination with object generators may be modelled as:

in which the super-function is bound differently with super genAPoint2D(self). Note in passing how self must be bound before we can bind super. This time, super does not denote a parent instance, but rather an adapted object, the result of applying the parent generator to self. To explore further what this means, we may simplify the super-function application internally, yielding:

From this, it appears that the super.equal(…) invocation is equivalent to invoking equal on an adapted parent object. This is quite subtle, because self-reference is redirected in this object onto the new self of 3D points. We can illustrate this more graphically by expanding super:

From this, it is clear that super.equal will select the inherited equal method body, in which self refers back to the local Point3D instance. Furthermore, super.equal(q) will produce the argument substitution {q/p}, where q is implicitly a variable of the type Point3D:

When this subexpression is replaced in the body of the local equal method, we obtain a combined equal method, which has consistent self-reference and an argument in the same type:

Method combination using super-reference is thereby proved to be equivalent to redefining the method wholesale. Note how the more subtle semantics of super is needed for this to work out fully. Cook et al. were the first to identify this formal interpretation of super in Smalltalk [5, 6], from the operational description of inheritance in that language.

8 CONCLUSION

We have constructed four different models for inheritance with method combination. Two involve the renaming of methods, in the style of C++ and Eiffel. Two involve the use of the pseudo-variable super, in the style of Java and Smalltalk. While C++ and Java have a simple model of inheritance, based on the extension of object records, Smalltalk and Eiffel have a more subtle model of inheritance, based on the extension of object generators. Hereafter in our theory, we shall refer to the simple extension model as derivation, to distinguish it from “genuine” inheritance, in which self-references are redirected to refer to more specific objects [3, 5].

Considering each approach to method combination individually, the first uses derivation and renaming. The second uses inheritance and renaming, of which Eiffel is the exemplar. The third uses derivation and super-reference, of which Java is the exemplar. The fourth uses inheritance and super-reference, of which Smalltalk is the exemplar. An even simpler model exists for C++, if we allow objects to have two names for each method, one local and one global:

and adopt the convention that only the local names are ever overridden. In this way, we can express the combined equal method for Point3D as:

which simplifies in accordance with our first model, above. The method combination strategies using inheritance were shown to be equivalent to wholesale method replacement, demonstrating again the usefulness of the theoretical model. The model also provided the pseudo-variable super with two semantic interpretations, corresponding to the meanings of this variable in Java and Smalltalk. We also provided an original renaming operator ® to account for Eiffel’s behaviour.


Footnotes

1 Popular books on object-oriented programming sometimes confuse these notions, referring to the hierarchical relationship as “inheritance”. Strictly speaking, inheritance is just the extension mechanism. However, an inheriting class will typically be a subclass, but only by virtue of obeying the rules about classification [2].

 

REFERENCES

[1] A J H Simons, “The theory of classification, part 7: A class is a type family”, in Journal of Object Technology, vol. 2, no. 3, May-June 2003, pp. 13-22. http://www.jot.fm/issues/issue_2003_05/column2

[2] A J H Simons, “The theory of classification, part 8: Classification and Inheritance”, in Journal of Object Technology, vol. 2, no. 4, July-August 2003, pp. 55-64. http://www.jot.fm/issues/issue_2003_07/column4

[3] A J H Simons, “The theory of classification, part 9: Inheritance and Self-Reference”, in Journal of Object Technology, vol. 2, no. 6, November-December 2003, pp. 25-34. http://www.jot.fm/issues/issue_2003_11/column2

[4] A Goldberg and D Robson, Smalltalk 80: The Language and its Implementation, Addison-Wesley, 1983.

[5] W Cook, W Hill and P Canning, “Inheritance is not subtyping”, Proc. 17th ACM Symp. Principles of Prog. Lang., (ACM Sigplan, 1990), pp. 125-135.

[6] W Cook and J Palsberg, “A denotational semantics of inheritance and its correctness”, Proc. 4th ACM Conf. Obj.-Oriented Prog. Sys. Lang. and Appl., pub. Sigplan Notices, 24(10), (ACM Sigplan, 1989), pp. 433-443.

 

About the author

Losavio

space Anthony Simons is a Senior Lecturer and Director of Teaching in the Department of Computer Science, University of Sheffield, where he leads object-oriented research in verification and testing, type theory and language design, development methods and precise notations. He can be reached at a.simons@dcs.shef.ac.uk.


Cite this column as follows: Anthony J.H. Simons: “The Theory of Classification, Part 10: Method Combination and Super-Reference”, in Journal of Object Technology, vol. 3, no. 1, January-February 2004, pp. 43-53. http://www.jot.fm/issues/issue_2004_01/column4


Previous column

Next column