William Kent
Database Technology Department
Hewlett-Packard Laboratories
Palo Alto, California
April, 1994
> ***PROLOGUE*** . . . 7
> 1 OBJECTIVES AND STATUS . . . 7
> 2 ORGANIZING PRINCIPLES . . . 7
>> 2.1 Isolation of Object Users From Object
Implementation . . . 7
>> 2.2 Behavioral Criteria . . . 8
>> 2.3 Fundamental Concepts . . . 8
>>> 2.3.1 Object Systems . . . 8
>>> 2.3.2 User Perspective . . . 9
>>> 2.3.3 Implementation Perspective . . . 10
> ***OBJECT SYSTEMS*** . . . 10
> 3 COMPUTATIONAL SYSTEMS . . . 10
>> 3.1 Illusion and Metaphor . . . 11
>> 3.2 Interfaces and Symbols . . . 11
>> 3.3 Requests and Expressions . . . 12
>> 3.4 Operator Expressions . . . 13
>> 3.5 What Symbols Mean . . . 14
> 4 INTRODUCTION TO OBJECT SYSTEMS . . . 15
>> 4.1 The Computational Context . . . 15
>>> 4.1.1 Interfaces to a Black Box . . . 15
>>> 4.1.2 Symbols . . . 16
>> 4.1 Object Systems . . . 17
>> 4.3 Object System Interfaces . . . 17
>> 4.4 Facets and Spheres . . . 18
> ***A GENERAL MODEL: USER PERSPECTIVE*** . . . 19
> 5 INTRODUCTION . . . 19
> 6 REQUESTS . . . 20
>> 6.1 Results and Conditions . . . 20
>> 6.2 Expressions . . . 21
>> 6.3 Performers of Requests . . . 22
>> 6.4 Update and State . . . 22
>>> 6.4.1 Updating Variables . . . 23
>>> 6.4.2 Updating Operations . . . 23
>>> 6.4.3 Changeable, Updatable and Recorded
Properties, and State . . . 23
> 7 OBJECT EXISTENCE AND IDENTITY . . . 24
>> 7.1 "Exists" vs. "Known" .
. . 24
>> 7.2 How Objects Become Known . . . 25
>> 7.3 Equality Axioms . . . 25
>> 7.4 Creating and Initializing Objects . . . 26
> 8 INFORMATION FOR REQUEST PLANNING . . . 26
> 9 TYPES . . . 27
>> 9.1 The Nature and Role of Types . . . 27
>> 9.2 Non-Materialized and Materialized Types . .
. 28
>>> 9.2.1 Materialized Types for Numbers . .
. 28
>>> 9.2.2 Ideal and Effective Types . . . 29
>>>> 9.2.2.1 Ideal Non-Materialized
Numeric Types . . . 30
>>>> 9.2.2.2 Ideal Materialized Numeric
Types . . . 30
>>>> 9.2.2.3 Effective Materialized
Numeric Types . . . 30
>>>> 9.2.2.4 Effective Non-Materialized
Numeric Types . . . 30
> 10 OPERATIONS . . . 32
>> 10.1 Specific and Generic Operations . . . 32
>> 10.2 Specific Operations . . . 32
>>> 10.2.1 Signatures . . . 33
>>> 10.2.2 Behavior Specifications . . . 33
>>>> 10.2.2.1 Behavior vs.
Implementation . . . 33
>>>> 10.2.2.2 Update Specifications . .
. 34
>> 10.3 Generic Operations and Inheritance . . .
35
>>> 10.3.1 Overview . . . 35
>>> 10.3.2 Inheritance . . . 36
>>> 10.3.3 Default Behavior of Generic
Operations . . . 36
>>> 10.3.4 Defined Behaviors . . . 37
>> 10.4 Additional Behaviors . . . 37
>>> 10.4.1 Casting (Substitutability) and
Its Uses . . . 38
>>>> 10.4.1.1 Type Casting . . . 38
>>>> 10.4.1.2 Intensional Aggregates .
. . 38
>>>> 10.4.1.3 Type Extents . . . 38
>>>> 10.4.1.4 Type Substitutability . .
. 38
>>> 10.4.2 Extending Non-Aggregate
Operations to Aggregate Operations . . . 38
>> 10.5 The Association Between Types and
Operations . . . 39
>> 10.6 Operations Involving Types and Operations
. . . 39
>>> 10.6.1 Populating Types: Asserted and
Derived Types . . . 39
>>> 10.6.2 Disjoint Types . . . 40
> 11 AGGREGATES . . . 41
>> 11.1 Unstructured Aggregates: Bags and Sets .
. . 41
>>> 11.1.1 Instances . . . 41
>>> 11.1.2 Instance Designators . . . 42
>>> 11.1.3 Types and Type Designators . . .
43
>> 11.2 Indexed Aggregates . . . 44
>>> 11.2.1 Instances . . . 44
>>> 11.2.2 Instance Designators . . . 45
>>>> 11.2.2.1 Sequence Designator . . .
45
>>>> 11.2.2.2 Compact Sequence
Designator . . . 46
>>> 11.2.3 Types and Type Designators . . .
46
>>>> 11.2.3.1 Sequence and Tuple Types
. . . 46
>> 11.3 Empty Aggregates . . . 47
>> 11.4 Type Constraints on Aggregates . . . 47
>> 11.5 Aggregate Subtypes . . . 48
>> 11.6 Arithmetic Semantics of Aggregate
Operations . . . 48
>> 11.7 Extensional and Intensional Aggregates .
. . 49
> 12 QUERY . . . 50
>> 12.1 Arithmetic Semantics . . . 51
>> 12.2 Basic Form . . . 51
>> 12.3 Group-By . . . 52
>> 12.4 Query Transformations . . . 54
> 13 OTHER INTERESTING OBJECTS . . . 55
>> 13.1 Carriers and Cargos . . . 55
>> 13.2 User-Defined Literals . . . 55
>>> 13.2.1 Subtypes of Basic Literals . . .
56
>> 13.3 Factoids . . . 56
>> 13.4 Objects With Content . . . 57
>> 13.5 Objects With Location . . . 57
>> 13.6 Measured Quantities . . . 57
>>> 13.6.1 Relevance of Non-Materialized and
Materialized Types . . . 58
>>> 13.6.2 Use and Mention of Quantity
Designators . . . 58
>>> 13.6.3 An Interesting Analogy . . . 59
>>>> 13.6.3.1 Single Designation . . .
59
>>>> 13.6.3.2 Multiple Designations . .
. 60
>>>> 13.6.3.3 Conversions . . . 61
>>> 13.6.4 Another Analogy . . . 61
>> 13.7 Geometric Constructs . . . 62
>>> 13.7.1 Geometric Points . . . 62
>>> 13.7.2 Plane Figures . . . 63
> ***A GENERAL MODEL: IMPLEMENTATION PERSPECTIVE*** . .
. 63
> 14 INTRODUCTION . . . 63
> 15 CLASSES . . . 63
> 16 CHOOSING PERFORMERS . . . 64
> ***OTHER MODELS*** . . . 65
> 17 MESSAGING MODELS . . . 65
> 18 LINK/INTERACTION MODELS . . . 65
> 19 OSQL . . . 65
>> 19.1 Semantics . . . 65
>>> 19.1.1 Aggregates . . . 65
>>> 19.1.2 Query . . . 66
> 20 BASIC RELATIONAL MODEL . . . 66
>> 20.1 Semantics . . . 66
>>> 20.1.1 Tuple Tables . . . 66
>>> 20.1.2 Update . . . 67
>>> 20.1.3 Query . . . 67
>> 20.2 SQL Syntax . . . 68
> 21 OBJECT-ORIENTED RELATIONAL MODEL . . . 68
>> 21.1 Non-Tuple Tables . . . 69
>> 21.2 Comparison of Tuple- and Non-Tuple Tables
. . . 69
>> 21.3 Managing the Extent (Population) of a
Type: Table of ALL . . . 70
>> 21.4 SELECT * . . . 70
> ***MODEL DIFFERENCES*** . . . 71
> 22 DIMENSIONS OF DIFFERENCE . . . 71
>> 22.1 Performer and Participant Models . . . 71
>> 22.2 Addressing and Associative Models . . .
74
>>> 22.2.1 Objects in Space . . . 74
>> 22.3 Other Significant Differences . . . 75
> 23 WHY THE DIFFERENCES? . . . 76
> ***MODEL INTEROPERATION*** . . . 77
> 24 REQUIREMENTS . . . 77
>> 24.1 Cascading Interfaces . . . 77
>> 24.2 Dimensions of Interoperation . . . 79
> 25 EQUIVALENT FORMS . . . 80
>> 25.1 Messaging and Functional Syntax . . . 80
>> 25.2 Multiple Arguments vs. Sequences of
Arguments . . . 80
>> 25.3 Curried Equivalence . . . 80
>>> 25.3.1 Description . . . 80
>>> 25.3.2 Examples . . . 81
>>>> 25.3.2.1 Typing Operations . . .
81
>>>> 25.3.2.2 Attributes . . . 81
>>>> 25.3.2.3 Units of Measure and Data
Types . . . 81
>>>> 25.3.2.4 Schema Mismatch . . . 81
>>>> 25.3.2.5 A Universal Relation and
the Apply Operation . . . 81
>> 25.4 (Relational) Operation Families . . . 82
>>> 25.4.1 Description . . . 82
>>> 25.4.2 Uses . . . 82
>> 25.5 Extended Operation Families . . . 83
>> 25.6 Structural Coercions . . . 83
> 26 MULTI-FACETED OBJECT SYSTEMS . . . 83
>> 26.1 Facets, Spheres, and Environments . . .
83
>> 26.2 Interoperation of Diverse Models . . . 84
> ***DETAILS*** . . . 84
> 27 EXPRESSIONS . . . 84
>> 27.1 Variables . . . 84
>>> 27.1.1 Environments and Binding . . . 84
>>> 27.1.2 Declaration vs. Binding . . . 85
>>> 27.1.3 Comparison With Argumentless
Operations . . . 85
>> 27.2 Expression Evaluation and Operator
Application . . . 86
>>> 27.2.1 Overview . . . 86
>>> 27.2.2 Evaluate . . . 86
>>> 27.2.3 Apply . . . 87
> 28 SOME USEFUL OPERATIONS . . . 87
>> 28.1 Equality and Null . . . 88
>> 28.2 Membership and Inclusion . . . 88
>> 28.3 Profiles and Predicates . . . 88
>> 28.4 Logical Operations . . . 88
>> 28.5 Operation Composition . . . 89
>> 28.6 Quoting . . . 89
>> 28.7 Bag Operations . . . 89
>>> 28.7.1 Duplicate Elimination . . . 90
>>> 28.7.2 Union and Difference . . . 90
>>> 28.7.3 Cross-Products . . . 91
>>> 28.7.4 Bag Processors . . . 91
>> 28.8 Other Relational Operations . . . 93
>>> 28.8.1 Project . . . 93
>>> 28.8.2 Restrict (Select) . . . 93
>>> 28.8.3 Joins . . . 94
> 29 SOME USEFUL OBJECTS . . . 95
>> 29.1 Constants, Values, and Variables . . . 95
>> 29.2 Atomic Objects . . . 95
>> 29.3 Basic (Literal) Data Types . . . 95
>> 29.4 Null . . . 95
>> 29.5 Indexed Aggregates . . . 97
>>> 29.5.1 Compact Aggregate . . . 97
>>> 29.5.2 Sequences/Lists/Tuples . . . 97
>>> 29.5.3 0-Sequence . . . 98
>>> 29.5.4 Record . . . 98
>>> 29.5.5 Array . . . 98
>>> 29.5.6 Regular Bag . . . 98
> 30 SPECIFIED BEHAVIORS FOR GENERIC OPERATIONS . . .
98
>> 30.1 Application to Multidatabase Systems . .
. 101
>>> 30.1.1 Operation Merging for
Inconsistent Data . . . 101
>>> 30.1.2 Merging Equivalent Objects . . .
103
> 31 REFERENCES . . . 104
This document:
This draft is very much a skeleton of work in progress. Parts of it are fairly complete, parts are totally missing. Some of the missing material simply needs to be written, and some still requires a bit of invention and may even remain a speculative sketch. There are undoubtedly some inconsistencies. Readability still needs to be substantially improved, perhaps by changing the order of presentation and adding more motivational and illustrative material. The overall structure is itself negotiable.
The document presents a hopefully coherent set of semantic concepts. Notably absent at the moment is material on why these ideas are useful, how to realize them in practical languages and systems, and how they relate to current work. Many of the ideas presented here are obviously derived from other sources, though not yet so identified. All this work also remains to be done.
The problem of consistent terminology is worse in object orientation than in most other fields, and there are efforts under to way to correct this. If consistent terminology emerges in time, we will adopt it in this document. In the meantime, the best we can do is define our terms carefully here and try to use them consistently. Most readers will not be satisfied with all of our terminology. Be patient, and be warned: some terms may not mean what you think they do. Since nobody wants to read a glossary at the outset (and we haven't yet extracted a consolidated glossary anyhow), you will probably be surprised by some of the definitions you encounter after the terms have been used. Sorry about that.
This document rests on these organizing principles:
Perhaps the central organizing principle of object orientation, and this document, is the isolation of object users from object implementation. Applications which use objects in this fashion can operate with different and changing implementations, making such applications more portable and more reusable.
Underlying this is the perception of an object as something which gets used for some purpose, rather than as an active thing which does things in a system. This latter view reduces focus on the user perspective, and diminishes the role of the infrastructure. This difference may in itself account for pervasive differences in object models.
The implementation constructs which are hidden from users behind an object system interface include program code for executing requests, query processing and optimization, data structures, data placement and clustering, and pointers.
Much of the work in object orientation focuses on implementation aspects (complex data structures, messaging and dispatching paradigms, pointer management, garbage collection, query processing, etc.); it might be instructive for the reader to assess the extent to which this is so. This also raises an interesting question, couched in terms we won't define further: if a system appears to be object-oriented on the user side but not on the implementation side, or vice versa, is the system object-oriented?
The present document, in contrast, focuses primarily on the user side, taking special care that implementation considerations do not intrude.
Distinctions are made in the model only if they make a difference in the way something works. Constructs are not included, for example, simply because they reflect the way people might think about things. Thus, if one construct is different from another, then there must be some meaningful operation which behaves differently for the two.
The material presented here is developed top-down from a set of fundamental concepts, which are summarized below and elaborated in the rest of the document.
A computational system is a symbol processor with interfaces [Section 4.1].
Everything can ultimately be explained in terms of symbol processing.
Objects are managed by object systems [Section 4.1].
Object systems provide an infrastructure which provides such services as routing requests from requestors to performers, returning results, and resolving generic requests. Models vary in the extent of services provided by this infrastructure.
Object systems provide interfaces which isolate object users from implementations [Section 4.3].
Object model features can thus be partitioned into those relating to users and those relating to implementation. This document is biased toward a focus on the user side.
From the user perspective, everything that happens in an object system is the consequence of a request [Section 6].
We take a request-centered approach. Everything that happens in the object system is the consequence of a user making a request to the object system. The user might be a person or a program, or some other active agent such as a sensing device. The request might be initiated spontaneously from outside the object system, it might arise as the consequence of performing another request, or it might be triggered by other mechanisms such as a monitor or other event/condition/action mechanism.
Things we therefore have to describe include:
How requests work.
What facilities are provided to allow requests to achieve the user's goals.
How the user figures out what facilities are available so that he can formulate the appropriate requests. That's what a schema is for, supplementing a basic understanding of how the system works.
From the user perspective, it doesn't matter who performs a requested service [Section 6.3].
The essential effect of update is to alter the results of future requests [Section 6.4].
The concept of state is not uniquely defined from the user perspective [Section 6.4.3].
Objects "exist" so long as they are known to an object system [Section 7.1].
If an object system can provide the date on which a certain file was deleted, then that file object still exists as far as the object system is concerned. Certain operations may no longer be supported, such as modifying or displaying the contents of the file, and the file may no longer be present in any directory, but the object system can still respond to requests involving that file.
Similarly, if an object system can provide the date on which a certain building will be completed, as well as its location, height, and blueprints, then the building object exists even if construction has not yet begun.
We try to avoid dealing with "existence" in this document, and speak only of objects being known by an object system. Operations which purport to "create" or "destroy" objects in an object system should really be understood as "introducing" and "erasing" objects, i.e., making them known and unknown to the object system.
The management of object identity depends on how an object becomes known to an object system [Section 7.2].
We thus have eternal, mortal, and ephemeral objects.
The management of object identity should be consistent with the axioms of equality [Section 7.3].
Schema constructs such as types, operation definitions, and inheritance are provided for planning purposes, so that users can choose the appropriate requests to achieve their intended results [Section 8].
The operation referenced in a request may be either specific or generic [Section 10.1].
There are no inheritance issues or problems for specific operations. The complexities of inheritance and overloading arise only with generic operations.
Behavior specifications are distinct from implementation specifications [Section 10.2.2.1].
An operation might be exclusively or jointly owned [Section 10.5].
Aggregates can be described in terms of content and form [Section 11].
There's a difference between extensional and intensional aggregates [Section 11.7].
The semantics of queries should be defined in terms which do not depend on any particular internal model of query execution [Section 12.1].
Some objects have an implicit notion of "content" [Section 13.4].
But not all. For these objects, operations such as Move, Copy, and Display are meaningful.
Some objects have a location property [Section 13.5].
But not all. For these objects, operations such as Locate and Move are meaningful.
Null signifies nothing [Section 29.4].
Different instances of the same type may be implemented with different data structures or methods [Section 15].
A method might be exclusively or jointly owned.
Exclusively owned methods may be thought of as being "performed" by their owner (object).
(This section is not integrated smoothly with the subsequent material.)
I see this page on my computer screen. Is this document in the computer? If I break it open will I find a micro-dot somewhere that I can enlarge with a magnifying glass to see this very page? Not really. The chains of words and characters are strung out over various segments of main memory and my hard disk, being assembled with blinding speed for display on this screen whenever I want to see it.
Well, that's not exactly true, either. There aren't really any words or characters inside my machine. They are all encoded in these numbingly long and unreadable strings of ones and zeros like 110111001100111011110011... Some blindingly fast bit of software turns those into letters and words whenever we want to see things on a screen or a printed page.
Is that the truth? Well, not exactly. There are no ones and zeros in my computer. There are just these electrons flowing around in bits of silicon and copper, and magnetized spots on the surface of my disk. On some other disk there are just some minuscule patches of lightness and darkness. When these little bits of things are intense enough, they get to be called a "1", otherwise they are a "0".
Have we reached bottom yet? Probably not. A mathematical physicist would probably say that electrons and magnetism and light are anthropomorphized metaphors expressed in terms we can relate to. What's "really" there are arcane behaviors of energy that humans can't really comprehend, but only "describe" in unreadable formulas.
Ultimately what's "really" happening goes on in physical matter and energy. That's how things are recorded in storage media, that's what flows around and gets transformed during computation, that's what goes into a computer in terms of pushing keys, and that's what comes out of a computer in a way that reflects light energy into our eyes or sends sound energy to our ears so that we can read and hear it.
All our communication and computation facilities build metaphors on top of these...
My word processor behaves in such a way that I can think I am dealing with words on a page.
A relational database system lets its users think they are dealing with rows and columns.
A file system...
Sometimes these are piled up one on top of another.
Objects are shaped by the computational systems which manage them. A computational system is an abstraction which presents a user interface at which users make requests. Behind this interface lie a hidden internal processor (black box), as well as storage, communication and networking facilities.
A computational system is a symbol processor. A symbol might be anything that can pass across the user interface, or it might be something which can only occur in the internal processor without passing across the user interface. For our present purposes, it suffices to think of a symbol as a finite sequence of characters from some underlying character set. Symbols which can pass across the interface might be called visible, external, or language symbols. Symbols which cannot might be called internal, hidden, or opaque symbols.
Opaque symbols might include:
Everything that happens in the computational system is the result of a request, which causes a symbol to be evaluated. What does evaluation do? What can be evaluated? How do requests happen?
Evaluation might do one or more of the following:
(Note that an evaluation result in not automatically displayed, or returned across the interface; it might be an opaque symbol.)
An error-free evaluation is one which does not yield an error condition.
In a broad sense, any symbol (external, opaque, or a mixture) can be evaluated, though in extreme cases evaluation might yield an error condition, or it might simply return the original symbol unchanged. Evaluation of symbols which can be recognized as operator expressions (containing operator parts and operand parts) is quite complex, and will be discussed shortly. Other symbols can be characterized by the results of their error-free evaluation:
Expressions to be evaluated might enter across the user interface in external form, or they might be internally constructed, perhaps during the course of evaluating other expressions. It might be useful to assume that all expressions are evaluated in an internalized form, having the following characteristics:
(Such parsing, or internalization, might also do such things as replace constants with their values, but we will count that as part of the evaluation process.)
The simplest operator expression can be decomposed into a pair of values serving as the operator part and operand part, often denoted operator(operand). The dot-notation form operand.operator is also used.
The operator part is said to be applied to the operand part. In the simplest case, such application consists of finding the body of the operator part and executing it with the operand part as argument to yield consequences as described above. Expression evaluation is often more complicated for a number of reasons:
For example, there might be different tax formulas for different states, such that TaxFormula(state) returned the formula for the specified state. To compute the tax on a particular item purchased in that state, one could evaluate the expression TaxFormula(state)(item).
And an important special case of this occurs when the operand is a list, giving the effect of multiple operands. This is commonly written in the simplified form f(x,y,z).
This typically arises when several operations have the same name. There might be operations to Fire an employee, Fire a cannon, or Fire a rule in a rule-based system. The Area formula might be different for rectangles, squares, triangles, circles, and arbitrary polygons.
This is an extremely important aspect of object-oriented systems, but we will put it off for a while. For now we make the simplifying assumption that operations are uniquely named.
The most general form of an operator expression may involve a fairly complex grammar of possibly parenthesized operators and operands, allowing such things as x+(y-z). These can often be transformed into simple operator form in several ways, e.g.,
+(x,-(y,z)),
+(-(y,z),x).
While such expressions are important in programming language design and processing, they don't have any special significance for object systems. We will therefore limit our attention to the operator-operand form.
In what sense does a computational system "know" what a symbol means? Ultimately it doesn't, with denotation being in the mind of the observer. It doesn't "know" that Bill Clinton is the president of the United States, nor what it means to be president. But when a well-behaved computational system is presented with a symbol that we think denotes the appropriate question, it will respond with a symbol that we think denotes the appropriate answer.
However, there are certain operational ways in which we might characterize the "meaning" of a symbol in a computational system. One is in the results of evaluating the symbol. Thus if evaluation of a symbol x results in a symbol y, we can say that x "means" y at the time of evaluation.
Another aspect has to do with the behavior of operators applied to the symbol. The computational system "knows" what 1 means by virtue of the results returned by arithmetic operations applied to it.
Equality is a third manifestation, being an operator which has special significance with regard to the "meaning" of symbols. If the symbol x is "equal" to the symbol y, then the computational system at least appears to think they mean the same thing, even if it doesn't understand what they mean. But what determines whether Equal(x,y) is true? That's another complex topic.
This section briefly introduces the basic notion of object systems. We will later return to discuss multi-faceted object systems [Section 26].
A computational system is a symbol processor with interfaces.
We should think of a computational system as a black box with interfaces [Figure 1]. The interfaces transfer information back and forth to users (output and input), and also back and forth to persistent storage or network communication facilities. For our purposes we distinguish three relevant viewpoints:
input/output (end user) interface | | | |---------------| |XXXXXXXXXXXXXXX| |XXXXXXXXXXXXXXX| end users<-->|XXXXXXXXXXXXXXX|<-->storage |XXXXXXXXXXXXXXX| external programs<-->|XXXXXXXXXXXXXXX|<-->network |XXXXXXXXXXXXXXX| |XXXXXXXXXXXXXXX| |---------------| | | Figure 1.
Depending on what we have in mind as the boundaries of the black box, the input/output interface is not limited to input/output devices in the usual sense. It may be an interface to other programming facilities, e.g., external address spaces. Thus, for example, certain variables may have their values maintained opaquely inside the black box, while other variables are external. Passing values to or from such external variables counts as crossing the input/output interface. (For this reason, I am sometimes tempted to use the terms "import" and "export" rather than "input" and "output", so that it doesn't necessarily connote an I/O device.) Representations need to be specified for data maintained in such external variables, but not for variables maintained in the black box.
Following the object-oriented principle of separating interface (semantics) from implementation, we focus primarily on the end user's input/output interface. We talk primarily about the language facilities provided for use at this interface, and how information appears when it crosses this interface. We also talk about the requirements and constraints imposed at this interface, without specifying how these are satisfied in the other viewpoints. Thus we may talk about how information looks on input, and what is consequently expected on output, without dictating how this appears inside the black box or in storage. In many cases it might be most expedient to represent things in a form similar to what was provided on input, but this is not required.
The other viewpoints do need to be considered as well. Somebody does have to decide how things will look in storage and inside the black box. Our position is that these specifications should be segregated in such a way that the end-user's understanding of the system behavior does not require knowledge of these specifications. Furthermore, these "implementation" specifications should be changeable without altering the semantic behavior presented to the end user.
The black box is a symbolic system, which means that the only things which pass across the interfaces are symbols. People and abstract numbers don't pass across these interfaces; strings and pictures do. Our general definition of "symbol" is circular, taken to mean whatever can pass across these interfaces. The exact nature expands with advances in technology, including such things as text sequences, pictures, sounds, electrical signals, and even actions such as mouse movements or screen touches. For our purposes, though, it suffices to think of symbols as text sequences.
An important point: although non-symbols can't pass across the interfaces, they can have opaque representations inside the black box. We can tell the box to create a thing such as a person and put it into a local variable. What goes into that local variable does not have to be known externally. Internal operations can be requested without such knowledge, using the local variable or some other sort of expression. The thing does have to be provided in a designed symbolic form when it is to be output (exported), either to some output device or an external variable. There also has to be some convention for understanding that an input symbol designates this thing. The thing also has to be put into a designed symbolic form when it goes to storage, but that need not be a concern of the end user.
Simple examples:
Objects are managed by object systems.
Objects are managed in computational systems which we will call object systems. Object systems are not totally transparent to the operation of objects. They provide an infrastructure which routes requests from requestors to performers, returns results, resolves generic requests, and may provide other services as well. Different systems and languages vary in the services provided by the object system infrastructure.
Object systems provide interfaces which isolate object users from implementations.
Object model features can thus be partitioned into those relating to users and those relating to implementation.
Object users are those entities which issue requests. They may be humans at an interactive interface, or they may be programs, possibly implementing services for other objects. They may also be mechanisms triggered by events and conditions, accounting for active databases.
The implementation constructs which are hidden from users behind an object system interface include program code for executing requests, query processing and optimization, data structures, data placement and clustering, and pointers.
The distinction between services provided by a compiler, by client facilities [18], and by the object system infrastructure [Figure 2] is a bit fuzzy. An object model might be defined in terms of the request as constructed by a user, or in terms of the request as provided either to a client facility or to the object system interface.
|programming language interface | | |"client services" interface | | | | |"object management" interface | | | |---------------|----------------------|---------------- |...............|//////////////////////|XXXXXXXXXXXXXXX| |...............|//////////////////////|XXXXXXXXXXXXXXX| end users<-->|...............|//////////////////////|XXXXXXXXXXXXXXX| |.. compiler ...|// client facility ///|XXXXXXXXXXXXXXX| external programs<-->|...............|//////////////////////|XXXXXXXXXXXXXXX| |...............|//////////////////////|XXXXXXXXXXXXXXX| |...............|//////////////////////|XXXXXXXXXXXXXXX| |---------------|----------------------|---------------- | | | Figure 2.
The notion of a request being a "message" to a single recipient, where that recipient is the performer of the request, really seems to be an implementation concept, not visible to the user. The user doesn't see the difference whether a request to register a student in a course is a message to the student or to the course, or even if it becomes a message to a Registrar application or a DBMS which actually performs the service. Syntactic forms such as Student.Register(Course) or Course.Register(Student) don't have any real operational significance. (Possible exceptions: inheritance patterns, content notions.)
This parallels the classical/generalized distinction, augmented with the possibility that the performer might be none of the objects mentioned in the request.
An object system may provide multiple object system interfaces. One configuration arises when the performance of a request is executed by making requests to a "lower-level" interface containing implementation objects [Section 24.1]. Different interfaces might support different object models, giving rise to a "multi-faceted system" [Section 26].
At a given interface, different users might have access to different sets of objects for various scoping reasons. Each such scope is called a sphere (suggesting a "sphere of knowledge") in which a specified set of objects is known. Each interface has a maximal sphere, being the set of all objects known at that interface by any users.
These concepts will be elaborated in Section 26. For now we deal simply with a single interface, operating under a single object model, with just one (maximal) sphere.
This section describes a particular model which, in the terms introduced in Section 22, can be characterized as a participant and associative model.
(This could be FOQL - Functional Object Query Language - abusing the word "query" to include all DDL and DML, just as in SQL and OSQL.)
By and large, this is an aggregation of familiar material, such as the functional Evaluate/Apply paradigm and some usual notions of types, operations, overloading, etc. However, there are a number of small but powerful refinements:
Most real systems and languages support only a subset of the features described here. This model is intended to be a superset of the model supported by most real systems and languages.
The model is developed top-down, developing the natural consequences of the fundamental concepts.
From the user perspective, everything that happens in an object system is the consequence of a request.
This model is essentially a functional object model - operations and functions are the same thing. A request designating an operation and an argument is issued by a user at an object system interface. In the simplest case the request explicitly identifies a specific operation and a simple object. In other cases the operation might be generic [Section 10.1], the argument might be complex [Section 11], and either might be designated by an expression [Section 6.2] consisting of a composition of requests.
A request is an event, occurring at a point in time. The same operation/argument pair might occur in many requests.
Evaluation of a request yields one or more of the following:
Evaluation always yields some condition object, in order to signal completion of the evaluation.
Following are some of the conditions which might be returned for an operation f and argument x:
Some of these conditions may not be treated as errors, depending on the degree of type checking in effect. If the condition is not an error, then the result should be considered null.
An error-free evaluation yields no error conditions.
Other things besides simple requests can be evaluated. Exactly who does this evaluation may be debatable. This is one point at which we enter the fuzzy domain between the user (client) environment and the object system. For example, an expression such as Length(x)+Length(y) might be compiled into two calls to the object system to retrieve the lengths of two objects, with the subsequent addition being performed locally in the program's own execution space. Compositions such as Length(Axle(x)) might be similarly decomposed into two calls to the object system. We will not address these sorts of decomposition here, simply saying that, from the user perspective, the object system does all evaluation.
Requests may be more complex than a simple operation/argument pair. Either of these elements might itself be the result of a request, giving rise to nested requests. At the other extreme, single objects can themselves be evaluated.
To be precise, an operation is a value object [Section 29.1] which can occur as the first element of some pair whose evaluation is error-free. The second object in such a pair is playing the role of an argument.
A request form is a pair <f,x> which is intended to be evaluated. Either element of the pair may itself be a request form. The request form is generally denoted as f(x) in functional notation, or as x.f in relational dot notation and object-oriented messaging notation. (In some syntaxes where the argument x is implicitly understood - as in the current row of a table during a query - f alone can also have the same meaning.) A request to evaluate an argumentless operation [Section 27.1.3] will be expressed as a pair with a null second element, i.e., f() or <f,>. The notion of a pair is itself defined in Section 29.5.
We can use the term property to mean an operation which may return a value, e.g., f is the property in f(x)=y.
It is not clear how to differentiate an expression from other valid objects, although a language parser might do so. A variable is an expression, though it is not a request form. The default evaluation for any object is to return itself, i.e., to treat it as a value object. Thus an expression is any object for our purposes.
Details of expression evaluation are described in Section 27.2.
From the user perspective, it doesn't matter who performs a requested service.
Notes:
A common paradigm: A performer object has a location property and a set of exclusively owned methods. A request is executed by sending a message to the performer object, causing a method to be dispatched.
Participant view: the requested service might be performed by any of the mentioned objects, or by something else altogether. The infrastructure plays a more active role, at least to the extent of helping to select a performer for the request.
Proposition: the knowledge of who performs the requested service is an implementation concept. The user doesn't care. It should be possible to have different performers in different implementations without affecting the user.
The essential effect of update is to alter the results of future requests.
The traditional notion of update in terms of writing data to storage is not effective from the user perspective, since storage mechanisms are hidden from the user on the other side of the object system interface. The only way the user knows that update has occurred is by observing the results of future requests. If the user requests that the radius of a circular object be modified, the user will subsequently see different responses to requests for the radius, diameter, circumference, area, volume, or weight of the object. The user doesn't know, nor need to know, which or how many of these facts are physically stored, as opposed to being computed from the others.
When the Assign operation is applied to a pair consisting of a quoted variable [Section 28.6] and an expression, its effect is to bind the variable in the current environment [Section 27.1.1] to the result of the expression (including null).
The request form Assign(<`x,y>) (i.e., <Assign,<<Quote,x>,y>>) is generally denoted as x<-y. Note that x itself is not evaluated, but y is. The effect is that a subsequent evaluation of x in the current environment, with no intervening update of x, will yield y.
When the Assign operation is applied to a triple <f,x,y>, where the first element is an updatable operation, the effect is to invoke the update component of the operation [Section 10.2.2.2]. The effect of executing the update component should be that a subsequent invocation of f(x) returns the value of y (including null).
Assign(<f,x,y>) can be denoted as f(x)<-y; this does not signify that f(x) is to be evaluated (although x itself is evaluated in this case).
Updates which would violate any constraints (invariants) are not permitted. An attempt to do so should yield an error condition.
Some languages support a single assignment operation such that Assign(f,x,y) signifies f(x)<-y (the language might directly support an assignment syntax). Other languages, via an attribute mechanism, associate with an updatable operation f an updating operation Updater(f), such that Updater(f)(x,y) signifies f(x)<-y. For example, the updater for Salary might be Set_Salary, and the updater for Location might be Move. The effect of Move(x,y) is thus defined as causing Location(x) to be y.
The concept of state is not uniquely defined from the user perspective.
A changeable property is one whose value may change with time, e.g., f(x)=y now and f(x)=z later. Square root and square are unchangeable properties of integers. A schema might define social security numbers or part numbers as unchangeable properties of persons or parts.
An updatable property is one whose value can be changed by direct assignment, for which we will use the syntactic form f(x)<-z. After such assignment, we have f(x)=z (ignoring funny situations casting might cause). A schema might define Age to be non-updatable, yet it is changeable by the passage of time or by the update of someone's birthday.
Updatable properties need not be stored. Update may be managed by procedures which update other stored information. For example, either the radius or diameter of a circular object could be stored. Both might be updatable, with the stored value being updated as appropriate. Thus, if the radius is stored, then updating the diameter causes half the new diameter to be stored as the new radius.
A recorded property is one whose value is stored; this is an implementation concept. This is sometimes equated with the notion of state. Unfortunately, the necessary set of recorded properties is not uniquely determined by semantics, but is ultimately an implementation choice. The set of minimal recorded properties is not unique. For example, while it is clear that either the radius, diameter, circumference, or area of a circular object must be stored, the choice is a matter of implementation (we might even choose to store several for efficient retrieval, keeping the various stored values synchronized).
Thus there is no natural definition of an object's state. Some systems and languages allow an arbitrary set of properties to be defined as the state of an object. Care should be taken not to assume that these are recorded properties, as this would expose implementation to the user. This set of properties is also sometimes taken to define the "content" of the object [Section 13.4] for the purposes of such operations as Copy or Display.
The term "mutable" is ambiguous. It is commonly used in the sense that some objects are mutable while others are not, but the concept really applies to properties of objects. Certain properties of an object might be mutable while others are not, and it might be the case that some objects have no mutable properties. In any case, however, it is not clear in which of the above senses mutability is defined. We avoid the term.
Objects "exist" so long as they are known to an object system.
If an object system can provide the date on which a certain file was deleted, then that file object still exists as far as the object system is concerned. Certain operations may no longer be supported, such as modifying or displaying the contents of the file, and the file may no longer be present in any directory, but the object system can still respond to requests involving that file.
Similarly, if an object system can provide the date on which a certain building will be completed, as well as its location, height, and blueprints, then the building object exists even if construction has not yet begun.
We try to avoid dealing with "existence" in this document, and speak only of objects being known by an object system. Operations which purport to "create" or "destroy" objects in an object system should really be understood as "introducing" and "erasing" objects, i.e., making them known and unknown to the object system.
An object is considered to exist in an object system if any operation can be successfully applied to it in the object system. More specifically, an object is known if it can be mentioned as an argument in some request without causing an unknown error condition [Section 6.1]. Such existence does not necessarily imply that storage space has been allocated for maintaining data about the object, or that certain particular operations can be applied to the object.
Other notions of "existence" can be modeled in terms of the status of known objects, perhaps in terms of types and subtypes. For example, "ExistingFile" might be a subtype of "File", such that operations which modify or display the contents, or manage the file within a directory, are only defined on ExistingFile.
The management of object identity depends on how an object becomes known to an object system.
The closest we come to dealing with the philosophical question of what "exists" in an object system is to describe what is known in a sphere. Objects can become known in a sphere by the following means:
An extensional set is known if and only if its elements are known.
For certain kinds of imported data, an object exists if and only if a certain value exists in some external data source.
The objects known in one sphere might be defined by selection from the objects known in another sphere.
The term surrogate refers to mortal objects together with the non-literal objects essential to the model itself, like the built-in types and operations. (In implementation terms, surrogates are things typically represented by system-generated object identifiers.)
The management of object identity should be consistent with the axioms of equality.
Equality in object systems is ultimately described in terms of an arbitrary equality predicate x=y whose truth may be defined either by users or by the object system. However, in order to provide expected behavior, the predicate should observe the axioms of equality and substitution.
The semantics of object identity are described by axioms for an equality operation x=y [Section 28.1], interpreted to mean that the values of the variables x and y are one and the same object. The operation may yield different results in different spheres, but is always subject to the following axioms (quantifiers range over a given sphere):
E1 (reflexivity): FORALL x, x=x.
E2 (symmetry): FORALL x FORALL y, x=y => y=x.
E3 (transitivity): FORALL x FORALL y FORALL z, x=y AND y=z => x=z.
E4 (substitutability): FORALL x FORALL y FORALL f, x=y => f(x)=f(y); also, f(x) and f(y) cause the same conditions and updates.
E5 (singularity): FORALL x FORALL y, x=y => {x,y}={x}, or equivalently, Card({x,y})=1.
E5 captures the notion that x and y refer to one object. E5 might not be an independent axiom, depending on how set construction is defined in terms of equal elements, but it doesn't hurt to emphasize it here.
Although identity is often implemented in terms of object identifiers (oid's), the semantics of identity are defined without reference to oid's.
New() is an argumentless operation which returns an object which did not previously exist.
AddType(x,t) makes x an instance of type t. It can be characterized as Add(<`Extent(t),x>).
RemoveType(x,t) makes x no longer an instance of type t. It can be characterized as Remove(<`Extent(t),x>).
The main purpose of the Initialize operation is to allow values of total operations to be provided at the time an object becomes an instance of their argument types. It has the form Initialize(<x,<<f1,y1>,...,<fn,yn>>>), and its effect is equivalent to
f1(x)<-y1,
...
fn(x)<-yn.
The AddType operation should incorporate Initialize in order to satisfy constraints on total operations. Hence AddType should accept arguments for Initialize (or the two should be packaged in some other atomic operation). Initialization should account for total operations defined on supertypes of t as well as on t.
Object creation operations often bundle New and AddType (and hence Initialize), creating an object as an instance of a type.
Schema constructs such as types, operation definitions, and inheritance are provided for planning purposes, so that users can choose the appropriate requests to achieve their intended results.
The following topics need to be developed:
Types are fundamentally a link between objects and operations, establishing whether the object system has instructions on how to apply an operation to an object. In a nutshell, if an operation f is defined to accept arguments of type t, and if x is an instance of type t when f is applied to x, then a request which applies f to x will not cause the inapplicable condition [Section 6.1]. This enables users to plan to apply f to x without fear of causing this particular condition.
Types also characterize the results returned by operations. If an operation g is defined to return results of type t (the argument type of f), then the user may plan to apply f to the result of g(y) without fear of raising the inapplicable condition (assuming g is applicable to y).
There are at least the following things associated with the notion of "type":
(The following text is a bit old, and may need to be cleaned up to better reflect these distinctions. An interesting thought to pursue is whether a single object can play all these roles. Also deal with the fact that created types are surrogates (mortal) while parameterized types are ephemeral.)
There is an object named Type. A type t is an object for which t IN Type. Type IN Type, i.e., Type is a type. If x IN t for a type t, then the value of x is an instance of the type t. (More precisely, x is an instance of the set which is the extent of the type t. We could model it that way if we took a little more trouble.)
A type t is also a total predicate, such that t(x)<=>x IN t. (Hence Type SUBSETEQ Predicate SUBSETEQ Profile SUBSETEQ Operation.)
There is an ArgType operation which, when applied to some operations, yields a type. If x IN ArgType(f) then evaluating f(x) will not yield an inapplicable condition.
There is a ResultType operation which, when applied to some operations, yields a type. If ResultType(f) is t and evaluation of f(x) does not yield an error or null condition, then f(x) IN ResultType(f).
If t1 SUBSETEQ t2 for types t1 and t2, we will say that t1 is a subtype of t2.
A subtype t2 of t1 is an immediate subtype of t1 (and t1 is an immediate supertype of t2) if no supertype of t2 is a subtype of t1. An instance x of type t is an immediate instance of t (and t is an immediate type of x) if x is not an instance of any subtype of t.
Every type has a name. System types have predefined names. Created types are named upon creation. Generated types are named by a naming convention. Type names are unique over all types known within any given sphere.
The fact that x is an instance of t can be expressed in a number of equivalent ways (some of which are curried equivalences [Section 25.3]):
x IN t <=> t(x) <=> TypeInstance(<t,x>) <=> t IN Types(x) <=> x IN Extent(t).
This is territory where we usually don't want to be bothered with the distinctions, because we assume some familiar defaulting conventions which gloss over the detail. Thus we hate to have to say that 10 is to be interpreted as decimal digits, because that's the normal assumption. Such things only matter when the defaults aren't self-evident. Thus our overall approach should proceed in stages: first spell out the painful details involved, then seek ways to ease the pain by restoring appropriate defaults wherever possible.
The general idea is that only materialized types can be exported and imported. Any other type has to be cast (coerced?) into a materialized type for export, and an inverse casting mechanism needs to be established for import.
This is closely related to the notion of semantic and presentation objects, taken to an extreme degree. Here, semantic objects are inside the black box, in opaque form. Anything else that is input, output, or stored is in a presentation form, including simple strings of bits, bytes, or characters.
The essential idea: Integer is a non-materialized type, not presuming any symbolic representation. The corresponding materialized types include Decimal_Integer (the traditional default), Hexadecimal, Octal, Binary, etc. We might also have Word_Integer, whose instances include "one", "ten", "one hundred twenty-one", perhaps with variants for different languages. The check-writer in my financial software converts numbers to a type similar to this. It may be the case that we know the internal form used inside the black box, or in storage, but this doesn't really matter to the end user.
The concept of a materialized numeric type deals with the correspondence between symbols and abstract numbers, with each such type having an associated:
The mapping is an important part of the type concept, since the same symbol can occur in different numeric data types to denote different numbers. Thus 10 means different things in decimal and binary, and 1E1 means different things in exponential and hex.
For the Hexadecimal type the set of symbols includes all sequences over the alphabet {0...9,A...F}. (This is the ideal type; corresponding effective types will be limited to finite sets [Section 9.2.2].)
The mapping is a pair of inverse functions for input and output, establishing correspondences between abstract numbers and symbols. Thus HexIn(A) applies the HexIn function to the symbol A, yielding the number ten (in no specific representation). Similarly, HexOut(OctalIn(10)+BinaryIn(10)) yields the symbol A.
We've actually seen these functions in many languages, though with a different syntax. HexIn(10) often takes the form x `10'. The forms x`10', o`10', and b`10' each map the string 10 into a different number. (Those are "designators".) In fact, we can think of quotation marks in a similar sense: "10" behaves like CharIn(10), mapping the string 10 to an opaque internal representation of itself.
It's interesting to note that there is no materialized type corresponding to the real numbers, if we assume that symbol sets are denumerable. A data type called "Real" is dealing at most with the rational numbers.
This is where we take into account the effect of implementation restrictions on data types. An ideal type is an abstraction which typically cannot be fully implemented in any real system. An effective type is the type that's really supported by an implementation.
We want to try to describe these in semantic terms, being minimally contaminated by "implementation" considerations. Unfortunately, "minimal" is not zero.
The essential problems are these:
Languages typically take one of the following approaches:
Dividing these types into non-materialized and materialized, and also into ideal and effective, yields four categories. We'll go around the matrix in the following order:
Ideal non-materialized numeric types are the ones we learned about in school. The counters (non-negative integers) are a subset of the integers, which are a subset of the rationals, which are a subset of the reals, which are a subset of the complex numbers if we want to go that far. By "subset" we mean a naive form of inclusion whereby the integer ten is itself a rational number, not just "equivalent" to something else denoted by 10.0.
All these sets are infinite, and they are all closed under addition, subtraction, and multiplication. All but the integers are closed under division. Comparisons are perfect, i.e., two numbers either are or are not equal, unambiguously. Equality is a perfect equivalence relation (symmetric, reflexive and, hardest of all, transitive), and the orderings perfectly satisfy their axioms. Even assignment works perfectly: x=e always holds after x<-e.
These are the ones described above in Section 9.2.1, with infinite symbol sets.
These are the materialized numeric types with length restrictions. There are overall length restrictions, as well as restrictions on various components, such as the mantissa and the exponent.
In effect, these are parameterized types, parameterized by different lengths.
The effective non-materialized numeric types are the ones actually supported in computational systems. They represent places where implementation considerations show through into language semantics, being impacted by limitations of hardware and representation.
(Alternative terminology: we might also call these "practical", "pragmatic", or even "finite" numeric types. Even the term "real" - as opposed to ideal - comes to mind, but that would get confused with the real numbers.)
Note that several different effective materialized types might correspond to the same effective non-materialized type. For example, 4-character hex and 16-bit binary have the same capacity.
An ideal numeric type can have a large number of overlapping effective numeric subtypes, corresponding to different internal limitations. The essential characteristic of the effective types is that they include only a subset (usually finite) of the instances of the ideal supertype. Thus Integer_16 only contains the integers up to (2**16)-1, while Integer_32 includes those as well as all other integers up to (2**32)-1. There may be interior gaps as well as outer bounds. A type restricted to three significant digits can represent 1230 and 12300, but not 1234; the "successor" to 1230 is 1240.
This incompleteness leads to the central semantic problem of effective types: failure of closure under arithmetic operations. This is exactly what causes overflow and underflow errors, as well as truncation and rounding.
Most operations are not closed within an effective type. More generally, trying to represent an arbitrary abstract number requires an additional fudge step (often roundoff or truncation) to find an appropriate (not always nearest) abstract number which is representable in that data type. Similarly, comparisons sometimes take such fudge factors into account.
So, the course of a computation goes roughly as follows:
Such data types correspond to mappings into, rather than onto, a certain kind of number (e.g., rational or integer). The set of numbers it maps symbols onto are its representable numbers. The inverse mapping is total on the representable numbers, partial on all the numbers. Alternatively, the inverse mapping is total but not invertible; an arbitrary number first gets fudged to a representable number, whose corresponding symbol is then used. Inverting this yields the representable number, not the original number.
Example: say SmallRational can represent numbers to two decimal places. SmallRational(2/3)=0.67. Number(SmallRational(2/3)) yields a number equal to 67/100, not 2/3.
We might distinguish between "exact numbers" and "true values". A symbol exactly denotes a certain number when interpreted within a specified data type. It might not be the intended "true" number for a variety of reasons. Thus 0.666666666667 very exactly denotes a certain rational number in decimal notation. It may be "wrong" because it was originally computed as 2/3, or because a ruler had finite precision, or because somebody entered the wrong number. But it is a very exact number. This is analogous to saying that 1,000,000 is a very exact number, but it might be "wrong" because it is only the estimated population of a certain city.
We'd like to relegate this all to the realm of "implementation", quite unrelated to the semantics of operations performed by users. Unfortunately, we can't. Users see the consequences in the form of various sorts of errors. Results of certain computations get too large or too small, and comparisons occasionally behave strangely. Assigning x/y to z might not yield equality between x/y and z.
Therefore, the user needs to be conscious of "subtypes" of the number kinds. It is in fact semantically meaningful to differentiate between Integer_16 and Integer_32, or between Rational(5,5) and Exponential(5,5). Each of these types has a different population of representable numbers, and assigning anything to cells having such types has to be understood as implying a fudge step.
On the other hand, we need to be careful whether we have in mind different internal implementations or different sets of abstract numbers. The difference is illustrated by whether or not we consider Integer_16 to be a subtype of Integer_32. The integer ten is an instance of both, and the same can be said of any abstract number representable in Integer_32. Thus the numbers in the abstract set denoted by Integer_16 is a subset of the set denoted by Integer_32. On the other hand, a 16-bit field is not a 32-bit field. The fields declared to be of type Integer_16 are not declared to be of type Integer_32. In this sense, Integer_16 is not a subtype of Integer_32.
The same sort of argument arises between such types as Integer and Rational (aka Real). Numerically, one is a subtype of the other, but in terms of representations they are not.
An interesting and possible useful idea is to treat numeric types as parameterized types, with the "storage" type as a parameter. This would be a useful way of relating the abstract and stored types. For example, Integer might be a type generator rather than a single type. Specific types would be given by Integer(32_bit) and Integer(16_bit). Similarly, rational types might be given by Rational(5,5) and Rational(5E5).
The operation referenced in a request may be either specific or generic.
A specific operation is explicitly defined with a name, signature, and behavior specification.
Several specific operations may have the same name. A generic operation implicitly exists for each set of specific operations having the same name. If a request identifies an operation by simple name only, this is a reference to the generic operation, which then has to be resolved to a specific operation appropriate to the argument in the request.
There are no inheritance issues or problems for specific operations. The complexities of inheritance and overloading arise only with generic operations.
There is a type named Operation (whose instances are all the operations), partitioned into the subtypes named SpecificOperation and GenericOperation (the latter are described in Section 10.3).
A specific operation has the following things:
There are several notions of signature. We define it here as the name, argument type, and result type of an operation, often denoted as f: t1 -> t2.
Behavior specifications are distinct from implementation specifications.
Behavior specifications describe the consequences a user should expect from applying an operation. Implementation specifications describe what the object system (including the objects it manages) has to do to yield such consequences. We reserve the term "method" for implementation specifications. Many current systems and languages merge the two concepts, taking methods to be behavior specifications.
The distinction is admittedly fuzzy. A definition of salary as the product of hourly rate and hours worked could arguably be taken either way. So could the definition of an operation in terms of a high-level query which is both readable and executable. The distinction must ultimately be made somewhat arbitrarily by type and class definers, based on the following guidelines:
Furthermore, the state of the art in behavior specification is not yet mature. Nevertheless, we describe the general model in terms of a distinction between behavior and implementation specifications.
A behavior specification thus defines the intended behavior of an operation when it is applied. The specification is provided for the user's information, and is also intended to constrain the implementation specification. It might be provided in various forms, such as:
The requirement that the argument be an instance of the argument type is an implicit pre-condition (if strict type checking is enforced - to be discussed).
Whether or not the operation can be applied to a null argument is also a pre-condition.
The fact that a non-null result will be an instance of the result type is an implicit post-condition.
Totality (i.e., the result will not be null if the argument is an instance of the argument type) is also a post-condition.
The implementation specification defines what the object system will actually do when the operation is applied. It might be provided in various forms, such as:
An operation may have several sets of implementation specifications, each associated with a different class [Section 15].
In a general model which supports direct update [Section 6.4.2], a separate specification is provided for the behavior of the operation when it is updateds. In effect, this serves as an "update entry point" for the operation. This specification might simply say that the operation is updatable, i.e., assignable [Section 6.4]. It could also define the intended behavior when this is ambiguous, e.g., it would indicate whether changing an employee's manager is interpreted as the employee changing departments or the department changing managers. The update semantics might be inferred by the system, e.g., when the operation is mapped to stored data, or when the system can determine the inverse of the retrieval specification.
Specific operations having a given name imply the existence of a generic operation with that name. A generic operation has a default behavior defined by the computational system (i.e., the rules for overloading) in terms of specific operations having the same name as the generic operation. User-specified behaviors can override the default behavior in order to provide:
Besides their general utility, these features are particularly useful for multidatabase systems [Section 30.1].
A behavior may be specified for a generic operation f with respect to a set of relevant types. Specifications may include a result type, a default result value, a disambiguation specification, and a uniqueness specification (these terms will be defined shortly). Different behaviors may be specified for different sets of relevant types. For example, they may have different result types; any operation named f whose argument type is in a relevant type set must have the specified result type.
When f(x) is invoked:
Inheritance behaves as follows (this is inheritance of interfaces, not implementations):
In particular, both f.t1 and f.t2 are known for t4 in the case shown in Figure 3.
------
| t1 |
f.t1 ------
:
.....................
: :
------ ------
| t2 | | t3 |
f.t2 ------ ------
: :
.....................
:
------
| t4 |
------
Figure 3.
Unless otherwise defined for the generic operation, all specific operations having the same simple name must have the same result type. (OSQL may allow overloaded operations defined on literals to have different result types from operations with the same name defined on surrogates. That's not particularly significant here.)
A request may involve a simple (generic) or specific operation name. If specific, the call invokes the behavior defined for the specific operation [Section 10.2].
The default behavior for a generic operation call f(x) is defined as follows:
1. The eligible operations are the specific operations f.t which are known for the immediate types of x.
If x is null, the eligible operations are the specific operations named f whose pre-conditions allow null arguments, including argumentless operations.
2. If there is exactly one eligible operation, invoke it and exit.
3. If there are no eligible operations:
3a. If there exists exactly one Caster(<t1,t2>) [Section 10.4.1] such that x is an instance of t1 and there exists an f.t2, then invoke f.t2(Caster(<t1,t2>)(x)) and exit.
3b. Else return an undefined condition and exit.
4. If there is more than one eligible operation:
4a. If all the non-null values are the same, then return that value (or null if all the values are null) and exit.
4b. Else raise an ambiguous condition and exit.
Without item 4a, f(x) would be considered ambiguous when there are several eligible operations even if they all have the same value.
The following behaviors may be explicitly defined for a generic operation with respect to a set of argument types:
Details are described in Section 30.
When a specific operation is applied to an argument which is not an instance of the operation's argument type, there are additional mechanisms which sometimes define behaviors.
The essential idea of casting is that an object x which is not of an appropriate type may be replaced by a related object c(x) which is of the appropriate type. An operation c which plays this role is a casting operation.
For any pair of types t1 and t2, there is at most one casting operation c with signature c: t1->t2. For such a pair of types, we define a Caster operation such that Caster(<t1,t2>)=c.
If Caster(<t1,t2>) is not null, and if any operation f.t2 is applied to an argument x which is an instance of t1 but not t2, then f.t2(x) can be evaluated as f.t2(Caster(<t1,t2>)(x)), i.e., as f.t2(c(x)).
CastingOperation is a subtype of Operation. An operation might be defined as a casting operation in several ways:
Since an instance of a type t is an instance of all supertypes of t, an instance of t is always acceptable where an instance of a supertype is required. Hence it does not make sense to allow a casting operation to be defined from a type to any of its supertypes.
Automatic casting between basic data types is often defined for some languages.
The Cargo operation is the casting operation for intensional aggregates [Section 11.7].
As a special case, we will assume that Extent is the casting operation from Type to Bag (did we say that Bag=BagType(Object)?). Thus, whenever a type t appears where a bag (or set) is needed, it can be replaced by Extent(t).
The existence of a casting operation from type t1 to type t2 means that an instance of t1 is acceptable wherever an instance of t2 is required, i.e., t1 is substitutable for t2.
If t1 is a subtype of t2, then t1 is trivially substitutable for t2 without a casting operation.
If f has signature
f: t1->t2,
where t1 is not a bag type [Section 11.1.3], it is useful to "overload" f with another definition with signature
f: BagType(t1)->BagType(t2),
whose behavior is defined for a bag b of type BagType(t1) as
f(b) ::= BagReplace(<b, `x, `f.t1(x)>) [Section 28.7.4].
The result is a bag in which each occurrence of x in b is replaced by an occurrence of f.t1(x).
An operation might be exclusively or jointly owned.
Topics:
A type can be acquire instances by one or more of the following means, corresponding to various ways in which its Extent operation can be managed:
Maintaining consistency of rules can be difficult. If a rule-based type is also assertable, or has subtypes, the instances acquired by those means should be consistent with its defining rule.
Types are disjoint (intensionally) if they may never have any instances in common. It follows that they may never have any common (non-empty) subtypes, and that subtypes of disjoint types are themselves disjoint. Types which are not disjoint are said to overlap, meaning that they could possibly have instances in common.
We can say that two distinct types intersect if they overlap with neither being a subtype of the other. Exactly one of the following relationships holds between any pair of types:
We summarize the rules governing overlap and disjointness:
A language may allow explicit specification of disjointness and/or overlap (intersection), consistent with the above rules. A language may also establish the default assumption. We will arbitrarily make the default assumption that types overlap.
Aggregates can be described in terms of content and form.
Aggregates have content and form. Bags and sets are the limiting case, having only content but no form. "Content" does not have connotations of being inside, or belonging. Doing things to an aggregate doesn't automatically do anything to its members. Content is ultimately described in terms of an arbitrary "occurs" predicate.
An aggregate is an object in which other objects occur. Formally, we define
Occurs: <:Object, Aggregate:> -> NonNegativeInteger,
with Occurs(<x,g>) giving the number of times x occurs in g. We use x IN g to mean the same thing as Occurs(x,g); hence, x NOT IN g means (x IN g)=0.
The cardinality of an aggregate is the sum of all occurrences of all things in the aggregate:
Card: Aggregate -> NonNegativeInteger,
Card(g) = SUM[x]Occurs(x,g).
A bag is an aggregate which is not an indexed aggregate [Section 11.2]. Alternatively, it can be characterized as an indexed aggregate whose index set is empty.
A set is a bag which satisfies the constraint FORALL x, x IN g=<0.
There is exactly one empty set g for which Card(g)=0. It is the same thing as the empty bag.
Bag and set equality:
g1=g2 <=> FORALL x, (x IN g1)=(x IN g2).
That is, g1 and g2 are the same bag (set) if and only if everything which occurs in one occurs the same number of times in the other.
For any bag g, NullCon IN g is defined to be 0.
We can get more elegant by allowing a bag itself to be a profile operation such that b(x) = x IN b. The expression defining the membership of b, i.e., the expression for computing b(x), will be referred to as the "profile" of b. As a trivial example, the expression b(x)=Prime(x) defines b to be the set of prime numbers. If x is prime, then Prime(x)=1. In turn, b(x)=1 means that x occurs once in b.
A designator is an expression used as a means of identifying something. Informal syntax such as {1,2} and {2,1} are examples of designators which identify the same set (analogous to saying that 1+2 and 2+1 denote the same number). We avoid the commonly used term "constructor" because of the unintended implication that something new is being constructed with each use of the expression.
The informal syntax [x,y] is commonly used to designate bags. If x¬=y, then the result in this case is also a set. {} and [] correspond to two different sorts of designator operations: {} removes duplicates, while [] does not. Either one can yield a set; {} always does.
Bag and set designators can be formally defined in terms of sequence designators. If we let Boolean values be treated as 1 for True and 0 for False, then every sequence s has a unique corresponding bag b such that b(x) = SUM[i](s[i]=x). This expression means that the number of occurrences of x in the bag b is equal to the number of distinct integers i for which x is the i-th element of the sequence s. Let the operation Seq2Bag map a sequence into this corresponding bag. A Bag instance designator can be defined as
Bag(<e1,...,en>) = Seq2Bag(<e1,...,en>).
It is often denoted [e1,...,en].
Every bag b has a unique corresponding set s such that s(x)=1 <=> b(x)>0 (i.e., s(x)=[b(x)>0]). Thus x occurs once in s if and only if x occurs at least once in b. Let the Distinct operation map a bag into this corresponding set. A Set instance designator can be defined as
Set(<e1,...,en>) = Distinct([e1,...,en]).
It is often denoted {e1,...,en}.
Note that a bag instance designator will yield a set if the argument expressions yield distinct values:
[e1,...,en] = {e1,...,en} when the non-null ei yield distinct values.
Since nulls are nothing, and sets are bags, we have
[] = {} = [NullCon] = {NullCon} = [NullCon,NullCon] = {NullCon,NullCon} etc.
These expressions all yield the same object.
Many relational operations can be described as designators involving regular bags.
An aggregate type is a type whose instances are aggregates whose members satisfy certain type constraints. Aggregate types are ephemeral, and they exist exactly whenever the types in their definitions exist. An aggregate type designator is an operation which returns an existing aggregate type. It does not create anything new. Details depend on the specific aggregate type designator.
(Type designators are parameterized types.)
(An interesting way to look at this: all imaginable and describable sets of existing aggregates exist. At any point in time, an aggregate type corresponds to one of these existing sets. Not all such sets correspond to aggregate types, however.)
Terminology: we will use Bag(...), Set(...), etc. to designate instances. Thus Bag(<1,2,2>) means [1,2,2], i.e., it designates a particular bag. We will use BagType(...), SetType(...), etc. to designate types. Thus BagType(Integer) is the type whose instances are bags of integers. The difference is that [Integer] designates a specific bag whose only member is the type object named Integer. We will use [:Integer:] and {:Integer:} to respectively mean BagType(Integer) and SetType(Integer).
(We may not be consistently using that notation in operation signatures at the moment.)
The aggregate type designator BagType maps a type into an aggregate type:
BagType: Type -> AggregateType.
If t is any existing type, then BagType(t) is an existing aggregate type, recursively. The instances of BagType(t) are all the bags whose members are instances of t:
b IN BagType(t) <=> Occurs(x,b)>0=>x IN t,
i.e.,
b IN [:t:] <=> b(x)>0=>x IN t.
Note that we are saying that b is an instance of that type which is returned (designated) by BagType(t).
For example, if an operation is constrained to return results of the type BagType(Integer), then any result returned by the operation will be a bag of integers.
Note that BagType is not a type, but an operation which returns a type. The type whose instances are all bags is designated as BagType(Object).
We have t1 SUBSETEQ t2 => [:t1:]=>[:t2:]. Thus [:Employee:] SUBSETEQ [:Person:], since any bag of employees is also a bag of persons.
Bag types may overlap, i.e., have instances in common, even if one is not a subtype of the other. If @sam refers to a person, then [@sam] might be an instance of [:Employee:], [:Teacher:], [:Student:], etc. Furthermore, [@sam,@jim] is an instance of [:t:] whenever Sam and Jim are both instances of t, and it is not an instance if either Sam or Jim is not an instance of t.
The aggregate type designator SetType is analogous to BagType, except that the instances of {:t:} are all the sets whose members are instances of t. For any type t, {:t:} SUBSETEQ [:t:].
Indexed aggregates provide a general way to describe things like sequences, arrays, and records.
An indexed aggregate x has an index set characterized by the operations:
IndexSet: IndexedAggregate -> {:Object:},
Extract: <:Object, IndexedAggregate:> -> Object.
({:Object:} means SetType(Object), i.e., the type whose instance is any set; see Section 11.1.3.)
Bags and sets can be considered the limiting case where the index set is empty, i.e., there are no accessors.
We use the notation g[i] for Extract(<i,g>). (We could also use the notation i(g), except when the index set itself happens to consist of operations. We will use this notation for sequences.)
If i IN IndexSet(g), then g[i] may return something, though it need not. If i NOT IN IndexSet(g), then g[i] returns nothing, i.e.,
i NOT IN IndexSet(g) => g[i]~NullCon.
The following also holds:
g[i]=x => x IN g>0.
The arity (i.e., "length") of an indexed aggregate is the cardinality of its index set:
Arity: IndexedAggregate -> NonNegativeInteger,
Arity(g) = Card(IndexSet(g)).
The number of occurrences of an object x in an indexed aggregate g is given by
x IN g = SUM[i IN IndexSet(g)](g[i]=x),
i.e., the number of occurrences of x in the indexed aggregate g is equal to the number of distinct objects i in IndexSet(g) for which g[i]=x.
Equality of indexed aggregates is defined by
g1=g2 <=> IndexSet(g1)=IndexSet(g2) AND FORALL i, g1[i]~g2[i].
(Some models further differentiate aggregates according to the kind of designator used in referring to them. In effect, the aggregate type becomes part of the identity of the aggregate. For example, List(1,2) could be different from Tuple(1,2). It's not clear why this is useful.)
Specific kinds of indexed aggregates are defined in Section 29.5.
A generalized model of indexed aggregate designation is given by an expression of the form
Agg(<<i1,e1>,...,<in,en>>),
whose value is the indexed aggregate g with index set i1...in (all distinct) such that g[ij]=ej and Arity(g)=n.
For a sequence designator the index set is omitted, defaulting to the integers 1...n:
Seq(<e1,...,en>) ::= Agg(<<1,e1>,...,<n,en>>),
which is often abbreviated to the form
<e1,...,en>.
The expression <>, i.e., Sequence(), yields a sequence of arity 0. There is exactly one such sequence.
Observe that <> ¬= <NullCon> ¬= <NullCon,NullCon> ¬= <NullCon,NullCon,NullCon> etc. They are all distinct sequences, having arities of 0, 1, 2, 3, etc., and correspondingly different index sets.
The compact sequence designator CompSeq(<e1,...,en>) essentially constructs a sequence from the non-null expressions in the argument sequence. To define it, we can first define a RemoveNulls operation on sequences:
RemoveNulls: Sequence -> Sequence.
RemoveNulls(s) is defined recursively:
1. Let i be the least integer 1 =<i=<n=Arity(s) such that s[i]~NullCon.
2. If none, return s.
3. Else return RemoveNulls(<s[1],...,s[i-1],s[i+1],...,s[n]>).
A sequence s is a compact sequence if and only if RemoveNulls(s)=s. Also, Arity(RemoveNulls(s))=<Arity(s), and RemoveNulls(<NullCon,...,NullCon>)=<>.
The compact sequence designator can then be defined as
CompSeq(<e1,...,en>) = RemoveNulls(<e1,...,en>).
If none of the argument expressions is null, then
CompSeq(<e1,...,en>) = <e1,...,en>.
The instances of sequence types and tuple types are sequences. The instances of the sequence type denoted by SequenceType(t) are all sequences of any length whose non-null constituents are all instances of t. The instances of the tuple type denoted by TupleType(t1,...,tn) are all sequences g of length n such that g[i] IN ti if g[i] is not null. We use <:t1,...,tn:> to denote TupleType(t1,...,tn). Note that it is not a sequence type.
We have t1 SUBSETEQ t2 => SequenceType(t1) SUBSETEQ SequenceType(t2).
Also, <@sam,@jim> is an instance of SequenceType(t) whenever Sam and Jim are both instances of t, and it is not an instance if either Sam or Jim is not an instance of t.
For tuple types, the subtype relationship is
<:t11,...,t1n:> SUBSETEQ <:t21,...,t2m:> <=> n=m AND 0<i=<n=>t1i SUBSETEQ t2i.
The subtype is proper if any of the type pairs has a proper subtype relationship.
Due to the length distinction, there is no single tuple type which is supertype of all supertypes. The types
<:Object:>, <:Object,Object:>, <:Object,Object,Object:>...
are all distinct types. The type whose instances are all the tuples, i.e., the supertype of all tuple types, is actually SequenceType(Object).
<:Programmer, Engineer:> is a subtype of SequenceType(Employee). Conversely, the sequence <@joe,@sam> could be an instance of the tuple type. Every instance of a tuple type is also an instance of a sequence type. In general,
<:t1,...,tn:> SUBSETEQ SequenceType(t),
where t is any common supertype of t1,...,tn.
Note that we did not define a tuple instance designator different from a sequence instance designator. Every instance of a tuple type is an instance of some sequence type, and vice versa.
There are several distinct empty aggregates g for which Card(g)=0.
Associated with each index set is one distinct empty aggregate g for which g[i]~NullCon is always True. That is, the empty aggregates for different index sets are different objects. There is exactly one indexed aggregate whose index set is the empty set and whose Arity is therefore 0. This indexed aggregate is different from the empty set, which has no index set.
Since every object is an instance of multiple types (including all its supertypes), every non-empty aggregate always contains objects of different types, yet it always contains objects of the same type: they are all instances of Object.
Example: assume Dick is a student and Jane is a teacher. Then SET(:Dick,:Jane) is simultaneously:
A bag type or a set type does not require that all instances be of the same type. It requires that they all be instances of some specified type, in addition to whatever other types they might have.
A given aggregate object is an instance of many aggregate types, corresponding to combinations of the types to which the members belong. SET(:Dick,:Jane) is an instance of SETTYPE(Object) and SETTYPE(Person); it also happens to be an instance of BAGTYPE(Object) and BAGTYPE(Person).
TUPLE(:Dick,:Jane) is an instance of TUPLETYPE(Person,Person), TUPLETYPE(Object, Student),... in fact, it is an instance of all tuple types of the form TUPLETYPE(T1,T2) where T1 is any one of Object, Surrogate, Person, Student, Man, and T2 is any one of Object, Surrogate, Person, Teacher, Woman.
All of the Dick and Jane examples proliferate further if they happen to have other types as well.
The types to which an aggregate object belongs changes when the types of its elements change. If Dick becomes a teacher, then SET(:Dick,:Jane) becomes an instance of SETTYPE(TEACHER).
There are some natural subtype relationship among aggregate types.
SET(T) SUBSET BAG(T) for any type T.
SET(S) SUBSET SET(T) if S SUBSET T.
BAG(S) SUBSET BAG(T) if S SUBSET T.
LIST(S) SUBSET LIST(T) if S SUBSET T.
TUPLE(S1,...,Sn) SUBSET TUPLE(T1,...,Tn) if each Si SUBSETEQ Ti, with at least one Si SUBSET Ti.
The subtype rule for tuples can be used to reduce overloading of multi-argument operations to the same rules as defined for single-argument operations.
Note that this actually applies to all aggregates, accounting for content but not form.
The semantics of operations which yield indexed aggregates can be defined in terms of the form and content of the result, i.e., its index set and the behavior of the Extract operation [Section 11.2.1]. Thus, for example, the semantics of sequence concatenation s0=Concat(s1,s2) can be defined by the arithmetic expressions:
i.e., the integer i is in the index set of s0 if i is greater than 0 and not greater than the combined lengths of s1 and s2.
i.e., the i-th element of s0 is x if
As mentioned in Section 11.2.1, the number of occurrences of an object x in an indexed aggregate g is given by
x IN g = SUM