An abstract structure is described that
is believed to be central to object-oriented programming and modelling.
In its main form,
the structure is built from three relations between objects,
ϵ, ≤ and .ec.
The most fundamental relation,
ϵ,
is called object membership and is
a refinement of the instance-of relation.
The ≤ relation is the inheritance between objects.
Finally, .ec is a partial map that forms a distinguished
subrelation of ϵ.
The structure arises as a generalization of
the innermost core of the
object model of the Ruby programming language.
In Ruby, the .ec map is total –
every object has an eigenclass.
The following equalities hold:
(≥) = (.ec) ○‣ (϶) and
(ϵ) = (.ec) ○‣ (≤).
The second equality says that
object membership is
the composition of infinite regress of eigenclasses with inheritance.
As an essential feature, the structure supports circular objects,
i.e. objects x such that x ϵ x.
This is also the main indicator of applicability.
It is shown how the structure applies to
class-based programming languages
(Ruby, Python, Java, Scala, Smalltalk, Objective-C, CLOS, Perl and Dylan),
prototypal languages
(JavaScript), and
ontology languages (RDF Schema, OWL Full).
A general mathematical structure of object membership is described in
an affiliate document
[].
A gradual set-theoretic representation is provided
with the exact correspondence of ϵ, ≤, .ec
and derived constituents of the structure to
fundamental notions of set theory.
As a result, a uniform and mathematically precise view of
an essential part of object technology is provided.
This document has been created without any prepublication review
except those made by the author himself.
Membership glyphs
This document uses HTML entities to display mathematical symbols.
In particular, there are multiple glyphs
used for different relation symbols of membership.
Best readability is achieved when the sequences of symbols from the following
two lines look (almost) identically.
Object technology (⁎) is based on
object models[].
The word model indicates that something is abstractly represented
in a structured way.
The word object indicates uniformity –
there is a uniform unit of representation called object.
Note:(⁎)
In this document we regard object technology
as an umbrella term for
object-oriented programming (OOP), object modelling and ontology languages
such as RDF Schema.
The approach
We can further combine the terms from the previous paragraph and say
that an object model is itself based on an abstract structure between objects.
The term structure between objects
can be further interpreted as family of relations between objects.
The term abstract suggests abstraction.
For every non-trivial object model M
there is a hierarchy of models that are abstractions of M.
Around the top of the hierarchy there are core structures
– they are formed by the most fundamental relations between objects.
This document identifies the following three relations
as the core relations of object technology:
ϵ, the object membership relation,
is the most fundamental relation between objects.
It is a generalization of the instance-of relation.
≤, the inheritance relation,
is considered the second most important.
.ec, the powerclass map,
is an auxiliary, possibly empty, one-to-one subrelation of ϵ.
Since abstraction is one of the most fundamental principles of object technology,
we can characterize our approach as
applying object technology to itsef.
Introductory sample
The diagram below shows an example of a core structure of object technology.
Objects are displayed as nodes.
The inheritance relation, ≤,
is shown by green arrows in the reduction to immediate pairs.
Object membership, ϵ, is the composition of blue arrows with inheritance.
The powerclass map, .ec,
is indicated by horizontal blue arrows.
(Ruby 1.9)
r = BasicObject
c = Class
A = c.new(r)
B = c.new(A)
s = A.new
u = B.new
v = B.new
class << s; end
class << v; end
The code on the right shows how the structure
can be obtained in the Ruby programming language
as a part of data structure of a running program.
c and r are only immediate in the partial structure,
restricted to chosen objects.
In the complete Ruby built-in structure,
there are 2 objects between c and r.
In order to demonstrate the possible partiality of the .ec
map, we deviate from the canonical interpretation supported further in the document.
In Ruby, we consider .ec to be a total map.
The objective
The objective of this document is to rigorously describe
structures that arise from
ϵ, ≤ and .ec.
That is, using the conventions in the diagram above,
the document is preoccupied with the following question:
What can be said about the blue and green arrows?
For instance, it can be said that there cannot be an additional green arrow
from r to s in the sample structure.
Therefore, what the document essentially contains is an axiomatic description
of families of structures that arise from the three core relations.
Since the relations are fundamental,
their description should contribute to foundations of object technology.
Presumably, the above question can be stated as
What is the mathematical structure for the
most fundamental part
utmost simplification
highest abstraction
of object technology?
Naturally, there is no universal description for all specific cases.
We have to define idealizations
on which the specific cases are based.
The ϵ^{2}≠∅ condition and circularity
Structures in which
ϵ^{2} is empty
(that is, the composition of ϵ with itself is an empty relation)
have a simple description which is provided
in a single introductory section.
The complementary condition ϵ^{2}≠∅ can be expressed
as the classes are objects principle.
(By convention, the phrase also indicates that the structure is not classless.)
This document is predominantly concerned with structures
satisfying ϵ^{2}≠∅.
That is, x ϵ y ϵ z
for some (not necessarily distinct) objects x, y and z.
It turns out that
in all the introduced structures,
the following stronger condition holds:
There exists an object x such that x ϵ x.
This circularity condition is perhaps the best indicator for the issues handled
in this document.
Another good indicator, although less perfect, is the presence of the notion of
metaclass.
Roughly speaking,
being a metaclass means being in the image of ϵ^{2}.
Therefore, support for metaclasses is roughly equivalent to the
ϵ^{2}≠∅ condition.
However,
there are programming languages, most notably Ruby and JavaScript,
that support circular objects,
but in which the notion of metaclass is not well established.
The non-objective
The focus being on the core structure of the object model,
many notions of object-oriented programming
occur outside the scope of this document.
This should be in particular emphasized for the notion of type.
This document provides no explicit explanation as to what a type is.
Maybe the document provides an implicit explanation but the author is unaware of it.
The concept of type is regarded as something more complex
(an therefore less fundamental) than things described in this document.
We use the term type exclusively as a mean of quotation (reference)
of particular concepts by other parties
(e.g. types as particular objects in Dylan,
or abstract power type system
for the abstract structure of Cardelli's power types).
As a consequence, this document becomes virtually disjoint with
the following two books,
both of which claim to provide foundations of object-oriented programing.
(The metaclass term can be used as an indicator
for the disjointness.
There is no occurrence of this word in either of the books.
Similarly for meta-class.)
A Theory of Objects by Martin Abadi and Luca Cardelli
[].
Excerpt from the Preface:
[]This book develops a theory of objects as a foundation
for object-oriented languages and programming.
Our theory provides explanations for object-oriented notions in terms of
a few basic primitives,
and can be useful for the design and understanding of programming languages.
Foundations of Object-Oriented Programming Languages: Types and Semantics
by Kim B. Bruce
[]
Excerpt from the publisher's overview:
[]This text explores the formal underpinnings of object-oriented languages
to help the reader understand the fundamental concepts of these languages
and the design decisions behind them.
Composition of ϵ and ≤
It will be convenient for further reference to
already introduce the following composition rules for ϵ and ≤:
Rule name
Short expression
Using variables
Set-theoretic counterpart
RDFS rule(s)
Transitivity of ≤
(≤) ○‣ (≤) ⊆ (≤)
if x ≤ y ≤ z then x ≤ z
(⊆) ○‣ (⊆) ⊆ (⊆)
rdfs11 (and rdfs5)
Subsumption of ϵ
(ϵ) ○‣ (≤) ⊆ (ϵ)
if x ϵ y ≤ z then x ϵ z
(∈) ○‣ (⊆) ⊆ (∈)
rdfs9
Monotonicity of ϵ
(≤) ○‣ (ϵ) ⊆ (ϵ)
if x ≤ y ϵ z then x ϵ z
These rules can be observed to be satisfied by the
introductory sample.
We even have used the first two conditions to reduce
the set of displayed arrows:
The set of green arrows is the transitive reduction of ≤
and the set R of blue arrows in the diagram is minimum such that
R ○‣ (≤) = (ϵ).
We could even have had further reduced the set
of displayed blue arrows by applying the mononicity rule.
The resulting subrelation of ϵ would
be the minimum relation S such that
(ϵ) = (≤) ○‣ S ○‣ (≤).
(In the case of the sample, S = (.ec) ∪ {(u,B)}.)
The table also indicates
that
⊆ (set inclusion)
and
∈ (set membership)
are the respective set-theoretic counterparts in of ≤ and ϵ.
However,
the latter correspondence is indirect
–
we will further introduce ∊, a restriction of ϵ,
to be the direct correspondent of ∈,
see
Set-theoretic interpretation.
In contrast to subsumption,
the monotonicity rule has no set-theoretic counterpart.
In set theory,
it is not true that
for every sets x, y, z,
if x ⊆ y ∈ z then x ∈ z.
(For example, if x ⊂ y ∈ {y}
then x ∉ {y}.)
Nevertheless,
monotonicity of ϵ is satisfied in the major part of object technology.
The monotonicity term comes from the following equivalent formulation:
for every objects x, y,
x ≤ y → x.ϵ⊇ y.ϵ
where u.ϵ is the set of all containers of u
(the image of {u} under ϵ).
In particular,
in canonical primary structures,
the condition
can be expressed as monotonicity of the .class map,
i.e.
for every objects x, y,
x ≤ y → x.class ≤ y.class.
(If x is a subclass of y then
x.class is a subclass of y.class.)
This is known as the
metaclass compatibility condition
[].
Main results
This document builds a mathematical model
that is presumably relevant to the core part of object technology.
The following fundamental notions of computer science can be rigorously described
in terms of the model:
class
metaclass
eigenclass
instance-of
inheritance
is-a
class-of
eigenclass-of
singleton-of
It is shown how the model applies to
class-based programming languages
(Ruby, Python, Java, Scala, Smalltalk, Objective-C, CLOS, Perl and Dylan),
prototypal languages
(JavaScript), and
ontology languages (RDF Schema, OWL Full).
The following characteristics can be observed:
The Ruby programming language is the definitive sample language
for the description of the object model.
The Ruby object model (ROM) provides a clean and robust implementation of the
core structure.
In fact, the work on this document originated in discovering the
exquisite properties of ROM.
The Python programming language can be thought of as complementary to Ruby
w.r.t. core structure.
The most part of the core structure of object technology can be described by
combining Ruby and Python.
The Smalltalk-80 programming language is the biggest obstacle to
understanding the above fundamental notions of object technology.
The JavaScript programming language can be thought of as a class-based language
with prototypes as inverse eigenclasses.
On the other hand, it is shown how the model can be embedded into the
universe of sets.
This results in a set-theoretical foundation of the core part of object technology.
Basic structure
ϵ¯
ϵ,
≤,
r,
.ec,
.ɛɕ
ϵ^{-1}
ϵ^{-2}
ϵ^{-3}
⋮
The general mathematical model of The Core is provided by
the family of basic structures.
The diagram on the right shows the signature of these structures.
In addition to the ϵ, ≤ and .ec
relations mentioned in the introduction
there are additional constituents:
ϵ¯, the power membership relation,
is an abstraction of the composition (.ec) ○‣ (≤).
ϵ^{-i}, for every natural i > 0,
are the negative powers of membership,
which are abstractions of (≤) ○‣ .ec(-i),
where .ec(-i) is the i-th relational composition of
the inverse of .ec.
.ɛɕ is the primary singleton map,
an auxiliary subrelation of ϵ
that is an abstraction of set membership between non-singleton sets
and singleton sets.
Objects are abstractions of sets in a suitable partial universe of well-founded
sets.
The universe is limited by a rank – both from above and below.
In particular, the empty set is not considered to belong to the universe.
r, the inheritance root, is a distinguished object,
that is an abstraction of the largest set within the partial universe.
The axioms of basic structures
are provided in a dedicated section.
Moreover,
there are two distinguished derived subrelations of ϵ:
.ɛϲ is the singleton map
–
an abstraction of set membership between (arbitrary) sets
and singleton sets,
∊ is the bounded membership relation,
which is an abstraction of
(.ɛϲ) ○‣ (≤)
and thus an abstraction
of set membership within the partial universe.
Finally, the most fundamental three relations
ϵ, ≤ and .ec have the following semantics:
≤ is an abstraction of set inclusion.
.ec is an abstraction of a relativized powerset operator.
That is,
if x is an object that is an abstraction of the set a,
then
x.ec is an abstraction of the set of all such subsets
b of a
such that both b and {b}
belong to the partial universe.
Since the empty set does not belong to the universe,
.ec and .ɛϲ are coincident on singletons.
ϵ equals (∊) ∪ (ϵ¯).
Distinguished subfamilies
The following distinguished families of basic structures can be singled out:
Metaobject structures
are those in which .ec is total and .ɛϲ is defined
for every object whose rank is not maximal.
They can be presented in the
signature
(O, ≤, r, .ec, .ɛϲ).
Complete structures
are partial universes with urelements, devoid of the empty set.
They
are superstructures
cumulatively built from the ground stage of memberless objects.
They can be expressed as (O, ∊)
–
that is, ∊ is the only definitory constituent,
just like ∈ in set theory.
Monotonic structures arise from
the (abstract) monotonicity condition
(ϵ) = (ϵ¯)
which is present virtually in all object-oriented programming.
Though not imposed in ontological languages such as RDF Schema,
it can be assumed that most real datasets are subject to monotonicity.
(In particular, the built-in RDFS structure is monotonic.)
In monotonic structures,
the term powerclass is interchangeable with eigenclass.
Monotonic eigenclass structures
are monotonic structures in which .ec is total.
This family can serve as the
essential mathematical model for the core structure of object technology.
This is for the following reasons:
The monotonicity condition poses no restriction in most parts
of object technology.
The .ec map can be completed for any basic structure.
The structures are axiomatized with 5 simple conditions
which can be stated with only a few preliminary definitions.
The structures are fully determined by ϵ:
x ≤ y ↔ x.ϵ⊇ y.ϵ
and
.ec is the unique map such that
(ϵ) = (.ec) ○‣ (≤)
(therefore,
ϵ arises as
the composition of infinite eigenclass regress with inheritance).
Canonical primary structures
are based on the Python object model.
They describe the instance-inheritance structure
that is thought to be canonical in the world of OOP.
Canonical eigenclass structures
are based on the Ruby object model.
In this document, these structures
are regarded as the standard core structures of OOP.
Up to a minor difference, there is a
duality
between the two families of canonical structures:
Canonical primary structures are obtained from canonical eigenclass structures
by omitting eigenclasses.
Conversely,
canonical eigenclass structures are obtained from canonical primary structures
by
eigenclass completion.
Connection between ϵ and ≤
The powerclass (.ec) and singleton (.ɛϲ)
maps provide a connection between membership
(ϵ) and inheritance (≤):
Using the concise notation of relational composition,
(.ec) ○‣ (϶) = (≥)
and
(ϵ) = (.ec) ○‣ (≤)
in a monotonic eigenclass structure,
(.ec) ○‣ (϶) = (≥)
and
(ϵ) = ((.ɛϲ) ∪ (.ec)) ○‣ (≤)
in a metaobject structure.
In monotonic structures, the singleton map .ɛϲ is a submap of
.ec.
The singletons are exactly the powerclasses from powerclass chains
that start in terminal objects
– which are objects that do not have any members or strict inheritance ancestors.
(In the sample structure,
s, u and v are terminals
and s.ec = s.ɛϲ and v.ec = v.ɛϲ
are singletons.)
Set-theoretic interpretation
Set-theoretic interpretation
of basic structures is summarized by
the table below.
Any basic structure S
can be identified with a set O
in the von Neumann universe of well-founded sets.
Let ℙ denote the standard powerset operator,
that is, for a set x,
ℙ(x) is the set of all subsets of x.
Moreover, let
ℙ_{₁}(x)
be the set of singleton subsets of x.
The constituents of S are then
obtained as follows:
Terminal objects
T
=
O∩ℙ_{₁}(∪O∖O)
Inheritance root
r
=
∪O∖∪T
For every x, y from O :
Bounded membership
x ∊ y
↔
x ∈ y
Inheritance
x ≤ y
↔
x ⊆ y
Singleton map
x.ɛϲ = y
↔
{x} = y
Powerclass map
x.ec = y
↔
r∩ℙ(x) = y
Power membership
x ϵ¯ y
↔
r∩ℙ(x) ⊆ y
Object membership
x ϵ y
↔
r∩ℙ(x) ⊆ y or x ∈ y
Simple cases of ϵ
To proceed further with the description of
ϵ, ≤ and .ec
(even before giving an account on history of implementation and documentation of
these structures)
we first do away with simple cases:
ϵ=∅ (purely prototypal structures),
ϵ≠∅ and
ϵ^{2}=∅ (bipartite structures).
For convenience, we also present the condition for the remaining
(i.e. non-simple) cases:
ϵ^{2}≠∅
(basic structures of ϵ and their specializations).
Purely prototypal structures
Purely prototypal object models are those which deny to institutionalize
any concept of a classification.
In accordance, a pp-core structure
is a structure
(O, ≤) such that
(pp~1)
≤ is a partial order on O.
By not presenting ϵ and .ec in the signature
it is implicitly understood that these relations are both empty.
We do not consider all prototype-based programming languages to have
a purely prototypal core structure.
In particular, in JavaScript
[],
ϵ≠∅.
We base this judgement on the following observations:
The expression x instanceof y can evaluate to true
for some x and y.
The notion of a class is supported in authoritative books about JavaScript
[].
Bipartite structures
Bipartite structures represent a
two-sorted view of ϵ which is characteristic for
static class-based languages like C++ or Eiffel.
Similarly to the previous case,
it is assumed that .ec is empty.
(This is also indicated by the adjective primary
since in theory, there can be bipartite structures that support
.ec on T.
However no such occurrence in object technology is known to the author.)
We might consider the additional condition of a single-rooted inheritance
(which is not satisfied in C++).
On the other hand,
(bp~4) is not to be imposed on
ontology languages.
Note that we did not mention the word object anywhere in the definition.
This is because we have disobeyed the two-sortedness
–
we unified the sorts
T and C into one set O.
In the two-sorted view of ϵ the term object is exclusively
reserved for elements of T.
This is expressed by:
This is in opposition to our approach.
We consider the core structure to be single-sorted
–
there is a uniform domain O of objects
on which the relations ϵ, ≤ and .ec are defined.
In particular,
Classes are objects.
The following table shows a division of significant representants of object technology
according to the composability of ϵ.
Note that there is a middle group
which takes a neutral approach:
For every class x, the reificiation of x
(x.reif) is an object.
The point of it is that reification can be overridden by
identity.
This approach seems to be supported in particular by the Java programming language.
In Java, the names of introspection methods like
getClass() or
getSuperclass()
suggest that it is a class what is returned, rather than its reification.
In the book Java reflection in action[], both
agreement and disagreement to the uniformity principle can be observed.
(According to page 23, classes are objects.
According to page 268, there is a
distinction between class and class object.)
The document describes the ultimate mathematical model of The Core
and its connection to set theory.
In particular, it is shown that object membership, ϵ,
arises by the following fundamental equality:
(ϵ) = (∊) ∪ (ϵ¯)
where ∊ is the bounded part, a well-founded relation,
and ϵ¯ is the monotonic part.
The main correspondence between (the core structure of)
object technology and set theory can be then expressed as
∊ ↔ ∈.
If objects have sufficiently many bounded members and .ec is total,
then all of ϵ, ≤ and .ec are
determined by ∊ so that the core structure can be expressed as
(O, ∊).
In a complete structure,
every non-empty subset of O.∍
equals the extension x.∍ of a unique object x.
Such a structure looks like a partial universe of sets,
given by the pair (ϖ+1, κ),
where
ϖ is a limit ordinal
that is the rank of the inheritance root r,
and κ
is the cardinality of the ground stage of urelement-like sets.
Every basic structure can be embedded
into such a partial universe.
The assumption of monotonicity ((ϵ) = (ϵ¯))
and of totality of .ec
results in the family
monotonic eigenclass structures.
This family has a simple description
(simpler than the general case of basic structures)
which is provided in the referred document.
The restrictions can be considered acceptable:
The monotonicity condition holds for the majority of object-oriented
programming and modelling.
A complete monotonic structure (O, ∊)
is obtained from a complete basic structure (V, ∊)
by the restriction to
hereditarily ↧-complete objects, i.e.
O= { x | x.∍= x.∍.↧⊆O }.
Historically, this document introduced the term object membership
(together with the ϵ symbol)
and
originally was the main document.
The (canonical) core structure of OOP arises by unifying core structures of
Ruby and Python.
It can be viewed as either
the Ruby core structure with multiple inheritance and
user-created explicit metaclasses allowed, or
the Python core structure equipped with eigenclasses.
The core structures of
Java, Scala, Smalltalk, Objective-C, CLOS or Perl
are viewed as modifications of the canonical structure.
(See also Specializations of ϵ.)
Additionally, refinement structures are described which provide linearization
of object's ancestors.
The document
provides a generalization of object membership as it applies to ontological structures
based on RDF Schema.
In contrast to object-oriented programming the following features are present:
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.
Inheritance does not have to be antisymmetric
– classes and properties can have distinct equivalents.
As already observed
on the example of the JavaScript programming language,
prototype-based languages cannot be, in general,
declared to be classless or to be devoid of the instance-of relation
(despite the traditional view []).
Moreover, it can be observed
that in the JavaScript core structure
(O, ϵ, ≤, r, .ec),
not only ϵ but also the .ec constituent is non-empty.
The following correspondence holds:
x.ec = y
↔
x == y.prototype.
That is, prototypes can be thought of as eigenclass predecessors of classes.
A summary of the referred document is provided in the
Prototypes section.
The document provides an explanation of the notion of a powertype in terms
of the core structure.
In particular, it is shown that, in a suitable axiomatic restriction,
the Cardelli's Power() operator coincides with .ec.
That is, Cardelli's power types are powerclasses in the abstract setting.
The only difference is that Power(x) is only defined
for Classes
(called types).
Subsequently, the adoption of powertypes in metamodelling is considered,
as well as powertype relationship in RDF Schema.
Historically, the Smalltalk programming language is of fundamental importance
to the core structure of object technology:
Smalltalk-76 is the first language in which ϵ^{2}≠∅,
Smalltalk-80 is the first language in which .ec ≠∅.
Unfortunately,
the .ec ≠∅ condition has not been reflected in
the terminology or documentation of Smalltalk-80.
As a consequence,
inconsistencies have been established
and so Smalltalk-80 became
the biggest obstacle for the description of the core structure of OOP,
at least for the author of this document.
The referred document collects evidence about the inconsistencies.
A consistent resolution of the terminology is provided in
a special section.
The document provides a detailed description of the Ruby Object Model
(as of version 1.9)
via abstraction refinement.
The object model is incrementally specified in the series of abstract structures
together with their possible transitions.
The most abstract, initial structure, denoted S0,
just introduces the basic nomenclature of objects:
terminals, classes and eigenclasses.
The next structure, S1, is the
core structure of Ruby
in the sense introduced at the beginning of this document.
The structure is (exactly what is) induced by
superclass and eigenclass links between objects.
The yet subsequent structure, S2, equips S1
with module inclusion lists
so that the complete inheritance structure is established
(referred to by MRO,
which stands for method resolution order).
There is an in-between structure,
denoted S1_{r} in
[],
which encompasses just the extension of the Ruby's (canonical) object membership,
ϵ,
to the full membership, ϵ•,
which can be introspected by the is_a? built-in method
(see also Specializations of ϵ).
There are more than 20 structures in the gradual description.
The
resulting structure
(still providing just an abstraction of the Ruby object model,
though far more detailed than S1) can be viewed as a naming multidigraph,
consisting of nodes and uniquely labelled arrows between them.
The document provides a set-theoretic representation of the core structure of Ruby
(again referred to as the S1 structure)
using the bottom stratum map .ϱ
between objects in an
(ω+1)-superstructure(V, ∈).
In contrast to the embedding presented in
[],
the embedding from
[]
maps all objects to elements of finite stages.
As a result, for objects x, y
whose metalevel index is lower than a predefined number k,
The document focuses on the description of the
S1 structure
using the material from the previous two documents.
In all these three documents,
object membership is expressed in the composition (.ec) ○‣ (≤),
the ϵ symbol is missing.
Moreover, ≤ is considered to be defined only between non-terminal objects.
Historically,
this document is the first description
(available at atalon.cz)
of the Smalltalk-80 correspondent of the Ruby's S1 structure.
The document can be regarded as a precursor to the
dedicated section.
The Wikipedia page
en.wikipedia.org/wiki/Eigenclass_model
containing the article
has been created in October 2012 by the author
of this document.
Several major edits followed until January 2013.
In October 2013, the page has been deleted
(changed to a redirect to
Ruby (programming language)#Semantics)
by Wikipedia administrators on the following grounds:
The article violates the NOR
principle (No original research).
The term eigenclass model is not an established topic in computer science.
For those interested in the article there is a short
list of corrections which
I would apply if the page was not deleted:
c(i)
replace by
c.ec(i)
other that
other than
(p~4)
extend with
and instances of each other.
History
The following table outlines the history
of object models whose core structures satisfy ϵ^{2}≠∅.
(⁎)Show me a list of documents (articles, books), possibly hundreds of items long,
that are not listed in the previous section.
If, in total, these documents say
about the abstract structure of ϵ, ≤ and .ec
more than one tenth
of what
documents inside of atalon.cz say,
then I remove my name from the table.
Bold font indicates that the introduction of Ruby
is regarded in this document to be the most significant
contribution to the development of the core structure of object technology.
We can guess that the Ruby core structure has been created
by rectification of Smalltalk-80 adopting the concept of universality of singletons
in Dylan.
This is best illustrated by samples from
Ruby, Smalltalk-80
and
Dylan.
The core structure by Forman & Danforth
In 1998,
a book by
Ira R. Forman and Scott Danforth has been published,
titled Putting Metaclasses to Work[].
The book provides an object model of class-based reflective programming languages
using the concept of a metaclass.
With some effort, a reduction of this model can be made to the core structure,
which concerns just
the ϵ and ≤ relations.
In the box below,
we provide an axiomatizaton of these structures
via the .class map and the ≤ relation.
The ϵ relation (referred to by isA in
[])
is obtained as the composition (.class) ○‣ (≤).
Notes:
Greyed conditions are not imposed
in [].
They are meant to show the correspondence to
canonical primary structures.
More specifically, after adding
(fd~6)(a) and
(fd~7)
and replacing objects by classes in (fd~8)
we obtain an equivalent to our axiomatization.
In the book, the set C of classes is introduced explicitly.
We have used an equivalent implicit definition.
The monotonicity condition
(fd~3) is the only axiom
that has a direct counterpart as a postulate of
[]
(Postulate 10, page 42).
Other conditions are mentioned as requirements
outside the list of postulates
or are obtained indirectly.
(fd~1) is asserted by
the requirement of the inheritance graph to be acyclic
(page 20).
(fd~2) is a price for having (O, ≤)
as a partial order.
(fd~4)
asserts that the one-element set {c}
is the only cycle of .class
(page 14, c is named Class).
(fd~5)
asserts the existence of an inheritance root
(page 25, r is named Object).
(fd~6) (b) and (c)
are asserted by Object is an instance of Class
and
Class is a subclass of Object, respectively
(page 25).
Preliminaries
Some familiarity with elementary algebra, order theory and set theory is assumed.
See
[] for details.
Well-foundedness
For a relation ϵ on a set X, an element x ∈ X is
well-founded in ϵ
if x is not a member of an infinite descending chain in ϵ, i.e.
if there is no infinite chain of the form
… x_{2}ϵ x_{1}ϵ x_{0}= x.
A relation ϵ on a set X is well-founded
if all elements x ∈ X are well-founded in ϵ.
Assuming the axiom of choice, this is equivalent to the condition that
every non-empty subset Y ⊆ X contains an element y that is
minimal in (Y,ϵ),
i.e.
there is no u from Y such that u ϵ y.
Rank
For a well-founded relation ∊ on a set X,
the rank function of ∊
(alternatively, the ∊-rank)
is a map r() from X to ordinal numbers such that for every
x ∈ X,
r(x) = sup {r(a) + 1 | a ∊ x}.
By well-founded recursion, there is exactly one such map.
Obviously,
r(x) = 0 ↔ x is minimal in ∊.
Moreover,
let the ∊-rank of a subset Y of X be
sup {r(a) + 1 | a ∈ Y},
let the rank of ∊ be the ∊-rank of X.
The instance-of relation
In class-based programming languages,
the instance-of relation is a fundamental mean to express similarity
between objects.
The relation links objects to classes.
Objects that are instances of a given class share behavior (and structure)
described by that class.
Let us write x ϵ y for
the object x is an instance of the class y.
By using the ϵ symbol (lunate epsilon) for the instance-of relation
we suggest the correspondence:
ϵ↭∈,
i.e
ϵ has the semantics of set membership, ∈.
The class y represents the set of all its instances.
Just like sets can share some elements, we allow classes to share instances.
That is, we consider ϵ in the weak sense
where an object can belong to several classes.
We might also speak about has-a-class as a synonym for instance-of.
There is a second point that should be noted in the expression x ϵ y:
both the object x and the class y are denoted by a lowercase letter.
This suggests that we are focused on programming languages
that support
the following uniformity principle of ϵ:
Classes are objects.
As a consequence, ϵ is a relation between objects.
If x ϵ y then the class y is a meta-object of x
in the sense that y is one of objects that provide description for x.
If x ϵ y and x is itself a class
(and so is every other potential instance of y)
then y is a metaclass.
In fact, the occurrence of the notion of a metaclass
in publications about a particular programming language
is a good indicator that the language supports handling of classes as objects.
Sample structure
The following diagram shows a sample structure of the instance-of relation.
The structure contains 7 objects: 4 classes and 3 ordinary objects.
The instance-of relation is displayed by dark blue arrows:
x ϵ y iff there is a blue arrow from x to y.
For an object x we denote x.϶ the set
of all instances of x and call it the extension of x.
Ordinary objects have empty extension.
The sample structure is saturated in the sense that classes are distinguishable
by their instances: different classes have different extensions.
This allows to derive a partial order,
denoted ≤, and called inheritance,
between the 7 objects by:
x ≤ y iff
x = y or
∅≠ x.϶⊂ y.϶.
If x ≤ y then
x is said to be an (inheritance) descendant of y
which is in turn an (inheritance) ancestor of x.
We also let < denote the reflexive reduction
(the strict inheritance)
of ≤ in the obvious sense.
The inheritance relation is shown as a Hasse diagram
in the transitive reduction of <
by green arrows between classes.
Ordinary objects are not involved in <.
The sample structure only has single inheritance
— every object has at most one inheritance parent.
x ≤ y
iff
x
→ …
→ y
x ϵ y
iff
x → y
y.϶= { x | x ϵ y }
o.϶= {s, u, v, A, B, o, c}
c.϶= {A, B, o, c}
A.϶= {s, u, v}
B.϶= {u, v}
Note that every object has a class that is least in inheritance.
For an object x let us denote x.class such a class
and call it the class of x.
If x.class = y then we also say that x is a
direct instance of y.
Thus, the .class map forms a subset of ϵ,
distinguished by thick blue arrows in the diagram.
The instance-of relation can be recovered
from the .class map and inheritance by their composition,
i.e. (ϵ) = (.class) ○‣ (≤)
where the composition symbol ○‣ is interpreted left-to-right.
The equality can be read as:
x is an instance of y iff
the class of x is an inheritance descendant of y.
Observe that classes o and c are circular –
they are instances of itself.
Moreover, every object is an instance of o
and classes are exactly the instances of c.
Structure creation
In a programming language,
o and c are distinguished built-in
classes, usually named Object and Class, respectively.
The remaining part of the structure is built incrementally,
by adding user classes A and B and their instances
s, u and v, one by one.
Each of the addition of these five user objects
x can be formally expressed as class instantiation:
x = q.new(p_{1}, …, p_{n})
where q is the requested class of x
and p_{1}, … p_{n}
are the requested parents (direct inheritance ancestors) of x.
For ordinary objects, the assignment reduces to x = q.new()
which we further abbreviate to x = q.new.
Since the sample structure only has single inheritance,
new class creation can be expressed by
x = c.new(p) with the single requested parent p.
As a result, the structure is built by the following five assignments:
This line of pseudocode (with ; used as a delimiter between the assignments),
if preceded by o = Object and c = Class,
is a valid line of code in the Ruby programming language
for the creation of the sample structure.
Adding inheritance to the signature
Let us denote
O_{0}= {o,c},
O_{1}= O_{0}∪ {A},
…,
O_{5}= O_{4}∪ {v} =Ō
so that O_{0} is the set of built-in objects of the sample structure
and for each i = 1, …, 5,
the set O_{i} corresponds to
an addition of a single object into the structure.
Note that most of the intermediate structures (O_{i}, ϵ)
do not satisfy the extensionality principle that allowed us
to distinguish classes as objects with non-empty extension
and to derive inheritance via inclusion of class extensions.
To capture also the intermediate structures,
the inheritance relation has to be prescribed explicitly.
Therefore, we extend the signature from
(Ō, ϵ) to
(Ō, ϵ, ≤).
We call this instance-inheritance
structure the primary structure of ϵ.
Note that since (ϵ) = (.class) ○‣ (≤)
we can use the signature (Ō, .class, ≤) as well.
The sample expressed in relevant languages
This section demonstrates the presence of the instance-of relation
in object oriented programming and modelling.
It is shown how the sample structure
can be created and introspected in various prominent programming languages.
An example of an ontological language is provided too.
Where applicable, a diagram is provided showing how the sample structure
is obtained as a restriction of a finer structure.
In Ruby
The Ruby programming language allows a uniform expression of the sample structure.
Every (user) object can be created via the new method.
The instance-of relation between the 7 objects can be detected via
the is_a? method (aliased as kind_of?).
In the restriction to classes, the <= method corresponds to ≤.
The .class map is provided by the class introspection method.
o = Object
c = Class
A = c.new # class A; end
B = c.new(A) # class B < A; end
s = A.new
u = B.new; v = B.new
In Python
o = object
c = type
A = c('A', (), dict()) # class A(): pass
B = c('B', (A,), dict()) # class B(A): pass
s = A()
u = B(); v = B()
In Python, new instances are created by calling classes.
Also the classes A and B can be created this way,
though not so transparently as in Ruby.
The instance-of relation between x and y is detected
by isinstance(x,y).
Inheritance between classes x, y is detected by:
x < y iff issubclass(x,y).
For every object x,
the expression type(x) returns the class of x.
In JavaScript
Traditionally,
prototype-based programming languages are regarded to
be classless and thus devoid of the instance-of relation.
However, as we have already
mentioned before,
we do not consider this characteristics to be applicable to JavaScript.
The diagram below demonstrates that JavaScript
allows for the creation of our sample structure.
(So that all of o, c, A and B
are examples of JavaScript classes.)
Every (user) object can be created via the new operator.
The instance-of relation between the 7 objects can be detected via the
instanceof operator.
The .class map is provided by the constructor property.
Inheritance between classes can be detected via the isPrototypeOf method
as follows:
x < y iff
y.prototype.isPrototypeOf(x.prototype).
Observe that in contrast to the Ruby sample,
the additional objects of the finer structure are drawn on the opposite
(i.e. left) side.
This is because Ruby supports implicit containers (eigenclasses),
whereas JavaScript supports implicit members (prototypes).
Note:
To simplify the code, inheritance between B and A
is achieved using the non-standard property __proto__.
o = Object; c = Function
A = new c
B = new c; B.prototype.__proto__ = A.prototype
s = new A
u = new B; v = new B
In Smalltalk
Smalltalk-80 (as of Pharo or Squeak) only allows creation of classes via the
subclass: method.
The instance-of relation between the 7 objects
corresponds to the isKindOf: introspection method.
The introspection method named class only partially corresponds to
the .class map: while it agrees on ordinary objects, it disagrees on classes.
o := Object. c := Class.
o subclass: #A.
A subclass: #B.
s := A new.
u := B new. v := B new.
In Java
class A {}
class B extends A {}
class Xx {
public static void main (String[] xx) {
Object
o = Object.class,
c = Class.class,
A = A.class,
B = B.class,
s = new A(),
u = new B(), v = new B();
}
}
In the Java programming language, classes can be regarded as objects
due to the reification facility.
For a class named A, the class object of A
is referred to by A.class.
Note that in contrast to Ruby,
A.class does not refer to the class of the class named A.
As a consequence, there is a notational duality between (non-reified) classes
and their object counterparts.
The instance-of relation between objects x and y
where y is known to be a reified class named Y
can be detected either via
x instanceof Y, or
y.isInstance(x).
The (reified) class of an object x equals x.getClass().
If x is a (reified) class other than o,
then x.getSuperclass() is
the (reified) inheritance parent of x.
Note that the method names
suggest that it is a class what is returned, rather than a class object.
In Scala
var o = classOf[Object]
var c = classOf[Class[_]]
class A
class B extends A
var s = new A
var u = new B; var v = new B
Scala adopts the Java's concept of reification of classes.
For a class named A,
the expression classOf[A] refers to the class object.
Note again that classOf[A] is not the class of A.
Introspection facilities for the instance-of relation and inheritance between
classes are similar to those of Java.
In Dylan
let o = <object>;
let c = <class>;
let A = make(c);
let B = make(c, superclasses: list(A));
let s = make(A);
let u = make(B); let v = make(B);
The Dylan programming language fully supports the
classes are objects principle
[].
Every user object can be created
via the make method.
Inheritance between classes is detected via subtype?,
the instance-of relation between objects and classes is detected via
instance?.
Finally, the object-class method is the exact correspondent to the
.class map.
In CLOS
According to authoritative publications
[][],
the Common Lisp Object System (CLOS)
fully conforms to the classes are objects principle.
(However, there is still some sort of notational distinction for classes.)
The instance-of and inheritance relations between objects can be detected via
the built-in
typep and subtypep methods, respectively.
(defvar o (find-class 'standard-object))
(defvar c (find-class 'standard-class))
(defvar A (make-instance c :name 'A))
(defvar B (make-instance c :name 'B :direct-superclasses (list A)))
(defvar s (make-instance A))
(defvar u (make-instance B)) (defvar v (make-instance B))
Gray color in the code indicates that
we consider two possible interpretations of
c,
shown in the diagrams below.
In the (a) case,
the class map between the 7 objects is provided by the class-of method.
(a) c corresponds to standard-class
(b) c corresponds to class
In RDFS
In RDF Schema,[][]
objects are called resources.
Our sample structure is obtained from the RDF graph entailed by the
following set of RDF triples
expressed in Turtle syntax [].
The example prefix ex: is used for the user-created objects.
The sample built-in classes o and c are those
named rdfs:Resource and rdfs:Class, respectively.
The rdf:type property stands for the instance-of relation, ϵ.
Inheritance between classes is expressed via the rdfs:subClassOf property.
In Objective-C
The diagram below shows how the sample structure can be interpreted
in Objective-C.
The o and c classes are coincident,
so that the sample structure contains one object less.
The diagram also indicates that there is a non-degenerate interpretation,
with c set to the gray object labelled by
c.
In this document, we prefer the first interpretation,
since we do not consider the gray object to be a class.
@interface A: NSObject; @end
@interface B: A; @end
@implementation A; @end
@implementation B; @end
int
main(int argc, const char *argv[]) {
id
o = [NSObject class],
s = [A new],
u = [B new], v = [B new];
return 0;
}
The instance-of relation can be detected via the isKindOfClass: method.
The class_getSuperclass method can be used for the introspection of
inheritance between classes.
Similarly to Smalltalk-80, the class introspection method only agrees with
the .class map on ordinary objects.
For a class x, the expression [x class] evaluates to x.
(This is in contrast to Smalltalk-80,
where x class is always different from x.)
In Perl
In Perl 5, the instance-of relation, ϵ, deviates from the standard
(represented by the sample structure) in a substantial way.
In the restriction to classes, ϵ coincides with inheritance, ≤.
As a consequence, there is a total circularity between classes:
every class is an instance of itself, and even
every class is the class of itself.
The instance-of relation can be detected by the isa introspection method.
The semantics of ϵ is then adhered to by method lookup.
[]
The diagram below shows the sample structure in the correspondent modification.
package UNIVERSAL { sub new { bless {}, $_[0] } }
package A { }
package B { our @ISA = A }
my
$o = UNIVERSAL,
$s = A->new,
$u = B->new, $v = B->new;
Refinement by implicit containers
In the primary structure (Ō, ϵ, ≤) introduced above,
every non-built-in object is explicitly created by class instantiation.
(As shown by the Ruby or Python code,
classes themselves are created by instantiation of c.)
As a consequence,
every class is the most specific descriptor for its direct instances.
Equivalently,
objects instantiated by the same class have the same description.
In particular,
every class has the same set {c, o} of describing classes
in (Ō, ϵ, ≤).
Eigenclasses
The instance-of relation can be refined by adding implicit containers.
In the following diagram,
the sample structure(Ō, ϵ, ≤) is extended to
(Ō', ϵ, ≤) in such a way
such that every object x from Ō has its own
implicit meta-object, the eigenclass of x,
denoted x.ec.
Therefore,
Ō' =Ō⊎Ō.ec,
where Ō are the primary objects, and
Ō.ec are eigenclasses.
The x ↦ x.ec assignment is displayed by gray left-to-right arrows.
x ϵ y
iff
x
→ …
→⇢→ …
→
y
The inheritance relation is extended to Ō' as follows.
For every x, y from Ō,
x.ec ≤ y.ec iff x ≤ y,
(That is, .ec is an order embedding of
(Ō, ≤) into (Ō', ≤).)
x.ec ≤ y iff x ϵ y,
x ≰ y.ec.
Object membership
The ϵ relation, extended to Ō', equals
(≤) ○‣ (.ec) ○‣ (≤).
In contrast to inheritance,
we do not preserve the instance-of term for ϵ.
Instead, we call the ϵ relation object membership.
If x ϵ y then x is said to be a member ofy.
We can also say that y is a container ofx.
Proposition:
For every x, y from Ō,
x ϵ y iff x.ec ≤ y.
That is,
x.ec is the least container of x. In particular,
x ϵ x.ec and
x.ec < x.class.
The refined class map
Just like every object x in the primary structure has x.class
as the unique least class that has x as its instance,
in the refined structure (Ō', ϵ, ≤),
every object has a unique least container.
For an object x we denote x.aclass such a container,
and call it the actualclass of x.
In the diagram below, the .aclass map is shown by blue links.
x ϵ y
iff
x
→→ …
→
y
Observations:
The .aclass map coincides with .ec on primary objects
and equals the the composition .ec^{−1}.class.ec on eigenclasses.
(ϵ) = (.aclass) ○‣ (≤).
Support in programming languages
Of the languages mentioned above,
only Ruby supports refinement presented in the previous subsection.
There are some languages that provide partial support.
In Smalltalk-80 and Objective-C, each class has its own implicit metaclass.
In Scala, the object construct can be used to create
ordinary objects that have its own meta-object.
In Dylan,
all the 7 eigenclasses have a correspondent but the .aclass map is
different
(see the sample structure).
In Objective-C
The refinement of the
sample primary structure
for Objective-C
is shown on the following diagram.
Blue links correspond to isa pointers,
green links to super_class pointers.
[]
id
e = object_getClass(o),
f = object_getClass(A),
g = object_getClass(B);
The implicit metaclasses e, f and g are created
together with classes o
(the built-in NSObject class), A and B, respectively.
In Scala
The structure on the following diagram can be created using the object
construct for s and v instead
of the new operator used in the
primary sample.
object s with A
val u = new B
object v with B
val e = s.getClass
val g = v.getClass
Eigenclass completion
The structure (Ō', ϵ, ≤) still provides only partial refinement
since the pattern has only been applied to primary objects.
A complete refinement arises when eigenclasses themselves have eigenclasses.
We can extend Ō' to Ō'' by eigenclasses of
Ō',
then extend ≤ and ϵ accordingly,
then extend Ō'' to Ō''' by eigenclasses of
Ō'', and so on.
This leads to infinite eigenclass chains.
The resulting structure (O, ϵ, ≤)
has infinitely many objects
and can be characterized as an
embedding of inifinite regress into inheritance.
Full uniformity of the structure provides the following simplifications:
Object membership, ϵ,
equals the composition (.ec) ○‣ (≤),
i.e. an object x is a member of an object y
iff x.ec is an inheritance descendant of y.
(However, the equality (ϵ) = (≤) ○‣ (.ec) ○‣ (≤)
is still valid.)
Inheritance is obtained from ϵ as inclusion of sets of containers.
Therefore, the structure can be expressed in the simple signature
(O, ϵ).
The core structure of Ruby
In this section we describe the completely refined structure
(O, ϵ, ≤) anew,
using Ruby as the definitive sample language.
The recapitulation allows us to establish
consistent notation and terminology.
Sample structure
The following diagram shows a sample for the description of the core structure
of Ruby.
Note that the structure is just the eigenclass completion of the
sample primary structure except that
the s object is removed to simplify the diagram, and
all four circular classes of Ruby 1.9 are contained in the structure,
not just Object and Class.
(Ruby 1.9)
r = BasicObject
c = Class
class A; end
class B < A; end
u = B.new
v = B.new
There are infinitely many
metalevels,
indexed 0, 1, 2, ….
The structure is built using two sorts of links.
Green links correspond to the superclass introspection method.
A green line going from an object x upwards to an object y indicates
that y is an (the) inheritance parent of x.
For curved lines (those starting at the top of metalevel 2 and higher)
the upward direction is
expressed explicitly by an arrow.
All the other superclass links are drawn as a Hasse diagram.
Gray arrows (directed left-to-right) show the infinite regress of meta-objects.
Each object x has its own meta-object,
called the eigenclass of x,
which is one metalevel higher than x.
The prefix eigen stands for own
– different objects have different eigenclass.
In the Ruby comunity, the term eigenclass appeared around the year 2005.
Previously, the term singleton class has been used.
As a (historical) consequence, the corresponding introspection method is named
singleton_class.
We use the notation x.ec for the eigenclass of x,
so that x.ec corresponds to x.singleton_class.
The .ec map is then the eigenclass map shown by gray arrows.
Furthermore, let x.ec(i) be the i-th application of .ec
to x.
Components of the .ec map are eigenclass chains
of the form x, x.ec, x.ec(2), x.ec(3),
….
The inverse of .ec is denoted .ce.
For x from O.ec,
x.ce is the eigenclass predecessor of x.
Let .ec^{∗} be the reflexive transitive closure of
.ec.
For an object y, let y.pr be the primary object
of y, that is, the first object of the eigenclass chain
y.pr.ec^{∗} to which
y belongs.
Inheritance and membership
The reflexive transitive closure of green links is the inheritance relation
between objects, denoted ≤.
Since the superclass links are acyclic, ≤ is a partial order.
We also let < denote the strict inheritance
with the obvious meaning.
It can be observed that
the eigenclass map is an order-embedding with respect to inheritance.
For every objects x, y,
x ≤ y iff x.ec ≤ y.ec.
Object membership, ϵ,
equals the composition (.ec) ○‣ (≤),
i.e. an object x is a member of an object y
iff x.ec is an inheritance descendant of y.
For a positive natural n, let ϵ^{n} denote the
n-th composition of ϵ with itself,
that is, ϵ^{1} equals ϵ and for objects x, y
x ϵ^{n} y
↔
x = x_{0}ϵ x_{1}ϵ ⋯ ϵ x_{n-1}ϵ x_{n}= y
for some objects
x_{1}, …, x_{n-1}.
For now,
we consider ϵ^{0} to be equal to the identity relation between objects.
Later in this document,
we redefine ϵ^{0} to ≤
according to the definitions for basic structures.
The reflexive transitive closure of ϵ is denoted
ϵ^{∗}.
We also introduce a notation for images and preimages under ≤ and ϵ.
x.↥ (resp. x.↧)
denotes the set of (non-strict) ancestors (resp. descendants) of an object x.
Similarly, for a set X of objects,
X.↥ (resp. X.↧)
is the upset (resp. downset) of X.
x.ϵ (resp. x.϶) is the set of all containers (resp. members) of
an object x.
x.ϵ^{∗} is the set
x.ϵ^{0}∪ x.ϵ^{1}∪ x.ϵ^{2}∪ ….
Observe that for every objects x, y,
(1)
x.↧= x.ec.϶
(descendants of x are exactly the members of x.ec),
(2)
x.ϵ= x.ec.↥
(containers of x are exactly the ancestors of x.ec),
(3)
x ≤ y iff x.ϵ⊇ y.ϵ
(x is a descendant of y iff
every container of y is also a container of x),
(4)
x.ec = y iff x.ϵ= y.↥
(the eigenclass of x is the least container of x).
Conditions (1) and (2) are the
(≥) = (.ec) ○‣ (϶) and
(ϵ) = (.ec) ○‣ (≤) equalities, respectively.
As a consequence of (3) and (4),
the whole structure (O, .ec, ≤)
is given just by object membership, (O, ϵ).
Note that the first equivalence implies that
ϵ is co-extensional –
objects are distinguished by their containers.
In contrast, ϵ is typically not extensional.
Direct inheritance
Green links in the diagram correspond to direct (strict) inheritance
– the reflexive transitive reduction of ≤.
We might sometimes use the ≺ symbol for this relation.
If x ≺ y then x is an (inheritance) child of y
and y is an (inheritance) parent of x.
We will mostly refer to direct inheritance through its image map, .parents.
For an object x, x.parents
(as an abbreviation of {x}.parents) denotes the set of inheritance parents
of x.
The notation is adapted to multiple inheritance.
If single inheritance is asserted, we can use the .sc notation for
≺ so that x.sc = y iff x ≺ y.
For an object x, the object x.sc,
if defined, is the superclass of x.
The core structure of Ruby can be then expressed as
(O, .ec, .sc).
[]
Membership as is-a
The object membership relation, ϵ, between the objects of
the
sample structure
can be detected in Ruby by the is_a? introspection method.
The method is aliased as kind_of?.
(There is also the Class#=== introspection method,
which detects the inverse relation, ϶.)
If x is a member of an object named B
then one can say that xis-aB.
The set B.϶ of all members of B
can be referred to as Bs.
This convention can be used for nomenclature of objects.
Moreover,
there can be a distinction between the names that are built using this convention
(these names are capitalized and styled)
and those names that are not.
In Ruby,
the built-in classes Object, Module and Class
provide such a distinction.
Objects are objects that are not blank slate objects.
Modules are modules together with Classes.
Classes are classes together with eigenclasses.
Note in particular that we regard is-a as another name for object membership,
ϵ, not for inheritance, ≤.
Unfortunately,
in object modeling, and in most publications about object oriented programming,
is-a corresponds to inheritance.
The reasoning goes as follows.
If A and B are classes
such that A ≤ B (A is a subclass of B)
then one can say that
anAis aB,
meaning that an instance of A is also an instance of B.
The sentence structure can be expressed as
an-A is a-B (two pairs of article-noun and a verb between).
However, the longest characteristic subsequence is is a which leads
to another hyphenation and to saying that
there is an is-a relationship between
A and B.
This is in turn abbreviated to Ais-aB
(so that the A's article is dropped and the B's article is
secluded from B),
meaning that the (A,B) pair belongs to the is-a relation.
This abbreviated statement then becomes ambiguous since one way to interpret it is
theAis aB
which is fundamentally different from the original statement.
Note:
The two different meanings of is-a have been analyzed by R. Brachman
[][].
The ϵ meaning is called individual/generic and is exemplified by
Socrates is a man.
The ≤ meaning is called generic/generic and is exemplified by
a cat is a mammal.
The ambiguity of is-a can be resolved
according to the adherence to the
uniformity principle
stated in the introduction.
If classes are not considered to be objects (individuals)
then is-a is resolved in favor of ≤.
Otherwise, if classes are among objects (as is our assumption)
it is reasonable to interpret is-a as ϵ.
At present, this second interpretation is supported only rarely.
The Ruby introspection method is_a? and the Objective-C isa pointers
are two notable examples.
Others can be found in publications about Smalltalk
[]
or Self
[].
As mentioned before, another example is the book by Forman and Danforth
[]
which uses isA for ϵ.
Basic nomenclature of objects
We introduce the basic nomenclature of objects according to the following diagram.
O
…
objects
=T⊎C⊎O.ec
O.ec
…
eigenclasses
O.pr
…
primary objects
=O.c =T⊎C
T
…
terminals
=O∖r.↧
C
…
classes
=O.pr ∖T
H
…
helix objects
=r.ϵ^{∗}=r.↧.he=R.↥
R
…
reduced helix
=r.ec^{∗}=r.↧.re
r
…
inheritance root
c
…
metaclass root / instance root
r.↧
…
Classes
=c.϶=O.ϵ.↧
c.↧
…
metaclasses
=C.class.↧
r.ec(i).϶∖r.ec(i).↧
…
i-th metalevel
We denote O the (infinite) set of all objects.
O.ec
(the image of the eigenclass map, shown right to the black line)
is the set of eigenclasses.
O∖O.ec
(objects that are NOT eigenclasses, to the left of the black line)
is the set of primary objects.
T denotes the set of
terminal objects or just terminals
– objects without members and without strict ancestors.
C is the set of classes, the primary non-terminal objects.
r is the inheritance root.
It is the highest non-terminal object, w.r.t. inheritance.
c
is the instance root and is also called the metaclass root
and named Class.
It is the unique inheritance parent of r.ec.
R
is the set of objects from the eigenclass chain of r,
the reduced helix.
H
is the set of helix objects – objects x such that x ϵ x.
Note that H=R.↥.
Previously, we used the term ordinary objects for elements of T.
The new terminology is similar to that introduced in the ObjVlisp model
[][][]
where the term terminal instances is used.
Note that for an object x the following are equivalent:
x is non-terminal.
x is a Class
(i.e. x is a member of the c object which is named Class).
x is an inheritance descendant of r
(i.e. x ≤r).
In particular, non-terminal objects can be referred to as Classes.
The terminology for the set H=r.ϵ^{∗}
is based on the similarity
of the diagrammatization of (H, ≤)
with a right-infinite helical curve.
Classification systems
By a classification system
we mean a closure system Y on Classes.
I.e. it is a set of distinguished non-terminal objects such that
every non-terminal x has a least ancestor from Y.
Equivalently, Y is such that
every object x has a least container from Y.
If .y is the corresponding closure operator
(that maps a non-terminal object to its least ancestor from Y),
then the corresponding classification map
(that maps any object to its least container from Y),
equals .ec.y.
Observe that since both .ec and .y are monotone,
any classification map is monotone, i.e. for every objects a, b,
if a ≤ b then a.ec.y ≤ b.ec.y.
Note that the sets C, R and H
are all classification systems.
(In fact, since in Ruby the inheritance on Classes forms a tree,
any subset of O∖T containing r
is a classification system.)
We denote the corresponding closure operators by
.c, .re and .he, respectively.
In the case of .c, we extend the definition to all objects:
we let .c to be the closure operator
corresponding to the closure system C⊎T
in (O, ≤).
This allows us to conveniently express the set of all primary objects as
O.c.
Metalevels
The set R is the classification system for metalevels.
An object x belongs to the i-th metalevel
(and therefore has the metalevel indexx.mli equal to i)
iff x.ec.re =r.ec(i).
Further observations:
The set T of terminal objects is the metalevel 0.
For i > 0,
the i-th metalevel has a top, equal to r.ec(i-1).
The i-th metalevel, i ≥ 0, equals the set
r.ec(i).϶∖r.ec(i).↧.
For an object x, the metalevel index x.mli
equals the cardinality of x.↥∩R.
The last metalevel containing a primary object is isomorphic to any higher metalevel
(via .ec(i) for a suitable i).
Classes and the .class map
The set of allClasses forms a
trivial classification system,
with .ec the corresponding classification map.
However, the eigenclass map is not useful for classifying objects since
different objects have different eigenclass,
so that each object is classified as different from every other object.
The most important classification system
is the set C of primary non-terminal objects.
Objects from C are called classes.
The corresponding classification map is denoted .class.
(So that .class = .ec.c.)
For an object x,
the object x.class is said to be the class ofx.
Note that the just introduced meaning of class and class-of
possesses the following fundamental consistency:
The class of x is the least container of x that is a class.
Further observations:
Classes are primary Classes.
Classes are classes together with eigenclasses.
x.class ≠ x.ec for every object x.
The .class map is derived
from the eigenclass map and the inheritance relation.
The distinguished objects r and c are classes.
The .class map forms a tree rooted at c.
In particular, c is the only object that is the class of itself.
Unlike eigenclasses, classes cannot be in general expressed as O.class
(the image of the class map).
The diagram on the right shows the class map for the
sample structure,
in the restriction to primary objects.
To illustrate the .ec.c composition,
the arrows are drawn along eigenclass paths.
In Ruby, all classes reside in the metalevel 1.
As a consequence, .class.class maps constantly to c.
The Ruby introspection method named class is in 100% correspondence
with the .class map.
The instance-of relation
Just like the .class map is a coarsement of the eigenclass map,
the composition (ϵ) ○‣ (.c) is a coarsement of object membership.
This relation is called instance-of
and can be equivalently defined as the range-restriction of ϵ to classes,
i.e. for objects x, y,
x is an instance ofy iff
x ϵ y and y is a class.
The .class map, taken as a relation, is called direct-instance-of.
Note that the term instance as such does not distinguish any objects.
Every object is an instance of some class.
In particular, every object is an instance of the inheritance root r
and every object is a direct instance of its class.
By allowing indirect instances
our terminology follows the semantics of
the isinstance() method of Python
or the instanceof operator from Java.
In Ruby, the introspection method instance_of?
corresponds to direct-instance-of.
(However, the Ruby Specification []
allows indirect instances.)
Note that
if y is the eigenclass of x then
x.instance_of?(y)
always evaluates to false.
An object is never an instance of its eigenclass.
Metaclasses
In order to establish a correspondence with other programming languages,
we introduce the term metaclass:
Metaclasses are exactly the inheritance descendants of c
(including c itself),
so that the set of all metaclasses can be expressed as c.↧.
This in particular ensures
that classes of classes (C.class) are metaclasses,
as well as the classes of eigenclasses (O.ec.class).
Observations:
The c class is the only metaclass from metalevel 1.
The set of all metaclasses other than c can be expressed
as r.ec.↧
– it consists of all objects from metalevel 2 or higher.
Suppose that our sample structure has been extended by
w = Module.new so that the Module class
(which is the parent of c) has a terminal member w.
Then
metaclasses are exactly the Classes
that do not have terminal members.
Metaclasses are said to be explicit or implicit
according to whether they are classes or eigenclasses, respectively.
Note that by naming the eigenclass c.ec by Metaclass
we could express the set c.↧ (=c.ec.϶)
as Metaclasses.
This suggests to define metaclasses as the primary Metaclasses
just like classes are primary Classes.
However, this would require an additional term for non-primary Metaclasses.
Moreover, the explicit / implicit adjectives seem to be an
established convention.
[][][]
Eigenclass actuality
Since eigenclass chains are infinite they must be lazily evaluated.
There can be only finitely many objects that are actually represented (allocated).
We call such objects actual.
A natural direction for evaluation of eigenclass chains
is that of the eigenclass map:
if x.ec is actual then x must be actual.
Let all primary objects be actual,
so that the set of actual objects forms a closure system in
(O, ≤).
We denote .a the corresponding closure operator
and let .aclass = .ec.a be the classification map.
For an object x, x.aclass is the actualclass ofx
– the least ancestor of x.ec that is actual.
The set O.a of all actual objects is
the actuality extent.
We can view the (O, ϵ, .a)
structure as an implementation-oriented refinement of (O, ϵ).
In particular, x.aclass can be regarded as
the actual startpoint of method lookup for x
– non-actual eigenclasses between x.ec and x.aclass
are skipped.
The diagram below shows
the actuality extent of allocated objects
for the sample structure.
The extent arises
after opening the eigenclasses of A and v.
The actualclass map (in the restriction to actual objects) is shown by blue arrows.
Note that the map forms a tree rooted at c.ec(2).
(Ruby 1.9)
r = BasicObject
c = Class
class A; end
class B < A; end
u = B.new
v = B.new
class << A; end
class << v; end
Note that the eigenclasses A.ec(2) and B.ec
have been allocated but not opened.
This is an implementation feature of Ruby.
Every newly created class x has its eigenclass allocated.
When the eigenclass x.ec(i) is evaluated
(e.g. by class << x; end for i = 1)
then
MRI/YARV
makes sure
that x.ec(i+1) is allocated.
As a consequence,
we can distinguish 2 actuality extents:
one for actually referenced (evaluated) objects
and a larger one for allocated objects.
As already mentioned, the diagram shows the structure for the larger extent.
Objects that have been allocated but not referenced are shown
in light blue.
The actualclass map shown by blue links could be denoted .klass,
since it is maintained by the implementation
via the klass field in the C source.
Note that there cannot be an introspection method for .klass
due to the probe effect.
There could only be an introspection method
for the actualclass map for the smaller extent,
but even this is not supported since
it is considered to be an implementation property.
The reason for having an extra object allocated in each eigenclass chain of classes
is an efficient update of the actualclass map
for inheritance descendants.
This does not affect terminal objects (or their eigenclasses).
Since they cannot have descendants,
they do not need to have their eigenclass allocated.
The core structure of Smalltalk-80
The Smalltalk-80 programming language is the first language which
introduced the refinement of the instance-of relation by implicit objects.
Simultaneously, Smalltalk is one of the first proponents of the
classes are objects pattern.
Unfortunately, the Smalltalk-80 core structure possesses uniformity deficiencies
which were compensated by equivocal terminology in the Smalltalk's literature.
[]
To describe the Smalltalk-80 counterpart of the
Ruby core structure
we use a specially restrained terminology in which the following
terms are (at first) avoided:
Class — we do not say which objects are classes and which not.
Metaclass — we do not say which objects are metaclasses and which not.
Class-of.
We do not say what is the class of an object.
In particular, even if the expression
x class evaluates to y
we do not say that y is the class ofx.
Instance-of.
We do not say what it means for objects x and y that
x is an instance ofy.
Sample structure
The following diagram shows a sample core structure of Smalltalk-80.
The structure consists of 18 objects with oriented links between them.
There are two sorts of links.
The green links correspond to the superclass introspection method.
There is a single line for which the upward direction is
expressed explicitly by an arrow.
All the other superclass links are drawn as a Hasse diagram.
The blue links correspond to the class introspection method.
A blue line starting at x and ending in y
(with an arrow head pointing to y)
indicates that
the expression x class evaluates to y.
(Pharo 1.3 / Squeak 4.2)
r := ProtoObject.
c := Class.
mc := Metaclass.
Object subclass: #A.
A subclass: #B.
u := B new.
v := B new.
The horizontal dashed line indicates the division of the structure into
the built-in part (above the line) and the user-created part.
In the code right to the diagram,
first distinguished built-in objects are denoted
(by r, c and mc) and
subsequently the user-part of the structure is created.
The built-in part forms a substructure
—
it contains exactly the objects reachable from the mc object
via a combination of blue and green links.
(Note that the substructure is generated by any single object it contains,
not just mc.)
Moreover, it is a minimum (nonempty) substructure,
since the mc object is reachable from any object
(via at most 3 blue links).
Metalevels
The sample diagram shows 3 types of blue links.
The curved blue links point to the mc object.
The straight left-to-right links precede the curved links.
Each curved link is preceded by exactly one straight link.
The remaining, broken-line links precede the straight links,
but without a one-to-one correspondence.
The division of blue links induces a division of objects into 3 metalevels.
The metalevel 2 consists of all objects x such that
x class == mc.
The metalevel 1 consists of all objects x such that
x class class == mc.
The metalevel 0 consists of all remaining objects.
For every x from the metalevel 0,
x class class class == mc.
However, this equality cannot be used to distinguish the metalevel 0
since it also holds for every object from the metalevel 2.
The sample structure contains 8 objects from metalevel 2 (shown in gray),
8 objects from metalevel 1,
and 2 objects from metalevel 0 (denoted u and v).
Uniformity deficiency No. 1
Observe that the blue links provide the following mappings between metalevels:
Objects of metalevel 0 are mapped to objects of metalevel 1,
possibly many-to-one.
Objects of metalevel 1 are mapped to objects of metalevel 2
in a one-to-one correspondence.
Objects of metalevel 2 are constantly mapped to the distinguished object mc
from metalevel 1.
This reveals a defect of uniformity of the
Smalltalk-80 object model:
Objects from the metalevel 1 have each an individual (meta)object from the next
metalevel pointed to by a blue link.
Objects from other metalevels do not have such an own meta-object.
Inheritance
We denote ≤ the reflexive transitive closure of green links,
i.e. for objects x, y
x ≤ y iff
y is reachable from x via zero or more green links.
This relation forms a partial order, called inheritance.
Further observations:
Objects from metalevel 0 are exactly the singletons in inheritance:
they have no (strict) descendants or ancestors.
The object r is the top of the metalevel 1 as well as of the union
of metalevels 1 and 2, w.r.t. inheritance.
The object r class is the top of the metalevel 2, w.r.t. inheritance.
The parent of r class is the object c from metalevel 1.
In the restriction to a metalevel,
the blue links constitute a map that is monotone w.r.t. inheritance,
i.e.
if x and y are from the same metalevel, then
x ≤ y implies
(x class)≤(y class).
Since blue links constitute bijection between metalevels 1 and 2,
they constitute an order isomorphism between these metalevels, w.r.t. inheritance.
If x is an object from metalevel 1 different from r,
then
x class superclass == x superclass class.
Uniformity deficiency No. 2
The following observation reveals another defect of uniformity of Smalltalk-80:
Without the restriction to a particular metalevel, the blue links do NOT constitue
a monotone map.
For example, if x := r class and y := c,
then x ≤ y (we even have x superclass == y)
but x class equals mc
which is not an inheritance descendant of y class.
The Ruby-Smalltalk core correspondence
The correspondence between
the core structures of Smalltalk-80 and Ruby
can be observed on the following pair of diagrams.
The Ruby structure has the actuality extent
O.a =T⊎C⊎C.ec,
so that
T is the set of actual objects on metalevel 0,
C is the set of actual objects on metalevel 1,
C.ec is the set of actual objects on metalevel 2,
and there are no more metalevels with actual objects.
Smalltalk-80
Ruby
We now resolve the terms
class, class-of, metaclass and instance-of
by applying Ruby-based terminology and notation to Smalltalk.
Let
terminals (T) be the objects from metalevel 0,
classes (C) be exactly the objects on metalevel 1, and
implicit metaclasses (C.ec) be the objects from metalevel 2,
In particular, the metalevel 1–2 correspondence is a correspondence
between classes and implicit metaclasses.
The differences between the core samples can be listed as follows:
The Smalltalk-80 core contains two more built-in classes, of which only
the mc class (named Metaclass) constitutes a structural
change as a receiver of blue arrows.
The blue arrows starting at metalevel 2 are redirected to mc.
Since blue arrows in the Ruby sample display the actualclass map, .aclass,
the blue arrows in the Smalltalk sample indicate the imposed actualclass
map,
which we denote .aȼlass.
Therefore,
x.aȼlass = x.aclass if x is a class or terminal,
x.aȼlass =mc otherwise
(i.e. if x is an implicit metaclass).
The imposed class map, .ȼlass, equals the composition
.aȼlass.c,
i.e.
x.ȼlass is the least ancestor of x.aȼlass that is a class.
The imposed (object) membership
equals the composition (.aȼlass) ○‣ (≤).
This relation can be detected via the isKindOf: introspection method.
The imposed instance-of relation
is the range restriction of imposed membership to classes,
so that it equals the composition (.ȼlass) ○‣ (≤).
By using imposed membership for the is-a naming convention,
classes can be expressed as Classes and
implicit metaclasses as Metaclasses.
Moreover,
C.ȼlass.↧
can be considered to be the set of all metaclasses.
The classes Class and Metaclass are
then the only explicit metaclasses.
Notes:
Note in particular, that the class introspection method in Smalltalk-80
does not correspond to the synonymous method of Ruby.
In Ruby, the class introspection method corresponds to the class map,
.class.
In Smalltalk-80, the class method corresponds to the imposed actualclass map,
.aȼlass.
As a consequence, x class is not necessarily a class.
The following table describes the differences:
For x from
Smalltalk-80 x class evaluates to
Ruby x.class evaluates to
T (terminals)
the class of x
C (classes)
the eigenclass of x
the class of x which is constantly Class
C.ec (implicit metaclasses)
the imposed class of x which is constantly Metaclass
There is no support for the above or similar definitions in the Smalltalk
literature.
Instead, publications about Smalltalk-80 use equivocal terminology
which suggests two different delimitations of classes and metaclasses:
[]
(A)
Classes are the objects from metalevels 1 and 2.
Metaclasses are the objects from metalevel 2
plus the class named Metaclass.
(B)
Classes are the objects from metalevel 1.
Metaclasses are the objects from metalevel 2.
The primary structure of ϵ according to Python
We now set out for a formal description of object membership.
This section provides axiomatizations of the canonical primary structure.
The axioms are general enough to allow two features that
have not yet been captured by the provided samples:
multiple inheritance (that is, an object can have multiple inheritance parents), and
explicit metaclasses other than the built-inc class.
It turns out that under some minor assumptions
the canonical primary structures of ϵ are exactly the structures that are
allowed in the Python programming language
[]
(of course, up to the number of helix classes).
The correspondence can be expressed as
(.class, .↥) ↔
(.__class__, .__mro__)
where __class__ and __mro__ are (built-in) attributes of
Python objects.
The __mro__ attribute is only applicable to classes.
It stands for method resolution order
and stores the list of inheritance ancestors in the order in which they are looked
up during method resolution.
The inheritance relation, ≤, between classes is obtained by
x ≤ y iff y ∈ x.__mro__
so that the order of classes in the __mro__ list is disregarded.
We assume that a potential explicit manipulation of the attribute
is a permutation (changing just the order of classes in the list).
Note:
In addition to the __mro__ attribute,
Python classes also contain another inheritance related attribute:
the __bases__ list.
Apart from the order within the list, the intended semantics of
.__bases__ is that of the .parents map.
However, the correspondence is not asserted.
In particular, the __mro__ and __bases__ attributes are not
kept in sync if they are explicitly manipulated.
We therefore think of .parents to be derived from .__mro__
(satisfying the assumption above) rather than from .__bases__.
Recursive definition
We first provide a recursive definition which shows how the structure can be
incrementally constructed.
A canonical primary structure (of ϵ) is a structure
S= (Ō, .class, .parents, r)
where
Ō is set of objects,
.class
is the class map between objects,
.parents
is the inheritance parent set map
from Ō to the powerset of Ō,
r
is the inheritance root, a distinguished object.
We denote ≺ the relation on Ō defined by
x ≺ y iff y ∈ x.parents.
For a set X of objects, we write
X.parents for the image of X under ≺.
Therefore, for an object x,
x.parents is just an abbreviation for {x}.parents.
We can also write .parents(i)
for the i-th application of .parents.
Furthermore, let ≤ be the reflective transitive closure of ≺.
The usual terminology and notation is used for ≤.
Descendants of r form the set C of classes,
the remaining objects are terminal(s).
Let c=r.class be the metaclass root.
Descendants of c are metaclasses.
The structure is then subject to the following conditions:
(py~1)
≺ is irreflexive and transitively reduced.
(py~2)
All objects from Ō.parents ∪Ō.class are classes.
(py~3)
The .class map is monotone w.r.t. ≤,
i.e.
x ≤ y implies x.class ≤ y.class
for every objects x, y.
(py~4)
If Ō=Ō.parents ∪Ō.class
then
(a) ≤ is a linear order,
(b) .class is constant, and
(c) r≠c.
(py~5)
Classes of terminal objects are not metaclasses.
(py~6)
The restriction of S to Ō∖ {x}
is a canonical primary structure
for every
x ∈Ō∖ (Ō.parents ∪Ō.class).
(py~7)
The set C of classes is finite.
Observations:
Ō.parents ∪Ō.class is the set of objects
that are not minimal w.r.t. (≺) ∪ (.class).
The restriction of the structure to c.↥
is described by (py~4).
It is a built-in substructure
containing no objects that are minimal w.r.t.
(≺) ∪ (.class).
Condition (py~1)
could be stated just for the built-in structure.
It asserts that
≺ is a reflexive transitive reduction of ≤
so that there is a one-to-one correspondence between .parents and ≤.
(py~6) is the only recursive condition.
It says that removing an object minimal w.r.t.
(≺) ∪ (.class) preserves the structure.
We avoided recursive definitions of classes and metaclasses by introducing
≤.
New object attachment
The recursive definition
says that any finite canonical primary structure can be incrementally built from its
restriction to c.↥ by attaching new objects, one by one.
Let an attachment request be a pair (P,q) such that
P is the requested (possibly empty) set of inheritance parents, and
q is the requested class,
so that P = x.parents and q = x.class
for the new object x.
An attachment request (P,q) is acceptable iff the following are
satisfied:
(1)
P is an antichain in ≤,
i.e.
if x and y are different objects from P,
then x ≰ y.
(2)
Assert (py~2):
Every object from P ∪ {q} is a class.
(3)
Assert (py~3):
For every x from P, q ≤ x.class.
(4)
Assert (py~5):
If P is empty then q is not a metaclass.
Conditions (py~1)–(py~7) are preserved
after the attachment of x if and only if (1)–(4) are asserted.
Condition (1) can be left out if x.parents is set to mins_{≤}(P)
instead of to P.
The following diagrams shows assertions of (2)–(4) in Python.
(a)
¬(py~2): s is not a class
(b)
¬(py~3): B.class ≰A.class
(c)
¬(py~5): M is a metaclass
class A():
def __new__(a): pass
s = A()
# TypeError:
class B(s): pass
class M(type): pass
class N(type): pass
class A(metaclass=M): pass
# metaclass conflict
class B(A,metaclass=N): pass
class M(type): pass
class X: pass
s = X()
# TypeError:
s.__class__ = M
Canonical primary structure
We now provide a default axiomatization of canonical primary structures.
In the description, a preparation is already made for the extension
by implicit objects.
The set of objects in a primary structure is denoted O.pr.
This expression can be later resolved to an application of .pr
to the extended set O of objects.
Similarly, some sentences contain the adjective primary
to be also applicable in the context of the extended structure.
By a canonical primary structure of ϵ we mean a structure
(O.pr, ϵ, ≤, r)
where
O.pr is set of primary objects,
ϵ
is the instance-of relation between primary objects,
≤
is the inheritance relation between primary objects,
r
is the inheritance root, a distinguished object.
The usual terminology and notation is used for ≤ and ϵ.
Objects that are not descendants of r
form the set T of terminal(s),
the remaining primary
objects form the set C of classes.
Helix objects x are such that
rϵ^{i} x for some i ≥ 0.
Metaclasses are the lower bounds of helix classes,
i.e. they are objects x such that all helix classes are among ancestors of
x.
An object x is
well-founded
w.r.t. ϵ
if there is no infinite sequence of objects
x_{1}, x_{2}, … of objects
such that
x ϶ x_{1}϶ x_{2}϶ ….
The structure is then subject to the following axioms:
Terminals have no instances and no strict descendants.
(p~4)
Helix classes are
(a) totally ordered by ≤,
(b) instances of each other, and
(c) at least two in number.
(p~5)
Metaclasses can only have classes as instances.
(p~6)
Every non-helix object is well-founded w.r.t. ϵ.
(p~7)
Every object x has a least primary container,
x.class.
(p~8)
The set C of classes is finite.
Notes and observations:
In RDF Schema, condition (p~2)(a)
is asserted by the rdfs9 entailment rule.
Using type theoretic terminology, this can be called the subsumption rule.
[]
Conditions (p~2)(b) and (p~6)
can be conveniently expressed using the .class map.
The .class map is monotone.
(Therefore, (p~2)(b) is the
metaclass compatibility condition.)
The .class map forms a tree.
Condition (p~2)
can be equivalently written as a single equality:
(≤) ○‣ (ϵ) ○‣ (≤) = (ϵ).
Condition (p~3) means that
terminals are minimal both in ϵ and ≤.
Proposition:
Axiomatizations
(py~1)–(py~7) and
(p~1)–(p~8) are equivalent.
The canonical eigenclass structure of ϵ
Roughly speaking, the canonical refinement of the instance-of relation is established
by combining Ruby with Python.
This can be viewed in two ways:
(A) Equipping Python's core structure with eigenclasses.
(B) Relaxing Ruby's core structure by allowing multiple inheritance and
classes on higher metalevels.
We provide precise interpretation of (A) and (B).
The interpretation of (A) will be tight in the sense that
every class has at most one eigenclass ancestor (necessarily r.ec).
This seems to be the simplest way of eigenclass completion.
However, since it also disallows classes on metalevels higher than 2,
the interpretation of (B)
defines a slightly larger family than that of (A).
Moreover, some axioms for (B) are singled out
for further generalization of object membership.
Eigenclass regress alone
The structure of infinite regress of eigenclasses
can be simply characterized as a monounary algebra
(O, .ec) such that
Elements of O are objects,
.ec is the eigenclass map between objects.
For an object x, x.ec is the eigenclass ofx.
We denote x.ec(i) the i-th application of .ec
to x. (Let x.ec(0) = x.)
Since the .ec map is injective, it has a partial inverse
which we denote .ce.
For an eigenclass x, x.ce is the
(direct) eigenclass predecessor of x.
Objects from O.ec are eigenclasses,
the remaining (i.e. those without an eigenclass predecessor) are primary.
Components of (O, .ec) are eigenclass chains.
Since .ec is well-founded, every eigenclass chain starts
in a primary object.
For an object x, let x.pr denote the primary object
of x,
(i.e. the primary object of the eigenclass chain to which x belongs).
The unique natural i such that x.pr.ec(i) = x
is denoted x.eci and called the eigenclass index of i.
Observations:
For each eigenclass chain X,
(X, .ec) is
isomorphic (via .eci)
to the structure (ℕ, succ) of natural numbers
where succ is the successor operator.
O=O.pr ⊎O.ec.
Notes:
As of version 2.0 or older, Ruby does not provide any introspection methods
for .ce, .pr or .eci.
Internally, the .ce links are implemented using the
__attached__ instance variable.
ABCL/R
is another example of a programming language that supports infinite regress.
In the documents
[][],
the term metaobject (or meta-object) is used for eigenclass.
An eigenclass chain is a metaobject tower.
As the term suggests, the regression is diagrammatized vertically.
The code expressions
[meta x] and
[den x] correspond to
x.ec and x.ce, respectively.
Tight canonical structure by eigenclass completion
By a tight canonical eigenclass structure of ϵ we mean a structure
(O, .ec, ≤, r)
where
O is a set of objects,
.ec is the eigenclass map O→O,
≤ is the inheritance relation between objects, and
r is a distinguished object.
The structure
is subject to conditions
(ec~1)–(ec~3) below.
Let the object membership relation, ϵ, be the composition
(.ec) ○‣ (≤).
Additional terminology and notation is induced by the first two conditions.
In particular, .pr is the primary object map
(obtained from .ec)
and c is the metaclass root.
(ec~1)
.ec is an injective well-founded map.
(ec~2)
(O.pr, ϵ, ≤, r)
is a primary structure of ϵ.
(ec~3)
For every primary objects a, b
and every natural i, j > 0, the following are satisfied:
(A)
a.ec(i) ≤ b iff a ϵ▫^{i} b
where ϵ▫ denotes the restriction of ϵ to primary objects.
(B)
a ≤ b.ec(j) iff
a < c, b =r and j = 1.
(C)
a.ec(i) ≤ b.ec(j) iff
a.ec(i-1) ≤ b.ec(j-1).
The definition is in fact a prescription for the eigenclass completion of a
primary structure.
Given a canonical primary structure(O.pr, ϵ, ≤, r),
the construction steps are as follows:
Equip each primary object with an eigenclass chain.
Extend ≤ according to (ec~3).
Extend ϵ by setting (ϵ) = (.ec) ○‣ (≤).
Canonical eigenclass structure
By a canonical eigenclass structure of ϵ we mean a structure
(O, .ec, ≤, r)
where
O is a set of objects,
.ec is the eigenclass map O→O,
≤ is the inheritance relation between objects, and
r is a distinguished object.
The following additional terminology and notation applies:
The object membership relation, ϵ, is the composition
(.ec) ○‣ (≤),
.ec^{∗} is the reflexive transitive closure of .ec,
ϵ^{∗} is the transitive closure of (≤) ∪ (ϵ).
Let
.ce,
.ce^{∗}, ϶ and
϶^{∗} be inverses of
.ec,
.ec^{∗}, ϵ and
ϵ^{∗}, respectively.
For an object x, the set x.ec^{∗} is the
eigenclass chain of x,
the set x.↧ / x.↥ / x.϶ / x.ϵ
is the set of
descendants / ancestors / members / containers
of x.
The .pr map is defined by:
x = y.pr ↔
{x} = y.ce^{∗}∖O.ec.
Let
O.ec be the set of eigenclasses,
the remaining object being primary,
T=O∖r.↧ be the set of
terminal objects,
C=r.↧∖O.ec be the set of
classes,
R=r.ec^{∗} be the reduced helix,
H=r.ϵ^{∗} be the set of
helix objects.
A canonical eigenclass structure of ϵ is subject to the following axioms
(the separator delimits the 5 axioms of
monotonic eigenclass structures):
•(e~1)
Inheritance, ≤, is a partial order.
(e~2)
The eigenclass map, .ec, is an order-embedding of
(O, ≤) into itself.
•(e~3)
Objects from eigenclass chains of terminals
are minimal in inheritance.
(e~4)
Every eigenclass is a descendant of the inheritance root.
(e~5)
R has no lower bound in ≤.
•(e~6)
Helix classes are
(a) totally ordered by ≤,
(b) an upset in ≤, and
(c) at least two in number.
Axiom (e~2) is the essential axiom.
It can be equivalently expressed as
(≤) = (.ec) ○‣ (≤) ○‣ (.ce).
Axiom (e~3) asserts that
terminals are unrelated by < to any object
and that this property is preserved after a free instantiation
of any class.
Axiom (e~4) asserts
that r is a universal object:
O=r.϶.
Since r is asserted to be a class by
e~(1)(2)(4)(5),
every object is an instance ofr.
Axiom (e~5) asserts
that .ec is a well-founded map.
Due to the injectivity asserted by (e~2),
.ec establishes the infinite regress of eigenclasses.
Axiom (e~6) asserts that the restriction to
H is (a)(b) as simple as possible
but (c) non-degenerate: H≠R.
Using the finiteness condition (e~12),
H is asserted to form a closure system in
(O∖T, ≤).
In addition, the existence of a least helix class, c, is ensured.
Axiom (e~7) asserts that the eigenclass chain of
c is not used for the connection to the helix.
Using .he as the closure operator for H
(i.e. such that r.↧.he =H),
(e~7) can be expressed as
c∉C.he.pr.
Axiom (e~8) asserts that H
is exactly the non-well-founded part of the structure.
Moreover, x ∈H iff x ϵ x.
Axioms (e~9) and (e~10)
assert a one-to-one correspondence between the well-founded part
(O∖H, …) and
its restriction (O.pr ∖H, …) to
primary objects.
Axiom (e~10)
can be equivalently stated as any of the following:
the member-of-instance-of relation is equal to
the instance-of-instance-of relation,
.ec.class = .class.class
(using (e~11)),
.c preserves ϵ
(using (e~11))
Axiom (e~11) asserts that the set
O.pr of primary objects
forms a closure system in inheritance.
We denote .c the corresponding closure operator
so that O.pr =O.c
and .class = .ec.c.
Moreover, this axioms makes
(e~4) redundant.
(This is because if e~(1)(2)
is assumed then:
(e~4)
↔
every object has a primary container.)
Notes and observations:
A canonical eigenclass structure of ϵ is
expressible in the (O, ϵ) signature.
Since (e~4) asserts that
every object has a primary container,
it becomes redundant within canonical structures
due to (e~11).
Correspondence between primary and eigenclass structures
The correspondence between the primary structures and the eigenclass structures
is described as follows.
Proposition:
The restriction of a canonical eigenclass structure to primary objects is
a canonical primary structure.
The .c map is a homomorphic projection
of (O, ϵ, ≤)
onto (O.pr, ϵ, ≤).
A tight canonical eigenclass structure is a canonical eigenclass structure satisfying
the following stronger version of axiom (e~9):
(e~9⁺)
Descendants of eigenclasses-other-than-r.ec are eigenclasses.
Note that (e~9⁺)
restrains the helix entry x.he of explicit metaclasses x other than
c to r.ec.
As a consequence, if x, y are explicit metaclasses different from
c such that x ϵ y then
≤ cannot be a single inheritance.
(Ancestors of x.ec cannot be linearly ordered in ≤
since y and x.ec.re are incomparable.)
A non-tight canonical structure
(so that (e~9⁺) is not imposed)
allows single inheritance for arbitrary depth of instantiation.
The diagrams below show the correspondence between a canonical eigenclass structure,
its restriction to primary objects and
the subsequent tight eigenclass completion.
Note that the tree structure of ≤ is not preserved.
(a)
Canonical eigenclass structure (O, .ec, ≤)
(b)
The primary structure of (a) (O.pr, .class, ≤)
(c)
The tight eigenclass completion of (b)
Ruby's additional constraints
The Ruby programming language imposes single inheritance
and a single metalevel for classes.
These additional conditions can be respectively written as follows.
(e~13)
For every object x, the set x.↥ is linearly ordered by ≤.
(e~9⁺⁺)
Descendants of eigenclasses are eigenclasses.
(Equivalently, every class is on metalevel 1.)
The conditions make some of the previous ones redundant.
In particular,
(e~9) ←
(e~9⁺) ←
(e~9⁺⁺)
is an obvious implication chain.
Monotonic eigenclass structure of ϵ
The family of structures given by the first five axioms of
canonical eigenclass structures
can be regarded as
the essential mathematical model for the core structure of object technology.
This is for the following reasons:
Simplicity.
There are five simple conditions that can be stated with only a few
preliminary definitions.
Moreover, the structures are fully determined solely by ϵ.
Generality.
The monotonicity condition seems to be predominant in object technology
so that it can be regarded as an acceptable (or even desirable) restriction.
Similarly, the requirement of
every object having an eigenclass only means that the structures
are expressed in their eigenclass completion
(which is unique, up to isomorphism).
General monotonic structures (in which .ec is partial)
can be thought of as implementation-oriented refinement
that records the actuality state of eigenclasses.
Connection to algebraic set theory.
Object membership, ϵ, is formed by the composition of
.ec and ≤ just like the membership relation ɛ
in Zermelo-Fraenkel algebras.[]
The following table shows the notational correspondence:
Monotonic eigenclass structure
x ϵ y
↔
x.ec ≤ y
Zermelo-Fraenkel algebra
x ɛ y
↔
s(x) ≤ y
The next subsection provides a concise and rather self-contained
definition of
monotonic eigenclass structures.
Monotonic eigenclass structure
By a monotonic eigenclass structure
we mean a structure
S= (O, .ec, ≤, r)
where
O is a set of objects,
.ec
is the eigenclass map O→O,
(objects from O.ec are eigenclasses)
≤
is the inheritance relation between objects,
r
is the inheritance root, a distinguished object.
The usual ancestor / descendant terminology is used for inheritance.
Objects that are not descendants of r are terminal(s).
Let .ec^{∗} denote the reflexive transitive closure of
.ec.
For an object x, the set
x.ec^{∗}
(the image of {x} under .ec^{∗})
is the eigenclass chain of x.
The structure is subject to the following axioms:
(e~1)
Inheritance, ≤, is a partial order.
(e~2)
The eigenclass map, .ec, is an order-embedding of
(O, ≤) into itself.
(≤) = (.ec) ○‣ (≤) ○‣ (.ce)
(e~3)
Objects from eigenclass chains of terminals
are minimal in inheritance.
(O×T.ec^{∗}) ∩ (<) =∅
(e~4)
Every eigenclass is a descendant of the inheritance root.
O.ec ≤r
(e~5)
The eigenclass chain of r
has no lower bound in ≤.
As already
shown
for the Ruby core sample,
any monotonic eigenclass structure can be expressed in the minimum signature
(O, ϵ).
The constituents of the original signature are obtained as follows:
x ≤ y
↔
x.ϵ⊇ y.ϵ,
x.ec = y
↔
x.ϵ= y.↥.
(In addition, x.ec = y
→ x.↧= y.϶
but ← does not hold in general.)
Moreover, r is the unique top of O.ϵ.
Monotonic primary structure of ϵ
For the sake of completeness we introduce a generalization
of canonical primary structures according to the following table.
Note:
For simplification,
we introduce slight discrepancy with the more precise document
[].
The family of structures defined in the following subsection
should be more correctly called membership-based monotonic structures
since they rely on the prescription
(mp-γ)
x ϵ^{-k} y
↔
x < r.ϵ^{k+i} and
r.ϵ^{k+i}≠r.ϵ^{k+i-1} and
rϵ^{i} y for some natural i
for negative powers of ϵ (ϵ^{-k} where k > 0)
which we introduce later for basic structures.
The correctly defined family of monotonic primary structures
arises simply as a subfamily of
monotonic basic structures
in which .ec =∅
(so that every object is primary).
Monotonic primary structure
By a monotonic primary structure of ϵ we mean a structure
(O, ϵ, ≤, r)
where
O is a set of objects,
ϵ
is the membership relation between objects,
≤
is the inheritance relation between objects, and
r
is the inheritance root, a distinguished object.
The usual terminology and notation is used for ≤ and ϵ.
In addition, the ≤ and < symbols are also used in the
polar sense for relations between sets of objects,
so that e.g X < Y means that every object of X
is less than every object of Y.
Let
T=O∖O.ϵ.↧ be the set of
terminal objects and
H=r.ϵ^{∗} the set of helix objects
where ϵ^{∗} is the
transitive closure of (≤) ∪ (ϵ).
For a natural i > 0,
let ϵ^{i}
be the i-th composition
of ϵ with itself and let ϵ^{0} be equal to ≤.
The inheritance root r is the top of
O.ϵ w.r.t. ≤.
(mp-γ~4)
Every object has a container, O=O.϶.
(mp-γ~5)
Terminal objects are minimal in ≤.
(mp-γ~6)
If H≠r.ϵ^{i} for every natural i
then
H has no lower bound in ≤.
(mp-γ~7)
For every natural i such that H≠r.ϵ^{i},
if x < r.ϵ^{i+1}
then x.϶ < r.ϵ^{i}.
Observation:
For a structure S= (O, ϵ, ≤, r)
the following are equivalent:
S is a canonical primary structure.
S is a monotonic primary structure satisfying
(p~4)–(p~8).
Moreover, the (p~4) condition
(Metaclasses can only have classes as instances.)
can only be stated for the metaclass root since other metaclasses are
strict descendants of r.ϵ and thus are subject to
(mp-γ~7).
Basic structure of ϵ
In this section we introduce a common generalization of
the hitherto introduced structures
that can be regarded as an abstract set-theoretical model of the core structure
of object technology.
The generalization can be roughly characterized by the following steps:
Remove (relax) the monotonicity condition.
As already observed in the
introduction,
in contrast to the subsumption rule,
the monotonicity condition
(≤) ○‣ (ϵ) ⊆ (ϵ)
is not universally satisfied when ≤ and ϵ
are interpreted as ⊆ and ∈, respectively.
Allow partial definition of .ec.
Until now we have formally described structures that
either had no eigenclasses
(primary structures)
or in which the eigenclass map was total
(eigenclass structures).
Provide a non-monotonic counterpart to .ec.
Until now, x.ec, if defined, was the least container of x.
The (≥) = (.ec) ○‣ (϶) equality
indicates that the .ec map is an abstraction of the powerset operator.
However,
in set theory,
the least set that contains a given set x as an element
is {x}, the singleton of x,
which is different from the powerset of a set x
(except when x is empty).
This is established by the family of basic structures[].
Basic structure
⋮
⋮
ϵ^{2}
ϵ¯^{2}
ϵ
ϵ¯
≤
ϵ^{-1}
ϵ^{-2}
⋮
By a basic structure of ϵ
we mean a structure
S= (O, ϵ^{⁽*⁾}, ϵ¯^{⁽*⁾}, r, .ec, .ɛɕ)
where
O is a set of objects,
ϵ^{⁽*⁾} and
ϵ¯^{⁽*⁾}
are bi-infinite sequences of relations between objects such that
(a) (ϵ^{i}) = (ϵ¯^{i}) for i ≤ 0,
(b) (ϵ^{j+1}) = (ϵ^{j}) ○‣ (ϵ) and
(c) (ϵ¯^{j+1}) = (ϵ¯^{j}) ○‣ (ϵ¯) for j > 0,
and where
(ϵ) = (ϵ^{1}) is the (object) membership relation,
(ϵ¯) = (ϵ¯^{1}) is the power membership relation,
(≤) = (ϵ^{0}) is the inheritance relation
(with .↧ / .↥ used for preimages / images under ≤),
(ϵ^{-1}) is the anti-membership relation,
r
is the inheritance root, a distinguished object,
and the remaining two definitory constituents are partial
maps O↷O
(i.e. functional relations between objects):
.ec
is the powerclass map
(objects from O.ec are powerclasses),
.ɛɕ
is the primary singleton map
(objects from O.ɛɕ are primary singletons).
Note that due conditions (a–c) the two bi-infinite sequences
are given by
ϵ and the left-infinite sequence
{ ϵ¯^{i}| i ∈ℤ, i ≤ 1 }.
In particular, we can drop the wildcard superscript from ϵ^{⁽*⁾}
in the signature.
Before stating the axioms some preliminary definitions need to be introduced.
For every integer i, ϶^{i} (resp. ϶¯^{i})
denotes the inverse of
ϵ^{i} (resp. of ϵ¯^{i}).
For a natural i,
let .ec(i)
be the i-th composition
of .ec with itself,
with .ec(0) being the identity on O.
Let .ec(-i) be the inverse of .ec(i).
Let
T=O∖O.ϵ.↧
be the set of terminal objects (or terminals).
The metalevel index, x.mli,
of an object x is
defined by
x.mli =
sup { i | x ϵ^{1-i}r, i ∈ℕ }.
Finally, the definition of the rank function, .d, assumes
a fixed limit ordinal ϖ in the context.
The rank of an object x is then recursively defined by
x.d
=ϖ
if x is non-well-founded in ϵ,
x.d
=ϖ∧
(sup {a.d + 1 | a ϵ x}
∨
sup {a.mli + i-j |
a ∈ x.϶^{i}.϶^{-j}, i,j ∈ℕ})
if x is well-founded in ϵ.
(We use α ∧ β (resp. α ∨ β)
to refer to the minimum (resp. maximum)
of ordinal numbers α and β.
To be correct, the prescription requires finiteness of a.mli
which is asserted by
(b~10).)
The structure is then subject to the following axioms:
The axioms
Observations:
For a suitable choice of (i,j) in (b~2)
we obtain
transitivity of ≤,
subsumption of ϵ¯,
and the
monotonicity of ϵ¯.
For i = 0
in (b~3) we obtain the subsumption of ϵ:
(ϵ) ○‣ (≤) ⊆ (ϵ).
In contrast, monotonicity is not asserted.
For i = 0 in (b~4) we obtain
the antisymmetry and reflexivity of ≤ so that
≤ is a partial order on O.
(b~5) asserts that
O=T⊎r.↧.
Since
rϵ x ≤r for some object x
it follows by subsumption of ϵ that rϵr.
Since r is non-well-founded in ϵ it follows by
(b~11) that rϵ¯r.
Consequently, for every non-terminal x,
x ϵ¯r
by monotonicity of ϵ¯
and
x ϵr since (ϵ¯) ⊆ (ϵ).
As a particular consequence of (b~6)
and (b~7)(b)
we obtain that x ϵ¯r
for every terminal x.
It follows that r is a universal (power) container:
O=r.϶¯=r.϶.
As a particular consequence of (b~7)(a)
we obtain that every object from T.ec^{∗}
is minimal in ≤
(cf.
(e~3)).
Rank
If every object is
ϵ-grounded,
i.e. connected with a terminal object via ϵ
(equivalently, T.ϵ^{∗}=O)
then the prescription for the rank function
is simplified as follows.
Let W be the set of objects that are well-founded in ϵ. Then
x.d
=ϖ
if x ∉ W,
x.d
=ϖ∧ sup {a.d + 1 | a ϵ x}
if x ∈ W.
That is,
x.d =ϖ
for all objects x that are either non-well-founded in ϵ
or are well-founded and their
rank in the well-founded relation (W,ϵ)
is greater or equal to ϖ.
For the remaining objects x,
let x.d be their rank in (W,ϵ).
The following diagram shows an ad-hoc completion
(⁎)
making each object of the original structure ϵ-grounded.
Added objects are
displayed in khaki color.
See
[] for the precise definition.
Notes and observations:
(⁎)
As indicated by the case of the a object,
new member chains are added even for
objects from T.ϵ^{∗}
so that the term completion is not quite adequate.
It is asserted that x.mli ≤ x.d
for every object x.
However, even memberless objects can have their rank strictly higher than
the metalevel index.
This is the case of the b object
(2 = b.mli < b.d = 3).
Another simplification arises in the case ϖ= ω.
That is, the default value of ϖ is the first
infinite ordinal
so that the rank of an object is either finite of equal to ω.
In this case, .d can be defined by
The rank function .d is used for distinction
between two kinds of objects:
Objects x such that x.d < ϖ are bounded.
Objects x such that x.d =ϖ are unbounded.
The bounded membership relation ∊
is then the domain-restriction of ϵ to bounded objects,
i.e.
x ∊ y iff
x ϵ y and x is bounded.
The set of bounded objects can be referred to by O.∍
or by r.∍.
Every bounded object is well-founded in ϵ
(i.e. ∊ is a well-founded relation) but not necessarily vice versa.
We also introduce the ∊¯ symbol for (ϵ¯) ∩ (∊)
(the bounded power membership).
Note that axioms (b~1) and (b~11)
can be stated as a single condition
(ϵ) = (∊) ∪ (ϵ¯).
This establishes an inclusion lattice
between
ϵ, ∊, ϵ¯ and ∊¯
according to the above diagram on the right.
Singletons
Singletons are the objects from
(T.ec ∪O.ɛɕ).ec^{∗}
(where .ec^{∗} is the reflexive transitive closure of
.ec).
The range-restriction of ϵ to singletons is denoted .ɛϲ
and called the singleton map.
Axioms (b~7)(a) and (b~8)(a)
assert that .ɛϲ is a partial map between objects, so that
x.ɛϲ = y
↔
{x} = y.϶ and y is a singleton.
Another consequence of the axioms is
.ɛϲ.ɛϲ = .ɛϲ.ec
–
powerclasses of singletons are singletons.
The primary singleton map .ɛɕ
used in the axiomatization equals the difference
(.ɛϲ) ∖ (.ec).
The following table shows similarities and differences between
.ec and .ɛϲ.
y is the powerclass of x,
x.ec = y
y is the singleton of x,
x.ɛϲ = y
Members of y
x.↧= y.϶
{x} = y.϶
Ancestors of y
x.ϵ¯= y.↥
x.ϵ= y.↥
Metalevel index increment (y.mli - x.mli)
1
1
Rank increment (y.d - x.d) on O.∍
1
1
x (or y) can be unbounded
YES
NO
Metaobject structure
The diagram on the right shows a basic structure that is metaobject complete
–
the powerclass map .ec (shown by horizontal blue arrows) is total
and the singleton map .ɛϲ (shown by blue arrows pointing to a circle
which indicates a singleton)
is defined on the set O.∍ of bounded objects.
This subfamily of basic structures can be axiomatized
as metaobject structures in
the signature
(O, ≤, r, .ec, .ɛϲ).
The membership constituents of a basic structure are obtained as follows:
(∊)
=
(.ɛϲ) ○‣ (≤)
(bounded membership),
(ϵ¯)
=
(.ec) ○‣ (≤)
(power membership),
(ϵ)
=
(∊) ∪ (ϵ¯)
((object) membership),
(ϵ^{-k})
=
(≤) ○‣ .ec(-k)
(anti-membership and its powers, k > 0).
A metaobject structure is subject to the following axioms:
For every objects x, y such that x.ɛϲ is defined,
x.ɛϲ ≤ y.ec↔x ≤ y.
(mo~9)
For every object x,
x.ɛϲ is defined ↔
x.d < ϖ.
The rank function .d is defined
by the same prescription as in basic structures.
See
[] for details.
Monotonic structures
ϵ
≤
ϵ^{-1}
ϵ^{-2}
⋮
Monotonic basic structures are such that (ϵ¯) = (ϵ).
They can be axiomatized
in the signature
(O, ϵ^{⁽*⁾}, r, .ec) where
ϵ^{⁽*⁾} is a left-infinite (or down-infinite) sequence according
to the diagram on the right.
The axioms are as follows
(using the terminology and notation established for
basic structures):
(m~1)
(ϵ^{i}) ○‣ (ϵ^{j}) ⊆ (ϵ^{i+j})
for every integer i, j.
(m~2)
(ϵ^{i}) ∩ (϶^{-i}) = .ec(i)
for every integer i.
(m~3)
O.ϵ≤r.
(m~4)
O=O.϶.
(m~5)
For every object x from T
and every natural i,
{x}.ec(i) = x.϶^{-i}.
(m~6)
For every object x,
the metalevel index x.mli,
defined as sup { i | x ϵ^{1-i}r, i ∈ℕ },
is finite.
Structures that have been introduced before the basic structures in this document
can be
considered to form subfamilies of monotonic basic structures:
Monotonic primary structures
(see the note about terminological imprecision before the subsection)
are obtained
from monotonic basic structures by imposing the following
condition to negative powers of ϵ:
For every natural k > 0,
x ϵ^{-k} y iff
there is a natural i such that
(a)
rϵ^{i} y,
(b)
x < r.ϵ^{i+k},
and
(c)
r.ϵ^{i+k}≠r.ϵ^{i+k-1}.
This yields .ec =∅ as a particular consequence.
See
[] for details.
The union map
The (b~9) label
is reserved for
the axiomatization of the non-member union map, .ⱷ.
This is considered to be the first candidate for
a possible expansion of basic structures.
The .ⱷ map forms the explicit part of .υ,
the union map, which is a partial map between objects
that is an abstraction of the least anti-container and thus of set union.
The .υ map is obtained from .ⱷ by
(.υ) = (.ⱷ) ⊎ ((ϵ^{-1}) ∩ (϶)).
Axioms of (non-expanded) basic structures assert that
(ϵ^{-1}) ∩ (϶) is a partial map.
Moreover, the inverses of .ec and .ɛϲ are
distinguished submaps.
The presumed axiomatization of .ⱷ
is shown below together with
the similar axiom (b~8).
(b~8)
If x.ɛɕ = y then:
(a) {x} = y.϶,
(b) x.ϵ^{i}= y.ϵ^{i-1} for every i ≤ 1,
(c) (x,y) ∉ (ϵ¯).
(b~9)
If x = y.ⱷ then:
(a_{1})
x.϶¯= y.϶.϶¯,
(a_{2})
x.϶= y.϶^{2},
(b) x.ϵ^{i}= y.ϵ^{i-1} for every i ≤ 0,
(c) (x,y) ∉ (ϵ).
Unfortunately,
the .ⱷ map also requires
an adjustment to the definition of the rank function .d
(see
[] for details).
Complete structure of ϵ
A basic structureS= (O, ϵ, ϵ¯^{⁽*⁾}, r, .ec, .ɛɕ)
is said to be complete
if it satisfies the following conditions:
(A)
S is
extensionally consistent:
For every objects x, y,
x ≤ y
↔
x = y or ∅≠ x.∍⊆ y.∍.
(B)
S is metaobject complete:
(a)
S is powerclass complete and
(b)
S is singleton complete.
(C)
S is extensionally complete:
For every subset X of O.∍ there is an object x
such that x.∍= X.
(D)
S is ∊-ranked:
For every object x,
r_{∊}(x) (the ∊-rank of x) equals x.d.
We also say that S is a complete structure (of ϵ).
Note that due (B), S can be considered
a special case of a metaobject structure.
Every complete structure S is uniquely given by the
bounded membership ∊
according to the following table:
Inheritance
x ≤ y
↔
x = y or ∅≠ x.∍⊆ y.∍
Inheritance root
r.∍
=
O.∍
Bounded inheritance
x ∊^{0} y
↔
x ≤ y and x ∈O.∍
Singleton map
x.ɛϲ = y
↔
{x} = y.∍
Powerclass map
x.ec = y
↔
x.∍^{0}= y.∍
Power membership
x ϵ¯ y
↔
x.∍^{0}⊆ y.∍
Object membership
x ϵ y
↔
x ∊ y or x ϵ¯ y
The bounded inheritance relation is the zeroth power
of ∊,
similarly to the (≤) = (ϵ^{0}) correspondence.
By definition,
x.∍^{0}= x.↧∩O.∍.
There are other simplifications via ∊:
Terminal objects
T
=
O∖O.∊
Metalevel index
x.mli
=
min {i | x ∈T.∊^{i}, i ∈ℕ }
Rank
x.d
=
sup {a.d + 1 | a ∊ x}
The equalities for .mli and .d can be described
as follows.
S is ∊-levelled, that is,
every non-terminal object has a bounded member with a lesser metalevel index.
S is ∊-ranked, that is,
x.d equals the ∊-rank of x for every object x.
Moreover, there is a simple and transparent
axiomatization of complete structures via (O, ∊).
Such an axiomatization can be provided in a generalization for
arbitrary rank of ∊,
as shown in the next subsection.
(Realize that r.d equals by definition a fixed limit ordinal
ϖ.
Since r.d is also the ∊-rank of r
and r.∍=O.∍
it follows that
the rank of (O, ∊) equals ϖ+1.)
Superstructure
By an (abstract) superstructure we mean
a structure
(V, ∊)
(where
V is the set of objects, and
∊ is a relation between objects)
such that
the following conditions hold.
(1)
∊ is well-founded.
For a subset X of V let us denote r(X)
the ∊-rank of X.
(2)
For every non-empty set X of objects
such that r(X) < r(V)
there is a unique object x such that x.∍= X.
The existence and uniqueness of the x object in (2) can be stated separately:
(2a)
For every set X of objects
such that r(X) < r(V)
there is an object x such that x.∍= X.
(2b)
For every objects x, y from V.∊,
if x.∍= y.∍ then x = y.
(Weak extensionality of ∊)
It can be shown that up to isomorphism,
every non-empty superstructure (V, ∊)
is uniquely given by the pair (α, κ) of non-zero ordinal numbers
where
α is the ∊-rank of V
and
κ is the cardinality of the ground stage
(which is
the set V∖V.∊ of objects with zero rank,
i.e. the set of terminal objects).
For convenience, we let the term α-superstructure
mean a superstructure
(V, ∊) whose ∊-rank equals α.
The axiomatization of complete structures via ∊ can be then
expressed as follows:
(O, ϵ, ϵ¯^{⁽*⁾}, r, .ec, .ɛɕ)
is a complete structure of ϵ
↔
(O, ∊) is an (ϖ+1)-superstructure.
That is, the bounded membership ∊ in a complete structure
forms an (ϖ+1)-superstructure,
and, conversely,
an (ϖ+1)-superstructure (O, ∊)
induces a complete structure S according to the
table above.
Bounded membership in S coincides with the original ∊ relation.
Stages
Any superstructure can be thought to be built in stages.
For an ordinal number i, the i-th stage, V_{i},
consists of objects whose rank is strictly less than i.
In the case of an (ϖ+1)-superstructure
(O, ∊)
we obtain the following sequence:
V_{0}=∅,
V_{1}=T=O∖O.∊
(the ground stage),
V_{i+1}= { x | x.∍⊆V_{i} },
V_{i}=∪{ V_{j}| j < i }
for a limit ordinal i,
V_{ϖ}=O.∍=r.∍
(bounded objects),
V_{ϖ+1}=O.
Except for V_{0} and V_{ϖ+1}
each stage V_{i} is an ∊-preimage
of a unique stage object, r_{i}
(see the diagram on the right,
note that singletons not from T.ec^{∗} are
not shown).
Kinds of superstructures
With some adjustments,
the definitional extension of an
(ϖ+1)-superstructure (O, ∊)
as specified above
can be
applied to arbitrary superstructures (V, ∊).
Apart from the degenerate cases of empty ∊,
the adjustments to be made are the following:
Instead of referring to r as the unique object whose existence
is guaranteed,
introduce a predicate x being an inheritance root:
x is such that x.∍=V.∍.
Add the ∅≠ x.∍^{0} condition in the definitions
of .ec and ϵ¯.
We can then classify superstructures according to the properties of
their definitional extensions:
(Let ϖ be a limit ordinal and α an arbitrary ordinal.)
ZFC
MK
Degenerate cases
V=V_{ϖ}
V=V_{ϖ+1}
V=V_{α+2}
V=V_{1}
V=V_{0}
Rank of V
ϖ
ϖ + 1
α + 2
1
0
Bounded objects V.∍
V
V_{ϖ}
V_{α+1}
∅
∅
Existence of the (an) inheritance root r
(r.∍=V.∍)
NO
YES
YES
NO, unless V= {r}
NO
Powerclass map .ec is total
YES
YES
NO
YES
Singleton map .ɛϲ is total
YES
NO
NO
NO
YES
Boundedness preserved by .ec / .ɛϲ
YES
YES
NO
YES
YES
The ZFC and MK labels indicate a connection to set theory.
For an inaccessible cardinal ϖ,
a superstructure
(V, ∊) whose
ground stage contains exactly one object
(i.e. ∊ is extensional)
is a model of set theory:
ZFC (Zermelo-Frankel set theory with the Axiom of Choice) if the rank of
∊ equals ϖ,
MK (Morse-Kelley set theory) if the rank of
∊ equals ϖ + 1.
Note:
In
[],
the singleton map .ɛϲ is total
– unbounded objects have their singleton constantly set to r
(considering (V, ∊) as a model of MK).
Completion
Every basic structure
can be faithfully embedded into a complete structure.
That is, if
S_{0}= (O_{0}, ϵ, ϵ¯^{⁽*⁾}, r, .ec, .ɛɕ)
is a basic structure
then there is a
complete structure
V= (V, ϵ, ϵ¯^{⁽*⁾}, r_{ϖ}, .ec, .ɛɕ)
and
an embedding map .ν from O_{0} to V
such that the following conditions are satisfied:
.ν is embedding w.r.t. ϵ^{i} and ϵ¯^{i}
for every integer i,
r.ν =r_{ϖ},
.ν is embedding w.r.t. .ec and .ɛϲ,
.ν preserves being a primary object,
i.e. O_{0}.pr.ν ⊆V.pr,
.ν preserves the rank,
i.e.
x.d = x.ν.d
for every x ∈O_{0}.
Note:
If R denotes a relation both in S_{0} and V
then
.ν is an embedding w.r.t. R
if the following equivalence holds
for every objects x, y from O_{0}:
(x,y) ∈ R
↔
(x.ν, y.ν) ∈ R.
The embedding is established in the following steps:
Rank pre-completion.
This step can be omitted for ϖ= ω.
Otherwise, attach a set X of ϖ new members
to each primary non-well-founded object x
that is not ∊-ranked.
The members are attached
in such a way that (X, ϵ, ≤) is isomorphic
to (ϖ, ∈, ⊆).
Powerclass completion.
Append an infinite powerclass chain to each object for which the powerclass
is not defined.
The resulting structure is powerclass complete.
Singleton completion.
Append an infinite singleton chain to each bounded object for which the
singleton is not defined.
Technically, this can be done in two steps
by first adding just the missing primary singletons
and subsequently performing the powerclass completion.
Extensional pre-completion.(⁎)
To every object x that is not extensionally consistent,
i.e. for which there exists y such that the following equivalence is
not satisfied,
x ≤ y
↔
x = y or ∅≠ x.∍⊆ y.∍,
attach two powerclass chains each of which starts in a terminal object.
The resulting structure is pre-complete, that is,
extensionally consistent
(the above equivalence holds for every objects x, y),
powerclass consistent
(that is, if x is powerclass-like
then x is a powerclass
–
see [] for details),
powerclass complete,
singleton complete
(every bounded object x has a singleton x.ɛϲ), and
∊-ranked.
In particular, the structure is fully determined by bounded membership
∊
according to the same prescription as with
complete structures.
Note:(⁎)
A simplified description is provided here, see
[] for the detailed description.
Cumulative embedding into an (ϖ+1)-superstructure.
Let S= (O, ∊) be the pre-complete structure
to be embedded.
Choose an (ϖ+1)-superstructure V= (V, ∊)
so that its ground stage V_{1}
has the same cardinality as the set T of terminal objects of S.
Then the requested embedding map .ν is obtained as a limit of
a transfinite sequence
.ν_{0}, .ν_{1}, …, .ν_{ϖ}= .ν
of maps from O to V
defined as follows:
The restriction of .ν_{i} to terminals is for every i
identical and forms a bijection
between T and V_{1}.
The restriction of .ν_{i} to the set
O.∊
of non-terminal objects x is recursively defined by
x.ν_{0}.∍
=
x.∍¯.ν_{0}.ec.∍∪ x.∍.ν_{0},
x.ν_{i}.∍
=
x.϶¯.ν_{i-1}.ec.∍∪ x.∍.ν_{0}
if i is a successor ordinal,
x.ν_{i}.∍
=
∪{ x.ν_{k}.∍| k < i }
if i is a limit ordinal.
Note that the definition of .ν_{0}
is by the well-founded recursion on (O, ∊),
whereas the definition of .ν_{i} for i > 0
uses transfinite recursion over i.
Powerclass completion
Powerclass completion deserves particular attention since it is actually
implemented in Ruby.
For canonical primary structures,
the
completion has already been described, see the
(ec~3)
condition.
(Since (ϵ) = (ϵ¯), the term eigenclass
is used for powerclass.)
In general, for a basic structure
S_{0}= (O_{0}, ϵ▫, ϵ▫¯^{⁽*⁾}, …),
its powerclass completion
S= (O, ϵ, ϵ¯^{⁽*⁾}, r, .ec, .ɛɕ)
is created in the following steps:
Prolongate powerclass chains to infinity, that is,
extend (O_{0}, .ec) to (O, .ec)
so that
.ec is an injective well-founded map on O and
O_{0}∖O_{0}.ec =O∖O.ec
(new objects are powerclasses).
Extend membership and power membership powers to new objects.
For every primary objects
a, b
and every natural i, j such that
at least one of a.ec(i) or b.ec(j) is new,
a.ec(i) ϵ b.ec(j)
iff
a ϵ▫¯^{1+i-j} b,
a.ec(i) ϵ¯^{k} b.ec(j)
iff
a ϵ▫¯^{k+i-j} b
for every integer k.
Representation by sets
As already foreshadowed in the context of superstructures,
the main correspondence between objects and well-founded sets
can be expressed by
∊ ↔ ∈.
That is, bounded membership, ∊, is an abstraction of set membership,
∈.
Assuming powerclass completeness for simplicity,
the set-theoretic interpretation of the 3 main constituents of
the core structure of object technology can be
informally described via the following correspondences:
≤
↔
⊆,
that is, inheritance is an abstraction of set inclusion,
x.ec
↔
r∩ℙ(x),
that is,
the powerclass map is an abstraction of relativized powerset operator,
ϵ
↔
∈ plus .ec.↥
that is,
object membership is like set membership augmented with the inclusion
of the powerclass.
The von Neumann universe
Let 𝕍 be the von Neumann universe of all well-founded sets.
Recall that 𝕍 is obtained from the empty set
by iterative application of the powerset operator ℙ.
For every ordinal α,
𝕍_{α}=∪{ ℙ(𝕍_{β}) | β < α },
that is,
𝕍_{0}=∅,
𝕍_{α}=ℙ(𝕍_{α-1})
if α is a successor ordinal,
𝕍_{α}=∪{ 𝕍_{β}| β < α }
if α is a limit ordinal,
𝕍=∪{ 𝕍_{α}| α ∈On }.
(α ∈On means that α is an ordinal.)
The rank function r() on 𝕍 is defined by
r(x) = α
↔
x ∈𝕍_{α+1}∖𝕍_{α}.
For every ordinal α,
𝕍_{α} is a set whose members
are exactly the sets
x such that r(x) < α.
The axiom of foundation says that every set belongs to
𝕍.
(ϖ+1)-superstructure in ∈
The
(ϖ+1)-superstructure
V= (V, ∊)
referred to
in the last step of
the completion of object membership
can be chosen as a restriction of the set membership structure in
the von Neumann universe.
Given the requested cardinality κ of the ground stage,
one can proceed as follows.
Determine the ground stage.
Choose V_{1} to be a set such that
V_{1}⊆𝕍_{α+1}∖𝕍_{α}
for some ordinal α,
every element of V_{1} is a singleton set
(so that V_{1} is an antichain w.r.t. ⊆),
the cardinality of V_{1} equals κ.
Since for every ordinal i, the set
𝕍_{i+1}∖𝕍_{i} has cardinality at least i,
we can put α = κ+1.
Cumulate the remaining stages.
Similarly as with the von Neumann hierarchy,
construct a transfinite sequence of stages up to the (ϖ+1)-th stage.
V_{0}=∅,
V_{i}=V_{1}∪
(ℙ(V_{i-1}) ∖ {∅})
if i is a successor ordinal,
(in contrast, 𝕍_{i}=ℙ(𝕍_{i-1}))
V_{i}=∪{ V_{j}| j < i }
if i is a limit ordinal,
V=V_{ϖ+1}.
As a result, (V, ∈) is an (ϖ+1)-superstructure
such that for every x, y from V,
r(x) = α + x.d,
x ≤ y ↔ x ⊆ y.
Basic structure as a set
Since every basic structure can be embedded into an
(ϖ+1)-superstructure
which in turn can be embedded
into the von Neumann universe,
it follows
that
every basic structure S
can be represented by a well-founded set O.
The following table shows how the main constituents of S can be
expressed in set-theoretic terms.
(Recall that ℙ_{₁}(x)
is the set of singleton subsets of x.)
Terminal objects
T
=
O∩ℙ_{₁}(∪O∖O)
Inheritance root
r
=
∪O∖∪T
Complete extension
V
=
r∪ (ℙ(r) ∖ {∅})
For every x, y from O :
Bounded membership
x ∊ y
↔
x ∈ y
Inheritance
x ≤ y
↔
x ⊆ y
Singleton map
x.ɛϲ = y
↔
{x} = y
Powerclass map
x.ec = y
↔
r∩ℙ(x) = y
Power membership
x ϵ¯ y
↔
r∩ℙ(x) ⊆ y
Object membership
x ϵ y
↔
r∩ℙ(x) ⊆ y or x ∈ y
The V set represents a complete basic structure V
that is a faithful extension of S.
Specializations of ϵ
This section describes how the
canonical structure
of object membership
can be applied to object models of particular languages.
We focus on 8 class-based programming languages
Ruby,
Python,
Smalltalk-80,
Java, Scala,
CLOS,
Objective-C,
and Perl
which have already been
considered for the sample structure
of the instance-of relation.
Prototypal languages (JavaScript),
ontology languages (RDFS)
and the Dylan programming language
(as the only representant of non-monotonic membership)
are discussed separately.
Similarly, the support of actual eigenclasses is described in another section.
In a particular programming language, object membership appears in a specialized form.
Such a specialization can be obtained by adjustments to
the canonical structure of ϵ.
In most cases (5 of 8), it is necessary to refine the structure by additional
constituents so that the minimum signature (O, ϵ)
needs to be extended.
In Ruby
We have already described the Ruby's additional constraints for the
canonical structure:
single inheritance and
single explicit metaclass (C∩c.↧= {c}).
As of Ruby 1.9 (and newer), there are 4 helix classes:
c=Class < Module
< Object < BasicObject=r.
As a consequence of single inheritance,
the structure is determined by superclass and eigenclass links,
corresponding to the superclass and singleton_class
introspection methods, respectively.
However,
this is only the (canonical) reduct of what is understood by object membership
in Ruby.
The full membership, ϵ•,
results from a finer structure which takes module inclusion into account.
Modules are terminal instances of the Module class,
i.e. modules are Modules that are not Classes.
The additional structure is given by the own-includer-of
relation between Modules (classes, eigenclasses, modules) and modules.
If Μ denotes the reflexive closure
(i.e. Μ is self-or-own-includer-of)
then the ϵ• relation is given by
(ϵ•) = (ϵ) ○‣Μ.
This extended membership corresponds to the is_a? introspection method
(aliased by kind_of? and, in the inverse, also by Class#===).
You can check that previously we stated the is_a?↔ϵ
correspondence just for the provided sample structures.
Similarly, the canonical inheritance, ≤, is extended to ≤•
by
(≤•) = (≤) ○‣Μ
which, in the restriction to Modules,
corresponds to the <= introspection method.
This extended inheritance is a multiple inheritance.
In addition, since Ruby supports dynamic module inclusion, ≤•
can have anomalies (as to transitivity and/or antisymmetry),
the problem known as the double/dynamic inclusion problem.
[]
In Python
Assuming consistent setting of the __mro__ attribute of classes,
Python core structures are exactly the primary structures
(O.pr, ϵ, ≤) with two helix classes.
(Therefore, the Python object model conforms to the tight canonical structure.)
Helix classes are named as follows:
c=type < object=r
In Scala and Java
In Scala and Java, the term classes
is used just for a subset of the set C
of primary descendants of r.
The subset forms a closure system in (r.↧, ≤),
so that it can be expressed as C.c
where .c is an explicit closure operator added to the canonical structure.
The generalized structure is then of the form
(O, ϵ, .c).
This way the set C
is split into classes and non-terminal mixins.
In Scala, mixins are called traits,
in Java they are interfaces.
Mixins are not allowed to be metaclasses.
The structure is then subject to additional constraints.
There are no explicit metaclasses other than c, and,
more importantly, a single inheritance between classes applies
(but not between traits / interfaces).
The helix contains 3 classes:
c=Class < Object < Any=r.
For Java, the Any
class can be thought of as a fictitious root allowing primitive values to be objects
– they become objects that are not Objects.
Mixins (traits / interfaces) are among descendants of the Object class.
Java in addition disallows interleaving interfaces with classes,
so that x.c =Object for every interface x.
In Smalltalk-80
Both Pharo and Squeak, the two major Smalltalk-80 implementations,
provide several ways to break
fundamental characteristics of the core structure
such as
the one-to-one correspondence
between classes and implicit metaclasses
or acyclicity of inheritance.
The diagram below shows that
(1)
instantianting the class named Behaviour
(or Class or ClassDescription) creates a dangling class,
(2)
instantianting the class named Metaclass creates a dangling metaclass,
(3)
a class can be made a direct inheritance descendant of its metaclass.
The superclass: method allows to change the superclass link to
point to (presumably) arbitrary non-terminal object so that cycles can arise.
(Pharo 1.3 / Squeak 4.2)
r := ProtoObject.
b := Behavior.
c := Class.
mc := Metaclass.
(1)
a := Behavior new.
(2)
m := Metaclass new.
(3)
Object subclass: #B. B superclass: (B class).
We assume that the above anomalies are only allowed due to negligence
of implementations, not by design.
To rule out the anomalies, we only consider structures created
without instantiation or subclassing of Behavior or of its descendants,
without using the superclass: setter.
As already demonstrated on the
sample core structure,
the Smalltalk-80 object model does not conform to the canonical structure of
ϵ
due to the metaclass redirection.
This is expressed via an imposed metaclass root ȼ,
named Metaclass,
which induces the corresponding imposed class map,
.ȼlass.
This map coincides with the standard .class
map except for implicit metaclasses,
where it redirects
the value from the Class class to the Metaclass class,
introducing monotonicity breaks with respect to inheritance.
Note that the class introspection method
does not correspond to .ȼlass but to
.aȼlass
(the imposed actualclass map)
which takes object actuality into account.
Another quirk that can be captured by an appropriate generalization
of the canonical structure is formed by additional twist links.
These are inheritance child-parent pairs (x.ec, c)
where x is a subsidiary inheritance root –
a built-in parentless class other than r.
Each of Pharo and Squeak contains one such class,
named PseudoContext and ObjectTracer, respectively.
The Metaclass class is a sibling of the Class class.
Metaclasses can be defined as C.ȼlass.↧
– this makes Class and Metaclass the only explicit metaclasses.
Finally, the Ruby conditions apply:
single inheritance and single metalevel for classes.
Traits
Similarly to Ruby module inclusion,
Smalltalk-80 supports extension of inheritance via inclusion of terminal objects,
called traits.[]
Traits are Traits –
instances of the built-in Trait class.
Unlike in Ruby, the semantics of extended object membership, ϵ•,
is not reflected by the isKindOf: introspection method (as of Pharo 1.3).
In Objective-C
In Objective-C,
the eigenclass model has to be generalized to allow
multiplicity and degeneracy of inheritance roots.
There are several components of object membership, each with its own inheritance root.
In each component, the inheritance root r is the only helix class
so that r.class = r.
Equivalently, (r.ec, r) is the twist link.
As of GNUstep, there are (at least) 3 built-in inheritance roots,
named Object, NSObject and NSProxy.
Like in Smalltalk-80,
the Ruby conditions apply:
single inheritance and single metalevel for classes.
As a consequence of degeneracy,
metaclasses cannot be expressed as
C.class.↧ since this set contains all classes.
One possible solution is to simply define a metaclass as an object
on the metalevel 2 or higher (so that there are no explicit metaclasses).
In CLOS
The Common Lisp Object System deviates from the canonical structure in two features.
It introduces non-linear inheritance between helix classes
as well as an imposed class map with monotonicity breaks w.r.t. inheritance.
Unlike in Smalltalk, this imposed class map cannot be expressed via a constant
redirection target.
As of CLISP 2.49, there are 8 helix classes:
The missing 4 classes do not form a chain in inheritance.
Like in Python, there are no additional constraints:
multiple inheritance is supported as well as creation of explicit metaclasses.
In Perl 5
As already shown on the
sample structure,
the Perl object model is distinguished by total circularity of classes:
Every class is the class of itself.
This is equivalent to say that Perl establishes the
(C, ≤) = (C, ϵ) equality:
the instance-of relation, in its restriction to classes,
coincides with the inheritance relation.
This way Perl merges the two different meanings of
is-a.
Consequently, the isa introspection method can be used both
to detect membership as well as inheritance.
As for metaclasses, we can apply the solution proposed to Objective-C
and define metaclasses to be the objects on metalevel 2 or higher.
Since Perl does not have any actual objects on these metalevels,
there are no actual metaclasses.
In Perl, multiple inheritance is allowed.
The built-in class named UNIVERSAL stands for the
inheritance-root r.
However, the assumption is needed
that the @ISA variable of this class is not changed.
Eigenclass actuality
The concept of eigenclass actuality has already been
introduced
for the Ruby core structure.
Any in-memory representation of object membership
can only store a finite front part of the structure.
We call objects from this substructure actual(s).
In languages that do not support ϵ refined by implicit objects,
the actual objects are exactly the primary ones.
In general, some eigenclasses may also be actual.
Given a monotonic eigenclass structure(O, ϵ),
possible subsets A of actual objects can
be axiomatized as follows.
(For a set X of objects,
we let X.⋀ be the set of all strict upper bounds of X.)
(a~1)
A is finite.
(a~2)
A ⊇O.pr.
(Every primary object is actual.)
(a~3)
A ⊇ A.ce.
(If x.ec is actual then so is x.)
(a~4)
A is a closure system in ≤.
(Every object has a least actual ancestor.)
(a~5)
A ∩H= (R∖ A).⋀.
(There exist a natural k such that for every helix object x,
x ∈ A ↔ x.mli < k.)
Conditions
(a~4) and
(a~5) assert
that there is a twist pair of objects t, u
such that u ≻ t ∈R and u.↥= A ∩H.
(That is, u is the unique inheritance parent of a metalevel top t,
and u is the bottom of all actual helix objects.)
Since A is a closure system in inheritance,
there is a corresponding closure operator, .a,
and the corresponding actualclass map, .aclass = .ec.a.
For an object x,
the actualclass of x is the least actual container of x.
In canonical structures,
the .aclass map forms a tree (similarly to .class).
The u object that is the bottom of A ∩H
belongs to the eigenclass chain of c
(the instance / metaclass root)
and is the unique fixpoint of .aclass
(that is, u is the root of the actualclass tree).
Observe also that
x.ec ≤ x.aclass ≤ x.class.
While .ec
is a conceptual refinement of .class,
the actualclass map is an implementation-oriented refinement.
The .aclass map is identical to the .class map
iff no eigenclass is actual.
Note:
In most cases
(e.g. in the introductory sample),
the blue arrows contained in the diagrams show the actualclass map.
(In general,
blue arrows have been used to display
.aclass or .class or .class.↥ or
.aȼlass.)
Specializations
In Python, Java, CLOS, and Perl, eigenclasses are purely fictitious
– they are never actual,
so that the actualclass map coincides with the class map.
Scala allows eigenclasses of terminal objects, e.g. via the object definition.
In Smalltalk-80 and Objective-C, the set of actual eigenclasses equals
C.ec.
In Ruby
In Ruby, all objects that are not immediate values
can have actual eigenclasses.
As of
MRI/YARV 1.9
inheritance ancestors of actual objects are actual,
i.e. for the set A of actual objects
(a~6)
A is an up-set in ≤.
This condition is thus satisfied for implementations of all languages
with
(e~9⁺⁺)
considered in this document.
(In general, A needs to be replaced with A ∪ {r.ec}.)
Ruby is the only language that supports dynamic eigenclass allocation.
Typically, for an object x,
the eigenclass x.ec becomes actual by defining
singleton methods for x.
For efficiency, there are more allocated eigenclasses than those accessed
from the user code.
This induces 2 different extents of actuality,
as described before.
In Smalltalk-80
In Smalltalk, the imposed class map, .ȼlass,
has the corresponding imposed actualclass map, .aȼlass,
which corresponds to the introspection method named class.
Due to the metaclass redirection,
.aȼlass does not form a tree
but just a (directed) pseudotree with a 2-element cycle
containing the Metaclass class and its eigenclass.
The Dylan core structure
The Dylan programming language is presumably the first language
that introduced singleton objects
and
probably the only language (as of 2014) that supports
– at least experimentally –
both powerclasses and universal singletons.
The singleton support makes Dylan the only non-monotonic language considered
in this document.
Non-terminal objects in Dylan are called types[].
The following table shows 3 supported kinds of types
that have correspondence to basic structures.
(⁎)
As of Open Dylan 2013.2,
the <subclass> class is not referenced by its name.
Evaluation of subclass(x)
is supported for every x that is a class.
Evaluation of singleton(x)
is supported for all objects x.
As a consequence, there cannot be a perfect correspondence between
singletons in Dylan and singletons in basic structures
since the latter ones are only defined for bounded objects.
Every evaluation of singleton(x) or subclass(x)
(even when performed repeatedly with the same argument x)
returns a new object.
Such objects can be thought of as equivalent representants of a given
singleton or powerclass.
Sample
The following diagram shows a sample core structure of Dylan.
Inheritance between non-terminal objects can be detected by
the subtype? method.
The composition of blue arrows with inheritance
– object membership in Dylan –
is exactly what is detected
by the instance? method.
All powerclasses of classes
(i.e. all the supported powerclasses w.r.t. given set of classes)
are displayed.
In contrast, supported singletons are only shown for some objects.
(Open Dylan 2013.2)
let r = <object>;
let ty = <type>;
let c = <class>;
let si = <singleton>;
let lt = last(direct-superclasses(si));
let su = object-class(subclass(r));
let A = make(c);
let B = make(c, superclasses: list(A));
let u = make(B);
lt
…
<limited-type>
su
…
<subclass>
Observations:
There is a correspondence between
subclass types in Dylan and metaclasses in Smalltalk-80.
Dylan
Smalltalk-80
Powerclasses of classes (C.ec) are termed:
Subclass types
(Implicit) metaclasses
The (imposed) metaclass root ȼ is named:
<subclass>
Metaclass
For a class x, the powerclass x.ec is evaluated by:
subclass(x)
x class
The imposed class map .ȼlass is introspected by method:
object-class
—
The imposed actualclass map .aȼlass is introspected by:
—
class
There is a cycle in membership caused by singletons.
According to the instance? method,
<singleton> and
singleton(<singleton>) are members of each other.
Powerclasses (Dylan's subclass types) can only have classes as members.
As a consequence, (≤) ○‣ (.ec) ⊆ (ϵ)
is not satisfied in general.
For example,
u.ɛϲ
(the singleton of the terminal object u)
is from
B.↧ but not from B.ec.϶.
Prototypes
It is also possible to refine the instance-of relation the opposite way
by eigenclass predecessors of objects, rather than successors.
Such implicit objects are called (instance) prototypes.
The prototype of a class y, denoted y.ce,
is the highest instance of y,
i.e.
every instance of y is an inheritance descendant of y.ce.
In contrast to eigenclasses,
we only consider prototypes of classes.
First, it does not (seem to) make sense to have instance prototypes of terminal objects.
Second, having no prototypes of prototypes simplifies the description.
Formally,
object membership with prototypes
can be defined by combining eigenclasses and prototypes.
In the
specialized document[],
S1_{ȷ} structures
are introduced as
structures
(Θ, O, ϵ)
such that
(Θ, ϵ) is a
canonical eigenclass structure
without terminal objects,
and
O is a subset of Θ such that the substructure
(O, ϵ) is a canonical eigenclass structure
whose non-terminal objects form the set Θ.ec.↧.
Objects from Θ∖O are the instance prototypes.
The inclusion Θ.ec.↧⊆O
establishes a one-to-one correspondence between
the i-th metalevel of (Θ, ϵ)
and the (i+1)-th metalevel of (O, ϵ)
for each natural i.
Sample
The following diagram shows the prototypal completion
of the instance-of sample.
Blue links display the restriction of the class map
to the set C.ce of prototypes,
let it be denoted .ͼlass.
The (unrestricted) .class map is inherited from .ͼlass
The instance-of relation is given by (ϵ) = (≤) ○‣ (.class),
or by (ϵ) = (≤) ○‣ (.ͼlass),
or also by (϶) = (.ce) ○‣ (≥).
(In this particular case we do not need to distinguish between member-of and
and instance-of.)
(JavaScript)
var r, c, A, B, s, u, v;
r = Object
c = Function
A = new c
B = new c; B.prototype.__proto__ = A.prototype
s = new A
u = new B; v = new B
The missing inheritance between classes:
A.__proto__ = c.__proto__ = r; B.__proto__ = A
Note that r.ce becomes the new inheritance root
– the unique common ancestor of all objects
(in contrast to r which is just a common root for non-zero metalevels).
In JavaScript
As of ECMAScript, 5th Edition,
[]
the JavaScript programming language
provides a limited native support for object membership.
The (ideal) structure is established by 3 (partial) maps between objects,
.sc', .class, and .ce,
given by object properties named __proto__,
constructor and prototype, respectively.
For an object x and a class y,
x.__proto__ is the inheritance parent of x,
x.constructor is the class of x,
y.prototype is the instance prototype of y.
The constructor property is owned by prototypes and inherited by other objects.
In contrast, __proto__ and prototype are never (strictly) inherited.
The __proto__ property is non-standard.
When not supported, Object.getPrototypeOf(x) can be used for introspection.
The instance-of relation can be introspected via the instanceof operator,
except that y.prototype is not reported as an instance of y.
The Ruby conditions apply:
single inheritance between objects and single metalevel for classes.
In contrast to Ruby, Smalltalk or Objective-C,
JavaScript does not support parallel metalevel hierarchies.
Only inheritance between prototypes is supported, not between classes.
This is why we wrote .sc' instead of just .sc.
According to .sc', the inheritance parent of every class is
c.ce (Function.prototype).
However, the modification
(≤) → (≤') = (≤) ∖ (C, <)
has no impact to the instance-of relation:
we still have
(ϵ) = (≤') ○‣ (.class) = (≤') ○‣ (.ͼlass).
There are two helix classes:
c=Function < Object=r.
Note that we wrote <, not <' which does not hold.
As the names constructor or Function suggest,
JavaScript uses another terminology for the class map or the class set.
In JavaScript, classes are constructors and also functions.
Every constructor is a function.
Functions are the Functions.
Except for c.ce and
for native built-in functions like eval or parseInt,
every function is also a constructor.
Being terminal instances of c, the
native built-in functions account for the relaxation of
(p~5).
Another deviation from the canonical structure is caused by the
built-in Function.prototype.bind method.
A constructor x created using this method shares its
instance prototype x.ce with the constructor
to which x is bound
(although x.ce is not obtained via x.prototype.)
The above description of the JavaScript native core structure
is only valid under
ideal circumstances which are not guaranteed
by the ECMAScript standard.
For example, the constructor or prototype properties
can be almost arbitrarily manipulated.
To ensure validity, additional restrictions have to be imposed on state transitions.
Ontological structure of ϵ
A generalization of the canonical structure of ϵ allows
for a description of the core structure of ontologies in which classes are
(among) individuals.
We introduce a two-step generalization
motivated by the RDF Schema.[][]
The narrow definition can be characterized by the following features:
Distinction of properties as instances of a special class, p.
Properties, like terminal objects, are not descendants of the inheritance root.
In contrast to terminals,
properties can have (other properties as) ancestors / descendants.
Inheritance does not have to be antisymmetric –
distinct classes or properties can be descendants of each other and
thus become equivalent.
Multiple classification –
an object x can have multiple minimum classes of which x is an instance,
so that the existence of x.class is not guaranteed.
Disallowing the above features leads to primary (canonical) structures.
The broad definition further generalizes the narrow definition
by only using those constraints that are imposed by
RDFS axioms and entailments rules.
Narrow definition
By a primary ontological structure of ϵ we mean a structure
(Ō, ϵ, ≤, r, c, p)
with a similar terminology, notation and axioms as
canonical primary structures.
The differences are as follows.
p is a distinguished object whose instances are called properties.
We denote P the set of all properties.
The set T of terminal objects equals
Ō∖ (C∪P).
The structure is then subject to the following axioms:
(o~1)
Inheritance, ≤, is a preorder.
(o~2)
(a) (ϵ) ○‣ (≤) ⊆ (ϵ) and
(b) (≤) ○‣ (ϵ) ⊆ (ϵ).
(o~3)
(a) Only classes can have instances.
(b) Terminals have no strict descendants.
(o~4)
Helix classes are
(a) totally pre-ordered by ≤, and
(b) instances of each other.
(o~5)
Metaclasses can only have classes as instances.
(o~6)
Every non-helix object is well-founded w.r.t. ϵ.
(o~7)
(a)
Ō=r.϶.
(b)
C.ϵ⊆c.↥∪c.↧.
(o~8)
The set C of classes is finite.
(o~9)
c is a least helix class.
(o~10)
p is a class
not from c.↥∪c.↧.
Notes and observations:
Non-equivalence of r and c is asserted by
(o~10).
Condition
(o~7) is a weakening of the class map axiom
(p~7).
It asserts that
(a) every object has a container, and
(b) only helix classes or metaclasses can have classes as instances.
Condition
(o~10) asserts disjointness of classes and properties so that
Ō=T⊎P⊎C.
By the broad definition, a RDFS core structure
is a structure
(Ō, ϵ, ≤_{C}, ≤_{P}, r, c, p)
where
Ō is the set of objects or resources,
ϵ, ≤_{C}, and ≤_{P}
are
the instance-of, subclass-of and subproperty-of
relations on Ō, respectively,
and
r, c, and p are distinguished objects.
Instances of c form the set C of classes,
instances of p form the set P of properties.
The structure is subject to the following conditions:
(r~1)
The subclass-of relation, ≤_{C}, is a preorder on C.
(rdfs10) and (rdfs11)
(r~2)
The subproperty-of relation, ≤_{P}, is a preorder on P.
(rdfs5) and (rdfs6)
(r~3)
The subsumption rule applies: (ϵ) ○‣ (≤_{C}) ⊆ (ϵ).
(rdfs9)
(r~4)
Only classes can have instances.
(r~5)
Every object is an instance of r.
(r~6)
Every class is a subclass of r.
(rdfs8)
(r~7)
The objects r, c and p are pairwise distinct.
(r~8)
The set C∖P is finite.
(r~9)
p is a class.
The narrow definition is obtained from the broad one
by defining the inheritance relation ≤
as the reflexive closure of (≤_{C}) ∪ (≤_{P})
and making the following assertions:
(o~2)(b):
(≤) ○‣ (ϵ) ⊆ (ϵ),
(o~4): helix classes are …,
(o~6): well-foundedness of
ϵ on non-helix objects,
(o~7)(b):
C.ϵ⊆c.↥∪c.↧,
(o~9): c is a least helix class,
and
(o~10):
p is not from c.↥∪c.↧.
Built-in RDFS core
The built-in RDFS core structure is an RDFS core structure
(Ō,
ϵ, ≤_{C}, ≤_{P}, r, c, p)
shown by the following diagram.
We consider the set Ō to be equal to the RDF(S) vocabulary[],
so that objects are URI names.
Let ≤ be the reflexive transitive closure of green links
(implicitly directed upwards).
The ϵ relation is obtained as
(≤) ○‣ R ○‣ (≤) where R is the relation shown by blue links.
Subsequently,
≤_{P} and ≤_{C} are the restrictions of ≤
to p.϶ and c.϶, respectively.
‹ϵ›
…
rdf:type
‹≤_{P}›
…
rdfs:subPropertyOf
‹≤_{C}›
…
rdfs:subClassOf
r
…
rdfs:Resource
c
…
rdfs:Class
p
…
rdf:Property
Note that the structure is fairly regular.
It has single inheritance and single classification,
yielding the .class map.
The only feature not allowed in canonical structures
is strict inheritance between objects that are not descendants of r.
Similarly to the Python programming language,
there is a minimal non-degenerate chain of 2 helix classes:
c=rdfs:Class < rdfs:Resource=r.
In addition to c, there is a second built-in metaclass,
rdfs:Datatype.
Note:
The diagram shows the built-in structure according to RDF 1.1 Semantics
[]
which adds
rdf:HTML and rdf:langString
as 2 new built-in instances of rdfs:Datatype
to the previous 2004 version [].
Interpretation by RDF graphs
In RDF Schema,
data structures are encoded via RDF graphs.
By an RDF graph we mean a structure
(Ō, Ψ) such that
Ō is set of objects and
Ψ is a subset of
Ō^{3}=Ō×Ō×Ō.
Elements of Ō^{3} are triples of objects.
For a triple t = (s,p,o),
s is the subject,
p is the predicate, and
o is the object of t.
The relational extent of p ∈Ō
is denoted p.rel and defined as the set
{(s,o) | (s,p,o) ∈Ψ}.
We can now define an RDFS core graph as an RDF graph
(Ō, Ψ)
such that the following holds:
(1)
Ō includes the RDF(S) vocabulary.
In particular, there are six distinguished objects
‹ϵ›, ‹≤_{C}›, ‹≤_{P}›,
r, c and p.
We also denote ϵ, ≤_{C},
≤_{P} the relational extends of
‹ϵ›, ‹≤_{C}›, and ‹≤_{P}›,
respectively.
(2)
The structure
S= (Ō, ϵ, ≤_{C}, ≤_{P}, r, c, p)
is an RDFS core structure.
Since every object appears as a subject in some triple,
an RDFS core graph is completely given by its set of triples.
The built-in RDFS core graph is the minimum set of triples.
Any RDFS core graph is obtained by (explicitly) adding new triples
and subsequently
applying entailment rules –
the presence of some triples entails the presence of other triples.
There are entailment rules that refer to distinguished objects
not considered in the above description.
(In particular, the rdfs:domain and rdfs:range properties.)
As a consequence,
some of our RDFS core graphs are in fact not allowed by RDF Schema.
However,
RDF Schema still only guarantees the conformance to the broad definition
of ontological structure of ϵ.
None of
(o~2)(b),
(o~4),
(o~6),
(o~7)(b)[],
(o~9), or
(o~10) is asserted.
OWL 2
In OWL 2 Full [],
the structure of RDF Schema is extended by additional axiomatic triples.
The extension is then subject to the (additional) OWL 2 RL/RDF rules
[].
However, no conditions from the difference between narrow and broad
structures are asserted.
Built-in structure
The built-in structure contains additional 58 classes and 62 properties
[].
There are four helix classes, preordered by
which indicates that RDFS helix classes have their OWL equivalents.
Similarly, rdf:Property is equivalent to owl:ObjectProperty
and the metaclass rdfs:Datatype
is equivalent to (the metaclass) owl:DataRange.
In total, there are 7 built-in metaclasses,
including the bottom class, owl:Nothing,
a descendant of all classes which is disallowed to have instances.
There is still single inheritance between non-equivalent objects other
than owl:Nothing.
Single classification is not preserved (not even up to equivalence)
due to common instances of
owl:AnnotationProperty and
owl:OntologyProperty.
The restriction of inheritance to RDF(S) vocabulary is the same as
inheritance in the built-in RDFS core structure.
The restriction of instance-of is almost the same:
the rdfs:Literal class is made an instance of rdfs:Datatype
by a single additional axiomatic triple
[].
Powertypes
The interplay between inheritance, ≤, and membership, ϵ,
provided by the powerclass map, .ec, and
expressed by
(≥) = (.ec) ○‣ (϶)
has been investigated in type-theoretic setting
by Luca Cardelli
[].
Let us focus
just on the structure induced by the typing relation and the power type operator.
Then, if we denote ⅽ=r.ec,
the following correspondence can be established:
In
[],
the ⊆ symbol is used for subtyping.
The table shows also two other symbols that are common in the literature.
The correspondence between inheritance (as defined in this document)
and subtyping
should be taken in the restriction to non-terminal objects.
A value is usually not considered to be a subtype of itself.
In the
specialized document[],
Cardelli's six typing rules are distinguished
(those that can be expressed by just :, Power() and Type)
to form
an abstract power type system(O, ϵ, .ec, ⅽ).
Subsequently, additional conditions are provided so that the resulting
family of structures is definitionally equivalent to
basic structures of ϵ such that x.ec
is defined exactly for non-terminal objects x.
Powertypes in metamodelling
The Cardelli's notion of power types has been adopted by J. Odell
in the field of metamodelling
[].
However,
whereas Cardelli's power type is an abstraction of powerset,
Odell's power type is an abstraction of a non-trivial partition.
In particular, in metamodelling,
a type can have more than one power type, and
there is no typing relation (instance-of)
between a type and its power type.
Since for every sets x, y,
y being a non-trivial partition of x
is a special case of
x being a non-member union of y,
the semantic shift
can be diagrammatized by
Daniel Bobrow, Gregor Kiczales,
The common Lisp object system metaobject kernel: a status report,
Proceedings of the 1988 ACM conference on LISP and functional programming,
ACM1988,
Daniel Bobrow, Mark Stefik,
The LOOPS Manual,
Xerox Corporation1983,
Grady Booch, Robert A. Maksimchuk, Michael W. Engel, Bobbi J. Young, Jim Conallen, and Kelli A. Houston,
Object-oriented analysis and design with applications,
Vol. 3,
Addison-Wesley2008,
Ronald J. Brachman,
What IS-A is and isn't: An analysis of taxonomic links in semantic networks,
Computer 16.10,
North-Holland1983,
Kim B. Bruce,
Foundations of Object-Oriented Programming Languages: Types and Semantics,
MIT Press2002,
Jean-Pierre Briot, Pierre Cointe,
The OBJVLISP Model: Definition of a Uniform, Reflexive and Extensible Object Oriented Language,
European Conference on Artificial Intelligence (ECAI'86), Advances in Artificial Intelligence-II,
North-Holland1986,
Jean-Pierre Briot, Pierre Cointe,
A Uniform Model for Object-Oriented Languages Using the Class Abstraction,
Tenth International Joint Conference on Artificial Intelligence (IJCAI'87),
1987,
C. C. Chang, H. Jerome Keisler,
Model Theory,
Studies in Logic and the Foundations of Mathematics (3rd ed.),
Elsevier,
1990,
David Chisnall,
Cocoa Programming Developer's Handbook,
Addison Wesley2009,
Pierre Cointe,
Metaclasses are First Class: the ObjVlisp Model ,
Proceeding OOPSLA '87 Conference proceedings on Object-oriented programming systems, languages and applications ,
North-Holland1987,
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-Verlag2001,
http://cs.ulb.ac.be/publications/P-01-01.pdf
David Flanagan,
JavaScript: The Definitive Guide, Sixth Edition,
O'Reilly2011
Neal Feinberg, Sonya E. Keene, Robert O. Mathews, and P. Tucker Withington,
Dylan Programming: An Object-oriented and Dynamic Language,
Addison Wesley1996opendylan.org/books/dpg/
Ira R. Forman, Scott H. Danforth,
Putting Metaclasses to Work,
Addison Wesley1998
Ira R. Forman, Nate Forman,
Java Reflection in Action,
Manning Publications2005
Cesar Gonzalez-Perez, Brian Henderson-Sellers,
A powertype-based metamodelling framework,
Software & Systems Modeling 5.12006
Daniel Ingalls,
The Smalltalk-76 programming system design and implementation,
Proceedings of the 5th ACM SIGACT-SIGPLAN symposium on Principles of programming languages,
ACM,
1978
Satoshi Matsuoka, Akinori Yonezava,
Metalevel solution to inheritance anomaly in concurrent object-oriented languages,
Proceedings of the ECOOP/OOPSLA'90 Workshop on Reflection and Metalevel Architectures in Object-Oriented Programming1990
Satoshi Matsuoka,
Language Features for Re-Use and Extensibility in Concurrent Object-Oriented Programming Languages,
1993
Linda G. DeMichiel, Richard P. Gabriel,
The common lisp object system: An overview,
ECOOP'87 European Conference on Object-Oriented Programming1987
Oscar Nierstrasz, Stéphane Ducasse, Damien Pollet,
Pharo by Example,
Square Bracket Associates2009,
http://pharobyexample.org
James J. Odell,
Power Types,
Journal of Object-Oriented Programming 7.21994
Reza Razavi, Noury Bouraqadi, Joseph Yoder, Jean-François Perrot, Ralph Johnson,
Language support for Adaptive Object-Models using Metaclasses ,
Computer Languages, Systems & Structures, 31(3)2005,