Gerbil Scheme

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.

The C4 Algorithm

Like C3 of which it is a successor, the C4 linearization algorithm respects the following four constraints. C3 was actually named after the first three constraints, omitting to count the 4th, yet implicitly respecting it:

  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. Direct Superclass Ordering (introduced by New Flavors): The list of a class's direct super classes, 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).

  3. Monotonicity (introduced by Ducournau et al. 1992 as "monotonic linearization"): A class's precedence list is included as a sublist (seen as an order, same as above) in the precedence list of each of its subclasses.

  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).

Additionally, C4 extends C3 with support for structs that require single-inheritance, by adding the following constraint:

  1. Struct Suffix (first implicitly recognized by Scala 3?): A struct's precedence list is a suffix of the precedence list of its subclasses.

Finally, C4 uses the following heuristic, same as C3, to deterministically compute the precedence list in cases that multiple solutions satisfy the above constraints:

  1. Depth-First Traversal: When the above constraints do not suffice to uniquely determine the next element in the precedence list, a choice is made between multiple candidates, and, given Shape Determinism and the other constraints above, this choice must be based on a traversal of the list of precedence lists from direct superclasses. As per the C3 algorithm, we build precedence list head-first with a depth-first traversal; this is equivalent to building the precedence list tail-first with the reverse traversal. A different traversal for instance would be depth-first, but there are good reasons to pick depth-first, notably in perserving as much as possible the tail of the precedence list, thereby maximizing sharing of partial semantics in methods and slots.

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 5th constraint has been adopted by Scala 3 (that fails to otherwise use C3 or offer its consistency). But as far as we know, as of May 2025, Gerbil Scheme 0.18.2 is the only language adopting both.

PS: Common Lisp, and the earlier tradition of multiple inheritance, that we follow here, all the way back to Flavors, calls "classes" the things with multiple inheritance and "structs" the things with single inheritance only. Smalltalk and after it Java, and the earlier and historically more prevalent tradition of single inheritance, calls "classes" the things with single inheritance and "traits" the things with multiple inheritance (after Mesa). C++ only has multiple inheritance (though duplicating non-virtual superclasses behave more like mixin inheritance), and calls "struct" a class where all "members" are public by default. Wonderful nomenclature, right? We here stick to the Common Lisp namings.

Procedures

c4-linearize

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

Compute the class precedence list of a class, given its super-classes 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 superclass that is a struct, or #f if none is found.

The function abstracts over the type X of 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 class descriptor for the class whose precedence list is being computed.

  • supers is a list of X, class descriptors for direct super-classes of the one being defined. In typical uses, supers will be (direct-supers x) where x is the class for which the precedence list is being computed.

  • get-precedence-list: specifies a procedure that, given a class descriptor c of type X for a direct super-class of the class at stake, returns the precedence list of c, from most-specific to least-specific, with c included at the start.

  • struct: specifies a predicate that, given a class descriptor c of type X (as above), returns true if the class 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 class descriptors of type X for equality.

  • get-name: (optional, defaults to the identity function) specifies what function to use to print the name of a class descriptor 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 class first to least-specific class last (with the base class 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.

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 infamous "billion dollar mistake", NULL.)

[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".)

[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 (Describes frames, a knowledge representation paradigm, where an "object" or "prototype" has a "description" made of multiple "descriptors" for as many "perspectives".)

[Kahn 1976] Kenneth Michael Kahn, "An Actor-Based Computer Animation Language", 1976 (Takes from AI knowledge representation research the concepts of prototype object-orientation and multiple inheritance, and frames them as a programming language.)

[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.)

[Cannon 1979] Howard Cannon, "Flavors: A non-hierarchical approach to object-oriented programming", 1979 https://www.softwarepreservation.org/projects/LISP/MIT/nnnfla1-20040122.pdf (Documents a message-passing class-based object system with multiple inheritance, linearization, mixins, method combinations.)

[Curry 1982] Gael Curry, Larry Baer, Daniel Lipkie, and Bruce Lee, "Traits: An approach to multiple-inheritance subclassing", 1982 (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.)

[Bobrow 1986] Daniel G. Bobrow, Kenneth Kahn, Gregor Kiczales, Larry Masinter, Mark Stefyk, and Frank Zdybel "CommonLoops: Merging Lisp and Object-Oriented Programming", 1986 (Object system for Common lisp, introduces multimethods and direct superclass ordering.)

[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.)

[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 (Describes CLOS.)

[Bobrow 1991] Daniel Bobrow, Gregor Kiczales, and Jim des Rivières, "The Art of the Meta-Object Protocol", 1991 (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 (Discusses the constraints required of a linearization algorithm.)

[Chambers 1992] Craig Chambers "Object-oriented multi-methods in Cecil", 1992 (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 (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 (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 (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://github.com/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://github.com/mighty-gerbils/gerbil/blob/master/src/gerbil/runtime/c3.ss (Implements the C3 linearization algorithm, later updated to C4.)