Python 2.3-metodens upplösningsordning

Anteckning

Detta är ett historiskt dokument, som tillhandahålls som en bilaga till den officiella dokumentationen. Method Resolution Order som diskuteras här introducerades i Python 2.3, men den används fortfarande i senare versioner - inklusive Python 3.

Av Michele Simionato.

Abstrakt:

Detta dokument är avsett för Python-programmerare som vill förstå C3-metoden Resolution Order som används i Python 2.3. Även om det inte är avsett för nybörjare är det ganska pedagogiskt med många utarbetade exempel. Jag känner inte till andra offentligt tillgängliga dokument med samma omfattning, därför bör det vara användbart.

Ansvarsfriskrivning:

Jag donerar detta dokument till Python Software Foundation, under Python 2.3-licensen. Som vanligt under dessa omständigheter varnar jag läsaren för att det som följer * bör * vara korrekt, men jag ger ingen garanti. Använd det på egen risk och fara!

Erkännande:

Alla personer på Pythons e-postlista som skickade mig sitt stöd. Paul Foley som påpekade olika felaktigheter och fick mig att lägga till delen om lokal prioritetsordning. David Goodger för hjälp med formateringen i reStructuredText. David Mertz för hjälp med redigeringen. Slutligen, Guido van Rossum som entusiastiskt lade till detta dokument på den officiella Python 2.3-webbplatsen.

Början

Felix qui potuit rerum cognoscere causas – Virgilius

Allt började med ett inlägg av Samuele Pedroni till e-postlistan för Python-utveckling [1]. I sitt inlägg visade Samuele att Python 2.2-metodens upplösningsordning inte är monoton och han föreslog att den skulle ersättas med C3-metodens upplösningsordning. Guido höll med om hans argument och därför använder Python 2.3 nu C3. C3-metoden i sig har inget med Python att göra, eftersom den uppfanns av personer som arbetade med Dylan och beskrivs i ett dokument som är avsett för lispers [2]. Den här artikeln ger en (förhoppningsvis) läsbar diskussion av C3-algoritmen för Pythonistas som vill förstå orsakerna till förändringen.

Först och främst vill jag påpeka att det jag ska säga bara gäller de nya stilklasserna som introducerades i Python 2.2: klassiska klasser behåller sin gamla metodupplösningsordning, djupet först och sedan vänster till höger. Därför finns det inget brott mot gammal kod för klassiska klasser; och även om det i princip skulle kunna finnas brott mot kod för Python 2.2 nya stilklasser, är de fall där C3-resolutionsordningen skiljer sig från Python 2.2-metodresolutionsordningen i praktiken så sällsynta att inget verkligt brott mot kod förväntas. Därför bör följande gälla:

Var inte rädd!

Om du inte använder dig mycket av multipel nedärvning och har icke-triviala hierarkier behöver du inte heller förstå C3-algoritmen, och du kan enkelt hoppa över den här artikeln. Å andra sidan, om du verkligen vill veta hur multipel arv fungerar, då är det här dokumentet för dig. Den goda nyheten är att saker och ting inte är så komplicerade som du kanske förväntar dig.

Låt mig börja med några grundläggande definitioner.

1. Givet en klass C i en komplicerad hierarki med flera arvsanlag är det en icke-trivial uppgift att ange i vilken ordning metoder åsidosätts, dvs. att ange ordningen på C:s förfäder.

2. Listan över förfäderna till en klass C, inklusive klassen själv, ordnad från den närmaste förfadern till den mest avlägsna, kallas klassens företrädeslista eller lineariseringen av C.

3. Method Resolution Order (MRO) är den uppsättning regler som konstruerar linjäriseringen. I Python-litteraturen används idiomet ”MRO för C” också som en synonym för linjäriseringen av klassen C.

4. Om C till exempel är en underklass till C1 och C1 är en underklass till C2 i en enkel arvshierarki, är linjäriseringen av C helt enkelt listan [C, C1 , C2]. Men med flera arvshierarkier är konstruktionen av linjäriseringen mer besvärlig, eftersom det är svårare att konstruera en linjärisering som respekterar lokal prioritetsordning och monotonicitet.

5. Jag kommer att diskutera den lokala prioritetsordningen senare, men jag kan ge definitionen av monotonicitet här. En MRO är monoton när följande är sant: om C1 föregår C2 i linjäriseringen av C, så föregår C1 C2 i linjäriseringen av någon underklass av C. I annat fall kan den oskyldiga åtgärden att härleda en ny klass ändra metodernas upplösningsordning, vilket kan leda till mycket subtila buggar. Exempel där detta händer kommer att visas senare.

6. Inte alla klasser tillåter en linjärisering. Det finns fall, i komplicerade hierarkier, där det inte är möjligt att härleda en klass så att dess linjärisering respekterar alla önskade egenskaper.

Här ger jag ett exempel på denna situation. Tänk på hierarkin

>>> O = object
>>> class X(O): pass
>>> class Y(O): pass
>>> class A(X,Y): pass
>>> class B(Y,X): pass

som kan representeras med följande arvsgraf, där jag med O har betecknat klassen objekt, som är början på varje hierarki för nya stilklasser:

 -----------
| |
| O |
| / \ |
 - X Y /
   | / | /
   | / |/
   A B
   \ /
     ?

I det här fallet är det inte möjligt att härleda en ny klass C från A och B, eftersom X föregår Y i A, men Y föregår X i B, och därför skulle metodens upplösningsordning vara tvetydig i C.

Python 2.3 gör ett undantag i denna situation (TypeError: MRO conflict among bases Y, X) och förbjuder den naive programmeraren att skapa tvetydiga hierarkier. Python 2.2 ger istället inte upphov till ett undantag, utan väljer en ad hoc-ordning (CABXYO i det här fallet).

C3-metoden Upplösningsorder

Låt mig introducera några enkla notationer som kommer att vara till nytta i den följande diskussionen. Jag kommer att använda förkortningsnotationen:

C1 C2 ... CN

för att ange listan över klasser [C1, C2, … , CN].

Listans huvud är dess första element:

huvud = C1

medan svansen är resten av listan:

svans = C2 ... CN.

Jag kommer också att använda notationen:

C + (C1 C2 ... CN) = C C1 C2 ... CN

för att beteckna summan av listorna [C] + [C1, C2, … ,CN].

Nu kan jag förklara hur MRO fungerar i Python 2.3.

Betrakta en klass C i en hierarki med flera arvsanlag, där C ärver från basklasserna B1, B2, … , BN. Vi vill beräkna linjäriseringen L[C] för klassen C. Regeln är följande:

linjäriseringen av C är summan av C plus sammanslagningen av linjäriseringarna av föräldrarna och listan över föräldrarna.

I symbolisk notation:

L[C(B1 ... BN)] = C + merge(L[B1] ... L[BN], B1 ... BN)

I synnerhet om C är klassen objekt, som inte har några föräldrar, är linjäriseringen trivial:

L[objekt] = objekt.

I allmänhet måste man dock beräkna sammanslagningen enligt följande recept:

ta huvudet på den första listan, dvs L[B1][0]; om detta huvud inte finns i svansen på någon av de andra listorna, lägg då till det i linjäriseringen av C och ta bort det från listorna i sammanslagningen, annars titta på huvudet på nästa lista och ta det, om det är ett bra huvud. Upprepa sedan operationen tills alla klasser är borttagna eller det är omöjligt att hitta bra huvuden. I det här fallet är det omöjligt att konstruera sammanslagningen, Python 2.3 kommer att vägra att skapa klassen C och kommer att ge upphov till ett undantag.

Denna föreskrift säkerställer att sammanslagningsoperationen bevarar ordningen, om ordningen kan bevaras. Å andra sidan, om ordningen inte kan bevaras (som i exemplet med allvarlig oenighet om ordningen som diskuterades ovan) kan sammanslagningen inte beräknas.

Beräkningen av sammanslagningen är trivial om C bara har en förälder (enkel nedärvning); i detta fall:

L[C(B)] = C + merge(L[B],B) = C + L[B]

Men när det gäller multipel arv är saker och ting mer besvärliga och jag förväntar mig inte att du kan förstå regeln utan ett par exempel ;-)

Exempel

Första exemplet. Tänk på följande hierarki:

>>> O = object
>>> class F(O): pass
>>> class E(O): pass
>>> class D(O): pass
>>> class C(D,F): pass
>>> class B(D,E): pass
>>> class A(B,C): pass

I detta fall kan arvsgrafen ritas enligt följande:

                          6
                         ---
Nivå 3 | O | (mer allmänt)
                      / --- \
                     / | \ |
                    / | \ |
                   / | \ |
                  --- --- --- |
Nivå 2 3 | D | 4| E | | F | 5 | --- --- --- --- --- --- --- --- ---
                  --- --- --- |
                   \ \ _ / | |
                    \ / \ _ | |
                     \ / \ | |
                      --- --- |
Nivå 1 1 | B | | C | 2
                      --- --- |
                        \ / |
                         \ / \ /
                           ---
Nivå 0 0 | A | (mer specialiserad)
                           ---

Linjäriseringarna av O,D,E och F är triviala:

L[O] = O
L[D] = D O
L[E] = E O
L[F] = F O

Linjäriseringen av B kan beräknas som:

L[B] = B + sammanslagning(DO, EO, DE)

Vi ser att D är ett bra huvud, därför tar vi det och vi reduceras till att beräkna merge(O,EO,E). Nu är O inte ett bra huvud, eftersom det ligger i svansen på sekvensen EO. I det här fallet säger regeln att vi måste hoppa till nästa sekvens. Då ser vi att E är ett bra huvud; vi tar det och vi reduceras till att beräkna merge(O,O) vilket ger O. Därför:

L[B] = B D E O

Genom att använda samma procedur finner man:

L[C] = C + merge(DO,FO,DF)
     = C + D + merge(O,FO,F)
     = C + D + F + merge(O,O)
     = C D F O

Nu kan vi beräkna:

L[A] = A + merge(BDEO,CDFO,BC)
     = A + B + sammanslagning(DEO,CDFO,C)
     = A + B + C + sammanslagning(DEO,DFO)
     = A + B + C + D + sammanslagning(EO,FO)
     = A + B + C + D + E + merge(O,FO)
     = A + B + C + D + E + F + merge(O,O)
     = A B C D E F O

I det här exemplet är linjäriseringen ordnad på ett ganska bra sätt enligt arvsnivån, i den meningen att lägre nivåer (dvs. mer specialiserade klasser) har högre prioritet (se arvsgrafen). Detta är dock inte det generella fallet.

Jag lämnar som en övning för läsaren att beräkna linjäriseringen för mitt andra exempel:

>>> O = object
>>> class F(O): pass
>>> class E(O): pass
>>> class D(O): pass
>>> class C(D,F): pass
>>> class B(E,D): pass
>>> class A(B,C): pass

Den enda skillnaden mot föregående exempel är ändringen B(D,E) –> B(E,D), men även en sådan liten ändring förändrar helt hierarkins ordning:

                           6
                          ---
Nivå 3 | O |
                       / --- \
                      / | \
                     / | \
                    / | \
                  --- --- ---
Nivå 2 2 | E | 4 | D | | F | 5
                  --- --- ---
                   \ / \ /
                    \ / \ /
                     \ / \ /
                      --- ---
Nivå 1 1 | B | | C | 3
                      --- ---
                       \ /
                        \ /
                          ---
Nivå 0 0 | A |
                          ---

Observera att klassen E, som befinner sig på den andra nivån i hierarkin, föregår klassen C, som befinner sig på den första nivån i hierarkin, dvs E är mer specialiserad än C, även om den befinner sig på en högre nivå.

En lat programmerare kan få MRO direkt från Python 2.2, eftersom det i detta fall sammanfaller med Python 2.3-linjäriseringen. Det räcker med att anropa mro()-metoden för klass A:

>>> A.mro()
[<class 'A'>, <class 'B'>, <class 'E'>,
<class 'C'>, <class 'D'>, <class 'F'>,
<class 'object'>]

Låt mig slutligen ta upp det exempel som diskuterades i det första avsnittet, med en allvarlig oenighet om ordern. I det här fallet är det enkelt att beräkna linjäriseringarna av O, X, Y, A och B:

L[O] = 0
L[X] = X O
L[Y] = Y O
L[A] = A X Y O
L[B] = B Y X O

Det är dock omöjligt att beräkna linjäriseringen för en klass C som ärver från A och B:

L[C] = C + sammanslagning(AXYO, BYXO, AB)
     = C + A + sammanslagning(XYO, BYXO, B)
     = C + A + B + sammanslagning(XYO, YXO)

Vid denna punkt kan vi inte slå samman listorna XYO och YXO, eftersom X är i svansen på YXO medan Y är i svansen på XYO: därför finns det inga bra huvuden och C3-algoritmen stannar. Python 2.3 ger upphov till ett fel och vägrar att skapa klassen C.

Bad Method Resolution Order

En MRO är dålig när den bryter mot sådana grundläggande egenskaper som lokal prioritetsordning och monotonicitet. I det här avsnittet ska jag visa att både MRO för klassiska klasser och MRO för new style-klasser i Python 2.2 är dåliga.

Det är lättare att börja med den lokala prioritetsordningen. Tänk på följande exempel:

>>> F=type('Food',(),{'remember2buy':'spam'})
>>> E=type('Eggs',(F,),{'remember2buy':'eggs'})
>>> G=type('GoodFood',(F,E),{}) # under Python 2.3 this is an error!

med nedärvningsdiagram

             O
             |
(köp skräppost) F
             | \
             | E (köp ägg)
             | /
             G

      (köpa ägg eller spam?)

Vi ser att klass G ärver från F och E, med F före E: därför skulle vi förvänta oss att attributet G.remember2buy ärvs av F.remember2buy och inte av E.remember2buy: ändå ger Python 2.2

>>> G.remember2buy
'eggs'

Detta är ett brott mot lokal prioritetsordning eftersom ordningen i den lokala prioritetslistan, dvs. listan över G:s föräldrar, inte bevaras i Python 2.2-linjäriseringen av G:

L[G,P22]= G E F objekt # F *följer* E

Man skulle kunna hävda att anledningen till att F följer E i Python 2.2-linjäriseringen är att F är mindre specialiserad än E, eftersom F är superklassen till E. Ändå är brytningen av lokal prioritetsordning ganska icke-intuitiv och felbenägen. Detta är särskilt sant eftersom det skiljer sig från klasser i gammal stil:

>>> class F: remember2buy='spam'
>>> class E(F): remember2buy='eggs'
>>> class G(F,E): pass
>>> G.remember2buy
'spam'

I detta fall är den huvudsakliga bestämmelseorten GFEF och den lokala prioritetsordningen bevaras.

Som en allmän regel bör hierarkier som den föregående undvikas, eftersom det är oklart om F ska åsidosätta E eller vice versa. Python 2.3 löser tvetydigheten genom att lyfta ett undantag i skapandet av klass G, vilket effektivt hindrar programmeraren från att generera tvetydiga hierarkier. Anledningen till detta är att C3-algoritmen misslyckas när merge:

sammanfoga(FO,EFO,FE)

kan inte beräknas, eftersom F är i svansen på EFO och E är i svansen på FE.

Den verkliga lösningen är att utforma en icke-tvetydig hierarki, dvs. att härleda G från E och F (den mer specifika först) och inte från F och E; i detta fall är MRO utan tvekan GEF.

           O
           |
           F (skräppost)
         / |
(ägg) E |
         \ |
           G
             (ägg, utan tvekan)

Python 2.3 tvingar programmeraren att skriva bra hierarkier (eller åtminstone mindre felbenägna sådana).

I sammanhanget vill jag påpeka att Python 2.3-algoritmen är tillräckligt smart för att känna igen uppenbara misstag, t.ex. dubblering av klasser i listan över föräldrar:

>>> class A(object): pass
>>> class C(A,A): pass # error
Traceback (most recent call last):
  File "<stdin>", line 1, in ?
TypeError: duplicate base class A

Python 2.2 (både för klassiska klasser och klasser med ny stil) skulle i denna situation inte ge upphov till något undantag.

Slutligen vill jag peka på två lärdomar som vi har dragit av detta exempel:

1. trots namnet bestämmer MRO resolutionsordningen för attribut, inte bara för metoder;

2. standardmat för Pythonistas är spam ! (men det visste du redan ;-)

Efter att ha diskuterat frågan om lokal prioritetsordning, låt mig nu ta upp frågan om monotonicitet. Mitt mål är att visa att varken MRO för klassiska klasser eller för Python 2.2 new style classes är monoton.

Att bevisa att MRO för klassiska klasser är icke-monoton är ganska trivialt, det räcker med att titta på diamantdiagrammet:

   C
  / \
 / \
A B
 \ /
  \ /
   D

Man kan lätt urskilja inkonsekvensen:

L[B,P21] = B C # B föregår C : B:s metoder vinner
L[D,P21] = D A C B C # B följer C : C:s metoder vinner!

Å andra sidan finns det inga problem med Python 2.2 och 2.3 MRO, de ger båda:

L[D] = D A B C

Guido påpekar i sin essä [3] att den klassiska MRO inte är så illa i praktiken, eftersom man vanligtvis kan undvika diamanter för klassiska klasser. Men alla klasser i ny stil ärver från objekt, därför är diamanter oundvikliga och inkonsekvenser dyker upp i varje multipel arvgraf.

MRO i Python 2.2 gör det svårt, men inte omöjligt, att bryta monotonicitet. Följande exempel, ursprungligen tillhandahållet av Samuele Pedroni, visar att MRO i Python 2.2 är icke-monoton:

>>> class A(object): pass
>>> class B(object): pass
>>> class C(object): pass
>>> class D(object): pass
>>> class E(object): pass
>>> class K1(A,B,C): pass
>>> class K2(D,B,E): pass
>>> class K3(D,A):   pass
>>> class Z(K1,K2,K3): pass

Här är linjäriseringarna enligt C3 MRO (läsaren bör verifiera dessa linjäriseringar som en övning och rita arvsdiagrammet ;-)

L[A] = A O
L[B] = B O
L[C] = C O
L[D] = D O
L[E] = E O
L[K1]= K1 A B C O
L[K2]= K2 D B E O
L[K3]= K3 D A O
L[Z] = Z K1 K2 K3 D A B C E O

Python 2.2 ger exakt samma linjäriseringar för A, B, C, D, E, K1, K2 och K3, men en annan linjärisering för Z:

L[Z,P22] = Z K1 K3 A K2 D B C E O

Det är uppenbart att denna linjärisering är felaktig, eftersom A kommer före D medan A i linjäriseringen av K3 kommer efter D. Med andra ord, i K3 åsidosätter metoder som härrör från D metoder som härrör från A, men i Z, som fortfarande är en underklass till K3, åsidosätter metoder som härrör från A metoder som härrör från D! Detta är ett brott mot monotonicitet. Dessutom är Python 2.2-linjäriseringen av Z också inkonsekvent med lokal prioritetsordning, eftersom den lokala prioritetslistan för klassen Z är [K1, K2, K3] (K2 föregår K3), medan K2 i linjäriseringen av Z följer K3. Dessa problem förklarar varför 2.2-regeln har avfärdats till förmån för C3-regeln.

Slutet

Detta avsnitt är för den otåliga läsaren, som hoppat över alla tidigare avsnitt och hoppade direkt till slutet. Det här avsnittet är också för den lata programmeraren, som inte ville träna sin hjärna. Slutligen är det för programmeraren med lite hybris, annars skulle han / hon inte läsa ett papper om C3-metodens upplösningsordning i flera arvshierarkier ;-) Dessa tre dygder tillsammans (och inte var för sig) förtjänar ett pris: priset är ett kort Python 2.2-skript som gör att du kan beräkna 2,3 MRO utan risk för din hjärna. Ändra bara den sista raden för att leka med de olika exemplen som jag har diskuterat i det här dokumentet::

#<mro.py>

"""C3 algorithm by Samuele Pedroni (with readability enhanced by me)."""

class __metaclass__(type):
    "All classes are metamagically modified to be nicely printed"
    __repr__ = lambda cls: cls.__name__

class ex_2:
    "Serious order disagreement" #From Guido
    class O: pass
    class X(O): pass
    class Y(O): pass
    class A(X,Y): pass
    class B(Y,X): pass
    try:
        class Z(A,B): pass #creates Z(A,B) in Python 2.2
    except TypeError:
        pass # Z(A,B) cannot be created in Python 2.3

class ex_5:
    "My first example"
    class O: pass
    class F(O): pass
    class E(O): pass
    class D(O): pass
    class C(D,F): pass
    class B(D,E): pass
    class A(B,C): pass

class ex_6:
    "My second example"
    class O: pass
    class F(O): pass
    class E(O): pass
    class D(O): pass
    class C(D,F): pass
    class B(E,D): pass
    class A(B,C): pass

class ex_9:
    "Difference between Python 2.2 MRO and C3" #From Samuele
    class O: pass
    class A(O): pass
    class B(O): pass
    class C(O): pass
    class D(O): pass
    class E(O): pass
    class K1(A,B,C): pass
    class K2(D,B,E): pass
    class K3(D,A): pass
    class Z(K1,K2,K3): pass

def merge(seqs):
    print '\n\nCPL[%s]=%s' % (seqs[0][0],seqs),
    res = []; i=0
    while 1:
      nonemptyseqs=[seq for seq in seqs if seq]
      if not nonemptyseqs: return res
      i+=1; print '\n',i,'round: candidates...',
      for seq in nonemptyseqs: # find merge candidates among seq heads
          cand = seq[0]; print ' ',cand,
          nothead=[s for s in nonemptyseqs if cand in s[1:]]
          if nothead: cand=None #reject candidate
          else: break
      if not cand: raise "Inconsistent hierarchy"
      res.append(cand)
      for seq in nonemptyseqs: # remove cand
          if seq[0] == cand: del seq[0]

def mro(C):
    "Compute the class precedence list (mro) according to C3"
    return merge([[C]]+map(mro,C.__bases__)+[list(C.__bases__)])

def print_mro(C):
    print '\nMRO[%s]=%s' % (C,mro(C))
    print '\nP22 MRO[%s]=%s' % (C,C.mro())

print_mro(ex_9.Z)

#</mro.py>

Det var allt, gott folk,

njut!

Resurser

[1]

Tråden på python-dev startad av Samuele Pedroni: https://mail.python.org/pipermail/python-dev/2002-October/029035.html

[2]

Uppsatsen A Monotonic Superclass Linearization for Dylan: https://doi.org/10.1145/236337.236343

[3]

Guido van Rossums uppsats, Unifying types and classes in Python 2.2: https://web.archive.org/web/20140210194412/http://www.python.org/download/releases/2.2.2/descrintro