|
#REDIRECT [[Ruby (programming language)#Semantics and philosophy]]
{{technical|date=October 2012}}
{{RCS|
{{TOC right|limit=3|width=30ex}}
{{R with history}}
__TOC__
{{R without mention}}
In [[object-oriented programming|object-oriented]] [[Computer programming|programming]], the '''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 <em>eigenclasses</em>.
Eigenclasses are auxiliary (mostly just fictitious) class-like objects that establish [[infinite regress]] via the eigenclass
[[Function_(mathematics)|map]]:
for every object <i>x</i>, the eigenclass of <i>x</i> is
the unique own meta-object of <i>x</i> that is one meta-level higher than <i>x</i>.
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 <em>object membership</em>,
a relation between objects, denoted ϵ ([[lunate epsilon]]) in
<ref name="ome">{{cite web | url=http://www.atalon.cz/om/object-membership/ | title=Object Membership: The core structure of object-oriented programming }}</ref>.
This relation is a generalization of the <em>instance-of</em> 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 following languages:
[[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]],
[[Perl (programming language)|Perl]].
<!-- -->
The group can be further divided into two subgroups: languages allowing an actual reference to an eigenclass (Ruby, Smalltalk, Objective-C and, in a lesser sense, Scala) and languages in which eigenclasses are a purely fictitious concept.
== History ==
The inception of the eigenclass model with referenceable eigenclasses can be attributed to [[Smalltalk (programming language)|Smalltalk-80]] which introduced <em>implicit metaclasses</em>.
In Smalltalk, every class has its own metaclass, and metaclass inheritance parallels class inheritance.
However, a full and consistent application of the eigenclass model appeared first (and only) in the
[[Ruby (programming language)|Ruby programming language]].
The term <em>"eigenclass"</em> has been established in <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 <em>"singleton class"</em>
(although in Ruby 1.9, the corresponding introspection method is still named <code>singleton_class</code>).
== {{anchor|canonical structure}} The canonical structure of ϵ ==
In its rudimentary form, the eigenclass model can be described
as a canonical structure <i>(<u>O</u>,</i> ϵ<i>)</i>
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
<i>(<u>O</u></i>, ϵ<i>)</i>,
together with corresponding Python code.
<table border="0" style="margin:2ex auto;"><tr>
<td>
[[File:Eigenclass-model-sample-a.svg|
Eigenclass model - A sample canonical structure|
450px
]]
</td>
<td 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>
</td>
</tr></table>
The structure contains 6 [[#Primary_objects|primary objects]]:
2 [[#Helix|helix]] classes
(the [[#Inheritance_root|inheritance root]] <i><u>r</u></i> and the [[#Instance_root|instance root]] / metaclass root <i><u>c</u></i>),
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 <i style="color:green">∫</i>-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 <i><u>r</u></i>.
The structure contains 2 explicit [[#Metaclasses|metaclasses]]:
the metaclass root <i><u>c</u></i> and the user-created metaclass <code>M</code>.
The remaining inheritance descendants of <i><u>c</u></i>
(i.e. all eigenclasses except the eigenclass of <code>b</code>) are implicit metaclasses.
=== Objects ===
The universum of the model is the set <i><u>O</u></i> of abstract entities called <em>objects</em>.
By further axioms, this set is asserted to be [[countably infinite]].
=== Object membership ===
The <em>object membership</em> relation, ϵ, is a (binary) relation between objects.
For objects <i>x</i>, <i>y</i>, if <i>x</i> ϵ <i>y</i>,
then <i>x</i> is a <em>member-of</em> <i>y</i> and
<i>y</i> is a <em>container-of</em> <i>x</i>.
By axiom (1), object membership is uniquely decomposable into the eigenclass map and the inheritance relation, which can be written as
:(ϵ) = (<i>.ec</i>) ○ (≤)
where the composition symbol '○' is interpreted left-to-right,
i.e. <i>x</i> ϵ <i>y</i> iff <i>x.ec</i> ≤ <i>y</i>.
=== Inheritance ===
The <em>inheritance</em>, denoted ≤, is a relation between objects
defined by
:<i>x</i> ≤ <i>y</i> iff <i>y</i> ϵ <i>a</i> implies <i>x</i> ϵ <i>a</i> for every object <i>a</i> (i.e. every container of <i>y</i> is a container of <i>x</i>).
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.
:<i>x</i> ≤ <i>y</i> only-if <i>a</i> ϵ <i>x</i> implies <i>a</i> ϵ <i>y</i> for every object <i>a</i> (every member of <i>x</i> is a member of <i>y</i>),
which indicates that the inheritance relation, ≤, has the semantics of the [[subset]] relation, ⊆.
If <i>x</i> ≤ <i>y</i> then <i>x</i> is a <em>descendant</em> of <i>y</i> and
<i>y</i> is an <em>ancestor</em> of <i>x</i>.
For an object <i>x</i>, <i>x</i>.↥ (resp. <i>x</i>.↧) denotes the set of all (non-strict) ancestors (resp. descendants) of <i>x</i>.
Similarly, for a set <i>X</i> of objects,
<i>X</i>.↥ (resp. <i>X</i>.↧) is the [[Upper set|upset]] (resp. downset) of <i>X</i>.
Direct ancestors ([[Covering relation|covers]]) of <i>x</i> are called
<em>parents</em> of <i>x</i>.
<!-- and denoted <i>x.parents</i>. -->
=== Eigenclasses ===
The <em>eigenclass-of</em> an object <i>x</i>, denoted <i>x.ec</i>,
is the container of <i>x</i> that is least (lowest) in the inheritance ≤.
Axiom (1) asserts that every object has its eigenclass.
Furthermore, (1) and (2) imply that the <i>.ec</i> map is an [[order embedding]] with respect to ≤.
In particular, <i>.ec</i> is [[Injective function|injective]] – different objects have different eigenclasses.
Another consequence of (1) is that for every objects <i>x</i>, <i>y</i>,
:<i>x</i> ϵ <i>y.ec</i> iff <i>x ≤ y</i>,
showing that the eigenclass map
corresponds to the [[powerset]] operator.
The <i>i</i>-th application of <i>.ec</i> to <i>x</i> is denoted <i>x.ec(i)</i>.
By further axioms, each component of the eigenclass map is an infinite chain
<i>x = x.ec(0)</i>, <i>x.ec = x.ec(1)</i>, <i>x.ec.ec = x.ec(2)</i>, … starting in a primary object <i>x</i>.
An <em>eigenclass</em> is an object that belongs to <i><u>O</u>.ec</i>, the [[Image_(mathematics)|image]] of <i>.ec</i>.
=== Primary objects ===
Objects that are not eigenclasses are <em>primary</em>.
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 <i>.c</i>, in inheritance.
For each object <i>x</i>, the primary object <i>x.c</i> is the
least primary ancestor of <i>x</i>.
Primary objects are further divided into
<em>terminals</em> and <em>classes</em> which can be expressed as
:<i><u>O</u>.c = <u>T</u></i> ⊎ <i><u>C</u></i>.
=== Classes ===
An object is a <em>class</em> 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 <i><u>C</u></i>.
Classes together with eigenclasses form the set of all descendants
of the inheritance root <i><u>r</u></i>,
i.e. <i><u>r</u></i>.↧ = <i><u>C</u></i> ⊎ <i><u>O</u>.ec</i>.
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 <i><u>c</u></i>.
=== Terminal objects ===
An object is <em>(a) terminal</em> if it is neither a class nor an eigenclass.
The set of terminals is denoted <i><u>T</u></i>.
Therefore, the set of objects is a disjoint union of the sets of
terminals, classes and eigenclasses:
:<i><u>O</u> = <u>T</u></i> ⊎ <i><u>C</u></i> ⊎ <i><u>O</u>.ec</i>.
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 <em>class-of</em> an object <i>x</i>, denoted <i>x.class</i>, is the smallest container of <i>x</i> that is a class.
Axiom (6) asserts that <i>x.class</i> is defined for every <i>x</i>.
Equivalently, the <i>.class</i> map can be written as <i>.ec.c</i> where
<i>.c</i> is the closure operator in ≤ such that the image
<i><u>O</u>.c</i> is the set of [[#Primary_objects|primary objects]].
As a consequence, <i>.class</i> is a [[Monotone_map#Monotonicity_in_order_theory|monotone map]].
Axiom (8) asserts that the <i>.class</i> map forms a tree
– the <em>instance tree</em>.
The diagram on the right shows the class map for the [[#Example|example]] structure, in the restriction to primary objects.
To illustrate the <i>.ec.c</i> composition, the arrows are drawn along eigenclass paths.
=== Instance of ===
The <em>instance-of</em> relation is defined as the range-[[Restriction_(mathematics)|restriction]] of object membership to classes, i.e.
:<i>x</i> is an instance of <i>y</i> iff <i>x</i> ϵ <i>y</i> and <i>y</i> is a class.
The relation can be expressed as (ϵ) ○ (<i>.c</i>).
The <em>direct instance-of</em> relation is the <i>.class</i> map taken as a relation, i.e.
:<i>x</i> is a direct instance of <i>y</i> iff <i>x.class = y</i>.
The direct-instance-of, instance-of and member-of relations form an inclusion chain:
:(<i>.class</i>) ⊂ (ϵ) ○ (<i>.c</i>) ⊂ (ϵ).
=== {{anchor|is-a}} Membership as is-a ===
If <i>x</i> is a member of an object named <code style="color:#700000">B</code>
(in particular, if <i>x</i> is an instance of the <code style="color:#700000">B</code> class) then one can say that <span style="white-space:nowrap"><i>x</i> <em>is-a</em> <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 <i>x</i> is a <em>helix</em> object if it is its own member,
i.e. <i>x</i> ϵ <i>x</i>.
The set of all helix objects is denoted <i><u>H</u></i>.
Axiom (4)(c) asserts that <i>(<u>H</u></i>, ≤<i>)</i> is a [[linear order]] so that the object membership structure restricted to <i><u>H</u></i> can be visualised as a circular [[helix]].
The helix has the inheritance root, <i><u>r</u></i>, 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 <em>inheritance root</em>, <i><u>r</u></i>, is the highest helix class – a common ancestor of all non-terminal objects.
Its existence is asserted by axiom (4)(a).
==== Instance root ====
The <em>instance root</em>, <i><u>c</u></i>, is the lowest helix class, usually named <code>Class</code>.
It can also be specified as <i><u>r</u>.class</i> or, explaining the terminology, as the root of the instance tree – it is the only object <i>x</i> such that <i>x.class = x</i>.
Axiom (4)(b) asserts that <i><u>c</u></i> is different from <i><u>r</u></i>.
==== Twist links ====
The child-parent pair <i>(<u>r</u>.ec, <u>c</u>)</i> is the <em>(front) twist link</em>.
Axiom (4)(d) asserts that <i><u>r</u>.ec</i> is the only child of <i><u>c</u></i>.
In addition, it is asserted that <i><u>c</u></i> is the only parent of <i><u>r</u>.ec</i>.
The same conditions hold for all twist links
<i>(<u>r</u>.ec(i+1), <u>c</u>(i))</i>.
=== Metaclasses ===
An object is a <em>metaclass</em> if it is a descendant of <i><u>c</u></i>, so that
the set of all metaclasses is simply expressed as <i><u>c</u></i>.↧.
The instance root <i><u>c</u></i> is therefore also the <em>metaclass root</em>.
Metaclasses are either <em>explicit</em> or <em>implicit</em> 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. <i><u>O</u>.class = <u>C</u></i>, the following symmetric formula applies:
:<i><u>c</u></i>.↧ = <i><u>O</u>.ec.class</i> ⊎ <i><u>O</u>.class.ec</i> ⊎ <i><u>O</u>.ec.ec</i>,
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 <i><u>C</u></i> for <i><u>O</u>.class</i> we obtain
:<i><u>c</u></i>.↧ ∖ <i><u>O</u>.ec(2)</i> = <i><u>C</u>.class</i> ⊎ <i><u>C</u>.ec</i>,
i.e. aside from higher-order eigenclasses, explicit metaclasses are <em>classes-of</em> classes (<i><u>C</u>.class</i>) whereas implicit metaclasses are <em>eigenclasses-of</em> classes (<i><u>C</u>.ec</i>).
The classical definition of metaclasses as "<i>classes whose instances are classes</i>"
<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"><i><u>C</u></i> ∖ <i><u>c</u></i>.↧ ⊆ <i><u>T</u>.class</i>.↥</span>
(in particular, the parent of <i><u>c</u></i> = <code style="color:#700000">Class</code> must have a terminal instance so that helix classes other that <i><u>c</u></i> are ruled out by the "all" adverb).
=== Axioms ===
The canonical structure <i>(<u>O</u></i>, ϵ<i>)</i> 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 <i>x</i> are exactly the
ancestors the eigenclass of <i>x</i>,
i.e.
:(ϵ) = (<i>.ec</i>) ○ (≤) for a unique map <i>.ec</i>.
<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 <i><u>r</u></i>.
<li>(b)
The eigenclass of <i><u>r</u></i> has at least 2 strict ancestors.
<li>(c)
The set <i><u>H</u></i> of helix objects is linearly ordered by inheritance.
<li>(d)
For every <i>i > 0</i>, the eigenclass <i><u>r</u>.ec(i)</i> has no siblings.
<li>(e)
Every helix descendant of <i><u>r</u>.ec</i> is an eigenclass.
</ol>
<li>(5)
Descendants of non-helix eigenclasses are eigenclasses.
<li>(6)
Every object <i>x</i> has a least container that is a class, <i>x.class</i>.
<li>(7)
For every object <i>x</i>, <i>x.ec.class = x.class.class</i>.
<li style="text-indent:-3ex; margin-left:3ex;">(8)
There is a helix object <i>h</i> such that for every non-helix class <i>x</i>, the sets <i>h</i>.↧ and <i>x</i>.↧
are disjoint.
<!--
<li>(8)
There is a helix object <i>h</i> such that the set <i>h</i>.↧.↥ 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 (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-<i><u>r</u>.ec</i> are eigenclasses.
</ol>
Assuming (5'), the object membership structure,
<i>(<u>O</u></i>, ϵ<i>)</i>,
is uniquely determined by inheritance and class map between primary objects,
<i>(<u>O</u>.c, ≤, .class)</i>, up to isomorphism.
== 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 <i>(<u>O</u>,</i> ϵ<i>)</i> 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 <i>(<u>O</u>,</i> ϵ<i>)</i> 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 <i><u>r</u></i>, every non-terminal object has exactly one parent, detectable by the <code>superclass</code> method.
The order-embedding property of <i>.ec</i> translates to the statement that for every object <i>x</i>, the superclass of the eigenclass of <i>x</i> equals the eigenclass of the superclass of <i>x</i>, whenever the superclass of <i>x</i> is defined.
In addition, Ruby disallows explicit metaclasses other than <i><u>c</u></i>.
As of Ruby 1.9, there are exactly 4 helix classes:
:<i><u>c</u></i> = <code>Class</code> < <code>Module</code> < <code>Object</code> < <code>BasicObject</code> = <i><u>r</u></i>.
==== Module inclusion ====
The "full" membership, ϵ', takes module inclusion into account.
<em>Modules</em> 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 <em>own-includer-of</em> 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 <em>self-or-own-includer-of</em>) 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 <em>multiple</em> inheritance.
In addition, since Ruby supports dynamic module inclusion,
≤' can have anomalies (as to transitivity and/or antisymmetry), the problem known as the <em>double/dynamic inclusion problem</em>
<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:
:<i><u>c</u></i> = <code>type</code> < <code>object</code> = <i><u>r</u></i>.
No additional constraints are imposed.
=== In Scala and Java ===
In Scala and Java, classes form actually a <em>subset</em> of <i><u>C</u></i>.
This subset can be expressed as <i><u>C</u>.c</i>
where <i>.c</i> is an explicit closure operator added to the canonical structure, so that the generalized structure is of the form <span style="white-space:nowrap"><i>(<u>O</u></i>, ϵ, <i>.c)</i></span>.
This way the set <i><u>C</u></i> is split into <em>classes</em> and <em>non-terminal mixins</em>.
In Scala, mixins are called <em>traits</em>,
in Java they are <em>interfaces</em>.
Mixins are not allowed to be metaclasses.
The structure is then subject to additional constraints.
There are no explicit metaclasses other than <i><u>c</u></i>,
and, more importantly, a single inheritance between classes applies
(but not between traits / interfaces).
The helix contains 3 classes:
:<i><u>c</u></i> = <code>Class</code> < <code>Object</code> < <code>Any</code> = <i><u>r</u></i>.
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 <i>x.c</i> = <code>Object</code> for every interface <i>x</i>.
=== 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 <i>(<u>O</u></i>, ϵ<i>)</i> but can be captured by an appropriate generalization:
<em>metaclass redirection</em> and <em>additional twist links</em>.
Metaclass redirection is expressed via an imposed metaclass subroot,
named <code>Metaclass</code>, which induces the corresponding <em>imposed class map</em>.
This map coincides with the standard <i>.class</i>
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 <i>(x.ec, <u>c</u>)</i> where <i>x</i> is a "subsidiary" inheritance root – a built-in parentless class other than <i><u>r</u></i>.
Each of Pharo and Squeak contain one such class, named <code>PseudoContext</code> and <code>ObjectTracer</code>, respectively.
The helix chain contains 5 classes:
:<i><u>c</u></i> = <code>Class</code> < <code>ClassDescription</code> < <code>Behavior</code> < <code>Object</code> < <code>ProtoObject</code> = <i><u>r</u></i>.
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 <i><u>c</u></i>, 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 <em>traits</em>
<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 <i>r</i> equals the instance root, so that <i>r.class = r</i>. Equivalently, <span style="white-space:nowrap"><i>(r.ec, r)</i></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 <i><u>c</u></i>, 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 <em>imposed class map</em> 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:
:<i><u>c</u></i> = <code>class</code> < <code>clos::potential-class</code> < … < <code>standard-object</code> < <code>T</code> = <i><u>r</u></i>.
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 <em>instance forest</em> rather than <em>instance tree</em>. 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 <i><u>O</u>.ec(2)</i>) 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 <em>actuality</em> is a structure <i>(<u>O</u></i>, ϵ, <i>.a)</i> where
<i>(<u>O</u></i>, ϵ<i>)</i> is a canonical structure of object membership and <i>.a</i> is a (total) map between objects.
<!-- -->
Objects from <i><u>O</u>.a</i> are <em>actual(s)</em>.
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 <i>x</i>, if <i>x.ec</i> is actual then so is <i>x</i>.
<li style="text-indent:-5ex; margin-left:5ex;">(a~4)
The <i>.a</i> map is a closure operator w.r.t. inheritance.
<li style="text-indent:-5ex; margin-left:5ex;">(a~5)
For some (necessarily unique) <i>i</i> ≥ 0, <i><u>c</u>.ec(i)</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 <em>actualclass map</em>, <i>.aclass</i>, is defined as the composition <i>.ec.a</i>.
Equivalently, for an object <i>x</i>, the <em>actualclass of</em> <i>x</i>, <i>x.aclass</i>,
is the least container of <i>x</i> that is actual.
The actualclass map goes between the eigenclass map and the class map, i.e. for every object <i>x</i>,
:<i>x.ec ≤ x.aclass ≤ x.class</i>.
The <i>.aclass</i> map is identical to the <i>.class</i> map iff no eigenclass is actual.
Similarly to the <i>.class</i> map, the actualclass map forms a tree.
The root equals <i><u>c</u>.ec(i)</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 <i><u>C</u>.ec</i>, i.e. all implicit metaclasses (without higher-order eigenclasses) are actual.
==== In Ruby ====
In Ruby, all objects that are not <em>immediate values</em>
<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> can have actual eigenclasses.
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 <i>x</i> (whether a class or a terminal), the eigenclass <i>x.ec</i> becomes actual by defining "singleton" methods for <i>x</i>.
<!-- -->
Moreover, Ruby in fact maintains 2 actuality extents, i.e. two different sets of actual objects.
The first set is the set of actually <em>referenced</em> objects. The second, larger set is the set of <em>allocated</em> 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.
==== In Smalltalk-80 ====
In Smalltalk, the imposed class map has the corresponding <em>imposed actualclass map</em> 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 <em>owner</em> and as <em>receiver</em>.
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 <em>[[Name resolution|(property) name resolution]]</em>.
There are two main ways how to interpret ϵ in name resolution of shared properties.
In the <em>prototypal</em> way, the owner-arrow is looked up in <em>ancestors</em> of the receiver.
For class-based programming languages, this mode is of minor importance and is usually unsupported. In Ruby, it occurs in <em>constant resolution</em>, e.g. resolving expressions like <code>A::B</code>.
In the <em>class-based</em> way, the owner-arrow is looked up in <em>containers</em> 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 <em>method resolution</em> or <em>method lookup</em>.
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 <i>s</i>-named binding for a given name <i>s</i> form a partial closure system: for every object <i>x</i>, either no ancestor of <i>x</i> owns an <i>s</i>-named binding or there is a (necessarily unique) <em>least</em> such ancestor, <i>y</i>, w.r.t. inheritance.
If <i>y</i> exists, then the <i>s</i>-named arrow emanating from <i>y</i> is basically the result of the resolution process.
In the general case, an object can have <em>multiple minimal</em> ancestors that are owners of an <i>s</i>-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 <i>s</i>,
make sure that the new object itself becomes an owner of an <i>s</i>-named binding.
This solution is used in Smalltalk-80 by the [[#smalltalk-traits|traits]] mechanism.
<li>
Maintain additional ordering so that a <em>linearization</em> of ancestors can be established.
This applies to Ruby, Scala, Python, CLOS and Perl.
</ol>
=== Linearization ===
The <em>linearization</em> of an object <i>x</i>,
denoted <i>x.ancs</i>, is a list of ancestors of <i>x</i>
that determines the order in which ancestors are looked up for
ownership of a property (binding) with a given name.
For every <i>x</i>, <i>x.ancs</i> starts with <i>x</i> itself.
The <i>.ancs</i> map can be equivalently expressed as a "quadratic" inheritance – a partial order between pairs <i>(x,y)</i> where <i>x</i> is a descendant of <i>y</i>.
This structure can be conveniently termed <em>method resolution order</em>, abbreviated as <em>MRO</em> (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 <i>(x,y)</i> has at most one parent.
Starting at <i>(x,x)</i>, the traversal of ancestors in MRO yields <i>x.ancs</i>, the linearization of <i>x</i>.
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 <i>(x,y)</i> of objects such that <i>x ≤ y</i>.
== Transitions ==
Standard [[State transition system|transitions]] are those of new "user" object creation. The structure is modified by adding a primary object <i>x</i>, together with its (fictitious) eigenclass chain, such that <i>x</i> is minimal in inheritance.
Except for languages with degenerated metaclass roots, new object <i>x</i> creation (whether a terminal <i>x</i> or a class <i>x</i>) can be uniformly expressed as class instantiation:
: <code><i>x</i> := <i>q</i>.new(<i>p<sub>1</sub>, …, p<sub>n</sub></i>)</code>
where <i>q</i> is the requested class of <i>x</i> and
<i>p<sub>1</sub>, …, p<sub>n</sub></i> are the requested parents of <i>x</i>.
In practice, creation of terminal objects <i>x</i>
(where <i>q</i> is not a metaclass and necessarily <i>n</i> = 0)
is syntactically differentiated from creation of classes <i>x</i>
(where <i>q</i> 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 <i>q</i> is an inheritance root, then one cannot recognize, if <i>x</i> 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 <i>(<u>O</u></i>, ϵ'<i>)</i> are made separately by transitions of the canonical reduct, <i>(<u>O</u></i>, ϵ<i>)</i>, 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.
==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]]
</div>
== Notes ==
{{notelist|1}}
== References ==
{{reflist|2}}
[[Category:Object-oriented programming]]
[[Category:Object models]]
[[Category:Mathematical structures]]
| 