Object Membership

The Core Structure of Object Technology

An abstract structure is described that is believed to be central to object-oriented programming and modelling. In its main form, the structure is built from three relations between objects, ϵ, and .ec. The most fundamental relation, ϵ, is called object membership and is a refinement of the instance-of relation. The relation is the inheritance between objects. Finally, .ec is a partial map that forms a distinguished subrelation of ϵ.

The structure arises as a generalization of the innermost core of the object model of the Ruby programming language. In Ruby, the .ec map is total – every object has an eigenclass. The following equalities hold:

The second equality says that object membership is the composition of infinite regress of eigenclasses with inheritance.

As an essential feature, the structure supports circular objects, i.e. objects x such that x ϵ x. This is also the main indicator of applicability. It is shown how the structure applies to class-based programming languages (Ruby, Python, Java, Scala, Smalltalk, Objective-C, CLOS, Perl and Dylan), prototypal languages (JavaScript), and ontology languages (RDF Schema, OWL Full).

A general mathematical structure of object membership is described in an affiliate document []. A gradual set-theoretic representation is provided with the exact correspondence of ϵ, , .ec and derived constituents of the structure to fundamental notions of set theory.

As a result, a uniform and mathematically precise view of an essential part of object technology is provided.

Preface

Author
Ondřej Pavlata
Czech Republic
Document date
Initial releaseAugust 24, 2012
Last major release March 12, 2015
Last updateApril 8, 2015
(see Document history)
PDF Version
A PDF version of this document is available via the following link: However, the HTML version is considered primary and can be more up-to-date.
Warning
This document has been created without any prepublication review except those made by the author himself.
Membership glyphs
This document uses HTML entities to display mathematical symbols. In particular, there are multiple glyphs used for different relation symbols of membership. Best readability is achieved when the sequences of symbols from the following two lines look (almost) identically.
(PNG images)
ϵ ϶ (HTML entities)

Table of contents

Introduction

Object technology (⁎) is based on object models []. The word model indicates that something is abstractly represented in a structured way. The word object indicates uniformity – there is a uniform unit of representation called object.

Note:(⁎) In this document we regard object technology as an umbrella term for object-oriented programming (OOP), object modelling and ontology languages such as RDF Schema.

The approach
We can further combine the terms from the previous paragraph and say that an object model is itself based on an abstract structure between objects. The term structure between objects can be further interpreted as family of relations between objects. The term abstract suggests abstraction. For every non-trivial object model M there is a hierarchy of models that are abstractions of M. Around the top of the hierarchy there are core structures – they are formed by the most fundamental relations between objects.

This document identifies the following three relations as the core relations of object technology:

Since abstraction is one of the most fundamental principles of object technology, we can characterize our approach as
applying object technology to itsef.
Introductory sample
The diagram below shows an example of a core structure of object technology. Objects are displayed as nodes. The inheritance relation, , is shown by green arrows in the reduction to immediate pairs. Object membership, ϵ, is the composition of blue arrows with inheritance. The powerclass map, .ec, is indicated by horizontal blue arrows.
(Ruby 1.9)

r = BasicObject
c = Class
A = c.new(r)
B = c.new(A)
s = A.new
u = B.new
v = B.new

class << s; end
class << v; end
The code on the right shows how the structure can be obtained in the Ruby programming language as a part of data structure of a running program.

Notes: (See Ruby core sample.)

  1. c and r are only immediate in the partial structure, restricted to chosen objects. In the complete Ruby built-in structure, there are 2 objects between c and r.
  2. In order to demonstrate the possible partiality of the .ec map, we deviate from the canonical interpretation supported further in the document. In Ruby, we consider .ec to be a total map.
The objective
The objective of this document is to rigorously describe structures that arise from ϵ, and .ec. That is, using the conventions in the diagram above, the document is preoccupied with the following question:
What can be said about the blue and green arrows?
For instance, it can be said that there cannot be an additional green arrow from r to s in the sample structure. Therefore, what the document essentially contains is an axiomatic description of families of structures that arise from the three core relations. Since the relations are fundamental, their description should contribute to foundations of object technology. Presumably, the above question can be stated as
What is the mathematical structure for the
  • most fundamental part
  • utmost simplification
  • highest abstraction
of object technology?
Naturally, there is no universal description for all specific cases. We have to define idealizations on which the specific cases are based.
The ϵ2 condition and circularity
Structures in which ϵ2 is empty (that is, the composition of ϵ with itself is an empty relation) have a simple description which is provided in a single introductory section. The complementary condition ϵ2 can be expressed as the classes are objects principle. (By convention, the phrase also indicates that the structure is not classless.)

This document is predominantly concerned with structures satisfying ϵ2 . That is, x ϵ y ϵ z for some (not necessarily distinct) objects x, y and z. It turns out that in all the introduced structures, the following stronger condition holds:

There exists an object x such that x ϵ x.
This circularity condition is perhaps the best indicator for the issues handled in this document. Another good indicator, although less perfect, is the presence of the notion of metaclass. Roughly speaking, being a metaclass means being in the image of ϵ2. Therefore, support for metaclasses is roughly equivalent to the ϵ2 condition. However, there are programming languages, most notably Ruby and JavaScript, that support circular objects, but in which the notion of metaclass is not well established.
The non-objective
The focus being on the core structure of the object model, many notions of object-oriented programming occur outside the scope of this document. This should be in particular emphasized for the notion of type. This document provides no explicit explanation as to what a type is. Maybe the document provides an implicit explanation but the author is unaware of it.

The concept of type is regarded as something more complex (an therefore less fundamental) than things described in this document. We use the term type exclusively as a mean of quotation (reference) of particular concepts by other parties (e.g. types as particular objects in Dylan, or abstract power type system for the abstract structure of Cardelli's power types).

As a consequence, this document becomes virtually disjoint with the following two books, both of which claim to provide foundations of object-oriented programing. (The metaclass term can be used as an indicator for the disjointness. There is no occurrence of this word in either of the books. Similarly for meta-class.)

Composition of ϵ and
It will be convenient for further reference to already introduce the following composition rules for ϵ and :
Rule name Short expression Using variables Set-theoretic counterpart RDFS rule(s)
Transitivity of () () () if x y z then x z () () () rdfs11 (and rdfs5)
Subsumption of ϵ (ϵ) () (ϵ) if x ϵ y z then x ϵ z () () () rdfs9
Monotonicity of ϵ () (ϵ) (ϵ) if x y ϵ z then x ϵ z
These rules can be observed to be satisfied by the introductory sample. We even have used the first two conditions to reduce the set of displayed arrows: The set of green arrows is the transitive reduction of and the set R of blue arrows in the diagram is minimum such that R () = (ϵ). We could even have had further reduced the set of displayed blue arrows by applying the mononicity rule. The resulting subrelation of ϵ would be the minimum relation S such that (ϵ) = () S (). (In the case of the sample, S = (.ec) {(u,B)}.)

The table also indicates that (set inclusion) and (set membership) are the respective set-theoretic counterparts in of and ϵ. However, the latter correspondence is indirect – we will further introduce , a restriction of ϵ, to be the direct correspondent of , see Set-theoretic interpretation.

In contrast to subsumption, the monotonicity rule has no set-theoretic counterpart. In set theory, it is not true that for every sets x, y, z,   if x y z then x z. (For example, if x y {y} then x {y}.) Nevertheless, monotonicity of ϵ is satisfied in the major part of object technology. The monotonicity term comes from the following equivalent formulation: for every objects x, y,

where u.ϵ is the set of all containers of u (the image of {u} under ϵ). In particular, in canonical primary structures, the condition can be expressed as monotonicity of the .class map, i.e. for every objects x, y, This is known as the metaclass compatibility condition [].

Main results

This document builds a mathematical model that is presumably relevant to the core part of object technology. The following fundamental notions of computer science can be rigorously described in terms of the model:
class instance-of class-of
metaclass inheritance eigenclass-of
eigenclass isa singleton-of
It is shown how the model applies to class-based programming languages (Ruby, Python, Java, Scala, Smalltalk, Objective-C, CLOS, Perl and Dylan), prototypal languages (JavaScript), and ontology languages (RDF Schema, OWL Full). The following characteristics can be observed: On the other hand, it is shown how the model can be embedded into the universe of sets. This results in a set-theoretical foundation of the core part of object technology.
Basic structure
ϵ¯
ϵ, , r, .ec, .ɛɕ
ϵ-1
ϵ-2
ϵ-3
The general mathematical model of The Core is provided by the family of basic structures. The diagram on the right shows the signature of these structures. In addition to the ϵ, and .ec relations mentioned in the introduction there are additional constituents:
Objects are abstractions of sets in a suitable partial universe of well-founded sets. The universe is limited by a rank – both from above and below. In particular, the empty set is not considered to belong to the universe. The axioms of basic structures are provided in a dedicated section. Moreover, there are two distinguished derived subrelations of ϵ: Finally, the most fundamental three relations ϵ, and .ec have the following semantics:
Distinguished subfamilies
The following distinguished families of basic structures can be singled out: Up to a minor difference, there is a duality between the two families of canonical structures: Canonical primary structures are obtained from canonical eigenclass structures by omitting eigenclasses. Conversely, canonical eigenclass structures are obtained from canonical primary structures by eigenclass completion.
Connection between ϵ and
The powerclass (.ec) and singleton (.ɛϲ) maps provide a connection between membership (ϵ) and inheritance ():
For every objects x, y,    in a monotonic eigenclass structure:   whereas in a metaobject structure:
x ϵ y.ec x y,
x ϵ y x.ec y,
x ϵ y.ec x y,
x ϵ y x.ɛϲ y or x.ec y.
Using the concise notation of relational composition,
(.ec) (϶) = (≥) and (ϵ) = (.ec) ()   in a monotonic eigenclass structure,
(.ec) (϶) = (≥) and (ϵ) = ((.ɛϲ) (.ec)) ()   in a metaobject structure.
In monotonic structures, the singleton map .ɛϲ is a submap of .ec. The singletons are exactly the powerclasses from powerclass chains that start in terminal objects – which are objects that do not have any members or strict inheritance ancestors. (In the sample structure, s, u and v are terminals and s.ec = s.ɛϲ and v.ec = v.ɛϲ are singletons.)
Set-theoretic interpretation
Set-theoretic interpretation of basic structures is summarized by the table below. Any basic structure S can be identified with a set O in the von Neumann universe of well-founded sets. Let denote the standard powerset operator, that is, for a set x, (x) is the set of all subsets of x. Moreover, let (x) be the set of singleton subsets of x. The constituents of S are then obtained as follows:
Terminal objects T   =   O (O O)
Inheritance root r   =   O T
For every x, y from O :
Bounded membership   x y   ↔   x y
Inheritance x y   ↔   x y
Singleton map x.ɛϲ = y   ↔   {x} = y
Powerclass map x.ec = y   ↔   r (x) = y
Power membership x ϵ¯ y   ↔   r (x) y
Object membership x ϵ y   ↔   r (x) y or x y

Simple cases of ϵ

To proceed further with the description of ϵ, and .ec (even before giving an account on history of implementation and documentation of these structures) we first do away with simple cases:
  1. ϵ =   (purely prototypal structures),
  2. ϵ and ϵ2 =   (bipartite structures).
For convenience, we also present the condition for the remaining (i.e. non-simple) cases:
  1. ϵ2   (basic structures of ϵ and their specializations).
Purely prototypal structures
Purely prototypal object models are those which deny to institutionalize any concept of a classification. In accordance, a pp-core structure is a structure (O, ) such that
(pp~1) is a partial order on O.
By not presenting ϵ and .ec in the signature it is implicitly understood that these relations are both empty.

We do not consider all prototype-based programming languages to have a purely prototypal core structure. In particular, in JavaScript [], ϵ . We base this judgement on the following observations:

Bipartite structures
Bipartite structures represent a two-sorted view of ϵ which is characteristic for static class-based languages like C++ or Eiffel.
By a bipartite primary structure we mean a structure (O, ϵ, ) where Let us denote T = O.϶, the pre-image of O under ϵ, and call elements of T instances. Elements of the complementary set C = O T are classes. The structure is subject to the following conditions.
(bp~1) Inheritance, , is a partial order. In particular, its reflexive reduction < is acyclic.
(bp~2) (a) (<) (ϵ) = .   (b) (ϵ) (ϵ) = .
That is, instances have (a) no strict descendants and (b) no instances.
(bp~3) (ϵ) () (ϵ).   (The subsumption rule.)
That is, every class has (inherits) all instances of its ancestors.
(bp~4) Every instance x has a least container, x.class.
As a consequence, there is a unique map .class from T to C such that (ϵ) = (.class) (). (Observe that this equality implies the subsumption rule.)
Similarly to the previous case, it is assumed that .ec is empty. (This is also indicated by the adjective primary since in theory, there can be bipartite structures that support .ec on T. However no such occurrence in object technology is known to the author.) We might consider the additional condition of a single-rooted inheritance (which is not satisfied in C++). On the other hand, (bp~4) is not to be imposed on ontology languages.

Note that we did not mention the word object anywhere in the definition. This is because we have disobeyed the two-sortedness – we unified the sorts T and C into one set O. In the two-sorted view of ϵ the term object is exclusively reserved for elements of T. This is expressed by:

This is in opposition to our approach. We consider the core structure to be single-sorted – there is a uniform domain O of objects on which the relations ϵ, and .ec are defined. In particular, The following table shows a division of significant representants of object technology according to the composability of ϵ. Note that there is a middle group which takes a neutral approach: The point of it is that reification can be overridden by identity. This approach seems to be supported in particular by the Java programming language. In Java, the names of introspection methods like getClass() or getSuperclass() suggest that it is a class what is returned, rather than its reification. In the book Java reflection in action [], both agreement and disagreement to the uniformity principle can be observed. (According to page 23, classes are objects. According to page 268, there is a distinction between class and class object.)
Group Composability of ϵ Programming Languages Ontology Languages
(A) = (ϵ) (ϵ) C++, Eiffel PHP OWL 2 DL
(B) (ϵ) (.reif) (ϵ) Java, Scala, C#
(C) (ϵ) (ϵ) Ruby, Python, Smalltalk, Objective-C, CLOS, JavaScript RDF Schema, OWL 2 Full

Overview of atalon.cz and related documents

There are several documents at atalon.cz that are concerned with the core structure of object technology.
Eigenclass model (Wikipedia article)
The archived Wikipedia article titled Eigenclass model [] provides a synopsis of monotonic object membership. The family of canonical eigenclass structures is introduced in the minimum signature (O, ϵ). The general family of monotonic eigenclass structures is presented under the name essential structure of ϵ.

The Wikipedia page en.wikipedia.org/wiki/Eigenclass_model containing the article has been created in October 2012 by the author of this document. Several major edits followed until January 2013. In October 2013, the page has been deleted (changed to a redirect to Ruby (programming language)#Semantics) by Wikipedia administrators on the following grounds:

For those interested in the article there is a short list of corrections which I would apply if the page was not deleted:
c(i) replace by c.ec(i)
other that other than
(p~4) extend with and instances of each other.

History

The following table outlines the history of object models whose core structures satisfy ϵ2 .
Year Author(s) Introduced (or applied) concept Language(s)
1976 Daniel Ingalls [] Classes are objects (ϵ2 ) Smalltalk-76
1980 James Althoff [] Implicit metaclasses (.ec defined for classes) Smalltalk-80
1983 D. Bobrow, M. Stefik [] Explicit metaclasses LOOPS
1988 D. Bobrow, G. Kiczales [] Explicit metaclasses with a monotonicity check CLOS
1988 Luca Cardelli [] Power types Smalltalk-80
1992 Apple Computers, Inc. Universal singletons Dylan
1994 James Odell [] Power types in metamodelling UML
1995 James Gosling The Class class in mainstream programming Java
1995 Yukihiro Matsumoto Universal eigenclasses, fully monotonic
(.ec defined for all objects, lazily evaluated)
Ruby
1995 Keith Playford [] Combining powerclasses with singletons Dylan
1995 Brendan Eich Prototypes as inverse eigenclasses JavaScript
1998 I. Forman and S. Danforth A book about metaclasses Java, Smalltalk, CLOS, Dylan
2001 Guido van Rossum Fully monotonic explicit metaclasses Python 2.2
2002 World Wide Web Consortium Classes are resources (ϵ2 in semantic web) RDF Schema, OWL 2 Full
2004 Martin Odersky Metalevel-1-only eigenclasses/singletons Scala
2012 Ondřej Pavlata (⁎) Formalization of monotonic ϵ with a total .ec (most of the languages
above and some others)
2015 Formalization of basic structure of ϵ
(⁎) Show me a list of documents (articles, books), possibly hundreds of items long, that are not listed in the previous section. If, in total, these documents say about the abstract structure of ϵ, and .ec more than one tenth of what documents inside of atalon.cz say, then I remove my name from the table.
O.P.

Notes:

  1. Bold font indicates that the introduction of Ruby is regarded in this document to be the most significant contribution to the development of the core structure of object technology. We can guess that the Ruby core structure has been created by rectification of Smalltalk-80 adopting the concept of universality of singletons in Dylan. This is best illustrated by samples from Ruby, Smalltalk-80 and Dylan.
The core structure by Forman & Danforth
In 1998, a book by Ira R. Forman and Scott Danforth has been published, titled Putting Metaclasses to Work []. The book provides an object model of class-based reflective programming languages using the concept of a metaclass. With some effort, a reduction of this model can be made to the core structure, which concerns just the ϵ and relations. In the box below, we provide an axiomatizaton of these structures via the .class map and the relation. The ϵ relation (referred to by isA in []) is obtained as the composition (.class) ().

An fd-core structure (fd stands for Forman & Danforth) is a structure (O, .class, ) where For an object x we say that   Objects that are not classes are called ordinary objects. The structure is subject to the following axioms:
(fd~1) Inheritance, , is a partial order on O.
(fd~2) There is no strict inheritance (<) between ordinary objects.
(fd~3) The .class map is monotone w.r.t. , i.e. for every objects x, y,   if x y then x.class y.class.
(fd~4) There is a unique class, c, such that c.class(i) = c for some i > 0.
(fd~5) There is a unique class, r, that is a top class w.r.t. .
(fd~6) (a) c. is linearly ordered by ,   (b) r.class = c,   (c) r c.
(fd~7) For every ordinary object x,   x.class is not a metaclass.
(fd~8) There are only finitely many objects.

Notes:

  1. Greyed conditions are not imposed in []. They are meant to show the correspondence to canonical primary structures. More specifically, after adding (fd~6)(a) and (fd~7) and replacing objects by classes in (fd~8) we obtain an equivalent to our axiomatization.
  2. In the book, the set C of classes is introduced explicitly. We have used an equivalent implicit definition.
  3. The monotonicity condition (fd~3) is the only axiom that has a direct counterpart as a postulate of [] (Postulate 10, page 42). Other conditions are mentioned as requirements outside the list of postulates or are obtained indirectly.

Preliminaries

Some familiarity with elementary algebra, order theory and set theory is assumed. See [] for details.
Well-foundedness
For a relation ϵ on a set X, an element x X is well-founded in ϵ if x is not a member of an infinite descending chain in ϵ, i.e. if there is no infinite chain of the form A relation ϵ on a set X is well-founded if all elements x X are well-founded in ϵ. Assuming the axiom of choice, this is equivalent to the condition that every non-empty subset Y X contains an element y that is minimal in (Y,ϵ), i.e. there is no u from Y such that u ϵ y.
Rank
For a well-founded relation on a set X, the rank function of (alternatively, the -rank) is a map r() from X to ordinal numbers such that for every x X, By well-founded recursion, there is exactly one such map. Obviously, r(x) = 0x is minimal in . Moreover,

 

The instance-of relation

In class-based programming languages, the instance-of relation is a fundamental mean to express similarity between objects. The relation links objects to classes. Objects that are instances of a given class share behavior (and structure) described by that class.

Let us write x ϵ y for the object x is an instance of the class y. By using the ϵ symbol (lunate epsilon) for the instance-of relation we suggest the correspondence:

ϵ     ,
i.e ϵ has the semantics of set membership, . The class y represents the set of all its instances. Just like sets can share some elements, we allow classes to share instances. That is, we consider ϵ in the weak sense where an object can belong to several classes. We might also speak about has-a-class as a synonym for instance-of.

There is a second point that should be noted in the expression x ϵ y: both the object x and the class y are denoted by a lowercase letter. This suggests that we are focused on programming languages that support the following uniformity principle of ϵ:

Classes are objects.
As a consequence, ϵ is a relation between objects. If x ϵ y then the class y is a meta-object of x in the sense that y is one of objects that provide description for x. If x ϵ y and x is itself a class (and so is every other potential instance of y) then y is a metaclass. In fact, the occurrence of the notion of a metaclass in publications about a particular programming language is a good indicator that the language supports handling of classes as objects.
Sample structure
The following diagram shows a sample structure of the instance-of relation. The structure contains 7 objects: 4 classes and 3 ordinary objects. The instance-of relation is displayed by dark blue arrows: x ϵ y iff there is a blue arrow from x to y.

For an object x we denote x.϶ the set of all instances of x and call it the extension of x. Ordinary objects have empty extension. The sample structure is saturated in the sense that classes are distinguishable by their instances: different classes have different extensions. This allows to derive a partial order, denoted , and called inheritance, between the 7 objects by:

If x y then x is said to be an (inheritance) descendant of y which is in turn an (inheritance) ancestor of x. We also let < denote the reflexive reduction (the strict inheritance) of in the obvious sense. The inheritance relation is shown as a Hasse diagram in the transitive reduction of < by green arrows between classes. Ordinary objects are not involved in <. The sample structure only has single inheritance — every object has at most one inheritance parent.
  • … built-in class
  • … user class
  • ordinary object
  • x y   iff   x y
  • x ϵ y   iff   x y
  • y.϶ = { x | x ϵ y }
  • o.϶ = {s, u, v, A, B, o, c}
  • c.϶ = {A, B, o, c}
  • A.϶ = {s, u, v}
  • B.϶ = {u, v}
Note that every object has a class that is least in inheritance. For an object x let us denote x.class such a class and call it the class of x. If x.class = y then we also say that x is a direct instance of y. Thus, the .class map forms a subset of ϵ, distinguished by thick blue arrows in the diagram. The instance-of relation can be recovered from the .class map and inheritance by their composition, i.e. (ϵ) = (.class) () where the composition symbol is interpreted left-to-right. The equality can be read as: x is an instance of y iff the class of x is an inheritance descendant of y.

Observe that classes o and c are circular – they are instances of itself. Moreover, every object is an instance of o and classes are exactly the instances of c.

Structure creation
In a programming language, o and c are distinguished built-in classes, usually named Object and Class, respectively. The remaining part of the structure is built incrementally, by adding user classes A and B and their instances s, u and v, one by one. Each of the addition of these five user objects x can be formally expressed as class instantiation: where q is the requested class of x and p1, … pn are the requested parents (direct inheritance ancestors) of x. For ordinary objects, the assignment reduces to x = q.new() which we further abbreviate to x = q.new. Since the sample structure only has single inheritance, new class creation can be expressed by x = c.new(p) with the single requested parent p. As a result, the structure is built by the following five assignments: This line of pseudocode (with ; used as a delimiter between the assignments), if preceded by o = Object and c = Class, is a valid line of code in the Ruby programming language for the creation of the sample structure.
Adding inheritance to the signature
Let us denote O0 = {o,c}, O1 = O0 {A}, …, O5 = O4 {v} = Ō so that O0 is the set of built-in objects of the sample structure and for each i = 1, …, 5, the set Oi corresponds to an addition of a single object into the structure. Note that most of the intermediate structures (Oi, ϵ) do not satisfy the extensionality principle that allowed us to distinguish classes as objects with non-empty extension and to derive inheritance via inclusion of class extensions. To capture also the intermediate structures, the inheritance relation has to be prescribed explicitly. Therefore, we extend the signature from (Ō, ϵ) to (Ō, ϵ, ). We call this instance-inheritance structure the primary structure of ϵ.

Note that since (ϵ) = (.class) () we can use the signature (Ō, .class, ) as well.

The sample expressed in relevant languages

This section demonstrates the presence of the instance-of relation in object oriented programming and modelling. It is shown how the sample structure can be created and introspected in various prominent programming languages. An example of an ontological language is provided too.

Where applicable, a diagram is provided showing how the sample structure is obtained as a restriction of a finer structure.

In Ruby
The Ruby programming language allows a uniform expression of the sample structure. Every (user) object can be created via the new method. The instance-of relation between the 7 objects can be detected via the is_a? method (aliased as kind_of?). In the restriction to classes, the <= method corresponds to . The .class map is provided by the class introspection method.
o = Object
c = Class
A = c.new     # class A; end
B = c.new(A)  # class B < A; end
s = A.new
u = B.new; v = B.new
In Python
o = object
c = type
A = c('A', (), dict())    # class A(): pass
B = c('B', (A,), dict())  # class B(A): pass
s = A()
u = B(); v = B()
In Python, new instances are created by calling classes. Also the classes A and B can be created this way, though not so transparently as in Ruby. The instance-of relation between x and y is detected by isinstance(x,y). Inheritance between classes x, y is detected by: x < y iff issubclass(x,y). For every object x, the expression type(x) returns the class of x.
In JavaScript
Traditionally, prototype-based programming languages are regarded to be classless and thus devoid of the instance-of relation. However, as we have already mentioned before, we do not consider this characteristics to be applicable to JavaScript. The diagram below demonstrates that JavaScript allows for the creation of our sample structure. (So that all of o, c, A and B are examples of JavaScript classes.) Every (user) object can be created via the new operator. The instance-of relation between the 7 objects can be detected via the instanceof operator. The .class map is provided by the constructor property. Inheritance between classes can be detected via the isPrototypeOf method as follows: Observe that in contrast to the Ruby sample, the additional objects of the finer structure are drawn on the opposite (i.e. left) side. This is because Ruby supports implicit containers (eigenclasses), whereas JavaScript supports implicit members (prototypes).

Note: To simplify the code, inheritance between B and A is achieved using the non-standard property __proto__.

o = Object; c = Function
A = new c
B = new c; B.prototype.__proto__ = A.prototype
s = new A
u = new B; v = new B
In Smalltalk
Smalltalk-80 (as of Pharo or Squeak) only allows creation of classes via the subclass: method. The instance-of relation between the 7 objects corresponds to the isKindOf: introspection method. The introspection method named class only partially corresponds to the .class map: while it agrees on ordinary objects, it disagrees on classes.
o := Object. c := Class.
o subclass: #A.
A subclass: #B.
s := A new.
u := B new. v := B new.
In Java
class A {}
class B extends A {}

class Xx {
  public static void main (String[] xx) {
    Object
    o = Object.class,
    c = Class.class,
    A = A.class,
    B = B.class,
    s = new A(),
    u = new B(), v = new B();
  }
}
In the Java programming language, classes can be regarded as objects due to the reification facility. For a class named A, the class object of A is referred to by A.class. Note that in contrast to Ruby, A.class does not refer to the class of the class named A. As a consequence, there is a notational duality between (non-reified) classes and their object counterparts. The instance-of relation between objects x and y where y is known to be a reified class named Y can be detected either via The (reified) class of an object x equals x.getClass(). If x is a (reified) class other than o, then x.getSuperclass() is the (reified) inheritance parent of x. Note that the method names suggest that it is a class what is returned, rather than a class object.
In Scala
var o = classOf[Object]
var c = classOf[Class[_]]
class A
class B extends A
var s = new A
var u = new B; var v = new B
Scala adopts the Java's concept of reification of classes. For a class named A, the expression classOf[A] refers to the class object. Note again that classOf[A] is not the class of A. Introspection facilities for the instance-of relation and inheritance between classes are similar to those of Java.
In Dylan
let o = <object>;
let c = <class>;
let A = make(c);
let B = make(c, superclasses: list(A));
let s = make(A);
let u = make(B); let v = make(B);
The Dylan programming language fully supports the classes are objects principle []. Every user object can be created via the make method. Inheritance between classes is detected via subtype?, the instance-of relation between objects and classes is detected via instance?. Finally, the object-class method is the exact correspondent to the .class map.
In CLOS
According to authoritative publications [] [], the Common Lisp Object System (CLOS) fully conforms to the classes are objects principle. (However, there is still some sort of notational distinction for classes.) The instance-of and inheritance relations between objects can be detected via the built-in typep and subtypep methods, respectively.
(defvar o (find-class 'standard-object))
(defvar c (find-class 'standard-class))
(defvar A (make-instance c :name 'A))
(defvar B (make-instance c :name 'B :direct-superclasses (list A)))
(defvar s (make-instance A))
(defvar u (make-instance B)) (defvar v (make-instance B))
Gray color in the code indicates that we consider two possible interpretations of c, shown in the diagrams below. In the (a) case, the class map between the 7 objects is provided by the class-of method.
(a)
c corresponds to standard-class
(b)
c corresponds to class
In RDFS
In RDF Schema,[] [] objects are called resources. Our sample structure is obtained from the RDF graph entailed by the following set of RDF triples expressed in Turtle syntax []. The example prefix ex: is used for the user-created objects.
ex:B rdfs:subClassOf ex:A .
ex:s rdf:type ex:A .
ex:u rdf:type ex:B .
ex:v rdf:type ex:B .
The sample built-in classes o and c are those named rdfs:Resource and rdfs:Class, respectively. The rdf:type property stands for the instance-of relation, ϵ. Inheritance between classes is expressed via the rdfs:subClassOf property.
In Objective-C
The diagram below shows how the sample structure can be interpreted in Objective-C. The o and c classes are coincident, so that the sample structure contains one object less. The diagram also indicates that there is a non-degenerate interpretation, with c set to the gray object labelled by c. In this document, we prefer the first interpretation, since we do not consider the gray object to be a class.
@interface A: NSObject; @end
@interface B: A;        @end
@implementation A; @end
@implementation B; @end
int
main(int argc, const char *argv[]) {
  id
  o = [NSObject class],
  s = [A new],
  u = [B new], v = [B new];
  return 0;
}
The instance-of relation can be detected via the isKindOfClass: method. The class_getSuperclass method can be used for the introspection of inheritance between classes. Similarly to Smalltalk-80, the class introspection method only agrees with the .class map on ordinary objects. For a class x, the expression [x class] evaluates to x. (This is in contrast to Smalltalk-80, where x class is always different from x.)
In Perl
In Perl 5, the instance-of relation, ϵ, deviates from the standard (represented by the sample structure) in a substantial way. In the restriction to classes, ϵ coincides with inheritance, . As a consequence, there is a total circularity between classes: The instance-of relation can be detected by the isa introspection method. The semantics of ϵ is then adhered to by method lookup. []

The diagram below shows the sample structure in the correspondent modification.

package UNIVERSAL { sub new { bless {}, $_[0] } }
package A         { }
package B         { our @ISA = A }
my
$o = UNIVERSAL,
$s = A->new,
$u = B->new, $v = B->new;

Refinement by implicit containers

In the primary structure (Ō, ϵ, ) introduced above, every non-built-in object is explicitly created by class instantiation. (As shown by the Ruby or Python code, classes themselves are created by instantiation of c.) As a consequence, every class is the most specific descriptor for its direct instances. Equivalently, objects instantiated by the same class have the same description. In particular, every class has the same set {c, o} of describing classes in (Ō, ϵ, ).
Eigenclasses
The instance-of relation can be refined by adding implicit containers. In the following diagram, the sample structure (Ō, ϵ, ) is extended to (Ō', ϵ, ) in such a way such that every object x from Ō has its own implicit meta-object, the eigenclass of x, denoted x.ec. Therefore, where Ō are the primary objects, and Ō.ec are eigenclasses. The x x.ec assignment is displayed by gray left-to-right arrows.
x ϵ y   iff   x y
The inheritance relation is extended to Ō' as follows. For every x, y from Ō,
Object membership
The ϵ relation, extended to Ō', equals () (.ec) (). In contrast to inheritance, we do not preserve the instance-of term for ϵ. Instead, we call the ϵ relation object membership. If x ϵ y then x is said to be a member of y. We can also say that y is a container of x.

Proposition: For every x, y from Ō,

That is, x.ec is the least container of x. In particular, x ϵ x.ec and x.ec < x.class.
The refined class map
Just like every object x in the primary structure has x.class as the unique least class that has x as its instance, in the refined structure (Ō', ϵ, ), every object has a unique least container. For an object x we denote x.aclass such a container, and call it the actualclass of x. In the diagram below, the .aclass map is shown by blue links.
x ϵ y   iff   x y

Observations:

  1. The .aclass map coincides with .ec on primary objects and equals the the composition .ec−1.class.ec on eigenclasses.
  2. (ϵ) = (.aclass) ().
Support in programming languages
Of the languages mentioned above, only Ruby supports refinement presented in the previous subsection. There are some languages that provide partial support.
In Objective-C
The refinement of the sample primary structure for Objective-C is shown on the following diagram. Blue links correspond to isa pointers, green links to super_class pointers. []
id
e = object_getClass(o),
f = object_getClass(A),
g = object_getClass(B);
The implicit metaclasses e, f and g are created together with classes o (the built-in NSObject class), A and B, respectively.
In Scala
The structure on the following diagram can be created using the object construct for s and v instead of the new operator used in the primary sample.
object s with A
val    u = new B
object v with B
val    e = s.getClass
val    g = v.getClass
Eigenclass completion
The structure (Ō', ϵ, ) still provides only partial refinement since the pattern has only been applied to primary objects. A complete refinement arises when eigenclasses themselves have eigenclasses. We can extend Ō' to Ō'' by eigenclasses of Ō', then extend and ϵ accordingly, then extend Ō'' to Ō''' by eigenclasses of Ō'', and so on. This leads to infinite eigenclass chains. The resulting structure (O, ϵ, ) has infinitely many objects and can be characterized as an embedding of inifinite regress into inheritance.

Full uniformity of the structure provides the following simplifications:

The core structure of Ruby

In this section we describe the completely refined structure (O, ϵ, ) anew, using Ruby as the definitive sample language. The recapitulation allows us to establish consistent notation and terminology.
Sample structure
The following diagram shows a sample for the description of the core structure of Ruby. Note that the structure is just the eigenclass completion of the sample primary structure except that
(Ruby 1.9)

r = BasicObject
c = Class
class A; end
class B < A; end
u = B.new
v = B.new
There are infinitely many metalevels, indexed 0, 1, 2, . The structure is built using two sorts of links. Green links correspond to the superclass introspection method. A green line going from an object x upwards to an object y indicates that y is an (the) inheritance parent of x. For curved lines (those starting at the top of metalevel 2 and higher) the upward direction is expressed explicitly by an arrow. All the other superclass links are drawn as a Hasse diagram. Gray arrows (directed left-to-right) show the infinite regress of meta-objects. Each object x has its own meta-object, called the eigenclass of x, which is one metalevel higher than x.

The prefix eigen stands for own – different objects have different eigenclass. In the Ruby comunity, the term eigenclass appeared around the year 2005. Previously, the term singleton class has been used. As a (historical) consequence, the corresponding introspection method is named singleton_class.

We use the notation x.ec for the eigenclass of x, so that x.ec corresponds to x.singleton_class. The .ec map is then the eigenclass map shown by gray arrows. Furthermore, let x.ec(i) be the i-th application of .ec to x. Components of the .ec map are eigenclass chains of the form x, x.ec, x.ec(2), x.ec(3), …. The inverse of .ec is denoted .ce. For x from O.ec, x.ce is the eigenclass predecessor of x. Let .ec be the reflexive transitive closure of .ec. For an object y, let y.pr be the primary object of y, that is, the first object of the eigenclass chain y.pr.ec to which y belongs.

Inheritance and membership
The reflexive transitive closure of green links is the inheritance relation between objects, denoted . Since the superclass links are acyclic, is a partial order. We also let < denote the strict inheritance with the obvious meaning. It can be observed that the eigenclass map is an order-embedding with respect to inheritance. For every objects x, y, Object membership, ϵ, equals the composition (.ec) (), i.e. an object x is a member of an object y iff x.ec is an inheritance descendant of y. For a positive natural n, let ϵn denote the n-th composition of ϵ with itself, that is, ϵ1 equals ϵ and for objects x, y For now, we consider ϵ0 to be equal to the identity relation between objects. Later in this document, we redefine ϵ0 to according to the definitions for basic structures. The reflexive transitive closure of ϵ is denoted ϵ. We also introduce a notation for images and preimages under and ϵ. Observe that for every objects x, y, Conditions (1) and (2) are the (≥) = (.ec) (϶) and (ϵ) = (.ec) () equalities, respectively. As a consequence of (3) and (4), the whole structure (O, .ec, ) is given just by object membership, (O, ϵ). Note that the first equivalence implies that ϵ is co-extensional – objects are distinguished by their containers. In contrast, ϵ is typically not extensional.
Direct inheritance
Green links in the diagram correspond to direct (strict) inheritance – the reflexive transitive reduction of . We might sometimes use the symbol for this relation. If x y then x is an (inheritance) child of y and y is an (inheritance) parent of x. We will mostly refer to direct inheritance through its image map, .parents. For an object x, x.parents (as an abbreviation of {x}.parents) denotes the set of inheritance parents of x.

The notation is adapted to multiple inheritance. If single inheritance is asserted, we can use the .sc notation for so that x.sc = y iff x y. For an object x, the object x.sc, if defined, is the superclass of x. The core structure of Ruby can be then expressed as (O, .ec, .sc). []

Membership as is-a
The object membership relation, ϵ, between the objects of the sample structure can be detected in Ruby by the is_a? introspection method. The method is aliased as kind_of?. (There is also the Class#=== introspection method, which detects the inverse relation, ϶.)

If x is a member of an object named B then one can say that x is-a B. The set B.϶ of all members of B can be referred to as Bs. This convention can be used for nomenclature of objects. Moreover, there can be a distinction between the names that are built using this convention (these names are capitalized and styled) and those names that are not. In Ruby, the built-in classes Object, Module and Class provide such a distinction.

Note in particular that we regard is-a as another name for object membership, ϵ, not for inheritance, . Unfortunately, in object modeling, and in most publications about object oriented programming, is-a corresponds to inheritance. The reasoning goes as follows. If A and B are classes such that A B (A is a subclass of B) then one can say that meaning that an instance of A is also an instance of B. The sentence structure can be expressed as an-A is a-B (two pairs of article-noun and a verb between). However, the longest characteristic subsequence is is a which leads to another hyphenation and to saying that This is in turn abbreviated to A is-a B (so that the A's article is dropped and the B's article is secluded from B), meaning that the (A,B) pair belongs to the is-a relation. This abbreviated statement then becomes ambiguous since one way to interpret it is which is fundamentally different from the original statement.

Note: The two different meanings of is-a have been analyzed by R. Brachman [] [].

The ambiguity of is-a can be resolved according to the adherence to the uniformity principle stated in the introduction. If classes are not considered to be objects (individuals) then is-a is resolved in favor of . Otherwise, if classes are among objects (as is our assumption) it is reasonable to interpret is-a as ϵ. At present, this second interpretation is supported only rarely. The Ruby introspection method is_a? and the Objective-C isa pointers are two notable examples. Others can be found in publications about Smalltalk [] or Self []. As mentioned before, another example is the book by Forman and Danforth [] which uses isA for ϵ.
Basic nomenclature of objects
We introduce the basic nomenclature of objects according to the following diagram.
O objects   = T C O.ec
O.ec eigenclasses
O.pr primary objects   = O.c = T C
T terminals   = O r.
C classes   = O.pr T
H helix objects   = r.ϵ = r..he = R.
R reduced helix   = r.ec = r..re
r inheritance root
c metaclass root / instance root
r. Classes   = c.϶ = O.ϵ.
c. metaclasses   = C.class.
r.ec(i).϶ r.ec(i). i-th metalevel
We denote O the (infinite) set of all objects. Previously, we used the term ordinary objects for elements of T. The new terminology is similar to that introduced in the ObjVlisp model [] [] [] where the term terminal instances is used. Note that for an object x the following are equivalent: In particular, non-terminal objects can be referred to as Classes.

The terminology for the set H = r.ϵ is based on the similarity of the diagrammatization of (H, ) with a right-infinite helical curve.

Classification systems
By a classification system we mean a closure system Y on Classes. I.e. it is a set of distinguished non-terminal objects such that every non-terminal x has a least ancestor from Y. Equivalently, Y is such that every object x has a least container from Y. If .y is the corresponding closure operator (that maps a non-terminal object to its least ancestor from Y), then the corresponding classification map (that maps any object to its least container from Y), equals .ec.y. Observe that since both .ec and .y are monotone, any classification map is monotone, i.e. for every objects a, b,

Note that the sets C, R and H are all classification systems. (In fact, since in Ruby the inheritance on Classes forms a tree, any subset of O T containing r is a classification system.) We denote the corresponding closure operators by .c, .re and .he, respectively.

In the case of .c, we extend the definition to all objects: we let .c to be the closure operator corresponding to the closure system C T in (O, ). This allows us to conveniently express the set of all primary objects as O.c.

Metalevels
The set R is the classification system for metalevels. An object x belongs to the i-th metalevel (and therefore has the metalevel index x.mli equal to i) iff x.ec.re = r.ec(i).

Further observations:

Classes and the .class map
The set of all Classes forms a trivial classification system, with .ec the corresponding classification map. However, the eigenclass map is not useful for classifying objects since different objects have different eigenclass, so that each object is classified as different from every other object.

The most important classification system is the set C of primary non-terminal objects. Objects from C are called classes. The corresponding classification map is denoted .class. (So that .class = .ec.c.) For an object x, the object x.class is said to be the class of x. Note that the just introduced meaning of class and class-of possesses the following fundamental consistency:

The class of x is the least container of x that is a class.
Further observations: The diagram on the right shows the class map for the sample structure, in the restriction to primary objects. To illustrate the .ec.c composition, the arrows are drawn along eigenclass paths.

In Ruby, all classes reside in the metalevel 1. As a consequence, .class.class maps constantly to c. The Ruby introspection method named class is in 100% correspondence with the .class map.

The instance-of relation
Just like the .class map is a coarsement of the eigenclass map, the composition (ϵ) (.c) is a coarsement of object membership. This relation is called instance-of and can be equivalently defined as the range-restriction of ϵ to classes, i.e. for objects x, y, The .class map, taken as a relation, is called direct-instance-of. Note that the term instance as such does not distinguish any objects. Every object is an instance of some class. In particular, every object is an instance of the inheritance root r and every object is a direct instance of its class.

By allowing indirect instances our terminology follows the semantics of the isinstance() method of Python or the instanceof operator from Java. In Ruby, the introspection method instance_of? corresponds to direct-instance-of. (However, the Ruby Specification [] allows indirect instances.) Note that

An object is never an instance of its eigenclass.
Metaclasses
In order to establish a correspondence with other programming languages, we introduce the term metaclass: This in particular ensures that classes of classes (C.class) are metaclasses, as well as the classes of eigenclasses (O.ec.class).

Observations:

Metaclasses are said to be explicit or implicit according to whether they are classes or eigenclasses, respectively. Note that by naming the eigenclass c.ec by Metaclass we could express the set c. (= c.ec.϶) as Metaclasses. This suggests to define metaclasses as the primary Metaclasses just like classes are primary Classes. However, this would require an additional term for non-primary Metaclasses. Moreover, the explicit / implicit adjectives seem to be an established convention. [] [] []
Eigenclass actuality
Since eigenclass chains are infinite they must be lazily evaluated. There can be only finitely many objects that are actually represented (allocated). We call such objects actual. A natural direction for evaluation of eigenclass chains is that of the eigenclass map: if x.ec is actual then x must be actual. Let all primary objects be actual, so that the set of actual objects forms a closure system in (O, ).

We denote .a the corresponding closure operator and let .aclass = .ec.a be the classification map. For an object x, x.aclass is the actualclass of x – the least ancestor of x.ec that is actual. The set O.a of all actual objects is the actuality extent. We can view the (O, ϵ, .a) structure as an implementation-oriented refinement of (O, ϵ). In particular, x.aclass can be regarded as the actual startpoint of method lookup for x – non-actual eigenclasses between x.ec and x.aclass are skipped.

The diagram below shows the actuality extent of allocated objects for the sample structure. The extent arises after opening the eigenclasses of A and v. The actualclass map (in the restriction to actual objects) is shown by blue arrows. Note that the map forms a tree rooted at c.ec(2).

(Ruby 1.9)

r = BasicObject
c = Class
class A; end
class B < A; end
u = B.new
v = B.new

class << A; end
class << v; end
Note that the eigenclasses A.ec(2) and B.ec have been allocated but not opened. This is an implementation feature of Ruby. Every newly created class x has its eigenclass allocated. When the eigenclass x.ec(i) is evaluated (e.g. by class << x; end for i = 1) then MRI/YARV makes sure that x.ec(i+1) is allocated. As a consequence, we can distinguish 2 actuality extents: one for actually referenced (evaluated) objects and a larger one for allocated objects.

As already mentioned, the diagram shows the structure for the larger extent. Objects that have been allocated but not referenced are shown in light blue. The actualclass map shown by blue links could be denoted .klass, since it is maintained by the implementation via the klass field in the C source. Note that there cannot be an introspection method for .klass due to the probe effect. There could only be an introspection method for the actualclass map for the smaller extent, but even this is not supported since it is considered to be an implementation property.

The reason for having an extra object allocated in each eigenclass chain of classes is an efficient update of the actualclass map for inheritance descendants. This does not affect terminal objects (or their eigenclasses). Since they cannot have descendants, they do not need to have their eigenclass allocated.

The core structure of Smalltalk-80

The Smalltalk-80 programming language is the first language which introduced the refinement of the instance-of relation by implicit objects. Simultaneously, Smalltalk is one of the first proponents of the classes are objects pattern.

Unfortunately, the Smalltalk-80 core structure possesses uniformity deficiencies which were compensated by equivocal terminology in the Smalltalk's literature. []

To describe the Smalltalk-80 counterpart of the Ruby core structure we use a specially restrained terminology in which the following terms are (at first) avoided:

Sample structure
The following diagram shows a sample core structure of Smalltalk-80. The structure consists of 18 objects with oriented links between them. There are two sorts of links. The green links correspond to the superclass introspection method. There is a single line for which the upward direction is expressed explicitly by an arrow. All the other superclass links are drawn as a Hasse diagram.

The blue links correspond to the class introspection method. A blue line starting at x and ending in y (with an arrow head pointing to y) indicates that the expression x class evaluates to y.

(Pharo 1.3 / Squeak 4.2)

 r := ProtoObject.
 c := Class.
mc := Metaclass.
Object subclass: #A.
A      subclass: #B.
u := B new.
v := B new.

The horizontal dashed line indicates the division of the structure into the built-in part (above the line) and the user-created part. In the code right to the diagram, first distinguished built-in objects are denoted (by r, c and mc) and subsequently the user-part of the structure is created.

The built-in part forms a substructure — it contains exactly the objects reachable from the mc object via a combination of blue and green links. (Note that the substructure is generated by any single object it contains, not just mc.) Moreover, it is a minimum (nonempty) substructure, since the mc object is reachable from any object (via at most 3 blue links).

Metalevels
The sample diagram shows 3 types of blue links. The curved blue links point to the mc object. The straight left-to-right links precede the curved links. Each curved link is preceded by exactly one straight link. The remaining, broken-line links precede the straight links, but without a one-to-one correspondence.

The division of blue links induces a division of objects into 3 metalevels.

The sample structure contains 8 objects from metalevel 2 (shown in gray), 8 objects from metalevel 1, and 2 objects from metalevel 0 (denoted u and v).
Uniformity deficiency No. 1
Observe that the blue links provide the following mappings between metalevels: This reveals a defect of uniformity of the Smalltalk-80 object model:
Inheritance
We denote the reflexive transitive closure of green links, i.e. for objects x, y This relation forms a partial order, called inheritance.

Further observations:

  1. Objects from metalevel 0 are exactly the singletons in inheritance: they have no (strict) descendants or ancestors.
  2. The object r is the top of the metalevel 1 as well as of the union of metalevels 1 and 2, w.r.t. inheritance.
  3. The object r class is the top of the metalevel 2, w.r.t. inheritance.
  4. The parent of r class is the object c from metalevel 1.
  5. In the restriction to a metalevel, the blue links constitute a map that is monotone w.r.t. inheritance, i.e. if x and y are from the same metalevel, then
  6. Since blue links constitute bijection between metalevels 1 and 2, they constitute an order isomorphism between these metalevels, w.r.t. inheritance. If x is an object from metalevel 1 different from r, then
Uniformity deficiency No. 2
The following observation reveals another defect of uniformity of Smalltalk-80: For example, if x := r class and y := c, then x y (we even have x superclass == y) but x class equals mc which is not an inheritance descendant of y class.
The Ruby-Smalltalk core correspondence
The correspondence between the core structures of Smalltalk-80 and Ruby can be observed on the following pair of diagrams. The Ruby structure has the actuality extent O.a = T C C.ec, so that and there are no more metalevels with actual objects.
Smalltalk-80 Ruby
We now resolve the terms class, class-of, metaclass and instance-of by applying Ruby-based terminology and notation to Smalltalk. Let In particular, the metalevel 1–2 correspondence is a correspondence between classes and implicit metaclasses.

The differences between the core samples can be listed as follows:

  1. The Smalltalk-80 core contains two more built-in classes, of which only the mc class (named Metaclass) constitutes a structural change as a receiver of blue arrows.
  2. The blue arrows starting at metalevel 2 are redirected to mc.
Since blue arrows in the Ruby sample display the actualclass map, .aclass, the blue arrows in the Smalltalk sample indicate the imposed actualclass map, which we denote .aȼlass. Therefore, The imposed class map, .ȼlass, equals the composition .aȼlass.c, i.e. x.ȼlass is the least ancestor of x.aȼlass that is a class. The imposed (object) membership equals the composition (.aȼlass) (). This relation can be detected via the isKindOf: introspection method. The imposed instance-of relation is the range restriction of imposed membership to classes, so that it equals the composition (.ȼlass) (). By using imposed membership for the is-a naming convention, classes can be expressed as Classes and implicit metaclasses as Metaclasses. Moreover, C.ȼlass. can be considered to be the set of all metaclasses. The classes Class and Metaclass are then the only explicit metaclasses.

Notes:

  1. Note in particular, that the class introspection method in Smalltalk-80 does not correspond to the synonymous method of Ruby. The following table describes the differences:
    For x from Smalltalk-80 x class evaluates to Ruby x.class evaluates to
    T (terminals) the class of x
    C (classes) the eigenclass of x the class of x which is constantly Class
    C.ec (implicit metaclasses) the imposed class of x which is constantly Metaclass
  2. There is no support for the above or similar definitions in the Smalltalk literature. Instead, publications about Smalltalk-80 use equivocal terminology which suggests two different delimitations of classes and metaclasses: []
    (A) Classes are the objects from metalevels 1 and 2.
    Metaclasses are the objects from metalevel 2 plus the class named Metaclass.
    (B) Classes are the objects from metalevel 1.
    Metaclasses are the objects from metalevel 2.

The primary structure of ϵ according to Python

We now set out for a formal description of object membership. This section provides axiomatizations of the canonical primary structure. The axioms are general enough to allow two features that have not yet been captured by the provided samples: It turns out that under some minor assumptions the canonical primary structures of ϵ are exactly the structures that are allowed in the Python programming language [] (of course, up to the number of helix classes). The correspondence can be expressed as where __class__ and __mro__ are (built-in) attributes of Python objects. The __mro__ attribute is only applicable to classes. It stands for method resolution order and stores the list of inheritance ancestors in the order in which they are looked up during method resolution. The inheritance relation, , between classes is obtained by so that the order of classes in the __mro__ list is disregarded. We assume that a potential explicit manipulation of the attribute is a permutation (changing just the order of classes in the list).

Note: In addition to the __mro__ attribute, Python classes also contain another inheritance related attribute: the __bases__ list. Apart from the order within the list, the intended semantics of .__bases__ is that of the .parents map. However, the correspondence is not asserted. In particular, the __mro__ and __bases__ attributes are not kept in sync if they are explicitly manipulated. We therefore think of .parents to be derived from .__mro__ (satisfying the assumption above) rather than from .__bases__.

Recursive definition
We first provide a recursive definition which shows how the structure can be incrementally constructed. A canonical primary structure (of ϵ) is a structure S = (Ō, .class, .parents, r) where We denote the relation on Ō defined by x y iff y x.parents. For a set X of objects, we write X.parents for the image of X under . Therefore, for an object x,   x.parents is just an abbreviation for {x}.parents. We can also write .parents(i) for the i-th application of .parents. Furthermore, let be the reflective transitive closure of . The usual terminology and notation is used for . Descendants of r form the set C of classes, the remaining objects are terminal(s). Let c = r.class be the metaclass root. Descendants of c are metaclasses.

The structure is then subject to the following conditions:

(py~1) is irreflexive and transitively reduced.
(py~2) All objects from Ō.parents Ō.class are classes.
(py~3) The .class map is monotone w.r.t. , i.e. x y implies x.class y.class   for every objects x, y.
(py~4) If Ō = Ō.parents Ō.class   then (a) is a linear order, (b) .class is constant, and (c) r c.
(py~5) Classes of terminal objects are not metaclasses.
(py~6) The restriction of S to Ō {x} is a canonical primary structure for every x Ō (Ō.parents Ō.class).
(py~7) The set C of classes is finite.

Observations:

New object attachment
The recursive definition says that any finite canonical primary structure can be incrementally built from its restriction to c. by attaching new objects, one by one. Let an attachment request be a pair (P,q) such that so that P = x.parents and q = x.class for the new object x. An attachment request (P,q) is acceptable iff the following are satisfied:
(1) P is an antichain in ,   i.e. if x and y are different objects from P, then x y.
(2) Assert (py~2): Every object from P {q} is a class.
(3) Assert (py~3): For every x from P,   q x.class.
(4) Assert (py~5): If P is empty then q is not a metaclass.
Conditions (py~1)(py~7) are preserved after the attachment of x if and only if (1)–(4) are asserted. Condition (1) can be left out if x.parents is set to mins(P) instead of to P. The following diagrams shows assertions of (2)–(4) in Python.
(a)
¬(py~2): s is not a class
(b)
¬(py~3): B.class A.class
(c)
¬(py~5): M is a metaclass
class A():
  def __new__(a): pass
s = A()

# TypeError:
class B(s): pass
class M(type): pass
class N(type): pass
class A(metaclass=M): pass

#  metaclass conflict
class B(A,metaclass=N): pass
class M(type): pass
class X: pass
s = X()

# TypeError:
s.__class__ = M
Canonical primary structure
We now provide a default axiomatization of canonical primary structures. In the description, a preparation is already made for the extension by implicit objects. The set of objects in a primary structure is denoted O.pr. This expression can be later resolved to an application of .pr to the extended set O of objects. Similarly, some sentences contain the adjective primary to be also applicable in the context of the extended structure.

By a canonical primary structure of ϵ we mean a structure (O.pr, ϵ, , r) where

The usual terminology and notation is used for and ϵ. Objects that are not descendants of r form the set T of terminal(s), the remaining primary objects form the set C of classes. Helix objects x are such that r ϵi x for some i ≥ 0. Metaclasses are the lower bounds of helix classes, i.e. they are objects x such that all helix classes are among ancestors of x. An object x is well-founded w.r.t. ϵ if there is no infinite sequence of objects x1, x2, of objects such that x ϶ x1 ϶ x2 ϶. The structure is then subject to the following axioms:
(p~1) Inheritance, , is a partial order.
(p~2) (ϵ) () = (ϵ) = () (ϵ).   (That is, (a) (ϵ) () (ϵ) and (b) () (ϵ) (ϵ).)
(p~3) Terminals have no instances and no strict descendants.
(p~4) Helix classes are (a) totally ordered by , (b) instances of each other, and (c) at least two in number.
(p~5) Metaclasses can only have classes as instances.
(p~6) Every non-helix object is well-founded w.r.t. ϵ.
(p~7) Every object x has a least primary container, x.class.
(p~8) The set C of classes is finite.

Notes and observations:

  1. In RDF Schema, condition (p~2)(a) is asserted by the rdfs9 entailment rule. Using type theoretic terminology, this can be called the subsumption rule. []
  2. Conditions (p~2)(b) and (p~6) can be conveniently expressed using the .class map.
  3. Condition (p~2) can be equivalently written as a single equality: () (ϵ) () = (ϵ).
  4. Condition (p~3) means that terminals are minimal both in ϵ and .

Proposition: Axiomatizations (py~1)(py~7) and (p~1)(p~8) are equivalent.

The canonical eigenclass structure of ϵ

Roughly speaking, the canonical refinement of the instance-of relation is established by combining Ruby with Python. This can be viewed in two ways: We provide precise interpretation of (A) and (B). The interpretation of (A) will be tight in the sense that every class has at most one eigenclass ancestor (necessarily r.ec). This seems to be the simplest way of eigenclass completion. However, since it also disallows classes on metalevels higher than 2, the interpretation of (B) defines a slightly larger family than that of (A). Moreover, some axioms for (B) are singled out for further generalization of object membership.
Eigenclass regress alone
The structure of infinite regress of eigenclasses can be simply characterized as a monounary algebra (O, .ec) such that Elements of O are objects, .ec is the eigenclass map between objects. For an object x,   x.ec is the eigenclass of x. We denote x.ec(i) the i-th application of .ec to x. (Let x.ec(0) = x.) Since the .ec map is injective, it has a partial inverse which we denote .ce. For an eigenclass x,   x.ce is the (direct) eigenclass predecessor of x. Objects from O.ec are eigenclasses, the remaining (i.e. those without an eigenclass predecessor) are primary. Components of (O, .ec) are eigenclass chains.
Since .ec is well-founded, every eigenclass chain starts in a primary object. For an object x, let x.pr denote the primary object of x, (i.e. the primary object of the eigenclass chain to which x belongs). The unique natural i such that x.pr.ec(i) = x is denoted x.eci and called the eigenclass index of i.

Observations:

  1. For each eigenclass chain X,   (X, .ec) is isomorphic (via .eci) to the structure (, succ) of natural numbers where succ is the successor operator.
  2. O = O.pr O.ec.

Notes:

Tight canonical structure by eigenclass completion
By a tight canonical eigenclass structure of ϵ we mean a structure (O, .ec, , r) where O is a set of objects, .ec is the eigenclass map O O, is the inheritance relation between objects, and r is a distinguished object. The structure is subject to conditions (ec~1)(ec~3) below. Let the object membership relation, ϵ, be the composition (.ec) (). Additional terminology and notation is induced by the first two conditions. In particular, .pr is the primary object map (obtained from .ec) and c is the metaclass root.
(ec~1) .ec is an injective well-founded map.
(ec~2) (O.pr, ϵ, , r) is a primary structure of ϵ.
(ec~3) For every primary objects a, b and every natural i, j > 0, the following are satisfied:
  • (A) a.ec(i) b   iff   a ϵi b   where ϵ denotes the restriction of ϵ to primary objects.
  • (B) a b.ec(j)   iff   a < c, b = r and j = 1.
  • (C) a.ec(i) b.ec(j)   iff   a.ec(i-1) b.ec(j-1).
The definition is in fact a prescription for the eigenclass completion of a primary structure. Given a canonical primary structure (O.pr, ϵ, , r), the construction steps are as follows:
  1. Equip each primary object with an eigenclass chain.
  2. Extend according to (ec~3).
  3. Extend ϵ by setting (ϵ) = (.ec) ().
Canonical eigenclass structure
By a canonical eigenclass structure of ϵ we mean a structure (O, .ec, , r) where O is a set of objects, .ec is the eigenclass map O O, is the inheritance relation between objects, and r is a distinguished object. The following additional terminology and notation applies:
A canonical eigenclass structure of ϵ is subject to the following axioms (the separator delimits the 5 axioms of monotonic eigenclass structures):
(e~1) Inheritance, , is a partial order.
(e~2) The eigenclass map, .ec, is an order-embedding of (O, ) into itself.
(e~3) Objects from eigenclass chains of terminals are minimal in inheritance.
(e~4) Every eigenclass is a descendant of the inheritance root.
(e~5) R has no lower bound in .
(e~6) Helix classes are (a) totally ordered by , (b) an upset in , and (c) at least two in number.
(e~7) Objects from R have no siblings in .
(e~8) Every non-helix object is well-founded w.r.t. ϵ.
(e~9) Descendants of non-helix eigenclasses are eigenclasses.
(e~10) For every object x and every class y such that x.ec ϵ y, there is a class a such that x ϵ a ϵ y.
(e~11) Every object x has a least primary container, x.class.
(e~12) The set C of classes is finite.
Conditions marked with have a direct counterpart in the axiomatization of the primary structure.

Notes and observations:

  1. Axiom (e~2) is the essential axiom. It can be equivalently expressed as () = (.ec) () (.ce).
  2. Axiom (e~3) asserts that terminals are unrelated by < to any object and that this property is preserved after a free instantiation of any class.
  3. Axiom (e~4) asserts that r is a universal object: O = r.϶. Since r is asserted to be a class by e~(1)(2)(4)(5), every object is an instance of r.
  4. Axiom (e~5) asserts that .ec is a well-founded map. Due to the injectivity asserted by (e~2), .ec establishes the infinite regress of eigenclasses.
  5. Axiom (e~6) asserts that the restriction to H is (a)(b) as simple as possible but (c) non-degenerate: H R. Using the finiteness condition (e~12), H is asserted to form a closure system in (O T, ). In addition, the existence of a least helix class, c, is ensured.
  6. Axiom (e~7) asserts that the eigenclass chain of c is not used for the connection to the helix. Using .he as the closure operator for H (i.e. such that r..he = H), (e~7) can be expressed as c C.he.pr.
  7. Axiom (e~8) asserts that H is exactly the non-well-founded part of the structure. Moreover, x H iff x ϵ x.
  8. Axioms (e~9) and (e~10) assert a one-to-one correspondence between the well-founded part (O H, …) and its restriction (O.pr H, …) to primary objects.
  9. Axiom (e~10) can be equivalently stated as any of the following:
  10. Axiom (e~11) asserts that the set O.pr of primary objects forms a closure system in inheritance. We denote .c the corresponding closure operator so that O.pr = O.c and .class = .ec.c.
    Moreover, this axioms makes (e~4) redundant. (This is because if e~(1)(2) is assumed then:   (e~4)   ↔   every object has a primary container.)

Notes and observations:

  1. A canonical eigenclass structure of ϵ is expressible in the (O, ϵ) signature.
  2. Since (e~4) asserts that every object has a primary container, it becomes redundant within canonical structures due to (e~11).
Correspondence between primary and eigenclass structures
The correspondence between the primary structures and the eigenclass structures is described as follows.

Proposition:

  1. The restriction of a canonical eigenclass structure to primary objects is a canonical primary structure.
  2. The .c map is a homomorphic projection of (O, ϵ, ) onto (O.pr, ϵ, ).
  3. A tight canonical eigenclass structure is a canonical eigenclass structure satisfying the following stronger version of axiom (e~9):
    (e~9⁺) Descendants of eigenclasses-other-than-r.ec are eigenclasses.
Note that (e~9⁺) restrains the helix entry x.he of explicit metaclasses x other than c to r.ec. As a consequence, if x, y are explicit metaclasses different from c such that x ϵ y then cannot be a single inheritance. (Ancestors of x.ec cannot be linearly ordered in since y and x.ec.re are incomparable.) A non-tight canonical structure (so that (e~9⁺) is not imposed) allows single inheritance for arbitrary depth of instantiation.

The diagrams below show the correspondence between a canonical eigenclass structure, its restriction to primary objects and the subsequent tight eigenclass completion. Note that the tree structure of is not preserved.

(a)
Canonical eigenclass structure
(O, .ec, )
(b)
The primary structure of (a)
(O.pr, .class, )
(c)
The tight
eigenclass completion of (b)
Ruby's additional constraints
The Ruby programming language imposes single inheritance and a single metalevel for classes. These additional conditions can be respectively written as follows.
(e~13) For every object x, the set x. is linearly ordered by .
(e~9⁺⁺) Descendants of eigenclasses are eigenclasses.   (Equivalently, every class is on metalevel 1.)
The conditions make some of the previous ones redundant. In particular, (e~9)(e~9⁺)(e~9⁺⁺) is an obvious implication chain.

Monotonic eigenclass structure of ϵ

The family of structures given by the first five axioms of canonical eigenclass structures can be regarded as the essential mathematical model for the core structure of object technology. This is for the following reasons: The next subsection provides a concise and rather self-contained definition of monotonic eigenclass structures.
Monotonic eigenclass structure
By a monotonic eigenclass structure we mean a structure S = (O, .ec, , r) where The usual ancestor / descendant terminology is used for inheritance. Objects that are not descendants of r are terminal(s). Let .ec denote the reflexive transitive closure of .ec. For an object x, the set x.ec (the image of {x} under .ec) is the eigenclass chain of x.
The structure is subject to the following axioms:
(e~1) Inheritance, , is a partial order.
(e~2) The eigenclass map, .ec, is an order-embedding of (O, ) into itself. () = (.ec) () (.ce)
(e~3) Objects from eigenclass chains of terminals are minimal in inheritance. (O × T.ec) (<) =
(e~4) Every eigenclass is a descendant of the inheritance root. O.ec r
(e~5) The eigenclass chain of r has no lower bound in . R. =
The definitions introduced before the axioms of canonical eigenclass structures apply. See also notes to the axioms.
Decomposition of ϵ
As already shown for the Ruby core sample, any monotonic eigenclass structure can be expressed in the minimum signature (O, ϵ). The constituents of the original signature are obtained as follows:
x y   ↔   x.ϵ y.ϵ,
x.ec = y   ↔   x.ϵ = y..   (In addition, x.ec = yx. = y.϶ but does not hold in general.)
Moreover, r is the unique top of O.ϵ.

Monotonic primary structure of ϵ

For the sake of completeness we introduce a generalization of canonical primary structures according to the following table.
Special General
.ec is total Canonical eigenclass structure Monotonic eigenclass structure
.ec is empty Canonical primary structure Monotonic primary structure

Note: For simplification, we introduce slight discrepancy with the more precise document []. The family of structures defined in the following subsection should be more correctly called membership-based monotonic structures since they rely on the prescription

(mp-γ) x ϵ-k y x < r.ϵk+i and r.ϵk+i r.ϵk+i-1 and r ϵi y for some natural i
for negative powers of ϵ (ϵ-k where k > 0) which we introduce later for basic structures. The correctly defined family of monotonic primary structures arises simply as a subfamily of monotonic basic structures in which .ec = (so that every object is primary).
Monotonic primary structure
By a monotonic primary structure of ϵ we mean a structure (O, ϵ, , r) where O is a set of objects, ϵ is the membership relation between objects, is the inheritance relation between objects, and r is the inheritance root, a distinguished object.
The structure is subject to the following axioms:
(mp-γ~1) is a partial order.
(mp-γ~2) (ϵ) () = (ϵ) = () (ϵ).   (That is, (a) (ϵ) () (ϵ) and (b) () (ϵ) (ϵ).)
(mp-γ~3) The inheritance root r is the top of O.ϵ w.r.t. .
(mp-γ~4) Every object has a container, O = O.϶.
(mp-γ~5) Terminal objects are minimal in .
(mp-γ~6) If H r.ϵi for every natural i then H has no lower bound in .
(mp-γ~7) For every natural i such that H r.ϵi,   if x < r.ϵi+1 then x.϶ < r.ϵi.

Observation: For a structure S = (O, ϵ, , r) the following are equivalent:

Moreover, the (p~4) condition (Metaclasses can only have classes as instances.) can only be stated for the metaclass root since other metaclasses are strict descendants of r.ϵ and thus are subject to (mp-γ~7).

 

Basic structure of ϵ

In this section we introduce a common generalization of the hitherto introduced structures that can be regarded as an abstract set-theoretical model of the core structure of object technology. The generalization can be roughly characterized by the following steps: This is established by the family of basic structures [].
Basic structure
ϵ2ϵ¯2
ϵ
ϵ¯
ϵ-1
ϵ-2
By a basic structure of ϵ we mean a structure S = (O, ϵ⁽*⁾, ϵ¯⁽*⁾, r, .ec, .ɛɕ) where and the remaining two definitory constituents are partial maps O O (i.e. functional relations between objects): Note that due conditions (a–c) the two bi-infinite sequences are given by ϵ and the left-infinite sequence { ϵ¯i | i , i 1 }. In particular, we can drop the wildcard superscript from ϵ⁽*⁾ in the signature. Before stating the axioms some preliminary definitions need to be introduced. The structure is then subject to the following axioms:
The axioms
(b~1) (ϵ¯) (ϵ).
(b~2) (ϵ¯i) (ϵ¯j) (ϵ¯i+j)   for every integer i, j.
(b~3) (ϵ) (ϵi) (ϵ1+i)   for every integer i.
(b~4) (ϵ¯i) (϶¯-i) = .ec(i)   for every integer i.
(b~5) The inheritance root r is the top of O.ϵ w.r.t. .
(b~6) Every object x has a container, x.ϵ .
(b~7) For every object x from T O.ɛɕ and every natural i,   (a) x.϶-i = {x}.ec(i), (b) x.϶-i.ϵ = x.϶-i.ϵ¯.
(b~8) If x.ɛɕ = y then: (a) {x} = y.϶, (b) x.ϵi = y.ϵi-1 for every i 1, (c) (x,y) (ϵ¯).
(b~9) Reserved for the non-member union map.
(b~10) For every object x, the metalevel index x.mli is finite.
(b~11) For every object x,   x.d = ϖ   →   x.ϵ = x.ϵ¯.   (That is, every unbounded object is a power member.)

Observations:

  1. For a suitable choice of (i,j) in (b~2) we obtain transitivity of , subsumption of ϵ¯, and the monotonicity of ϵ¯.
  2. For i = 0 in (b~3) we obtain the subsumption of ϵ: (ϵ) () (ϵ). In contrast, monotonicity is not asserted.
  3. For i = 0 in (b~4) we obtain the antisymmetry and reflexivity of so that is a partial order on O.
  4. (b~5) asserts that O = T r.. Since r ϵ x r for some object x it follows by subsumption of ϵ that r ϵ r. Since r is non-well-founded in ϵ it follows by (b~11) that r ϵ¯ r. Consequently, for every non-terminal x,   x ϵ¯ r by monotonicity of ϵ¯ and x ϵ r since (ϵ¯) (ϵ).
  5. As a particular consequence of (b~6) and (b~7)(b) we obtain that x ϵ¯ r for every terminal x. It follows that r is a universal (power) container: O = r.϶¯ = r.϶.
  6. As a particular consequence of (b~7)(a) we obtain that every object from T.ec is minimal in (cf. (e~3)).
Rank
If every object is ϵ-grounded, i.e. connected with a terminal object via ϵ (equivalently, T.ϵ = O) then the prescription for the rank function is simplified as follows. Let W be the set of objects that are well-founded in ϵ. Then
x.d = ϖ if x W,
x.d = ϖ sup {a.d + 1 | a ϵ x} if x W.
That is, x.d = ϖ for all objects x that are either non-well-founded in ϵ or are well-founded and their rank in the well-founded relation (W,ϵ) is greater or equal to ϖ. For the remaining objects x, let x.d be their rank in (W,ϵ).

The following diagram shows an ad-hoc completion (⁎) making each object of the original structure ϵ-grounded. Added objects are displayed in khaki color. See [] for the precise definition.

Notes and observations:

  1. (⁎) As indicated by the case of the a object, new member chains are added even for objects from T.ϵ so that the term completion is not quite adequate.
  2. It is asserted that x.mli x.d for every object x. However, even memberless objects can have their rank strictly higher than the metalevel index. This is the case of the b object (2 = b.mli < b.d = 3).
Another simplification arises in the case ϖ = ω. That is, the default value of ϖ is the first infinite ordinal so that the rank of an object is either finite of equal to ω. In this case, .d can be defined by
Bounded membership
The rank function .d is used for distinction between two kinds of objects: The bounded membership relation is then the domain-restriction of ϵ to bounded objects, i.e. The set of bounded objects can be referred to by O. or by r.. Every bounded object is well-founded in ϵ (i.e. is a well-founded relation) but not necessarily vice versa. We also introduce the ¯ symbol for (ϵ¯) () (the bounded power membership).

Note that axioms (b~1) and (b~11) can be stated as a single condition (ϵ) = () (ϵ¯). This establishes an inclusion lattice between ϵ, , ϵ¯ and ¯ according to the above diagram on the right.

Singletons
Singletons are the objects from (T.ec O.ɛɕ).ec (where .ec is the reflexive transitive closure of .ec). The range-restriction of ϵ to singletons is denoted .ɛϲ and called the singleton map. Axioms (b~7)(a) and (b~8)(a) assert that .ɛϲ is a partial map between objects, so that Another consequence of the axioms is .ɛϲ.ɛϲ = .ɛϲ.ec – powerclasses of singletons are singletons. The primary singleton map .ɛɕ used in the axiomatization equals the difference (.ɛϲ) (.ec).

The following table shows similarities and differences between .ec and .ɛϲ.

y is the powerclass of x,
x.ec = y
y is the singleton of x,
x.ɛϲ = y
Members of y x. = y.϶ {x} = y.϶
Ancestors of y x.ϵ¯ = y. x.ϵ = y.
Metalevel index increment (y.mli - x.mli) 1 1
Rank increment (y.d - x.d) on O. 1 1
x (or y) can be unbounded YES NO
Metaobject structure
The diagram on the right shows a basic structure that is metaobject complete – the powerclass map .ec (shown by horizontal blue arrows) is total and the singleton map .ɛϲ (shown by blue arrows pointing to a circle which indicates a singleton) is defined on the set O. of bounded objects. This subfamily of basic structures can be axiomatized as metaobject structures in the signature (O, , r, .ec, .ɛϲ). The membership constituents of a basic structure are obtained as follows:
() = (.ɛϲ) () (bounded membership),
(ϵ¯) = (.ec) () (power membership),
(ϵ) = () (ϵ¯) ((object) membership),
(ϵ-k) = () .ec(-k) (anti-membership and its powers, k > 0).
A metaobject structure is subject to the following axioms:
(mo~1)(mo~5) The same as axioms (e~1)(e~5) of monotonic eigenclass structures.
(mo~6) The singleton map, .ɛϲ, is injective.
(mo~7) Objects from O.ɛϲ.ec are minimal in .
(mo~8) For every objects x, y such that x.ɛϲ is defined,   x.ɛϲ y.ec x y.
(mo~9) For every object x,   x.ɛϲ is defined   ↔   x.d < ϖ.
The rank function .d is defined by the same prescription as in basic structures. See [] for details.
Monotonic structures
ϵ
ϵ-1
ϵ-2
Monotonic basic structures are such that (ϵ¯) = (ϵ). They can be axiomatized in the signature (O, ϵ⁽*⁾, r, .ec) where ϵ⁽*⁾ is a left-infinite (or down-infinite) sequence according to the diagram on the right. The axioms are as follows (using the terminology and notation established for basic structures):
(m~1) (ϵi) (ϵj) (ϵi+j)   for every integer i, j.
(m~2) (ϵi) (϶-i) = .ec(i)   for every integer i.
(m~3) O.ϵ r.
(m~4) O = O.϶.
(m~5) For every object x from T and every natural i,   {x}.ec(i) = x.϶-i.
(m~6) For every object x, the metalevel index x.mli, defined as sup { i | x ϵ1-i r, i }, is finite.

Structures that have been introduced before the basic structures in this document can be considered to form subfamilies of monotonic basic structures:
The union map
The (b~9) label is reserved for the axiomatization of the non-member union map, .. This is considered to be the first candidate for a possible expansion of basic structures. The . map forms the explicit part of .υ, the union map, which is a partial map between objects that is an abstraction of the least anti-container and thus of set union. The .υ map is obtained from . by Axioms of (non-expanded) basic structures assert that (ϵ-1) (϶) is a partial map. Moreover, the inverses of .ec and .ɛϲ are distinguished submaps. The presumed axiomatization of . is shown below together with the similar axiom (b~8).
(b~8) If x.ɛɕ = y then: (a) {x} = y.϶, (b) x.ϵi = y.ϵi-1 for every i 1, (c) (x,y) (ϵ¯).
(b~9) If x = y. then: (a1) x.϶¯ = y.϶.϶¯, (a2) x.϶ = y.϶2, (b) x.ϵi = y.ϵi-1 for every i 0, (c) (x,y) (ϵ).
Unfortunately, the . map also requires an adjustment to the definition of the rank function .d (see [] for details).

Complete structure of ϵ

A basic structure S = (O, ϵ, ϵ¯⁽*⁾, r, .ec, .ɛɕ) is said to be complete if it satisfies the following conditions:
(A) S is extensionally consistent: For every objects x, y,   x y   ↔   x = y or x. y..
(B) S is metaobject complete: (a) S is powerclass complete and (b) S is singleton complete.
(C) S is extensionally complete: For every subset X of O. there is an object x such that x. = X.
(D) S is -ranked: For every object x,   r(x) (the -rank of x) equals x.d.
We also say that S is a complete structure (of ϵ). Note that due (B), S can be considered a special case of a metaobject structure. Every complete structure S is uniquely given by the bounded membership according to the following table:
Inheritance x y   ↔   x = y or x. y.
Inheritance root r.   =   O.
Bounded inheritance x 0 y   ↔   x y and x O.
Singleton map x.ɛϲ = y   ↔   {x} = y.
Powerclass map x.ec = y   ↔   x.0 = y.
Power membership x ϵ¯ y   ↔   x.0 y.
Object membership x ϵ y   ↔   x y or x ϵ¯ y
The bounded inheritance relation is the zeroth power of , similarly to the () = (ϵ0) correspondence. By definition, x.0 = x. O.. There are other simplifications via :
Terminal objects T   =   O O.
Metalevel index x.mli   =   min {i | x T.i, i }
Rank x.d   =   sup {a.d + 1 | a x}
The equalities for .mli and .d can be described as follows. Moreover, there is a simple and transparent axiomatization of complete structures via (O, ). Such an axiomatization can be provided in a generalization for arbitrary rank of , as shown in the next subsection. (Realize that r.d equals by definition a fixed limit ordinal ϖ. Since r.d is also the -rank of r and r. = O. it follows that the rank of (O, ) equals ϖ+1.)
Superstructure
By an (abstract) superstructure we mean a structure (V, ) (where V is the set of objects, and is a relation between objects) such that the following conditions hold.
(1) is well-founded.   For a subset X of V let us denote r(X) the -rank of X.
(2) For every non-empty set X of objects such that r(X) < r(V) there is a unique object x such that x. = X.
The existence and uniqueness of the x object in (2) can be stated separately:
(2a) For every set X of objects such that r(X) < r(V) there is an object x such that x. = X.
(2b) For every objects x, y from V.,   if x. = y. then x = y.   (Weak extensionality of )
It can be shown that up to isomorphism, every non-empty superstructure (V, ) is uniquely given by the pair (α, κ) of non-zero ordinal numbers where α is the -rank of V and κ is the cardinality of the ground stage (which is the set V V. of objects with zero rank, i.e. the set of terminal objects).

For convenience, we let the term α-superstructure mean a superstructure (V, ) whose -rank equals α. The axiomatization of complete structures via can be then expressed as follows:

(O, ϵ, ϵ¯⁽*⁾, r, .ec, .ɛɕ) is a complete structure of ϵ   ↔   (O, ) is an (ϖ+1)-superstructure.
That is, the bounded membership in a complete structure forms an (ϖ+1)-superstructure, and, conversely, an (ϖ+1)-superstructure (O, ) induces a complete structure S according to the table above. Bounded membership in S coincides with the original relation.
Stages
Any superstructure can be thought to be built in stages. For an ordinal number i, the i-th stage, Vi, consists of objects whose rank is strictly less than i. In the case of an (ϖ+1)-superstructure (O, ) we obtain the following sequence: Except for V0 and Vϖ+1 each stage Vi is an -preimage of a unique stage object, ri (see the diagram on the right, note that singletons not from T.ec are not shown).
Kinds of superstructures
With some adjustments, the definitional extension of an (ϖ+1)-superstructure (O, ) as specified above can be applied to arbitrary superstructures (V, ). Apart from the degenerate cases of empty , the adjustments to be made are the following: We can then classify superstructures according to the properties of their definitional extensions:
(Let ϖ be a limit ordinal and α an arbitrary ordinal.) ZFC MK Degenerate cases
V = Vϖ V = Vϖ+1 V = Vα+2 V = V1 V = V0
Rank of V ϖ ϖ + 1 α + 2 1 0
Bounded objects V. V Vϖ Vα+1
Existence of the (an) inheritance root r (r. = V.) NO YES YES NO, unless
V = {r}
NO
Powerclass map .ec is total YES YES NO YES
Singleton map .ɛϲ is total YES NO NO NO YES
Boundedness preserved by .ec / .ɛϲ YES YES NO YES YES
The ZFC and MK labels indicate a connection to set theory. For an inaccessible cardinal ϖ, a superstructure (V, ) whose ground stage contains exactly one object (i.e. is extensional) is a model of set theory: Complete structures belong to the MK-group.

Note: In [], the singleton map .ɛϲ is total – unbounded objects have their singleton constantly set to r (considering (V, ) as a model of MK).

Completion
Every basic structure can be faithfully embedded into a complete structure. That is, if S0 = (O0, ϵ, ϵ¯⁽*⁾, r, .ec, .ɛɕ) is a basic structure then there is a complete structure V = (V, ϵ, ϵ¯⁽*⁾, rϖ, .ec, .ɛɕ) and an embedding map from O0 to V such that the following conditions are satisfied:

Note: If R denotes a relation both in S0 and V then is an embedding w.r.t. R if the following equivalence holds for every objects x, y from O0:

The embedding is established in the following steps:
  1. Rank pre-completion. This step can be omitted for ϖ = ω. Otherwise, attach a set X of ϖ new members to each primary non-well-founded object x that is not -ranked. The members are attached in such a way that (X, ϵ, ) is isomorphic to (ϖ, , ).
  2. Powerclass completion. Append an infinite powerclass chain to each object for which the powerclass is not defined. The resulting structure is powerclass complete.
  3. Singleton completion. Append an infinite singleton chain to each bounded object for which the singleton is not defined. Technically, this can be done in two steps by first adding just the missing primary singletons and subsequently performing the powerclass completion.
  4. Extensional pre-completion. (⁎) To every object x that is not extensionally consistent, i.e. for which there exists y such that the following equivalence is not satisfied, attach two powerclass chains each of which starts in a terminal object. The resulting structure is pre-complete, that is, In particular, the structure is fully determined by bounded membership according to the same prescription as with complete structures.

    Note: (⁎) A simplified description is provided here, see [] for the detailed description.

  5. Cumulative embedding into an (ϖ+1)-superstructure. Let S = (O, ) be the pre-complete structure to be embedded. Choose an (ϖ+1)-superstructure V = (V, ) so that its ground stage V1 has the same cardinality as the set T of terminal objects of S. Then the requested embedding map is obtained as a limit of a transfinite sequence of maps from O to V defined as follows:
    1. The restriction of i to terminals is for every i identical and forms a bijection between T and V1.
    2. The restriction of i to the set O. of non-terminal objects x is recursively defined by
      x.ν0. = x.¯0.ec. x.0,
      x.νi. = x.϶¯i-1.ec. x.0 if i is a successor ordinal,
      x.νi. = { x.νk. | k < i } if i is a limit ordinal.
    Note that the definition of 0 is by the well-founded recursion on (O, ), whereas the definition of i for i > 0 uses transfinite recursion over i.
Powerclass completion
Powerclass completion deserves particular attention since it is actually implemented in Ruby. For canonical primary structures, the completion has already been described, see the (ec~3) condition. (Since (ϵ) = (ϵ¯), the term eigenclass is used for powerclass.)

In general, for a basic structure S0 = (O0, ϵ, ϵ¯⁽*⁾, …), its powerclass completion S = (O, ϵ, ϵ¯⁽*⁾, r, .ec, .ɛɕ) is created in the following steps:

  1. Prolongate powerclass chains to infinity, that is, extend (O0, .ec) to (O, .ec) so that
  2. Extend membership and power membership powers to new objects.
    For every primary objects a, b and every natural i, j such that at least one of a.ec(i) or b.ec(j) is new,
    a.ec(i) ϵ b.ec(j)   iff   a ϵ¯1+i-j b,
    a.ec(i) ϵ¯k b.ec(j)   iff   a ϵ¯k+i-j b     for every integer k.

Representation by sets

As already foreshadowed in the context of superstructures, the main correspondence between objects and well-founded sets can be expressed by
  ↔   .
That is, bounded membership, , is an abstraction of set membership, . Assuming powerclass completeness for simplicity, the set-theoretic interpretation of the 3 main constituents of the core structure of object technology can be informally described via the following correspondences:
, that is, inheritance is an abstraction of set inclusion,
x.ec r (x), that is, the powerclass map is an abstraction of relativized powerset operator,
ϵ plus .ec. that is, object membership is like set membership augmented with the inclusion of the powerclass.
The von Neumann universe
Let 𝕍 be the von Neumann universe of all well-founded sets. Recall that 𝕍 is obtained from the empty set by iterative application of the powerset operator . For every ordinal α,
𝕍α = { (𝕍β) | β < α },   that is, 𝕍0 = ,
𝕍α = (𝕍α-1) if α is a successor ordinal,
𝕍α = { 𝕍β | β < α } if α is a limit ordinal,
𝕍 = { 𝕍α | α On }.   (α On means that α is an ordinal.)
The rank function r() on 𝕍 is defined by For every ordinal α,   𝕍α is a set whose members are exactly the sets x such that r(x) < α. The axiom of foundation says that every set belongs to 𝕍.
(ϖ+1)-superstructure in
The (ϖ+1)-superstructure V = (V, ) referred to in the last step of the completion of object membership can be chosen as a restriction of the set membership structure in the von Neumann universe. Given the requested cardinality κ of the ground stage, one can proceed as follows.
  1. Determine the ground stage. Choose V1 to be a set such that Since for every ordinal i, the set 𝕍i+1 𝕍i has cardinality at least i, we can put α = κ+1.
  2. Cumulate the remaining stages. Similarly as with the von Neumann hierarchy, construct a transfinite sequence of stages up to the (ϖ+1)-th stage.
    V0 = ,
    Vi = V1 ((Vi-1) {}) if i is a successor ordinal, (in contrast, 𝕍i = (𝕍i-1))
    Vi = { Vj | j < i } if i is a limit ordinal,
    V = Vϖ+1.
As a result, (V, ) is an (ϖ+1)-superstructure such that for every x, y from V,
Basic structure as a set
Since every basic structure can be embedded into an (ϖ+1)-superstructure which in turn can be embedded into the von Neumann universe, it follows that every basic structure S can be represented by a well-founded set O. The following table shows how the main constituents of S can be expressed in set-theoretic terms. (Recall that (x) is the set of singleton subsets of x.)
Terminal objects T   =   O (O O)
Inheritance root r   =   O T
Complete extension V   =   r ((r) {})
For every x, y from O :
Bounded membership   x y   ↔   x y
Inheritance x y   ↔   x y
Singleton map x.ɛϲ = y   ↔   {x} = y
Powerclass map x.ec = y   ↔   r (x) = y
Power membership x ϵ¯ y   ↔   r (x) y
Object membership x ϵ y   ↔   r (x) y or x y
The V set represents a complete basic structure V that is a faithful extension of S.

 

Specializations of ϵ

This section describes how the canonical structure of object membership can be applied to object models of particular languages. We focus on 8 class-based programming languages Ruby, Python, Smalltalk-80, Java, Scala, CLOS, Objective-C, and Perl which have already been considered for the sample structure of the instance-of relation. Prototypal languages (JavaScript), ontology languages (RDFS) and the Dylan programming language (as the only representant of non-monotonic membership) are discussed separately. Similarly, the support of actual eigenclasses is described in another section.

In a particular programming language, object membership appears in a specialized form. Such a specialization can be obtained by adjustments to the canonical structure of ϵ. In most cases (5 of 8), it is necessary to refine the structure by additional constituents so that the minimum signature (O, ϵ) needs to be extended.

In Ruby
We have already described the Ruby's additional constraints for the canonical structure: single inheritance and single explicit metaclass (C c. = {c}). As of Ruby 1.9 (and newer), there are 4 helix classes:
c = Class < Module < Object < BasicObject = r.
As a consequence of single inheritance, the structure is determined by superclass and eigenclass links, corresponding to the superclass and singleton_class introspection methods, respectively.

However, this is only the (canonical) reduct of what is understood by object membership in Ruby. The full membership, ϵ, results from a finer structure which 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 (aliased by kind_of? and, in the inverse, also by Class#===). You can check that previously we stated the is_a?ϵ correspondence just for the provided sample structures. Similarly, the canonical 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, Python core structures are exactly the primary structures (O.pr, ϵ, ) with two helix classes. (Therefore, the Python object model conforms to the tight canonical structure.) Helix classes are named as follows:
c = type < object = r
In Scala and Java
In Scala and Java, the term classes is used just for a subset of the set C of primary descendants of r. The subset forms a closure system in (r., ), so that it can be expressed as C.c where .c is an explicit closure operator added to the canonical structure. The generalized structure is then 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
Both Pharo and Squeak, the two major Smalltalk-80 implementations, provide several ways to break fundamental characteristics of the core structure such as the one-to-one correspondence between classes and implicit metaclasses or acyclicity of inheritance. The diagram below shows that (1) instantianting the class named Behaviour (or Class or ClassDescription) creates a dangling class, (2) instantianting the class named Metaclass creates a dangling metaclass, (3) a class can be made a direct inheritance descendant of its metaclass. The superclass: method allows to change the superclass link to point to (presumably) arbitrary non-terminal object so that cycles can arise.
(Pharo 1.3 / Squeak 4.2)

r  := ProtoObject.
b  := Behavior.
c  := Class.
mc := Metaclass.
  • (1) a := Behavior new.
  • (2) m := Metaclass new.
  • (3) Object subclass: #B.
    B superclass: (B class).
We assume that the above anomalies are only allowed due to negligence of implementations, not by design. To rule out the anomalies, we only consider structures created As already demonstrated on the sample core structure, the Smalltalk-80 object model does not conform to the canonical structure of ϵ due to the metaclass redirection. This is expressed via an imposed metaclass root ȼ, named Metaclass, which induces the corresponding imposed class map, .ȼlass. 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. Note that the class introspection method does not correspond to .ȼlass but to .aȼlass (the imposed actualclass map) which takes object actuality into account.

Another quirk that can be captured by an appropriate generalization of the canonical structure is formed by additional twist links. These are inheritance 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 contains 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. Metaclasses can be defined as C.ȼlass. – this makes Class and Metaclass the only explicit metaclasses. Finally, the Ruby conditions apply: single inheritance and single metalevel for classes.
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 is the only helix class so that r.class = r. Equivalently, (r.ec, r) is the twist link.

As of GNUstep, there are (at least) 3 built-in inheritance roots, named Object, NSObject and NSProxy. Like in Smalltalk-80, the Ruby conditions apply: single inheritance and single metalevel for classes. As a consequence of degeneracy, metaclasses cannot be expressed as C.class. since this set contains all classes. One possible solution is to simply define a metaclass as an object on the metalevel 2 or higher (so that there are no explicit metaclasses).

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
As already shown on the sample structure, the Perl object model is distinguished by total circularity of classes: Every class is the class of itself. This is equivalent to say that Perl establishes the (C, ) = (C, ϵ) equality: the instance-of relation, in its restriction to classes, coincides with the inheritance relation. This way Perl merges the two different meanings of is-a. Consequently, the isa introspection method can be used both to detect membership as well as inheritance.

As for metaclasses, we can apply the solution proposed to Objective-C and define metaclasses to be the objects on metalevel 2 or higher. Since Perl does not have any actual objects on these metalevels, there are no actual metaclasses.

In Perl, multiple inheritance is allowed. The built-in class named UNIVERSAL stands for the inheritance-root r. However, the assumption is needed that the @ISA variable of this class is not changed.

Eigenclass actuality

The concept of eigenclass actuality has already been introduced for the Ruby core structure. Any in-memory representation of object membership can only store a finite front part of the structure. We call objects from this substructure actual(s). In languages that do not support ϵ refined by implicit objects, the actual objects are exactly the primary ones. In general, some eigenclasses may also be actual.

Given a monotonic eigenclass structure (O, ϵ), possible subsets A of actual objects can be axiomatized as follows. (For a set X of objects, we let X. be the set of all strict upper bounds of X.)

(a~1) A is finite.
(a~2) A O.pr.   (Every primary object is actual.)
(a~3) A A.ce.   (If x.ec is actual then so is x.)
(a~4) A is a closure system in .   (Every object has a least actual ancestor.)
(a~5) A H = (R A)..   (There exist a natural k such that for every helix object x,   x Ax.mli < k.)
Conditions (a~4) and (a~5) assert that there is a twist pair of objects t, u such that u t R and u. = A H. (That is, u is the unique inheritance parent of a metalevel top t, and u is the bottom of all actual helix objects.) Since A is a closure system in inheritance, there is a corresponding closure operator, .a, and the corresponding actualclass map, .aclass = .ec.a. For an object x, the actualclass of x is the least actual container of x.

In canonical structures, the .aclass map forms a tree (similarly to .class). The u object that is the bottom of A H belongs to the eigenclass chain of c (the instance / metaclass root) and is the unique fixpoint of .aclass (that is, u is the root of the actualclass tree). Observe also that

While .ec is a conceptual refinement of .class, the actualclass map is an implementation-oriented refinement. The .aclass map is identical to the .class map iff no eigenclass is actual.

Note: In most cases (e.g. in the introductory sample), the blue arrows contained in the diagrams show the actualclass map. (In general, blue arrows have been used to display .aclass or .class or .class. or .aȼlass.)

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.
In Ruby
In Ruby, all objects that are not immediate values can have actual eigenclasses. As of MRI/YARV 1.9 inheritance ancestors of actual objects are actual, i.e. for the set A of actual objects
(a~6) A is an up-set in .
This condition is thus satisfied for implementations of all languages with (e~9⁺⁺) considered in this document. (In general, A needs to be replaced with A {r.ec}.)

Ruby is the only language that supports dynamic eigenclass allocation. Typically, for an object x, the eigenclass x.ec becomes actual by defining singleton methods for x. For efficiency, there are more allocated eigenclasses than those accessed from the user code. This induces 2 different extents of actuality, as described before.

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

The Dylan core structure

The Dylan programming language is presumably the first language that introduced singleton objects and probably the only language (as of 2014) that supports – at least experimentally – both powerclasses and universal singletons. The singleton support makes Dylan the only non-monotonic language considered in this document.

Non-terminal objects in Dylan are called types []. The following table shows 3 supported kinds of types that have correspondence to basic structures.

Kind of Dylan types Our terminology Evaluation Instances of
(via instance?)
Classes <class>
Singletons x.ɛɕsingleton(x) <singleton>
Subclass types [] Powerclasses outside O.ɛϲ x.ecsubclass(x) <subclass> (⁎)

Notes:

  1. (⁎) As of Open Dylan 2013.2, the <subclass> class is not referenced by its name.
  2. Evaluation of subclass(x) is supported for every x that is a class.
  3. Evaluation of singleton(x) is supported for all objects x. As a consequence, there cannot be a perfect correspondence between singletons in Dylan and singletons in basic structures since the latter ones are only defined for bounded objects.
  4. Every evaluation of singleton(x) or subclass(x) (even when performed repeatedly with the same argument x) returns a new object. Such objects can be thought of as equivalent representants of a given singleton or powerclass.
Sample
The following diagram shows a sample core structure of Dylan. Inheritance between non-terminal objects can be detected by the subtype? method. The composition of blue arrows with inheritance – object membership in Dylan – is exactly what is detected by the instance? method. All powerclasses of classes (i.e. all the supported powerclasses w.r.t. given set of classes) are displayed. In contrast, supported singletons are only shown for some objects.
(Open Dylan 2013.2)

let r  = <object>;
let ty = <type>;
let c  = <class>;
let si = <singleton>;
let lt = last(direct-superclasses(si));
let su = object-class(subclass(r));
let A = make(c);
let B = make(c, superclasses: list(A));
let u = make(B);

lt <limited-type>
su <subclass>

Observations:

  1. There is a correspondence between subclass types in Dylan and metaclasses in Smalltalk-80.
    Dylan Smalltalk-80
    Powerclasses of classes (C.ec) are termed:   Subclass types (Implicit) metaclasses
    The (imposed) metaclass root ȼ is named:   <subclass> Metaclass
    For a class x, the powerclass x.ec is evaluated by:   subclass(x) x class
    The imposed class map .ȼlass is introspected by method:   object-class
    The imposed actualclass map .aȼlass is introspected by:  
    class
  2. There is a cycle in membership caused by singletons. According to the instance? method,
  3. Powerclasses (Dylan's subclass types) can only have classes as members. As a consequence, () (.ec) (ϵ) is not satisfied in general. For example, u.ɛϲ (the singleton of the terminal object u) is from B. but not from B.ec.϶.

Prototypes

It is also possible to refine the instance-of relation the opposite way by eigenclass predecessors of objects, rather than successors. Such implicit objects are called (instance) prototypes. The prototype of a class y, denoted y.ce, is the highest instance of y, i.e. every instance of y is an inheritance descendant of y.ce. In contrast to eigenclasses, we only consider prototypes of classes. First, it does not (seem to) make sense to have instance prototypes of terminal objects. Second, having no prototypes of prototypes simplifies the description.

Formally, object membership with prototypes can be defined by combining eigenclasses and prototypes. In the specialized document [], S1ȷ structures are introduced as structures (Θ, O, ϵ) such that (Θ, ϵ) is a canonical eigenclass structure without terminal objects, and O is a subset of Θ such that the substructure (O, ϵ) is a canonical eigenclass structure whose non-terminal objects form the set Θ.ec.. Objects from Θ O are the instance prototypes. The inclusion Θ.ec. O establishes a one-to-one correspondence between the i-th metalevel of (Θ, ϵ) and the (i+1)-th metalevel of (O, ϵ) for each natural i.

Sample
The following diagram shows the prototypal completion of the instance-of sample. Blue links display the restriction of the class map to the set C.ce of prototypes, let it be denoted .ͼlass. The (unrestricted) .class map is inherited from .ͼlass The instance-of relation is given by (ϵ) = () (.class), or by (ϵ) = () (.ͼlass), or also by (϶) = (.ce) (≥). (In this particular case we do not need to distinguish between member-of and and instance-of.)
(JavaScript)

var r, c, A, B, s, u, v;
r = Object
c = Function
A = new c
B = new c; B.prototype.__proto__ = A.prototype
s = new A
u = new B; v = new B

The missing inheritance between classes:
A.__proto__ = c.__proto__ = r; B.__proto__ = A
Note that r.ce becomes the new inheritance root – the unique common ancestor of all objects (in contrast to r which is just a common root for non-zero metalevels).
In JavaScript
As of ECMAScript, 5th Edition, [] the JavaScript programming language provides a limited native support for object membership. The (ideal) structure is established by 3 (partial) maps between objects, .sc', .class, and .ce, given by object properties named __proto__, constructor and prototype, respectively. For an object x and a class y, The constructor property is owned by prototypes and inherited by other objects. In contrast, __proto__ and prototype are never (strictly) inherited. The __proto__ property is non-standard. When not supported, Object.getPrototypeOf(x) can be used for introspection. The instance-of relation can be introspected via the instanceof operator, except that y.prototype is not reported as an instance of y.

The Ruby conditions apply: single inheritance between objects and single metalevel for classes. In contrast to Ruby, Smalltalk or Objective-C, JavaScript does not support parallel metalevel hierarchies. Only inheritance between prototypes is supported, not between classes. This is why we wrote .sc' instead of just .sc. According to .sc', the inheritance parent of every class is c.ce (Function.prototype). However, the modification ()(') = () (C, <) has no impact to the instance-of relation: we still have (ϵ) = (') (.class) = (') (.ͼlass). There are two helix classes:

c = Function < Object = r.
Note that we wrote <, not <' which does not hold.

As the names constructor or Function suggest, JavaScript uses another terminology for the class map or the class set. In JavaScript, classes are constructors and also functions. Every constructor is a function. Functions are the Functions. Except for c.ce and for native built-in functions like eval or parseInt, every function is also a constructor. Being terminal instances of c, the native built-in functions account for the relaxation of (p~5). Another deviation from the canonical structure is caused by the built-in Function.prototype.bind method. A constructor x created using this method shares its instance prototype x.ce with the constructor to which x is bound (although x.ce is not obtained via x.prototype.)

The above description of the JavaScript native core structure is only valid under ideal circumstances which are not guaranteed by the ECMAScript standard. For example, the constructor or prototype properties can be almost arbitrarily manipulated. To ensure validity, additional restrictions have to be imposed on state transitions.

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. We introduce a two-step generalization motivated by the RDF Schema.[] [] The narrow definition can be characterized by the following features: Disallowing the above features leads to primary (canonical) structures. The broad definition further generalizes the narrow definition by only using those constraints that are imposed by RDFS axioms and entailments rules.
Narrow definition
By a primary ontological structure of ϵ we mean a structure (Ō, ϵ, , r, c, p) with a similar terminology, notation and axioms as canonical primary structures. The differences are as follows. p is a distinguished object whose instances are called properties. We denote P the set of all properties. The set T of terminal objects equals Ō (C P). The structure is then subject to the following axioms:
(o~1) Inheritance, , is a preorder.
(o~2) (a) (ϵ) () (ϵ) and (b) () (ϵ) (ϵ).
(o~3) (a) Only classes can have instances. (b) Terminals have no strict descendants.
(o~4) Helix classes are (a) totally pre-ordered by , and (b) instances of each other.
(o~5) Metaclasses can only have classes as instances.
(o~6) Every non-helix object is well-founded w.r.t. ϵ.
(o~7) (a) Ō = r.϶. (b) C.ϵ c. c..
(o~8) The set C of classes is finite.
(o~9) c is a least helix class.
(o~10) p is a class not from c. c..

Notes and observations:

  1. Non-equivalence of r and c is asserted by (o~10).
  2. Condition (o~7) is a weakening of the class map axiom (p~7). It asserts that (a) every object has a container, and (b) only helix classes or metaclasses can have classes as instances.
  3. Condition (o~10) asserts disjointness of classes and properties so that Ō = T P C.
  4. Primary (canonical) structures (equipped with a pointed class p) are the primary ontological structures such that
Broad definition
By the broad definition, a RDFS core structure is a structure (Ō, ϵ, ≤C, ≤P, r, c, p) where Ō is the set of objects or resources, ϵ, C, and P are the instance-of, subclass-of and subproperty-of relations on Ō, respectively, and r, c, and p are distinguished objects. Instances of c form the set C of classes, instances of p form the set P of properties. The structure is subject to the following conditions:
(r~1) The subclass-of relation, C, is a preorder on C.   (rdfs10) and (rdfs11)
(r~2) The subproperty-of relation, P, is a preorder on P.   (rdfs5) and (rdfs6)
(r~3) The subsumption rule applies: (ϵ) (≤C) (ϵ).   (rdfs9)
(r~4) Only classes can have instances.
(r~5) Every object is an instance of r.
(r~6) Every class is a subclass of r.   (rdfs8)
(r~7) The objects r, c and p are pairwise distinct.
(r~8) The set C P is finite.
(r~9) p is a class.
The narrow definition is obtained from the broad one by defining the inheritance relation as the reflexive closure of (≤C) (≤P) and making the following assertions: (o~2)(b): () (ϵ) (ϵ), (o~4): helix classes are …, (o~6): well-foundedness of ϵ on non-helix objects, (o~7)(b): C.ϵ c. c., (o~9): c is a least helix class, and (o~10): p is not from c. c..
Built-in RDFS core
The built-in RDFS core structure is an RDFS core structure (Ō, ϵ, ≤C, ≤P, r, c, p) shown by the following diagram. We consider the set Ō to be equal to the RDF(S) vocabulary [], so that objects are URI names. Let be the reflexive transitive closure of green links (implicitly directed upwards). The ϵ relation is obtained as () R () where R is the relation shown by blue links. Subsequently, P and C are the restrictions of to p.϶ and c.϶, respectively.
ϵ rdf:type
‹≤P rdfs:subPropertyOf
‹≤C rdfs:subClassOf
r rdfs:Resource
c rdfs:Class
p rdf:Property
Note that the structure is fairly regular. It has single inheritance and single classification, yielding the .class map. The only feature not allowed in canonical structures is strict inheritance between objects that are not descendants of r. Similarly to the Python programming language, there is a minimal non-degenerate chain of 2 helix classes:
c = rdfs:Class < rdfs:Resource = r.
In addition to c, there is a second built-in metaclass, rdfs:Datatype.

Note: The diagram shows the built-in structure according to RDF 1.1 Semantics [] which adds rdf:HTML and rdf:langString as 2 new built-in instances of rdfs:Datatype to the previous 2004 version [].

Interpretation by RDF graphs
In RDF Schema, data structures are encoded via RDF graphs. By an RDF graph we mean a structure (Ō, Ψ) such that Ō is set of objects and Ψ is a subset of Ō3 = Ō × Ō × Ō. Elements of Ō3 are triples of objects. For a triple t = (s,p,o), s is the subject, p is the predicate, and o is the object of t. The relational extent of p Ō is denoted p.rel and defined as the set {(s,o) | (s,p,o) Ψ}.

We can now define an RDFS core graph as an RDF graph (Ō, Ψ) such that the following holds:

Since every object appears as a subject in some triple, an RDFS core graph is completely given by its set of triples. The built-in RDFS core graph is the minimum set of triples. Any RDFS core graph is obtained by (explicitly) adding new triples and subsequently applying entailment rules – the presence of some triples entails the presence of other triples.

There are entailment rules that refer to distinguished objects not considered in the above description. (In particular, the rdfs:domain and rdfs:range properties.) As a consequence, some of our RDFS core graphs are in fact not allowed by RDF Schema. However, RDF Schema still only guarantees the conformance to the broad definition of ontological structure of ϵ. None of (o~2)(b), (o~4), (o~6), (o~7)(b)[], (o~9), or (o~10) is asserted.

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 []. However, no conditions from the difference between narrow and broad structures are asserted.
Built-in structure
The built-in structure contains additional 58 classes and 62 properties []. There are 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. There is still single inheritance between non-equivalent objects other than owl:Nothing. Single classification is not preserved (not even up to equivalence) due to common instances of owl:AnnotationProperty and owl:OntologyProperty.

The restriction of inheritance to RDF(S) vocabulary is the same as inheritance in the built-in RDFS core structure. The restriction of instance-of is almost the same: the rdfs:Literal class is made an instance of rdfs:Datatype by a single additional axiomatic triple [].

Powertypes

The interplay between inheritance, , and membership, ϵ, provided by the powerclass map, .ec, and expressed by has been investigated in type-theoretic setting by Luca Cardelli []. Let us focus just on the structure induced by the typing relation and the power type operator. Then, if we denote = r.ec, the following correspondence can be established:
This document Type-theoretic setting []
Terminology Notation Notation Terminology
Inheritance / / <: Subtyping
Object membership ϵ : Typing
Powerclass map .ec Power() Power type operator
Terminal objects T Values
Non-terminal objects .϶ Types
Top of metalevel 2 Type Type of types

Notes:

  1. In [], the symbol is used for subtyping. The table shows also two other symbols that are common in the literature.
  2. The correspondence between inheritance (as defined in this document) and subtyping should be taken in the restriction to non-terminal objects. A value is usually not considered to be a subtype of itself.
In the specialized document [], Cardelli's six typing rules are distinguished (those that can be expressed by just :, Power() and Type) to form an abstract power type system (O, ϵ, .ec, ). Subsequently, additional conditions are provided so that the resulting family of structures is definitionally equivalent to basic structures of ϵ such that x.ec is defined exactly for non-terminal objects x.
Powertypes in metamodelling
The Cardelli's notion of power types has been adopted by J. Odell in the field of metamodelling []. However, whereas Cardelli's power type is an abstraction of powerset, Odell's power type is an abstraction of a non-trivial partition. In particular, in metamodelling,
  1. a type can have more than one power type, and
  2. there is no typing relation (instance-of) between a type and its power type.
Since for every sets x, y, y being a non-trivial partition of x is a special case of x being a non-member union of y, the semantic shift can be diagrammatized by where .' is a distinguished subrelation of the non-member union map ..

 

References
Martin Abadi, Luca Cardelli, A Theory of Objects, Springer Science & Business Media 1996, http://lucacardelli.name/theoryofobjects.html
James Althoff, [Python-Dev] Classes and Metaclasses in Smalltalk , 2001, https://mail.python.org/pipermail/python-dev/2001-May/014508.html
Giuseppe Attardi, Cinzia Bonini, Maria Rosario Boscotrecase, Tito Flagella, and Mauro Gaspari, Metalevel Programming in CLOS, In ECOOP, vol. 89, 1989, http://www.ifs.uni-linz.ac.at/~ecoop/cd/papers/ec89/ec890243.pdf
Daniel Bobrow, Gregor Kiczales, The common Lisp object system metaobject kernel: a status report, Proceedings of the 1988 ACM conference on LISP and functional programming, ACM 1988,
Daniel Bobrow, Mark Stefik, The LOOPS Manual, Xerox Corporation 1983,
Grady Booch, Robert A. Maksimchuk, Michael W. Engel, Bobbi J. Young, Jim Conallen, and Kelli A. Houston, Object-oriented analysis and design with applications, Vol. 3, Addison-Wesley 2008,
Ronald J. Brachman, What IS-A is and isn't: An analysis of taxonomic links in semantic networks, Computer 16.10, North-Holland 1983,
Kim B. Bruce, Foundations of Object-Oriented Programming Languages: Types and Semantics, MIT Press 2002,
Jean-Pierre Briot, Pierre Cointe, The OBJVLISP Model: Definition of a Uniform, Reflexive and Extensible Object Oriented Language, European Conference on Artificial Intelligence (ECAI'86), Advances in Artificial Intelligence-II, North-Holland 1986,
Jean-Pierre Briot, Pierre Cointe, A Uniform Model for Object-Oriented Languages Using the Class Abstraction, Tenth International Joint Conference on Artificial Intelligence (IJCAI'87), 1987,
Luca Cardelli, Structural Subtyping and the Notion of Power Type, Proc. of the 15th ACM Symp. on Principles of Programming Languages, POPL'88, 1988, http://www.daimi.au.dk/~madst/tool/tool2004/papers/structural.pdf
C. C. Chang, H. Jerome Keisler, Model Theory, Studies in Logic and the Foundations of Mathematics (3rd ed.), Elsevier, 1990,
David Chisnall, Cocoa Programming Developer's Handbook, Addison Wesley 2009,
Pierre Cointe, Metaclasses are First Class: the ObjVlisp Model , Proceeding OOPSLA '87 Conference proceedings on Object-oriented programming systems, languages and applications , North-Holland 1987,
Damian Conway, Object Oriented Perl, Manning Publications, 2000,
Mohamed Dahchour, Alain Pirotte, Esteban Zimányi, Definition and Application of Metaclasses, Proceedings of the 12th International Conference on Database and Expert Systems Applications, Springer-Verlag 2001, http://cs.ulb.ac.be/publications/P-01-01.pdf
Ecma International, ECMAScript Language Specification, Edition 5.1, http://www.ecma-international.org/ecma-262/5.1/
(eigenclass.org admin), The double inclusion problem, 2005, http://eigenclass.org/hiki/The+double+inclusion+problem
David Flanagan, JavaScript: The Definitive Guide, Sixth Edition, O'Reilly 2011
Neal Feinberg, Sonya E. Keene, Robert O. Mathews, and P. Tucker Withington, Dylan Programming: An Object-oriented and Dynamic Language, Addison Wesley 1996 opendylan.org/books/dpg/
Ira R. Forman, Scott H. Danforth, Putting Metaclasses to Work, Addison Wesley 1998
Ira R. Forman, Nate Forman, Java Reflection in Action, Manning Publications 2005
Cesar Gonzalez-Perez, Brian Henderson-Sellers, A powertype-based metamodelling framework, Software & Systems Modeling 5.1 2006
Daniel Ingalls, The Smalltalk-76 programming system design and implementation, Proceedings of the 5th ACM SIGACT-SIGPLAN symposium on Principles of programming languages, ACM, 1978
IPA Ruby Standardization WG, Ruby Draft Specification, 2010, https://www.ipa.go.jp/osc/english/ruby/
Andri Joyal, Ieke Moerdijk, Algebraic set theory, Cambridge University Press 1995
John L. Kelley, General Topology, Springer 1975
Seiji Koide, Hideaki Takeda, OWL-Full Reasoning from an Object Oriented Perspective, The Semantic Web–ASWC 2006 Springer 2006 http://www-kasm.nii.ac.jp/papers/takeda/06/koide06aswc.pdf
Timothy C. Lethbridge, Robert Laganiere, Object-oriented software engineering, McGrawhill Education 2005
Mark Lutz, Learning Python, O'Reilly 2009
Aimilia Magkanaraki, Sofia Alexaki, Vassilis Christophides, and Dimitris Plexousakis, Benchmarking RDF Schemas for the Semantic Web, ISWC, 2002, http://www.ics.forth.gr/isl/publications/paperlink/iswc02.pdf
Satoshi Matsuoka, Akinori Yonezava, Metalevel solution to inheritance anomaly in concurrent object-oriented languages, Proceedings of the ECOOP/OOPSLA'90 Workshop on Reflection and Metalevel Architectures in Object-Oriented Programming 1990
Satoshi Matsuoka, Language Features for Re-Use and Extensibility in Concurrent Object-Oriented Programming Languages, 1993
Linda G. DeMichiel, Richard P. Gabriel, The common lisp object system: An overview, ECOOP'87 European Conference on Object-Oriented Programming 1987
Oscar Nierstrasz, Stéphane Ducasse, Damien Pollet, Pharo by Example, Square Bracket Associates 2009, http://pharobyexample.org
James J. Odell, Power Types, Journal of Object-Oriented Programming 7.2 1994
OMG, OMG UML Superstructure 2.4.1, Object Management Group 2011
Jari Palomäki, Hannu Kangassalo, That IS-IN Isn't IS-A: A Further Analysis of Taxonomic Links in Conceptual Modelling, 2012
Ondřej Pavlata, The Ruby Object Model: Data Structure in Detail, 2012, http://www.atalon.cz/rb-om/ruby-object-model
Ondřej Pavlata, The Ruby Object Model: S1 superstructure representation, 2012, http://www.atalon.cz/rb-om/ruby-object-model/s1-rep/
Ondřej Pavlata, Ruby Object Model – The S1 structure, 2012, http://www.atalon.cz/rb-om/ruby-object-model/rb-om-s1.pdf
Ondřej Pavlata, The Ruby Object Model: Comparison with Smalltalk-80, 2012, http://www.atalon.cz/rb-om/ruby-object-model/co-smalltalk/
Ondřej Pavlata, Object Membership: The Core Structure of Object-Oriented Programming, 2012–2015, http://www.atalon.cz/om/object-membership/oop/
Ondřej Pavlata, Object Membership: The ontological structure, 2012, http://www.atalon.cz/om/object-membership/ontology/
Ondřej Pavlata, Object Membership – Basic Structure, 2015, http://www.atalon.cz/om/object-membership/basic/
Ondřej Pavlata, Object Membership: Simplified Structure, 2015, http://www.atalon.cz/om/object-membership/simple/
Ondřej Pavlata, The Dialectic of Classes and Metaclasses in Smalltalk-80, 2015, http://www.atalon.cz/om/smalltalk/dialectic/
Ondřej Pavlata, Object Membership with Prototypes, 2015, http://www.atalon.cz/om/object-membership/prototypes/
Ondřej Pavlata, Object Membership and Powertypes, 2015, http://www.atalon.cz/om/object-membership/powertypes/
Guiseppe Peano, Arithmetices principia: nova methodo, Fratres Bocca 1889, https://archive.org/details/arithmeticespri00peangoog
Keith Playford, Dylan Enhancement Proposal: Subclass, Dylan Hackers 1995, http://opendylan.org/proposals/dep-0005.html
Reza Razavi, Noury Bouraqadi, Joseph Yoder, Jean-François Perrot, Ralph Johnson, Language support for Adaptive Object-Models using Metaclasses , Computer Languages, Systems & Structures, 31(3) 2005,
Nathanael Schärli, Traits: Composing Classes from Behavioral Building Blocks, 2005, http://scg.unibe.ch/archive/phd/schaerli-phd.pdf
Andrew Shalit, Jeffrey Piazza and David Moon, Dylan, an object-oriented dynamic language, Apple Computer Inc 1992,
Guy L. Steele, Common LISP: the language, Digital press 1990,
David Ungar, Randal B. Smith, Self: The power of simplicity, Vol. 22. No. 12. ACM, 1987,
World Wide Web Consortium, OWL 2 Profiles, 2009, http://www.w3.org/TR/owl2-profiles/
World Wide Web Consortium, OWL 2 RDF-Based Semantics, 2009, http://www.w3.org/TR/owl2-rdf-based-semantics/
World Wide Web Consortium, RDF Schema, 2004, http://www.w3.org/TR/rdf-schema/
World Wide Web Consortium, RDF Semantics, 2004, http://www.w3.org/TR/2004/REC-rdf-mt-20040210/
World Wide Web Consortium, RDF 1.1 Semantics, 2014, http://www.w3.org/TR/2014/REC-rdf11-mt-20140225/
World Wide Web Consortium, RDF Vocabulary Description Language 1.0: RDF Schema, 2004, http://www.w3.org/TR/2004/REC-rdf-schema-20040210/
World Wide Web Consortium, Terse RDF Triple Language, 2014, http://www.w3.org/TR/turtle/
Wikipedia: The Free Encyclopedia, http://wikipedia.org
Browser compatibility browser-compatibility
To be viewed correctly, this document requires advanced browser features to be supported, including
Document history
August242012 The initial release of the original document [].
March122015 The original document [] moved to ./oop/ and became subsidiary.
March172015 Spelling corrections, url link corrections (in some cases, the fragment identifier # was missing).
March242015 Introduced symbol 𝕍. The Membership glyphs subsection added.
April82015 A PDF version added. Some accompanying styling changes made.
License
This work is licensed under a Creative Commons Attribution-NonCommercial-ShareAlike 3.0 License.