Objects and Object Systems

1 INTRODUCTION: FIRST PRINCIPLES

The goals of object orientation include:

• Supporting more complex information organizations than flat tables.
• Incorporating behavioral (procedural) knowledge into information.
• Maximizing the independence of users from implementations.
• Maximizing the reusability of implementations.

2 THE CONTEXT

An object system (obsys) is, among other things, a computational system which provides users with the ability to manage (update and retrieve) information. Users include people interacting via interactive user interfaces as well as applications (programs). In the latter case, the needs of people developing and maintaining such programs need to be considered.

Users use an object system via an object system interface allowing users to apply operations to objects. An object system interface description (often called a schema) describes the objects and operations which may be used at the interface, and says something about the effects of applying various operations to various objects. Users need this information in order to know which operations they should apply to which objects in order to meet their needs.

Behind the object system interface are facilities which implement the operations and the objects. An object system implementation description describes such implementations (in practice, this may also be incorporated in the same schema, which can turn out to be troublesome).

Object systems are distinguished from other kinds of information systems by the very high premium placed on making users maximally independent of implementations. Users should be able to operate uniformly on similar sorts of objects even if individual objects are implemented differently, and even if such implementations change over time. Thus there may be several implementation descriptions for the same interface description, either concurrently or over time. Users should not be dependent on any information in the implementation descriptions.

Object systems also place a high premium on reusability of implementations. An implementation developed for one sort of object should be reusable for similar sorts of objects whenever possible.

Object technology thus has two facets, the user aspect and the implementation aspect. It's important not to confuse the two.

A unit of program code may relate to objects in either or both of the following ways:

• The program is a user of certain objects.
• The program is a method, i.e., it provides the implementation of certain operations for certain objects.

3 SEPARATION OF OBJECT SYSTEM INTERFACE AND IMPLEMENTATION

The current state of object technology does not deal adequately with the separation of interface and implementation descriptions. They tend to be lumped together in the same schema. What is lacking is a facility to combine an interface description with different implementation descriptions, and to verify that each implementation correctly implements the interface description. There is also lack of agreement on the boundary between interface and implementation descriptions.

[Is the OSQL definition of a derived function an interface description or an implementation description - or both? Also, if different formulas are used to calculate the areas of circles and triangles, is that significant to the interface? How much needs to be included in the interface description to assure users that the operations will do what they expect? One possible criterion: the interface should only include things whose change would require a change in the way the user uses the objects (recompilation alone doesn't count). Anything which can be changed without changing the usage of the object should not be in the interface description. But another criterion: the interface description should enable a user to decide whether a given operation will meet his needs.]

[The lock and key metaphor. The external definition of a keyed doorlock is that a certain shape of key can be inserted and turned in one direction to enable opening a door and in the other direction to prevent opening. What goes on beyond that does not concern the key user. Different sorts of mechanisms can be used, i.e., various kinds of pins, tumblers, gears, latches, magnetic devices, optical recognizers (for the shape of the key), etc. If a key is supposed to open several doors, they can each be implemented with different sorts of locks, and the implementation in any particular door can be changed. Reusability: a lock devised for residential doors might also be usable for business doors, vehicle doors, and even not on doors, e.g., gates, drawers, bicycle chains, etc.]

A method (implementation of an operation) can use objects in two fashions. Recall that an object system interface includes a particular set of operations. A method implementing an operation in one object system interface might use objects in the same or different interfaces. For example, a method implementing an operation on relations might use tuples and other relations (objects in the same obsys interface) and/or it might use files (objects in a different obsys interface). The latter are sometimes described as being at a lower level of abstraction.

We might refer to the first mode as "peer-to-peer" usage, and the second as "cascading implementations". As another example of the latter, execution of a request to register a student in a course might use a registrar object, though not mentioned in the original request. This "performer" object is not visible at the higher obsys interface. In fact, different implementations might use different performer objects; some might invoke a dbms rather than a registrar application. The lower obsys interface may or may not perceive students and courses as objects.

4 WHAT WE WRITE DOWN

Sooner or later we need to take a digression into the realm of symbols and human communication. There are issues here which underlie some of our confusions. (If this digression is too soon for you, you can come back to it later.)

We glibly talk about Sam and 10 and the set {10,20}, and we can get away with that most of the time because we automatically make appropriate assumptions that allow us to ignore certain details of the process. It's like saying "I sent a memo to my boss" without needing to mention that you dictated the memo to a secretary who then typed it and put it into her out-basket from which it was picked up by the messenger-boy who... Alternatively, you might have composed a message at your keyboard and then directed your mailer to post it to the network which then... Those details usually don't matter, but once in a while they do.

Computational systems are symbolic systems. Symbols pass across their interfaces and symbols are stored internally. Operations ultimately do things like accepting incoming symbols across the interface, overwriting internally stored symbols with other symbols, and sending outgoing symbols across the interface. When we communicate with each other as human beings, we do so via symbols. Our technology is in a transitional phase where the notion of symbol includes images and sounds, but for our present purposes we can limit our attention to linguistic symbols, defined as finite linear sequences of elements from some finite alphabet. They might be bit strings or byte strings or character strings over some fixed character set. For the moment it doesn't matter which.

Concepts are different from symbols (though in a precise sense we might say that symbols are a very small subset of concepts). There is a many-to-many correspondence between symbols and concepts, often called denotation, which often depends on context. Thus, for example, if we make the right contextual assumptions about number base or language, all of the following symbols denote the same concept: A, 10, 12, 1010, 1111111111, X, ten, dix, diez, zehn, tiz. This concept also corresponds to the number fingers I have, and also to the number of my toes.

We don't write down concepts. We write down symbols which are intended to denote concepts. They will communicate concepts effectively if the communicators are making the appropriate assumptions about the context. Much of our work really involves establishing a context in which symbols will convey the appropriate denotation between sender and receiver.

Some symbols denote expressions intended to describe procedures for arriving at the intended denotation. For example, 2+2 denotes an expression which upon evaluation yields the same number as is denoted by the symbol 4. (I am eliding quotes around symbols for now.)

This begins to matter, for example, when we are dealing with sets. We naively speak of "the set {10,20}" as though {10,20} was a set. Most of the time that assumption is good enough. Once in a while, though, it's better to treat {10,20} as an expression which evaluates to a set. One reason is that there are many such expressions which evaluate to the same set, such as {20,10}, {10,10,20}, and so on, not to mention all the various ways we might represent the numbers we call ten and twenty. The phrase "the set {10,20}" should be interpreted in much the same manner that we might interpret the phrase "the number 2+2".

5 OBJECT EXISTENCE AND IDENTITY

Abstract definitions of "identity" say things like "that which distinguishes one thing from another". Object systems go a step further. They say that each object has at least one symbol (ultimately a bit string) which uniquely identifies it, being different from the symbol which identifies any other object in that object system.

Let me coin the term identifying-reference (or id-ref) to mean a symbol which is intended to uniquely denote one object in the context of an object system. Some symbols are not id-refs, but a given symbol will always denote the same object in a given object system so long as that symbol is an id-ref.

This is a generalization of the term object identifier (oid), which usually means an arbitrary identifier generated by the object system during an explicit act of object creation. An id-ref might also be a syntactically recognizable construct not explicitly generated by the object system. For example, the id-ref of an extensional set might consist of a flag indicating it is a set followed by the id-refs of its instances in some canonical ordering. Similarly, literals could be treated as objects if we treat some standard representation as their id-refs. We postulate that the object system internally knows some ordering of id-refs. We postulate that every object has [exactly? at least?] one id-ref which uniquely identifies the object in a given object system. [In some object systems, while an object may have several uniquely-identifying tokens, only one is considered to be the id-ref.]

We say that an object exists in an object system if an only if it is known by the system, i.e., its id-ref is recognized as an id-ref by the object system. That defines the lifetime of an object in the system: so long as its id-ref is valid to the object system.

An object reference is any expression which evaluates to an id-ref. An id-ref is itself an object reference. An identical predicate, which we denote as x==y, is true if and only if x and y refer to the same object, i.e., they evaluate to the same id-ref or to id-refs of the same object.

There is only one of a given object, unaffected by different forms of reference. If x==y, then

• f(...,x,...) and f(...,y,...) behave the same for any operation f.
• {x,y}=={x}, where {} denotes an extensional set constructor. This should hold in any context which excludes duplicates.

[In the current draft, we often use x=y when we mean x==y.]

[Observe: for consistency, we need to say that the bag [2,2,3,3,3] does not contain five things, but five occurrences of things. There are two things, with 2 occurring twice and 3 occurring thrice. Cardinality does not mean how many things, but how many occurrences of things. It's analogous to saying that one person has two votes on a committee and another person has three votes. Though there are five votes, there are only two persons.]

Object creation and construction are sometimes unclear in several respects. We should distinguish (introducing new neutral terminology):

• Invention: Bringing an object into existence. Some symbol which was previously not a valid id-ref now becomes a valid id-ref.
• Reference: An expression which evaluates to a valid id-ref.
• Allocation: Providing space in an implementation for storing information about an object.

For example, consider points in a given two-dimensional space with a fixed origin. We can distinguish two kinds: geometric points and moveable points. A geometric point (g-point) is a fixed location in the space, and can be referred to in rectangular, polar, or other coordinates relative to the origin for the space. All geometric points in a space exist; all syntactically correct rectangular or polar coordinates are recognizable as referring to an existing g-point. The first mention of the point at rectangular coordinates <10,20> does not create that point. Two distinct g-points cannot have the same rectangular coordinates.

A moveable point (m-point) is something which can occupy different g-points at different times without altering its identity. It might be the center of some circle, or a corner of a rectangle. Two m-points can occupy the same g-point. The current g-point is an attribute of an m-point, perhaps returned by a Location operation. (An m-point might have no current location, but that doesn't make null a g-point.) M-points need to be explicitly created and destroyed, and they need arbitrary identifiers. A g-point can't be moved, but an m-point can, by assigning it a new location.

Something like < -15,0> or <15,180> or <15,pi > is not a g-point. Such expressions denote a tuple (pair?) of numbers, which can be interpreted as coordinates of a point in an appropriate context. (In some other contexts it might be interpreted as an imaginary number.) We can imagine operations such as

Rect2Point(< -15,0>),
PolarDeg2Point(<15,180>),
PolarRad2Point(<15,pi >),

which, for these particular arguments, all evaluate to the same g-point. Without requiring creation, these operations return an existing g-point for any pair of numeric arguments. [They could all be treated as constructors.] [If more than one geometric space is known in an object system, then such operations would need an additional argument to designate the space to which the point belongs.]

Each of these operations has an inverse, which can be used to "cast" a point into a displayable pair of numbers. If m is a movable point, then

• Location(m) returns a g-point, which is not itself a displayable result.
• Point2Rect(Location(m)) returns a displayable pair of numbers representing the rectangular coordinates of the g-point.

Syntactic devices in a particular language can elide such explicit constructs, allowing something like < -15,0> to be recognized as a point in the appropriate context. The corresponding semantics, however, are described in terms of such operations.

What is the id-ref of a g-point? That should be transparent to users, depending on the local implementation. It might be a structure containing an identification of the type of coordinate system, together with two numbers. A g-point might have several such id-refs, one for each type of coordinate system. (This assumes there is only one two dimensional space, with one origin. If not, the id-ref might be more complex.) It's also possible to assign an arbitrary oid to a g-point, provided that (a) no explicit creation event is required to make one come into existence, and (b) there are not two distinct g-points having the same rectangular coordinates. Whatever the choice, it should have no effect on the results of user operations on points.

What is the id-ref of an m-point? So long as they are moveable, it can't depend on the location. Furthermore, since several might have all the same property values, they really do need to be created explicitly. (The explicit creation might be included in the execution of another operation, such as one creating a line or a circle.) The id-ref of an m-point has to be a system generated oid.

Does it make sense to say that a point is a pair of numbers? Different implementations might choose to implement g-points differently, using different coordinates to represent them. And it clearly doesn't make sense to say that an m-point is a pair of numbers, unless we expect the system to update every reference to the point when it moves.

What has all this to do with invention, reference, and allocation? To begin with, m-points need to be invented, while g-points don't. An expression like "Create m-point" invents a new m-point; an expression like "Create g-point" doesn't make sense. An expression like Rect2Point(< -15,0>) is a reference to an existing g-point, without creating anything new. As far as allocation goes, g-points may not need anything allocated. When and how space is allocated for information about an m-point is really up to the implementation. It could happen when the m-point is created, or when it is first given a location.

Location does not return displayable results without being cast into appropriate coordinates. Casting is just another operation application.

6 APPLYING OPERATIONS

Object systems are made to do things by symbols passed across their interfaces by users. The symbol which is passed across an object interface during one of these events will be called a request. Requests can generally be treated as expressions, which can be decomposed (parsed, translated) in various ways into significant constituent symbols. A particularly important constituent will be called an invocation (informally similar to a function call or procedure call), which can further be decomposed into an operator part and an operand part which are intended to eventually designate an operator object and an operand object. Details of how this happens will be explored later. Very often, the operator part is a symbol intended to invoke one of several operations which have that symbol as their name. Sometimes the operand part designates a composite object whose constituents are thought of as multiple operands for the operator.

An invocation is itself an elementary form of request or expression. An id-ref is itself an elementary form of operand part. A variable behaves much like a function which takes no arguments. A constant is essentially a non-updatable variable. Variables and constants are expressions, and so are literals.

What might happen when a user applies an operation to some objects? Zero or more of the following:

• Some information is returned, usually considered to be the value of the invocation.
• An "exception" is raised.
• Update occurs.

Exceptions (also called conditions) provide information about the request to the user, other than the returned value itself. Possibilities include:

• The operator part does not yield a reference to a known operator.
• The operand part does not yield a reference to a known object, i.e., a valid id-ref.
• There is no known implementation of the designated operator for the designated operand. We will call this a violation condition.

  An operator f is applicable to an object x if the request f(x) does not raise a violation condition.

• No value will be returned. We will call this a void condition.
• Other unusual occurrences or errors.

Updates are not immediately apparent to the user. They become apparent in the altered results of future requests.

Polar and rectangular coordinates are both properties of points. Storing and representing them one way or another are different implementations.

That reminds us that "implementation" takes place on both sides: storage format internally and presentation format for user.

"Materialization" for the user occurs when returning values into the user's program space, and when displaying results on output devices. And also when absorbing requests from input devices.

Thus we have presentation form <-> abstraction <-> storage form.

An operation f is assertable (updatable) if there is an operation g(f,x,y) whose execution causes a subsequent request f(x) to return the value y. This commonly takes one of two forms:

• The operation g is specific to f. Hence there are many such operations, and f does not have to be mentioned explicitly as an operand: g(x,y) => f(x)=y. This in turn has three common syntactic variants:
  • The updater g is explicitly named in the definition of f, e.g., Move(x,y) is named as the updater for Locate(x).
  • There is a fixed naming convention, so that the updater for f is named something like Set_f.
  • Users may not use the name f directly. There is a fixed naming convention so that retrieving the value of f is done by Get_f and updating is done by Set_f.
• There is a single assignment operation applicable to all assertable operations, such as Assign(f,x,y). This could be written in an infix assignment syntax: f(x)<-y.

7 BUT WHAT EXACTLY IS AN OBJECT?

It depends on what sort of answer you seek. One style of answer tries to visualize an object as a tangible bundle of data and code, something you could "point" to inside a computational system. One reaction to that is to say this is too closely tied to specific implementations.

Another answer says that an object itself is an abstraction, which has various manifestations in a computational system. Its id-ref represents the essential concept, the very existence, of the object itself. The object is represented wherever this id-ref occurs. The object is "known" to the object system so long as the object system can recognize its id-ref as a valid id-ref, even if it doesn't happen to occur in the system at the moment. Information about the object is manifest as the results of various operations, which can be implemented in various possible configurations of stored data and computational processes.

8 WHAT DO USERS NEED TO KNOW?

Schemas (object system interface descriptions) exist to enable users to choose the appropriate operators and operands for accomplishing certain tasks via a given object system interface. What they need to know is:

• Which objects are known at the interface.
• Which operators are known at the interface.
• What will happen when certain operators are applied to certain objects.

It would be absurd to enumerate the known objects individually, or describe the effects of operations on individual objects. There are infinitely many known objects, and many of them don't exist yet. That's why types were invented, as an abstraction that lets us talk about collections of similar things rather than about each individual thing.

(We deliberately choose the term "type" rather than "class", a common alternative, which we will use in a different sense later.)

Types are objects, although many real object systems don't treat them so. They also have the three modes of existence.

If an operation f is defined on a type t, then f(x) will not cause a violation condition for any instance x of t. We then say that the operation f is applicable to the type t and any subtype thereof.

What users don't need to know:

• Formats of id-refs. (Users do need to know the presentation format when id-refs are exported into the user's space.)
• How information (function values) are stored or computed, including forms of representation as well as clustering, and details of procedures which implement functions.
• How equality and operations are defined or executed.
• How constructor operations are defined or executed.

9 WHAT DO IMPLEMENTERS (IMPLEMENTATIONS?) NEED TO KNOW?

[Somebody, perhaps the object system infrastructure, needs to know enough to use the appropriate implementation.]

Each operation f applicable to a given object x has a particular implementation, in terms of a data structure and/or computational specification (method). Another object y may have a different data structure and/or method in its implementation of f. The data structure holds information specific to an individual object, but many objects may use the same format for the data structure, and many objects may use the same method.

The data format and method could conceivably be specified for each object to which f is applicable, and specified anew for each new object. However, it makes far more sense to use a classification scheme, just as with types. We choose to use the term "class" for this purpose. A class specifies implementations for the operations defined on a particular type of object. There may be several classes providing different implementations for the same type of object. Each instance of a type must belong to exactly one of its classes.

However, a user should not know or care about the class to which an object belongs. It should even be possible to change the class of an object (within type) without affecting the user. The mechanism for choosing an appropriate class when the user creates an instance of a type should be transparent to the user.

The complete specification of a class includes:

• A name.
• Identification of the type which it implements.
• Data formats and methods for each operation defined on the type. These need not be separate. A single piece of code and a single data structure might embody the implementations of several operations, perhaps via case statements or multiple entry points.

In most object-oriented systems, schemas currently intermix class and type specifications. They should be separable. It should be possible to have several class specifications refer to the same type specification. This is sometimes inconvenient, since there are many detailed cross references from the name and signature of a method to the name and signature of an operation. However, modern graphical interfaces should make it easier to embed an active copy of a type specification into a corresponding class specification for ease of reading and maintenance.

An experimental example:

CREATE TYPE Circle
FUNCTIONS (
Center -> Point ASSERTABLE;
Radius -> Number ASSERTABLE;
Diameter -> Number ASSERTABLE;)

CREATE CLASS Circle1 FOR Circle
FUNCTIONS (
Center AS STORED (format);)

CREATE CLASS Circle1a SUBCLASS OF Circle1
FUNCTIONS (
Radius AS STORED (format);
Diameter(x) AS 2*Radius(x),
ASSERTION x,y: Radius(x)<-y/2;)

CREATE CLASS Circle1b SUBCLASS OF Circle1
FUNCTIONS (
Radius(x) AS Diameter(x)/2,
ASSERTION x,y: Diameter(x)<-2*y;
Diameter AS STORED (format);)

Every instance of the type Circle must also be an instance of one of the leaf classes Circle1a or Circle1b.

10 ORGANIZATION OF SCHEMAS

Users need to know the following about an operation:

• A name by which it can be invoked.
• Under what conditions this specific operation will be invoked.
• The maximal type of operand to which it is applicable, i.e., the argument type on which it is defined.
• The type of result which will be returned, if any.
• Other things about its behavior, e.g., what determines the particular result value to be returned, what updates does it cause, what does it send back out across the obsys interface.
• Whether it is assertable, and how.
• Which conditions might be raised.
• [Maybe more, e.g., having to do with synchronization.]

Additional information needed about types:

• Which types are known?
• Which type constructors are known?
• How do they relate to each other in terms of shared instances (subtypes) or function applicability (inheritance).

Schemas for object-oriented systems frequently organize this information by clustering it around types [ref usobmod]. That is, a type is described with a list of operations defined on it. This implies some sort of containment and clustering, as though the values of these operations for a given object "belonged" to the object and were maintained in a distinct cluster. We have made no such assumptions about the nature of objects as yet from the user's point of view. Such assumptions are usually more relevant to the implementations. They can be relevant to users when operations are provided for locating, moving, or copying certain objects.

11 NULL

Null is the condition which arises when evaluating an expression returns nothing (i.e., a request causes the void condition). IsNull is a predicate on expressions:

IsNull: Expression -> Boolean.

IsNull(e) is true if evaluating e returns nothing.

NullCon is a constant whose value is empty. IsNull(NullCon) is always true.

Null expressions can't be compared, since there are no objects to compare. Hence IsNull(NullCon=NullCon) is always true.

EqOrNull is a binary predicate on expressions:

EqOrNull: <Expression, Expression> -> Boolean.

EqOrNull(e1,e2) is denoted e1~e2. The predicate is True if

• IsNull(e1) and IsNull(e2), or
• ¬IsNull(e1) and ¬IsNull(e2) and e1=e2.

¬p denotes p=False. Equality means identity, i.e., reference to the same object:

e1=e2 => Card({e1,e2})=1.

12 AGGREGATES

The following aspects of aggregates need to be distinguished:

• Instances
• Types
• Instance constructors
• Type constructors

12.1 Aggregate Instances

An aggregate is an object which can be said to contain other objects. Formally, we define

Contains: <Aggregate, Object> -> Boolean,
Occurs: <Object, Aggregate> -> NonNegativeInteger

with Contains(g,x) being True if g contains x, and Occurs(x,g) giving the number of times it occurs. If we let Boolean values be equivalent to 1 and 0, we have

Contains(g,x) = Occurs(x,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).

12.1.1 Bags and Sets

A bag is an aggregate which is not an indexed aggregate (see below). A set is a bag which satisfies the constraint

FORALL x: Occurs(x,g)=<1.

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: Occurs(x,g1)=Occurs(x,g2).

12.1.2 Indexed Aggregates

Indexed aggregates provide a generic way of describing things like sequences and tuples and arrays.

An indexed aggregate x has an index set characterized by the operations:

IndexSet: IndexedAggregate -> Set`Object',
Extract: <Object, IndexedAggregate> -> Object.

12.1.2.1 Compact Aggregate

i IN IndexSet(g) => ¬IsNull(g[i]).

12.1.2.2 Sequence

The index set is an initial subset of the positive integers 1,...,n. Arity=n.

12.1.2.3 0-Sequence

The index set is an initial subset of the non-negative integers 0,...,n-1. Arity=n.

These come in compact and non-compact varieties.

An OSQL Tuple is a 0-sequence.

12.1.2.4 Record

12.1.2.5 Array

12.1.2.6 Regular Bag

A regular bag has an associated index set, which is not an index set of the bag itself, but which is the index set for each object occurring in the bag.

12.2 Aggregate Instance Constructors

A constructor is an operation which returns an existing object. It does not create anything new. Why certain operations are designated as constructors is not entirely clear. The result of a constructor expression is often an object which has the arguments of the constructor expression as its components, or as its properties of some other sort.

[Should seek a term other than "constructor", which has the unintended connotation of building something new. Something like "designator" or "referral" might be better.]

[Hypothesis about what distinguishes a constructor from other operations. If we trace the history of the value of a function or variable in terms of which got assigned from which, it must always trace back eventually to a constructor operation. I.e., if a function or variable has an aggregate value, it must have gotten the value by assignment from another function or variable, or from a constructor expression. Is that true?]

A generalized model of indexed aggregate construction is given by an expression of the form

ConsAgg(<<i1,e1>,...,<in,en>>),

12.2.1 Sequence Constructor

For a sequence constructor the index set is omitted, defaulting to the integers 1,...,n:

ConsSeq(<e1,...,en>) ::= ConsAgg(<<1,e1>,...,<n,en>>),

which is often abbreviated to the form

<e1,...,en>.

This definition appears circular, since one has to provide the sequence constructor with a sequence of arguments. A non-circular definition arises by defining a sequence itself to be an operator which yields another sequence. Thus, if s is a sequence of arity n, then s(e) returns a sequence of arity n+1 whose n+1st element is the value of e. There is an empty sequence denoted <>. The expression <>(e1) returns a sequence of arity 1, <>(e1)(e2) returns a sequence of arity 2, and so on. The syntactic form <e1,...,en> is equivalent to <>(e1),...,(en).

The expression <>, i.e., ConsSequence(), yields a sequence of arity 0. There is exactly one such sequence.

12.2.2 Compact Sequence Constructor

The compact sequence constructor ConsCompSeq(<e1,...,en>) essentially constructs a sequence from the non-null expressions in the argument sequence. To define it, we can first define a RemoveNulls operator on sequences:

RemoveNulls: Sequence -> Sequence.

RemoveNulls(s) is defined recursively:

1. Let i be the least integer 1 =< i =< n=Arity(s) such that IsNull(s[i]).
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 constructor can then be defined as

ConsCompSeq(<e1,...,en>) = RemoveNulls(<e1,...,en>).

If none of the argument expressions is null, then

ConsCompSeq(<e1,...,en>) = <e1,...,en>.

12.2.3 0-Sequence Constructors (OSQL Tuple and List Constructors)

0-sequence constructors yield sequences using zero origin, i.e., having index set 0,...,Arity(s)-1. A ShiftLeft operation maps a sequence into the corresponding 0-sequence (essentially by decrementing each integer in the index set), so that s[i]=ShiftLeft(s)[i-1].

A 0-sequence constructor can then be defined as

Cons0Seq(<e1,...,en>) = ShiftLeft(<e1,...,en>).

A compact 0-sequence constructor can then be defined as

ConsComp0Seq(<e1,...,en>) = Cons0Seq(ConsCompSeq(<e1,...,en>)).

The constructors can take zero or more expressions as operands.

12.2.4 Bag and Set Constructors

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 Occurs(x,b) = SUM[i](s[i]=x). Let the function Seq2Bag map a sequence into this corresponding bag. A Bag instance constructor can be defined as

ConsBag(<e1,...,en>) = Seq2Bag(<e1,...,en>).

It is often denoted [e1,...,en].

Every bag b has a unique corresponding set s such that Occurs(x,b)>0 <=> Occurs(x,s)=1. Let the Distinct function map a bag into this corresponding set. A Set instance constructor can be defined as

ConsSet(<e0,...,en-1>) = Distinct([e0,...,en-1]).

It is often denoted {e1,...,en}.

Note that a bag instance constructor 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

[] = {} = [NULL] = {NULL} = [NULL,NULL] = {NULL,NULL} etc.

These expressions all yield the same object.

12.3 Aggregate Types and Type Constructors

An aggregate type is a type whose instances are aggregates whose components satisfy certain type constraints. Aggregate types are ephemeral, and they exist exactly whenever the types in their definitions exist. An aggregate type constructor is an operation which returns an existing aggregate type. It does not create anything new. Details depend on the specific aggregate type constructor.

12.3.1 Bag and Set Types

The aggregate type constructor ConsBagType maps a type into an aggregate type:

ConsBagType: Type -> AggregateType.

If t is any existing type, then ConsBagType(t) is an existing aggregate type, recursively. The instances of ConsBagType(t) are all the bags whose members are instances of t:

b IN ConsBagType(t) <=> Occurs(x,b)>0 => x IN t.

Note that we are saying that b is an instance of the type T, where T is the type returned (constructed) by ConsBagType(t).

For example, if a function is constrained to return results of the type ConsBagType(Integer), then any result returned by the function will be a bag of integers.

A note on notation. OSQL uses BagType(t) for this constructor, but I find that misleading, since the nomenclature suggests that BagType is itself a type. It's not; it's a constructor operation. For readability, I will adopt the notation Bag`t' to mean ConsBagType(t), so that Bag`t' can be read as the "name" of the type returned by ConsBagType(t).

We have

t1 SUBSETEQ t2 => Bag`t1' SUBSETEQ Bag`t2'.

Thus Bag`Employee' SUBSETEQ Bag`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 is the id-ref of a person, then [@sam] might be an instance of Bag`Employee', Bag`Teacher', Bag`Student', etc. Furthermore, [@sam,@jim] is an instance of Bag`t' whenever Sam and Jim are both instances of t, and it is not an instance if either Sam or Joe is not an instance of t.

Note that we have not defined Bag itself as a type. If we did, it would be equivalent to the type Bag`Object', which has all bags as its instances. It is a supertype of Bag`t' for any t.

12.3.2 Sequence Types

Many sorts of sequence type constructors can be defined, with various sorts of constraints on origin, arity, and types of their components.

Perhaps the simplest is the general sequence type constructor ConsSeqType, denoted by Sequence`t', which again maps a type into an aggregate type. Sequence`t' refers to a type whose instances are sequences in which each non-null constituent is of type t. It is very similar to Bag`t'. In particular,

t1 SUBSETEQ t2 => Sequence`t1' SUBSETEQ Sequence`t2'.

Also, <@sam,@jim> is an instance of Sequence`t' whenever Sam and Jim are both instances of t, and it is not an instance if either Sam or Joe is not an instance of t.

If there was a type named Sequence, it would be equivalent to Sequence`Object', a supertype of Sequence`t' for any type t.

The constructor 0-Sequence`t' can be defined in exactly the same way. It refers to the type whose instances are 0-sequences in which each component is an instance of t.

Constructors CompSeq`t' and Comp0Seq`t' can also be defined similarly for compact sequences. We have

CompSeq`t' SUBSETEQ Sequence`t',
Comp0Seq`t' SUBSETEQ 0-Sequence`t',

since every compact sequence of t's is a sequence of t's.

Of special interest are sequence types whose instances are constrained to be of some fixed length (arity), since this includes various notions of tuple and record. In particular, the aggregate type constructor ConsTupleType maps a sequence of types into an aggregate type:

ConsTupleType: Sequence`Type' -> AggregateType.

We extend our previous notation so that

Tuple#t1,...,tn# ::= ConsTupleType(<t1,...,tn>).

Note the distinction. Tuple#t1,...,tn# refers to a type, not a tuple object. <t1,...,tn> is a tuple of types, but it is not itself a type.

Tuple#t1,...,tn# refers to the type whose instances are all sequences g with Arity n such the gi IN ti.

For tuple types, the subtype relationship is

Tuple#t11,...,t1n# SUBSETEQ Tuple#t21,...,t2m# <=> n=m & 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

Tuple#Object#, Tuple#Object,Object#, Tuple#Object,Object,Object# etc.

are all distinct types. Thus it may not be useful to consider a type called Tuple, since it would include tuples of all lengths. In fact, it would probably be indistinguishable from the type called Sequence, i.e., Sequence#Object#.

Tuple#Programmer, Engineer# could be a subtype of List#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 list type. In general,

Tuple#t1,...,tn# SUBSETEQ Sequence#t#,

where t is any common supertype of t1,...,tn.

12.4 Immutable (Literal) and Mutable (Surrogate) Aggregates

The aggregates we have described so far are immutable. They don't change. Operations which appear to change them should be viewed as replacing one with another. If we add one to the second component of <Sam,17>, we haven't altered the tuple. <Sam,17> is still <Sam,17>. What we have done is to replace <Sam,17> with <Sam,18>.

The immutable aggregates are also ephemeral. Things like {Sam}, {Sam,1}, [Sam,Sam], <Sam, 1, Sam> are all known to exist exactly whenever Sam is known to exist. Aggregate constructors yield existing immutable aggregates.

Immutable aggregates can be assigned as the values of variables or other functions.

If we want objects which behave like mutable mortal aggregates, we can:

• Define Carrier as a new type of surrogate object. They are mortal, i.e., get explicitly created and destroyed, and have system-assigned id-refs.
• Define Cargo as an operation which maps a carrier into an immutable aggregate, which can be considered the "value" of the carrier.
• Define CargoType as an operation which maps a carrier into an aggregate type. The cargo of a carrier must be an instance of the carrier's CargoType.
• Overload certain operations on immutable aggregates to apply to carriers. E.g., for a carrier c,

  Card(c) = Card(Cargo(c)),
  Occurs(x,c) = Occurs(x,Cargo(c)).

Carrier objects behave a lot like variables.