Previous column

Next column

---

The Theory of Classification Part 9: Inheritance and Self-Reference   Anthony J H Simons, Department of Computer Science, University of Sheffield, U.K.

COLUMN PDF Version

1 INTRODUCTION

This is the ninth article in a regular series on object-oriented type theory, aimed specifically at non-theoreticians. The previous article demonstrated how the intuitive notion of class in object-oriented languages has a strictly formal interpretation that is more general than the simple notion of type [1]. A class can be modelled as an F-bounded polymorphic type, representing a family of similar types which share a minimum common structure and behaviour [2, 3]. In this second-order model, which provides an alternative to first-order subtyping [2, 4], even recursively-defined classes can be shown to nest properly inside each other [1], a more sophisticated kind of type compatibility that we call subclassing in figure 1 (box 8). Type rules were defined for class membership, sub-classification and class extension by inheritance.

Figure 1: Dimensions of Type Checking

The previous article concentrated only on the typeful aspects of classes. In this article, we now turn to the concrete aspect of classes and the detailed modelling of method implementations. We want to be able to explain in the formal model how an object’s structure is extended or altered during inheritance. In particular, we want to understand the process of method overriding and the meaning, after inheritance, of the special self-referential variable self, also known as this, or current in different object-oriented languages.

2 OBJECT IMPLEMENTATIONS

Several articles ago, we considered three different formal encodings of simple objects [5]. We preferred the -calculus encoding, which represents recursive objects as functional closures, denoting simple records of methods. One reason for choosing this model is because it fits so well with the F-bounded explanation of polymorphic classes, since both models rely on the use of generators, special functions which accept self (or, the self-type) as their argument. Later, we shall link the object model with the type model, in a combined second-order F-bounded –calculus. For the time being, we shall deal with objects in an untyped way.

A simple two-dimensional point object at the co-ordinate (3, 5) may be represented as a record, whose fields store values and functions, representing the attributes and methods of the object. Each field consists of label which maps to a value (a simple value, or a function):

In the above, self is the recursion variable, a placeholder equivalent to the eventual definition of the whole object aPoint2D, which contains embedded references to self (technically, we say that binds self to the resulting definition – see [5] for an explanation of this convention). Following the dot is a record of fields, enclosed in braces {…}. The first two fields, labelled x and y, map to simple values in the model. This is because we want aPoint2D.x and aPoint2D.y to return the simple values directly, rather like accessor methods. The third field identity is a method for returning the object itself; the fourth field equal maps to another function p.(…), representing a method that compares aPoint2D with the argument p, which is assumed to be another Point2D instance.

This is where it becomes clear why aPoint2D is a recursive object: inside the body of the equal method, aPoint2D must invoke further methods x and y upon itself, to perform the field-by-field comparison with the argument p. To enable this, the body of the equal method needs a handle on the top-level object aPoint2D, granted through the recursion variable self. Any object that needs to invoke nested methods on itself must be recursive, so this is quite a common occurrence in practice. The identity method is also recursive, returning the object itself.

This theoretical use of self corresponds exactly to the usual meaning of self (in Smalltalk), this (in Java and C++) and current (in Eiffel). In the model, you always invoke nested methods explicitly through the recursion variable self. In some of these programming languages, you can omit the receiver of a nested message to the same object, which is implicitly understood to be self (this, or current). This is just a syntactic sugaring in the programming language.

3 OBJECT GENERATORS

Readers who have been following this series will know by now that a recursive definition is created from first principles using a generator, a function which abstracts over the point of recursion. Previously, we used type generators to build recursive types [1, 2]. Here, we introduce object generators to build recursive objects:

In this function, self is not yet bound to any value – it is the argument of the function. The generator can be used to build the recursive object by infinite self-application [5]:

and for convenience’s sake, we may use the fixpoint finder Y to build this infinite sequence:

Later, we will see more expressions of this kind to describe the final fixing of the recursive structure of an object. Roughly speaking, an object generator genAPoint2D is a template for the structure of points like aPoint2D, in which self does not yet refer to anything. It turns out that this is a useful construction, since it will allow us to explain how self can refer to different objects.

4 EXTENDED OBJECT IMPLEMENTATIONS

Our goal is to model the inheritance of implementation. This can be thought of as a kind of extension or adaptation of an object, to produce an extended object with more fields, some of which may be modified, in the sense that the labels map to different values than in the original object. The challenge we set ourselves is to derive a three-dimensional point aPoint3D at the co-ordinate (3, 5, 2) by extending the simple two-dimensional aPoint2D in some fashion.

To begin with, we jump ahead to describe what we want aPoint3D to look like, at the end of the derivation process. Ultimately, we want it to have an extra z dimension and a modified version of the equal method, as if it had been defined from scratch, as a whole, in the following way:

In the above, self is the placeholder variable, equivalent to the eventual definition of the object aPoint3D, which also contains embedded references to self in its identity and equal methods. Note the difference in the meaning of self: whereas before bound self aPoint2D, here aPoint3D. The object denoted by self changes, depending on the binding context. From the practical point of view, this is also desirable, since the body of the modified equal method is only valid if self stands for aPoint3D (viz: you could not access the z-method of aPoint2D).

In the previous article [1], we constructed a simple model for inheritance, in which we treated a record as a set of fields and used set union to build a larger derived record by taking the union of the fields of the base record and a record of extra fields:

This only works for very simple records, which have unique fields and no recursion:

We cannot construct aPoint3D in this way, because the simple union of fields would create a result in which there were two different versions of equal, since the original and redefined versions of this field are not actually identical, therefore the union would preserve two copies.

5 UNION WITH OVERRIDE

Instead, a different operator must used, called union with override: . This is a standard mathematical operator, defined for maps (rather than sets), that combines two maps in a certain way, which we define below. A map is a collection of pairs of values, called maplets, with an arrow from the left- to the right-hand value in each pair. A map is written like:

and can be viewed variously as a lookup table, in which each maplet relates a key (on the left) to a corresponding value (on the right), or alternatively as a function¹ from the domain {a, b, c, … } to the range {x, y, z, … }. Where a map models a function, all the domain values are unique (but the range could contain duplicates).

An advantage in modelling objects as records is that they can also be thought of as maps: each field is a maplet consisting of a label (the domain) that maps to a value (the range). In object maps, the labels always have the same type (viz: Label), but the values could be of many different types. For this reason, we give the union with override operator the following definition:

The top line is a polymorphic type signature [2], saying that takes two maps with the individual type signatures and , and returns a map with the signature . Notice how the type of the domain is the same in each case (for labels), but the types of the ranges are possibly different. The range in the result is a union type , formed by merging the types of the ranges of each argument. This is consistent with the type unions used in the previous article [1].

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 | ). The domain values k are obtained by taking the union of the domains of each argument map. This ensures that the domain of the result contains all the unique domain values from both maps. The range values v are obtained according to the asymmetric rule: if k is in the domain of the right-hand map g, use the corresponding range value g(k) from the right-hand map; otherwise use the corresponding range value f(k) from the left-hand map. This works, because every k must either be in the domain of the left-, or right-hand maps, or both. Note that f(k), g(k) denote range values by appealing to the functional interpretation of maps: f(k) “applies” the map f to the domain value k, yielding the corresponding range value.

When used with records, the union with override operator has the effect of merging two records, but preferring the fields from the right-hand side in the case of conflicting labels. Where there are no label-conflicts, it takes the union of the fields. If there are label-conflicts, it discards fields on the left-hand side and chooses fields from the right-hand side. This is exactly the behaviour we need to model record extension with overriding.

Another use for this operator is to model field updates in an object. We shall look at this first, as a simple way of illustrating the behaviour of . Consider updating the x position of the simple co-ordinate from above:

This can be used to model a primitive notion of field reassignment, although in the calculus we always create and return new objects (the -calculus is purely functional, after all).

6 SCHIZOPHRENIC SELF-REFERENCE

Following this example, it would seem natural to define the extended object aPoint3D by combining the record for aPoint2D with a record of the extra methods (z and the modified equal) that we want it to have. The overriding behaviour of will ensure that the result gains just one copy of the equal method, from the right-hand record of extra methods, which has the following structure:

Notice how this record also implies a recursion somewhere, because the equal method contains free references to self. To which object should this self refer? Looking at the body of the equal method, it is clear that we intend it to refer to aPoint3D, because we want to invoke the nested method self.z, which is not valid for aPoint2D. The only way to make self refer to the resulting object is to bind it outside the record combination (see bold highlight):

This says that aPoint3D is a recursive object, formed by taking the union-with-override of aPoint2D and a record of extra methods, in which self refers to aPoint3D. Unrolling the definition of aPoint2D (see bold highlight) this gives:

We can now judge how will combine the fields of these two records. The result should contain fields having all the labels {x, y, z, identity, equal} and the right-hand version of equal should be preferred, overriding the left-hand version. After record combination, this simplifies to:

This is the correct result, but on closer inspection, it may not be quite what was expected. Unrolling the definition of aPoint3D reveals what has become of all the references to self:

From this it is apparent that aPoint3D is a schizophrenic object, in two minds about itself! The inherited method identity thinks that self aPoint2D, while the locally added method equal thinks that self aPoint3D. How did this confusion arise? Recall that the recursive object aPoint2D was defined in isolation, such that self was bound over a different record:

All self-reference in this object inevitably refers to aPoint2D. So, when we inherit any methods from aPoint2D that contain self, this always refers to aPoint2D. In an earlier article [2], we described the problem of type-loss in languages such as C++ and Java, when methods referring to the self-type are inherited. The current example explains in more detail why this type-loss occurs: it is because inherited self always refers to the old object.

7 REDIRECTING SELF-REFERENCE

It was Cook and Palsberg who first described the more flexible behaviour of self in languages like Smalltalk and Eiffel [6]. They drew analogies between object self-reference and recursive function derivations . Figure 2 shows the two contrasting cases.

Figure 2: Naïve, and mutually recursive derivations

In the first example, a simple recursive function F calls itself, indicated by the loop. A modification to F is modelled as a derived function M which calls F. Recursive calls in F are unaffected, so the encapsulation of F is preserved. This is like the treatment of self in languages such as Java and C++. In these languages, a derived object does not modify the self-reference of the base object.

In the second example, the derived function M is mutually recursive with F. Recursive calls in F are affected by the modification, in the sense that they refer back to M, instead of to F. This is like the treatment of self in languages such as Smalltalk and Eiffel. In these languages, a derived object implicitly modifies the inherited self-references of the base object, such that these refer instead to the derived object.

To model inheritance in Smalltalk and Eiffel, we must redirect inherited self-references to refer to the derived object. In the formal model, this is accomplished by using generators instead of records. A generator is a function of self, in which the argument self is unbound (see section 3 above). The generator for 2D point objects is given by:

and now we seek to derive a generator for 3D point objects, by inheritance. The key strategy is to make sure that the old self_2D is replaced by the new self before any record fields are combined. This is achieved by applying genAPoint2D to the new self-argument for 3D points (see bold highlight):

This creates an instance of the generator body in which the substitution {self/self_2D} has taken place. This body has the form of a record (see bold highlight):

Both records on the left- and right-hand sides now refer to exactly the same self. We may combine them using the union with override operator, yielding the final simplified expression:

This produces the generator that we desired, in which all self-reference is uniform (see bold highlight). To create the derived recursive object, all we need to do is take the fixpoint of the generator, which has the effect of binding self to the resulting record:

We have now succeeded in our challenge, for this object has the desired structure and uniformity that we anticipated in section 4, but it required a more sophisticated model of inheritance. This model of implementation inheritance is somehow more satisfying, in that it allows inherited code to adapt to the derived object. For example, the inherited identity method will now return the derived object aPoint3D, rather than the old object aPoint2D.

8 CONCLUSION

We have constructed two different models of implementation inheritance and found that these correspond broadly to the mechanisms used in the major object-oriented languages. The core idea of extending and modifying object templates can be modelled using records and the union with override operator , for which we provided a satisfying typed definition. In Cook’s earlier work [4, 3, 6], no general typed definition was ever given for , so this aspect is novel in our Theory of Classification. The operator captures the basic mechanism for record combination with overriding for all languages. After this, object-oriented languages diverge, falling into two groups.

In the first group, which includes Java and C++, self-reference is fixed as soon as the object template is defined. When such an object is extended, although self-reference in the additional methods refers to the derived object, self-reference in the inherited methods always refers to the base object. In a suitably deep inheritance hierarchy, this means that objects may contain many versions of self, each referring to a different embedded ancestor-object! We described this as a kind of schizophrenia in self-reference. It is also linked to the problem of type-loss when methods passing values of the self-type are inherited [2]. Nonetheless, this model is the one used in all languages based on types and subtyping.

In the second group, which includes Smalltalk and Eiffel, self-reference is open to modification, even after the object template is defined. When such an object is extended, self-reference in the inherited methods is always redirected to refer to the derived object. All references to self are uniform, which is good for consistency, but they are interpreted locally in the object concerned. This is a novel feature of object-oriented languages, anticipating other kinds of adaptive programming. It is interesting to note how this flexibility came about. In Smalltalk, all methods are dynamically interpreted, so references to self are only bound at runtime to mean the current receiver. In Eiffel, the recursion variable current was originally conceived as a macro, to be expanded locally to refer to the new class. This had the effect of building implicit type redefinition into the language. The flexible model of inheritance is used in all languages based on classes and subclassing [1].

Formally, the difference between the two models of inheritance is very slight: it depends only on when fixpoints are taken. In the subtyping model, the recursion in the base object is fixed before record combination. In the subclassing model, the recursion is only fixed after record combination. For this reason, we can claim that the theory is both elegant and economical.

Footnote

¹ The operator is sometimes called function override in formal methods like Z, precisely because functions in Z are modelled as maps.

REFERENCES

[1] 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

[2] 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

[3] 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.

[4] P Canning, W Cook, W Hill, W Olthoff and J Mitchell, “F-bounded polymorphism for object-oriented programming”, Proc. 4th Int. Conf. Func. Prog. Lang. and Arch. (Imperial College, London, 1989), pp. 273-280.

[5] A J H Simons, “The theory of classification, part 3: Object encodings and recursion”, in Journal of Object Technology, vol. 1, no. 4, September-October 2002, pp. 49-57. http://www.jot.fm/issues/issue_2002_09/column4

[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

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