Prototypes -- delegation versus inheritance

subsections:

Alternative forms of sharing
Implementation techniques -- Self

The classical object model (which is constituted by classes, objects and inheritance) not only has its theoretical weaknesses (as outlined in the previous section) but has also been criticized from a more pragmatic perspective because of its inflexibility when it comes to developing systems. Code sharing has been mentioned as one of the advantages of inheritance (as it allows incremental development). However, alternative (read more flexible) forms of sharing have been proposed, employing prototypes and delegation instead of inheritance.

Alternative forms of sharing

A class provides a generic description of one or more objects, its instances. From a formal point of view, classes are related to types, and hence a class may be said to correspond to the set of instances that may be generated from it. This viewpoint leads to some anomalies, as in the case of abstract classes that at best correspond to partially defined sets. As another problem, in the context of inheritance, behavioral compatibility may be hard to arrive at, and hence the notion of subtype (which roughly corresponds with the subset relation) may be too restrictive. In practice, we may further encounter one-of-a-kind objects, for which it is simply cumbersome to construct an independent class. In a by now classical paper, [Lieber] proposes the use of prototypes instead of classes. The notion of prototypes (or exemplars) has been used in cognitive psychology to explain the incremental nature of concept learning. As [Lieber] notes, the philosophical distinction between prototypes (which provide a representative example of an object) and classes (which characterize a set of similar objects) may have important pragmatical consequences as it concerns the incremental definition of (hierarchies of) related objects. First, it is (claims Lieberman, 1986) more natural to start from a concrete example than to start from an abstract characterization as given by a class. And secondly, sharing information between prototypes and clones (that is, modified copies) thereof is far more flexible than the rather static means of sharing code as supported by the class inheritance mechanism. Code sharing by inheritance may be characterized as creation time sharing, which in this respect is similar to creating a copy of the object by cloning. In addition, prototypes may also support lifetime resource sharing by means of delegation. In principle, delegation is nothing but the forwarding of a message. However, in contrast to the forwarding mechanism as described in sections delegation-in-Java and hush-idioms, delegation in the context of prototypes does not change implicit self-reference to the forwarding object. In other words, when delegating a message to a parent object, the context of answering the message remains the same, as if the forwarding object answers the request directly. See slide 5-prototypes.

Prototypes -- exemplars

cloning -- creation time sharing
delegation -- lifetime sharing

slide: Prototypes

An almost classical example used to illustrate prototypical programming is the example of a turtle object that delegates its request to move itself to a pen object (which has x and y coordinate attributes and a move method). The flexibility of delegation becomes apparent when we define a number of turtle objects by cloning the pen object and adding an y coordinate private to each turtle. In contrast to derivation by inheritance, the x coordinate of the pen object is shared dynamically. When changing the value of x in one of the turtle objects, all the turtle objects will be affected. Evidently, this allows considerable (and sometimes unwished for) flexibility. However, for applications (such as multimedia systems) such flexibility may be desirable.

Design issues

Strictly speaking, prototype-based delegation is not stronger than forwarding in languages supporting classes and inheritance. In [Dony], a taxonomy of prototype-based languages is given. (This taxonomy has been partly implemented in Smalltalk. The implementation, however, employs so-called class-variables, which are not unproblematic themselves. See section meta.) One of the principal advantages of prototype-based languages is that they offer a consistent yet simple model of programming, consisting of objects, cloning and delegation. Yet, when designing a prototype-based language, a number of design decisions must be made (as reflected in the taxonomy given in Dony {\it et al.}, 1992). These issues concern the representation of the state of an object, how objects are created and the way in which delegation is handled. See slide 5-proto.

State

slots -- parents
variables and methods

Creation

shallow cloning
deep cloning

Delegation

implicit delegation
explicit delegation

slide: Prototypes -- state, creation, delegation

The basic prototype model only features slots which may store either a value or a piece of code that may be executed as a method. Alternatively, a distinction may be made between variables and methods. In both cases, late binding must be employed to access a value. In contrast, instance variable bindings in class-based languages are usually resolved statically. When creating a new object by cloning an existing object, we have the choice between deep copying and shallow copying. Only shallow copying, however, allows lifetime sharing (since deep copying results in a replica at creation time). Shallow copying is thus the obvious choice. Finally, delegation is usually handled implicitly, for instance by means of a special parent slot, indicating the ancestor of the object (which may be changed dynamically). Alternatively, it may be required to indicate delegation explicitly for each method. This gives a programmer more flexibility since it allows an object to have multiple ancestors, but at the price of an increase in notational complexity. Explicit delegation, by the way, most closely resembles the use of forwarding in class-based systems. One of the, as yet, unresolved problems of delegation-based computing is how to deal with what [Dony] call split objects. An object may (internally) consist of a large number of (smaller) objects that are linked to each other by the delegation relation. It is not clear how to address such a complex object as a single entity. Also, the existence of a large number of small objects that communicate by message passing may impose severe performance penalties.

Implementation techniques -- Self

A major concern of software developers is (often) the runtime efficiency of the system developed. An order of magnitude difference in execution speed may, indeed, mean the difference between acceptance and rejection.

Improving performance

special-purpose hardware
hybrid languages
static typing
dynamic compilation

slide: Improving performance

There are a number of ways in which to improve on the runtime efficiency of programs, including object-oriented programs. For example, [Ungar92] mention the reliance on special-purpose hardware (which thus far has been rapidly overtaken by new general-purpose processor technology), the use of hybrid languages (which are considered error-prone), static typing (which for object-oriented programming provides only a partial solution) and dynamic compilation (which has been successfully applied for Self). See slide 5-opt. As for the use of hybrid languages, of which C++ is an example, the apparent impurity of such an approach may (to my mind) even be beneficial in some cases. However, the programmer is required to deal more explicitly with the implementation features of the language than may be desirable. In general, both with respect to reliability and efficiency, statically typed languages have a distinct advantage over dynamically typed (interpreted) languages. Yet, for the purpose of fast prototyping, interpreted languages (like Smalltalk) offer an advantage in terms of development time and flexibility. Moreover, the use of (polymorphic) virtual functions and dynamic binding necessitate additional dynamic runtime support (that is not needed in strictly procedural languages). Clever compilation reduces the overhead (even in the case of multiple inheritance) to one or two additional indirections.

Dynamic compilation

The language Self is quite pure and simple in design. It supports objects with slots (that may contain both values and code, representing methods), shallow cloning, and implicit delegation (via a designated parent slot). Moreover, the developers of Self have introduced a number of techniques to improve the efficiency of prototype-based computing.

Self -- prototypes

- objects, cloning, delegation

Dynamic compilation -- type information

customized compilation
message inlining
lazy compilation
message splitting

slide: Dynamic compilation -- Self

The optimization techniques are based on dynamic compilation, a technique that resembles the partial evaluation techniques employed in functional and logic programming. Dynamic compilation employs the type information gathered during the computation to improve the efficiency of message passing.

Whenever a method is repeatedly invoked, the address of the recipient object may be backpatched in the caller. In some cases, even the result may be inlined to replace the request. Both techniques make it appear that message passing takes place, but at a much lower price. More complicated techniques, involving lazy compilation (by delaying the compilation of infrequently visited code) and message splitting (involving a dataflow analysis and the reduction of redundancies) may be applied to achieve more optimal results.

Benchmark tests have indicated a significant improvement in execution speed (up to 60% of optimized C code) for cases where type information could be dynamically obtained. The reader is referred to [Ungar92] for further details.

[] readme course preface 1 2 3 4 5 6 7 8 9 10 11 12 appendix lectures resources

eliens@cs.vu.nl

draft version 0.1 (15/7/2001)