Skip to content

2.8 C3

Below is the documentation for module gerbil/runtime/c3 and the C4 linearization algorithm it implements, itself a slight extension of the well-known C3 linearization algorithm for multiple inheritance.

2.8.1 The C4 Algorithm

Like C3 of which it is a successor, the C4 linearization algorithm respects the following five constraints. C3 was actually named after constraints 5, 2, 3, omitting to count 1 and 4, yet implicitly respecting them:

  1. Linearization (introduced by Flavors): The precedence list returned is a linearization (total order extension) of the inheritance DAG (viewed as a partial order).

  2. Local Precedence (introduced by New Flavors 1986 as “local ordering of components”): The list of a specification’s parents, a.k.a. its local precedence list, is a sublist of its precedence list (seen as an order, i.e. all elements are present in the same order but not necessarily consecutively). C4 further extends this principle by supporting not just a total order among parents, but an arbitrary DAG for the local precedence order, as given by a list of totally ordered lists of parents. If these lists are all singletons, the parents are otherwise unordered, yet even then there order matters for the Extended Precedence below.

  3. Monotonicity (introduced by Ducournau et al. 1992 as “monotonic linearization”): A specification’s precedence list is included as a sublist (seen as an order, same as above) in the precedence list of each of its descendents.

  4. Shape Determinism (introduced by Ducournau et al. 1994 as “acceptability”): The precedence list must only depend on the shape of the inheritance graph (inheritance graphs isomorphic up to some renaming should yield identical precedence lists up to the very same renaming).

  5. Extended Precedence (introduced by Ducournau et al. 1992 as “extended order”): If a parent specification X is chosen before parent specification Y in the linearization, then every ancestor of X will also appear before Y and every ancestor of Y in the linearization, except where this contradicts one of the other constraints. This constraint forces the algorithm of iteratively picking among valid candidates for the next most specific ancestor according to a depth-first traversal as the priority order.

Additionally, C4 extends C3 with support for “suffix specifications” that provide all the performance benefits of single-inheritance, by adding the following constraint (wherein suffix specifications correspond to Gerbil “structs”):

  1. Suffix Property (first implicitly recognized by Ruby, and later by Scala 3): A suffix specification’s precedence list is a suffix of the precedence list of each of its descendents.

NB: C3 was adopted by many modern multiple inheritance object systems for its consistency properties: OpenDylan, Python 2.3, Raku, Parrot, Solidity, PGF/TikZ. Our 6th constraint has been adopted by Ruby and Scala 3, but they fail to otherwise use C3 or offer its consistency.

As far as we know, as of May 2025, Gerbil Scheme 0.18.2 is the only language respecting all these constraints. Also, as of 2026, Gerbil Scheme will be the only one that implements C3 (and C4) in O(dn) like simpler linearization algorithms, instead of O(d²n²) as in the original C3 paper and its common implementations (where d is the number of parents specified, n the total number of ancestors).

PS: Common Lisp, and the earlier Lisp tradition of multiple inheritance, that we follow here, all the way back to Flavors, calls “classes” the entities with multiple inheritance and “structs” the entities with single inheritance only. Smalltalk and after it Java and Scala, and the earlier and historically more prevalent tradition of single inheritance, calls “classes” the entities with single inheritance and “traits” the entities with multiple inheritance (after Mesa); as for Ruby, it calls them respectively “classes” and “modules”. C++ only has its own limited variant of “Multiple Inheritance” (though duplicating non-virtual superclasses behave more like mixin inheritance), and calls “struct” a class where all “members” are public by default.

To avoid all these clashes, we call “specification” a class or prototype or entity subject to inheritance, “target” the entity being specified, and “suffix” a specification that has the suffix property, in which case we distinguish a “suffix specification” from a “suffix precedence list”.

PPS: Maintaining the consistency requirements of C3 at scale and over time can be difficult. The authors of Sagemath show how that can be automated to a point in [Hivert 2024], with an instrumentation of C3 that outputs the minimal local precedence declarations that will achieve a desired global ordering of classes.

2.8.2 Procedures

c4-linearize

(c4-linearize rhead parents
  get-precedence-list: get-precedence-list
  struct: struct?
  [eq: eq?]
  [get-name: get-name]) -> (values list (or suffix-specification #f))

Compute the precedence list of a specification, given its parents and additional information. This function takes two positional arguments, two compulsory keyword arguments get-precedence-list: and struct:, and two optional keyword arguments eq: (defaults to eq?) and get-name (defaults to the identity function). It returns two values, the precedence list from most-specific to least-specific, and the most specific ancestor that is a struct, or #f if none is found.

The function abstracts over the type X of specifications (typically class descriptors) used for input and output, that it only access via the values and functions passed as arguments:

  • rhead is a list of X, the reverse of a prefix to the precedence list. Its value will be prepended to the list as computed. In typical uses, rhead is either an empty list, or a singleton list containing the specification whose precedence list is being computed. A list of length more than 1 is frowned upon as a future variant of this function might not reverse the prefix anymore.

  • parents is a list of X, specifications for parents of the one being defined. In typical uses, parents will be (direct-supers x) where x is the specification whose precedence list is being computed.

  • get-precedence-list: specifies a procedure that, given a specification x of type X for a parent of the specification at stake, returns the precedence list of x, from most-specific to least-specific, with x included at the start.

  • struct: specifies a predicate that, given a specification x of type X (as above), returns true if the specification is a “struct”, subject to the suffix constraint (see section with that name above).

  • eq: (optional, defaults to eq?) specifies what predicate to use to compare specifications of type X for equality.

  • get-name: (optional, defaults to the identity function) specifies what function to use to print the name of a specification of type X in case an inheritance inconsistency is detected, and an error message must be printed.

The precedence lists involved are ordered from most-specific specification first to least-specific specification last (with any base specification at the end).

An error is raised if there is an inconsistency in the inheritance DAG such that no linearization exists that satisfies the four constraints.

NB: In the near future, the function c4-linearize* below may be renamed to c4-linearize and replace this one.

c4-linearize*

(c4-linearize* head parents
  get-precedence-list: get-precedence-list
  suffix: suffix?
  [eq: eq?]
  [get-name: get-name]) -> (values list (or suffix-specification #f))

Generalizes the previous interface, with the following updates:

  • The head is not reversed anymore (which shouldn’t change much when it’s usually empty or a singleton).
  • The parents are now a list of lists, rather than a single list; if you have a single list, wrap it in a singleton list.
  • The keyword argument struct: has been renamed suffix:.

2.8.3 Bibliography

[Hoare 1965] C. A. R. Hoare, “Record Handling”, 1965, http://archive.computerhistory.org/resources/text/Knuth_Don_X4100/PDF_index/k-9-pdf/k-9-u2293-Record-Handling-Hoare.pdf (Introduces the concept of class, though without an implementation thereof. Also introduces the confusion between subtyping and subclassing, and the infamous “billion dollar mistake”, NULL.)

[Dahl 1966] Ole-Johan Dahl and Kristen Nygaard “Class and subclass declarations”, 1967, https://www.ub.uio.no/fag/naturvitenskap-teknologi/informatikk/faglig/dns/dokumenter/classandsubclass1967.pdf (First implementation of classes, has “prefix classes”, and their “subclasses”, a “prefix sequence” for the ancestry, the keyword “this”, “objects” and their “attributes”, and a “concatenation” based semantics for single inheritance (neither the word “inheritance” though, nor the kind of “subclass is in charge” semantics that we love and appreciate in OO).

[Winograd 1975] Terry Winograd, “Frame Representations and the Declarative/Procedural Controversy”, 1975 https://hci.stanford.edu/winograd/papers/FrameRep.pdf https://api.pageplace.de/preview/DT0400.9781483299150_A23889670/preview-9781483299150_A23889670.pdf (Introduces the term “inheritance of properties” in the context of knowledge representation using “frames”. But it’s still more descriptive than definitional.)

[Bobrow 1976] Daniel G. Bobrow and Terry Winograd, “An Overview of KRL, A Knowledge Representation Language”, 1976 https://apps.dtic.mil/sti/tr/pdf/ADA042508.pdf (The very first paper that uses the words “object-oriented”, “inheritance” and “prototype” in their modern meaning, though not the first for “class”, see Simula above. Describes KRL, a frame-based Knowledge Representation Language, where an “object” or “prototype” has a “description” made of multiple “descriptors” for as many “perspectives”. Its “inheritance” is multiple inheritance.)

[Kahn 1976] Kenneth Michael Kahn, “An Actor-Based Computer Animation Language”, 1976 https://dspace.mit.edu/handle/1721.1/41950 (Inspired by Actors, Smalltalk, KRL, one of the very first OO programming language, later called Director, with prototypes and single inheritance, to model animations.)

[Borning 1977] Alan Hamilton Borning, “ThingLab — an Object-Oriented System for Building Simulations using Constraints”, 1977, https://www.ijcai.org/Proceedings/77-1/Papers/085.pdf (Introduces a prototype-based object system with multiple inheritance on top of Smalltalk 1976, though it’s the “conflict” kind where methods from multiple ancestors clash.)

[Cannon 1979] Howard Cannon, “Flavors: A non-hierarchical approach to object-oriented programming”, 1979 https://www.softwarepreservation.org/projects/LISP/MIT/nnnfla1-20040122.pdf (Watershed paper for multiple inheritance, replacing conflict between methods with cooperation. Documents a message-passing class-based object system with multiple inheritance, linearization, mixins, and method combinations inspired by Teitelman’s ADVISE. Not well-known outside Lisp circles at the time. Updated and published a bit more widely in 1982. Flavors was documented in the Lisp Machine Manual, but without the rationales from this paper. Republished 2004.)

[Curry 1982] Gael Curry, Larry Baer, Daniel Lipkie, and Bruce Lee, “Traits: An approach to multiple-inheritance subclassing”, 1982 https://doi.org/10.1145/966873.806468 (Describes the multiple inheritance with Traits added in 1979 to the Mesa programming language (started early 1978 with single inheritance), in which WS, the workstation software of the Xerox Star 8010, was written. Unhappily it is the flavorless “conflict” kind of multiple inheritance.)

[Moon 1986] David Moon “Object-Oriented Programming with Flavors”, 1986 https://dl.acm.org/doi/10.1145/960112.28698 (Introduces Flavors to a wider public than Cannon, with cleanups. Introduces the local precedence order.)

[Bobrow 1986] Daniel G. Bobrow, Kenneth Kahn, Gregor Kiczales, Larry Masinter, Mark Stefyk, and Frank Zdybel “CommonLoops: Merging Lisp and Object-Oriented Programming”, 1986 https://dl.acm.org/doi/10.1145/960112.28700 (Object system for Common lisp, introduces multimethods, and the ability to explicitly call super methods in the context of multiple inheritance. Has local precedence order.)

[Bobrow1988] Daniel G. Bobrow, Linda D. DeMichiel, Richard P. Gabriel, Sonya E. Keene, Gregor Kiczales, and David A. Moon “Common Lisp Object Specification X3J13”, 1988 https://www.researchgate.net/publication/220178512_Common_Lisp_Object_System_Specification_X2JI3_Document_88-002R (Chapter of the Common Lisp specification then being standardized (finalized in 1994). The introduction is very short, and most of the paper is a description of the API. For a presentation of the concepts, see the Keene book, but the API was already mature in 1988.)

[Bracha 1990] Gilad Bracha, and William Cook, “Mixin-Based Inheritance”, 1990, https://www.semanticscholar.org/paper/Mixin-based-inheritance-Bracha-Cook/cbc4f2d93bb62d1c287f4fe458de6ac416379282 (Introduces mixin inheritance as a way to formalize the semantics of inheritance. Crucially reinterpreting equations introduced by Cook in his thesis the previous year, to make them valid beyond single inheritance.)

[Steele 1990] Guy Steele, “Common Lisp: The Language, 2nd edition”, 1990 http://www.cs.cmu.edu/afs/cs.cmu.edu/project/ai-repository/ai/html/cltl/cltl2.html (Includes a version of CLOS, which wasn’t present in the 1st edition.)

[Gabriel 1991] Richard P Gabriel, Jon L White, and Daniel G Bobrow, “CLOS: Integrating object-oriented and functional programming”, 1991 https://dreamsongs.com/Files/clos-cacm.pdf (Describes CLOS.)

[Bobrow 1991] Daniel Bobrow, Gregor Kiczales, and Jim des Rivières, “The Art of the Meta-Object Protocol”, 1991 https://direct.mit.edu/books/book/2607/The-Art-of-the-Metaobject-Protocol (Meta-Object Protocol for CLOS. Not all of it part of the CL standard.)

[Ducournau 1992] Roland Ducournau, Michel Habib, Marianne Huchard, and Marie-Laure Mugnier, “Monotonic conflict resolution mechanisms for inheritance”, 1992 https://www.researchgate.net/publication/234827636_Monotonic_conflict_resolution_mechanisms_for_inheritance (Discusses the constraints required of a linearization algorithm.)

[Chambers 1992] Craig Chambers “Object-oriented multi-methods in Cecil”, 1992 http://www.laputan.org/pub/papers/cecil-ecoop-92.pdf (Multimethods in a Prototype Oriented Object language.)

[Ducournau 1994] Roland Ducournau, Michel Habib, Marianne Huchard, and Marie-Laure Mugnier, “Proposal for a monotonic multiple inheritance linearization”, 1994 https://doi.org/10.1145/191080.191110 (Further discusses the constraints required of a linearization algorithm, with a solution.)

[Kay 1996] Alan Kay, “The Early History of Smalltalk”, 1996 https://dl.acm.org/doi/pdf/10.1145/234286.1057828 (Inheritance introduced in Smalltalk 1976 after inspiration from SIMULA 67, from Tesler, from Lieberman, and from Bobrow & Winograd’s KRL)

[Barrett 1996] Kim Barrett, Bob Cassels, Paul Haahr, David A. Moon, Keith Playford and P. Tucker Withington, “A Monotonic Superclass Linearization for Dylan”, 1996 https://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.19.3910 (Introduces the C3 algorithm.)

[Flatt 1998] Matthew Flatt, Shriram Krishnamurthi, and Matthias Felleisen, “Classes and mixins”, 1998 https://doi.org/10.1145/268946.268961 (Uses single-inheritance classes, but they are first-class, so uses mixins to generate them, except it’s proposed in the context of a Java dialect with Scheme only barely mentioned.)

[Odersky 2005] Martin Odersky, and Matthias Zenger “Scalable Component Abstractions”, 2005 http://lampwww.epfl.ch/~odersky/papers/ScalableComponent.pdf (Multiple inheritance as an extension to Java single-inheritance. Programmers must manually include the most specific struct if any as explicit first class to extend.)

[Flatt 2006] Matthew Flatt, Robert Bruce Findler, and Matthias Felleisen, “Scheme with classes, mixins, and traits”, 2006 https://www2.ccs.neu.edu/racket/pubs/asplas06-fff.pdf (Extension of 1998 paper.)

[Cunningham 2014] Dave Cunningham, “Jsonnet”, 2014, https://jsonnet.org (A simple pure functional lazy dynamic language with builtin prototype object system using mixin inheritance.)

[Simons 2015] Peter Simons, “Nixpkgs fixed-points library”, 2015, https://github.com/NixOS/nixpkgs/blob/master/lib/fixed-points.nix (A prototype object system using mixin inheritance in two short functions on top of a simple pure functional lazy dynamic language.)

[Rideau 2020] François-René Rideau, “gerbil-poo”, 2020, https://git.cons.io/mighty-gerbils/gerbil-poo (Implements a prototype-based object system with multiple inheritance on top of Gerbil Scheme)

[Wiki 2021] Wikipedia, “C3 linearization”, 2021 https://en.wikipedia.org/wiki/C3_linearization (Describes C3 linearization.)

[Rideau 2021] François-René Rideau, Alex Knauth, and Nada Amin, “Prototypes: Object-Orientation, Functionally”, 2021 https://github.com/metareflection/poof (Explains how to implement prototype-based OO with mixin inheritance in two lines of code, and clarifies the relationship between single and mixin and multiple inheritance, between prototypes and classes, and more.)

[Rideau 2024] François-René Rideau, “gerbil/src/gerbil/runtime/c3.ss”, 2024, https://git.cons.io/mighty-gerbils/gerbil/blob/master/src/gerbil/runtime/c3.ss (Implements the C3 linearization algorithm, later updated to C4.)

[Rideau 2026] François-René Rideau, “Lambda, the Ultimate Object — Object Orientation Elucidated” http://fare.tunes.org/files/cs/poof/ltuo.html (Eludicates the theory of OO, and includes an explanation of C4 in its chapter 7.)

[Hivert 2024] Florent Hivert and Nicolas M. Thiéry, “Controlling the C3 Super Class Linearization Algorithm for Large Hierarchies of Classes” https://arxiv.org/abs/2401.12740 (The authors describe how they have automated the maintenance of C3 consistency properties for the SageMath abstract algebra system since 2013, their system being large enough that manual consistency maintenance doesn’t scale.)