Multiple inheritance — Python's C3 linearization algorithm

2.1.10 · Coding › OOP Fundamentals

WHY humein C3 chahiye?

WHAT kya galat hota hai bina achhe algorithm ke:

Purana Python (pre-2.3) depth-first, left-to-right use karta tha: D → B → A → C. Disaster — usne A ko C se pehle check kiya, jabki C A se "zyada derived" hai.
Hum chahte hain: ek child hamesha apne parents se pehle aaye, aur original parent order preserve ho.

C3 dono fix karta hai. Teen properties jo yeh guarantee karta hai:

Consistency with local precedence — class statement mein parents ka order maintain rehta hai.
Monotonicity — agar kisi parent ke MRO mein X, Y se pehle aata hai, to woh order kisi bhi subclass mein kabhi reverse nahi hoga.
Child hamesha apne saare parents se pehle appear karta hai.

HOW algorithm kaam karta hai — scratch se derive kiya hua

HOW merge kaam karta hai (yahi dil hai):

Worked Example 1 — Diamond

Classes: class A, class B(A), class C(A), class D(B, C).

Step — pehle simple waalon ko linearize karo. Yeh step kyun? C3 recursive hai; $L [D]$ se pehle humein $L [B]$ aur $L [C]$ chahiye.

$L [A] = [A, object]$ $L [B] = B + merge (L [A], [A]) = B + merge ([A, O], [A]) = [B, A, O]$ $L [C] = [C, A, O]$

Step — D ko linearize karo. Yeh step kyun? Ab dono parents ke saath master formula apply karo.

$L [D] = D + merge ([B, A, O], [C, A, O], [B, C])$

Ab merge chalao:

Iter	Lists	Candidate head	Good?	Why
1	`[B,A,O] [C,A,O] [B,C]`	`B`	✅	`B` kisi tail mein nahi hai
2	`[A,O] [C,A,O] [C]`	`A`	❌	`A` list 2 ki tail mein hai → skip; `C` try karo (list2 ka head) ✅
3	`[A,O] [A,O] []`	`A`	✅	ab kisi tail mein nahi hai
4	`[O] [O] []`	`O`	✅

Result: $L [D] = [D, B, C, A, object]$ .

Worked example Real Python mein verify karo

class A: pass
class B(A): pass
class C(A): pass
class D(B, C): pass
print(D.__mro__)
# (<class 'D'>, <class 'B'>, <class 'C'>, <class 'A'>, <class 'object'>)

Dekho: A (shared grandparent) ek baar appear karta hai, aur B aur C dono ke baad.

Figure — Multiple inheritance — Python's C3 linearization algorithm

Worked Example 2 — ek inconsistent hierarchy

class X, class Y, class A(X, Y), class B(Y, X), class C(A, B).

Yeh kyun dekhein? Yeh dikhata hai jab C3 fail karta hai aur Python class ko reject karta hai.

$L [A] = [A, X, Y, O]$ , $L [B] = [B, Y, X, O]$ .

$L [C] = C + merge ([A, X, Y, O], [B, Y, X, O], [A, B])$

A emit karo ✅ → lists: [X,Y,O] [B,Y,X,O] [B]
X try karo: woh list 2 ke tail mein hai (...,Y,X,O) → skip.
B try karo (list 2 ka head): kya B kisi tail mein hai? Nahi → B emit karo ✅ → [X,Y,O] [Y,X,O] []
X try karo: list 2 ke tail mein hai (Y,X,O) → skip. Y try karo (list2 ka head): list 1 ke tail mein hai (X,Y,O) → skip. Koi good head nahi!

→ TypeError: Cannot create a consistent method resolution order (MRO). Reason: A chahta hai X before Y, B chahta hai Y before X. Contradiction → koi valid linear order exist nahi karta.

Flashcards

MRO ka matlab kya hai aur woh hai kya?

Method Resolution Order — woh single linear order jisme Python kisi attribute/method ke liye classes search karta hai.

C3 linearization of class C ko kaun sa formula define karta hai?

L [C] = C + merge (L [P_{1}], \dots, L [P_{n}], [P_{1}, \dots, P_{n}])

C3 merge mein head "good head" kab hota hai?

Jab woh kisi bhi remaining list ke tail (head ke baad koi bhi position) mein NAHI aata.

Jo head kisi list ke tail mein milta hai uske saath kya hota hai?

Use skip kar diya jaata hai; aap next list ka head test karne jaate hain.

D(B,C) ka MRO kya hai jahan B(A), C(A) hain?

[D, B, C, A, object].

Kyun shared base MRO mein sirf ek baar aur apne descendants ke baad appear karta hai?

Child ko hamesha uske parents se pehle search kiya jaana chahiye; merging base ko har us class ke baad place karti hai jo usse derive karta hai, bina duplicates ke.

Python kya error raise karta hai jab C3 consistent MRO nahi bana pata?

TypeError: Cannot create a consistent method resolution order (MRO).

Kya super() literal parent class ko call karta hai?

Nahi — yeh MRO mein next class ko call karta hai, jo ek sibling ho sakta hai, written parent nahi.

C3 ka base case kya hai?

L [object] = [object]

C3 ki teen guarantees ke naam batao.

Local precedence order preserved, monotonicity, aur child-before-parent.

Recall Feynman: 12-saal-ke-bachche ko samjhao

Socho tum apne family se koi sawaal poochh rahe ho, aur ek rule hai pehle kisse poochho. Tum khud se poochho, phir mom se, phir dad se (jis order mein listed hain), aur sirf unke dono ke baad grandma se poochho — kyunki grandma sabki parent hai, isliye usse tab tak wait karna hoga jab tak uske saare bachche se poochha na jaaye. C3 bas woh careful rule hai jo yeh "pehle kisse poochho" ki line banata hai taaki kisi ke bhi parent se unse pehle kabhi na poochha jaaye, aur grandma line mein sirf ek baar khadi ho.

Connections

Method Resolution Order
super() and cooperative inheritance
The Diamond Problem
Single inheritance
Mixins
Composition vs Inheritance
Topological sort (C3 ek constrained topological ordering hai)