Content deleted Content added
link around redirect |
cleanup |
||
Line 4:
__TOC__
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 ''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''.
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'',
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>
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:
Line 102 ⟶ 64:
== {{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.
<table border="0" style="margin:2ex auto;"><tr>
Line 142 ⟶ 100:
The <span style="color:green">''∫''</span>-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.
Line 194 ⟶ 141:
=== 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''.
Line 214 ⟶ 156:
=== 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>''.
Line 234 ⟶ 171:
=== 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''.
Line 268 ⟶ 199:
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.
| |||