Object Membership

The core structure of object-oriented programming

An abstract structure is described that forms a generalization of object model core for class-based programming languages. Considered are Ruby, Python, Java, Scala, Smalltalk, Objective-C, CLOS and Perl. The structure is built around a single relation between objects, denoted ϵ and called object membership. This relation can be viewed as a counterpart to , the set membership as known from set theory.

As a result, the document provides a uniform and consistent view of an essential part of the foundations of object oriented programming.

Preface

Author
Ondřej Pavlata
Czech Republic
Document date
Initial releaseAugust 24, 2012
Last major release March 12, 2015
Last updateMarch 12, 2015
(see Document history)
Disambiguation
The object membership relation ϵ that is the subject of this document is a generalization of the instance-of relation. It should not be confused with other kinds of membership between objects, in particular, with the following relations: We can write ϵ-membership to distinguish the ϵ-sense of object membership from other uses.
Warning
  1. This document has been created without any prepublication review except those made by the author himself.

Table of contents

Introduction

Note: For a more detailed introduction into the subject see [].


The objective of this document is to provide abstract description of the fundamental part of data model of object-oriented programming (OOP). By fundamental part we mean a structure that encompasses the following fundamental relations: Before providing precise definitions we call such a structure an instance–inheritance structure. Encompassing the instance relation implies that we are concerned with class-based programming languages.

The goal is to introduce a common mathematical structure such that for most class-based languages, there is a correspondent part of the data model that forms a special case. Such a common mathematical structure would provide a uniform and consistent view of foundations of OOP.

To specify the universe on which the structure is defined, we follow the well-known OOP guideline:

Everything is an object.
This means that entities of the universe are objects (so that we can use the term object model instead of data model). In particular, both the inheritance and instance relations are relations between objects. The following picture shows an instance–inheritance structure with 5 objects, denoted Any, Object, Class, Int and i.
  • … class
  • … terminal
  • … direct inheritance-descendant-of
  • … direct instance-of  (the class map)
  • … inheritance
  • … instance-of
The green and blue links in the diagram do not directly correspond to the inheritance and instance relations. Instead, they are their constituents: The diagram also displays basic nomenclature of objects which can be obtained as follows: The structure corresponds to the following Scala code:
var    Any = classOf[Any]
var Object = classOf[Object]
var  Class = classOf[Class[_]]
var    Int = classOf[Int]
var      i = 7
assert (Object.isAssignableFrom(Class))
assert(!Object.isAssignableFrom(Int))
assert ( Class.isInstanceOf    [Object])
assert (   Int.isInstanceOf    [Object])
assert (     i.isInstanceOf    [Int])
assert (     i.isInstanceOf    [Any])
//assert(   !i.isInstanceOf    [Object])   // not supported
assert (i.getClass          == Int)
assert (i.getClass.getClass == Class)
println (if (Object == Any) "???" else "OK")  // ???
The code also shows that in Scala, there is some indirection in support of the Everything is an object pattern. In particular: Both kinds of obstruction can be seen in Java and notational duality also in Objective-C and CLOS. We regard these features as mere inconveniencies for users who are interested in programming language concepts. Such features do not constitute reasons why not to treat language data entities in a uniform manner.
Name resolution
In a program, the instance–inheritance structure is used for name resolution. Informally, given a receiver object a and a name s the task is to determine the value of the possibly inherited property of a named (by) s. As a subtask, the owner object y has to be determined that interprets s – i.e. y is an object that owns an s-named binding to the requested target value. In a simplified form, the subtask is performed in two steps:
  1. (1) (Use the instance relation.)
    Determine the lookup start point – the object x whose (non-strict) inheritance ancestors should be taken into consideration.
  2. (2) (Use the inheritance.)
    Determine the target owner y. First, let Y be the set of all inheritance ancestors of x that contain (own) an s-named binding.
In (1) the startpoint x is obtained by (a) zero or (b) one application of the class map.

In step (2), if we denote y = x.owner(s) then for each name s, the .owner(s) map is a partial closure operator in inheritance. (By partial we mean a restriction to the set of objects that have an ancestor with an s-named binding.) However, the existence of such an operator is only guaranteed for single inheritance – i.e. when the inheritance relation is a forest. In general, additional structure is required that equips every ancestor set with a linear order.

Eigenclass completion
Following the Ruby object model, we describe the instance–inheritance structure in its eigenclass completion. This means that part of the structure is the eigenclass map, .ec, between objects which induces infinite eigenclass chains x, x.ec, x.ec.ec, . These chains provide conceptual counterpart for infinite regress. Naturally, only a finite front substructure can have an in-memory representation, so that eigenclasses are mostly fictitious: Beside providing uniform structural view both for languages with and without (direct) eigenclass support, eigenclass completion has another interesting benefit:
The composition of the eigenclass map with the inheritance relation is uniquely decomposable.
As a consequence, the instance—inheritance structure (in its basic form S1ϵ) can be induced from a single relation which we call object membership and denote ϵ. This terminology and notation suggests a parallel with the set membership relation, , known from set theory.
The metaclass puzzle
In the literature [] [], metaclasses are defined as There are 2 problems with these definitions. First, the definitions are not correct from the logical point of view. In the (a) case, all classes without instances would pass the definition (so that they become metaclasses by vacuous truth). In the (b) case, metaclasses without instances would not pass the definition.

The second, more serious, problem consists in the requirement that metaclasses are classes. Consider the following Ruby code:

class A; end
p     A.class                      # Class
(class B < Class; end) rescue p $! #... can't make subclass of Class
Using the (b) definition, we could conclude that in Ruby, there is one and only one metaclass: the Class class. However, since the Ruby object model is in tight correspondence with the Smalltalk-80 object model (regarding the instance–inheritance structure) we would obtain the following paradox:
Except for the Class class, Smalltalk has no metaclasses.   ()
This would be in a contradiction with all documents about the Smalltalk-80 object model.

We provide a solution to the above problems by proposing a new definition of a metaclass:

In (3), inheritance descendant is meant in the non-strict sense – including the metaclass root itself. Metaclasses that are (resp. are not) classes are called explicit (resp. implicit). The paradox () then turns into the statement that except for the Class class, Smalltalk has no explicit metaclasses.

The definition applies directly to all of Ruby, Python, Scala, Java, Smalltalk and CLOS, although in the case of the latter two languages care must be taken as to what is meant by class of in (2). Unfortunately, the introspection methods class (in Smalltalk) and class-of (in CLOS) are misleading here.

For Objective-C and Perl we have to use a modified definition due to the multiplicity and degeneracy of metaclass roots:

This definition applies to all eight languages but is not so appealing in cases where eigenclasses are purely fictitious.

Preliminaries

For preliminary definitions and notational conventions see [] [] [].

Overview of introduced structures

The following table provides a summary of language support for features that are related to object membership.
Languages → Ruby Python Smalltalk Objective-C Scala Java CLOS Perl
 Supported features ↓
S1 Explicit metaclasses
Implicit metaclasses
Eigenclasses of terminal objects
Eigenclasses of eigenclasses
Multiple inheritance
Terminal mixins
Non-terminal mixins
Multiple roots
Degenerated root(s)
Additional twist links
Imposed class map
Non-linear helix
Circular classes
Described by structure S1r S1p S1m+w+r S1c S1s S1 S1@
S2 Linearization
Described by structure S2r S2p S1m+w+r S1c S2s S1s S2 S2@

Notes:

  1. By explicit metaclasses here we mean explicit metaclasses other than metaclass root(s). For Python and CLOS it also means support for user-created explicit metaclasses. The ○ symbol for Perl indicates that Perl's classes become metaclasses by universal circularity.
  2. Regarding multiple inheritance, the ○ symbol indicates inclusion of terminal mixins, which establish a one-to-many includer-includee relationship. The ◐ symbol indicates twofold inheritance: the mixin part allows multiple parents, the class part forms a single inheritance.
  3. By terminal mixins we mean Ruby modules or Smalltalk traits. These are terminal objects that are indirectly involved in inheritance – in particular, being terminal objects, they are NOT descendants of the inheritance root.
  4. By non-terminal mixins we mean Java interfaces or Scala traits. These class-like objects are distinct from classes but are directly involved in inheritance – in particular, they are descendants of the inheritance root.
  5. Multiple roots means that there can be more that one class without inheritance parent(s). The ○ symbol for Smalltalk indicates that in Smalltalk-80 (as implemented by Pharo or Squeak), there are multiple classes without ancestors but only a single main root. The subsidiary roots arise from additional twist links.
  6. By a (front) twist link we mean a pair (x,c) where c is the metaclass root and x is a direct descendant (child) of c. By standard, there is exactly one such x, namely the eigenclass of the inheritance root. However, in both Pharo and Squeak, an additional twist link exists.
  7. By a degenerated root we mean an inheritance root that is its own class. (Equivalently, it is an inheritance root that is a parent of its eigenclass.)
  8. The imposed class map feature can be equivalently characterized as a support for a class map with monotonicity breaks w.r.t. inheritance. That is, it is possible that for some objects x, y, x is a descendant of y but the class of x is not a descendant of the class of y.
  9. Non-linear helix means that there is multiple inheritance (even) between helix classes (ancestors of the metaclass root).
  10. The circular classes feature means that in addition to helix classes there are other classes that are its own instances.
  11. S2 structures are the correspondent S1 structures equipped with linearization.
The table also indicates that we will not introduce a single general structure covering all features relevant to object membership. Instead, we present variants that could eventually be combined. The following diagram shows specialization relationship between (most of) the introduced structures. The S1p structure is the most special of the structures displayed.
Language versions
The following table shows programming language versions to which this document should be relevant.
  Ruby Python Smalltalk Objective-C Scala Java CLOS Perl
Implementation platform MRI CPython Pharo GNUStep JRE CLISP Strawberry
Version 1.9.2 3.2.2 1.3 0.29.1 2.10.0 1.7.0 2.49 5.16.1

S1p: The canonical structure of object membership

The canonical structure of object membership is a Python-like generalization of the Ruby S1 structure [] [].

An S1p structure is a structure (O, .ec, .pr, , r, c) where

Additional notation and terminology is applied:
The structure is subject to the following axioms:
(S1p~1) (O, .ec, .pr) is a primorder algebra.
We will apply established notation and terminology, in particular, definition of .ce and .eci.
(S1p~2) The inheritance is a partial order on O such that
  • r is the highest non-terminal object (the top of O T),
  • terminals are minimal, i.e. they have no strict descendants.
(By the original definition, T = O.pr r.. Now by (S1p~2), T = O r..)
(S1p~3) For every objects x, y,
  • x < y   iff   x.ec < y.ec.
Equivalently, (using injectivity of .ec,) the eigenclass map .ec is an order-embedding of (O, ) into itself.
(S1p~4) For helix objects, the following holds:
  • (a) The set H.pr of helix classes forms a chain in inheritance
  • (b) c and r are different classes.   (So that c is the bottom helix class and r is the top.)
  • (c) For every helix objects x, y,
    • x.eci < y.eci   implies   x > y.
  • (d) For every object x and each i ≥ 0,
    • x < c.ec(i)   implies   x r.ec(i+1).   (Therefore, r.ec(i+1) is the only child of c.ec(i).)
(S1p~5) For every class x and every eigenclass e,
  • if x < e then e is a helix object.
(S1p~6) The set O.pr of primary objects forms a closure system in the inheritance .
Let .c denote the corresponding closure operator, i.e. for a non-terminal object x, x.c is the least class y such that x y. (For a terminal x, x.c = x.)
Let .class denote the composition .ec.c (and .class(i) its i-th application, i ≥ 0).
(S1p~7) For every object x,
  • x.c.ec x.ec.c   (equivalently, x.c.class = x.class).
(S1p~8) For every non-helix class x and every i > 0,
  • x.ec(i) x.
(S1p~9) The set C of classes is finite.
A sample structure
The following diagram shows a sample S1p structure from the side view.
Full structure Restriction to primary objects
Inheritance Instance tree
Legend
  • … helix class
  • … non-helix class
  • … terminal
  • … eigenclass
  • … inheritance
  • … the .ec map
  • … the .class map
The next diagram shows a slightly different structure that has identical restriction to primary objects (i.e. the substructure (O.pr, , .class) is the same). This structure satisfies condition (S1p~5⁺) which strenghtens (S1p~5) by stating that r.ec is the only eigenclass that can have class descendants, thus disallowing M < r.ec(2).
Corresponding Python code:

class M(type): pass
class N(type, metaclass=M): pass
class A(metaclass=N): pass
class B(A): pass
b = B()
Examples of disallowed structures
The following diagrams show sample cases that are disallowed by particular conditions.
By (S1p~3)
(ⅰ)
¬(S1p~3): b.ec < r.ec
(ⅱ)
¬(S1p~3): A.ec < b.ec
(ⅲ)
¬(S1p~3): b.ec(1) < b.ec(2)
By (S1p~4) and (S1p~5)
(ⅰ)
¬(S1p~4)(d): r.ec A < c
(ⅱ)
¬(S1p~5): B < A.ec
By (S1p~6)
(ⅰ)
¬(S1p~6): B.class is undefined

class M(type): pass
class N(type): pass
class A(metaclass=M): pass

#  metaclass conflict
class B(A,metaclass=N): pass
(ⅱ)
¬(S1p~6): B.class is undefined
By (S1p~7)
(ⅰ)
¬(S1p~7):
A.class.class A.ec.class
(ⅱ)
¬(S1p~7):
N.class.class N.ec.class
(ⅲ)
¬(S1p~7):
N.class.class N.ec.class
By (S1p~8)
(ⅰ)
¬(S1p~8): M.ec < M
(ⅱ)
¬(S1p~8): M.ec < M
(ⅲ)
¬(S1p~8): M.ec(2) < M
The member-of relation ϵ
The relation of object membership is denoted ϵ and is defined as the composition .ec , i.e. for objects x, y If x ϵ y then x is said to be a member of y. We might also use the term container-of for the inverse relation. For an object x, we denote x.϶ the set of all members of x.

Proposition:

(1) For every objects x, y,
  • x y   iff   y ϵ a implies x ϵ a for every object a.
(2) For every objects x, y,
  • x.ec = y   iff   x ϵ y z for every object z such that x ϵ z.
(3) An object is terminal if it is both maximal and minimal in .
(4) The inheritance root r is the unique object that is maximal in but not minimal.

Corollary: An S1p structure is fully determined by the ϵ relation.

Note: In the sequel we provide alternative axiomatization of S1p structures based on the ϵ relation.

The instance-of relation
The instance-of relation is defined as the range-restriction of object membership to classes (which can be written as (ϵ) (O × C)) i.e. for objects x, y, Instances of a class named X are referred to as Xs. An instance of X is said to be an X.

Observations:

  1. The instance-of relation equals the following compositions:
  2. If {c} = c. O.ec (i.e. c is the only explicit metaclass) then the instance-of relation equals (.class) ().
  3. If Class is the name of the metaclass root c then Classes is synonymous to non-terminal objects (i.e. classes and eigenclasses).
The .class map
The .class function maps objects to classes. As already introduced in (S1p~6) it is defined as the composition .ec.c, i.e. for every object x, If x.class = y, then y is the class of x and x is a direct instance of y. This reflects the fact the .class map, as a relation, is a subset of the instance-of relation which is in turn a subset of ϵ. This is summarized by the following table.
Notation Composition Terminology y restricted to
ϵ (ϵ) (Μ) x kind-of y C, O.ec, T m.϶
ϵ (.ec) () x member-of y C, O.ec
(ϵ) (.c) x instance-of y C
.class (.ec) (.c) x direct-instance-of y
(the class of x is y)
C
The kind-of relation ϵ is introduced later as a generalization of object membership ϵ. Eelements of T m.϶ are called modules. For the meaning of Μ and m, see Terminal mixins.
Derived properties

Proposition A:

(1) Assuming just (S1p~1)(S1p~6), the condition (S1p~7) is equivalent to
(S1p~7') The compositions .class.class and .ec.class are identical, i.e. for every object x,
  • x.class.class = x.ec.class.
(2) For every object x,
  • x.c = x.pr.class(x.eci).
(3) For every object x,
  • x.class = x.pr.class(x.eci+1).
(3') For every object x and every i ≥ 0,
  • x.ec(i).class = x.class(i+1).
(4) Let x, y be objects such that x H iff y H. Then
  • x y   implies   x.eci ≥ y.eci.
(5) The inheritance is upper finite, i.e. every object has finite number of ancestors.
(6) Every non-helix eigenclass chain is an antichain in inheritance.
(7) The set of helix objects forms an up-set in inheritance. (I.e. if x < y and x is a helix object then so is y.)
(8) The set of non-helix eigenclasses forms a down-set in inheritance.
(9) Let be a relation between primary objects defined by
  • x y   iff   x.ec(i) y.ec(j) for some i, j ≥ 0.
Then is a preorder on primary objects such that the restriction (O.pr H, ) to non-helix objects is a partial order. The set H.pr of helix classes is the top, i.e.
  • () = (O.pr H, ) (O.pr × H.pr).

Proposition B: Assume just (S1p~1)(S1p~7). Then the following are equivalent:

(i) (S1p~8).
(ii) The .class map forms a tree such that c is the root. Equivalently, for every class x,
  • x.class(i) = c   for some i ≥ 0.
(ii') For every class x and every i ≥ 0,
  • x.class(i+1) = x   implies   x = c.
(iii) The following is satisfied:
  • The .class map forms a tree.
  • The set of helix objects forms an up-set in inheritance.
(iv) For some helix object h,
  • h. is disjoint with x. for every non-helix class x.
(Equivalently, instances of non-helix classes only occur in finitely many metalevels.)

Proof:
(i)→(ii')
We first show that

Denote y = c.class and assume y c, i.e. c.ec < y < r.ec < c. Applying .ec, we obtain thus y.ec < y, a contradiction with (i).
Let x be a helix class. From x.ec < c we obtain we obtain x.class = x.ec.c c. From c x we obtain c = c.class x.class. Taken together, it yields x.class = c.

Let x.class(i) = x for some i > 0. Since x.class(i) = x.ec(i).c we have x.ec(i) < x, thus x must be a helix class. But x.class = c for every helix class so that x = c.
(ii')→(i)
Assume x.ec(i) < x for some class x and i > 0. Denote y = x.ec(i).c. Then

which implies y.ec(i) x.ec(i) < y, therefore y.ec(i).c = y, i.e. y.class(i) = y. This means that y = c and x is a helix class.
The helix
The restriction of an S1p structure to the set H of helix objects is shown in the following diagram. In this case, the set H.pr contains 4 helix classes, just like in Ruby.

Proposition:

  1. An object is a helix object iff it is its own member   (x H iff x ϵ x).
  2. An object is a helix class iff it is its own instance.
  3. (H, ) is a linear order.
  4. H forms the smallest non-empty substructure of (O, .ec, .parents).
  5. (H, ϵ) is an S1p structure (that equals its own helix).
  6. The set H of helix objects forms a closure system in (O T, ), i.e. for every non-terminal object x there is a helix object that is the least helix object between all ancestors of x. We denote .he the corresponding closure operator, x.he is the helix entry of x.
The reduced helix
We denote R = {r.ec(i) | i ≥ 0} the set of objects from the eigenclass chain of the inheritance root r. We call this distinguished subset of H the reduced helix.

Proposition:

  1. The reduced helix R forms a closure system in (O T, ). We denote .re the corresponding closure operator. For a non-terminal x, x.re is the metalevel root of x.
  2. Helix objects are exactly the ancestors of objects from H, i.e.

Metalevels

For a natural number i, let the i-th metalevel (or the metalevel of index i) be the set r.ec(i).϶ r.ec(i)., i.e. an object x belongs to the i-th metalevel iff x is a member of r.ec(i) but not a descendant of r.ec(i).

Observations:

For an object x, we denote x.mli the metalevel index of x, defined as the index of the metalevel to which x belongs, i.e.
The following diagram shows metalevels of the sample structure. In contrast to the previous diagrams, terminals are drawn one column left to the inheritance root r so that each column contains objects from the same metalevel.

Note: In the eigenclass alignment used before, terminals are drawn in the same column as the inheritance root r. This alignment is motivated by the situation when all descendants of r.ec are eigenclasses (i.e. there are no explicit metaclasses other than c) as is the case in Ruby. Each column then contains objects x with the same eigenclass index x.eci.

Metalevel separation
In general, an S1p structure allows non-helix connections between metalevels, as shown below.
 
class A: pass
class M(A,type): pass
class M(type): pass
class N(M,metaclass=M): pass
assert N.__class__ == M
Such cases are prevented by the following metalevel separation condition.
(S1p~sep) For every non-helix objects x, y,
  • x y    implies    x.re = y.re
i.e. non-helix objects comparable by inheritance are in the same metalevel.

Proposition A:

  1. The following are equivalent:
    1. The metalevel separation condition (S1p~sep).
    2. Except for T, metalevels are components of connectedness of the Hasse diagram (i.e. reflexive transitive reduction) of inheritance without twist links, i.e. without pairs (r.ec(i),c.ec(i-1)), i > 0.
  2. If (O, ) is a forest then (S1p~sep) is implicitly satisfied.
  3. Conditions (S1p~1)(S1p~7) together with (S1p~sep) imply (S1p~8).

Proposition B: Assume that the metalevel separation condition (S1p~sep) is satisfied.

  1. For every object x, In case (b) and (c) the metalevel index is incremented, i.e.
  2. The height of the instance tree is at most m + 1 where m is the maximum metalevel index of a class.

Metaclasses

An object is called a metaclass if it is an inheritance descendant of c. A metaclass is said to be

Note: The explicit/implicit terminology is redundant. We could use the primary/secondary terminology established in the 2x2 nomenclature of objects. [].

The following diagram shows metaclasses of the previously introduced sample structure. Objects that are not metaclasses are displayed in gray color. Note that there are 3 explicit metaclasses: c, M and N.

Observations:

  1. An object is a metaclass iff it either equals the metaclass root c or its metalevel index is at least 2.
  2. For an object x, the following are equivalent:
    1. x is not terminal.
    2. x.ec is a metaclass.
    3. x.class is a metaclass.

Generating substructures

The O.pr H substructure
The following proposition shows that non-helix eigenclasses can be obtained from the remaining structure using the .class map.

Proposition:

  1. For every object x, every class y and every i ≥ 0,
  2. For every primary objects x, y, and every i, j ≥ 0, the following are equivalent:

Corollary: Up to isomorphism, an S1p structure is uniquely given by (O.pr H, .pr, , .class).

The O.pr substructure
In general, an S1p structure cannot be recovered from its restriction to primary objects using the .class map. A stronger version of (S1p~5) is required that restrains the helix entry of explicit metaclasses:
(S1p~5⁺) For every class x and every (helix) eigenclass e,
  • x < e   implies   e = r.ec.
Equivalently, r.ec is the only eigenclass that is allowed to have classes as descendants. As a consequence, the metalevel index of a class is at most 2.

Proposition A: The following conditions are equivalent:

Proposition B: Assume that (S1p~5⁺) is satisfied. Then for every primary objects x, y, and every i, j ≥ 0, the following are equivalent:

Corollary:

Note: A standalone axiomatization of (O.pr, ϵ, ) / (O.pr, .class, ) is provided in a specialized section.

Transitions

Any S1p structure can be incrementally built from the helix structure by attaching eigenclass chains, one by one.
Object attachment
By an (object) attachment pair we mean a pair (P,q) such that and the following conditions are satisfied:
  1. (1) P is an antichain in inheritance.
  2. (2) P consists of zero or more classes and zero or one helix eigenclass. (P C {e} for some e H.ec.)
  3. (3) c P.pr.
  4. (4) q P.class.   (That is, q y for every y P.class.)

Proposition:

  1. For every primary object x (even a helix class),
  2. For every S1p structure S = (O, …) and an attachment pair (P,q) in S there exists an S1p structure S' = (O', …) such that Therefore, O' O equals the eigenclass chain whose primary object is x. Up to isomorphism, the extension S' is uniquely given by:
New (primary) object creation
The extension of S to S' from the previous subsection can be understood as a transition S S'. The structure is modified by adding a primary object x, together with its (fictitious) eigenclass chain, such that x is minimal in inheritance. This can be uniformly expressed as class instantiation: where q is the requested class and P = {p1, … pn} are the requested inheritance parents of x. The transition request is acceptable if and only if (P,q) is an attachment pair according to the previous subsection. After a successful transition, x is a new direct instance of q such that x.parents = P.

In the following Ruby code, new primary objects A and a are created.

class Object
  alias ec singleton_class
end
c = Class         # c refers to Class, the only explicit metaclass in Ruby
A = c.new(Object) # A is a new class - a subclass of Object
a = A.new         # a is a new terminal - a direct instance of A

c.new(c)    rescue puts $!.message  # can't make subclass of Class
c.new(A.ec) rescue puts $!.message  # can't make subclass of singleton class
A.ec.new    rescue puts $!.message  # can't create instance of singleton class
a.new       rescue puts $!.message  # undefined method `new' for #<A:0x8b48e0>
The last 4 lines show rejected transition requests. Neither c nor the eigenclass A.ec can be inheritance parents of a class. Neither A.ec nor a can have instances.

S1ϵ: Axiomatization via ϵ

As already stated before, S1p structures are completely determined by object membership, the ϵ relation. In this section, we provide a full ϵ-axiomatization.

By an S1ϵ structure we mean a structure (O, ϵ) where

If x ϵ y then x is said to be a member of y and y is said to be a container of x. Additional notation and terminology is applied:
The structure is subject to the following axioms:
(S1ϵ~1) Every object x has a unique smallest container, called the eigenclass of x, denoted x.ec, whose all ancestors are containers of x, i.e.
  • x ϵ y   iff   x.ec y   for every object y.
(S1ϵ~2) Distinct objects have distinct sets of containers, i.e. for every objects x, y,
  • x y x   implies   x = y.
Equivalently, is a partial order.
(S1ϵ~3) Terminals are minimal in inheritance, i.e. for every objects x, y,
  • if x T and y x   then   x = y.
(S1ϵ~4) Helix objects satisfy the following properties:
  • (a) There is an inheritance root r – the unique common ancestor of all non-terminal objects, i.e.
    • x T implies x r   for every object x.
  • (b) The eigenclass of r has at least 2 strict ancestors, i.e. for some object x,
    • r.ec < x < r.
  • (c) Helix objects are linearly ordered by inheritance, i.e. for every objects x, y from H,
    • either x y or y x.
  • (d) For every i > 0, the eigenclass r.ec(i) has no siblings, i.e. for every object x,
    • if x and r.ec(i) have a direct common ancestor then they are equal.
  • (e) Every helix descendant of r.ec is an eigenclass, i.e. for every helix object x,
    • x r.ec implies x O.ec.
(S1ϵ~5) Descendants of non-helix eigenclasses are eigenclasses, i.e. for every objects x, y,
  • x y O.ec H   implies   x O.ec.
(S1ϵ~6) Primary objects form a closure system in the inheritance, equivalently, for every object x there is a unique object, denoted x.class, such that
  • x ϵ y   iff   x.class y     for every class y.
(S1ϵ~7) For every object x,
  • x.ec.class = x.class.class.
(S1ϵ~8) Helix ancestors of descendants of non-helix classes are lower bounded, i.e. there exists a helix object h such that for every non-helix class x,
  • x. h. = .
(S1ϵ~9) The following finiteness conditions are satisfied:
  • (a) Every object has finite number of ancestors.
  • (b) The set C of classes is finite.
We also introduce (S1ϵ~5⁺) as an alias of (S1p~5⁺), i.e.
(S1ϵ~5⁺) An eigenclass different from r.ec can only have eigenclasses as descendants.

Proposition:

  1. Except for (S1ϵ~9), every axiom can be expressed as either a first-order sentence or a schema of first-order sentences.
    (An axiom schema is needed for (S1ϵ~4)(d) – the schema contains a single sentence for each i.)
  2. Axiom (S1ϵ~7) can be expressed without a reference to the .class map as follows:
    (S1ϵ~7') For every object x,
    • x.ec.ec. C   =   (x.ec. C).ec. C.
    Equivalently, for every class y, a member of an instance of y is also an instance of an instance of y.
Derived properties
(1)
For every objects x, y,
  • x ϵ y.ec   iff   x y   iff   x.ec y.ec.
In particular, .ec is an order embedding of (O, ) into itself. In particular, .ec is injective.

Proof: The implication x ϵ y.ecx y is shown by the diagram on the right. Assume x ϵ y.ec and let a be a container of y, y ϵ a. Then x.ec y.ec a, thus x ϵ a.

(2) Terminal objects have no members.

Proof: Assume that x ϵ t for a terminal t. Then x.ec t, thus, by (S1ϵ~3), x.ec = t, so that t is an eigenclass – a contradiction.

(3) An object x is a helix class iff r.ec < x.

Proof: Let r.ec < x. Since x is not minimal it cannot be terminal. The implication r.ec < y.ecr < y shows that x cannot be an eigenclass. Thus x is a class. In particular, x r. As a consequence, x.ec r.ec < x so that x ϵ xx is a helix class. The only-if-part is asserted by (S1ϵ~4)(e).

(4) The inheritance root, r, is a helix class.

Proof: Follows by (3) and (S1ϵ~4)(b).

(5) There is a least helix class, the instance root c, equal to r.class. In addition, c r.

Proof: Follows by (3) and (S1ϵ~4)(b).

(6) The sets { r.ec(i) | i } and H are closure systems in (O T, ). (The corresponding closure operators are denoted .re and .he, respectively.)

Proof: By (S1ϵ~9)(a), for every object x, the set x. is finite. As a consequence, for every non-terminal x, the set x. { r.ec(i) | i } (resp. x. H) is non-empty, finite and linearly ordered in , so that it has a bottom element.

(7) Every object x has a unique primary object, x.pr, i.e. for every x there exists a primary object p,
  • p.ec(i) = x for some i ≥ 0.

Proof: Let x be an object. If x is primary then x.pr = x. For an eigenclass x, let i be such that r.ec(i) = x.re. If p.ec(i+1) = x for some eigenclass p then p r would imply x = p.ec(i+1) r.ec(i+1) < r.ec(i) = x.re – a contradiction with the definition of x.re. This means that p.ec(j) = x for some j i + 1 and a primary object p.

(8) The class map .class forms a tree rooted at the instance root c. Equivalently, for every object x,
  • x.class(i) = c   for some i ≥ 0.

Proof: Let h be a helix object satisfying (S1ϵ~8). We can assume that h = h.re = r.ec(i) for some i ≥ 0. Let x be a non-helix class. Since x.ec(i).re r.ec(i) = h it follows by (S1ϵ~8) that x.ec(i) is not a descendant of any non-helix class. Thus, x.ec(i).class = c. Using (S1ϵ~7) we obtain that x.class(i+1) = c.

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

S1ϵ.pr: The primary structure

In this section we provide an axiomatization of the restriction of object membership to primary objects. Since the inheritance relation is not obtainable from the instance-of relation between primary objects, the symbol is added to the signature.

An S1ϵ.pr structure is a structure (O.pr, ϵ, ) where

Additional notation / terminology is applied: The structure is subject to the following axioms:
(S1ϵ.pr~1)
  • (a) (ϵ) () = (ϵ).
  • (b) () (ϵ) = (ϵ).
(S1ϵ.pr~2) The inheritance is a partial order between objects.
(S1ϵ.pr~3)
  • (a) Only classes can have instances.
  • (b) Terminals have no strict descendants.
(S1ϵ.pr~4) The set H.pr of helix classes is subject to the following conditions:
  • (a) H.pr is a chain in inheritance.
  • (b) There are at least 2 helix classes.
  • (c) Every two helix classes are instances of each other.
(S1ϵ.pr~5) Metaclasses can only have classes as instances.
(S1ϵ.pr~6) Every object x has a least primary container, x.class.
(In particular, every object is an instance of a class.)
(S1ϵ.pr~7) Cycles in ϵ only occur among helix classes, i.e. for every object x and every i > 0,
  • x ϵi x   implies   x ϵ x.
(S1ϵ.pr~8) The set C of classes is finite.

Proposition:

  1. Condition (S1ϵ.pr~1) can be equivalently written as a single equality: () (ϵ) () = (ϵ).
  2. Primary containers of helix classes are helix classes.
  3. Since helix classes form a finite chain c < … < r , (S1ϵ.pr~4)(c) can be equivalently written as any of the following:
  4. The restriction of an S1ϵ structure (O, ϵ, ) to primary objects is an S1ϵ.pr structure.
  5. For an S1ϵ structure (O, ϵ, ), the .c operator is a homomorphic projection onto the primary structure (O.pr, ϵ, ).
  6. (The correspondence between canonical and primary structures.)
    Up to isomorphism, there is a one-to-one correspondence between S1ϵ.pr structures and S1ϵ structures satisfying condition (S1ϵ~5⁺) (The condition can be expressed as C.he r.ec..)
    For the proof, see Eigenclass completion.
Sample
The following diagram shows the sample structure in the primary restriction. The class map is displayed in its reduction, .ͼlass. The instance-of relation is given by (ϵ) = () (.ͼlass) (.).
Eigenclass completion
For an S1ϵ.pr structure (O.pr, ϵ, ) we define its eigenclass completion as a structure (O, ϵ, .ec, ) with the following properties:
  • (O, .ec) is a (reduct of a) primorder algebra such that the notation O.pr coincides (i.e. O.pr are the primary objects).
  • The inheritance is extended to eigenclasses as follows. Let a, b be primary objects, and i, j > 0. Then
    • (ec~A) a.ec(i) b   iff   a ϵi b. ()
    • (ec~B) a b.ec(j)   iff   a < c, b = r and j = 1.
    • (ec~C) a.ec(i) b.ec(j)   iff   a.ec(i-1) b.ec(j-1).
  • The object membership ϵ is extended by (O, ϵ) = (O, .ec) (O, ).
Condition (ec~B) can be written as: For every class a and every eigenclass e,
  • (ec~B') a e   iff   a < c and e = r.ec.
() For convenience, we introduce a special symbol, ϵ, for the restriction of ϵ to primary objects, i.e.
  • (ϵ) = (O.pr, ϵ).

Proposition A: (O, ) is a partial order.

Proof: i.e. for every objects u, v, w,

  • u u (reflexivity),
  • u v w implies u w (transivity),
  • u v u implies u = v (antisymmetry).
Reflexivity is trivially satisfied. To prove transitivity of , we can assume without loss of generality that at least one (and not all) of u, v and w is a primary object. Assume that x, y, z are primary objects and i ≥ 0, j > 0.
  1. Let x.ec(i+j) y.ec(j) z, i.e. x.ec(i) y and y.ec(j) z. Then x ϵi y ϵj z, thus x ϵi+j z, therefore x.ec(i+j) z.
  2. Let x.ec(i) y.ec(i+j) z, i.e. x y.ec(j) and y ϵi+j z. Then x < c, y = r and j = 1, so that r ϵi+j z implies that z is a helix class. Moreover, x < c implies x ϵi c. From x ϵi c z we obtain x ϵi z (using (S1ϵ.pr~1)(a)).
  3. Let x.ec(i+1) y z.ec(j). Then z = r and j = 1 so that x.ec(i) ϵ y z.ec, thus x.ec(i+1) z.ec (using (S1ϵ.pr~1)(b)).
  4. Let x y z.ec(j). Then y < c and z = r and j = 1. Having x y < c, we obtain x z.ec(j).
  5. Let x y.ec(i+1) z.ec(i+1+j). Then y < c and y = z = r so that this case cannot occur.
  6. Let x y.ec(i+j) z.ec(j). Then i+j = 1 so that the case is equivalent to x y.ec z.ec. From r = y z we obtain y = z.
  7. Let x.ec(j) y z. This case is a simplification of the first case.
To prove that u v u implies u = v it is sufficient to show that if u is an eigenclass and v a primary object then the condition u v u cannot be satisfied. But this follows from (ec~B'): r.ec v r.ec cannot be satisfied.

Proposition B: The .ec map is an order embedding of (O, ) into itself.

Corollary:

  1. () (.ec) (.ec) ().
  2. (.ec) (ϵ) = (ϵ) (ϵ).
  3. For every (not necessarily primary) objects x, y, and every i ≥ 0,
    • x.ec(i) y   iff   x ϵi y.
  4. For every primary objects x, y, and every i ≥ 0,
    • x ϵi y   iff   x ϵi y.

Proof: Follows from the previous proposition and the definition of eigenclass completion.


Proposition C: For every objects x, y, there are at most finitely many k such that

  • x y.ec(k).

Corollary: Every object has finite number of ancestors.

Proof: Let x = a.ec(i), y = b.ec(j) for primary objects a, b and let k ≥ 0 be such that a.ec(i) b.ec(j+k). By condition (ec~B), j+k i+1, i.e. k is upper bounded by i+1-j.


For a non-terminal object x, we denote x.re = r.ec(i) such that x r.ec(i) and i is maximal with such property.

Proposition D: For every non-terminal object x and every i ≥ 0,

  • x.ec(i).re = x.re.ec(i).

Proposition E:

  1. An object x is a helix object iff x.pr is a helix class.
  2. Descendants of r are exactly the non-terminal objects.
  3. Ancestors of helix objects are helix objects.
  4. For every helix objects x, y,
    • x.eci < y.eci   implies   x > y.

    Corollary:

    1. Helix objects are linearly ordered by .
    2. H.pr = r.ec. {r.ec}, i.e. helix classes are exactly the strict ancestors of r.ec.
    3. H.ec = r.ec. H, i.e. helix eigenclasses are exactly the helix descendants of r.ec.
  5. For every object x, i ≥ 0,
    • x < c.ec(i) implies x r.ec(i+1).

    Corollary: For every i > 0, r.ec(i) has no siblings in inheritance.

Proof:

  1. Let x = a.ec(i) for some primary object a and i ≥ 0. We have
      x ϵ x   iff   a.ec(i+1) a.ec(i)   iff   a ϵ a.
  2. Let x = a.ec(i) for some primary object a, i ≥ 0. We have
    • a.ec(i) r   iff   a ϵi r.
    It follows that x r iff x is a non-terminal object.
  3. Let a.ec(i) b.ec(j) for a helix class a and a primary object b. If i < j then b = r by (ec~B). Otherwise a ϵi-j b. In both cases it follows that b is a helix class.
  4. Let a, b be helix classes and 0 i < j. Then the following equivalence chain holds:
    • b.ec(j) a.ec(i)   iff   b.ec(j-i) a   iff   b ϵj-i a.
    Since b ϵj-i a is always satisfied (due to (S1ϵ.pr~4)(c)), the desired statement follows.
  5. Let a be a primary object and j ≥ 0 such that x = a.ec(j). Assume that x < c.ec(i), i ≥ 0.
    1. If j-i = 0 then a r.ec due to (ec~B').
    2. If j-i = 1, i.e. a.ec < c, then it follows from (S1ϵ.pr~5) that a is a class, so that a r, thus a.ec r.ec.
    3. If j-i ≥ 2 then a.ec(j-i) r.ec follows from a.ec(j-i-1) r.
    4. If j-i < 0 then a < c.ec(j-1). But this is not possible, since it would imply c = r due to (ec~B).

Proposition F: The structure (O, ϵ) is an S1ϵ structure satisfying (S1ϵ~5⁺).

Proof: We prove the conditions (S1ϵ~1)(S1ϵ~9).

  1. The first 3 conditions follow by definition of (O, ϵ) using the previous proposition that (O, ) is a partial order.
  2. (S1ϵ~4) holds by proposition E.
  3. (S1ϵ~5⁺) holds due to (ec~B).
  4. (S1ϵ~6) holds by (S1ϵ.pr~6).
  5. (S1ϵ~7) holds:
    Let a ϵ b ϵ y where y is a class and a and b are (general) objects. We should show that a ϵ b' ϵ y for some class b'. Let x be a primary object, and i such that a = x.ec(i). Then x ϵi+2 y, i.e. x ϵi u ϵ v ϵ y for some classes u, v. Therefore x.ec(i) u ϵ v which yields x.ec(i) ϵ v, so that v is the desired class.
  6. (S1ϵ~8) holds:
    By finiteness of the set of classes and by (S1ϵ.pr~7), the length of ϵ-chains between non-helix primary objects is bounded. That is, there is a k such that x ϵk y cannot be satisfied for a non-helix class. Let h be the helix object r.ec(k+1). We show that h has the desired property from (S1ϵ~8). Let y be a non-helix class and let a be a descendant of y, i.e.
    • x.ec(i) y   (equivalently, x ϵi y),
    where x is a primary object and i is such that a = x.ec(i). Since x.ec.re.eci 2 (by (ec~B)), i < k (by definition of k) and x.ec.re.ec(i) = x.ec(i).ec.re, we have a.ec.re.eci < 2 + k, i.e. a.re.eci < k + 1. It follows that the helix object h cannot be an ancestor of a.
  7. (S1ϵ~9) holds by proposition C and condition (S1ϵ.pr~8).
Class map reduction
By (S1ϵ.pr~1), the ϵ relation is a relation R such that
  • ()   () R () = (ϵ).
Obviously, ϵ is the largest such relation (w.r.t. inclusion).

Proposition:

  1. The class map, .class, as a relation R, satisfies ().
  2. There is a class map reduction, .ͼlass, – the smallest relation R satisfying (). Necessarily, (.ͼlass) (.class).
  3. The .class map is inherited from its reduction by
    • x.class = y.ͼlass
    where y is a minimal (not necessarily unique) ancestor of x for which y.ͼlass is defined.
  4. In the eigenclass completion (O, ϵ), the .ͼlass partial map is the smallest generator of the instance-of relation, (ϵ) (.c), more specifically, .ͼlass is the smallest relation R such that
    • () R () (.c) = (ϵ) (.c).   (Both and ϵ are taken in (O, ϵ) instead of in (O.pr, ϵ).)
S1p.pr: The primary structure via the class map
For completeness, we also provide an alternative axiomatization of the primary structure, based on the .class map.

An S1p.pr structure is a structure (O.pr, .class, , r, c) where

  • O.pr is the set of primary objects.
  • .class is a function between primary objects. For an object x, x.class is the class of x.
  • is a relation between primary objects, called inheritance.
  • r is a primary object, called the inheritance root.
  • c is a primary object, called the metaclass root or instance root.
Additional notation / terminology is applied:
  • Let T be the set of primary objects x such that x r. Elements of T are terminal(s).
  • Let C be the set of remaining primary objects, that is, O.pr = T C. Elements of C are classes.
  • Let H.pr be the set of classes x such that c x. Elements of H.pr are called helix classes.
  • Classes x such that x c are called explicit metaclasses.
  • If x y then x is an (inheritance) descendant of y and y is an (inheritance) ancestor of x. By (S1p.pr~2), inheritance is a partial order on O.pr, so that corresponding notation and terminology applies to . In particular, if x < y then y is said to be a strict ancestor of x.
  • The instance-of relation, ϵ, is defined as the composition (.class) ().
The structure is subject to the following axioms:
(S1p.pr~1) The .class map is monotone with respect to inheritance, i.e. for every objects x, y,
  • x y   implies   x.class y.class.
Equivalently, () (ϵ) = (ϵ).
(S1p.pr~2) The inheritance is a partial order between objects. In addition,
  • r is the highest class (the top of (C, )),
  • terminals are minimal – they have no strict descendants.
(S1p.pr~3) The set H.pr of helix classes forms a substructure with the following properties:
  • H.pr is a chain in the inheritance.
  • r is different from c.
  • r.class = c.
(S1p.pr~4) For every terminal object x,
  • x.class c,
i.e. the class of a terminal object is not a metaclass.
(S1p.pr~5) The .class map forms a tree on primary objects called the instance tree. In addition,
  • c is the root,
  • terminals are (among the) leaves, i.e. the class of a primary object is a class.
(S1p.pr~6) The set C of classes is finite.
Obviously, the structure is uniquely given by (O.pr, .class, ).

Proposition: For a structure S = (O.pr, ϵ, .class, ) the following are equivalent:

  • S is an S1p.pr structure.
  • S is an S1ϵ.pr structure.

S1r: Terminal mixins (modules)

Motivated by the Ruby object model we introduce a generalization of S1p structures that allows extension of object membership via terminal mixins (modules).

An S1r structure is an S1p structure equipped with (Μ, m) where

  • Μ is a relation between objects,
  • m is a distinguished object, called the metamodule root.
Additional terminology is introduced as follows.
  • If (a,b) Μ and a b then a is an own-includer-of b, so that Μ can be called the self-or-own-includer-of relation.
  • Terminals that are members of the metamodule root m (i.e. elements of m.϶ T) are called modules.
  • Objects that are either modules or non-terminals (classes or eigenclasses) are called includers. If m is a helix class then m.϶ is the set of all includers. (In Ruby, m equals the helix class Module, so that includers are Modules.)
  • We allow m to be arbitrary object. In a meaningful interpretation (allowing non-empty set of modules), m is a class but not a metaclass. The best choice for m is strictly between c and r.
  • Recall that the diagonal map . is the map x (x,x).
The structure is subject to the following axioms:
(S1r~1)
  • (a) For every object x, (x,x) Μ.
  • (b) For every (a,b) Μ such that a b,
    • a is an includer,
    • b is a module.
(S1r~2) Μ is antisymmetric, i.e.
  • (a,b), (b,a) Μ implies a = b.
(S1r~3) The reflexive reduction of Μ (i.e. the set Μ O.) is finite.
(S1r~4) The set m.϶ T of modules is finite.

Note: Transitivity of Μ is not asserted so that Μ is not necessarily a partial order [].

The composed inheritance
The composed inheritance, , is defined as (O, ) Μ, i.e. is a relation between objects such that
  • x y     iff     x y   or   x a for some a such that (a,y) Μ.
The kind-of relation ϵ
The kind-of relation, ϵ, is defined as ϵ Μ, i.e. ϵ is a relation between objects such that
  • x ϵ y   iff   x ϵ y or x ϵ a for some a such that (a,y) Μ.

Proposition: (ϵ) = (.ec) ().

S1s: Non-terminal mixins

Motivated by the Scala object model we introduce a generalization of S1p structures that allows non-terminal mixins as the third kind of primary objects (in addition to terminals and classes).

An S1s structure is a structure (O, .ec, .pr, , r, c, .c) where

  • O, .ec, .pr, ., r and c are introduced the same way as for S1p structures.
  • .c is a total function between objects.
Additional notation and terminology is applied like for S1p structures. The differences are as follows:
  • Elements of the set C = O.pr T of non-terminal primary objects are called semiclasses.
  • Let Ͼ be the set C.c. Elements of Ͼ are classes.
  • Let Ϯ be the set of remaining primary objects, i.e. O.pr = T Ͼ Ϯ. Elements of Ϯ are (non-terminal) mixins. (In Scala, they are called traits. In Java, they are interfaces.)
S1s structures are subject to similar conditions as S1p structures. The differences are as follows:
(S1s~4) As in (S1p~4) but in (a), classes is replaced by semiclasses.
(S1s~5) As in (S1p~5) but class is replaced by semiclass.
(S1s~6) The .c map is a closure operator in such that O.c = T Ͼ.
(S1s~8) As in (S1p~8) but class is replaced by semiclass.
(S1s~9) Mixins are not metaclasses, i.e. Ϯ c. = .
The additional condition (S1s~9) ensures that explicit metaclasses are classes. Just like in S1p structures, the class map .class is defined as .ec.c and object membership ϵ as ec .

Proposition:

(1) An S1s structure is uniquely given by (O, ϵ, .c).
(2) For any S1s structure (O, ϵ, .c), the structure (O Ϯ.pr−1, ϵ) is an S1p structure.  
(Ϯ.pr−1 denotes the set of non-strict eigenclass successors of mixins, i.e. objects x such that x.pr Ϯ.)
(3) For a structure (O, ϵ, .c) the following are equivalent:
  • (O, ϵ) is an S1p structure and .c is the closure operator as defined in (S1p~6) (i.e. corresponding to the set O.pr of primary objects as a closure system in (O, )).
  • (O, ϵ, .c) is an S1s structure that does not contain mixins.
Example
The following diagram shows an S1s structure that cannot be considered an S1p structure. The eigenclass e has has 2 parents that are primary objects: A and T. Therefore, the set O.pr of primary objects does not form a closure system.
  • … helix class
  • … non-helix class
  • … mixin
  • … eigenclass
  • … terminal
The structure corresponds to the following Scala code:
def p (x:Object) { println (x.toString.replace("Main$$anon$2$", ""))
}
class A
trait T
val    A = classOf[A]     ;p(A)    // class A
val    T = classOf[T]     ;p(T)    // interface T
val    a = new A          ;p(a)    // A@c76887
val    b = new A with T   ;p(b)    // $anon$1@19f9744
val    e = b.getClass     ;p(e)    // class $anon$1
object x extends A        ;p(x)    // x$@12b644e
val    y = x.getClass     ;p(y)    // class x$
assert (A == e.getSuperclass)
assert (A == y.getSuperclass)
Semi-instance-of
In the previous example, b.isInstanceOf[T] would evaluate to true. To reflect this, we introduce semi-instance-of as the range-restriction of ϵ to semiclasses, i.e.
  • x is semi-instance-of y   iff   x ϵ y and y is a primary object.
The following table shows the position of this relation with respect to ϵ (and others).
Notation Composition Terminology y restricted to
ϵ (.ec) () x member-of y Ͼ, Ϯ, O.ec
x semi-instance-of y Ͼ, Ϯ
(ϵ) (.c) x instance-of y Ͼ
.class (.ec) (.c) x direct-instance-of y
(the class of x is y)
Ͼ

S1c: Multiple roots and degenerate helixes

Motivated by the Objective-C object model we introduce a generalization of S1p structures that allows multiple components of inheritance as well as helixes that have only one class.

An S1c structure is a structure (O, .ec, .pr, , .r) where

  • O, .ec, .pr and are introduced the same way as for S1p structures.
  • .r is a total function between objects, x.r is called the (inheritance) root of x.
Additional notation and terminology is applied like for S1p structures. The differences are as follows:
  • The set T of terminals is the set of primary objects x such that x x.ec.r.
  • The set H of helix objects is the set of objects x such that x.r.ec < x.pr.
  • Metaclasses are objects x such that either x x.r.ec or x = x.r.class.
    (The .class map is induced by the same condition as for S1p structures.)
S1c structures are subject to similar conditions as S1p structures. The differences are as follows:
(S1c~2) The inheritance is a partial order on O such that the following holds:
  • x.r is the top of x. for every object x. Equivalently, the set of maximal elements in forms a closure system with .r as the corresponding closure operator.
  • Terminals are minimal.
(S1c~4) For helix objects, the following holds:
  • (a) For every helix class x, the set { y | x.r = y.r } H.pr of helix classes with the same inheritance root forms a chain in inheritance.
  • (b) (There is no requirement that x.r x.r.class.)
  • (c) For every helix objects x, y,
    • x.r = y.r and x.eci < y.eci   implies   x > y.
  • (d) For every class x and each i ≥ 0,
    • if x.r x.r.class and x < x.r.class.ec(i)   then   x x.r.ec(i+1).

Proposition:

(1) An S1c structure is uniquely given by object membership ϵ   (= .ec ).
(2) Each component of connectedness of ϵ is an S1c structure.
(3) An S1c structure is connected in ϵ   iff   (O T, ) has a top, r.
(4) For an S1c structure S the following are equivalent:
  1. S is an S1p structure.
  2. S is connected in ϵ and r.class r.
Example
The following diagram shows a component of an S1c structure.
The structure corresponds to the following Objective-C code:
#import <Foundation/Foundation.h>

@interface A_: NSObject; @end; @implementation A_; @end
@interface B_: A_;       @end; @implementation B_; @end
int
main(int argc, const char *argv[]) {

  id r = [NSObject class];  id e = object_getClass(r);
  id A = [A_ class];        id f = object_getClass(A);
  id B = [B_ class];        id g = object_getClass(B);
  id b = [B new];

  return 0;
}

S1m: Metaclass redirection

Motivated by the Smalltalk-80 object model we introduce a generalization of S1p structures that allows redirection of the class map on metaclasses (those from the subroot level of the instance tree).

An S1m structure is an S1p structure equipped with (ȼ) where

  • ȼ is a distinguished object, called the (imposed) metaclass subroot.
In Smalltalk-80, ȼ is named Metaclass. The following condition is required:
(S1m~9)
  • ȼ c = ȼ.class,
i.e. ȼ is a class that is either equal to the metaclass root c or is not a metaclass.
Note that for ȼ c there is some terminological controversy with ȼ not being a metaclass. We denote .ȼlass the imposed class map, which is a total function between objects defined by
  • x.ȼlass = ȼ   if x < c = x.class,
  • x.ȼlass = x.class otherwise.

Proposition:

(1) The following are equivalent:
  1. .ȼlass coincides with .class.
  2. .ȼlass is monotone w.r.t. .
  3. c = ȼ.
  4. r.ec is not a .ȼlass-prototype.
(2) The .ȼlass map forms a tree whose root equals c   (so that .class and .ȼlass have equal roots).

Note: Condition (1)(iv) means that metaclass redirection (if any) is inherited from r.ec.

A sample
The following diagram shows a sample S1m structure without explicit metaclasses other than c (which is the case of Smalltalk). The dashed arrow from r.ec to ȼ indicates the metaclass redirection which is inherited by all (implicit) metaclasses. Dashed border for b.ec indicates that in Smalltalk, eigenclasses of terminal objects are fictitious, see Object actuality.
rProtoObject
cClass
ȼMetaclass
A, B and b are created by:
Object subclass: #A.
A      subclass: #B.
b := B new.

S1w: Additional twist links

Motivated by another quirk of the Smalltalk-80 object model we introduce a generalization of S1p structures that allows multiple direct descendants of the metaclass root.

An S1w structure is a structure (O, .ec, .pr, , r, c) where

  • all constituents are introduced the same way as for S1p structures.
Additional notation and terminology is applied like for S1p structures. The differences are as follows:
  • The set T of terminals is the set of primary objects x such that x.ec c.
  • Classes that are not descendants of the inheritance root r are subsidiary.
S1w structures are subject to similar conditions as S1p structures. The differences are as follows:
(S1w~2) The inheritance is a partial order on O such that the following holds:
  • r is the top of all objects x such that x.ec r.ec.
  • Terminals are minimal.
(S1w~4) For helix objects, (S1p~4) holds except for (d) which is modified by inserting the underlined text as follows:
  • (d) For every object x such that x.pr is not maximal in (i.e. has parent(s)) and each i ≥ 0,
    • x < c.ec(i)   implies   x r.ec(i+1).
As a consequence, r.ec is not necessarily the only child of the metaclass root c.

Proposition:

(1) An S1w structure is uniquely given by object membership ϵ   (= .ec ).
(2) An S1w structure is connected in ϵ.
(3) The following are equivalent:
  • (O, ϵ) is an S1p structure.
  • (O, ϵ) is an S1w structure without subsidiary classes.
(4) In an S1w structure the following are equivalent:
  • Every object is an instance of the inheritance root (i.e. r.϶ = O).
  • Subsidiary classes have no instances.
(5) Every subsidiary class is a direct instance of c.
Example
The following diagram shows an S1w structure that refers to the PseudoContext class as known from Pharo.
r  := ProtoObject.
c  := Class.
r2 := PseudoContext.
r2 subclass: #A.

Note: Instantiation of A (or r2) in Pharo causes a crash.

S1: Non-linear helix and imposed class map

Motivated by CLOS we introduce a generalization of S1p structures that allows non-comparable helix classes as well as redirection of the class map.
Preliminaries
Let (X, ) be a partial order and .f a function on X. We say that an element p X is an .f-prototype if the following conditions are satisfied:
  • (a) The set p.f.f−1 has a/the top p (in ).
  • (b) The set p.f.f−1 is convex in .
For an element x X, if p is an .f-prototype such that x.f = p.f then p is said to be the .f-prototype of x and denoted x.proto(.f). Semantically, x inherits the value of .f from p.

Proposition:

  1. The set of all .f-prototypes form a partial closure system in , i.e. .proto(.f) is a closure operator on its domain.
  2. If .f is a monotone map X X (w.r.t. ) then (b) is implicitly satisfied.
  3. The restriction of .f to .f-prototypes uniquely determines .f on the domain of .proto(.f) by
    • x.f = x.proto(.f).f       (x.f is inherited from x.proto(.f)).
Definition

An S1 structure is a structure (O, .ec, .pr, , r, c, .¢lass) where

  • O, .ec, .pr, ., r and c are introduced the same way as for S1p structures.
  • .¢lass is a total function between objects, called the imposed class map.
Additional notation and terminology is applied like for S1p structures. In addition:
  • We denote .¢p the partial closure operator corresponding to the set of .¢lass-prototypes, i.e. .¢p = .proto(.¢lass). This in particular means that for an object x, x.¢p (if defined) is the highest ancestor of x that has the same imposed class.
S1 structures are subject to similar conditions as S1p structures. The differences are as follows:
(S1~4) For helix objects, (S1p~4) holds except for (a) which is dropped, so that
  • the set H.pr of helix classes only forms an interval in inheritance.
(S1~9) The .¢lass map is subject to the following:
  • (a) x.¢lass = x.class whenever x.class c.
  • (b) x.¢lass = c.¢lass whenever x.class = c and x is not a helix class.
  • (c) x.¢lass c. C whenever x is a helix class.   (I.e. all of H.pr.¢lass are explicit metaclasses.)
  • (d) x.¢lass.class = c for every helix class x.
  • (e) Every helix class has a .¢lass-prototype.

Proposition:

(1) The following are equivalent:
  1. .¢lass coincides with .class.
  2. .¢lass is monotone w.r.t. .
  3. c.¢lass = c and c.¢p = r.
(2) The .¢lass map forms a tree with c.¢lass as the root.
The CLISP built-in core structure
The following diagram shows the built-in core structure of CLOS as implemented by CLISP. The set of displayed classes can be obtained in the following steps:
(0) Start with the metaclass root c.
(1) Add helix classes. Let X1 be the set c..
(2) Add explicit metaclasses. Let X2 be the set X1 c. ().
(3) Add .¢lass-prototypes. Let X3 be the set X2 X2.¢p. (X2.¢p = { r, so, to, fso })
(4) Add ancestors. Let X4 be the set X3. (). (X4 X3 = { f })

() Set intersection with C should be applied to exclude eigenclasses.

r T   (the inherince root r)
to structure-object
so standard-object
f function
fso funcallable-standard-object
mo metaobject
sh standard-stablehash
uc clos::superclass
sp specializer
pc clos::potential-class
c class   (the metaclass root c)
bc built-in-class
lc clos::slotted-class
tc structure-class
ssc clos::semi-standard-class
fsc funcallable-standard-class
sc standard-class   (the imposed
instance root c.¢lass)
… the .class / .¢lass map on non-helix .¢lass-prototypes
… the .¢lass map on helix .¢lass-prototypes
The .¢lass map is inherited from its restriction to .¢lass-prototypes by x.¢lass = x.¢p.¢lass.
A sample user structure
The following diagram shows a sample user-created S1 structure in metaclass alignment. Note that
  • eigenclasses of eigenclasses are not displayed,
  • except for c.ec, eigenclasses of metaclasses are not displayed,
  • the non-linear part of the helix is not displayed.
(defclass  A () ())
(defclass  B (A) ())
(defvar    x (make-instance 'B))
(defstruct S ())
(defvar    y (make-instance 'S))
(defvar    l (lambda ()))
Helix entry
The diagram in the appendix shows that CLISP allows classes with undefined helix entry.

S1@: Circular classes

Motivated by the Perl object model we introduce a generalization of S1p structures that allows multiple instance roots (while still preserving a single inheritance root).

An S1@ structure is a structure (O, .ec, .pr, , r, c) where

  • all constituents are introduced the same way as for S1p structures.
The (additional) notation and terminology introduced for S1p structures is applied with the following alteration:
  • c is a metaclass root / an instance root instead of the … / the ….
  • An object x is a metaclass if either x r.ec or x.class = x.
The axioms are altered as follows:
(S1@~4) Condition (S1p~4) is weakened by dropping (b) and dropping (d) whenever the inheritance root is degenerated:
  • (b) There is no requirement that r c.
  • (d) If r c then r.ec(i+1) is the only child (in ) of c.ec(i) for each i ≥ 0.
(S1@~8) Condition (S1p~8) is weakened as follows:
  • (a) The .class map forms a forest (but not necessarily a tree). Thus, instead of an instance tree we speak about an instance forest.
  • (b) The class c is an instance root, i.e. c.class = c.

Proposition:

(1) An S1@ structure is uniquely given by object membership ϵ and is connected in ϵ.
(2) The following are equivalent:
  • (O, ϵ) is an S1p structure.
  • (O, ϵ) is an S1@ structure such that r c and the .class map forms a tree.
Perl circularity
By a Perl S1@ structure we mean an S1@ structure such that the following properties are satisfied:
(S1@~perl~1) r = c.
(S1@~perl~2) C.re = {r}, i.e. every class belongs to the first metalevel (i.e. every descendant of r.ec is an eigenclass).
(S1@~perl~3) Every class is the class of itself.

Proposition: Assuming just (S1@~perl~1) and (S1@~perl~2) the following are equivalent.

  1. (S1@~perl~3)
  2. Every class is a metaclass.
  3. Every class is its own instance.
  4. (C, ) = (C, ϵ), i.e. in the restriction to classes, inheritance and membership ϵ coincide.
A sample
The following diagram shows a Perl S1@ structure together with corresponding Perl code.
my $r = UNIVERSAL; package $r { sub new { bless {}, $_[0] } } package A { sub me { $_[0] } } package B { our @ISA = A } my $b = B->new; print $b->me ."\n"; # B=HASH(0x7aaae4) print B->me ."\n"; # B print $b->isa(B) && $b->isa(A) && $b->isa($r) && B->isa(B) && B->isa(A) && B->isa($r) && A->isa(A) && A->isa($r) && $r->isa($r); # 1

S1 in particular programming languages

Ruby
Recall that a Ruby S1 structure [] is a structure of the form (O, .ec, .pr, .sc, r, c) with .sc being the superclass partial function. If we express the forest (O, .sc) as its reflexive transitive closure (O, ), we obtain the same list of symbols (and the same signature) as for S1p structures.

A Ruby S1p structure is then an S1p structure such that the following properties are satisfied

(S1p~rb~1) The metaclass root c is the only explicit metaclass. Equivalently,
  • every inheritance descendant of r.ec is an eigenclass.
Equivalently, every class belongs to the first metalevel.
(S1p~rb~2) There are exactly 4 helix classes:
c = Class < Module < Object < BasicObject = r
(S1p~rb~3) The inheritance is a forest. (I.e. (O T, ) is a tree.)

A Ruby S1r structure is an S1r structure (O, ϵ, Μ, m) such that the following conditions are satisfied:
(S1r~rb~1) (O, ϵ) is a Ruby S1p structure.
(S1r~rb~2) The metamodule root m equals the Module (helix) class.
Python
A Python S1p structure is an S1p structure such that the following properties are satisfied
(S1p~py~1) The metalevel index x.mli is at most 2 for every class x.
(S1p~py~2) There are exactly 2 helix classes:
c = type < object = r

Proposition: A Python S1 structure [] is an S1p.pr structure with just 2 helix classes.

Scala
A Scala S1s structure is an S1s structure such that the following properties are satisfied:
(S1s~scala~1) The metaclass root c is the only explicit metaclass.
(S1s~scala~2) There are exactly 3 helix classes (and no helix mixin):
c = Class < Object < Any = r
(S1s~scala~3) The set Ͼ of classes forms a tree in the inheritance .
(S1s~scala~4) All mixins are descendants of the Object class.

Note: In Scala, mixins (elements of Ϯ) are called traits.

Java
A Java S1s structure is a Scala S1s structure with additional properties. In Java, elements of Ϯ are called interfaces (instead of traits).
(S1s~java~4) For every interface x,
  • x.c = Object,
i.e. (S1s~scala~4) is strenghtened by the condition that the set Ϯ is convex in the inheritance .
(S1s~java~5) An interface cannot be a parent of an eigenclass, i.e.
  • O.ec.parents Ϯ = .

Notes:

  1. We adopt the helix chain from Scala (Class < Object < Any) – i.e. we add Any as a fictitious root. As a consequence, primitive values are objects – they are objects that are not Objects.
Smalltalk-80
A Smalltalk S1m structure is an S1m structure such that the following conditions are satisfied:
(S1m~smt~1) The metaclass root c is the only explicit metaclass.
(S1m~smt~2) There are exactly 5 helix classes:
c = Class < ClassDescription < Behavior < Object < ProtoObject = r
(S1m~smt~3) The inheritance is a forest.
(S1m~smt~4) c and ȼ are different siblings in inheritance.

A Smalltalk S1w structure can be defined as an S1w structure satisfying the same conditions as above except for the last one. Additionaly, an extra condition might be imposed that subsidiary classes have no instances.
A Smalltalk S1r structure is an S1r structure such that the following holds.
(S1r~smt~1) The metamodule root m equals the Trait class. Moreover, the set m. m.he. of ancestors up to the helix entry forms the following chain:
m = Trait < TraitDescription < TraitBehavior < Object = m.he.
As the name of m suggests, terminal mixins in Smalltalk-80 are called traits (just like non-terminal mixins in Scala).

Note: The traits facility in Smalltalk [] does not seem to be mature enough to allow serious description.

  • In Squeak (as of version 4.2), traits are not being made terminal. The following assertions succeed:
      self assert: Trait new new class class == Trait.
      self assert: Trait new     superclass  == Object.
    This has been remedied in Pharo (although traits still understand the superclass message in contrast to e.g. direct instances of the Object class).
  • It is not clear whether traits can be included into metaclasses.
Objective-C
Object membership in Objective-C does not conform to the S1p structure for the following 2 reasons:
  1. The inheritance hierarchy is multi-rooted. There are multiple officially supported classes (Object, NSObject and NSProxy) that have no parents.
  2. Each helix is degenerated, i.e. each inheritance root r equals its class r.class.
Therefore, we have to resort to S1c structures introduced for this purpose. An Objective-C S1c structure is an S1c structure such that
(S1c~objc~1) For every helix class x,
  • x.class = x.
Equivalently, each ϵ-component has exactly one helix class.
CLOS
A CLOS S1 structure is an S1 structure such that the following properties are satisfied
(S1~clos~1) The (S1p~5⁺) condition is satisfied, i.e. r.ec is the only eigenclass with class descendants.
(S1~clos~2) (Conditions concretizing the built-in core structure can be stated.)
Perl
The Perl S1@ structure has been introduced within S1@ structures.
Helix classes in comparison
  Ruby Python Smalltalk Scala Java CLOS
Inheritance root r BasicObject object ProtoObject Any T
Default class parent Object object Object Object standard-object
Metaclass root c Class type Class Class class
Number of helix classes 4 2 5 3 8
  • Objective-C has multiple inheritance roots: Object, NSObject and NSProxy. Each inheritance root is simultaneously a metaclass root. Therefore, each ϵ-component has exactly 1 helix class.
  • In Perl, the UNIVERSAL class is the only helix class.

S1ϵ,a: Object actuality and the actualclass map

An S1ϵ,a structure is a structure (O, ϵ, .a) where
  • (O, ϵ) is an S1ϵ structure.
  • .a is a total function between objects.
Objects from O.a are actual(s). We denote .aclass the composition .ec.a (and .aclass(i) its i-th application, i ≥ 0). For an object x, x.aclass is the actualclass of x.

The structure is subject to the following conditions:

(S1ϵ,a~1) O.a is a finite.
(S1ϵ,a~2) O.a O.pr, i.e. every primary object is actual.
(S1ϵ,a~3) O.a O.a.ce, i.e. if x.ec is actual then so is x.
(S1ϵ,a~4) .a is a closure operator in inheritance, i.e. for an object x, x.a is the least actual object y such that x y.
(S1ϵ,a~5) O.a H = c.ec(i). for some (necessarily unique) i ≥ 0. Equivalently, the least actual helix object (which is also the only fixpoint of .aclass) is in the eigenclass chain of c.
For an S1ϵ structure (O, ϵ), if A = O.a for some .a satisfying the above properties then we say that A forms an actuality system (in (O, ϵ)). We might also use the term actuality extent for the set O.a in an S1ϵ,a structure.

For an object x, we denote x.actuals the (necessarily finite) list of all non-strict eigenclass successors of x that are actual. In particular, if x is primary then x.actuals is the actual initial part of the eigenclass chain of x.

Proposition:

(1) The set O.a of actual objects (and thus the .a map) is uniquely given by the actualclass map .aclass,
  • O.a = O.pr O.aclass.
(2) The actualclass map, .aclass, satisfies similar properties as the .class map. In particular:
  • The .aclass map forms a tree – the actualclass tree. The root equals c.actuals.last.
  • .ec.aclass = .aclass.aclass.
  • .aclass is monotone w.r.t. .
(3) For every object x and every i ≥ 0,
  • x.ec(i) x.aclass(i) x.class(i).
(4) If A is an actuality extent then so is
  • A A.ec,
  • A B for any finite downset B such that B.ce B,
  • A T.pr−1.ec.   (T.pr−1.ec is the set of eigenclasses from eigenclass chains of terminals.)
(5) (The Python / Java / CLOS actuality extent.)
The set O.pr of primary objects forms an actuality system (the smallest possible). The corresponding actualclass map equals .class.
(6) (The Smalltalk actuality extent.)
The set O.pr C.ec of primary objects together with first eigenclasses of classes forms an actuality system. If c is the only explicit metaclass then the corresponding actualclass map, .aclass, is defined as follows:
  • x.aclass = x.class if x is terminal,
  • x.aclass = x.ec if x is a class,
  • x.aclass = c.ec for every eigenclass x.
(7) (The Scala actuality extent.)
Any subset of O.pr T.ec forms an actuality system. In this case
  • x.aclass = x.ec if x is terminal and x.ec is actual,
  • x.aclass = x.class otherwise.
S1s,a
Object actuality for S1s structures is subject to an additional condition.
(S1s,a~6) A mixin cannot be an actualclass, i.e. O.aclass Ϯ = .
S1c,a
For S1c,a structures, (S1ϵ,a~5) is to be replaced by
(S1c,a~5) If x.aclass = x then x.pr = x.r.class.
S1m,a
For S1m,a structures, the following additional condition is required:
(S1m,a~6) The c.actuals and ȼ.actuals lists are equally sized.
The imposed actualclass map, .aȼlass, is a total function between objects defined by
(a) x.aȼlass = ȼ if ȼ c and x.aclass = c.actuals.last,
(b) x.aȼlass = x.aclass otherwise.
In particular, .aȼlass = .aclass iff ȼ = c.

Proposition: The imposed actualclass map .aȼlass forms a pseudotree (which can be called the (imposed) actualclass pseudotree). Its pseudoroot consists of elements of ȼ.actuals.

The following diagram shows a sample Smalltalk-80 S1m,a structure with its actualclass pseudotree. The pseudoroot contains the Metaclass class and its eigenclass. Non-actual eigenclasses are not displayed.
Object subclass: #A.
A      subclass: #B.
x := Object new.
y := Object new.
a :=      A new.
b :=      A new.
… the .aclass map (where coincident with .aȼlass)
… the .aȼlass map (where different from .aclass)
Actuality in particular programming languages
The following table shows support for actual eigenclasses in the considered programming languages. In Python, Java and CLOS, all actual objects are primary. Smalltalk and Objective-C have fixed set of actual eigenclasses consisting of first eigenclasses of classes.
Language Actual eigenclasses
(O.a O.pr)
Ruby An upset in (O.ec, )
Python
Scala A subset of T.ec
Java
Smalltalk The set C.ec
Objective-C
CLOS
Perl
Ruby
Ruby supports dynamic eigenclass actualization. In fact, there are 2 actuality systems in MRI, corresponding to two actualclass maps:
  • .aclass – this standard actuality system contains allocated objects that can be actually referenced.
  • .klass – this semiactuality system contains all allocated objects. For each class x, there is one semiactual eigenclass after the chain of actual eigenclasses from x.pr−1.
For details, see [] [].

S2r: Linearization of terminal mixins

An S2r structure is an S1r structure equipped with (≤Μ) where
  • Μ is a relation on Μ (i.e. between ordered pairs of objects) called MRO (method resolution order).
Being a subset of (O × O) × (O × O), the MRO can be considered a quaternary relation between objects. It is preferably written without the subscript, as (Μ, ). Additional notation and terminology is introduced as follows.
  • Let .incl be the projection of Μ onto the first coordinate – for (a,b) Μ,
    • (a,b).incl = a.
The structure is subject to the following conditions:
(S2r~1) The MRO relation, (Μ, ), is a partial order.
(S2r~2) The diagonal map . establishes an order embedding between (O, ) and (Μ, ), i.e. for every objects x, y,
  • x y   iff   (x,x) (y,y).
(S2r~3) The .incl map is monotone, i.e. for every (a,b), (x,y) Μ,
  • if (a,b) (x,y) then a x.
(S2r~4) For every (a,b), (a,c), (x,y) Μ,
(a) (a,a) (a,b) (i.e. (a,a) is the bottom of a.incl−1).
(b) If (a,a) < (x,x) then (a,b) < (x,x) (i.e. a.incl−1 is below a.parents.).
(c) Either (a,b) (a,c) or (a,c) (a,b) (i.e. a.incl−1 is linearly ordered by (Μ, )).
Informally, MRO is obtained from the inheritance by equipping each inclusion set with a linear order. For each includer a, the inclusion chain is placed between a and its parent(s) (or above a if a is maximal in inheritance).

Proposition:

  1. For every object a, a.incl−1 is convex in (Μ, ), i.e. for every (a,b), (x,y) Μ,
    • if (a,a) (x,y) (a,b) then x = a.
  2. An S2r structure can be expressed as (O, ϵ, ≤Μ, m)   (Μ is obtained as the domain of Μ).
  3. O. is an interior system in (Μ, ) (i.e. a closure system in (Μ, ≥)) and .incl. is the corresponding interior operator. That is, for every (x,y) Μ,
    • (x,x) is the top of (x,y). O..
  4. Components of (Μ, ) and (O, ) are in one-to-one correspondence via .incl. Like in inheritance, the MRO has a single main component, the set Μ T2 = (O T).incl−1. All the remaining components are inclusion chains (x.incl−1, ) for terminal x, which are singletons whenever x is not a module.
Inclusion lists
For an object x the (own) inclusion list of x, denoted x.incs, corresponds to (x.incl−1, ) without the bottom. More specifically, x.incs is a (possibly empty) list of modules defined by
  • x.incs[i] = y   iff   (x,y) is i-1-th ancestor of (x,x) in (x.incl−1, ).

Proposition: An S2r structure can be expressed as (O, ϵ, .incs, m).

In Ruby
A Ruby S2r structure is an S2r structure such that the S1r-reduct (obtained by forgetting the inclusion order) is a Ruby S1r structure.

The structure is also specified in [] where it is referred to as the S2 structure. Since inheritance (O, ) in Ruby is a forest, the MRO relation is also a forest, which is the designed characteristics. For a sample structure, see [] or an S2ϵ sample.

S2s: Linearization of non-terminal mixins

In an S1s structure, the Μ relation is obtained implicitly is a subset of the inheritance defined by (x,y) Μ iff one of the following conditions is satisfied:
  • (a) x = y,
  • (b) x < y and every object a such that x < a y is a mixin (in particular, y is a mixin).
If (x,y) Μ and x y then it can be said that x is an own-includer-of y, where own means that all objects strictly between x and y in inheritance are mixins.

An S2s structure is an S1s structure equipped with (≤Μ) where

  • Μ is a relation on Μ called MRO (method resolution order).
Similar notation applies as for S2r structures, in particular, .incl is the projection of Μ onto the first coordinate.
S2s structures are subject to similar conditions as S2r structures:
(S2s~1) MRO is a partial order.
(S2s~2) For the restriction of MRO to O. the following holds:
  • (x,x) < (y,y)   iff   x < y and y is not a mixin.
(S2s~3) The .incl map is monotone.
(S2s~4) Conditions (a)—(c) hold like in (S2r~4) except that (a) is strenghtened by (S2s~5) and in (b), .parents has to be replaced by .parents.c.
(S2s~5) The MRO respects inheritance between mixins, i.e. for every (a,b), (a,c) Μ,
  • if b c then (a,b) (a,c)

Proposition A:

  1. 1–4. Similar statements as with S2r structures apply.

Proposition B: In contrast to S2r structures, the following properties are satisfied:

  1. The Μ relation is a partial order.
  2. An includee can appear only once in an MRO ancestor set, i.e. for every (a,x), (b,x) Μ,
    • if (a,x) (b,x) then a = b.
In Scala
Like with Ruby S2r structures, a Scala S2s structure is an S2s structure such that the S1s-reduct is a Scala S1s structure. Since the inheritance on the set Ͼ of classes is a tree, the MRO relation, restricted to Μ' = Μ (T r.ec.)., is also a tree, which is the designed characteristics.

Notes:

  1. The main component of MRO is the set Μ T.. In general, this set does not form a tree in MRO, since the MRO, as defined above, does not establish any additional ordering between eigenclasses of traits.
  2. The set Μ' is obtained from the main component by removing r.ec.., the diagonal image of implicit metaclasses.
  3. In Scala, c3-compatibility is not enforced. In the following code, the A class is a descendant of traits U and V that are not c3-compatible:
    trait R
    trait S
    trait U extends R with S
    trait V extends S with R
    class A extends U with V  # OK
    

S2p: Linearization of ancestors

The Μ relation, in its default semantics (which is overridden in S1r or S1s), equals the inheritance , i.e.
  • (x,y) Μ   iff   x y.
An S2p structure is then an S1p structure equipped with (≤Μ) where
  • Μ is a relation on Μ called MRO (method resolution order), and preferably denoted as (Μ, ).
The structure is subject to the following conditions, with 4 alternatives for (S2p~3):
(S2p~1) The MRO relation, (Μ, ), is a partial order.
(S2p~2) Components of MRO correspond to linearly ordered ancestor sets, i.e. for every (a,b), (a,c), (x,y) Μ,
  • (a) If (a,b) (x,y) then a = x.
  • (b) Either (a,b) (a,c) or (a,c) (a,b).
(S2p~3) The MRO consistency conditions are as follows (listed from the weakest to the strongest):
  • (c1) For every (a,b) Μ,
    • (a,a) (a,b).
  • (c2) MRO respects inheritance between ancestors, i.e. for every (a,x), (a,y) Μ,
    • if x y then (a,x) (a,y).
  • (c3) We say that objects a and b are c3-compatible if for every pair x, y of common ancestors of a and b,
    • (a,x) (a,y) iff (b,x) (b,y).
    Condition (c3) then asserts that (c1) is satisfied together with any of the following equivalent conditions:
    • If a b then a and b are c3-compatible.
    • If a and b have a common descendant then they are c3-compatible.
  • (c4) Condition (c1) holds and the c3-compatibility condition is satisfied for every pair of objects.

Note: The (c3) condition is enforced by the C3 linearization algorithm [].

In Python
By default, Python uses C3 linearization. A request for creation of a class with c3-incompatible parents results in an error. This behavior can be altered by explicitly setting the __mro__ attribute.

Note: As of version 3.2, Python allows to set quite arbitrary ancestor lists to __mro__, but we assume that at least (c1) is satisfied.

In CLOS
In CLOS, the (c3) condition is mandatory – according to Common Lisp HyperSpec [].
In Perl
By default, Perl uses depth-first linearization so that even (c2) is not guaranteed. Optionally, the use mro 'c3' pragma can be used to enforce C3 linearization.

S2ϵ: Iclasses

This section provides an ϵ-axiomatization of S2r structures, similarly as S1ϵ structures are S1p structures axiomatized via ϵ. The description introduces iclasses which are objectivized elements of Μ O..

By an S2ϵ structure we mean a structure (Θ, ϵ, m) where

  • Θ is a set of objects, and
  • ϵ is a relation between objects, called membership,
  • m is a distinguished object, called the metamodule root.
With respect to S1ϵ structures, notation and terminology is altered as follows.
  • The inheritance is a relation between objects defined by
    • x y   iff   for every object a, both of the following are satisfied:
      • y ϵ a implies x ϵ a,
      • a ϵ x implies a ϵ y.
  • The eigenclass of x, x.ec, is the unique smallest container of x. Its existence is ensured by (S2ϵ~1). Objects from Θ.ec are eigenclasses, the remaining objects are primary.
  • The set H of helix objects is the set of circular objects, i.e. objects x such that x ϵ x.
  • The set I of iclasses (a shorthand for inclusion classes, but similarly to eigenclasses, an iclass is never a class) is a set of primary objects x such that
    • x is not minimal in the inheritance ,
    • x.ec(2) = y.ec for some y different from x.ec.
  • The set O of referenceable objects is defined as Θ I I.ec, i.e. an object is referenceable iff it is neither an iclass nor the eigenclass of an iclass.
  • The set T of terminals is defined as O r.. Equivalently, x T iff
    • x is not a member of any helix eigenclass, and
    • x is not an iclass.
  • The set C of classes is defined as O O.ec T.
  • Terminals that are members of the metamodule root m are called modules.
The structure is subject to the following axioms:
(S2ϵ~1) The same sentence as (S1ϵ~1).
(S2ϵ~2) Like in (S1ϵ~1): The inheritance is antisymmetric, thus a partial order. Equivalently, distinct objects have either
  • different sets of containers OR
  • different sets of members.
Note that this is weaker than (S1ϵ~2) so that in an S2ϵ structure, different objects may have identical sets of containers.
(S2ϵ~3)

(S2ϵ~6)
The same sentences as (S1ϵ~3)(S1ϵ~6)
(S2ϵ~7) For every object x that is not an iclass,
  • x.ec.class = x.class.class.
(S2ϵ~8) There exists a helix object h such that the set h. of all descendants of h is disjoint with all the following sets:
  • (a) x. for every non-helix class x.     (Therefore, (S2ϵ~8)(a) is the same as (S1ϵ~8).)
  • (b) {x, x.ec} for every iclass x.
(S2ϵ~9) The same finiteness conditions as (S1ϵ~9).
(S2ϵ~10) The eigenclass map .ec is injective on Θ I.ec, i.e. for every objects x, y that are not eigenclasses of iclasses,
  • x.ec = y.ec implies x = y.
(S2ϵ~11) For every iclass x there exists a (necessarily unique) module y such that
  • x.ec(2) = y.ec(2).
We denote .i2m the corresponding function I T.
(S2ϵ~12) The set O of referenceable objects forms a closure system in the inverse inheritance (Θ, ≥). We denote .incl the corresponding interior operator, i.e. for an object x, x.incl is the highest descendant of x that is a referenceable object.
(S2ϵ~13) Iclasses with the same includer are linearly ordered, i.e. for every iclasses x, y,
  • x.incl = y.incl   implies   x y or y x.
(S2ϵ~14) For every iclasses x, y,
  • (a) x.incl = y.incl and x.i2m = y.i2m   implies   x = y.  
    (A module cannot be included twice into the same includer.)
  • (b) x.incl = y.i2m   implies   x.i2m y.incl.  
    (Two modules cannot be included into each other. In particular, a module cannot be included into itself.)
(S2ϵ~15) Iclasses are not intertwined with eigenclasses of iclasses, i.e. for every iclasses x, y,
  • (a) x.ec < y implies x.ec < y.incl.
  • (b) x < y.ec implies x < y.ec.incl.
(S2ϵ~16) m O.
Sample structure
The following diagrams show a sample S2ϵ structure from Ruby.
  • … helix class
  • … non-helix class
  • … module
  • … eigenclass
  • … iclass
  • … eigenclass of iclass
The diagram on the left shows the Kernel module together with its inclusion into the Ruby helix.

The structure that corresponds to the merge of both diagrams can be created by the following Ruby code:

module M;           end
module N; include M end
class A < BasicObject
  class << self; include N end
end
class Object; def ec; singleton_class end end

p M   .ancestors # [M]
p N   .ancestors # [N, M]
p A   .ancestors # [A, BasicObject]
p N.ec.ancestors # [Module, Object, Kernel, BasicObject]
p A.ec.ancestors # [N, M, Class, Module, Object, Kernel, BasicObject]

Notes:

  1. In Ruby, iclasses are hidden objects. The interpreter makes sure that they are never referenced. For example, the superclass method skips all iclasses.
  2. Eigenclasses of iclasses (and their .ec links) should be regarded as a formal means rather than an implementation feature of MRI.
S2ϵ versus S1ϵ

Proposition:

  1. For any S2ϵ structure (Θ, ϵ, m), the restriction & reduction (O, ϵ) is an S1ϵ structure.
  2. For a structure (Θ, ϵ, m) the following are equivalent:
    • (Θ, ϵ) is an S1ϵ structure and m is an object.
    • (Θ, ϵ, m) is an S2ϵ structure that does not contain iclasses.
S2ϵ versus S2r
We denote Μ the relation on O defined by
  • (a,b) Μ   iff   either of the following holds:
    (a) a = b = x for some x O,
    (b) (a,b) = (x.incl, x.i2m) for some x I.
Because of (S2ϵ~14), the object x is unique. This defines a bijection .ω : Μ O I. In particular, an iclass is a module in the context of its own includer.

The bijection in turn induces a partial order Μ on Μ:

  • (a,b) ≤Μ (x,y)   iff   (a,b).ω (x,y).ω.

Proposition: Let S = (Θ, ϵ, m) be an S2ϵ structure and denote S r = (O, ϵ, ≤Μ, m).

  1. S r is an S2r structure.
  2. Up to isomorphismus, S is uniquely given by S r.
    (As a consequence, S2r structures and S2ϵ structures are in one-to-one correspondence.)
  3. The correspondence between introduced sets is shown in the following diagram.
… set-inclusion ()
… bijection
Eigenclasses of iclasses
According to the definition, for every iclass x, the eigenclass map .ec is
  • injective (non-constant) on the 2-element set {x, x.i2m}, and
  • non-injective (constant) on the 2-element set {x.ec, x.i2m.ec}.
    (Therefore, attributing higher preference to x.i2m.ec, we can say that x.ec does not have a true eigenclass.)
This level of indirection is necessary to ensure that the inheritance can be recovered from the membership relation ϵ. If we used already in the signature for the axiomatization, (e.g. (Θ, .ec, , m)) we could dispense with (true) eigenclasses of iclasses. This would simplify the description. In particular, (S2ϵ~15) could be removed.

 

Appendix

The ontological structure of ϵ
The document [] provides a generalization of object membership as it applies to ontological structures based on RDF Schema. The generalization structure, denoted S1o, is distinguished by the following features:
  • The existence of the .class map is not guaranteed – an object x can have multiple minimum classes of which x is an instance.
  • There is a distinguished sort of objects, called properties. Like terminals, properties are not descendants of the inheritance root. Unlike terminals, properties can have descendants (which are necessarily also properties).
  • Inheritance does not have to be antisymmetric – classes and properties can have distinct equivalents.
The structure can be expressed as (O, ϵ, p) provided that there is no need for distinction of r and c between possibly many equivalent objects.
Prototypes
The document Object Membership with Prototypes [] shows that 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 corresponding S1ȷ structures are introduced as structures (Θ, O, ϵ) such that (Θ, ϵ) is an S1ϵ structure without terminal objects, and O is a subset of Θ such that the substructure (O, ϵ) is an S1ϵ 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.

It is shown how S1ȷ structures apply to the JavaScript programming language. As a particular conclusion which can be drawn, JavaScript cannot be declared to be classless. (Such a judgement is also supported by the presence of the instanceof operator and also by the presence of the class notion in authoritative books about JavaScript [].)

The Python Object Model
The document [] provides a brief description of Python's S1 and S2 structures.
CLOS/CLISP metaobject classes
The following diagram shows inheritance between built-in descendants of the metaobject class in CLOS as implemented by CLISP 2.49. The set of displayed classes equals mo.. (without eigenclasses) where mo is the metaobject class. Red oval indicates that for the m class (and its descendants), the helix entry m.he is undefined.
r T   (the inherince root r)
so standard-object
mo metaobject
sh standard-stablehash
sp specializer
esp eql-specializer
f function
fso funcallable-standard-object
gf generic-function
sgf standard-generic-function
uc clos::super-class
pc clos::potential-class
frc forward-referenced-class
mfrc
 
misdesigned-
forward-referenced-class
sd slot-definition
dsd direct-slot-definition
ssd standard-slot-definition
esd effective-slot-definition
sdsd standard-direct-slot-definition
sesd standard-effective-slot-definition
tdsd structure-direct-slot-definition
tesd structure-effective-slot-definition
m method
sm standard-method
sam standard-accessor-method
srm standard-reader-method
swm standard-writer-method
mc method-combination
c class   (the metaclass root c)
bc built-in-class
lc clos::slotted-class
tc structure-class
ssc clos::semi-standard-class
fsc funcallable-standard-class
sc standard-class   (the imposed
instance root c.¢lass)
Correspondence to related former documents
Specialized description of the instance–inheritance structure of the Ruby object model is provided in []. The structure is then further developed in [] together with a comparison with Smalltalk-80 []. There are slight differences in notation and terminology which are summarized in the following table.
This document Documents [] [] []
Terminology Notation Notation Terminology
(O T, ) Superclass inheritance
(sc-inheritance)
Inheritance T.
m.϶ HM descendancy
Composed inheritance T.
Object membership ϵ .ec Restricted kind-of
Kind-of ϵ (.ec) () (Full) kind-of
Imposed class map .ȼlass .rclass
Imposed actuaclass map .aȼlass .aclass actualclass map
Μ m.϶ Μ self-or-own-includer-of
(between includers)
self-or-own-includer-of
(between all objects)
Μ Μ T.
In particular:
  • In this document, inheritance and self-or-own-includer-of are reflective on the whole set O of objects, whereas in the referenced documents, they are restricted to non-terminals and includers, respectively.
  • The symbol in [] is used for composed inheritance, restricted to includers. This is in correspondence with the Ruby <= introspection method.

 

References
David Aspinall, Subtyping with Power Types, In Proc. Computer Science Logic, CSL 2000, Springer, 2000, http://homepages.inf.ed.ac.uk/da/papers/lambdapower/lambdapower.pdf
Kim Barrett, Bob Cassels, Paul Haahr, David A. Moon, Keith Playford, P. Tucker Withington, A Monotonic Superclass Linearization for Dylan, Proceedings of the 11th ACM SIGPLAN conference on Object-oriented programming, systems, languages, and applications , ACM New York, 1996, http://www.webcom.com/haahr/dylan/linearization-oopsla96.html
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
Tom Christiansen, brian d foy, Larry Wall and Jon Orwant, Programming Perl: Unmatched power for text processing and scripting, O'Reilly, 2012,
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
B.A. Davey, H.A. Priestley, Introduction to lattices and order, Cambridge University Press 2002
David Flanagan, JavaScript: The Definitive Guide, Sixth Edition, O'Reilly 2011
David Flanagan, Yukihiro Matsumoto, The Ruby Programming Language, O'Reilly 2008
Ira R. Forman, Scott H. Danforth, Putting Metaclasses to Work, Addison Wesley 1998
Adele Goldberg, David Robson, Smalltalk-80: The Language and Its Implementation, Addison Wesley 1983, http://stephane.ducasse.free.fr/FreeBooks/BlueBook/Bluebook.pdf
James Gosling, Bill Joy, Guy Steele, Gilad Bracha, Alex Buckley, The Java™ Language Specification, Java SE 7 Edition, Oracle America, Inc. 2012, http://docs.oracle.com/javase/specs/jls/se7/jls7.pdf
Bruno Haible, Michael Stoll, Sam Steingold, Implementation Notes for GNU CLISP, 2010, http://www.clisp.org/impnotes/
Stephen G. Kochan, Programming in Objective-C, Addison Wesley 2011
Mark Lutz, Learning Python, O'Reilly 2009
Martin Odersky, Lex Spoon, Bill Venners, Programming in Scala, Artima 2011
Ondřej Pavlata, Object Membership: The Core Structure of Object Technology, 2015, http://www.atalon.cz/om/object-membership/
Ondřej Pavlata, Object Membership – Basic Structure, 2015, http://www.atalon.cz/om/object-membership/basic/
Ondřej Pavlata, Object Membership: The ontological structure, 2012, http://www.atalon.cz/om/object-membership/ontology/
Ondřej Pavlata, Object Membership with Prototypes, 2015, http://www.atalon.cz/om/object-membership/prototypes/
Ondřej Pavlata, The Ruby Object Model: Data Structure in Detail, 2012, http://www.atalon.cz/rb-om/ruby-object-model
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 Python Object Model: Core Structure in Detail, 2012, http://www.atalon.cz/om/python/object-model
Ondřej Pavlata, The Linux VFS Model: Naming structure, 2011, http://www.atalon.cz/vfs-m/linux-vfs-model/
Ondřej Pavlata, Object Membership: Set theoretic representation, 2013, http://www.atalon.cz/om/object-membership/set-rep/
Kent Pitman (ed), The Common Lisp HyperSpec, 2005, http://clhs.lisp.se
Nathanael Schärli, Traits: Composing Classes from Behavioral Building Blocks, 2005, http://scg.unibe.ch/archive/phd/schaerli-phd.pdf
Browser compatibility
To be viewed correctly, this document requires advanced browser features to be supported, including
  • CSS level 3,
  • HTML entities (Ϯ, ϵ, ϶, Ͼ, |, ¢, ř, ȷ, ȼ, , , , , , , , , , , , , , , , , , , , , , , , , , ͼ, , , , , Μ, Θ, á, &, ', ä, , , , , >, , , , , <, , ,  , , ¬, , ω, ", , , , , , , ×, ),
  • JavaScript,
  • Scalable Vector Graphics (SVG).
Document history
August242012 The initial release.
October102012 Major update. Main changes:
  • Perl added to the list of considered languages.
  • S1r singled out from S2r.
  • The finiteness axioms added to S1ϵ so that S1ϵ is just a re-axiomatization of S1p.
  • Adjustments to S2ϵ.
  • Linearization structures added.
  • (S1s~scala~4) added, (S1p,a~5) strenghtened.
December122012
  • The primary structure S1ϵ.pr introduced, equivalent to S1p.pr.
  • Eigenclass completion provided for S1ϵ.pr.
  • (S1p~py) renamed to (S1p~5⁺) (aliased as (S1ϵ~5⁺)).
  • Correspondence to power types provided.
  • Added new appendix: The ontological structure. []
January222013
  • The term metaclass level changed to meta-level. The corresponding meta-level index is shifted by 1 so that it starts with 0 (as opposed to the former metaclass level index which started at -1).
  • Added new appendix: Set theoretic representation. []
March122015 The document moved to ./oop/ and became subsidiary to [].
  • The term meta-level changed to metalevel. The prescription for x.mli corrected.
  • S1p,a renamed to S1ϵ,a.
  • (S1ϵ,a~5) weakened to the original version.
  • Added: (S1ϵ.pr~4)(c) Helix classes are instances of each other.
  • Finiteness of O.pr weakened to the finiteness of C.
  • In the introductory definition of metaclasses:
    • Corrected: eigenclass of metaclass root eigenclass of inheritance root.
    • Added the definition of inheritance root.
  • Changes in the Appendix. In particular, [] removed (since it has been superceded by []).
License
This work is licensed under a Creative Commons Attribution-NonCommercial-ShareAlike 3.0 License.