C3 linearization

Last updated

"In object-oriented systems with multiple inheritance, some mechanism must be used for resolving conflicts when inheriting different definitions of the same property from multiple superclasses." [1] C3 superclass linearization is an algorithm used primarily to obtain the order in which methods should be inherited in the presence of multiple inheritance. In other words, the output of C3 superclass linearization is a deterministic Method Resolution Order (MRO).

Contents

C3 superclass linearization is called C3 because it "is consistent with three properties": [1]

It was first published at the 1996 OOPSLA conference, in a paper entitled "A Monotonic Superclass Linearization for Dylan". [1] It was adapted to the Open Dylan implementation in January 2012 [2] following an enhancement proposal. [3] It has been chosen as the default algorithm for method resolution in Python 2.3 (and newer), [4] [5] Raku, [6] Parrot, [7] Solidity, and PGF/TikZ's Object-Oriented Programming module. [8] It is also available as an alternative, non-default MRO in the core of Perl 5 starting with version 5.10.0. [9] An extension implementation for earlier versions of Perl 5 named Class::C3 exists on CPAN. [10]

Python's Guido van Rossum summarizes C3 superclass linearization thus: [11]

Basically, the idea behind C3 is that if you write down all of the ordering rules imposed by inheritance relationships in a complex class hierarchy, the algorithm will determine a monotonic ordering of the classes that satisfies all of them. If such an ordering can not be determined, the algorithm will fail.

Description

The C3 superclass linearization of a class is the sum of the class plus a unique merge of the linearizations of its parents and a list of the parents itself. The list of parents as the last argument to the merge process preserves the local precedence order of direct parent classes.

The merge of parents' linearizations and parents list is done by selecting the first head of the lists which does not appear in the tail (all elements of a list except the first) of any of the lists. Note, that a good head may appear as the first element in multiple lists at the same time, but it is forbidden to appear anywhere else. The selected element is removed from all the lists where it appears as a head and appended to the output list. The process of selecting and removing a good head to extend the output list is repeated until all remaining lists are exhausted. If at some point no good head can be selected, because the heads of all remaining lists appear in any one tail of the lists, then the merge is impossible to compute due to inconsistent orderings of dependencies in the inheritance hierarchy and no linearization of the original class exists.

A naive divide-and-conquer approach to computing the linearization of a class may invoke the algorithm recursively to find the linearizations of parent classes for the merge-subroutine. However, this will result in an infinitely looping recursion in the presence of a cyclic class hierarchy. To detect such a cycle and to break the infinite recursion (and to reuse the results of previous computations as an optimization), the recursive invocation should be shielded against re-entrance of a previous argument by means of a cache or memoization.

This algorithm is similar to finding a topological ordering.

Example

Given

A dependency graph for the C3 linearization example. C3 linearization example.svg
A dependency graph for the C3 linearization example.
<nowiki/>classOclassAextendsOclassBextendsOclassCextendsOclassDextendsOclassEextendsOclassK1extendsC,A,BclassK3extendsA,DclassK2extendsB,D,EclassZextendsK1,K3,K2

the linearization of Z is computed as

<nowiki/>L(O):=[O]// the linearization of O is trivially the singleton list [O], because O has no parentsL(A):=[A]+merge(L(O),[O])// the linearization of A is A plus the merge of its parents' linearizations with the list of parents...=[A]+merge([O],[O])=[A,O]// ...which simply prepends A to its single parent's linearizationL(B):=[B,O]// linearizations of B, C, D and E are computed similar to that of AL(C):=[C,O]L(D):=[D,O]L(E):=[E,O]L(K1):=[K1]+merge(L(C),L(B),L(A),[C,A,B])// first, find the linearization of K1's parents, L(C), L(B), and L(A), and merge them with the parent list [C, A, B]=[K1]+merge([C,O],[B,O],[A,O],[C,A,B])// class C is a good candidate for the first merge step, because it only appears as the head of the first and last lists=[K1,C]+merge([O],[B,O],[A,O],[A,B])// class O is not a good candidate for the next merge step, because it also appears in the tails of list 2 and 3, class B is also not good; but class A is a good candidate=[K1,C,A]+merge([O],[B,O],[O],[B])// class B is a good candidate; class O still appears in the tail of list 2=[K1,C,A,B]+merge([O],[O],[O])// finally, class O is a valid candidate, which also exhausts all remaining lists=[K1,C,A,B,O]L(K3):=[K3]+merge(L(A),L(D),[A,D])=[K3]+merge([A,O],[D,O],[A,D])// select A=[K3,A]+merge([O],[D,O],[D])// fail O, select D=[K3,A,D]+merge([O],[O])// select O=[K3,A,D,O]L(K2):=[K2]+merge(L(B),L(D),L(E),[B,D,E])=[K2]+merge([B,O],[D,O],[E,O],[B,D,E])// select B=[K2,B]+merge([O],[D,O],[E,O],[D,E])// fail O, select D=[K2,B,D]+merge([O],[O],[E,O],[E])// fail O, select E=[K2,B,D,E]+merge([O],[O],[O])// select O=[K2,B,D,E,O]L(Z):=[Z]+merge(L(K1),L(K3),L(K2),[K1,K3,K2])=[Z]+merge([K1,C,A,B,O],[K3,A,D,O],[K2,B,D,E,O],[K1,K3,K2])// select K1=[Z,K1]+merge([C,A,B,O],[K3,A,D,O],[K2,B,D,E,O],[K3,K2])// select C=[Z,K1,C]+merge([A,B,O],[K3,A,D,O],[K2,B,D,E,O],[K3,K2])// fail A, select K3=[Z,K1,C,K3]+merge([A,B,O],[A,D,O],[K2,B,D,E,O],[K2])// select A=[Z,K1,C,K3,A]+merge([B,O],[D,O],[K2,B,D,E,O],[K2])// fail B, fail D, select K2=[Z,K1,C,K3,A,K2]+merge([B,O],[D,O],[B,D,E,O])// select B=[Z,K1,C,K3,A,K2,B]+merge([O],[D,O],[D,E,O])// fail O, select D=[Z,K1,C,K3,A,K2,B,D]+merge([O],[O],[E,O])// fail O, select E=[Z,K1,C,K3,A,K2,B,D,E]+merge([O],[O],[O])// select O=[Z,K1,C,K3,A,K2,B,D,E,O]// done.

Example demonstrated in Python 3

First, a metaclass to enable a short representation of the objects by name instead of the default class REPR value:

classType(type):def__repr__(cls):# Will make it so that repr(O) is "O" instead of "<__main__.O>",# and the same for any subclasses of O.returncls.__name__classO(object,metaclass=Type):pass

Next, we define our base classes:

classA(O):passclassB(O):passclassC(O):passclassD(O):passclassE(O):pass

Then we construct the inheritance tree:

classK1(C,A,B):passclassK3(A,D):passclassK2(B,D,E):passclassZ(K1,K3,K2):pass

And now:

>>> Z.mro()[Z, K1, C, K3, A, K2, B, D, E, O, <class 'object'>]

Example demonstrated in Raku

Raku uses C3 linearization for classes by default:

classA {} classB {} classC {} classD {} classE {} classK1isCisAisB {} classK3isAisD {} classK2isBisDisE {} classZisK1isK3isK2 {} sayZ.^mro; # OUTPUT: ((Z) (K1) (C) (K3) (A) (K2) (B) (D) (E) (Any) (Mu))

(the Any and Mu are the types all Raku objects inherit from, so Any stands in place of O)

Related Research Articles

<span class="mw-page-title-main">Heap (data structure)</span> Computer science data structure

In computer science, a heap is a tree-based data structure that satisfies the heap property: In a max heap, for any given node C, if P is a parent node of C, then the key of P is greater than or equal to the key of C. In a min heap, the key of P is less than or equal to the key of C. The node at the "top" of the heap is called the root node.

Multiple inheritance is a feature of some object-oriented computer programming languages in which an object or class can inherit features from more than one parent object or parent class. It is distinct from single inheritance, where an object or class may only inherit from one particular object or class.

<span class="mw-page-title-main">Merge sort</span> Divide and conquer sorting algorithm

In computer science, merge sort is an efficient, general-purpose, and comparison-based sorting algorithm. Most implementations produce a stable sort, which means that the relative order of equal elements is the same in the input and output. Merge sort is a divide-and-conquer algorithm that was invented by John von Neumann in 1945. A detailed description and analysis of bottom-up merge sort appeared in a report by Goldstine and von Neumann as early as 1948.

<span class="mw-page-title-main">Regular expression</span> Sequence of characters that forms a search pattern

A regular expression, sometimes referred to as rational expression, is a sequence of characters that specifies a match pattern in text. Usually such patterns are used by string-searching algorithms for "find" or "find and replace" operations on strings, or for input validation. Regular expression techniques are developed in theoretical computer science and formal language theory.

<span class="mw-page-title-main">Sorting algorithm</span> Algorithm that arranges lists in order

In computer science, a sorting algorithm is an algorithm that puts elements of a list into an order. The most frequently used orders are numerical order and lexicographical order, and either ascending or descending. Efficient sorting is important for optimizing the efficiency of other algorithms that require input data to be in sorted lists. Sorting is also often useful for canonicalizing data and for producing human-readable output.

<span class="mw-page-title-main">Triple DES</span> Block cipher

In cryptography, Triple DES, officially the Triple Data Encryption Algorithm, is a symmetric-key block cipher, which applies the DES cipher algorithm three times to each data block. The Data Encryption Standard's (DES) 56-bit key is no longer considered adequate in the face of modern cryptanalytic techniques and supercomputing power. A CVE released in 2016, CVE-2016-2183 disclosed a major security vulnerability in DES and 3DES encryption algorithms. This CVE, combined with the inadequate key size of DES and 3DES, led to NIST deprecating DES and 3DES for new applications in 2017, and for all applications by the end of 2023. It has been replaced with the more secure, more robust AES.

A discrete Hartley transform (DHT) is a Fourier-related transform of discrete, periodic data similar to the discrete Fourier transform (DFT), with analogous applications in signal processing and related fields. Its main distinction from the DFT is that it transforms real inputs to real outputs, with no intrinsic involvement of complex numbers. Just as the DFT is the discrete analogue of the continuous Fourier transform (FT), the DHT is the discrete analogue of the continuous Hartley transform (HT), introduced by Ralph V. L. Hartley in 1942.

<span class="mw-page-title-main">Runge–Kutta methods</span> Family of implicit and explicit iterative methods

In numerical analysis, the Runge–Kutta methods are a family of implicit and explicit iterative methods, which include the Euler method, used in temporal discretization for the approximate solutions of simultaneous nonlinear equations. These methods were developed around 1900 by the German mathematicians Carl Runge and Wilhelm Kutta.

In physics, a ferromagnetic material is said to have magnetocrystalline anisotropy if it takes more energy to magnetize it in certain directions than in others. These directions are usually related to the principal axes of its crystal lattice. It is a special case of magnetic anisotropy. In other words, the excess energy required to magnetize a specimen in a particular direction over that required to magnetize it along the easy direction is called crystalline anisotropy energy.

One-key MAC (OMAC) is a family of message authentication codes constructed from a block cipher much like the CBC-MAC algorithm. It may be used to provide assurance of the authenticity and, hence, the integrity of data. Two versions are defined:

In chemistry, a steady state is a situation in which all state variables are constant in spite of ongoing processes that strive to change them. For an entire system to be at steady state, i.e. for all state variables of a system to be constant, there must be a flow through the system. A simple example of such a system is the case of a bathtub with the tap running but with the drain unplugged: after a certain time, the water flows in and out at the same rate, so the water level stabilizes and the system is in a steady state.

qrpff is a Perl script created by Keith Winstein and Marc Horowitz of the MIT SIPB. It performs DeCSS in six or seven lines. The name itself is an encoding of "decss" in rot-13. The algorithm was rewritten 77 times to condense it down to six lines.

Extendible hashing is a type of hash system which treats a hash as a bit string and uses a trie for bucket lookup. Because of the hierarchical nature of the system, re-hashing is an incremental operation. This means that time-sensitive applications are less affected by table growth than by standard full-table rehashes.

In mathematics, the Runge–Kutta–Fehlberg method is an algorithm in numerical analysis for the numerical solution of ordinary differential equations. It was developed by the German mathematician Erwin Fehlberg and is based on the large class of Runge–Kutta methods.

Transient kinetic isotope effects occur when the reaction leading to isotope fractionation does not follow pure first-order kinetics and therefore isotopic effects cannot be described with the classical equilibrium fractionation equations or with steady-state kinetic fractionation equations. In these instances, the general equations for biochemical isotope kinetics (GEBIK) and the general equations for biochemical isotope fractionation (GEBIF) can be used.

In mathematics, more specifically, in convex geometry, the mixed volume is a way to associate a non-negative number to a tuple of convex bodies in . This number depends on the size and shape of the bodies, and their relative orientation to each other.

In numerical analysis and scientific computing, the Gauss–Legendre methods are a family of numerical methods for ordinary differential equations. Gauss–Legendre methods are implicit Runge–Kutta methods. More specifically, they are collocation methods based on the points of Gauss–Legendre quadrature. The Gauss–Legendre method based on s points has order 2s.

<span class="mw-page-title-main">Centripetal Catmull–Rom spline</span> Variant form of the Catmull-Rom spine

In computer graphics, the centripetal Catmull–Rom spline is a variant form of the Catmull–Rom spline, originally formulated by Edwin Catmull and Raphael Rom, which can be evaluated using a recursive algorithm proposed by Barry and Goldman. It is a type of interpolating spline defined by four control points , with the curve drawn only from to .

Funnelsort is a comparison-based sorting algorithm. It is similar to mergesort, but it is a cache-oblivious algorithm, designed for a setting where the number of elements to sort is too large to fit in a cache where operations are done. It was introduced by Matteo Frigo, Charles Leiserson, Harald Prokop, and Sridhar Ramachandran in 1999 in the context of the cache oblivious model.

In the bin covering problem, items of different sizes must be packed into a finite number of bins or containers, each of which must contain at least a certain given total size, in a way that maximizes the number of bins used.

References

  1. 1 2 3 Kim Barrett, Bob Cassels, Paul Haahr, David A. Moon, Keith Playford, P. Tucker Withington (1996-06-28). "A Monotonic Superclass Linearization for Dylan". OOPSLA '96 Conference Proceedings. ACM Press. pp. 69–82. CiteSeerX   10.1.1.19.3910 . doi:10.1145/236337.236343. ISBN   0-89791-788-X.{{cite conference}}: CS1 maint: multiple names: authors list (link)
  2. ↑ News item on opendylan.org
  3. ↑ Dylan Enhancement Proposal 3: C3 superclass linearization
  4. ↑ Python 2.3's use of C3 MRO
  5. ↑ Tutorial for practical applications of C3 linearization using Python
  6. ↑ Perl 6's use of the C3 MRO
  7. ↑ "Parrot uses C3 MRO". Archived from the original on 2007-02-08. Retrieved 2006-12-06.
  8. ↑ Tantau, Till (August 29, 2015). The TikZ & PGF Manual (PDF) (3.1.9a ed.). p. 1062. Retrieved 2021-05-15.
  9. ↑ C3 MRO available in Perl 5.10 and newer
  10. ↑ Perl 5 extension for C3 MRO on CPAN
  11. ↑ van Rossum, Guido (23 June 2010). "Method Resolution Order". The History of Python. Retrieved 18 January 2018.
This page is based on this Wikipedia article
Text is available under the CC BY-SA 4.0 license; additional terms may apply.
Images, videos and audio are available under their respective licenses.