Second Generation Object Models

ABSTRACT

1 INTRODUCTION

The object-oriented approach seeks a clean demarcation between the external semantics of an object and its internal implementation. External semantics are expressed entirely in terms of the operational interfaces of objects, i.e., the operators which may be applied to them. Applications which respect the object-oriented discipline only access objects by means of these operators, and are in no way aware of the implementation. Such applications can transparently be used with objects having different implementations, or whose implementations change.

Objects also have state, in the sense that information asserted about them is remembered for future use. Historically, object state is typically specified as a set of instance variables associated with the object. Similar formulations express this as a tuple or record whose elements correspond to the values of instance variables.

We thus get an image of an object as an encapsulated chunk of data. The sense of encapsulation is reinforced by the messaging paradigm: an operator is described as being sent to a single receiver. One can then think of an operator as belonging to a single object, and the method (a procedure which implements the requested operation) can then also be thought of as being in the object.

Thus an object has been characterized as something which contains data and to which messages can be sent. This capsule view has an intuitive appeal, being easy to grasp and relatively easy to implement. It also provides a simple foundation for the design of other facilities, such as security, versioning, distribution, concurrency control, export, and so on.

So, is there a problem? Yes. The capsule view of an object's data, if taken too literally, precludes certain implementation options, making the object too implementation-dependent. It certainly isn't required by the abstraction principle: applications don't care how the underlying data is organized, so long as the operational interface is supported.

The capsule view also encourages the object to be taken as the unit of scoping for the above-mentioned facilities. It then becomes difficult to provide such capabilities as different authorizations to different properties of an object, distribution of an object's properties over different sites, applications accessing different properties of an object without being in contention, exporting different views of an object, and so on.

The capsule view of data even has subtle implications for the semantics of complex objects, extensibility, multiple typing, and object identity.

Similarly, the messaging paradigm precludes or complicates type checking and polymorphism for multi-operand operators.

The capsule view of object data and operators characterizes what we may call first-generation object models, exemplified by Smalltalk [GR] and C++ [St]. Second generation models generalize this in two ways:

• The state of an object is treated as a requirement to remember asserted information about an object, without prescribing storage constructs. The behavior of operators can be described in terms of their effects on other operators, in the style of abstract data types.
• Operators may be defined on one or more operands. To the extent that there is a sense of belonging, operators can be thought of as jointly owned by their operands.

The other main principles of object orientation endure in much the same form [A+, K2]: identity, abstraction, data hiding, classification, generalization, inheritance, and polymorphism.

2 THE EVOLVING CONCEPT OF STATE

2.1 The First-Generation View

The state of a first-generation object is typically modeled as a set of instance variables, allocated in the image of a template associated with a class. Similar formulations express this as a tuple or record whose elements correspond to the values of instance variables. Though rarely articulated, the following assumptions often follow:

• The state of an object corresponds to stored data.
• The stored states of objects are disjoint from each other.
• The state of an object is localized.
• The state of an object has a stable form.

2.1.1 Stored Data

The correspondence to stored data is imperfect. Different data might be stored for different implementations of the same operational interface.

Some assertable information need not be stored: the radius, diameter, and circumference of a circle might all be asserted, but only one needs to be stored. Which one(s) is a matter of implementation, which should be free to change over time, or at different sites, for performance tuning.

Conversely, some information that is stored may not be assertable, being stored only to enhance the efficiency of data retrieval by such implementation techniques as caching, materialized views, and forward chaining. A person's age might be recomputed from his birthday on every request, or it might be stored in an instance variable. The distinction should have no bearing on the definition of the object, and again should be tunable.

2.1.2 Disjointness

State variables, or tuples, belonging exclusively to one object or another imply a partitioning of storage among objects. This presumed disjointness of object states unnecessarily constrains the implementation of relationships and inverses.

A first-generation definition of a graph would require that a node "contains" the edges that terminate there, or an edge "contains" its terminal nodes, or both redundantly. There is no option to maintain the graph connections neutrally in some shared mechanism, such as a relation. (While such a neutral form could be realized by defining connections as objects in their own right, it doesn't seem right to require this just to achieve a certain implementation structure.)

2.1.3 Localization

The contiguity of state variables (especially when defined by a template for a class) and the unity of a tuple suggest that the state of an object exists entirely in one place. It doesn't matter exactly what we mean by a "place"; it could be a machine, or a node in a network, or a name space, or some other unit of locality.

Such localization unduly constrains the capabilities of an object system. It seems perfectly reasonable to allow different operations on an object to be supported at different places, with corresponding distribution and possible replication of the supporting "state" information. For example, the shape of an airplane wing might be maintained at one place and its manufacturing cost at another. Routing of messages need not be guided solely by the identity of the recipient; it may be appropriate to route different messages to different places for the same object.

Localization of state information might simplify the design of message routing, authorization, locking, and similar facilities - but it's not consistent with the kind of location transparency that should be afforded the user.

2.1.4 Stability of Form

2.1.5 Objects and the Storage Resource

First-generation concepts of object existence and identity may be too closely linked to a particular approach to storage management.

What does it mean to create an object? Operational semantics are generally expressed in terms of a creation operator, applied to a type of which the object is to be an instance. Information about that object can be asserted at the time of creation or afterwards.

The operational consequences:

• There is now a valid mechanism for referring to the object. For example, the creation operator might return an object identifier which can be used in subsequent operations, perhaps being held as the value of some variable.
• Operations can be applied to the object, asserting or retrieving information about that object, and perhaps about other objects as well. Some such operations may be handled with the create operation to provide initial information about the object.
• It can be included in operations which assert information about other objects. That is, it can be the value of properties of other objects.
• It can occur among the results returned by applying operations.

The operational consequences of destroying an object are analogous:

• Mechanisms for referring to the object are rendered invalid. E.g., its object identifier is no longer valid.
• It is no longer valid to apply operations to the object. Hence it is no longer useful to remember assertions about the object.
• The object can no longer occur among the results returned by applying operations. Information involving the object must effectively be retracted; it is no longer useful to remember any information involving the object.

Deletion of an object may render other objects "unreachable", i.e., there are no longer any operations which return these objects. For example, such objects may previously have only occurred in the results of operations applied to the deleted object. It is no longer useful to remember the existence of such unreachable objects or any information involving them. Operationally, they are as good as deleted. This is a recursive notion which may in turn render other objects unreachable.

Unreachable objects are, in effect, the same as deleted objects. Actual detection and automatic deletion of unreachable objects is often implemented in order to conserve the storage resource. This automatic deletion of unreachable objects is one meaning of the term "garbage collection".

We can imagine several implementation scenarios for managing the storage resource for an object. A common implementation of first-generation models allocates space at object creation to hold information for the object, formatted in the image of a template associated with the type under which the object was created. Space is reserved for recording various assertions, which might be filled in when the object is created or later. Object deletion deallocates and recovers this chunk of space.

Storage allocation and deallocation are thus primarily associated with object creation and deletion. However, other operations may also require storage management activity:

• Changing information values:

  Storage may have to be allocated when a value changes from a very small number (or string or set) to a very large number (or string or set), and deallocated in the inverse case. Negative assertions, i.e., retractions, could cause value space to shrink. Such retractions may occur implicitly upon deletion of an object which is the value of some properties of other objects.

• Extensible types and dynamic typing:

  If supported, the addition or removal of operators for types, or the addition or removal of types for objects, also involve storage management. Space may have to be allocated for the values of new operators that become applicable to an object, due either to extension of a type or acquisition of a new type. Space is deallocated in the inverse cases.

Recovering the storage resource liberated by deleting objects or by shortening values and sets in other objects is another meaning of the term "garbage collection".

That scenario supports a first-generation view of state, treating objects as records or tuples, presuming object state to be localized and disjoint.

There are alternative scenarios which allocate space more dynamically. At minimum, object creation might in itself do no more than validate and return a new object identifier. Space could be dynamically allocated as needed to record assertions, and recovered for retractions.

2.1.6 Corollaries

We've mentioned some consequences of the first-generation philosophy of storage management. Semantic implications include localization of objects, and reluctance to support extensible types or dynamic typing.

Reluctance to support dynamic typing leads to reluctance to support static multiple typing as well, i.e., allowing an object to be a direct instance of multiple types (something might be both a document and a product, with neither being a subtype of the other). Multiple inheritance - a type having several supertypes - seems to be tolerable; having to establish composite templates seems acceptable when types are defined, but not when instances are created.

Other consequences are more subtle. Pre-allocation of templated space may depend on assumptions about uniformity or predictability of value sizes, in turn leading to presumptions about fixed lengths for object identifiers.

This in turn complicates the semantics of sets as objects (and also the semantics of large literal values, for much the same reasons). In order to have the option to treat sets extensionally, i.e., as though their identity was determined by their membership, such sets ought to behave as though their object identifiers consisted of a canonically ordered list of their members. Then equality of two such sets would simply be established by comparing their oid's. This approach is, of course, impractical to implement. The need to implement set identifiers in short strings leads to thinking of those short strings as oid's, which leads to thinking of the sets as being intensional, their identity being independent of their membership.

This in turn gives rise to the distinction between "shallow equality" of sets based on matching oid's and "deep equality" based on matching membership. And this in turn is generalized to distinguish shallow and deep equality for any object, based on the presumption of an inherent content concept for objects.

We also make too much of the metaphor of containment in modeling complex objects, which are made up of other objects. We seem to feel that if one object is part of another, as a diagram is part of a document, then the space occupied by the diagram should be embedded in the space occupied by the document. This in turn makes us reluctant to support shared sub-objects; if the diagram is used in two documents, we don't know readily know how to make it be in two places at the same time.

2.2 The Second-Generation View

2.2.1 Memory of Assertions

The essence of object state is memory of asserted information. The semantics of state are describable entirely in terms of operational interfaces, without recourse to internal constructs such as state variables.

Operations having the effect of assertions can be described by their effect on other operations, in the spirit of abstract data types. The effect of Set-Birthday alters the future results of Get-Birthday and Get-Age. The effect of Connect(edge,node) alters the future results of Get-Nodes(edge) and Get-Edges(node).

The nature of object state is implicit in the lingering effect of such operations. A more precise definition of state may be difficult to come by. It may be the current value of all operations applicable to an object; it may be the current value of operations that directly test assertable information. Is age part of a person's state, if it is determined from birthdate? Does state include the values of operations that take other arguments as well? If a document has different lengths in different languages, is its length part of the state of the document?

2.2.2 Explicit and Implicit Methods

Implementation has to get to stored data eventually. In second-generation models, instance variables are internalized from the object abstraction into the implementation. Second-generation models are less prescriptive about structure, leaving it more as local options for implementation in whatever sort of structures are available and judged to be efficient.

Implementations are expressed in methods, which in first-generation models are explicitly specified procedures. In second-generation models, implementations can also be specified as mappings to underlying storage structures, implicitly defining the corresponding methods in terms of access to the structures.

2.2.3 The Content of Objects

In the second-generation view, objects don't have an inherent notion of "content", although there may be fairly natural defaults for some objects. The content concept for documents may appear self-evident - unless the documents have different texts in different languages. Or we may be dealing with the existence of a document even before it has any text. On the other hand, there is no obvious notion of content for a person. Or an airplane: do we mean its passengers and cargo, or the components of which it is built, or its flight log, or its manufacturing and testing history, or its design drawings, or what?

Without an inherent notion of content, objects in themselves do not make a natural unit of scoping for authorization, locking, copying, or export (e.g., for display or for shipment across a network). They are not natural units in any case. We can imagine differential authorization to different pieces of information about an object; we can imagine applications operating on different information about an object without being in contention (locking each other out); we can imagine different subsets of the information about an object being exported.

2.2.4 Where's the Object?

If we can't point to an object as occupying some definite chunk of storage, then where's the object? How do we know it exists?

A user knows an object exists because references to the object are valid, and operations can be applied to it. The user doesn't care where an object is, only that operations applied to it behave appropriately.

When a user really "sees" something on a display screen, he sees a "presentation object" as a specified formatting of a specified scope of information, i.e., a view. It may denote some other object in the same way that a photograph denotes its subject, but it is a different object. The object on the screen may be operated on, e.g., moved or resized, independently of operations on the object it denotes. Our obligation is to collect and export such a presentation object on demand, but we can do it any way our wits contrive. Of course, we'll do it more efficiently if the presentation object corresponds closely to stored data structures - but that's a tuning option, which may require load balancing among conflicting requirements.

2.2.5 Complex Objects

How does a user know that a diagram is part of a document?

• When he asks for the parts of the document, the diagram is included.
• When he does certain things to the document, like destroying or copying or displaying it, the same thing happens to the diagram.

We can define and do all those things operationally, without necessarily embedding the diagram into the storage space occupied by the document. Of course, we'll try to implement it that way whenever we can, to do things faster.

2.2.6 Separation of Type and Class

First-generation models cleanly distinguish interface from implementation on the processing side, by distinguishing between the operations invoked (messages sent) by users and the methods which implement them. The corresponding distinction is not made for data.

To talk about this, we need the terms "type" and "class". Of the many definitions extant for these two terms, we choose the following:

• Type is associated with the external semantics of objects. Instances of the same type share a common operational interface.
• Class is associated with implementation. Instances of the same class share a common implementation. Several classes may implement the same type.

A class typically specifies a set of methods as implementations for a set of operators (messages), and a set of instance variables or a tuple template as the format for instance state data. Different classes may provide different methods and instance variables to implement the same operations. Abstraction is served by requiring applications to use the specified operators rather than manipulating the state data directly.

However, first-generation languages do breach the abstraction barrier in some respects. Applications create objects as instances of classes, make decisions based on the classes of objects, and iterate over instances of classes. Such applications are implementation-dependent, since they cannot be freely used with different classes implementing the same operational interfaces.

Second-generation languages would do all these things in terms of types rather than classes. Clearly, when an object is created, the system must know in which class it is to be implemented. However, rather than being specified explicitly by the application, the class of a new object would be deducible from the type under which the application creates the object. Typically the object is being created within some scope (machine, database, etc.) in which there is only one possible implementation locally available. Thus the choice of class might be embedded in the local methods supporting the creation operators for various types.

3 THE EVOLVING CONCEPTS OF MESSAGES AND OPERATORS

In first-generation object models, a message is sent to a single recipient object, to be serviced by a method "contained" in the object. In second-generation object models, an operator is applied to one or more operand objects.

Since messages can generally include other objects as auxiliary arguments, the difference might appear to be purely syntactic: one of the operands of an operator can be distinguished as the recipient, with the others corresponding to arguments. There is a simple syntactic correspondence between a message taking one argument

document.print(device)

and a binary operation

print(document,device).

3.1 Operational Interfaces and Type Checking

The operational interface of an object describes the applicability of messages (operators) to the object. First-generation models characterize an object by the messages it may receive, but not by its ability to be an argument for other messages. For instance, if a document can receive a message like

document.print(device),

the document's operational interface will say that it can receive a print message, but the device's operational interface says nothing about its ability to serve as an argument of the print message.

3.2 Symmetry

Many operators naturally take multiple operands, and it is quite artificial to require one of them to serve as the principle recipient. Examples abound in arithmetic, logic, and set theory, just for starters.

Many operators deal with relationships among objects: connecting nodes and edges, connecting wires and pins, printing documents on devices, computing registration fees for students in courses, counting parts in warehouses, or components in assemblies, and so on. No useful purpose is served by requiring the message to go to the node rather than the edge, to the wire rather than the pin, etc.

3.3 Ownership

The main hangup seems to be a vestige of encapsulation, a feeling that each message and method needs to have a home, to be owned by some object. Some models, and most implementations, generalize this a bit so that messages and methods belong to types and classes, respectively, rather than to individual objects. But there is still an assumption of a single owner.

Who owns a multi-operand operator or method?

3.4 Polymorphism and Inheritance

Polymorphism and inheritance in first-generation models are defined in terms of message recipients. For the message

document.print(device),

different methods can be provided for different subclasses of documents, but no corresponding provision is made for subclasses of devices.

3.5 A Role Model of Operational Interfaces

In second-generation models, the operational interface of an object is expressed in terms of the roles it may play in various operations, rather than directly in terms of the operations (messages) which may be applied to it. Thus the role concept is itself formally introduced into the object model.

Consider the operation

Set-Fare(Origin City, Destination City, Fare Integer).

It is not sufficient to characterize the operational interfaces of cities and integers simply by saying that Set-Fare is applicable to them. That fails to express the illegality of an integer as the first operand or a city as the third.

The operational interface of a city should be characterized by the fact that it may occur as the first or second operand of Set-Fare. The terms "Origin" and "Destination" label these two roles. They serve as intermediaries linking types with operations. That is, the Origin role belongs to the Set-Fare operation, and the role may be played by objects of type City.

Roles bear some resemblance to types, in the sense that we can say that certain cities are origins, or are destinations. The difference here is between pre-condition and post-condition. It is a prerequisite that an object be a city in order to be the first operand of Set-Fare; the object becomes an origin as a consequence. The fact that the object is an origin is not something which can be type-checked a priori in order to determine the applicability of Set-Fare. In this sense, roles are not directly relevant to type checking. (The role may become a type for type-checking other operators. E.g., it might be a prerequisite for some other operator that the object be playing the role of an origin.)

Roles might be labeled in various ways. Usually the labels are not globally unique, but only unique within a given operator. Origin and Destination might also be roles played by nodes in a graph. Roles might simply be numbered, e.g., the first and second roles. Roles could also be labeled with their associated types, if unambiguous, i.e., if the operator only has one role of that type.

With more complex aggregate operands, roles could even label the internal portions of aggregates where types of objects may occur. For example, an operator definition of the form

Op-1: L1 List of (I1 Integer, C1 City, S1 Set of C2 City)

means that cities can play roles C1 and C2. In a list which is a valid operand to Op-1, a city may occur as the second element in the list or as a member of a set which is the third element of the list.

Thus the operational interface of an object is characterized by a set of roles it may play, linking the object indirectly to the operations in which it may play those roles. By extension, the operational interface conferred by a type is characterized by such a set of roles. Instances of the type may play those roles.

An operator does not belong exclusively to one type. It may be linked to one or more types via its roles.

Unary operators, having only one role, do in effect belong to only one type. In this sense, unary operators correspond to messages in first-generation object models. However, auxiliary arguments of messages are still inadequately accounted for in first-generation models.

The same sort of role structure can be used to link methods and classes.

4 CONCLUSIONS

Though it is the next generation of information processing, we can already see beyond the first generation of object orientation. The object model is evolving. We may well interpret "object orientation" as signifying a direction toward a goal as yet unattained.

Second-generation models generalize the treatment of object state and messaging, modifying the encapsulation concept. Second-generation object models preserve the following principles of object orientation:

• Object identity: for intensional objects, whether two references are to the same object is independent of any information known about the object.
• Abstraction: users only know objects by the operations applicable to them, without knowledge of internal structure or other aspects of implementation.
• Data hiding: certain information is hidden from object users, being relevant only to the implementations of objects. (This could be seen as information about objects at a lower level of abstraction which implement objects at a higher level.)
• Classification: objects are grouped into types, such that objects of the same type share a common operational interface, and into classes, such that objects of the same class share a common implementation.
• Generalization and inheritance: there is a subtype mechanism such that the operational interface conferred by a type is also conferred by its subtypes, and a similar subclass mechanism.
• Polymorphism: the same operation may have different behaviors and implementations for different types of objects.

Second-generation models also have these characteristics:

• The state of an object reflects the need to remember asserted information, without being tied to any structural or storage constructs.
• The behaviors of assertions can be described in terms of their effects on other operations, in the spirit of abstract data types.
• Operators may be applied to one or more operands.
• Operational interfaces of objects are defined in terms of the roles they may play in various operators.
• Types correspond to groups of objects which share common operational interfaces, i.e., which may play the same roles in operators.
• Operators are owned by one or more types, corresponding to the roles of the operators. Methods are similarly linked to classes by roles. The algorithms for inheritance and polymorphism are therefore more complicated.
• Methods define implementations either as explicit procedures or implicitly via mappings to stored data structures.
• Classes correspond to groups of objects which share common implementations, i.e., which may play the same roles in methods.
• Classes are not visible to object users, but only to object implementers.
• Scopes of information for copying, export, authorization, and concurrency can be defined in terms of views.

The encapsulation principle takes on different nuances. Abstraction and hiding still, in a sense, "encapsulate" the form and content of implementations; there is a "shell" which object users cannot penetrate.

That shell is a collective one covering implementations of all objects. There is less of a sense of encapsulating individual objects as packages or chunks of data and operations. The states of several objects may share pieces of stored data, and the stored data for an object may be distributed over several places. An operator is not necessarily contained in an individual object or type, but might be jointly owned by a set of owners corresponding to the operands of the operator.

When a "capsule" is needed, view constructs can define units of scoping for such purposes as copying, export, authorization, and concurrency.

Second-generation models adhere more strictly to the abstraction principle, by separating state from structure and storage. Freed from constraints of the storage metaphor, second-generation models are more likely to support extensible types, dynamic typing, multiple typing, and sophisticated semantics for complex objects.

5 ACKNOWLEDGMENTS

6 REFERENCES

[A+] M. Atkinson, F. Bancilhon, D. DeWitt, D. Maier, S. Zdonik, "The object-oriented database system manifesto (a political pamphlet)", Working paper, November 1988.

[B+] D.G. Bobrow, L. DeMichiel, R.P. Gabriel, G. Kiczales, D. Moon, S. Keene, "The Common Lisp Objects System Specification: Chapters 1 and 2", Technical Report 88-002R, X3J13 standards committee document, 1988.

[BW] Kim B. Bruce and Peter Wegner, "An Algebraic Model of Subtypes in Object-Oriented Languages", working paper, May 1986.

[F1] D.H. Fishman, et al, "Iris: An Object-Oriented Database Management System", ACM Transactions on Office Information Systems, Volume 5 Number 1, January 1987. Also in [ZM1].

[F2] Dan Fishman, et al, "Overview of the Iris DBMS", Object-Oriented Concepts, Databases, and Applications, Kim and Lochovsky, eds, Addison-Wesley, 1989.

[GT] J.A. Goguen and J. Tardo, "An Introduction to OBJ: A Language for Writing and Testing Software Specifications", Specification of Reliable Software, IEEE, 1979

[GR] A. Goldberg and D. Robson, Smalltalk-80: The Language And Its Implementation, Addison-Wesley, 1983.

[HZ1] Sandra Heiler and Stanley Zdonik, "FUGUE: A Model for Engineering Information Systems and Other Baroque Applications", Proc. Third Intl Conf on Data and Knowledge Bases, Jerusalem, 1988.

[HZ2] Sandra Heiler and Stanley Zdonik, "Object Views: Extending the Vision", Proc. Sixth Intl Conf on Data Engineering, Los Angeles, Feb. 1990.