Worked examples — Multiple inheritance — Python's C3 linearization algorithm

---

The scenario matrix

Every possible C3 problem is really one of these shapes. The rest of the page fills in each cell.

#	Cell (the scenario)	What makes it special	Example
1	Single chain C(B), B(A)	degenerate: no merge conflict at all	Ex 1
2	Flat multi-parent D(B,C), no shared base	parents unrelated; order = written order	Ex 2
3	Classic diamond D(B,C), B(A), C(A)	shared grandparent must wait, appear once	Ex 3 (figure)
4	Order flip matters D(C,B) vs D(B,C)	swapping parents swaps the MRO	Ex 4
5	Deep / wide combo three levels + width	recursion goes several layers deep	Ex 5 (figure)
6	Mixin on the left C(Mixin, Base)	why mixins are written first	Ex 6
7	Inconsistent → TypeError conflicting orders	the machine legally refuses	Ex 7 (figure)
8	Explicit object class A(object)	zero/degenerate: same as class A	Ex 8
9	Real-world word problem GUI widgets	reading MRO to predict behaviour	Ex 9
10	Exam twist super() jumps sideways	MRO ≠ literal parent	Ex 10

---

Example 1 — Single chain (Cell 1)

Step 1 — base case. Why this step? C3 is recursive; every linearization bottoms out at object. $L[A]=[A,O]$

Step 2 — linearize B. Why this step? Apply the master formula $L[C]=C+\text{merge}(L[P_1],\dots ,[P_1,\dots ])$ with one parent. $L[B]=B+\text{merge}([A,O],[A])=[B,A,O]$ The merge is trivial: B isn't even in the lists; A is a good head (never in a tail), so it comes out, then O.

Step 3 — linearize C. Why this step? Same formula, parent is B. $L[C]=C+\text{merge}([B,A,O],[B])=[C,B,A,O]$

Verify: This is just Single inheritance — walk straight up the family line, nobody has to wait. The list is exactly the chain top-to-bottom reversed: $[C,B,A,O]$. ✅

Recall Why is single inheritance the degenerate case?

A degenerate case is one where the general machine has nothing to do ::: with only one parent per class there are no competing orders, so the merge never has to skip a head — the answer is always the straight chain.

---

Example 2 — Flat multi-parent, no shared base (Cell 2)

Step 1 — the parents. Why this step? We need $L[B]$ and $L[C]$ first. $L[B]=[B,O],L[C]=[C,O]$

Step 2 — merge for D. Why this step? The last argument is the parent list itself, $[B,C]$, which is what keeps written order. $L[D]=D+\text{merge}([B,O],[C,O],[B,C])$

Run it:

• Head B: in any tail? Tails are $[O]$, $[O]$, $[C]$. No → emit B. Lists → $[O],[C,O],[C]$.
• Head O (list 1): is O in a tail? Yes, tail of list 2 is $[O]$ → skip. Next list head C: in any tail? No → emit C. Lists → $[O],[O],[]$.
• Head O: good now → emit. Then done.

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

Verify: Because they share no base, B and C come out in exactly the written order, then the common object. Sanity: object still appears once, last. ✅

---

Example 3 — The classic diamond (Cell 3)

Step 1 — parents. Why this step? Recursion needs $L[B],L[C]$. $L[B]=[B,A,O],L[C]=[C,A,O]$

Step 2 — merge. Why this step? This is the whole point of C3 — resolving the two roads to A. $L[D]=D+\text{merge}([B,A,O],[C,A,O],[B,C])$

• B good → emit. → $[A,O],[C,A,O],[C]$
• A: in tail of list 2 (C,A,O) → skip. Next head C: good → emit. → $[A,O],[A,O],[]$
• A: now in no tail → emit. Then O.

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

Verify: Look at the figure — the amber A sits at the bottom, drawn once, and both roads through B and C are already placed before we reach it. This is the diamond problem solved: A after all its children, exactly one copy. ✅

---

Example 4 — Flipping the parent order (Cell 4)

Step 1 — same parent linearizations. Why this step? B and C don't change; only D's parent order does. $L[B]=[B,A,O],L[C]=[C,A,O]$

Step 2 — merge with swapped parent list. Why this step? The last argument becomes $[C,B]$, encoding the new written order. $L[D]=D+\text{merge}([C,A,O],[B,A,O],[C,B])$

• C good → emit. → $[A,O],[B,A,O],[B]$
• A: in tail of list 2 → skip. B good → emit. → $[A,O],[A,O],[]$
• A → emit, then O.

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

Verify: Yes — C and B swapped, everything else identical. This proves the local precedence guarantee: C3 always honours the order you wrote parents in. ✅

---

Example 5 — Deep and wide combined (Cell 5)

Step 1 — the leaves. Why this step? Build the simple ones first. $L[A]=[A,R,O],L[B]=[B,R,O],L[C]=[C,R,O](R=O_{root},O=\text{object})$

Step 2 — the middle layer. Why this step? We need $L[K1],L[K2]$ before $Z$. $L[K1]=K1+\text{merge}([A,R,O],[B,R,O],[A,B])=[K1,A,B,R,O]$ $L[K2]=K2+\text{merge}([B,R,O],[C,R,O],[B,C])=[K2,B,C,R,O]$

Step 3 — the top merge. Why this step? Now the master formula for Z. $L[Z]=Z+\text{merge}([K1,A,B,R,O],[K2,B,C,R,O],[K1,K2])$

• K1 good → emit. → $[A,B,R,O],[K2,B,C,R,O],[K2]$
• A good (not in any tail) → emit. → $[B,R,O],[K2,B,C,R,O],[K2]$
• B: in tail of list 2 (K2,B,C,R,O) → skip. K2 good → emit. → $[B,R,O],[B,C,R,O],[]$
• B: now head of both lists, in no tail → emit. → $[R,O],[C,R,O],[]$
• R: in tail of list 2 → skip. C good → emit. → $[R,O],[R,O],[]$
• R → emit, then O.

Result: $L[Z]=[Z,K1,A,K2,B,C,R,O]$.

Verify: B (shared by both middle classes) appears once, and only after both K1 and K2 are placed — exactly as a constrained topological order demands. O_root and object each appear once, at the very end. ✅

---

Example 6 — Mixin on the left (Cell 6)

Step 1 — parents. Why this step? Both are simple. $L[\text{LoggerMixin}]=[\text{LoggerMixin},O],L[\text{Base}]=[\text{Base},O]$

Step 2 — merge. Why this step? Written order is (LoggerMixin, Base). $L[\text{Service}]=\text{Service}+\text{merge}([LM,O],[Base,O],[LM,Base])$

• LM good → emit. → $[O],[Base,O],[Base]$
• O: in tail of list 2 → skip. Base good → emit. Then O.

Result: $L[\text{Service}]=[\text{Service},\text{LoggerMixin},\text{Base},O]$.

Verify: The mixin lands before Base, so Service().save() finds the logging version first — which then calls super().save() to reach Base. That is the whole reason mixins go on the left. ✅

---

Example 7 — The machine legally refuses (Cell 7)

Step 1 — the two conflicting parents. Why this step? Their internal orders are the source of the clash. $L[A]=[A,X,Y,O],L[B]=[B,Y,X,O]$

Step 2 — try the merge. Why this step? We must show exactly where it dead-ends. $L[C]=C+\text{merge}([A,X,Y,O],[B,Y,X,O],[A,B])$

• A good → emit. → $[X,Y,O],[B,Y,X,O],[B]$
• X: in tail of list 2 (B,Y,X,O) → skip. B good → emit. → $[X,Y,O],[Y,X,O],[]$
• X: in tail of list 2 (Y,X,O) → skip. Next head Y: in tail of list 1 (X,Y,O) → skip. No good head remains.

Result: Python raises TypeError: Cannot create a consistent method resolution order (MRO) for bases X, Y.

Verify: In the figure the amber arrows point in opposite directions — one demands X→Y, the other Y→X. No line can satisfy both, so C3 correctly refuses rather than silently guessing. This is the machine being honest, not broken. ✅

---

Example 8 — Explicit object (Cell 8, degenerate)

Step 1 — reason it out. Why this step? Every class in Python 3 already inherits from object implicitly. $L[\text{object}]=[O](\text{the base case})$ $L[A]=A+\text{merge}([O],[O])=[A,O]$

Writing class A gives the identical calculation — the implicit parent is object either way.

Verify: Both spellings yield $[A,O]$. The explicit object is a no-op in Python 3; it only mattered in Python 2's old-vs-new style classes. Degenerate input, same output. ✅

---

Example 9 — Real-world word problem (Cell 9)

Step 1 — leaves. Why this step? Both mid-classes share Widget. $L[\text{Clickable}]=[\text{Clickable},\text{Widget},O],L[\text{Draggable}]=[\text{Draggable},\text{Widget},O]$

Step 2 — merge for Button. Why this step? Diamond shape again, base = Widget. $L[\text{Button}]=\text{Button}+\text{merge}([Cl,W,O],[Dr,W,O],[Cl,Dr])$

• Cl good → emit. W: in tail of list 2 → skip. Dr good → emit. W now good → emit. O → emit.

Result: $L[\text{Button}]=[\text{Button},\text{Clickable},\text{Draggable},\text{Widget},O]$.

Verify: Python searches Button → Clickable → Draggable → Widget. Clickable has no on_event, so the search continues to Draggable, finds it there, and runs it. Prediction confirmed: yes, it is found, at the Draggable step. ✅

---

Example 10 — Exam twist: super() steps sideways (Cell 10)

Step 1 — recall the MRO of the actual object. Why this step? super() follows the MRO of the instance's class, not B's literal parent. $L[D]=[D,B,C,A,O](\text{from Ex 3})$

Step 2 — find B's successor in that list. Why this step? super() inside B means "the class after B in this MRO". The element after B in $[D,B,C,A,O]$ is C.

Result: super().greet() inside B jumps to C, not A.

Verify: This is the classic exam trap. Literal parent of B is A, but for a D instance the MRO puts C between them, so cooperative super() visits C first. Sanity check: this is precisely why every class in a cooperative hierarchy calls super() — so each class in the MRO gets its turn exactly once. ✅

---

Recall Quick self-test across the matrix

MRO of D(C,B) with B(A), C(A) ::: [D, C, B, A, object] Does writing class A(object) change the MRO vs class A? ::: No — identical [A, object] in Python 3. In Button(Clickable, Draggable), both Widget-based, where is Widget in the MRO? ::: Last before object, appearing once. Inside B of D(B,C), super() reaches which class for a D instance? ::: C, the MRO successor of B — not the literal parent A. What halts the merge in the inconsistent C(A,B) case? ::: No good head remains — X and Y each sit in the other list's tail.

---

Connections

• Parent topic
• Method Resolution Order
• The Diamond Problem
• Single inheritance
• Mixins
• super() and cooperative inheritance
• Composition vs Inheritance
• Topological sort