Liniarizarea superclasei C3 este un algoritm utilizat în principal pentru a obține o liniarizare stabilă a unei ierarhii de moștenire multiplă în programarea orientată pe obiecte . Această liniarizare este utilizată pentru a determina ordinea în care metodele ar trebui să fie moștenite, care este adesea menționată în literatura engleză ca „MRO” (prescurtare pentru „Method Resolution Order”, adică „method resolution order”). C3 în titlu indică trei trăsături principale ale liniarizării finale: grafic stabil și în expansiune (după vechime) , păstrarea ordinii locale de prioritate și monotonitatea. Această teorie a fost prezentată pentru prima dată în 1996 la conferința OOPSLA , într-o lucrare intitulată „Monotone Superclass Linearization for the Dylan Language” [1] . Ulterior, acest algoritm a fost ales ca algoritm implicit pentru rezoluția metodei în limbajul de programare Python 2.3 (și mai târziu), Perl 6 și mașina virtuală Parrot . Este disponibil și ca alternativă (nu MRO implicit) în nucleul Perl 5 începând cu versiunea 5.10.0. O implementare extinsă pentru versiunile anterioare de Perl 5 se numește Class::C3 și există la CPAN .
Pentru
clasa O clasa A se extinde pe O clasa B se extinde pe O clasa C se extinde pe O clasa D se extinde pe O clasa E se extinde pe O clasa K1 se extinde pe A, B, C clasa K2 se extinde pe D, B, E clasa K3 se extinde pe D, A clasa Z extinde K1, K2, K3Linearizarea lui Z este considerată ca
L(O) := [O] // liniarizarea lui O este trivială, este o listă cu un singur element [O] deoarece O nu are părinți L(A) := [A] + merge(L(O), [O]) // liniarizarea lui A este A plus unirea liniarizărilor părinților lui A și părinților lui A = [A] + îmbinare([O], [O]) = [A,O] L(B) := [B, O] // liniarizarea lui B, C, D și E L(C) := [C,O] L(D) := [D, O] L(E) := [E, O] L(K1) := [K1] + merge(L(A), L(B), L(C), [A, B, C]) // găsiți mai întâi linearizările părinților lui K1: L(A ), L(B) şi L(C); și alăturați-le cu lista de părinți [A, B, C] = [K1] + merge([A, O], [B, O], [C, O], [A, B, C]) // clasa A este potrivită pentru primul pas de îmbinare deoarece apare doar la începând toate listele = [K1, A] + merge([O], [B, O], [C, O], [B, C]) // clasa O nu este potrivită deoarece se află în cozile listelor 2 și 3, dar... = [K1, A, B] + îmbinare([O], [O], [C, O], [C]) = [K1, A, B, C] + merge([O], [O], [O]) // la urma urmei, clasa O rămâne singurul și ultimul candidat = [K1, A, B, C, O] L(K2) := [K2] + îmbinare(L(D), L(B), L(E), [D, B, E]) = [K2] + îmbinare([D, O], [B, O], [E, O], [D, B, E]) // selectați D = [K2, D] + merge([O], [B, O], [E, O], [B, E]) // O nu este potrivit, alegeți B = [K2, D, B] + merge([O], [O], [E, O], [E]) // O nu se potrivește, alegeți E = [K2, D, B, E] + merge([O], [O], [O]) // alegeți O = [K2, D, B, E, O] L(K3) := [K3] + îmbinare(L(D), L(A), [D, A]) = [K3] + îmbinare([D, O], [A, O], [D, A]) = [K3, D] + îmbinare([O], [A, O], [A]) = [K3, D, A] + îmbinare([O], [O]) = [K3, D, A, O] L(Z) := [Z] + îmbinare(L(K1), L(K2), L(K3), [K1, K2, K3]) = [Z] + îmbinare([K1, A, B, C, O], [K2, D, B, E, O], [K3, D, A, O], [K1, K2, K3]) / / selectați K1 = [Z, K1] + îmbinare([A, B, C, O], [K2, D, B, E, O], [K3, D, A, O], [K2, K3]) // A nu este potrivit, alegeți K2 = [Z, K1, K2] + îmbinare([A, B, C, O], [D, B, E, O], [K3, D, A, O], [K3]) // A nu t se potrivește, D nu se potrivește, alegeți K3 = [Z, K1, K2, K3] + merge([A, B, C, O], [D, B, E, O], [D, A, O]) // A nu se potrivește, alegeți D = [Z, K1, K2, K3, D] + merge([A, B, C, O], [B, E, O], [A, O]) // selectați A = [Z, K1, K2, K3, D, A] + îmbinare([B, C, O], [B, E, O], [O]) // selectați B = [Z, K1, K2, K3, D, A, B] + merge([C, O], [E, O], [O]) // selectați C = [Z, K1, K2, K3, D, A, B, C] + merge([O], [E, O], [O]) // O nu se potrivește, alegeți E = [Z, K1, K2, K3, D, A, B, C, E] + merge([O], [O], [O]) // alegeți O = [Z, K1, K2, K3, D, A, B, C, E, O] // răspunsDenumiri:
L(Class) - liniarizarea clasei Class [A,B,C] - o listă de trei elemente, unde capul este A și coada este [B,C] merge - îmbina listeFuncția de îmbinare îmbină listele în așa fel încât fiecare element să apară exact o dată în rezultat, în acest fel este similară cu îmbinarea mulțimilor, dar ordinea elementelor din listă este importantă aici. Funcția de îmbinare funcționează după cum urmează - iterează peste listele de argumente în ordinea apariției (de la stânga la dreapta), selectând primul element, care poate fi primul din mai multe liste, dar nu este menționat nicăieri în a doua și mai departe, și îl mută în lista de rezultate, excluzând din liste argumentele, repetând această procedură de mai multe ori până când toate elementele sunt mutate din listele de argumente în lista de rezultate. Dacă la un moment dat apare o situație în care este imposibil să se selecteze un element candidat care îndeplinește condiția specificată, de ex. dacă în toate listele de argumente primele elemente nu apar mai întâi în alte liste de argumente, lista rezultată nu este creată.