Dec '99

Inheritance and Instantiation

Part 1

Nomenclature:

To be clear on the effects of inheritance and instantiation, there has to be definitions for these two concepts. Let us define the symbols "" and "" to be read as:

"A B" or "B A" as "B is a partial instance of A"

"A B" or "B A" as "B is a descendent of A"

Just because the symbols defined above refer to "inheritance" and "instantiation", it does not mean that we are going to use those concepts in their usual sense. These symbols will be defined explicitly below. But we will also see that they match very well to our intuitive definitions of these two concepts. The language of this text also refers to the concepts of up and down. In the cases of "A B" and "A B" we say A is above B. Therefore we can speak of a path made from B "up to" A, or from A "down to" B.

Definitions:

An attribute of an object is either a method or a field. Every one of these attributes has to have a unique identifier, called a UID. Using this concept we define some functions that act on objects:

DEF(A)  Returns a set of UIDs for all defined attributes of A.
ATT(A)  Returns a set of UIDs for all accessible attributes of A.

Here is an example to the application of the above definition. Consider a the set of all people (with UID="Person"). We also define all people to have a defined attribute (UID="Name"). If we consider a particular person (UID="Kyle"), then that person has an accessible attribute called "Name". More succinctly we say:

DEF("Person") = {"Name"}    //The set of all people defines the Name attribute
ATT("Person") = {}          //but set has no accessible attributes.
DEF("Kyle")   = {}          //Kyle does not define any attributes,
ATT("Kyle")   = {"Name"}    //but does have an attribute accessible via "Name"

This paper is abstract and is not intended to provide implementation details. This example was used only to get a 'feel' for how the theorems below can be applied. In the example we see a notion of instantiation, we define it now formally, along with inheritance.

Definition A:

A B iff DEF(A) ATT(B) (A1)

A B iff DEF(A) DEF(B) (A2)
and ATT(A) ATT(B) (A3)

We will also add an axiom. It is important that for every attribute there is a definition for that attribute.

Axiom B (Reasonable Instantiation):

b, where b ATT(B), A such that b DEF(A) and A B.

Part 2

Instantiation:

Definition C (Full Instantiation):

We write "A --*+ B" and say "B is a full instance of A" IFF A B and C, C B implies C A.

Theorem 2.1

If A --*+ B then DEF(A) == ATT(B)

Proof:

Inspecting (A1), we see we only need to prove that DEF(A) ATT(B). Select any b ATT(B). We know from Reasonable Instantiation that C such that b DEF(C) and CB. Full Instantiation forces C to be an ancestor of A: C A. Then using (A2) can conclude that b DEF(A). Therefore, since b was arbitrary we see DEF(A) ATT(B).

An object that is a direct instance of itself has strict consequences. You can see that any attributes defined in an object are also implemented. This will lead us to the definition of an auto object later.

Inheritance:

Theorem 2.2:

A A is always true.

Proof:

DEF(A) DEF(A) (def A2)

ATT(A) ATT(A) (def A3)

"A A" can be used liberally in ER modeling if it happens to improve understanding.

Theorem 2.3:

If A B and A B then A == B.

Proof:

ATT(A) ATT(B) ATT(A) (def A2)
DEF(A) DEF(B) DEF(A) (def A3)

Theorem 2.4:

If A B and A +*-- B then DEF(B) == ATT(B).

Proof:

We see from (2.1) that DEF(B) == ATT(A). From (A2) we also know that ATT(A) ATT(B), so DEF(B) ATT(B). Now, we are left to prove only DEF(B) ATT(B): Select any b ATT(B). We know from Reasonable Instantiation that C such that b DEF(C) and CB. Full Instantiation forces C to be an ancestor of A: C A. (A2) states DEF(C) DEF(A) DEF(B) so we must conclude that b DEF(B). Now we know DEF(B) == ATT(B).

This is the most important theorem of this paper. It allows for a closed, self-describing system. The implication of this theorem begs us to create a special definition.

Definition D (Auto Object):

A is an "Auto Object" iff DEF(A) == ATT(A).

Lemma:

If A --*+ A then A is an Auto Object.

Theorem 2.5:

If A B and A +*-- B then A B.

Proof:

From (A2) we know that DEF(A) DEF(B). We can use the result of (2.4) to note, simply, that DEF(A) ATT(B).

This is very interesting result. Due to the cyclical nature of the relationships, B is actually an instance of A. We will use this special construction to build the Object Hierarchy later in this paper.

Part 3

Interactions involving 3 objects allow us to see relationships between the instantiation and inheritance relations.

Theorem 3.1: (Transitivity of Inheritance)

If A B and B C then A C

Proof:

DEF(A) DEF(B) DEF(C) (def A2)
ATT(A) ATT(B) ATT(C) (def A3)

Theorem 3.2 (Transitivity of Instantiation):

If A B and B C then A C. (3.2.A)
If A B and B C then A C. (3.2.B)

Proof (3.2.A):

DEF(A) DEF(B) ATT(C) (def A2, A1)

Proof (3.2.B):

DEF(A) ATT(B) ATT(C) (def A1, A3)

What we can conclude from this theorem is that by inspection of the inheritance/instantiation hierarchy one can determine partial instantiation of any object, C, by finding a special path to reach an A. This special path must include one, and only one, instantiation relationship. The restriction of "only one" is demonstrated by the following theorem

Theorem 3.4

If A B and !(A B) and |DEF(A)| > 0 then we can construct a C such that B C and !(A C).

Proof:

The wording here is a little difficult because we are proving that ATT(C) has no relation to DEF(A). If we start by supposing we could not construct a C such that DEF(A) ATT(C), then our proof would be done. If we could find such a result then we can construct another, C'. Note that DEF(A) ATT(C) implies |ATT(C)| > 0. Construct C' by removing a single UID from ATT(C), and subsequently from DEF(B). We know we can do this because DEF(B) is not restricted by holding DEF(A) fixed. Our C' does not satisfy DEF(A) ATT(C').

Definition E (Remote Objects):

C is "remote" wrt A IFF DEF(A) ! ATT(C)

Theorem 3.5:

If A where DEF(A) is empty then C, A C.

Proof:

Trivial, using (A1).

Theorem 3.4 gives us insight into the implications of a very special, but important scenario. We have rule system that, given almost any object, allows the construction of other objects that are not an instance of it. The impact of this conclusion is demonstrated by supposing that A is the description of ALL 'objects'. There could exist a C that is not an instance of A, and not an 'object' at all! Theorem 3.5 gives us the conditions that must be met to build an object that describes all objects. The emptiness of DEF(A) that allows A C, C.

Let us construct the top-most part of the object hierarchy:

We will make the Class of all Objects (aObject) and the Class of all Classes (aClass). Since the set of all classes is a subset of the set of all objects we can conclude that aObject aClass. Since aObject is also a Class, it is an instance of aClass (aClass aObject). Using theorem 2.3 we conclude that aClass is an Auto Object. Theorem 2.4 notes that aObject --*+ aClass; a necessary observation that aClass is still just an object.

Using this simple construction we could define attributes that would be common for all objects and all classes. But, as mentioned before, to successfully model everything, there are none. DEF(aObject) is empty, and DEF(aClass) is empty.

The hierarchy can be extended off these two objects. The aClass can be inherited to generate a Java "Class" object, along with all its attributes. The aObject can be extended to generate a Java "Object" object. The inheritance and Instantiation relationships can be added between the two, and all of the Java object hierarchy can be added.

The Java primitives are not objects in terms of the Java specification, but they are still objects in aObject sense. aClass and aObject objects can be extended to define the special attributes for these primitive objects. It is up to the implementor to determine if the JVM operations are attributes of the primitives, or stand-alone functions leaving the primitives with no attributes. Objects without attributes act as place holders, signifying existence, but lack of functionality or structure.

By adding something called Primitive Types, we can design a more traditional hierarchy. These primitive types add attributes from outside the DEF() and ATT() functions. These attributes are exposed in Primitive Attributes.