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.
Given
the linearization of Z is computed as
First, a metaclass to enable a short representation of the objects by name instead of the default class REPR value:
Next, we define our base classes:
Then we construct the inheritance tree:
And now:
Raku uses C3 linearization for classes by default:
(the Any and Mu are the types all Raku objects inherit from, so Any stands in place of O)
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) 0-89791-788-X ↩
News item on opendylan.org http://opendylan.org/news/2012/01/25/c3.html ↩
Dylan Enhancement Proposal 3: C3 superclass linearization http://opendylan.org/proposals/dep-0003.html ↩
Python 2.3's use of C3 MRO https://www.python.org/download/releases/2.3/mro/ ↩
Tutorial for practical applications of C3 linearization using Python http://rhettinger.wordpress.com/2011/05/26/super-considered-super/ ↩
Perl 6's use of the C3 MRO https://doc.perl6.org/type/Metamodel::C3MRO ↩
"Parrot uses C3 MRO". Archived from the original on 2007-02-08. Retrieved 2006-12-06. https://web.archive.org/web/20070208165958/http://aspn.activestate.com/ASPN/Mail/Message/perl6-internals/2746631 ↩
Tantau, Till (August 29, 2015). The TikZ & PGF Manual (PDF) (3.1.9a ed.). p. 1062. Retrieved 2021-05-15. http://ftp.ntua.gr/mirror/ctan/graphics/pgf/base/doc/pgfmanual.pdf ↩
C3 MRO available in Perl 5.10 and newer https://metacpan.org/module/mro ↩
Perl 5 extension for C3 MRO on CPAN https://metacpan.org/module/Class::C3 ↩
van Rossum, Guido (23 June 2010). "Method Resolution Order". The History of Python. Retrieved 18 January 2018. http://python-history.blogspot.co.uk/2010/06/method-resolution-order.html ↩