|
#REDIRECT [[Ruby (programming language)#Semantics and philosophy]]
{{original research|date=October 2013}}
<!-- Please do not remove or change this AfD message until the issue is settled -->
{{Article for deletion/dated|page=Eigenclass model|timestamp=20130918202844|year=2013|month=September|day=18|substed=yes}}
<!-- For administrator use only: {{Old AfD multi|page=Eigenclass model|date=18 September 2013|result='''keep'''}} -->
<!-- End of AfD message, feel free to edit beyond this point -->
{{technical|date=October 2012}}
{{TOC right|limit=3|width=30ex}}
In [[object-oriented programming|object-oriented]] [[Computer programming|programming]], an '''eigenclass model''' is an [[abstract structure]]{{efn|
In the wider sense, the eigenclass model is an [[Abstract state machines|abstract state machine]] (ASM) – a system of structures together with transitions between them. It can be considered the most abstract non-trivial ASM of object-oriented programming.
}}
that constitutes a fundamental part of the [[object model]] using the concept of ''eigenclasses''. Eigenclasses are auxiliary (mostly just fictitious) class-like objects that establish [[infinite regress]] via the eigenclass [[Function (mathematics)|map]]: for every object ''x'', the eigenclass of ''x'' is the unique own meta-object of ''x'' that is one meta-level higher than ''x''.
{{RCS|
As a complementary constituent to the eigenclass map, the model encompasses the [[Inheritance (object-oriented programming)|inheritance]] relation. The composition of the eigenclass map with inheritance gives rise to ''object membership'',
{{R with history}}
a relation between objects, denoted ϵ ([[lunate epsilon]]).<ref name="ome">{{cite web | url=http://www.atalon.cz/om/object-membership/ | title=Object Membership: The core structure of object-oriented programming }}</ref>
{{R without mention}}
This relation is a generalization of the ''instance-of'' relation and can be viewed as a [[Non-well-founded set theory|non-well-founded]] counterpart of [[set membership]], ∈.
As a result, the eigenclass model provides a uniform and mathematically precise description of the core structure of class-based
programming languages in which classes are (or can be considered as) objects. In particular, the model applies to the language [[Ruby (programming language)|Ruby]], [[Python (programming language)|Python]], [[Scala (programming language)|Scala]],
[[Java (programming language)|Java]], [[Smalltalk (programming language)|Smalltalk]], [[Objective-C (programming language)|Objective-C]], [[Common Lisp Object System|CLOS]] and [[Perl]].
<!-- -->
Generally, the model relates to the core part of data models in which classes appear as objects. As a consequence, the model relates to [[ontology language]]s such as [[RDF Schema]] or [[Web Ontology Language|OWL]]. A good indicator of applicability is the presence of the notion of [[metaclass]].
One can distinguish two degrees of applicability. High degree is assigned to languages that allow an actual reference to an eigenclass: Ruby, Smalltalk, Objective-C and, in a lesser sense, Scala. Low degree is assigned to languages in which eigenclasses are a purely fictitious concept. In this latter case the eigenclass model can be regarded as an abstract device for joining inheritance with the instance-of relation.
== History ==
The inception of the eigenclass model with referenceable eigenclasses can be attributed to [[Smalltalk (programming language)|Smalltalk-80]] which introduced ''implicit metaclasses''. In Smalltalk, every class has its own metaclass, and metaclass inheritance parallels class inheritance.
In 1988, [[Luca Cardelli]] introduced the notion of ''power types''<ref>
{{cite web | author=Luca Cardelli | url=http://www.daimi.au.dk/~madst/tool/tool2004/papers/structural.pdf | title=Structural Subtyping and the Notion of Power Type}}</ref> which can be regarded as type-theoretic counterparts to eigenclasses.
The notion has later been adopted in the field of [[Metamodeling|metamodelling]].<ref>{{cite journal |last=Odell |first=James |title=Power Types |journal=Journal of Object-Oriented Programming |volume=7 |year=1994 |number=2 |pages=8–12}}</ref>
<ref>{{cite web | author=C. Gonzalez-Perez, B. Henderson-Sellers | url=http://www.ie.inf.uc3m.es/grupo/docencia/reglada/ASDM/GonzalezPerez06.pdf | title=A powertype-based metamodelling framework}}</ref>
(Nowadays, the single word ''"powertypes"'' is preferred.)
A full and consistent application of the eigenclass model appeared in 1995 as a core part of the [[Ruby (programming language)|Ruby programming language]], created by [[Yukihiro Matsumoto]]. The term ''"eigenclass"'' emerged around 2005 in the Ruby community. In 2008, the term has been established in an authoritative book,<ref>{{cite book | publisher=O'Reilly Media | author=David Flanagan, Yukihiro Matsumoto | url=http://oreilly.com/catalog/9780596516178/ | title=The Ruby Programming Language | isbn=978-0-596-51617-8}}</ref> replacing the previously used ''"singleton class"'' (although in Ruby 1.9, the corresponding introspection method is still named <code>singleton_class</code>).
By simplification, the development history of the eigenclass model can be viewed as a 3-stage extension of a universality principle, summarized by the following table:
{| class="wikitable"
|-
! Year
! Inventor
! The principle
! … in terms of the eigenclass model
|-
| style="white-space:nowrap" | c. 1980
| James Althoff<ref>
{{cite web | url=http://mail.python.org/pipermail/python-dev/2001-May/014508.html | title=[Python-Dev] Classes and Metaclasses in Smalltalk }}</ref>
| Every class has its own metaclass.
| Every class has an eigenclass.
|-
| c. 1988
| Luca Cardelli
| Every type has a power type.
| Every class and every eigenclass has an eigenclass.
|-
| c. 1995
| Yukihiro Matsumoto
| colspan=2 style="text-align:center" | Every object has an eigenclass.
|}
== {{anchor|canonical structure}} The canonical structure of ϵ ==
In its rudimentary form, the eigenclass model can be described as a canonical structure ''(<u>O</u>,'' ϵ'')''
with subsequently introduced notation, terminology and axioms. For convenience, an example structure is provided first.
=== Example ===
The following diagram shows an example of the canonical structure ''(<u>O</u>'', ϵ'')'', together with corresponding Python code.
{| style="margin:2ex auto;"
|-
| [[File:Eigenclass-model-sample-a.svg|400px|Eigenclass model - A sample canonical structure|]]
| style="padding-left: 3ex;" | <code>
<pre style="font-family:'Lucida Console',monospace; color:brown;">
r = object
c = type
class M(c): pass
class A(metaclass=M): pass
class B(A): pass
b = B()</pre>
</code>
|}
The structure contains 6 [[#Primary objects|primary objects]]:
2 [[#Helix|helix]] classes
(the [[#Inheritance root|inheritance root]] ''<u>r</u>'' and the [[#Instance root|instance root]] / metaclass root ''<u>c</u>''),
3 other [[#Classes|classes]] (<code>M</code>, <code>A</code> and <code>B</code>),
and 1 [[#Terminal objects|terminal object]] (<code>b</code>).
Right-directed arrows (in gray) show the eigenclass map,
up-directed arrows (in green) show the child-parent relation of [[#Inheritance|inheritance]].
The {{color|green|''∫''}}-shaped arrows are the [[#Twist links|twist links]].
[[#Eigenclasses|Eigenclasses]] are shown as unnamed nodes in gray. Each eigenclass chain is infinite – the diagram displays just an initial part, without descendants of the fourth eigenclass of ''<u>r</u>''.
The structure contains 2 explicit [[#Metaclasses|metaclasses]]: the metaclass root ''<u>c</u>'' and the user-created metaclass <code>M</code>. The remaining inheritance descendants of ''<u>c</u>'' (i.e. all eigenclasses except the eigenclass of <code>b</code>) are implicit metaclasses.
=== Objects ===
The universum of the model is the set ''<u>O</u>'' of abstract entities called ''objects''. By further axioms, this set is asserted to be [[countably infinite]].
=== Object membership ===
The ''object membership'' relation, ϵ, is a (binary) relation between objects. For objects ''x'', ''y'', if ''x'' ϵ ''y'',
then ''x'' is a ''member-of'' ''y'' and ''y'' is a ''container-of'' ''x''. By axiom (1), object membership is uniquely decomposable into the eigenclass map and the inheritance relation, which can be written as
:(ϵ) = (''.ec'') ○ (≤)
where the composition symbol '○' is interpreted left-to-right, i.e. ''x'' ϵ ''y'' iff ''x.ec'' ≤ ''y''.
=== Inheritance ===
The ''inheritance'', denoted ≤, is a relation between objects defined by
:''x'' ≤ ''y'' iff ''y'' ϵ ''a'' implies ''x'' ϵ ''a'' for every object ''a'' (i.e. every container of ''y'' is a container of ''x'').
Axiom (2) asserts antisymmetry of ≤, so that inheritance is a [[partial order]]. Furthermore, axiom (1) asserts that
<span style="white-space:nowrap">(ϵ) ○ (≤) = (ϵ)</span>, i.e.
:''x'' ≤ ''y'' only-if ''a'' ϵ ''x'' implies ''a'' ϵ ''y'' for every object ''a'' (every member of ''x'' is a member of ''y''),
which indicates that the inheritance relation, ≤, has the semantics of the [[subset]] relation, ⊆.
If ''x'' ≤ ''y'' then ''x'' is a ''descendant'' of ''y'' and
''y'' is an ''ancestor'' of ''x''.
For an object ''x'', ''x''.↥ (resp. ''x''.↧) denotes the set of all (non-strict) ancestors (resp. descendants) of ''x''.
Similarly, for a set ''X'' of objects,
''X''.↥ (resp. ''X''.↧) is the [[Upper set|upset]] (resp. downset) of ''X''.
Direct ancestors ([[Covering relation|covers]]) of ''x'' are called
''parents'' of ''x''.
<!-- and denoted ''x.parents''. -->
=== Eigenclasses ===
The ''eigenclass-of'' an object ''x'', denoted ''x.ec'', is the container of ''x'' that is least (lowest) in the inheritance ≤.
Axiom (1) asserts that every object has its eigenclass. Furthermore, (1) and (2) imply that the ''.ec'' map is an [[order embedding]] with respect to ≤. In particular, ''.ec'' is [[Injective function|injective]] – different objects have different eigenclasses.
Another consequence of (1) is that for every objects ''x'', ''y'',
:''x'' ϵ ''y.ec'' iff ''x ≤ y'',
showing that the eigenclass map corresponds to the [[powerset]] operator.
The ''i''-th application of ''.ec'' to ''x'' is denoted ''x.ec(i)''. By further axioms, each component of the eigenclass map is an infinite chain
''x = x.ec(0)'', ''x.ec = x.ec(1)'', ''x.ec.ec = x.ec(2)'', … starting in a primary object ''x''.
An ''eigenclass'' is an object that belongs to ''<u>O</u>.ec'', the [[Image (mathematics)|image]] of ''.ec''.
=== Primary objects ===
Objects that are not eigenclasses are ''primary''. Axiom (6) asserts that the set of all primary objects forms a closure system in inheritance, i.e. the set appears as the image of a (necessarily unique) [[closure operator]], denoted ''.c'', in inheritance.
For each object ''x'', the primary object ''x.c'' is the least primary ancestor of ''x''.
Axiom (7) asserts that ''.c'' preserves ϵ.
As a consequence, ''.c'' is a [[Homomorphism#Homomorphisms_of_relational_structures|homomorphic]] [[Projection (mathematics)|projection]] of
<span style="white-space:nowrap">''(<u>O</u>'', ϵ, ≤'')''</span>
onto the [[#Primary_structure|primary structure]],
<span style="white-space:nowrap">''(<u>O</u>.c'', ϵ, ≤'')''</span>.
Primary objects are further divided into ''terminals'' and ''classes'' which can be expressed as
:''<u>O</u>.c = <u>T</u>'' ⊎ ''<u>C</u>''.
=== Classes ===
An object is a ''class'' if it is primary and either is its own member or is not maximal in inheritance
(i.e. has parents). The set of classes is denoted ''<u>C</u>''. Classes together with eigenclasses form the set of all descendants
of the inheritance root ''<u>r</u>'', i.e. ''<u>r</u>''.↧ = ''<u>C</u>'' ⊎ ''<u>O</u>.ec''.
Using the [[#is-a|is-a]] naming convention, this set is equal to the set of <code style="color:#700000">Class</code>es, where <code style="color:#700000">Class</code> is the name for the instance root ''<u>c</u>''.
=== Terminal objects ===
An object is ''(a) terminal'' if it is neither a class nor an eigenclass. The set of terminals is denoted ''<u>T</u>''.
Therefore, the set of objects is a disjoint union of the sets of terminals, classes and eigenclasses:
:''<u>O</u> = <u>T</u>'' ⊎ ''<u>C</u>'' ⊎ ''<u>O</u>.ec''.
Terminals can be equivalently characterized as objects that are both maximal and minimal in inheritance.
=== Class map ===
[[File:Eigenclass-model-class-map.svg|
Eigenclass model - The class map|
right|
250px
]]
The ''class-of'' an object ''x'', denoted ''x.class'', is the smallest container of ''x'' that is a class.
Axiom (6) asserts that ''x.class'' is defined for every ''x''.
Equivalently, the ''.class'' map can be written as ''.ec.c'' where
''.c'' is the closure operator in ≤ such that the image
''<u>O</u>.c'' is the set of [[#Primary_objects|primary objects]].
As a consequence, ''.class'' is a [[Monotone_map#Monotonicity_in_order_theory|monotone map]].
Axiom (8) asserts that the ''.class'' map forms a tree – the ''instance tree''.
The diagram on the right shows the class map for the [[#Example|example]] structure, in the restriction to primary objects.
To illustrate the ''.ec.c'' composition, the arrows are drawn along eigenclass paths.
=== Instance of ===
The ''instance-of'' relation is defined as the range-[[Restriction (mathematics)|restriction]] of object membership to classes, i.e.
:''x'' is an instance of ''y'' iff ''x'' ϵ ''y'' and ''y'' is a class.
The relation can be expressed as (ϵ) ○ (''.c'').
The ''direct instance-of'' relation is the ''.class'' map taken as a relation, i.e.
:''x'' is a direct instance of ''y'' iff ''x.class = y''.
The direct-instance-of, instance-of and member-of relations form an inclusion chain:
:(''.class'') ⊂ (ϵ) ○ (''.c'') ⊂ (ϵ).
=== {{anchor|is-a}} Membership as is-a ===
If ''x'' is a member of an object named <code style="color:#700000">B</code>
(in particular, if ''x'' is an instance of the <code style="color:#700000">B</code> class) then one can say that <span style="white-space:nowrap">''x'' ''is-a'' <code style="color:#700000">B</code></span>.
The set of all members of <code style="color:#700000">B</code> (instances of the <code style="color:#700000">B</code> class) can be referred to as <code style="color:#700000">B</code>s.
If <code style="color:#700000">A</code> and <code style="color:#700000">B</code> are classes such that
<code style="color:#700000">A</code> ≤ <code style="color:#700000">B</code> then one can say that
:an <code style="color:#700000">A</code> is a <code style="color:#700000">B</code>,
meaning that an instance of <code style="color:#700000">A</code>
is also an instance of <code style="color:#700000">B</code>.
Unfortunately, this leads to an interpretation (which can be considered a misinterpretation) of the is-a relation such that
:<s>the <code style="color:#700000">A</code> class is-a the <code style="color:#700000">B</code> class</s>,
i.e. the is-a relation is regarded as synonymous to the inheritance relation.
=== Helix ===
An object ''x'' is a ''helix'' object if it is its own member,
i.e. ''x'' ϵ ''x''.
The set of all helix objects is denoted ''<u>H</u>''.
Axiom (4)(c) asserts that ''(<u>H</u>'', ≤'')'' is a [[linear order]] so that the object membership structure restricted to ''<u>H</u>'' can be visualised as a circular [[helix]].
The helix has the inheritance root, ''<u>r</u>'', as a start-point (origin), the other side is infinite.
Eigenclass chains are parallel to the helix axis.
Each complete turn away from the origin corresponds to one application of the eigenclass map.
==== Inheritance root ====
The ''inheritance root'', ''<u>r</u>'', is the highest helix class – a common ancestor of all non-terminal objects.
Its existence is asserted by axiom (4)(a).
==== Instance root ====
The ''instance root'', ''<u>c</u>'', is the lowest helix class, usually named <code>Class</code>.
It can also be specified as ''<u>r</u>.class'' or, explaining the terminology, as the root of the instance tree – it is the only object ''x'' such that ''x.class = x''.
Axiom (4)(b) asserts that ''<u>c</u>'' is different from ''<u>r</u>''.
==== Twist links ====
The child-parent pair ''(<u>r</u>.ec, <u>c</u>)'' is the ''(front) twist link''.
Axiom (4)(d) asserts that ''<u>r</u>.ec'' is the only child of ''<u>c</u>''.
In addition, it is asserted that ''<u>c</u>'' is the only parent of ''<u>r</u>.ec''.
The same conditions hold for all twist links
''(<u>r</u>.ec(i+1), <u>c</u>(i))''.
==== Reduced helix ====
Let ''<u>R</u>'' denote the eigenclass chain
{''<u>r</u>'', ''<u>r</u>.ec(1)'', ''<u>r</u>.ec(2)'', …}
of the inheritance root.
Being a distinguished subset of ''<u>H</u>'', the set ''<u>R</u>'' can be called the ''reduced helix''.
Helix objects are the ancestors of objects from the reduced helix, i.e.
''<u>H</u> = <u>R</u>.''↥.
Assuming finiteness of the set of primary objects (asserted by (9)(b)), condition (9)(a) can be equivalently replaced by the requirement that the reduced helix has no [[Upper and lower bounds|lower bound]] in inheritance, i.e. there is no object ''x'' such that
''<u>R</u>'' ⊆ ''x.''↥.
As a consequence, ''<u>R</u>'' is a closure system in
<span style="white-space:nowrap">''(<u>O</u>'' ∖ ''<u>T</u>'', ≤'')''</span> and so is ''<u>H</u>''.
=== Metaclasses ===
An object is a ''metaclass'' if it is a descendant of ''<u>c</u>'', so that
the set of all metaclasses is simply expressed as ''<u>c</u>''.↧.
The instance root ''<u>c</u>'' is therefore also the ''metaclass root''.
Metaclasses are either ''explicit'' or ''implicit'' according to whether they are classes or eigenclasses, respectively.
An object is an implicit metaclass iff it is an eigenclass of a non-terminal object.
Under the assumption that every class has a direct instance, i.e. ''<u>O</u>.class = <u>C</u>'', the following symmetric formula applies:
:''<u>c</u>''.↧ = ''<u>O</u>.ec.class'' ⊎ ''<u>O</u>.class.ec'' ⊎ ''<u>O</u>.ec.ec'',
i.e. an object is a metaclass if it is either the class of an eigenclass or the eigenclass of a class or the eigenclass of an eigenclass.
Using axiom (7) and substituting ''<u>C</u>'' for ''<u>O</u>.class'' we obtain
:''<u>c</u>''.↧ ∖ ''<u>O</u>.ec(2)'' = ''<u>C</u>.class'' ⊎ ''<u>C</u>.ec'',
i.e. aside from higher-order eigenclasses, explicit metaclasses are ''classes-of'' classes (''<u>C</u>.class'') whereas implicit metaclasses are ''eigenclasses-of'' classes (''<u>C</u>.ec'').
The classical definition of metaclasses as "''classes whose instances are classes''"<ref>
{{cite book|author=Ira R. Forman and Scott Danforth|title=Putting Metaclasses to Work|year=1999|isbn=0-201-43305-2}}</ref>
applies as follows:
:Metaclasses are <code style="color:#700000">Class</code>es whose all members are <code style="color:#700000">Class</code>es.
This definition is valid if and only if each class that is not a metaclass has at least one terminal instance, i.e.
<span style="white-space:nowrap">''<u>C</u>'' ∖ ''<u>c</u>''.↧ ⊆ ''<u>T</u>.class''.↥</span>
(in particular, the parent of ''<u>c</u>'' = <code style="color:#700000">Class</code> must have a terminal instance so that helix classes other that ''<u>c</u>'' are ruled out by the "all" adverb).
=== Axioms ===
The canonical structure ''(<u>O</u>'', ϵ'')'' of object membership is subject to the following conditions:
<ol style="list-style-type:none; margin-left: 2ex;">
<li style="text-indent:-3ex; margin-left:3ex;">(1)
Containers of an object ''x'' are exactly the
ancestors the eigenclass of ''x'',
i.e.
:(ϵ) = (''.ec'') ○ (≤) for a unique map ''.ec''.
<li>(2)
Distinct objects have distinct sets of containers.
<li>(3)
Terminals are minimal in inheritance.
<li>(4)
Helix objects satisfy the following properties:
<ol style="list-style-type:none; margin-left: 3ex;">
<li>(a)
All non-terminal objects are descendants of a single object,
the inheritance root ''<u>r</u>''.
<li>(b)
The eigenclass of ''<u>r</u>'' has at least 2 strict ancestors.
<li>(c)
The set ''<u>H</u>'' of helix objects is linearly ordered by inheritance.
<li>(d)
For every ''i > 0'', the eigenclass ''<u>r</u>.ec(i)'' has no siblings.
<li>(e)
Every helix descendant of ''<u>r</u>.ec'' is an eigenclass.
</ol>
<li>(5)
Descendants of non-helix eigenclasses are eigenclasses.
<li>(6)
Every object ''x'' has a least container that is a class, ''x.class''.
<li>(7)
For every object ''x'', ''x.ec.class = x.class.class''.
<li style="text-indent:-3ex; margin-left:3ex;">(8)
There is a helix object ''h'' such that for every non-helix class ''x'', the sets ''h''.↧ and ''x''.↧
are disjoint.
<!--
<li>(8)
There is a helix object ''h'' such that the set ''h''.↧.↥ does not contain non-helix classes.
-->
<li>(9)
The following finiteness conditions hold:
<ol style="list-style-type:none; margin-left: 3ex;">
<li>(a)
Every object has finite number of ancestors.
<li>(b)
The set of primary objects is finite.
</ol>
</ol>
Axiom (7) can be expressed without a reference to the ''.class'' map as equality of the
''member-of-instance-of'' relation with the
''instance-of-instance-of'' relation.
== The primary structure {{anchor|Primary_structure}} ==
The restriction of a canonical structure of object membership
to primary objects can be expressed as a structure
<span style="white-space:nowrap">''(<u>O</u>.c'', ϵ, ≤'')''</span>
where
<ul>
<li>
''<u>O</u>.c'' is the set of (primary) objects,
<li>
ϵ is the ''instance-of'' relation between (primary) objects,
<li>
≤ is the ''inheritance'' relation between (primary) objects.
</ul>
''Helix classes'' are (primary) objects ''x''
such that ''x'' ϵ ''x''.
''Classes'' are (primary) inheritance descendants of helix classes.
''Terminals'' are the remaining (primary) objects.
''Metaclasses'' are the [[Upper and lower bounds|lower bounds]] of helix classes, i.e. they are objects ''x'' such that
all helix classes are among ancestors of ''x''.
<!-- -->
The structure is subject to the following axioms:
<ol style="list-style-type:none; margin-left: 2ex;">
<li style="text-indent:-3ex; margin-left:3ex;">(p~1)
(ϵ) ○ (≤) = (ϵ) = (≤) ○ (ϵ).
<li>(p~2) Inheritance ≤ is a partial order.
<li>(p~3)
Terminals have neither strict descendants nor instances.
<li style="text-indent:-3ex; margin-left:3ex;">(p~4)
Helix classes are totally ordered by inheritance, and at least two in number.
<li>(p~5) Metaclasses cannot have terminal instances.
<li>(p~6) Every object ''x'' has a least (primary) container,
''x.class''.
<li>(p~7) Cycles in ϵ only occur between helix classes.
<li>(p~8) The set of primary objects is finite.
</ol>
[[File:Eigenclass-model-sample-pr.svg|
Eigenclass model - The primary structure|
right|
225px
]]
The diagram on the right shows the primary structure that is the restriction of the [[#Example|example]] structure.
The instance-of relation is obtained as the composition
<span style="white-space:nowrap">(≤) ○ (''.ͼlass'') ○ (≤)</span> where
''.ͼlass'' is the ''class map reduction''
– the "non-inherited" part of the ''.class'' map
(displayed by dark blue arrows).
=== Eigenclass completion ===
Axiom [[#Axioms|(5)]] can be considered in the following stronger form
since it is satisfied in all mentioned programming languages (and presumably all relevant ones in general):
<ol style="list-style-type:none; margin-left: 2ex;">
<li>(5')
Descendants of eigenclasses-other-than-''<u>r</u>.ec'' are eigenclasses.
</ol>
Assuming (5'), the object membership structure,
<span style="white-space:nowrap">''(<u>O</u>'', ϵ'')''</span>,
is uniquely determined by the primary structure,
<span style="white-space:nowrap">''(<u>O</u>.c'', ϵ, ≤'')''</span>,
up to isomorphism.
(Therefore,
<span style="white-space:nowrap">''(<u>O</u>'', ϵ'')''</span> is also determined by
<span style="white-space:nowrap">''(<u>O</u>.c'', ''.class'', ≤'')''</span>.)
Given a structure
<span style="white-space:nowrap">''(<u>O</u>.c'', ϵ, ≤'')''</span> between primary objects,
the ''eigenclass completion''
<span style="white-space:nowrap">''(<u>O</u>'', ϵ'')''</span> can be constructed in the following steps:
<ol>
<li>
Equip each primary object with an eigenclass chain
such that distinct primary objects have disjoint eigenclass chains.
Let the ''.ec'' map be coincident with the successor operator.
<li>
Extend ≤ to all objects as follows.
Let ''a'', ''b'' be primary objects, and ''i'', ''j'' > 0. Then
<ol style="list-style-type: upper-alpha">
<li>
''a.ec(i) ≤ b'' iff
''a'' ϵ<sup>''i''</sup> ''b''
where ϵ<sup>''i''</sup> is the
''i''-th composition of ϵ (not yet extended) with itself.
<li>
''a'' ≤ ''b.ec(j)'' iff
''a'' is a non-helix metaclass,
''b'' is the inheritance root, and ''j'' = 1.
<li>
''a.ec(i) ≤ b.ec(j)'' iff
''a.ec(i-1) ≤ b.ec(j-1)''.
</ol>
<li>
Extend ϵ to all objects by:
''(<u>O</u>'', ϵ'')'' = ''(<u>O</u>'', ''.ec)'' ○ ''(<u>O</u>'', ''≤)''.
</ol>
== Representation by sets ==
The eigenclass model can be interpreted by means of set theory.<ref name="ome-set-rep">
{{cite web | url=http://www.atalon.cz/om/object-membership/set-rep/ | title=Object Membership: Set-theoretic representation}}</ref>
<!-- -->
Objects are represented by sets so that object membership structure is induced by set structure.
The correspondence is best described via a generalization of the [[#canonical_structure|canonical structure]] such that only those features are axiomatized that are essential w.r.t. set representation.
=== {{anchor|essential_structure}} Essential structure of ϵ ===
An ''essential structure'' of ϵ is a structure
<span style="white-space:nowrap">''(<u>O</u>, .ec, ≤, <u>r</u>)''</span>
where
''<u>O</u>'' is the set of objects,
''.ec'' is the ''eigenclass map'' between objects,
''≤'' is the ''inheritance'' relation, and
''<u>r</u>'' is the ''inheritance root'', a distinguished object.
Objects that are not inheritance descendants of ''<u>r</u>'' are ''terminal(s)''.
The structure is subject to the following axioms:
<ol style="list-style-type:none; margin-left: 2ex;">
<li style="text-indent:-3ex; margin-left:3ex;">(e~1)
Inheritance, ≤, is a partial order.
<li>(e~2)
The eigenclass map, ''.ec'', is an order embedding w.r.t. ≤.
<li>(e~3)
Objects from eigenclass chains of terminals are minimal in ≤.
<li>(e~4)
Every eigenclass is a descendant of ''<u>r</u>''.
<li>(e~5)
The eigenclass chain of ''<u>r</u>''
(i.e. the [[#Reduced_helix|reduced helix]] ''<u>R</u>'') has no lower bound in ≤.
</ol>
Like with canonical structures, an essential structure is given by
<span style="white-space:nowrap">''(<u>O</u>,'' ϵ'')''</span>
where
<span style="white-space:nowrap">(ϵ) = (''.ec'') ○ (≤)</span>.
=== The embedding ===
Any essential structure of ϵ can be embedded into a set ''<u>V</u>'' that is formed as a cumulative hierarchy over a set of [[urelement]]s, ''<u>U</u>''.
Elements of ''<u>U</u>'' can be [[pure set]]s
that are minimal both in
<span style="white-space:nowrap">''(<u>V</u>,'' ∈'')''</span> and
<span style="white-space:nowrap">''(<u>V</u>,'' ⊆'')''</span>
so that
they just behave ''like'' urelements with respect to ''<u>V</u>''.
<!-- -->
The set ''<u>V</u>'' is built in ''ω''+1 stages.
The 0-th stage is the set ''<u>U</u>'' of urelements.
For each natural number ''i'', the ''i''-th stage equals the ''i''-th application of ''P<sub style="margin-left:-.8ex">⋆</sub>'',
the ''powerset cumulation'' operator, defined by
:''P<sub style="margin-left:-.8ex">⋆</sub>(X)'' = (''P(X)'' ∖ {∅}) ∪ ''X''
where ''P(X)'' denotes the powerset of ''X''.
The ''ω''-th stage, called ''[[Universe (mathematics)#In ordinary mathematics|superstructure]]'' in the field of [[non-standard analysis]],{{efn|
However, we provide a slightly different construction by removing the empty set.
}}
is the union of all previous stages.
This set stands for the inheritance root – it is therefore denoted ''<u>r</u>''.
The set ''<u>V</u>'' then equals the powerset cumulation of ''<u>r</u>'',
i.e. ''<u>V</u> = P<sub style="margin-left:-.8ex">⋆</sub><sup>ω+1</sup>(<u>U</u>) = P<sub style="margin-left:-.8ex">⋆</sub>(<u>r</u>)''.
The eigenclass map, ''.ec'', is defined on ''<u>V</u>'' by
:''x.ec = P(x)'' ∩ ''<u>r</u>'',
i.e. the eigenclass of ''x'' is the set of all those subsets of ''x'' which belong to some finite stage.
<!-- -->
Then
<span style="white-space:nowrap">''(<u>V</u>, .ec,'' ⊆'', <u>r</u>)''</span> is an essential structure of ϵ.
The inheritance relation, ≤, coincides with set inclusion, ⊆, on ''<u>V</u>''.
Object membership on ''<u>V</u>'' is given by:
''x'' ϵ ''y'' iff ''P(x)'' ∩ ''<u>r</u>'' is a subset of ''y''.
Terminal objects are the urelements.
The following are satisfied:
<!-- -->
{| cellpadding=2 style="margin:1ex 3ex;"
|- valign=top
| ''x.ec'' = {''x''}
| if ''x'' is terminal
(or ''x'' is from the eigenclass chain of a terminal),
|- valign=top
| style="padding-right:2ex;white-space:nowrap;" | ''x.ec = P(x)'' ∖ {∅}
| if (and only if) ''x'' ∈ ''<u>r</u>'',
|- valign=top
| ''x.ec'' ⊂ ''x''
| if (and only if) ''x'' ϵ ''x''.
|}
Any subset ''<u>O</u>'' of ''<u>V</u>'' such that ''<u>r</u>'' ∈ ''<u>O</u>'' and ''<u>O</u>.ec'' = ''<u>V</u>.ec'' ∩ ''<u>O</u>'' forms an "object system": the substructure
<span style="white-space:nowrap">''(<u>O</u>, .ec,'' ⊆'', <u>r</u>)''</span> is an essential structure of object membership.
<!-- -->
Conversely, any essential structure of ϵ can be represented by such set ''<u>O</u>''.
Moreover, such a representation exists that
for every ''x'', ''y'' from ''<u>O</u>'',
:''x'' ∈ ''y'' iff ''x'' ϵ ''y'' and ''x'' ∈ ''<u>r</u>''.
== Specializations ==
In a particular programming language, the eigenclass model appears in a specialized form.
A specialization of the model can be derived from the canonical structure in two steps:
<ol>
<li>
Generalize the canonical structure ''(<u>O</u>,'' ϵ'')'' by appropriately relaxing some of the axioms, possibly also
[[Expansion (model theory)|expanding]] the structure.
<li>
Specify additional constraints.
</ol>
The first step is necessary in most cases – of the above mentioned programming languages only Ruby and Python conform to the canonical structure.
=== In Ruby ===
The structure of object membership in Ruby is best explained in two steps by first describing the canonical structure and then the extension via module inclusion.
==== Canonical reduct ====
The canonical reduct ''(<u>O</u>,'' ϵ'')'' is given by the superclass and eigenclass links between objects.<ref name="ruby-s1">
{{cite web | url=http://www.atalon.cz/rb-om/ruby-object-model/rb-om-s1.pdf | title=Ruby Object Model – The S1 structure }}</ref>
In particular, the structure only allows single inheritance so that
except for ''<u>r</u>'', every non-terminal object has exactly one parent, detectable by the <code>superclass</code> method.
The order-embedding property of ''.ec'' translates to the statement that for every object ''x'', the superclass of the eigenclass of ''x'' equals the eigenclass of the superclass of ''x'', whenever the superclass of ''x'' is defined.
In addition, Ruby disallows explicit metaclasses other than ''<u>c</u>''.
As of Ruby 1.9, there are exactly 4 helix classes:
:''<u>c</u>'' = <code>Class</code> < <code>Module</code> < <code>Object</code> < <code>BasicObject</code> = ''<u>r</u>''.
==== Module inclusion ====
The "full" membership, ϵ', takes module inclusion into account.
''Modules'' are terminal instances of the
<code style="color:#700000">Module</code> class,
i.e. modules are <code style="color:#700000">Module</code>s
that are not <code style="color:#700000">Class</code>es.
The additional structure is given by the ''own-includer-of'' relation between <code style="color:#700000">Module</code>s (classes, eigenclasses, modules) and modules.
If <u>Μ</u> denotes the reflexive closure (i.e. <u>Μ</u> is ''self-or-own-includer-of'') then
the ϵ' relation is given by
: (ϵ') = (ϵ) ○ <u>Μ</u>.
This extended membership corresponds to the <code>is_a?</code> introspection method which is aliased by <code>kind_of?</code>.
Similarly, the "superclass" inheritance, ≤, is extended to ≤' by
: (≤') = (≤) ○ <u>Μ</u>,
which, in the restriction to <code style="color:#700000">Module</code>s, corresponds to the <code><=</code> 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''.<ref>
{{cite web | url=http://web.archive.org/web/20101113235808/http://eigenclass.org/hiki/The+double+inclusion+problem | title=The double inclusion problem }}</ref>
=== In Python ===
Assuming consistent setting of the <code>__mro__</code> attribute of classes, the Python eigenclass model conforms to the canonical structure.
There are exactly 2 helix classes:
:''<u>c</u>'' = <code>type</code> < <code>object</code> = ''<u>r</u>''.
No additional constraints are imposed.
<ref>{{cite web | url=http://www.python.org/download/releases/2.3/mro/ | title=The Python 2.3 Method Resolution Order }}</ref>
<ref>{{cite web | url=http://python-history.blogspot.com/2010/06/method-resolution-order.html | title=The History of Python: Method Resolution Order }}</ref>
<ref>[[C3 linearization]]</ref>
=== In Scala and Java ===
In Scala and Java, classes form actually a ''subset'' of ''<u>C</u>''.
This subset can be expressed as ''<u>C</u>.c''
where ''.c'' is an explicit closure operator added to the canonical structure, so that the generalized structure is of the form <span style="white-space:nowrap">''(<u>O</u>'', ϵ, ''.c)''</span>.
This way the set ''<u>C</u>'' 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 ''<u>c</u>'',
and, more importantly, a single inheritance between classes applies
(but not between traits / interfaces).
The helix contains 3 classes:
:''<u>c</u>'' = <code>Class</code> < <code>Object</code> < <code>Any</code> = ''<u>r</u>''.
For Java, the <code>Any</code> class can be thought of as a fictitious root allowing primitive values to be objects
– they become objects that are not <code style="color:#700000">Object</code>s.
Mixins (traits / interfaces) are among descendants of the <code>Object</code> class.
Java in addition disallows interleaving interfaces with classes, so that ''x.c'' = <code>Object</code> for every interface ''x''.
=== In Smalltalk-80 ===
To describe the eigenclass model as it applies to Smalltalk, one has to make several assumptions about possible program states.<ref>{{ cite web | url=http://www.atalon.cz/rb-om/ruby-object-model/co-smalltalk/ | title=The Ruby Object Model: Comparison with Smalltalk-80 }}</ref>
<!-- -->
As a consequence, the model does not capture all the anomalies allowed by [[Pharo]] or [[Squeak]], the major Smalltalk-80 implementations.
These ruled-out anomalies include in particular cycles in the inheritance relation (established via the <code>superclass:</code> method), "dangling metaclasses" (created by <code style="white-space:nowrap">Metaclass new</code>), and subclasses of the <code>Class</code> class.
There are two features of the Smalltalk object model that do not conform to the canonical structure ''(<u>O</u>'', ϵ'')'' but can be captured by an appropriate generalization:
''metaclass redirection'' and ''additional twist links''.
Metaclass redirection is expressed via an imposed metaclass subroot,
named <code>Metaclass</code>, which induces the corresponding ''imposed class map''.
This map coincides with the standard ''.class''
map except for implicit metaclasses, where it "redirects" the value from the <code>Class</code> class to the <code>Metaclass</code> class, introducing monotonicity breaks with respect to inheritance.
Additional twist links are child-parent pairs ''(x.ec, <u>c</u>)'' where ''x'' is a "subsidiary" inheritance root – a built-in parentless class other than ''<u>r</u>''.
Each of Pharo and Squeak contain one such class, named <code>PseudoContext</code> and <code>ObjectTracer</code>, respectively.
The helix chain contains 5 classes:
:''<u>c</u>'' = <code>Class</code> < <code>ClassDescription</code> < <code>Behavior</code> < <code>Object</code> < <code>ProtoObject</code> = ''<u>r</u>''.
The <code>Metaclass</code> class is a sibling of the <code>Class</code> class.
Finally, the Ruby-like conditions apply: There are no explicit metaclasses other than ''<u>c</u>'', and the inheritance relation is a forest.
==== {{anchor|smalltalk-traits}} Traits ====
Similarly to Ruby module inclusion, Smalltalk-80 supports extension of inheritance via inclusion of terminal objects, called ''traits''.<ref name="traits">{{cite web | author=Nathanael Schärli | url=http://scg.unibe.ch/archive/phd/schaerli-phd.pdf | title=Traits: Composing Classes from Behavioral Building Blocks}}</ref>
Traits are <code style="color:#700000">Trait</code>s – instances of the built-in <code style="color:#700000">Trait</code> class.
Unlike in Ruby, the semantics of extended object membership, ϵ', is not reflected by the <code>isKindOf:</code> introspection method (as of Pharo 1.3).
=== In Objective-C ===
In Objective-C, the eigenclass model has to be generalized to allow multiplicity and degeneracy of inheritance roots.
There are several components of object membership, each with its own inheritance root.
In each component, the inheritance root ''r'' equals the instance root, so that ''r.class = r''. Equivalently, <span style="white-space:nowrap">''(r.ec, r)''</span> is the twist link.
As a consequence, metaclasses have to be defined as objects that are either equal to an inheritance root or are descendants of the eigenclass of an inheritance root (this definition also applies to the canonical structure).
As of [[GNUstep]], there are (at least) 3 built-in inheritance roots, named <code>Object</code>, <code>NSObject</code> and <code>NSProxy</code>.
Finally, the Ruby/Smalltalk-like conditions apply: There are no explicit metaclasses other than metaclass roots, and the inheritance relation is a forest.
=== In CLOS ===
The Common Lisp Object System deviates from the canonical structure in two features.
It introduces non-linear inheritance between helix classes as well as an ''imposed class map'' with monotonicity breaks w.r.t. inheritance.
Unlike in Smalltalk, this imposed class map cannot be expressed via a constant "redirection" target.
As of [[CLISP]] 2.49, there are 8 helix classes:
:''<u>c</u>'' = <code>class</code> < <code>clos::potential-class</code> < … < <code>standard-object</code> < <code>T</code> = ''<u>r</u>''.
The missing 4 classes do not form a chain in inheritance.
Like in Python, there are no additional constraints: multiple inheritance is supported as well as creation of explicit metaclasses.
=== In Perl 5 ===
The Perl object model is distinguished by total circularity of classes: Every class is the class of itself. As a consequence, the instance-of relation, in its restriction to classes, coincides with the inheritance relation (so that there is no disambiguity in the interpretation of [[#is-a|is-a]]).
Every class is an instance root – so that there is an ''instance forest'' rather than ''instance tree''. Every class is also an explicit metaclass (metaclasses have to be defined via eigenclasses of instance roots similarly to Objective-C).
There is a single built-in inheritance-root, named <code>UNIVERSAL</code> (however, this statement requires the assumption that the <code>@ISA</code> variable of this class is not changed).
Multiple inheritance is allowed.
== Object actuality ==
Since eigenclass chains are infinite, any in-memory representation of object membership must involve the notion of "actual" objects – the finitely many objects that are actually represented (allocated).
It turns out that for all the above mentioned programming languages, the set of actual objects forms a closure system in inheritance, so that it can be expressed via the corresponding closure operator.
Actual objects comprise all primary objects (terminals and classes) plus some eigenclasses.
Except for Ruby, eigenclasses of eigenclasses (elements of ''<u>O</u>.ec(2)'') are never actual.
Even in Ruby, manipulating these higher-order eigenclasses did not find any practical use.<ref>
{{cite book | publisher=Pragmatic Bookshelf | author=Paolo Perrotta | url=http://pragprog.com/book/ppmetr/metaprogramming-ruby | title=Metaprogramming Ruby | isbn=978-1-934356-47-0}}</ref>
=== {{anchor|actuality-axioms}} Axioms ===
A canonical structure of object membership with ''actuality'' is a structure ''(<u>O</u>'', ϵ, ''.a)'' where
''(<u>O</u>'', ϵ'')'' is a canonical structure of object membership and ''.a'' is a (total) map between objects.
<!-- -->
Objects from ''<u>O</u>.a'' are ''actual(s)''.
The structure is subject to the following conditions:
<ol style="list-style-type:none; margin-left: 2ex;">
<li>(a~1)
There are only finitely many actual objects.
<li>(a~2)
Every primary object is actual.
<li>(a~3)
For every object ''x'', if ''x.ec'' is actual then so is ''x''.
<li style="text-indent:-5ex; margin-left:5ex;">(a~4)
The ''.a'' map is a closure operator w.r.t. inheritance.
<li style="text-indent:-5ex; margin-left:5ex;">(a~5)
For some (necessarily unique) ''i'' ≥ 0, ''<u>c</u>.ec(i)'' is actual but has no actual strict descendants.
</ol>
These axioms apply to all mentioned specializations of the model, provided that (a~5) is appropriately altered in case of multiple instance roots.
=== Actualclass map ===
The ''actualclass map'', ''.aclass'', is defined as the composition ''.ec.a''.
Equivalently, for an object ''x'', the ''actualclass of'' ''x'', ''x.aclass'',
is the least container of ''x'' that is actual.
The actualclass map goes between the eigenclass map and the class map, i.e. for every object ''x'',
:''x.ec ≤ x.aclass ≤ x.class''.
The ''.aclass'' map is identical to the ''.class'' map iff no eigenclass is actual.
Similarly to the ''.class'' map, the actualclass map forms a tree.
The root equals ''<u>c</u>.ec(i)'' from (a~5).
=== Specializations ===
In Python, Java, CLOS, and Perl, eigenclasses are purely fictitious – they are never actual, so that the actualclass map coincides with the class map.
Scala allows eigenclasses of terminal objects, e.g. via the <code>object</code> definition.<ref>
{{cite book | publisher=Artima Press | author=Martin Odersky, Lex Spoon, Bill Venners | url=http://www.artima.com/shop/programming_in_scala_2ed | title=Programming in Scala | isbn=978-0-9815316-4-9}}</ref>
In Smalltalk-80 and Objective-C, the set of actual eigenclasses equals ''<u>C</u>.ec'', i.e. all implicit metaclasses (without higher-order eigenclasses) are actual.
==== In Ruby ====
In Ruby, all objects that are not ''immediate values''
can have actual eigenclasses.<ref name="rb-om">
{{cite web | url=http://www.atalon.cz/rb-om/ruby-object-model/ | title=The Ruby Object Model: Data structure in detail}}</ref>
As of [[Ruby MRI|MRI]] 1.9, ancestors of actual objects are actual.
Ruby is the only language (at least of the above mentioned ones) that supports dynamic eigenclass allocation. Typically, for an object ''x'' (whether a class or a terminal), the eigenclass ''x.ec'' becomes actual by defining "singleton" methods for ''x''.
<!-- -->
Moreover, Ruby in fact maintains 2 actuality extents, i.e. two different sets of actual objects.
The first set is the set of actually ''referenced'' objects. The second, larger set is the set of ''allocated'' objects.
The actualclass map for the larger set corresponds to the <code>klass</code> field in the [[C (programming language)|C]] source code of MRI.
==== {{anchor|actualclass_in_Smalltalk-80}} In Smalltalk-80 ====
In Smalltalk, the imposed class map has the corresponding ''imposed actualclass map'' which corresponds to the introspection method named <code>class</code>.
Due to the metaclass redirection, the imposed actualclass map does not form a tree but just a (directed) [[pseudotree]] with a 2-element cycle containing the <code>Metaclass</code> class and its eigenclass.<ref>
{{cite book | publisher=Springer Verlag | author=John Hunt | url=http://stephane.ducasse.free.fr/FreeBooks/STandOO/Smalltalk-and-OO.pdf | title=Smalltalk and Object Orientation: An Introduction | isbn=978-3540761150}}</ref>
== Name resolution ==
Object membership, ϵ, provides fundamental semantics for sharing properties between objects.
Similarly to [[Resource Description Framework|RDF]] triples, an object property can be considered as a named source-target arrow.
There are two basic interpretations of the source: as ''owner'' and as ''receiver''.
Owner-arrows are explicit data bindings: a target value is bound to an owner object under a name.
Receiver-arrows are implicit: an object receives (inherits) a named property from an appropriate owner via ϵ.
The process of finding an owner-arrow for a given receiver and name is an essential part of ''[[Name resolution|(property) name resolution]]''.
There are two main ways how to interpret ϵ in name resolution of shared properties.
In the ''prototypal'' way, the owner-arrow is looked up in ''ancestors'' of the receiver.
For class-based programming languages, this mode is of minor importance and is usually unsupported. In Ruby, it occurs in ''constant resolution'', e.g. resolving expressions like <code>A::B</code>.
In the ''class-based'' way, the owner-arrow is looked up in ''containers'' of the receiver.
This is the primary mode, used in particular for finding arrows that point to methods, (a part of) the process known as ''method resolution'' or ''method lookup''.
Since containers of an object are just ancestors of the object's eigenclass, method lookup can be thought of as a two-stage process: first step to the eigenclass, then look up in ancestors.
In Ruby, this is expressed as a "method call mantra":<ref>
{{cite web | url=http://pragprog.com/screencasts/v-dtrubyom/the-ruby-object-model-and-metaprogramming | title=The Ruby Object Model and Metaprogramming }}</ref>
:<cite style="font-style:italic;">one to the right, then up</cite>.
Considering object actuality,
the actual start-point of the lookup is the actualclass of the receiver.
In most cases (and in all cases for languages without actual eigenclasses) it means that the lookup starts in the receiver's class.
=== Conflict resolution ===
In the ideal case, objects that are owners of an ''s''-named binding for a given name ''s'' form a partial closure system: for every object ''x'', either no ancestor of ''x'' owns an ''s''-named binding or there is a (necessarily unique) ''least'' such ancestor, ''y'', w.r.t. inheritance.
If ''y'' exists, then the ''s''-named arrow emanating from ''y'' is basically the result of the resolution process.
In the general case, an object can have ''multiple minimal'' ancestors that are owners of an ''s''-named binding.
There are 3 main ways how to either avoid or resolve such conflicts:
<ol>
<li>
Only allow single inheritance between potential owners. This condition guarantees that every set of owner objects is a partial closure system.
This solution is applied in Java and Objective-C.
<li>
Disallow conflicts by enforcing additional arrows.
Upon object creation (in particular, class creation),
if a conflict is detected for a name ''s'',
make sure that the new object itself becomes an owner of an ''s''-named binding.
This solution is used in Smalltalk-80 by the [[#smalltalk-traits|traits]] mechanism.
<li>
Maintain additional ordering so that a ''linearization'' of ancestors can be established.
This applies to Ruby, Scala, Python, CLOS and Perl.
</ol>
=== Linearization ===
The ''linearization'' of an object ''x'',
denoted ''x.ancs'', is a list of ancestors of ''x''
that determines the order in which ancestors are looked up for
ownership of a property (binding) with a given name.
For every ''x'', ''x.ancs'' starts with ''x'' itself.
The ''.ancs'' map can be equivalently expressed as a "quadratic" inheritance – a partial order between pairs ''(x,y)'' where ''x'' is a descendant of ''y''.
This structure can be conveniently termed ''method resolution order'', abbreviated as ''MRO'' (using "method" instead of some more general term like "property" can be attributed to the prominent position of methods in object-oriented programming).
As a result of linearization, MRO is a forest: every element ''(x,y)'' has at most one parent.
Starting at ''(x,x)'', the traversal of ancestors in MRO yields ''x.ancs'', the linearization of ''x''.
The [[Domain (mathematics)|___domain]] of MRO is the part of the inheritance relation where multiple parents are allowed.
In Ruby, this is exactly the self-or-own-includer-of relation, <u>Μ</u> (as a subset of the extended inheritance, ≤').
In Scala, the MRO ___domain is a similar relation between
<code style="color:#700000">Class</code>es (classes, eigenclasses, traits) and traits.
In Python, Perl and CLOS, there is no distinction of mixins like in Ruby or Scala, so that the MRO ___domain equals the inheritance – it contains all pairs ''(x,y)'' of objects such that ''x ≤ y''.
== Transitions ==
Standard [[State transition system|transitions]] are those of new "user" object creation. The structure is modified by adding a primary object ''x'', together with its (fictitious) eigenclass chain, such that ''x'' is minimal in inheritance.
Except for languages with degenerated metaclass roots, new object ''x'' creation (whether a terminal ''x'' or a class ''x'') can be uniformly expressed as class instantiation:
: <code>''x'' := ''q''.new(''p<sub>1</sub>, …, p<sub>n</sub>'')</code>
where ''q'' is the requested class of ''x'' and
''p<sub>1</sub>, …, p<sub>n</sub>'' are the requested parents of ''x''.
In practice, creation of terminal objects ''x''
(where ''q'' is not a metaclass and necessarily ''n'' = 0)
is syntactically differentiated from creation of classes ''x''
(where ''q'' is a metaclass).{{efn|
However, Ruby also supports the uniform expression:
<code>Class.new(A)</code> creates a new subclass of <code>A</code>.
}}
In Perl, the pattern is not applicable to class creation due to the [[Chicken or the egg|chicken-egg problem]] caused by the circularity of classes.
In Objective-C, if ''q'' is an inheritance root, then one cannot recognize, if ''x'' should be terminal or a class.
Similarly, the pattern is not applicable to the helix structure, which is built-in and cannot be changed by transitions.
In less dynamic languages like Scala, Java or Objective-C, most or all classes are usually created in an initial loading phase, before terminal objects.
Dynamic class creation is provided as a secondary option.
In Ruby, transitions of the extended structure ''(<u>O</u>'', ϵ''')'' are made separately by transitions of the canonical reduct, ''(<u>O</u>'', ϵ'')'', and of the
<u>Μ</u> relation, the latter performed via the <code>include</code> method.
Some languages support transitions such that the old structure is not a [[substructure]] of the new one.
In particular, Python, CLOS and Perl allow to change the class of a terminal object.
== {{anchor|ontological structure}} Ontological structure of ϵ ==
A generalization of the canonical structure of ϵ
allows
for a description of the core structure of [[Ontology (information science)|ontologies]] in which
classes are (among) individuals.<ref name="ome-ontology">
{{cite web | url=http://www.atalon.cz/om/object-membership/ontology/ | title=Object Membership: The ontological structure}}</ref>
<!-- -->
Motivated by the [[RDF Schema]],
the generalization can be characterized by the following features:
<ul>
<li>
Distinction of ''properties''
as instances of a special class, ''<u>p</u>''.
Properties, like terminal objects, are not descendants of the inheritance root. In contrast to terminals, properties can have (other properties as) ancestors / descendants.
<li>
Inheritance does not have to be antisymmetric
–
distinct classes or properties can be descendants of each other and thus become equivalent.
<li>
''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.
<li>
Finiteness conditions are less strict in order to
allow infinitely many terminals or properties.
</ul>
In eigenclass completion,
the structure can be expressed with the signature
<span style="white-space:nowrap">''(<u>O</u>'', ϵ, ''<u>p</u>)''</span>.
Additional symbols ''<u>r</u>'' and ''<u>c</u>'' can be used for distinction between the possibly many equivalent inheritance and metaclass roots.
The primary ontological structure is then expressed as
<span style="white-space:nowrap">
''(<u>Ō</u>'', ϵ, ≤, ''<u>r</u>, <u>c</u>, <u>p</u>)''</span>.
=== {{anchor|rdfs|RDFS}} In RDF Schema ===
In [[RDF Schema]] (RDFS),<ref>
{{cite web | url=http://www.w3.org/TR/rdf-mt/ | title=RDF Semantics }}</ref>
the (primary) ontological structure of ϵ is the core structure of the RDF graph formed by triples ''(s,p,o)'' whose predicate ''p'' equals
<code>rdf:type</code>,
<code>rdfs:subClassOf</code> or <code>rdfs:subPropertyOf</code>.
The <code>rdf:type</code> property stands for the instance-of relation,
ϵ.
Uniformity of inheritance, ≤, is achieved by the assumption
of disjointness of classes and properties,
which is not guaranteed by RDFS but usually satisfied.
The
<code>rdfs:subClassOf</code> and <code>rdfs:subPropertyOf</code> properties then
correspond to the restriction of inheritance to classes and properties,
respectively.
Objects are called ''resources''
– every object is an instance of the <code>rdfs:Resource</code> class (''<u>r</u>'').
Classes are instances of <code>rdfs:Class</code> (''<u>c</u>''),
properties are instances of <code>rdf:Property</code> (''<u>p</u>'').
Unlike classes, properties do not have a common built-in ancestor.
Structure constraints are expressed via [[entailment]] rules
– the presence of some triples entails the presence of other triples.
For example,
the <span style="white-space: nowrap">(ϵ) ○ (≤) = (ϵ)</span> equality is asserted by the rdfs9 entailment rule,{{efn|
More precisely,
rdfs9 only asserts the inclusion (ϵ) ○ (≤) ⊆ (ϵ). Equality is asserted by other rules.
}}
which says that triples ''(x'',ϵ,''y)'' and ''(y'',≤,''z)'' entail the triple ''(x'',ϵ,''z)'', i.e.
whenever ''x'' is an instance of ''y'' and ''y'' a subclass of ''z'' then ''x'' is an instance of ''z''
(this is also known as the ''subsumption rule''<ref>
{{cite web | author= Seiji Koide, Hideaki Takeda | url=http://www-kasm.nii.ac.jp/papers/takeda/06/koide06aswc.pdf | title=OWL-Full Reasoning from an Object Oriented Perspective}}</ref>).
There are conditions that can be considered as natural constraints but are not asserted by RDFS entailment.
In particular, there is no "type monotonicity" rule which would assert that
<span style="white-space: nowrap">(≤) ○ (ϵ) = (ϵ)</span>.
Another example of a possible anomaly is a class that is not a metaclass (a descendant of <code>rdfs:Class</code>) but has classes as instances.<ref>
{{cite web | author=Aimilia Magkanaraki et al. | url=http://www.ics.forth.gr/isl/publications/paperlink/iswc02.pdf | title=Benchmarking RDF Schemas for the Semantic Web}}</ref>
[[File:Rdfs-builtin-isa.svg|
The built-in core structure of RDF Schema|
right|
350px
]]
The built-in structure, entailed by the empty set, is shown by the diagram on the right.
The structure is fairly regular.
Except for inheritance between properties and the infinity of the set {<code>rdf:_1</code>, <code>rdf:_2</code>, …},
even the axioms for the (primary) [[#Primary_structure|canonical structure]] are satisfied.
There is single classification (yielding the ''.class'' map) and single inheritance.
Since the ''.class'' map is inherited via type monotonicity, the diagram shows only the reduction (dashed arrows).
Similarly to the Python programming language,
there is a minimal chain of 2 helix classes:
:''<u>c</u>'' = <code>rdfs:Class</code> < <code>rdfs:Resource</code> = ''<u>r</u>''.
The <code>rdfs:Datatype</code> class is the second built-in metaclass.
=== In OWL 2 ===
In [[Web_Ontology_Language#OWL_Full|OWL 2 Full]],<ref>
{{cite web | url=http://www.w3.org/TR/owl2-rdf-based-semantics/ | title=OWL 2 RDF-Based Semantics }}</ref>
the structure of RDF Schema is extended by additional axiomatic triples.
The extension is then subject to the (additional) OWL 2 RL/RDF rules.<ref>
{{cite web | url=http://www.w3.org/TR/owl2-profiles/ | title=OWL 2 Profiles }}</ref>
The built-in structure contains four helix classes, preordered by
:{<code>owl:Class</code>, <code>rdfs:Class</code>} < {<code>owl:Thing</code>, <code>rdfs:Resource</code>},
which indicates that RDFS helix classes have their OWL equivalents.
Similarly,
<code>rdf:Property</code> is equivalent to
<code>owl:ObjectProperty</code> and
the metaclass <code>rdfs:Datatype</code> is equivalent to
(the metaclass) <code>owl:DataRange</code>.
<!-- -->
In total, there are 7 built-in metaclasses, including
the bottom class, <code>owl:Nothing</code>, a descendant of all classes which is disallowed to have instances.
==See also==
<div style="column-count:2;-moz-column-count:2;-webkit-column-count:2">
*[[Object (computer science)]]
*[[Class (computer programming)]]
*[[Metaclass]]
*[[Class-based programming]]
*[[Top type]]
*[[Order theory]]
</div>
== Notes ==
{{notelist|1}}
== References ==
{{reflist|2}}
[[Category:Object-oriented programming]]
[[Category:Object models]]
[[Category:Class (computer programming)]]
[[Category:Mathematical structures]]
| 