Eigenclass model

In object-oriented programming, the eigenclass model is an abstract structure that constitutes a fundamental part of the object model using the concept of eigenclasses. Eigenclasses are auxiliary (mostly just fictitious) class-like objects that establish infinite regress via the eigenclass map: for every object x, the eigenclass of x is the unique own meta-object of x that is one meta-level higher than x.

As a complementary constituent to the eigenclass map, the model encompasses the inheritance relation. The composition of the eigenclass map with inheritance gives rise to object membership, a relation between objects, denoted ϵ (lunate epsilon). This relation is a generalization of the instance-of relation and can be viewed as a non-well-founded counterpart of set membership, ∈.

As a result, the eigenclass model provides a uniform and mathematically precise description of the core structure of class-based programming languages in which classes are (or can be considered as) objects. In particular, the model applies to the following languages: Ruby, Python, Scala, Java, Smalltalk, Objective-C, CLOS, Perl. Generally, the model relates to the core part of data models in which classes appear as objects. As a consequence, the model relates to ontology languages such as RDF Schema or OWL. A good indicator of applicability is the presence of the notion of metaclass.

One can distinguish two degrees of applicability. High degree is assigned to languages that allow an actual reference to an eigenclass: Ruby, Smalltalk, Objective-C and, in a lesser sense, Scala. Low degree is assigned to languages in which eigenclasses are a purely fictitious concept. In this latter case the eigenclass model can be regarded as an abstract device for joining inheritance with the instance-of relation.

History

The inception of the eigenclass model with referenceable eigenclasses can be attributed to Smalltalk-80 which introduced implicit metaclasses. In Smalltalk, every class has its own metaclass, and metaclass inheritance parallels class inheritance.

In 1988, Luca Cardelli introduced the notion of power types which can be regarded as type-theoretic counterparts to eigenclasses. The notion has later been adopted in the field of metamodelling. (Nowadays, the single word "powertypes" is preferred.)

A full and consistent application of the eigenclass model appeared in 1995 as a core part of the Ruby programming language, created by Yukihiro Matsumoto. The term "eigenclass" emerged around 2005 in the Ruby community. In 2008, the term has been established in an authoritative book, replacing the previously used "singleton class" (although in Ruby 1.9, the corresponding introspection method is still named singleton_class).

By simplification, the development history of the eigenclass model can be viewed as a 3-stage extension of a universality principle, summarized by the following table:

Year	Inventor	The principle	… in terms of the eigenclass model
c. 1980	James Althoff	Every class has its own metaclass.	Every class has an eigenclass.
c. 1988	Luca Cardelli	Every type has a power type.	Every class and every eigenclass has an eigenclass.
c. 1995	Yukihiro Matsumoto	Every object has an eigenclass.

The canonical structure of ϵ

In its rudimentary form, the eigenclass model can be described as a canonical structure (O, ϵ) with subsequently introduced notation, terminology and axioms. For convenience, an example structure is provided first.

Example

The following diagram shows an example of the canonical structure (O, ϵ), together with corresponding Python code.

r = object c = type class M(c): pass class A(metaclass=M): pass class B(A): pass b = B()

The structure contains 6 primary objects: 2 helix classes (the inheritance root r and the instance root / metaclass root c), 3 other classes (M, A and B), and 1 terminal object (b). Right-directed arrows (in gray) show the eigenclass map, up-directed arrows (in green) show the child-parent relation of inheritance. The ∫-shaped arrows are the twist links.

Eigenclasses are shown as unnamed nodes in gray. Each eigenclass chain is infinite – the diagram displays just an initial part, without descendants of the fourth eigenclass of r.

The structure contains 2 explicit metaclasses: the metaclass root c and the user-created metaclass M. The remaining inheritance descendants of c (i.e. all eigenclasses except the eigenclass of b) are implicit metaclasses.

Objects

The universum of the model is the set O of abstract entities called objects. By further axioms, this set is asserted to be countably infinite.

Object membership

The object membership relation, ϵ, is a (binary) relation between objects. For objects x, y, if x ϵ y, then x is a member-of y and y is a container-of x. By axiom (1), object membership is uniquely decomposable into the eigenclass map and the inheritance relation, which can be written as

(ϵ) = (.ec) ○ (≤)

where the composition symbol '○' is interpreted left-to-right, i.e. x ϵ y iff x.ec ≤ y.

Inheritance

The inheritance, denoted ≤, is a relation between objects defined by

x ≤ y   iff   y ϵ a implies x ϵ a for every object a   (i.e. every container of y is a container of x).

Axiom (2) asserts antisymmetry of ≤, so that inheritance is a partial order. Furthermore, axiom (1) asserts that (ϵ) ○ (≤) = (ϵ), i.e.

x ≤ y   only-if   a ϵ x implies a ϵ y for every object a   (every member of x is a member of y),

which indicates that the inheritance relation, ≤, has the semantics of the subset relation, ⊆.

If x ≤ y then x is a descendant of y and y is an ancestor of x. For an object x, x.↥ (resp. x.↧) denotes the set of all (non-strict) ancestors (resp. descendants) of x. Similarly, for a set X of objects, X.↥ (resp. X.↧) is the upset (resp. downset) of X. Direct ancestors (covers) of x are called parents of x.

Eigenclasses

The eigenclass-of an object x, denoted x.ec, is the container of x that is least (lowest) in the inheritance ≤. Axiom (1) asserts that every object has its eigenclass. Furthermore, (1) and (2) imply that the .ec map is an order embedding with respect to ≤. In particular, .ec is injective – different objects have different eigenclasses. Another consequence of (1) is that for every objects x, y,

x ϵ y.ec   iff   x ≤ y,

showing that the eigenclass map corresponds to the powerset operator.

The i-th application of .ec to x is denoted x.ec(i). By further axioms, each component of the eigenclass map is an infinite chain x = x.ec(0), x.ec = x.ec(1), x.ec.ec = x.ec(2), … starting in a primary object x.

An eigenclass is an object that belongs to O.ec, the image of .ec.

Primary objects

Objects that are not eigenclasses are primary. Axiom (6) asserts that the set of all primary objects forms a closure system in inheritance, i.e. the set appears as the image of a (necessarily unique) closure operator, denoted .c, in inheritance. For each object x, the primary object x.c is the least primary ancestor of x.

Axiom (7) asserts that .c preserves ϵ. As a consequence, .c is a homomorphic projection of (O, ϵ, ≤) onto the primary structure, (O.c, ϵ, ≤).

Primary objects are further divided into terminals and classes which can be expressed as

O.c = T ⊎ C.

Classes

An object is a class if it is primary and either is its own member or is not maximal in inheritance (i.e. has parents). The set of classes is denoted C. Classes together with eigenclasses form the set of all descendants of the inheritance root r, i.e. r.↧ = C ⊎ O.ec. Using the is-a naming convention, this set is equal to the set of Classes, where Class is the name for the instance root c.

Terminal objects

An object is (a) terminal if it is neither a class nor an eigenclass. The set of terminals is denoted T. Therefore, the set of objects is a disjoint union of the sets of terminals, classes and eigenclasses:

O = T ⊎ C ⊎ O.ec.

Terminals can be equivalently characterized as objects that are both maximal and minimal in inheritance.

Class map

Eigenclass model - The class map

The class-of an object x, denoted x.class, is the smallest container of x that is a class. Axiom (6) asserts that x.class is defined for every x. Equivalently, the .class map can be written as .ec.c where .c is the closure operator in ≤ such that the image O.c is the set of primary objects. As a consequence, .class is a monotone map.

Axiom (8) asserts that the .class map forms a tree – the instance tree.

The diagram on the right shows the class map for the example structure, in the restriction to primary objects. To illustrate the .ec.c composition, the arrows are drawn along eigenclass paths.

Instance of

The instance-of relation is defined as the range-restriction of object membership to classes, i.e.

x is an instance of y   iff   x ϵ y and y is a class.

The relation can be expressed as (ϵ) ○ (.c). The direct instance-of relation is the .class map taken as a relation, i.e.

x is a direct instance of y   iff   x.class = y.

The direct-instance-of, instance-of and member-of relations form an inclusion chain:

(.class)   ⊂   (ϵ) ○ (.c)   ⊂   (ϵ).

Membership as is-a

If x is a member of an object named B (in particular, if x is an instance of the B class) then one can say that x is-a B. The set of all members of B (instances of the B class) can be referred to as Bs. If A and B are classes such that A ≤ B then one can say that

an A is a B,

meaning that an instance of A is also an instance of B. Unfortunately, this leads to an interpretation (which can be considered a misinterpretation) of the is-a relation such that

the A class   is-a   the B class,

i.e. the is-a relation is regarded as synonymous to the inheritance relation.

Helix

An object x is a helix object if it is its own member, i.e. x ϵ x. The set of all helix objects is denoted H. Axiom (4)(c) asserts that (H, ≤) is a linear order so that the object membership structure restricted to H can be visualised as a circular helix. The helix has the inheritance root, r, as a start-point (origin), the other side is infinite. Eigenclass chains are parallel to the helix axis. Each complete turn away from the origin corresponds to one application of the eigenclass map.

Inheritance root

The inheritance root, r, is the highest helix class – a common ancestor of all non-terminal objects. Its existence is asserted by axiom (4)(a).

Instance root

The instance root, c, is the lowest helix class, usually named Class. It can also be specified as r.class or, explaining the terminology, as the root of the instance tree – it is the only object x such that x.class = x. Axiom (4)(b) asserts that c is different from r.

Twist links

The child-parent pair (r.ec, c) is the (front) twist link. Axiom (4)(d) asserts that r.ec is the only child of c. In addition, it is asserted that c is the only parent of r.ec. The same conditions hold for all twist links (r.ec(i+1), c(i)).

Reduced helix

Let R denote the eigenclass chain {r, r.ec(1), r.ec(2), …} of the inheritance root. Being a distinguished subset of H, the set R can be called the reduced helix. Helix objects are the ancestors of objects from the reduced helix, i.e. H = R.↥.

Assuming finiteness of the set of primary objects (asserted by (9)(b)), condition (9)(a) can be equivalently replaced by the requirement that the reduced helix has no lower bound in inheritance, i.e. there is no object x such that R ⊆ x.↥. As a consequence, R is a closure system in (O ∖ T, ≤) and so is H.

Metaclasses

An object is a metaclass if it is a descendant of c, so that the set of all metaclasses is simply expressed as c.↧. The instance root c is therefore also the metaclass root.

Metaclasses are either explicit or implicit according to whether they are classes or eigenclasses, respectively. An object is an implicit metaclass iff it is an eigenclass of a non-terminal object.

Under the assumption that every class has a direct instance, i.e. O.class = C, the following symmetric formula applies:

c.↧ = O.ec.class ⊎ O.class.ec ⊎ O.ec.ec,

i.e. an object is a metaclass if it is either the class of an eigenclass or the eigenclass of a class or the eigenclass of an eigenclass. Using axiom (7) and substituting C for O.class we obtain

c.↧ ∖ O.ec(2) = C.class ⊎ C.ec,

i.e. aside from higher-order eigenclasses, explicit metaclasses are classes-of classes (C.class) whereas implicit metaclasses are eigenclasses-of classes (C.ec).

The classical definition of metaclasses as "classes whose instances are classes" applies as follows:

Metaclasses are Classes whose all members are Classes.

This definition is valid if and only if each class that is not a metaclass has at least one terminal instance, i.e. C ∖ c.↧ ⊆ T.class.↥ (in particular, the parent of c = Class must have a terminal instance so that helix classes other that c are ruled out by the "all" adverb).

Axioms

The canonical structure (O, ϵ) of object membership is subject to the following conditions:

1. (1) Containers of an object x are exactly the ancestors the eigenclass of x, i.e.

   (ϵ) = (.ec) ○ (≤)   for a unique map .ec.

2. (2) Distinct objects have distinct sets of containers.
3. (3) Terminals are minimal in inheritance.
4. (4) Helix objects satisfy the following properties:
   1. (a) All non-terminal objects are descendants of a single object, the inheritance root r.
   2. (b) The eigenclass of r has at least 2 strict ancestors.
   3. (c) The set H of helix objects is linearly ordered by inheritance.
   4. (d) For every i > 0, the eigenclass r.ec(i) has no siblings.
   5. (e) Every helix descendant of r.ec is an eigenclass.
5. (5) Descendants of non-helix eigenclasses are eigenclasses.
6. (6) Every object x has a least container that is a class, x.class.
7. (7) For every object x,   x.ec.class = x.class.class.
8. (8) There is a helix object h such that for every non-helix class x, the sets h.↧ and x.↧ are disjoint.
9. (9) The following finiteness conditions hold:
   1. (a) Every object has finite number of ancestors.
   2. (b) The set of primary objects is finite.

Axiom (7) can be expressed without a reference to the .class map as equality of the member-of-instance-of relation with the instance-of-instance-of relation.

The primary structure

The restriction of a canonical structure of object membership to primary objects can be expressed as a structure (O.c, ϵ, ≤) where

• O.c is the set of (primary) objects,
• ϵ is the instance-of relation between (primary) objects,
• ≤ is the inheritance relation between (primary) objects.

Helix classes are (primary) objects x such that x ϵ x. Classes are (primary) inheritance descendants of helix classes. Terminals are the remaining (primary) objects. Metaclasses are the lower bounds of helix classes, i.e. they are objects x such that all helix classes are among ancestors of x. The structure is subject to the following axioms:

1. (p~1) (ϵ) ○ (≤) = (ϵ) = (≤) ○ (ϵ).
2. (p~2) Inheritance ≤ is a partial order.
3. (p~3) Terminals have neither strict descendants nor instances.
4. (p~4) Helix classes are totally ordered by inheritance, and at least two in number.
5. (p~5) Metaclasses cannot have terminal instances.
6. (p~6) Every object x has a least (primary) container, x.class.
7. (p~7) Cycles in ϵ only occur between helix classes.
8. (p~8) The set of primary objects is finite.

Eigenclass model - The primary structure

The diagram on the right shows the primary structure that is the restriction of the example structure. The instance-of relation is obtained as the composition (≤) ○ (.ͼlass) ○ (≤) where .ͼlass is the class map reduction – the "non-inherited" part of the .class map (displayed by dark blue arrows).

Eigenclass completion

Axiom (5) can be considered in the following stronger form since it is satisfied in all mentioned programming languages (and presumably all relevant ones in general):

1. (5') Descendants of eigenclasses-other-than-r.ec are eigenclasses.

Assuming (5'), the object membership structure, (O, ϵ), is uniquely determined by the primary structure, (O.c, ϵ, ≤), up to isomorphism. (Therefore, (O, ϵ) is also determined by (O.c, .class, ≤).)

Given a structure (O.c, ϵ, ≤) between primary objects, the eigenclass completion (O, ϵ) can be constructed in the following steps:

1. Equip each primary object with an eigenclass chain such that distinct primary objects have disjoint eigenclass chains. Let the .ec map be coincident with the successor operator.
2. Extend ≤ to all objects as follows. Let a, b be primary objects, and i, j > 0. Then
   1. a.ec(i) ≤ b   iff   a ϵⁱ b     where ϵⁱ is the i-th composition of ϵ (not yet extended) with itself.
   2. a ≤ b.ec(j)   iff   a is a non-helix metaclass, b is the inheritance root, and j = 1.
   3. a.ec(i) ≤ b.ec(j)   iff   a.ec(i-1) ≤ b.ec(j-1).
3. Extend ϵ to all objects by:   (O, ϵ) = (O, .ec) ○ (O, ≤).

Representation by sets

The eigenclass model can be interpreted by means of set theory. Objects are represented by sets so that object membership structure is induced by set structure. The correspondence is best described via a generalization of the canonical structure such that only those features are axiomatized that are essential w.r.t. set representation.

Essential structure of ϵ

An essential structure of ϵ is a structure (O, .ec, ≤, r) where O is the set of objects, .ec is the eigenclass map between objects, ≤ is the inheritance relation, and r is the inheritance root, a distinguished object. Objects that are not inheritance descendants of r are terminal(s). The structure is subject to the following axioms:

1. (e~1) Inheritance, ≤, is a partial order.
2. (e~2) The eigenclass map, .ec, is an order embedding w.r.t. ≤.
3. (e~3) Objects from eigenclass chains of terminals are minimal in ≤.
4. (e~4) Every eigenclass is a descendant of r.
5. (e~5) The eigenclass chain of r (i.e. the reduced helix R) has no lower bound in ≤.

Like with canonical structures, an essential structure is given by (O, ϵ) where (ϵ) = (.ec) ○ (≤).

The embedding

Any essential structure of ϵ can be embedded into a set V that is formed as a cumulative hierarchy over a set of urelements, U. Elements of U can be pure sets that are minimal both in (V, ∈) and (V, ⊆) so that they just behave like urelements with respect to V. The set V is built in ω+1 stages. The 0-th stage is the set U of urelements. For each natural number i, the i-th stage equals the i-th application of P_⋆, the powerset cumulation operator, defined by

P_⋆(X) = (P(X) ∖ {∅}) ∪ X

where P(X) denotes the powerset of X. The ω-th stage, called superstructure in the field of non-standard analysis, is the union of all previous stages. This set stands for the inheritance root – it is therefore denoted r. The set V then equals the powerset cumulation of r, i.e. V = P_⋆^ω+1(U) = P_⋆(r).

The eigenclass map, .ec, is defined on V by

x.ec = P(x) ∩ r,

i.e. the eigenclass of x is the set of all those subsets of x which belong to some finite stage. Then (V, .ec, ⊆, r) is an essential structure of ϵ. The inheritance relation, ≤, coincides with set inclusion, ⊆, on V. Object membership on V is given by: x ϵ y iff P(x) ∩ r is a subset of y. Terminal objects are the urelements. The following are satisfied:

x.ec = {x}	if x is terminal (or x is from the eigenclass chain of a terminal),
x.ec = P(x) ∖ {∅}	if (and only if) x ∈ r,
x.ec ⊂ x	if (and only if) x ϵ x.

Any subset O of V such that r ∈ O and O.ec = V.ec ∩ O forms an "object system": the substructure (O, .ec, ⊆, r) is an essential structure of object membership. Conversely, any essential structure of ϵ can be represented by such set O. Moreover, such a representation exists that for every x, y from O,

x ∈ y   iff   x ϵ y and x ∈ r.

Specializations

In a particular programming language, the eigenclass model appears in a specialized form. A specialization of the model can be derived from the canonical structure in two steps:

1. Generalize the canonical structure (O, ϵ) by appropriately relaxing some of the axioms, possibly also expanding the structure.
2. Specify additional constraints.

The first step is necessary in most cases – of the above mentioned programming languages only Ruby and Python conform to the canonical structure.

In Ruby

The structure of object membership in Ruby is best explained in two steps by first describing the canonical structure and then the extension via module inclusion.

Canonical reduct

The canonical reduct (O, ϵ) is given by the superclass and eigenclass links between objects. In particular, the structure only allows single inheritance so that except for r, every non-terminal object has exactly one parent, detectable by the superclass method. The order-embedding property of .ec translates to the statement that for every object x, the superclass of the eigenclass of x equals the eigenclass of the superclass of x, whenever the superclass of x is defined.

In addition, Ruby disallows explicit metaclasses other than c. As of Ruby 1.9, there are exactly 4 helix classes:

c = Class < Module < Object < BasicObject = r.

Module inclusion

The "full" membership, ϵ', takes module inclusion into account. Modules are terminal instances of the Module class, i.e. modules are Modules that are not Classes. The additional structure is given by the own-includer-of relation between Modules (classes, eigenclasses, modules) and modules. If Μ denotes the reflexive closure (i.e. Μ is self-or-own-includer-of) then the ϵ' relation is given by

(ϵ') = (ϵ) ○ Μ.

This extended membership corresponds to the is_a? introspection method which is aliased by kind_of?. Similarly, the "superclass" inheritance, ≤, is extended to ≤' by

(≤') = (≤) ○ Μ,

which, in the restriction to Modules, corresponds to the <= introspection method. This extended inheritance is a multiple inheritance. In addition, since Ruby supports dynamic module inclusion, ≤' can have anomalies (as to transitivity and/or antisymmetry), the problem known as the double/dynamic inclusion problem.

In Python

Assuming consistent setting of the __mro__ attribute of classes, the Python eigenclass model conforms to the canonical structure. There are exactly 2 helix classes:

c = type < object = r.

No additional constraints are imposed.

In Scala and Java

In Scala and Java, classes form actually a subset of C. This subset can be expressed as C.c where .c is an explicit closure operator added to the canonical structure, so that the generalized structure is of the form (O, ϵ, .c). This way the set C is split into classes and non-terminal mixins. In Scala, mixins are called traits, in Java they are interfaces. Mixins are not allowed to be metaclasses.

The structure is then subject to additional constraints. There are no explicit metaclasses other than c, and, more importantly, a single inheritance between classes applies (but not between traits / interfaces). The helix contains 3 classes:

c = Class < Object < Any = r.

For Java, the Any class can be thought of as a fictitious root allowing primitive values to be objects – they become objects that are not Objects. Mixins (traits / interfaces) are among descendants of the Object class. Java in addition disallows interleaving interfaces with classes, so that x.c = Object for every interface x.

In Smalltalk-80

To describe the eigenclass model as it applies to Smalltalk, one has to make several assumptions about possible program states. As a consequence, the model does not capture all the anomalies allowed by Pharo or Squeak, the major Smalltalk-80 implementations. These ruled-out anomalies include in particular cycles in the inheritance relation (established via the superclass: method), "dangling metaclasses" (created by Metaclass new), and subclasses of the Class class.

There are two features of the Smalltalk object model that do not conform to the canonical structure (O, ϵ) but can be captured by an appropriate generalization: metaclass redirection and additional twist links. Metaclass redirection is expressed via an imposed metaclass subroot, named Metaclass, which induces the corresponding imposed class map. This map coincides with the standard .class map except for implicit metaclasses, where it "redirects" the value from the Class class to the Metaclass class, introducing monotonicity breaks with respect to inheritance.

Additional twist links are child-parent pairs (x.ec, c) where x is a "subsidiary" inheritance root – a built-in parentless class other than r. Each of Pharo and Squeak contain one such class, named PseudoContext and ObjectTracer, respectively.

The helix chain contains 5 classes:

c = Class < ClassDescription < Behavior < Object < ProtoObject = r.

The Metaclass class is a sibling of the Class class. Finally, the Ruby-like conditions apply: There are no explicit metaclasses other than c, and the inheritance relation is a forest.

Traits

Similarly to Ruby module inclusion, Smalltalk-80 supports extension of inheritance via inclusion of terminal objects, called traits. Traits are Traits – instances of the built-in Trait class. Unlike in Ruby, the semantics of extended object membership, ϵ', is not reflected by the isKindOf: introspection method (as of Pharo 1.3).

In Objective-C

In Objective-C, the eigenclass model has to be generalized to allow multiplicity and degeneracy of inheritance roots. There are several components of object membership, each with its own inheritance root. In each component, the inheritance root r equals the instance root, so that r.class = r. Equivalently, (r.ec, r) is the twist link. As a consequence, metaclasses have to be defined as objects that are either equal to an inheritance root or are descendants of the eigenclass of an inheritance root (this definition also applies to the canonical structure).

As of GNUstep, there are (at least) 3 built-in inheritance roots, named Object, NSObject and NSProxy. Finally, the Ruby/Smalltalk-like conditions apply: There are no explicit metaclasses other than metaclass roots, and the inheritance relation is a forest.

In CLOS

The Common Lisp Object System deviates from the canonical structure in two features. It introduces non-linear inheritance between helix classes as well as an imposed class map with monotonicity breaks w.r.t. inheritance. Unlike in Smalltalk, this imposed class map cannot be expressed via a constant "redirection" target. As of CLISP 2.49, there are 8 helix classes:

c = class < clos::potential-class < … < standard-object < T = r.

The missing 4 classes do not form a chain in inheritance. Like in Python, there are no additional constraints: multiple inheritance is supported as well as creation of explicit metaclasses.

In Perl 5

The Perl object model is distinguished by total circularity of classes: Every class is the class of itself. As a consequence, the instance-of relation, in its restriction to classes, coincides with the inheritance relation (so that there is no disambiguity in the interpretation of is-a). Every class is an instance root – so that there is an instance forest rather than instance tree. Every class is also an explicit metaclass (metaclasses have to be defined via eigenclasses of instance roots similarly to Objective-C).

There is a single built-in inheritance-root, named UNIVERSAL (however, this statement requires the assumption that the @ISA variable of this class is not changed). Multiple inheritance is allowed.

Object actuality

Since eigenclass chains are infinite, any in-memory representation of object membership must involve the notion of "actual" objects – the finitely many objects that are actually represented (allocated). It turns out that for all the above mentioned programming languages, the set of actual objects forms a closure system in inheritance, so that it can be expressed via the corresponding closure operator.

Actual objects comprise all primary objects (terminals and classes) plus some eigenclasses. Except for Ruby, eigenclasses of eigenclasses (elements of O.ec(2)) are never actual. Even in Ruby, manipulating these higher-order eigenclasses did not find any practical use.

Axioms

A canonical structure of object membership with actuality is a structure (O, ϵ, .a) where (O, ϵ) is a canonical structure of object membership and .a is a (total) map between objects. Objects from O.a are actual(s). The structure is subject to the following conditions:

1. (a~1) There are only finitely many actual objects.
2. (a~2) Every primary object is actual.
3. (a~3) For every object x, if x.ec is actual then so is x.
4. (a~4) The .a map is a closure operator w.r.t. inheritance.
5. (a~5) For some (necessarily unique) i ≥ 0, c.ec(i) is actual but has no actual strict descendants.

These axioms apply to all mentioned specializations of the model, provided that (a~5) is appropriately altered in case of multiple instance roots.

Actualclass map

The actualclass map, .aclass, is defined as the composition .ec.a. Equivalently, for an object x, the actualclass of x, x.aclass, is the least container of x that is actual.

The actualclass map goes between the eigenclass map and the class map, i.e. for every object x,

x.ec ≤ x.aclass ≤ x.class.

The .aclass map is identical to the .class map iff no eigenclass is actual. Similarly to the .class map, the actualclass map forms a tree. The root equals c.ec(i) from (a~5).

Specializations

In Python, Java, CLOS, and Perl, eigenclasses are purely fictitious – they are never actual, so that the actualclass map coincides with the class map. Scala allows eigenclasses of terminal objects, e.g. via the object definition. In Smalltalk-80 and Objective-C, the set of actual eigenclasses equals C.ec, i.e. all implicit metaclasses (without higher-order eigenclasses) are actual.

In Ruby

In Ruby, all objects that are not immediate values can have actual eigenclasses. As of MRI 1.9, ancestors of actual objects are actual.

Ruby is the only language (at least of the above mentioned ones) that supports dynamic eigenclass allocation. Typically, for an object x (whether a class or a terminal), the eigenclass x.ec becomes actual by defining "singleton" methods for x. Moreover, Ruby in fact maintains 2 actuality extents, i.e. two different sets of actual objects. The first set is the set of actually referenced objects. The second, larger set is the set of allocated objects. The actualclass map for the larger set corresponds to the klass field in the C source code of MRI.

In Smalltalk-80

In Smalltalk, the imposed class map has the corresponding imposed actualclass map which corresponds to the introspection method named class. Due to the metaclass redirection, the imposed actualclass map does not form a tree but just a (directed) pseudotree with a 2-element cycle containing the Metaclass class and its eigenclass.

Name resolution

Object membership, ϵ, provides fundamental semantics for sharing properties between objects. Similarly to RDF triples, an object property can be considered as a named source-target arrow. There are two basic interpretations of the source: as owner and as receiver. Owner-arrows are explicit data bindings: a target value is bound to an owner object under a name. Receiver-arrows are implicit: an object receives (inherits) a named property from an appropriate owner via ϵ. The process of finding an owner-arrow for a given receiver and name is an essential part of (property) name resolution.

There are two main ways how to interpret ϵ in name resolution of shared properties. In the prototypal way, the owner-arrow is looked up in ancestors of the receiver. For class-based programming languages, this mode is of minor importance and is usually unsupported. In Ruby, it occurs in constant resolution, e.g. resolving expressions like A::B.

In the class-based way, the owner-arrow is looked up in containers of the receiver. This is the primary mode, used in particular for finding arrows that point to methods, (a part of) the process known as method resolution or method lookup. Since containers of an object are just ancestors of the object's eigenclass, method lookup can be thought of as a two-stage process: first step to the eigenclass, then look up in ancestors. In Ruby, this is expressed as a "method call mantra":

one to the right, then up.

Considering object actuality, the actual start-point of the lookup is the actualclass of the receiver. In most cases (and in all cases for languages without actual eigenclasses) it means that the lookup starts in the receiver's class.

Conflict resolution

In the ideal case, objects that are owners of an s-named binding for a given name s form a partial closure system: for every object x, either no ancestor of x owns an s-named binding or there is a (necessarily unique) least such ancestor, y, w.r.t. inheritance. If y exists, then the s-named arrow emanating from y is basically the result of the resolution process.

In the general case, an object can have multiple minimal ancestors that are owners of an s-named binding. There are 3 main ways how to either avoid or resolve such conflicts:

1. Only allow single inheritance between potential owners. This condition guarantees that every set of owner objects is a partial closure system. This solution is applied in Java and Objective-C.
2. Disallow conflicts by enforcing additional arrows. Upon object creation (in particular, class creation), if a conflict is detected for a name s, make sure that the new object itself becomes an owner of an s-named binding. This solution is used in Smalltalk-80 by the traits mechanism.
3. Maintain additional ordering so that a linearization of ancestors can be established. This applies to Ruby, Scala, Python, CLOS and Perl.

Linearization

The linearization of an object x, denoted x.ancs, is a list of ancestors of x that determines the order in which ancestors are looked up for ownership of a property (binding) with a given name. For every x, x.ancs starts with x itself.

The .ancs map can be equivalently expressed as a "quadratic" inheritance – a partial order between pairs (x,y) where x is a descendant of y. This structure can be conveniently termed method resolution order, abbreviated as MRO (using "method" instead of some more general term like "property" can be attributed to the prominent position of methods in object-oriented programming).

As a result of linearization, MRO is a forest: every element (x,y) has at most one parent. Starting at (x,x), the traversal of ancestors in MRO yields x.ancs, the linearization of x.

The domain of MRO is the part of the inheritance relation where multiple parents are allowed. In Ruby, this is exactly the self-or-own-includer-of relation, Μ (as a subset of the extended inheritance, ≤'). In Scala, the MRO domain is a similar relation between Classes (classes, eigenclasses, traits) and traits. In Python, Perl and CLOS, there is no distinction of mixins like in Ruby or Scala, so that the MRO domain equals the inheritance – it contains all pairs (x,y) of objects such that x ≤ y.

Transitions

Standard transitions are those of new "user" object creation. The structure is modified by adding a primary object x, together with its (fictitious) eigenclass chain, such that x is minimal in inheritance. Except for languages with degenerated metaclass roots, new object x creation (whether a terminal x or a class x) can be uniformly expressed as class instantiation:

x := q.new(p1, …, pn)

where q is the requested class of x and p₁, …, p_n are the requested parents of x. In practice, creation of terminal objects x (where q is not a metaclass and necessarily n = 0) is syntactically differentiated from creation of classes x (where q is a metaclass). In Perl, the pattern is not applicable to class creation due to the chicken-egg problem caused by the circularity of classes. In Objective-C, if q is an inheritance root, then one cannot recognize, if x should be terminal or a class. Similarly, the pattern is not applicable to the helix structure, which is built-in and cannot be changed by transitions.

In less dynamic languages like Scala, Java or Objective-C, most or all classes are usually created in an initial loading phase, before terminal objects. Dynamic class creation is provided as a secondary option.

In Ruby, transitions of the extended structure (O, ϵ') are made separately by transitions of the canonical reduct, (O, ϵ), and of the Μ relation, the latter performed via the include method.

Some languages support transitions such that the old structure is not a substructure of the new one. In particular, Python, CLOS and Perl allow to change the class of a terminal object.

Ontological structure of ϵ

A generalization of the canonical structure of ϵ allows for a description of the core structure of ontologies in which classes are (among) individuals. Motivated by the RDF Schema, the generalization can be characterized by the following features:

• Distinction of properties as instances of a special class, p. Properties, like terminal objects, are not descendants of the inheritance root. In contrast to terminals, properties can have (other properties as) ancestors / descendants.
• Inheritance does not have to be antisymmetric – distinct classes or properties can be descendants of each other and thus become equivalent.
• Multiple classification – an object x can have multiple minimum classes of which x is an instance, so that the existence of x.class is not guaranteed.
• Finiteness conditions are less strict in order to allow infinitely many terminals or properties.

In eigenclass completion, the structure can be expressed with the signature (O, ϵ, p). Additional symbols r and c can be used for distinction between the possibly many equivalent inheritance and metaclass roots. The primary ontological structure is then expressed as (Ō, ϵ, ≤, r, c, p).

In RDF Schema

In RDF Schema (RDFS), the (primary) ontological structure of ϵ is the core structure of the RDF graph formed by triples (s,p,o) whose predicate p equals rdf:type, rdfs:subClassOf or rdfs:subPropertyOf. The rdf:type property stands for the instance-of relation, ϵ. Uniformity of inheritance, ≤, is achieved by the assumption of disjointness of classes and properties, which is not guaranteed by RDFS but usually satisfied. The rdfs:subClassOf and rdfs:subPropertyOf properties then correspond to the restriction of inheritance to classes and properties, respectively.

Objects are called resources – every object is an instance of the rdfs:Resource class (r). Classes are instances of rdfs:Class (c), properties are instances of rdf:Property (p). Unlike classes, properties do not have a common built-in ancestor.

Structure constraints are expressed via entailment rules – the presence of some triples entails the presence of other triples. For example, the (ϵ) ○ (≤) = (ϵ) equality is asserted by the rdfs9 entailment rule, which says that triples (x,ϵ,y) and (y,≤,z) entail the triple (x,ϵ,z), i.e. whenever x is an instance of y and y a subclass of z then x is an instance of z (this is also known as the subsumption rule).

There are conditions that can be considered as natural constraints but are not asserted by RDFS entailment. In particular, there is no "type monotonicity" rule which would assert that (≤) ○ (ϵ) = (ϵ). Another example of a possible anomaly is a class that is not a metaclass (a descendant of rdfs:Class) but has classes as instances.

The built-in core structure of RDF Schema

The built-in structure, entailed by the empty set, is shown by the diagram on the right. The structure is fairly regular. Except for inheritance between properties and the infinity of the set {rdf:_1, rdf:_2, …}, even the axioms for the (primary) canonical structure are satisfied. There is single classification (yielding the .class map) and single inheritance. Since the .class map is inherited via type monotonicity, the diagram shows only the reduction (dashed arrows). Similarly to the Python programming language, there is a minimal chain of 2 helix classes:

c = rdfs:Class < rdfs:Resource = r.

The rdfs:Datatype class is the second built-in metaclass.

In OWL 2

In OWL 2 Full, the structure of RDF Schema is extended by additional axiomatic triples. The extension is then subject to the (additional) OWL 2 RL/RDF rules. The built-in structure contains four helix classes, preordered by

{owl:Class, rdfs:Class}   <  {owl:Thing, rdfs:Resource},

which indicates that RDFS helix classes have their OWL equivalents. Similarly, rdf:Property is equivalent to owl:ObjectProperty and the metaclass rdfs:Datatype is equivalent to (the metaclass) owl:DataRange. In total, there are 7 built-in metaclasses, including the bottom class, owl:Nothing, a descendant of all classes which is disallowed to have instances.

See also

• Object (computer science)
• Class (computer programming)
• Metaclass
• Class-based programming
• Top type
• Order theory