Exercises — Multiple inheritance — Python's C3 linearization algorithm

$L[C]=C+\text{merge}(L[P_1],\dots ,L[P_n],[P_1,\dots ,P_n])$, base case $L[\text{object}]=[\text{object}]$. Merge: take the head of the first list; it is a good head if it appears in no tail (any position after position 0) of any list. If good, emit it and delete it everywhere; if not, try the head of the next list. If no good head exists → TypeError. Throughout, $O$ means object.

WHAT: Apply the base rule. A has no explicit parents, so its only parent is object. $L[A]=A+\text{merge}(L[O],[O])=A+\text{merge}([O],[O])=[A,O].$ Answer: [A, object].

WHAT: One direct parent → Single inheritance. C3 on a single chain just stacks the parent's MRO under the child. $L[B]=B+\text{merge}(L[A],[A])=B+\text{merge}([A,O],[A])=[B,A,O].$ Answer: single inheritance; [B, A, object].

WHAT: Check whether B appears in the tail of any list. Tails: [A,O], [A,O], [C]. B is in none of them. Answer: Yes — B is a good head, so it is emitted first.

Precompute: $L[B]=[B,A,O]$, $L[C]=[C,A,O]$. $L[D]=D+\text{merge}([B,A,O],[C,A,O],[B,C]).$

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

Precompute: $L[A]=[A,O]$, $L[B]=[B,A,O]$, $L[C]=[C,B,A,O]$, $L[D]=[D,A,O]$. $L[E]=E+\text{merge}([C,B,A,O],[D,A,O],[C,D]).$

Answer: [E, C, B, A, D, O]... wait — recheck iter 3: after emitting B, D becomes a good head before A because A is still blocked. So the order is E, C, B, D, A, O. Let me re-lay iter 3 cleanly: lists are [A,O] [D,A,O] [D]. Head of list 1 is A, blocked (in tail of list 2). Head of list 2 is D, in no tail → emit D. Lists become [A,O] [A,O] []. Then A, then O. Answer: [E, C, B, D, A, object].

Each of A,B,C is [X,O]. $L[D]=D+\text{merge}([A,O],[B,O],[C,O],[A,B,C]).$ A not in any tail → emit. Then B (tail-free) → emit. Then C → emit. Then O. Answer: [D, A, B, C, object] — the written parent order is preserved, and O sinks to the bottom.

$L[A]=[A,X,Y,O]$, $L[B]=[B,Y,X,O]$. $L[C]=C+\text{merge}([A,X,Y,O],[B,Y,X,O],[A,B]).$ Emit A (tail-free). Lists: [X,Y,O] [B,Y,X,O] [B]. Try X: in tail of list 2 → skip. Try B: tail-free → emit. Lists: [X,Y,O] [Y,X,O] []. Try X: in tail of list 2 (Y,X,O) → skip. Try Y: in tail of list 1 (X,Y,O) → skip. No good head. Answer: No valid MRO. Contradiction: A demands X before Y; B demands Y before X. Python raises TypeError: Cannot create a consistent method resolution order (MRO).

WHAT: super() walks the MRO of the instance's type, not B's literal parent. In L[D], the successor of B is C. Answer: C.m runs — even though B's written parent is A. This is the cooperative behaviour covered in super() and cooperative inheritance.

WHAT: Monotonicity says relative order in a parent's MRO is never reversed in a subclass. Since B precedes A in $L[B]$, no subclass may put A first. Answer: Impossible — and a child always precedes its parents anyway, so B before A is doubly guaranteed.

Design: class Base, class M1, class M2, class E(M1, M2, Base). Each mixin/base is [X,O]. $L[E]=E+\text{merge}([M1,O],[M2,O],[Base,O],[M1,M2,Base]).$ Emit M1, then M2, then Base, then O. Answer: class E(M1, M2, Base): ... → [E, M1, M2, Base, object]. (List mixins before the concrete base so their overrides win — a standard Mixins pattern.)

Design: A; B(A), C(A), D(A); E(B, C), F(C, D); G(E, F). Precompute: B=[B,A,O], C=[C,A,O], D=[D,A,O], E=[E,B,C,A,O], F=[F,C,D,A,O]. $L[G]=G+\text{merge}([E,B,C,A,O],[F,C,D,A,O],[E,F]).$ Emit E → B → then C blocked (tail of list 2) so try list 2 head F → emit F → now C free → C → D → A → O. Answer: [G, E, F, B, C, D, A, object]. ✅ (Note F jumps ahead of B... let's confirm: after E, lists [B,C,A,O] [F,C,D,A,O] [F]; B tail-free → emit B; lists [C,A,O] [F,C,D,A,O] [F]; C blocked (tail of list 2) → try F, tail-free → emit F; then C, D, A, O. Order emitted: E,B,F,C,D,A. So the real MRO is [G, E, B, F, C, D, A, object].) Corrected answer: the design above yields [G, E, B, F, C, D, A, object]. To get B after F you would need F listed to force it — but C3 keeps B right after E here. Trust the merge, not the guess.

$L[D]=[D,B,C,A,O]$, $L[C]=[C,A,O]$. $L[E]=E+\text{merge}([D,B,C,A,O],[C,A,O],[D,C]).$ Emit D (tail-free). Lists: [B,C,A,O] [C,A,O] [C]. B tail-free → emit. Lists: [C,A,O] [C,A,O] [C]. C tail-free (its only tails are [A,O]) → emit. Then A, then O. Answer: [E, D, B, C, A, object]. Swap E(C, D): now the parent list is [C,D]. But $L[D]$ already places D before C (as D's own... actually D before C inside L[D]), while E(C,D) demands C before D. Conflict → TypeError. So order matters: E(D, C) works, E(C, D) fails.

Answer: (<class 'E'>, <class 'D'>, <class 'B'>, <class 'C'>, <class 'A'>, <class 'object'>) — i.e. [E, D, B, C, A, object], confirming Ex 5.1. This is a constrained Topological sort: every child precedes its parents, and no two ancestors' orders were reversed.