Lambda: the Ultimate Object
Object Orientation Elucidated
🔗

1.1.1 Curiosity about OO, Familiarity with FP🔗

What even are objects? What aren’t? What is OO? What isn’t? What is it for? What is a paradigm to begin with? How do I use OO to write programs? How do I make sense of existing OO programs? How may I best think about OO programs, to design them? How may I best reason about them, to debug them? What are variants of OO? How do I compare them? How can I build OO if I don’t have it yet (or not a good variant of it)? And why are so many people so into OO, and so many others so against it? Which of their arguments is right or wrong when? Am I missing something by not using OO, or by using it?

These are the kinds of questions this book will help you answer. To get there, I will have to introduce many concepts. Don’t worry: when others may relish in complexity, I instead aspire to simplicity. You will learn some new words and new ideas. But if you practice programming, and think about your practice, then you are in my target audience; and you will find it will be easier to program with the right ideas than with the wrong ones. And the Internet is certainly full of wrong and sometimes toxic ideas, about OO as about anything.

To answer those questions, I will assume from my readers a passing familiarity with Functional Programming (FP). You don’t have to be an expert at FP; you just need basic knowledge about how to read and write “anonymous higher-order” functions in your favorite programming language.22Anonymous functions are just functions that do not need to have a name. Higher-Order means that they can take other functions as arguments, and return functions as results, both old and new (by e.g. applying or composing previous functions). These days, in 2026, most mainstream languages have such functions, quite unlike 20 years ago. It is also possible to emulate such functions in languages that do not have them; that is a topic I will not cover, but I can refer you to classic books about programming languages that do it well  (Abelson and Sussman 1996; Friedman et al. 2008; Khrisnamurthi 2008; Pierce 2002; Queinnec 1996). I do love these books, however I find their treatment of OO lacking—otherwise I wouldn’t be writing the present book.

1.1.2 Decades too late, but still decades ahead🔗

Conceived around 1967 with Dahl and Nygaard’s Simula and Alan Kay’s musings, OO was actually born in 1976 when these two collided with each other and with Bobrow’s Lisp AI work, resulting in Smalltalk-76 and KRL-0. OO took off from there, at first reserved to the happy few who could use the most high-end systems from Xerox, BBN or MIT. OO became popular among researchers in the 1980s, and at some point was the Next Big Thing™. In the 1990s, OO finally became available to every programmer, accompanied by endless industry hype to promote it. By the mid 2000s it had become the normal paradigm to program in. Then, at some point in the mid 2010s it started to become as boring as ubiquitous. Now in the mid 2020s it is on its way to become forgotten, at least among the Cool Kids. Yet, one thing OO never was, was understood. Until now.

As a USENET wiseman wrote: “Every technique is first developed, then used, important, obsolete, normalized, and finally understood.” This book then is here to bring the final nail on the coffin of OO: understanding it. Too bad no one reads books anymore, except AIs. If that book, and most importantly its understanding, had come a few decades earlier, it could have saved a lot of people a lot of trouble. OO sure baffled me for a long time, and many around me. Now that I am not baffled anymore, I can bring you all my explanations—but long after the battle.

It would be nice to hear a few of my old colleagues tell me: “so that is what OO was about all along!” But I have little hope of convincing many in the old generations of the benefits of OO done right (yes, I am one of those Lispers bragging about how their 1988 OO system is still decades ahead of yours). And even if I did, they will be retiring soon. However, a new generation of programmers is born every year, and it is always time to inspire and educate the new generation, that they do not fall as low as their predecessors, or lower. And even if AIs take over programming, they too will need education.

1.1.3 Towards a Rebirth of OO🔗

When I mention OO becoming boring, then forgotten, or talk of nailing its coffin, I’m not celebrating OO’s decline. I’m lamenting that a bad version of OO became popular, then faded. Meanwhile, there’s little interest or funding in either industry or academia to further improvement to OO—a topic wrongly considered already understood.

These days, bright programmers gravitate toward Functional Programming (FP), a paradigm unjustly neglected in the industry during OO’s heyday. As distributed systems became widespread, FP proved more practical than imperative programming for managing state and avoiding the problematic interactions that make concurrent programs slow and buggy. Because OO had been sold in a package deal with imperative programming, it fell out of fashion alongside it.

Grumpy old Lispers like me yell at the clouds that there was never an opposition between OO and FP—that we Lispers have been enjoying both together since the 1970s, and that OO can be so much more than you “blub” programmers can even imagine.33Blub is how Lispers disparagingly call less expressive languages, after Graham (2001a). Graham notably wrote two books on Lisp, with interesting chapters on OO  (Graham 1994, 1995). He is however rightfully skeptical of the overuse of OO in corporate software  (Graham 2001b).

My hope—my faith, even, despite available evidence—is that a better OO can and will rise from the dead: Simpler than what was once popular. Unbundled from imperative programming. More powerful. With the advanced features of Lisp OO at long last adopted by the mainstream.

But I have to admit my defeat so far: I have yet to build a system to my liking that would attract a critical mass of adopters to become self-sustaining. And so, like all researchers who title their papers “Towards a …” when they fail to achieve their goals, I am switching to plan B: trying to convince others that there’s gold in them thar hills, so they will go dig it—because I can’t dig it all by myself. In writing this book, I am sharing the treasure map with you.

Exercise 1.1 (Easy) Rate from 0-10 (a) how well you understand OO, and (b) how well you understand FP. You can redo the rating after reading this book (and reflect on your earlier opinions), to see if it improved.

Exercise 1.2 (Medium) In a paragraph, write what you expect from reading this book. You can later use this paragraph to decide which sections to skim and which to focus on. But also after you read the book, to decide whether you were satisfied, and whether you were surprised.

Exercise 1.3 (Hard) In one sentence to one page maximum, draft what you think is the essence of OO, as if you had to explain it to a junior programmer.

Exercise 1.4 (Research) Write your own book about OO. Show me how it’s done.

1.2.1 Proximate Cause🔗

So I tried to get the Good News out, by getting a paper published. And I did get a paper published eventually  (Rideau et al. 2021), but only at the Scheme Workshop, a small venue of sympathetic Lispers, who already understood half of it and did not need much effort to understand the rest, but who already had plenty of good object systems to play with. Meanwhile, my repeated attempts at publishing in more mainstream Computer Science conferences or journals were met with incomprehension—also with great technical feedback, of course, that helped me learn and improve a lot, and for which I am most grateful; but fundamentally, with a deep misunderstanding about what I was even talking about. As Gabriel (2012) would say, my reviewers were trying to evaluate my work while making sense of it from an Incommensurable Paradigm.

Certainly, I could try to explain myself, to translate between their language and mine; spend time explaining the denotations and connotations of my words as I was using them, and defusing those that may mistakenly be heard by various readers from different communities; tell my readers to put aside the concepts they think they know, and somehow teach them the concepts I am putting behind the words, so they understand. But that takes a lot of time and space. For me. And for my readers. Resources that we both lack, especially scientific publications limited to 12-25 pages, depending on the venue.44Even a journal, with articles sometimes up to 70 pages, would require splitting the content of this book into four parts; maybe more, because each part would have to spend a good chunk of its page limit to summarize enough of what comes before so that the current part is understandable, and enough of what comes after so that it doesn’t appear pointless or petty. This is much more effort than just writing a book, an already costly and time-consuming endeavor. Splitting the same content over a dozen or more 25-page papers would be even more work. And so, as Pascal wrote about one of his letters: Je n’ai fait celle-ci plus longue que parce que je n’ai pas eu le loisir de la faire plus courte. (I have made this longer than usual because I have not had time to make it shorter.)


That was barely enough to address actual misunderstandings experienced by previous reviewers, and make my claims clear—see how much that takes in What Object Orientation is not and What Object Orientation is — Informal Overview respectively—with no space left to properly explain and substantiate those claims. Attempts to compress that information into this kind of format would again lead to loss of clarity, and the inevitable misunderstanding by reviewers, and frankly, the readers they rightfully stand for.

Or, I could take the time and space to explain things right. But then, I’d have to abandon the hope of fitting in existing venues. I would have to write a book. This book.

1.2.2 Ultimate Cause🔗

I repeatedly develop theories too large to publish in parts because I tend to think in terms of big pictures—or what others call big pictures, for I am also an aphantasiac: one with no mind’s eye except when dreaming. A “bird”, I like to explain large-scale human behavior, or tie together seemingly disparate phenomena, by identifying common causal patterns that you can observe from “above”. Ideas that are hard to communicate to “frogs”, who don’t think at a high enough level of abstraction. And I suspect that even other “birds” who do think at a high enough level, sometimes higher, not being aphantasiac, are overwhelmed or distracted by their visual imagery, and miss structural patterns I perceive non-visually.

However in the case of this book on Object Orientation, there is the difference that I actually have three decades of practical as well as theoretical experience with OO. I studied the semantics of programming languages in college. I professionally wrote or maintained OO programs in Lisp, Python, Java, JavaScript, Jsonnet, Scala, C++. I kept writing papers about OO while working in the industry (Rideau 2012; Rideau et al. 2021). And for many years, I have been implementing OO, and maintaining two object systems for Gerbil Scheme (Rideau 2020; Vyzovitis 2016). OO is a topic both easier and more concrete, in general and for me in particular. A topic in which I have direct experience as a frog, and where I can stand as a bird on the shoulders of giants who already solved many of the foundational problems. On this mature topic, I am ready and capable, and can explain a complete Theory of OO that is also fully implemented and immediately usable.

Ultimately, then, OO is the topic where my bird’s view and frog’s experience meet, where I made worthy findings that won’t fit in a short publication, but that I can share in the form of a book.

Exercise 1.5 (Easy) Laugh at me. I am spending so much time being serious about a topic that is relatively silly to anyone else. I feel smug about my opinions, yet I mostly can’t get my message through.

Exercise 1.6 (Medium) Laugh at the reviewers, the other readers. Their preconceptions, their paradigms, wouldn’t let them understand what I wrote, even after reading it.

Exercise 1.7 (Medium) Laugh at other authors who wrote about OO. They like me spent lot of time serious about the topic (or pretending to be), yet failed to see the simple things I will explain.

Exercise 1.8 (Hard) Laugh at yourself. You care enough about this topic and my opinions to be reading this book. Congratulations. Yet your own preconceptions are clouding your judgement and you still won’t get it all.

Exercise 1.9 (Hard) Love the other authors who wrote about OO, the reviewers, the other readers, and maybe even me—and of course yourself. Beyond our differences, we all share an interest in this same topic. But we all have a limited ability to focus, with finite time and energy, necessary preconceptions, to care about whatever it is we each care about. Most everyone means well and does their best—and even the few who don’t could use a hug.

Exercise 1.10 (Research) Find out what topic or subtopic you really care about. Get to understand it better than most other people. Become even better at that topic than those who teach it. Write a book about it.

Exercise 1.11 (Research) Make the world a better place. The world can use your positive contributions. They need not be books, and need not be about OO.

1.3.1 A Theory of OO🔗

This characterization of OO should be retrospectively obvious to all familiar with OO. Yet remarkably, some programmers explicitly reject it, eminent professors even.55A notable dissident to this characterization is William Cook, a respected academic who made many key contributions to understanding the semantics of inheritance  (Bracha and Cook 1990; Cook and Palsberg 1989, 1994; Cook et al. 1989; Cook 1989) yet also argued that Inheritance was orthogonal to OO and that OO is about “classes” of “objects” that can only be accessed through “interfaces”  (Cook 2009, 2012; Cook 1991). However, coding against an SML module would count as OO by Cook’s criteria, and indeed Cook explicitly calls the untyped λ-calculus “the first object-oriented language”, while dismissing Smalltalk as not OO enough because its integers are not pure objects (Cook 2009). Cook’s definition, that embraces the modular aspect of OO while rejecting its extensible or dynamic aspect, runs contrary to common practice. It brings no light on any of the languages commonly considered OO yet derided by Cook as not being OO enough, no light on any of the Functional Programming (FP) languages blessed by Cook as actually being OO to the surprise of their users, and no light on the difference between the two. Cook’s many works on OO over the years also systematically neglect important concepts in OO, such as prototypes, multiple inheritance, method combination or multiple dispatch. In the end, Cook’s PhD and subsequent academic career grew out of brilliantly modeling the key mechanism of OO (Inheritance) from the foreign point of view of FP; but his lack of appreciation and understanding for the OO tradition, indeed missing the point of it all, were such, that they have become proverbial: immortalized in Gabriel’s essay “The Structure of a Programming Language Revolution”  (Gabriel 2012) as a prototypical failure to understand a phenomenon when viewed through a scientific paradigm incommensurable with the one that produced it. The problem is not just that Cook solved Inheritance as frog and failed to take the big picture as a bird: he did take a bird’s view, and still couldn’t see what his paradigm couldn’t express. Cook is well worth mentioning precisely to illustrate the lack of common vocabulary, common concepts, and common paradigms among those who practice and study OO, even or especially among notable academics with deep expertise in the field. And yet, there are undeniably common practices, common phenomena, common concepts, common language features, common design patterns, common goals, common aspirations, worth understanding, conceptualizing, defining and naming in the rich (though sometimes mutually conflicting) traditions that grew around OO.


There is thus a need to elucidate the words and concepts of OO, behind the hype and confusion, and justify the choices made by OO (or then again, their amendment). Such is the main purpose of this book: to offer a Theory of OO.

This Theory of OO is Meaningful. A theory is meaningful if it is a body of explanations necessary and sufficient to explain what we do when we do OO, and we don’t when we don’t. It can clearly state the problems to be solved by or for OO, and the criteria by which we can judge some solutions as better than others, good or bad, acceptable or unacceptable. In these explanatory abilities, the negative is as important as the positive: it allows to demarcate the concept of OO from other concepts; to distinguish that which partakes in it, that explains it, from that which doesn’t, and would only corrupt it if accepted as part of OO.

This Theory of OO is Consistent: to remain consistent, a theory shall not contain internal contradictions. Consistency as such is easy: just avoid saying much, stick to tautologies and things already known for sure. Consistency, however, is much harder when you want to actually say a lot of useful things that interact with each other—which is why we want the theory to also be relevant.

This Theory of OO is Relevant A theory of OO is relevant to OO, and not of something else, if it matches the lore of OO: it will restate most if not all the things we know and care about OO, especially what has been well-known for decades.

To be both consistent and relevant at the same time in a lore full of controversial and mutually contradictory opinions, a theory must be critical when recalling the existing lore: it must organize the information, distinguish the wheat from the chaff, promoting some views deemed correct and denouncing incorrect ones, whether or not they are backed by majority opinions. Even if it contradicts the explanations of previous theories though, a theory must still account for and be consistent with the same observed and verifiable phenomena; or else it is a theory of something different altogether.

This Theory of OO is Productive. To be actually interesting, a theory must be productive: it must positively contribute new information. Just contributing new criteria to make sense of the existing lore can be enough to be productive. But I will go further and contribute more lore, too: useful ideas never published about OO, that make it simpler.

This Theory of OO is Constructive. While I will discuss informal principles, I will include running code in Scheme that you can easily adapt to your favorite programming language (see Why Scheme? regarding choosing Scheme). I will explain which features are needed beyond the mere applicative λ-calculus, why, and how to typically implement them in existing programming languages. Remarkably, the main feature needed is lazy evaluation, or ways to emulate it, as OO is most naturally defined in a pure lazy functional setting, and eager evaluation of OO without side-effects leads to exponential recomputations.

One aspect for which I do not provide a construction, however, is static typing. I am a proficient user of types, but am no expert at the design, implementation or theory of types. Therefore I will only provide semi-formal designs for what better static types for OO should look like. And I will refer to the better papers among the many I have read, for what I believe are good foundations for typing OO (Allen et al. 2011; Eifrig et al. 1995b,a). Among other things, good OO types should work not just for Second-Class Classes, but also for First-Class Prototypes; they require recursive types, subtyping, and some form of existential types. Dependent types are not necessary.

1.3.2 Multiple Variants of Inheritance🔗

With this variety of options, programmers (respectively programming language designers) face a choice of which of several variants of inheritance to use (respectively implement), if any at all.66And then there are dubious variants published in obscure papers, that I will not discuss. Hopefully, after reading Inheritance: Mixin, Single, Multiple, or Optimal, you will be able to understand why they are either trivially expressible in terms of the above variants, or fundamentally flawed, if you should come across them. That said, when, in old papers, I see pioneers struggling to find solutions to problems few if anyone else suspected existed, then make mistakes, or take wrong turns—I laugh, I cry, but I root for them. On the other hand, when, in more recent papers, I see researchers propose wrong solutions to problems that were solved long ago, I just shake my head, and express sadness that scientific communication and education are not working well.


Is there an objectively superior form of inheritance—whether an existing variant or some combination—with respect to expressiveness, modularity, extensibility, runtime performance, and whatever else might matter? Is one of the usual variants superior to the others in every way? If not, is there a combination of them, or a superset of them, that is? Some languages notably support forms of both single inheritance and multiple inheritance, though with some constraints: Lisp, Ruby, Scala. Would the best way to do inheritance subsume these combinations? If so, how does it relate to the multiple flavors of multiple inheritance?

And of course, critics of OO argue against using inheritance at all. What are the reasons to use or not use inheritance to begin with? I will use the absence of inheritance as a baseline against which to evaluate our variants.

1.3.3 Optimal Inheritance🔗

It is unusual for a book to claim some significant innovation like that: usually, a researcher would publish it at some conference. However, C4 in isolation might only look mildly interesting: it “just” combines a couple well-known ideas and a speed optimization. The concepts I develop are a prerequisite for the claim of optimality of C4 to even make sense, yet require this book to properly articulate. C4 itself is a notable improvement, that crowns the theory as productive. But the theory behind it is the real achievement.

What that means for you in practice, though, is that a good theory brought you a better inheritance algorithm with which to improve your existing (or future) languages.

Exercise 1.12 (Easy) Pick a theory you hate on whatever topic you know about. Analyze how this theory satisfies or fails to satisfy the criteria I have set for mine.

Exercise 1.13 (Medium) For each of the criteria that I claim my theory satisfies, identify a theory you know about that fails this criterium. With regards to productivity, mind that it is enough for the theory to have produced novel results at the time it was first proposed—it is fine if the results of that theory are not novel anymore.

Exercise 1.14 (Hard) Pick a theory you believe in that is controversial in the public at large. Identify how at least the way it is presented by people on your side, that theory is failing one of the criteria I set for my theory.

Exercise 1.15 (Research) Pick some phenomenon you’re interested in and able to observe. It can be something small or large, but has to be something you can repeatedly interact with. Some of your behavior or that of a member of your direct family or colleague at work is fine, but not the behavior of a random stranger you won’t meet again, unless it’s a general enough behavior that many people exhibit around you every week. Develop a meaningful, consistent, relevant, productive and constructive theory of that phenomenon.

Exercise 1.16 (Research) Identify some technique that comes in many variants, with divergent opinions on which variant is better, in a field you’re interested in. Determine whether you can devise an optimal variant of that technique, or an optimal strategy to pick which variant in which circumstances.

1.4.1 Plan of the Book🔗

In chapter 2, I dispel common misconceptions about OO, to ensure that my theory isn’t met with misunderstanding due to these misconceptions or to disagreements about what is or isn’t being theorized.

In chapter 3, I provide a quick overview of Object Orientation, and the three variants of inheritance in common use. This chapter serves as a map of the concepts and of the words I use to describe them, necessary because there is no common theory of OO, and no unambiguous shared vocabulary to name what common concepts there are. Importantly, I introduce the essential yet oft-ignored notion of Conflation between Specification and Target value. I then describe the relationship between Specifications, Prototypes, Classes and Objects.

In chapter 4, I explain what I mean by Internal Extensible Modularity, the rationale for OO, its motivation and purpose. This chapter remains informal, but lays the conceptual groundwork for the formal approach I take in the rest of this book.

In chapter 5, I introduce minimal formal models of Modularity and Extensibility. Using pure Functional Programming (FP) as a foundation, with Scheme syntax, I derive from first principles a minimal OO system, in two lines of code. This minimal OO system uses mixin inheritance, and, remarkably, has neither objects nor prototypes, much less classes, only specifications and targets.

In chapter 6, I rebuild all the mainstream features and appurtenances of popular OO systems as additions or modifications to the minimal system from chapter 5: prototypes, classes, types, mutation, etc. I notably clarify the all-too-common confusion between subtyping and subclassing, and discuss the actual relationship between OO and imperative programming, when the natural framework for OO is actually pure lazy functional programming.

In chapter 7, I discuss in detail the main forms of inheritance: single inheritance, multiple inheritance and mixin inheritance. I examine issues surrounding method conflict and resolution, or harmonious combination. I explain the known consistency constraints that matter for linearization algorithms in the context of multiple inheritance, and the state-of-the-art in satisfying them, the C3 algorithm. Finally, I discuss how to combine multiple and single inheritance, and examine the existing solutions adopted by Common Lisp, Ruby and Scala. I then propose my solution, a linearization algorithm I call C4, that satisfies all the constraints of C3 plus those for combining single and multiple inheritance. I explain why the residual heuristic I also adopt from C3 is arguably the best one.

In chapter 8, I discuss more advanced topics including Focused Modular Extensions, Method Combination, Multiple Dispatch (Multimethods), Monotonicity, Orphan Typeclasses, and Global Fixpoints.

In chapter 9, I discuss object representation and meta-object protocols.

Finally, in chapter 10, I conclude by recapitulating my original findings. If you want to check whether there’s anything new for you in this book, or are a future researcher interested in when now-well-known ideas were introduced, you may peek there first.

1.4.2 Stop and Go🔗

The narrative goes from the most informal, most generic and most basic information about OO, to the most formal, most specific and most advanced. Some readers may prefer to stop when the material becomes more formal. Others may want to skip the informal discussion and jump directly to the formal parts at Minimal OO, about a third into the book.

The most enthusiastic among you will read the book cover to cover, including footnotes and bibliographical notes, and go all the way into using and implementing the most advanced OO techniques of the later chapters (see Extending the Scope of OO, Efficient Object Implementation), end up building your OO system, and writing a sequel to this book. If you do, why not contact me and join me to build and write them together?

But you don’t have to be that enthusiastic to read and hopefully enjoy this book. You may read casually, skip parts that don’t interest you. You can look only at the section titles and the informal principles in bold italic. You can focus on the formal code definitions, or their type declarations. You can search for an argument on a specific controversy. You can scan the bibliography for more things to read.

What will enhance your experience, however, will be the ability to interact with a computer and play with the code. If you have an electronic copy, you may copy/paste the code, use text search to compensate for the lack of a word index, click directly into the sections that interest you, and even ask AI assistants for navigation help.

1.4.3 Self-Description🔗

At times, I will highlight some short sentence in bold italic, to make it clear I believe it is an important principle, as follows: “If you have exceptions to your stated principle, ask yourself by what standard you make the exceptions. That standard is the principle you really hold.” The above principle describes principles; in this case, it was written not by me, but by my friend Jesse Forgione.

I intend to include more examples in a future edition. But good examples take time to write, and space in the book; they can be too much for some readers and not enough for others. I am seeking the perfect concise teachable example in each case, that neatly illustrates what I mean without taking too much space or explanations. Until I find it, I must direct you to online resources, where OO code in general is abundant. If you are looking specifically for code that uses Prototype OO and multiple inheritance, you may look at my library Gerbil-POO  (Rideau 2020): it provides a practical but short implementation of a prototype object system; and it builds interesting type descriptors on top of that object system, including a nice trie data structure, that is further specialized in the gerbil-persist library. AI assistants may also be able to find examples tailored to your needs. If you struggle with a particular concept that lacks an example, please tell me. And if you find good illustrative examples for ideas you or others struggled with, please send them my way.

1.4.4 Being Objectively Subjective🔗

Too many authors hide the responsibility for a decision among multiple authors (even when there is only one), or include the readers in a collective decision they did not make. Using an unwarranted “we” is a trick commonly used by conmen, narcissists and politicians (but I repeat myself), and I find it misleading even when done innocently. I once set myself and my friends a “cuss box” in which to drop a dollar when any of us did it, even on social media. But maybe Mark Twain put it best: “Only presidents, editors, and people with tapeworms have the right to use the editorial ‘we’.” And I don’t think presidents have that right, either.

I will still say “we” on occasions, speaking for me and you readers, or for all humans. That “we” will then be passive, as things that we are, experience, or happen to us, or are constrained by the laws of logic and history: “we saw that example in a previous section” (you who read and I who wrote), “that experiment tells us” (us who saw it), “we cannot solve the termination problem” (we subject to logic). It will not be a trick to hide an action or decision that some among us made while shifting praise or blame or responsibility onto others: “we got one Nobel prize each—on average” (Marie Curie and I, but she did all the work), “we killed that poor man” (I did, but I’m trying to implicate you), “we must help that poor widow” (you all must, I’ll take a large cut of the funds).

1.4.5 Technical Nomenclature🔗

Thus, when multiple nomenclatures conflict, I will try to identify the least ambiguous word for each concept, even if it is neither the most popular word for the concept, nor the oldest, even if I sometimes make one up just for this book. Ideally, I can find a word that will be unambiguously understood by all my readers; but if that is not the case, I will prefer an awkward word that causes readers to pause and reflect, to a deceptively familiar word that causes them to unwittingly misunderstand the sometimes subtle points I make.

In particular, I will conspicuously avoid using the unqualified words “object” and “class” unless strictly necessary, because they carry different connotations for each reader, depending on their adopted traditions, that are at odds with the theory I am laying out. I will also avoid the word “class” when talking about the most general kind of entity subject to inheritance, since a class is but a quite limited special case of a prototype, that is itself derivative of what I’ll call a specification. I will define those terms precisely in What Object Orientation is — Informal Overview, OO as Internal Extensible Modularity, Minimal OO, Rebuilding OO from its Minimal Core.

Exercise 1.17 (Easy) Note that this book addresses readers with some familiarity with programming, and that it starts having code at chapter 5. Adjust your expectations and reading pattern accordingly.

Exercise 1.18 (Easy) What does the word “function” mean to a mathematician? To a C programmer? A Scheme programmer? Haskell programmer? Rocq user? Are they the same thing?

Exercise 1.19 (Easy) Identify a case where someone tries to bamboozle others by using the word “we” or “us”.

Exercise 1.20 (Medium) Identify in your domain of expertise, a technical word that is used to mean different things by practitioners of different backgrounds and communities.

Exercise 1.21 (Medium) State a principle that pertains to writing good programs, that many seasoned professionals know (though not necessarily all, or the majority, of them), and that uninitiated beginners will have trouble figuring out by themselves.

Exercise 1.22 (Hard) Identify a case where you were once bamboozled by someone using the word “we” and your granting undue credit or accepting undue responsibility—or a case were you bamboozled someone (typically child or spouse) with the same technique.

Exercise 1.23 (Hard) If you are familiar with OO, then, in advance of reading the next chapter, try to make a list of things many people claim are OO, but that aren’t really, at least not what programmers mean when they think of an OO language. You can later compare your list to mine after reading What Object Orientation is not.

Exercise 1.24 (Research) Articulate some principle of good program design, that stems from your experience, that few other people really master, and that hasn’t been fully articulated yet.

Exercise 1.25 (Research) Help a friend or family member who has been bamboozled by words see through the deception they fell for.

Exercise 1.26 (Research) Hardest of all: let apparent enemies help you identify where you yourself are being bamboozled right now.

3.1.1 Partial specifications🔗

A program is made of many parts that can be written independently, enabling division of labor, as opposed to all logic being expressed in a single monolithic loop.2727The entire point of partial specifications is that they are not complete, and you want to be able to manipulate those incomplete specifications, even though, of course, trying to “instantiate” them before all the information has been assembled should fail. Typesystems and semantic frameworks incapable of dealing with such incomplete information are thereby incapable of apprehending OO.

3.1.2 Modularity (Overview)🔗

A programmer can write or modify one part (or “module”) while knowing very little information about the contents of other parts, enabling specialization of tasks. Modularity is achieved by having modules interact with each other through well-defined “interfaces” only, as opposed to having to understand in detail the much larger contents of the other modules so as to interact with them.

3.1.3 Extensibility (Overview)🔗

A programmer can start from the existing specification and only need contribute as little incremental information as possible when specifying a part that modifies, extends, specializes or refines other parts, as opposed to having to know, understand and repeat existing code nearly in full to make modifications to it.

3.1.4 Internality🔗

Those partial programs and their incremental extensions are entities inside the language, as opposed to merely files edited, preprocessed or generated outside the language itself, which can be done for any language.

3.2.1 Prototype OO vs Class OO🔗

These in-language entities are called prototypes if first-class (manipulated at runtime, and specifying values, most usually records), and classes if second-class (manipulated at compile-time only, and specifying types, most usually record types). A language offers prototype-based object orientation (“Prototype OO”) if it has prototypes, and class-based object orientation (“Class OO”) if it only has classes.

The first arguably OO language used classes  (Dahl and Nygaard 1967), but the second one used prototypes  (Winograd 1975), and some provide both  (International 2015). Class OO is the more popular form of OO, but the most popular OO language, JavaScript, started with Prototype OO, with Class OO only added on top twenty years later.

3.2.2 Classes as Prototypes for Types🔗

A class is a compile-time prototype for a type descriptor: a record of a type and accompanying type-specific methods, or some meta-level representation thereof across stages of evaluation.

Class OO is therefore a special case of Prototype OO, which is therefore the more general form of OO  (Lieberman 1986; Rideau et al. 2021). And indeed within Prototype OO, you can readily express prototypes for runtime type descriptors for your language, or prototypes for type descriptors for some other language you are processing as a meta-language.

In this book, I will thus discuss the general case of OO, and thus will seldom mention classes, that are a special case of prototypes. Exceptions include when I elucidate the relationship between Class OO and Prototype OO, or mention existing systems that are somehow restricted in expressiveness so they only support classes.2828There would be plenty to discuss about classes and types from the point of view of library design and ecosystem growth, patterns that OO enables and antipatterns to avoid, tradeoffs between expressiveness and ease of static analysis, etc. There are plenty of existing books and papers on Class OO, OO software libraries, techniques to type and compile OO, to get inspiration from, both positive and negative. While some of the extant OO lore indeed only applies to defining classes, a great deal of it easily generalizes to any use of inheritance, even without classes, even without prototypes at all, even when the authors are unaware that any OO exists beyond Class OO.


Still my discussion of OO, and my exploration of inheritance in particular, directly applies just as well to the special case that is Class OO. See Rebuilding Class OO.

3.2.3 Classes in Dynamic and Static Languages🔗

Dynamic languages with reflection, such as Lisp, Smalltalk or JavaScript, can blur the distinction between runtime and compile-time, and thus between Prototype OO and Class OO. Indeed, many languages implement Class OO on top of Prototype OO exactly that way, with classes being prototypes for type descriptors.

Static languages, on the other hand, tend to have very restricted sublanguages at compile-time with termination guarantees, such that their Class OO is vastly less expressive than Prototype OO, in exchange for which it is amenable to somewhat easier static analysis. A notable exception is C++, that has a full-fledged Pure Functional Lazy Dynamically-Typed Prototype OO language at compile-time: templates. On the other hand, Java and after it Scala are also Turing-universal at compile-time, but not in an intentional way that enables practical metaprogramming, only an unintentional way that defeats guarantees of termination  (Grigore 2017).

3.3.1 Specifications and Targets🔗

As I reconstruct the semantics of OO from first principles, I will see that more so than prototype, class, object, or method, the fundamental notions of OO are specification and target: target computations are being specified by extensible and modular, partial specifications (see Minimal OO).

The target can be any kind of computation, returning any type of value. In Prototype OO, the target most usually computes a record, which offers simpler opportunities for modularity than other types. In Class OO, the target is instead a record type, or rather a type descriptor, record of a record type and its associated methods, or of their compile-time or runtime representation.

A (partial or complete) specification is a piece of information that (partially or completely) describes a computation. Multiple specifications can be combined into a larger specification. From a complete specification, a target computation is specified that can be extracted; but most specifications are incomplete and you can’t extract any meaningful target from them. A specification is modular inasmuch as it can define certain aspects of the target while referring to other aspects to be defined in other specifications. A specification is extensible inasmuch as it can refer to some aspects of the target as partially defined so far by previous specifications, then amend or extend them. In Prototype OO, access to this modular context and to the previous value being extended are usually referred to through variables often named self and super respectively. In Class OO, such variables may also exist, but there is an extra layer of indirection as they refer to an element of the target type rather than to the target itself.

3.3.2 Prototypes as Conflation🔗

A specification is not a prototype, not a class, not a type, not an object—it is not even a value of the target domain. It is not a record and does not have methods, fields, attributes or any such thing.

A target value in general is not an object, prototype or class either; it’s just an arbitrary value of that arbitrary domain that is targeted. It needs not be any kind of record nor record type; it needs not have been computed as the fixpoint of a specification; indeed it is not tied to any specific way to compute it. It cannot be inherited from or otherwise extended according to any of the design patterns that characterize OO.

Rather, a prototype (a.k.a. “object” in Prototype OO, and “class” but not “object” in Class OO) is the conflation of a specification and its target, i.e. an entity that depending on context at various times refers to either the specification (when you extend it) or its target (when you use its methods).

Formally speaking, a conflation can be seen as a cartesian product with implicit casts to either component factor depending on context. In the case of a prototype, you’ll implicitly refer to its specification when speaking of extending it or inheriting from it; and you’ll implicitly refer to its target when speaking of calling a method, looking at its attributes, reading or writing a field, etc. See Conflation: Crouching Typecast, Hidden Product.

3.3.3 Modularity of Conflation🔗

In first-class OO without conflation, developers of reusable libraries are forced to decide in advance and in utter ignorance which parts of a system they or someone else may want to either extend or query in the future. Having to choose between specification and target at every potential extension point leads to an exponential explosion of bad decisions to make: Choosing target over specification everywhere would of course defeat extensibility; but choosing specification over target for the sake of extensibility, especially so without the shared computation cache afforded by conflation, would lead to an exponential explosion of runtime reevaluations. By letting programmers defer a decision they lack information to make, the conflation of specification and target is an essential pragmatic feature of Prototype OO: it increases intertemporal cooperation between programmers and their future collaborators (including their future selves) without the need of communication between the two (that would require time-travel). Thus, in first-class OO, Conflation Increases Modularity.

This modularity advantage, however, is largely lost in static languages with second-class Class OO.2929Note that this does not include dynamic Class OO languages like Lisp, Smalltalk, Ruby or Python. In these languages, compilation can keep happening at runtime, and so programmers still benefit from Conflation.


In such languages, all class extensions happen at compile-time, usually in a restricted language. Only the type descriptors, targets of the specifications, may still exist at runtime (if not inlined away). The specifications as such are gone and cannot be composed or extended anymore. Thus, you can always squint and pretend that conflation is only a figure of speech used when describing the system from the outside (which includes all the language documentation), but not a feature of the system itself. However, this also means that in these static OO languages, conflation of specification and target is but a minor syntactic shortcut with little to no semantic benefit. Yet its major cost remains: the confusion it induces, not just among novice developers, but also experts, and even language authors.

3.3.4 Conflation and Confusion🔗

Conflation without Distinction is Confusion. Those who fail to distinguish between two very different concepts being conflated will make categorical errors of using one concept or its properties when the other should be used. Inconsistent theories will lead to bad choices. Developers will pursue doomed designs they think are sound, and eschew actual solutions their theories reject. At times, clever papers will offer overly simple solutions that deal with only one entity, not noticing an actual solution needed to address two. In rare cases, heroic efforts will lead to overly complicated solutions that correctly deal with both conflated entities at all times. Either way, incapable of reasoning correctly about OO programs, developers will amend bad theories with myriad exceptions and “practical” recipes, rather than adopt a good theory that no one is offering. Murky concepts will lead to bad tooling. Confused developers will write subtle and persistent application bugs. Researchers will waste years in absurd quests and publish nonsense along the way, while fertile fields lay unexplored. See the NNOOTT (The NNOOTT: Naive Non-recursive OO Type Theory) regarding decades of confusion between subtyping and subclassing due to confusing target (subtyping) and specification (subclassing).

Still, when you clearly tease the two notions apart, and are aware of when they are being conflated for practical purposes, so you can distinguish which of the two aspects should be invoked in which context, then the semantics of OO becomes quite simple. Shockingly, conflation was first explicitly discussed only in Rideau et al. (2021) even though (a) the concept is implicitly older than OO, going at least as far back as Hoare (1965), and (b) the implementation of various Prototype OO systems has to explicitly accommodate for it (see e.g. the __unfix__ attribute in Simons (2015)) even when the documentation is silent about it.

3.4.1 An Ambiguous Word🔗

In Prototype OO, a prototype, conflation of a specification and its target, is also called an “object” or at times an “instance”, especially if the target is a record. Note that laziness is essential in computing the target record or its entries, since most specifications, being partial, do not specify a complete computation that terminates without error in finite time, yet this expected non-termination should not prevent the use of the conflated entity to extract and extend its specification (see Rebuilding Prototype OO).

In Class OO, a prototype, conflation of a specification and its target, is instead called a “class”, and the target is specifically a type descriptor rather than an arbitrary record, or than a non-record value. What, in Class OO, is called an “object” or an “instance” is an element of a target type as described. A class being a prototype, its regular prototype fields and methods are called “class fields” or “class methods” (or “static” fields and methods, after the keyword used in C++ and Java)—but be mindful that they only involve the target type, not the specification. “Object methods” are semantically regular methods that take one implicit argument in front, the object (i.e. element of the target type). “Object fields” are regular fields of the object as a record (see Rebuilding Class OO).

Finally, many languages, systems, databases, articles or books call “object” some or all of the regular runtime values they manipulate:3030Alan Kay, in his Turing Award lecture, remarks: “By the way, I should mention that, you know, the name, the term object predates object-oriented programming. Object, in the early 60s, was a general term that was used to describe compound data structures, especially if they had pointers in them.”


these “objects” may or may not be records, and are in no way part of an actual OO system extensible with inheritance. The authors will not usually claim that these objects are part of an OO framework actual or imagined, but then again sometimes they may.3131This situation can be muddled by layers of language: Consider a language without OO itself implemented in an OO language. The word “object” might then be validly denote OO from the point of view of the implementer using the OO meta-language, yet not from the point of view of the user using the non-OO language. Conversely, when an OO language is implemented using a non-OO language, calling some values “objects” may validly denote OO for the user yet not for the implementer.


.

3.4.2 OO without Objects🔗

Furthermore, the fundamental patterns of OO can exist and be usefully leveraged in a language that lacks any notion of object, merely with the notions of specification and target, as we will show in Minimal OO. Meanwhile, Yale T Scheme has a class-less object system  (Adams and Rees 1988; Rees and Adams 1982), wherein the authors call “object” any language value, and “instance” the prototypes in their object system.

Therefore the word “object” is worse than useless when discussing OO in general. It is actively misleading. It should never be used without a qualifier or outside the context of a specific document, program, system, language, ecosystem or at least variant of OO, that narrows down the many ambiguities around its many possible mutually incompatible meanings.3232It’s a bit as if you had to discuss Linear Algebra without being able to talk about lines, or had to discuss Imperative Programming without being able to talk about the Emperor. Ridiculous. Or perhaps just an artifact of etymology.


Meanwhile, the word “class” is also practically useless, denoting a rather uninteresting special case of a prototype. Even the word “prototype”, while meaningful, is uncommon to use when discussing OO in general. If discussing inheritance, one will only speak of “specifications”. And if discussing instantiation, one will speak of “specification” and “target”. Prototypes only arise when specifically discussing conflation. To avoid confusion, I will be careful in this book to only speak of “specification”, “target”, “prototype”, and (target type) “element” and to avoid the words “object” or “class” unless necessary, and then only in narrowly defined contexts.3333I am, however, under no illusion that my chosen words would remain unambiguous very long if my works were to find any success. They would soon be rallying targets not just for honest people to use, but also for ignoramus, spammers, cranks, and frauds to subvert—and hopefully for pioneers to creatively misuse as they make some unforeseen discovery.

This is all particularly ironic when the field I am studying is called “Object Orientation”, in which the most popular variant involves classes. But fields of knowledge are usually named as soon as the need is felt to distinguish them from other fields, long before they are well-understood, and thus based on misunderstandings; this misnomer is thus par for the course.3434The wider field of study is similarly misnamed. E. W. Dijkstra famously said that Computer Science is not about computers. Hal Abelson completed that it is not a science, either.

On the other hand, this book is rare in trying to study OO in its most general form. Most people instead try to use OO, at which point they must soon enough go from the general to the particular: before a programmer may even write any code, they have to pick a specific OO language or system in which to write their software. At that point, the context of the language and its ecosystem as wide as it may be, is plenty narrow enough to disambiguate the meanings of all those words. And likely, “object”, and either or both of “prototype” or “class” will become both well-defined and very relevant. Suddenly, the programmer becomes able to utter their thought and communicate with everyone else within the same ecosystem... and at the same time becomes more likely to misunderstand programmers from other ecosystems who use the same words with different meanings. Hence the tribal turn of many online “debates”.

3.5.1 Inheritance as Modular Extension of Specifications🔗

Inheritance is the mechanism by which partial modular specifications are incrementally extended into larger modular specifications, until the point where a complete specification is obtained from which the specified target computation can be extracted.

There have historically been three main variants of inheritance, with each object system using a variation on one or two of them: single inheritance, multiple inheritance and mixin inheritance. For historical reasons, I may speak of classes, subclasses and superclasses in this section, especially when discussing previous systems using those terms; but when discussing the general case of prototypes and specifications, I will prefer speaking of specifications and their parents, ancestors, children and descendants—also specifications.

3.5.2 Single Inheritance Overview🔗

Historically, the first inheritance mechanism discovered was single inheritance  (Dahl and Nygaard 1967), though it was not known by that name until a decade later. In an influential paper (Hoare 1965), Hoare introduced the notions of “class” and “subclass” of records (as well as, infamously, the null pointer). The first implementation of the concept appeared in Simula 67  (Dahl and Nygaard 1967). Alan Kay later adopted this mechanism for Smalltalk 76  (Ingalls 1978), as a compromise instead of the more general but then less well understood multiple inheritance  (Kay 1993). Kay took the word “inheritance” from KRL  (Bobrow and Winograd 1976; Winograd 1975), a “Knowledge Representation Language” written Lisp around Minsky’s notion of Frames. KRL had “inheritance of properties”, which was what we would now call “multiple inheritance”. The expressions “single inheritance” and “multiple inheritance” can be first be found in print in Stansfield (1977), another Lisp-based frame system. Many other languages adopted “inheritance” after Smalltalk, including Java that made it especially popular circa 1995.

In Simula, a class is defined starting from a previous class as a “prefix”. The effective text of a class (hence its semantics) is then the “concatenation” of the direct text of all its transitive prefix classes, including all the field definitions, method functions and initialization actions, in order from least specific superclass to most specific.3535Simula later on also allows each class or procedure to define a “suffix” as well as a “prefix”, wherein the body of each subclass or subprocedure is the “inner” part between this prefix and suffix, marked by the inner keyword as a placeholder. Lack of explicit inner keyword is same as before, as if the keyword was at the end. This approach by Simula and its successor Beta  (Kristensen et al. 1987) (that generalized classes to “patterns” that also covered method definitions the same way; except that lack of “inner” means the “do” block cannot be extended anymore, like “final” in Java or C++), is in sharp contrast with how inheritance is done in almost all other languages, that copy Smalltalk. The “prefix” makes sense to initialize variables, and to allow procedure definitions to be overridden by later more specialized definitions; the “suffix” is sufficient to do cleanups and post-processing, especially when all communication of information between concatenated code fragments happens through side-effects to shared instance variables (including, in Algol style, a special variable with the same name as the procedure being defined, to store the working return value). The entire “inner” setup also makes sense in the context of spaghetti code with GOTOs, before Dijkstra made everyone consider them harmful in 1968; the reliance on side-effects everywhere also made more sense before Lisp, Functional Programming, and eventually concurrency and large distributed systems, made people realize side-effects can be more confusing than pure information flow through function calls, return values and immutable let bindings. But this concatenation semantics is both limited and horribly complex to use in the post-1968 context of structured code blocks, not to mention post-1970s higher-order functions, etc. You could express the modern approach in a roundabout way in Beta, by explicitly building a list or nesting of higher-order functions as your only side-effect, that re-invert control in a pure way back the way everyone else does it, that you call at the end; but that would be an awkward design pattern. And so, while Simula was definitely a breakthrough, its particular form of inheritance was also a dead-end. No one but the Simula inventors wants anything resembling inner for the language they build or use. After Smalltalk, languages instead let subclass methods control the context for possible call of superclass methods, rather than the other way around). Beta behavior is easily expressible with user-defined method combinations in CLOS  (Bobrow et al. 1988), or can also be retrieved by having methods explicitly build an effective method chained the other way around. Thus, I can rightfully say that inheritance, and OO, were only invented and named through the interaction of Bobrow’s Interlisp team and Kay’s Smalltalk team at PARC circa 1976, both informed by ideas from Simula, and Minsky’s frames, and able to integrate these ideas in their respective AI and teachable computing experiments thanks to their dynamic environments, considerably more flexible than the static Algol context of Simula. In the end, Simula should count as a precursor to OO, or at best an early draft of it—but either way, not the real, fully-formed concept. Dahl and Nygaard never invented, implemented, used or studied OO as most of us know it: not then with Simula, not later with Beta, and never later in their life either. Just like Columbus never set foot on the continent of America. Yet they made the single key contribution thanks to which the later greater discovery of OO became not just possible, but necessary. They rightfully deserve to be gently mocked for getting so close to a vast continent they sought yet failing to ever set foot on it. But this only makes me admire them more for having crossed an uncharted ocean the vast extent of which no one suspected, beyond horizons past which no one dared venture, to find a domain no one else dreamed existed.


In modern terms, most authors call the prefix a superclass in general, or direct superclass when it is syntactically specified as a superclass by the user. I will be more precise, and after Snyder (1986), I will speak of a parent for what users explicitly specify, or, when considering transitively reachable parents of parents, an ancestor; and in the other direction, I will speak of child and descendant. The words parent and ancestor, in addition to being less ambiguous, also do not presume Class OO. I will call inheritance hierarchy of a specification, the set of its ancestors, ordered by the transitive parent relation. When using single inheritance, this hierarchy then constitutes a list, and the ancestor relation is a total order.

Single inheritance is easy to implement without higher-order functions: method lookup can be compiled into a simple and efficient array lookup at a fixed index — as opposed to some variant of hash-table lookup in the general case for mixin inheritance or multiple inheritance. Moreover, calls to the “super method” also have a simple obvious meaning. In olden days, when resources were scarce and before FP was mature, these features made single inheritance more popular than the more expressive but costlier and less understood alternatives.

Even today, most languages that support OO only support single inheritance, for its simplicity.

3.5.3 Multiple Inheritance Overview🔗

Discovered a few years later, and initially just called inheritance, in what, in retrospect, was prototype OO, in KRL  (Bobrow and Winograd 1976; Winograd 1975), Multiple inheritance allows a specification (frame, class, prototype, etc.) to have multiple direct parents. The notion of (multiple) inheritance thus predates Smalltalk-76  (Ingalls 1978) adopting the term, retroactively applying it to Simula. The terms “single” and “multiple” inheritance were subsequently invented to distinguish the two approaches as well as recognize their commonality  (Stansfield 1977).

Although some more early systems  (Bobrow and Stefik 1983; Borning and Ingalls 1982; Borning 1977; Curry et al. 1982; Goldstein and Bobrow 1980) used multiple inheritance, multiple inheritance only became usable with the epochal system Flavors  (Cannon 1979; Weinreb and Moon 1981), refined and improved by successor Lisp object systems New Flavors (Moon 1986), CommonLoops (Bobrow et al. 1986) and CLOS (Bobrow et al. 1988; Steele 1990). Since then, many languages including Ruby, Perl, Python and Scala correctly adopted the basic design of Flavors (though none of its more advanced features)—I will call them flavorful.3636To be fair, these languages all include the capability for a method to call a super-method, that was not directly possible in Flavors (1979) without writing your own method-combination, but only introduced by CommonLoops (1986) with its run-super function, known as call-next-method in CLOS (1988).


On the other hand, influential or popular languages including Smalltalk, Self, C++ and Ada failed to learn from Flavors and got multiple inheritance largely wrong—I will call them flavorless.

With multiple inheritance, the structure of a specification and its ancestors is a Directed Acyclic Graph (“DAG”). The set of all classes is also a DAG, the subclass relation is a partial order. Most OO systems include a common system-wide base class at the end of their DAG; but it is possible to do without one.3737Indeed, Flavors allowed you not to include the system-provided vanilla-flavor at the end of its precedence list, so you could write your own replacement, or do without.

The proper semantics for a specification inheriting multiple different methods from a non-linear ancestry proved tricky to get just right. The older (1976) “flavorless” viewpoint sees it as a conflict between methods you must override. The newer (1979) “flavorful” viewpoint sees it as a cooperation between methods you can combine. Unhappily, too many in both academia and industry are stuck in 1976, and haven’t even heard of the flavorful viewpoint, or, when they have, still don’t understand it. For this reason, despite its being more expressive and more modular than single inheritance, flavorful multiple inheritance still isn’t as widely adopted as of 2026.3838Out of the top 50 most popular languages in the TIOBE index, 2025, 6 support flavorful multiple inheritance (Python, Perl, Ruby, Lisp, Scala, Solidity), 3 only support flavorless multiple inheritance (C++, Ada, PHP), 2 require a non-standard library to support multiple inheritance (JavaScript, Lua), 17 only support single inheritance (Java, C#, VB, Delphi, R, MATLAB, Rust, COBOL, Kotlin, Swift, SAS, Dart, Julia, TypeScript, ObjC, ABAP, D), and the rest don’t support inheritance at all (C, Go, Fortran, SQL, Assembly, Scratch, Prolog, Haskell, FoxPro, GAMC, PL/SQL, V, Bash, PowerShell, ML, Elixir, Awk, X++, LabView, Erlang).

3.5.4 Mixin Inheritance Overview🔗

Mixin inheritance was discovered last  (Bracha and Cook 1990), probably because it relies on a more abstract pure functional view of OO—maybe also because it was one of the first successful attempts at elucidating inheritance in the paradigm of programming language semantics, when the concept had previously been developed in paradigm of computing systems  (Gabriel 2012). Yet, for the same reasons, Mixin Inheritance is more fundamental than the other two variants. It is the simplest kind of inheritance to formalize given the basis of FP, in a couple of higher-order functions. Specifications are simple functions, inheritance is just chaining them, and extracting their target computation is just computing their fixpoint. Mixin inheritance also maps directly to the concepts of Modularity and Extensibility I am discussing, and for these reasons I will study it first when presenting a formal semantics of OO (see Minimal OO).

Mixins equipped with a binary inheritance operator constitute a monoid (associative with neutral element), and the inheritance structure of a specification is just the flattened list of elementary specifications chained into it, as simple as single inheritance. Mixin inheritance works better at runtime, either with Prototype OO, or, in a dynamic and somewhat reflective system, with Class OO.

Mixin inheritance is in some way simpler than single inheritance (but only if you understand FP yet are not bound by limitations of most of today’s FP typesystems), and as expressive as multiple inheritance (arguably slightly more, though not in a practically meaningful way), but is less modular than multiple inheritance because it doesn’t automatically handle transitive dependencies but forces developers to handle them manually, effectively making those transitive dependencies part of a specification’s interface.

For all these reasons adoption of mixin inheritance remains relatively limited, to languages like StrongTalk  (Bak et al. 2002; Bracha and Griswold 1993), Racket  (Flatt et al. 2006; Flatt et al. 1998), Newspeak  (Bracha et al. 2008), GCL  (Bokharouss 2008), Jsonnet  (Cunningham 2014), and Nix  (Simons 2015). Yet it still has outsized outreach, for just the use of GCL at Google means a large part of the world computing infrastructure is built upon configurations written using mixin inheritance.3939My understanding is that GCL as such only had single inheritance, but that users would define their own mixins by abstracting over the base class being extended using single inheritance, e.g. lambda base: base { a = 1 + super.a; b = c + d;} Semantically, this is just the same trick as used by Racket to implement mixins on top of single inheritance.


One may also construe the way C++ handles non-“virtual” repeated superclasses as a form of mixin inheritance with automatic renaming, at which point mixin inheritance is actually very popular, just not well-understood.

3.5.5 False dichotomy between Inheritance and Delegation🔗

Many authors have called “delegation” the mechanism used by Prototype OO as distinct from the “inheritance” mechanism of Class OO. This wrongheaded distinction started with Hewitt et al. (1979), in whose ACT1 language the two concepts were both implemented, but through separate implementation paths. The distinction was further popularized by Lieberman (1986), who contrasts the two joined concepts of prototype-delegation vs class-inheritance.

Yet, identifying inheritance with classes to the exclusion of prototypes is historically counterfactual: the words “inheritance” and “prototype” were both simultaneously introduced by KRL  (Bobrow and Winograd 1976; Winograd 1975), a system with (multiple) inheritance and prototype OO—from before the word Object Oriented was popular. Indeed, KRL was instrumental as an inspiration to Smalltalk-76, the system that made OO popular.

Opposing inheritance and delegation is also logically counterfactual: Lieberman (1986) itself explains how “inheritance” (i.e. classes) can be expressed as a special use of “delegation” (i.e. prototypes). On the other hand, paper also explains you cannot go the other way around and express prototypes in terms of classes: prototypes enable dynamic extension of individual “objects” (prototypes) at runtime, while classes only allow extension at compile-time, and only for an entire type (“class”) of “objects” (elements of the type).

In the end, the inheritance mechanism is indeed the same, and it is very wrong to give it two different names depending on whether it is used for prototypes or for classes. Even Self, that became the most popular language with “delegation” in academia, uses the word “inheritance” in its papers  (Chambers et al. 1989; Chambers et al. 1991; Ungar and Smith 1987). And Stein (1987) argues that delegation and inheritance are the same concept, and notes that prototypes map to classes, not class instances (though strictly speaking she gets the mathematical direction of the map wrong). The real distinction and comparison that should have been made was between the relative expressiveness of prototypes and classes, especially if considered as second-class entities and in absence of reflection (or refraint from using it). But that is the conclusion that none of the authors who wrote on the topic made explicit, even though it is implicit in both. And so the authors focus on arguing about different ways to name the same concept in two contexts while failing to argue on the different contextual concepts that do matter.4040If irrelevant changes in the context are a valid excuse to give an existing concept a new name and get a publication with hundreds of citations based on such a great original discovery, I here dub “ainheritance” the concept of “inheritance” when the name of the entity inheriting from others starts with “a”, “binheritance” the concept of “inheritance” when the programmer’s console is blue, “cinheritance” the concept of “inheritance” when the programmer is in China, and “sinheritance” the concept of “inheritance” when the specification is not conflated with its target, therefore neither a class nor a prototype. Also “ninheritance” when there is no actual inheritance, and “tinheritance” when it looks like inheritance, but is not real inheritance, just target extension without open recursion through a module context. I am also reserving the namespace for variants of the name starting with a heretofore unused letter, unicode character, or prefix of any kind, and launching the Interplanetary Xinheritance Foundation to auction the namespace away, as well as the related Intergalactic Zelegation Alliance. I am impatiently awaiting my Turing Award, or at least Dahl Nygaard prize, for all these never discussed before original inventions related to OO. The Lieberman paper deserves its thousands of citations because it is a great paper. However, a lot of citers seem to fixate only on the unfortunate choice of concept delineation and naming by Lieberman, who probably did not anticipate that he would set a bad trend with it. The delineation made sense in the historical context of the Actor team separately implementing prototypes and classes with related yet distinct mechanisms in their ACT1 language  (Hewitt et al. 1979), way before they or anyone understood how classes were a special case of prototypes. But too many readers took this historical artifact as an essential distinction, and thereafter focused on studying or tweaking low-level “message passing” mechanisms on a wild goose chase for tricks and features, instead of looking at the big picture of the semantics of inheritance, what it actually is or should be and why, what is or isn’t relevant to its semantics. Concept delineation and naming is tremendously important; it can bring clarity, or it can mislead hundreds of researchers into a dead end.

One confounding factor is that of mutable state. Early OO, just like early FP, was usually part of systems with ubiquitous mutable state; prototype inheritance (or “delegation”) algorithms thus often explicitly allow or cope with interaction with such state, including mutation and sharing or non-sharing of per-object or per-class variables, and especially tricky, mutation and sharing of a prototype’s inheritance structure. However, class systems often had all their inheritance semantics resolved at compile-time, during which there is no interaction with user-visible side-effects, and it doesn’t matter whether the compiler does or doesn’t itself use mutable state: from the user point of view it is as if it were pure functional and there is no mutation in the inheritance structure or state-sharing structure of classes, at least not without using “magic” reflection primitives. One may then have been tempted then to see Prototype Delegation as intrinsically stateful, and class inheritance as intrinsically pure (though at compile-time).

Yet, recent pure functional Prototype OO systems  (Cunningham 2014; Rideau et al. 2021; Simons 2015) prove constructively that prototypes can be pure, and that they use the very same inheritance mechanisms as classes, indeed with classes as a particular case of prototypes with the usual construction. Meanwhile, old reflective Class OO systems like Lisp and Smalltalk  (Gabriel et al. 1991; Kahn 1976; Kay 1993; Kiczales et al. 1991) also support mutable state to modify the inheritance structure at runtime, for the sake of dynamic redefinition of classes at runtime, in what remains semantically a pure functional model once when the structure is set. See how in CLOS you can define methods on generic function update-instance-for-redefined-class to control how data is preserved, dropped or transformed when a class is redefined. Mutable state and mutable inheritance structure in particular are therefore clearly an independent issue from prototypes vs classes, though it might not have been obvious at the time. As I introduce formal models of OO, I will start with pure functional models (see Minimal OO), and will only discuss the confounding matter of side-effects much later (see Stateful OO).4141It might be interesting to explain why many authors failed so systematically to identify delegation and inheritance, when the similarities are frankly obvious, and the relationship between classes and prototypes is well-known to anyone who implemented classes atop prototypes. But lacking direct access to those authors’ brains, my explanations must remain speculative. First, pioneers are eager to conceptualize and present their experiments as original and not just the same concept in a different context. They necessarily have to sell their ideas as historical package deals, before the underlying concepts are clearly identified and separated from each other. They are too close to the matter to tell which of the features they built would be immortalized through the ages as fundamental concepts vs just contingent implementation details soon to be forgotten. In the brief time that publishing about Prototypes was trendy, scientists studying pioneering works may have focused too much on the specifics of Actors, Self, or other successful Prototype language du jour, and failed to properly conceptualize a general notion of Prototype. Unlike the pioneers themselves, they deserve blame for their myopia, and so do the followers who cite and repeat their “findings” without criticism. However this explanation is not specific to the topic at hand, and is valid for every field of knowledge. Second, and with more specificity to Prototypes, Computer Scientists following the Programming Language (PL) paradigm (Gabriel 2012) might have been unable to unify Prototypes and Classes when delegation happens at runtime while inheritance happens at compile-time: not only does the machinery look very different to users and somewhat different as implementers, written in different languages with different formalisms, but PL people tend to deeply compartmentalize the two. They may have looked at low-level mutable state (omnipresent in any practical language until the mid-2000s) as essential when happening at runtime, when they could clearly conceptualize it away as an implementation detail when happening at compile-time. Systems paradigm people (including the old Lisp, Smalltalk and Self communities) who freely mix or interleave runtime and compile-time in the very same language, might have had no trouble unifying the two across evaluation times, but they tend not to publish articles about PL semantics, and not to be read by most PL semanticians, or not understood by those that do read the articles. Revisiting these topics several decades after they were in vogue, and finding their then-treatment lacking, with errors from the time still uncorrected to this day, makes me wonder about what other false ideas I, like most people, assume are true in all the other topics I haven’t revisited, whether in Computer Science or not, where I just blindly assume the “experts” to be correct due to Gell-Mann amnesia.

As for which words to keep, the word “inheritance” was used first for the general concept, in a language with “prototypes”. The word “delegation” stems from the Actor message-passing model, and is both later and less general, from after the words “inheritance” and “prototypes” were better established, and is strongly connoted to specific implementations using the message-passing paradigm. It also fell out of fashion some time in the 1990s, after JavaScript became a worldwide phenomenon, and (correctly) used the term “inheritance” rather than delegation (as it isn’t particularly “message passing”, just calling functions).  (ECMA-262 1997)

3.6.1 Is my definition correct?🔗

3.6.2 What does it even mean for a definition to be correct?🔗

But no, such a point of view is worse than wrong—it is outright evil. The phenomena that effectively affect people, that they care to name, discuss, think about and act on, are not arbitrary. Thus the important part of definitions isn’t convention at all: it is the structure and understanding of these phenomena, rather than the labels used for them. A correct definition precisely identifies the concepts that are relevant to people’s concerns, that help them make better decisions that improve their lives, whereas an incorrect definition misleads them into counterproductive choices. Specifically overriding your reason with power is an act of war against you, and generally overriding all reason with power is the very definition of evil.

3.6.3 Is there an authority on those words?🔗

3.6.4 Shouldn’t I just use the same definition as Alan Kay?🔗

But neither the above  (Kay 2003) nor any of Kay’s pronouncement on OO constitutes a precise definition with an objective criteria, if a definition at all.4242My interpretation is that the first part of this definition (until the last comma) corresponds to modularity, the ability to think about programs in terms of separate “local” entities each with its own “state-process” wherein interactions only happen through well-delimited interfaces (“messaging”). The second part “extreme late-binding of all things” indirectly references the in-language and extensible aspect of modules: extreme late-binding means that the value of those units of modularity may change at runtime, which means not only dynamic dispatch of method invocation depending on the runtime class of an object, but also the ability to dynamically define, incrementally extend, refine or combine those units in the language. Those units may be first-class prototypes, and even when they are only second-class classes, there is a first-class reflection mechanism to define and modify them. When this extensibility is only available at compile-time, as in the object system of many static languages, then the OOP only happens in the meta-language (as in e.g. C++ templates), or the language lacks complete support for OOP. Note that Kay didn’t immediately adopt Simula’s inheritance mechanism in Smalltalk-72 (it wasn’t called that yet in Simula, either); but he did adopt it eventually in Smalltalk-76, notably under the push of Larry Tesler (who previously used “slot inheritance” on early desktop publishing applications), and this adoption is what launched OO as a phenomenon. Kay stated adopting single inheritance over multiple inheritance was a compromise  (Kay 1993); his team later added multiple inheritance to Smalltalk  (Goldstein and Bobrow 1980), but it is unclear that Kay had much to do with that addition, that never became standard. More broadly, Kay didn’t endorse any specific inheritance mechanism, and never focused on that part of the design. To Kay it was only a means to an end, which is what Kay called “extreme late binding”: the fact that behavior definition happens and takes effect dynamically up to the last moment based on values computed at runtime. Inheritance, the practical means behind the late behavior definition that is late bound, and the precise form it takes, is secondary to Kay; what matters to Kay is the role it plays in enabling dynamic code specialization. But inheritance becomes a primary concern to whoever wants to formalize the concepts behind OO, and must refine the intuitions of a pioneer into codified knowledge after decades of practice. And if other means are found to arguably satisfy Kay’s “extreme late binding”, then they’ll have to be given a name that distinguishes them from what is now called OO.


And even if he had at some point given a definition, one still should remain skeptical of what Kay, and other pioneers, said, if only to recursively apply the same semantic attention to the definition of the words they used in their definitions. Now, one should certainly pay close attention to what pioneers say, but one should pay even closer attention to what they do. The pioneer’s authority lies not in precise words, but in inspiring or insightful ones; not in well-rounded neatly-conceptualized theories, but in the discovery of successful new practices that are not yet well understood. Solid theories arise only after lots of experience, filtering, and reformulation.

3.6.5 Shouldn’t I just let others define “OO” however they want?🔗

But it is no good to let an ignorant majority “define” the term “Object Orientation” to mean what little they know of it—for instance, to pick the most popular elements: Class OO only, always mutable records, only single inheritance or C++ style flavorless “multiple inheritance”, only single dispatch, no method combination, etc. Letting those who don’t know and don’t care define technical words would be knowledge bowing to ignorance; it would be for those who know and care to abdicate their responsibility and follow the masses when they should instead lead them; it would be ceding terrain to the Enemy—snake oil salesmen, chaosmongers, corrupters of language, manipulators, proud spreaders of ignorance, etc.—who if let loose would endlessly destroy the value of language and make clear meaning incommunicable. Beside, if you retreat to “inheritance” in the hope that at least for that term you can get people to agree on a clear unambiguous meaning,4343The term “inheritance” is already corrupted, since Goguen uses it at times to mean refinement  (Goguen 1992) while claiming to do OO, and others use it to mean the (non-modular) extension of database tables or equivalent. Moreover, the term “inheritance”, that originated in KRL, in parallel to the adoption and evolution it saw in the field of OO, also had its evolution in the field of Knowledge Representation, Description Logics, Semantic Web, etc. And there are plenty of further legitimate non-OO uses of the word “inherit”, to mean that some entity derives some property from a historical origin, an enclosing context, etc.


you’ll find that if you have any success defining a useful term that way, the agents of entropy will rush to try to defile it in direct proportion to your success; you will have given up precious lexical real estate for no gain whatsoever, only terrible loss.4444Indeed, if you don’t know to stand your ground, you will constantly retreat, and be made to use ever more flowery “politically correct” vocabulary as a humiliation ritual before those who will wantonly take your words away to abuse you and thereby assert their dominance over you.

3.6.6 So what phenomena count as OO?🔗

And these phenomena are what is captured by the intra-linguistic extensible modularity as defined above: (a) the ability to “code against an interface” and pass any value of any type that satisfies the interface (modularity, whether following structural or nominative rules), (b) the ability to extend and specialize existing code by creating a new entity that “inherits” the properties of existing entities and only needs specify additions and overrides in their behavior rather than repeat their specifications, wherein each extension can modularly refer to functionality defined in other yet-unapplied extensions; and (c) the fact that these entities and the primitives to define, use and specialize them exist within the programming language rather than in an external preprocessing layer.

I contend that the above is what is usually meant by OO, that matches the variety of OO languages and systems without including systems that are decidedly not OO, like Erlang, SML or UML. Whatever clear or murky correspondence between names and concepts others may use, this paradigm is what matters, and is what I will call OO—it is what I will discuss in this book, and will systematically reduce to elementary concepts.

As to why should this particular meaning of “object-oriented” should win over other plausible meanings offered before or after Kay’s and Bobrow’s 1976 invention, or other names for the concept, I will conclude with this tweet by Harrison Ainsworth: Naming is two-way: a strong name changes the meaning of a thing, and a strong thing changes the meaning of a name.

Exercise 3.1 (Easy) Identify one to three concepts from this chapter that you were not familiar with. For each, write a one-sentence definition in your own words.

Exercise 3.2 (Easy) For each concept above you feel comfortable with, and among the programs you know, identify a program that illustrates the use of the concept, if you know any. If you don’t know any program that illustrates the concept, you might know instead a language that offers a builtin construct for it.

Exercise 3.3 (Easy) Look back at the previous chapter on what OO is not. Explain how the concepts of this chapter justifies the previous judgements. Consider sections of the previous chapter in a random order, so that, if you stop before the end, you don’t just do the first few sections like everyone else.

Exercise 3.4 (Easy) Make a mindmap of the concepts I presented, and establish correspondences with OO languages you know. Include at least: modularity, extensibility, internality; specification, target, prototype, class, and conflation; single, multiple and mixin inheritance. Do you now have a clearer understanding of these languages and how their concepts relate? Write a couple of sentences describing how your understanding has changed.

Exercise 3.5 (Medium) Make a note of cases where you were confused in the past by people using the same word for what turned out to be very different concepts (though possibly related) or by people using different words for what turned out to be the same concept. The words “object”, “inheritance”, “delegation” are obvious candidates; but there are probably more such words, beyond the field of OO, for which you know or suspect this might be the case.

Exercise 3.6 (Medium) Identify an OO language in a point of the OO design space you didn’t suspect existed. Read the tutorial for that language, look at examples exercising idioms not directly expressible in languages you know of. Play with it. Use it to extend programs or configurations that you or other people wrote.

Exercise 3.7 (Medium) Consider among programs you are familiar with. For each, ask: Does it have multiple variants or configurations? Do different parts need to be modified independently? Are there places the code could be extended, specialized or modified in different ways to satisfy different goals? Would there be a benefit to users if a shared core were maintained on top of which users each have their own custom variant? See if you can devise a simple criterion (1-2 sentences) for what separates programs that would benefit from modular extensibility from those that wouldn’t.

Exercise 3.8 (Medium) In the first footnote of the chapter, I claim that “typesystems and semantic frameworks incapable of dealing with such incomplete information are thereby incapable of apprehending OO.” Find a type system you know (Java, Haskell, TypeScript, etc.) and explain: Can it represent incomplete specifications? If so, how? If not, what would need to be added? Describe the transition from incomplete specification to complete. Hint: Many typesystems can deal with incomplete specifications at the level of types, but not directly of values. You might however a different “partial” record type with options on each field as a feature outside the language if not inside it.

Exercise 3.9 (Medium, Recommended) If you did exercise 2.8, compare your previous answers to mine. See what surprised you—what you agreed and disagreed with before you read this chapter, and how your understanding has evolved already.

Exercise 3.10 (Hard, Recommended) Based on this informal overview, and before you read the next chapter, try to write down your own short theory of what the main concepts like “modularity”, “extensibility” and “internality” might mean, and what formalizing them might look like. Bonus if you can then explain how the three together can mean something more than the same three apart. Save your answer to compare with the treatment in OO as Internal Extensible Modularity.

Exercise 3.11 (Hard) Identify another phenomenon named with a word the meaning of which has been diluted in the public at large, yet a precise definition of which can be given; see how people misled by the dilution of meaning may hold wrong beliefs and make bad decisions based on the misidentification of concepts.

Exercise 3.12 (Research) Find a controversy on the Internet where two sides have a fundamental disagreement—if possible in a technical topic with verifiable facts, though possibly not. (The exercise is much easier if you’re on neither side, but can be more useful if you are.) Talk to people on both sides, to drill down to what words they may be using with different meanings or hidden connotations and assumptions. Identify fundamental underlying concepts they actually disagree about, which may include such hidden assumptions. Try to “strongman” the theories on both sides, keeping only their very best arguments (though also recording their worst); use neutral parties or verifiable facts to assess the strength of arguments. Then, use criteria about good theories from chapter 1 to determine whether the better theories on either or both sides are failing to satisfy the properties of a good theory. After clarifying words and concepts and theories, make your own theory, possibly unifying concepts and arguments from the previous two, about the topic. Bonus: study the kind of bias that makes each party blind to the strength of some arguments from the other side, and to the weakness of some arguments from their own side.

4.1.1 Division of Labor🔗

4.1.2 First- to Fourth-class, Internal or External🔗

However, many languages offer no such internal notion of modules. Indeed modules are a complex and costly feature to design and implement, and few language designers and implementers will expend the necessary efforts toward it at the start of their language’s development; only the few that have success and see their codebase grow in size and complexity will generally bother to add a module system.4646Unless they develop their language within an existing modular framework for language-oriented programming, such as Racket, from which they inherit the module system.

When for the sake of “simplicity”, “elegance”, or ease of development or maintenance, support for modularity is left out of a language, or of an ecosystem around one or multiple languages, this language or ecosystem becomes but the weak kernel of a haphazard collection of tools and design patterns cobbled together to palliate this lack of internal modularity with external modularity. The result inevitably ends up growing increasingly complex, ugly, and hard to use, develop and maintain.

4.1.3 Criterion for Modularity🔗

A design is more modular if it enables developers to cooperate more while coordinating less compared to alternative designs that enable less cooperation or require more coordination, given some goals for developers, a space of changes they may be expected to enact in the future, etc. More ability to code one’s part, while requiring less knowledge about other people’s parts.4848Note how, in the great ledger of software development costs and benefits, coordination counts negatively, in the column of costs: coordination, whether by one-on-one communication, meetings, emails, documents, chat rooms, code comments, edicts principled or whimsical, reports, processes, etc., all take their toll on the developers’ resources. Hopefully, the coordination methods used come not only with benefits greater than the costs, but also with a greater profit (difference between benefits and costs) than possible alternative methods considering the total capital immobilized in the development process. However there is nothing automatic to that, contrary to the apparent belief of many a manager. If the benefits of active business practices in general tend to be commensurate with and superior to their costs, that is only the precarious result of market forces, through the feedback of businesses persisting in their bad practices losing resources and eventually stopping activity. Selection bias: we only observe the businesses still alive. But these market forces do not happen magically outside of human activity, or outside yourself: your actions partake in those market forces, and so will your going bankrupt if you persist in pursuing counter-productive practices.

For instance, the object-oriented design of the Common Lisp build system ASDF (Rideau 2014; Rideau and Goldman 2010) made it simple to configure, to extend, and to refactor to use algorithms in O(n) rather than O(n³) or worse, all without any of the clients having to change their code. This makes it arguably more modular than its predecessor MK-DEFSYSTEM (Kantrowitz 1991) that shunned the use of objects (possibly for portability reasons at the time), was notably hard to configure, and resisted several attempts to extend or refactor it.

Note that while external modularity enables cooperation during development, internal modularity also enables cooperation during deployment, with conditional selection and reconfiguration of modules, gradual deployment of features, user-defined composition of modules, automated A/B testing, and more.

For a more complete theory of Modularity, see Rideau (2016).

4.1.4 Historical Modularity Breakthroughs🔗

Programmers these days are very aware of files, and file hierarchies, as units of modularity they have to think about quite often, naming, opening, visiting and closing them in their editors, manipulating them in their source control, etc. Although files as such embody a form of modularity external to most simple programming languages that they use, the more advanced programming languages, that they use most often, tend to have some notion of those files, runtime and/or compile-time representation for those files, and often some correspondence between file names and names of internal module entities that result from compiling those files. In other words, for most languages that matter, files embody modularity internal to programming languages.4949Note that while a file may be a unit of modularity, this is not always the case: often, actual modules span multiple files; at other times, there may be multiple modules in a single file. For instance, compiling a C program typically requires each file to be registered into some “build” file (e.g. a Makefile) to be considered as part of the software; a C library also comes with an accompanying “header” file, though there need not be a 1-to-1 correspondence between C source files and C header files (as contrasted with source and interface files in OCaml). A C “module” therefore typically spans multiple files, and some files (headers and build files) can have bits from multiple modules. Of course, having to manually ensure consistency of information between multiple files makes the setup less modular than a language that doesn’t require as much maintenance. Then again, the C language also recently adopted some notion of namespace, which, though it doesn’t seem used that much in practice, can constitute yet another notion of modules, several of which can be present in a file. At a bigger scale, groups of files in one or multiple directories may constitute a library, and a “package” in a software “distribution” may include one or several libraries, etc. Thus, even within a single language, there can be many notions of modularity at several different scales of software construction, enabling division of labor across time for a single person, for a small team, for a large team, between several teams, etc., each time with different correspondences between modules and files, that are never quite 1-to-1: even “just a file” is not merely a blob of data, but also the meta-data of a filename registered in a broader namespace, and some intended usage.

Now, while files go back to the 1950s and hierarchical filesystems to the 1960s, there was an even earlier breakthrough in modularity, so pervasive that programmers use it without even thinking about using it: subroutines, already conceptualized by Ada Lovelace as “operations” (Lovelace 1843), formalized early on by Wilkes et al. in the 1940s used by the earliest programmers in manually assembled code, part of the first programming language Plankalkül, and of FORTRAN II. Subroutines allow programmers to divide bigger problems into smaller ones at a fine grain, that can each be solved by a different programmer, while other programmers only have to know its calling convention.

No less important than subroutines as such yet also taken for granted was the concept of a return address allowing calls to a single copy of a subroutine from multiple sites, and later of a call stack of such return addresses and other caller and callee data. The call stack enabled reentrancy of subroutines, such that a subroutine can be recursively called by a subroutine it itself called; thus, programmers do not have to care that their subroutines should not be reentered while being executed due to a direct or indirect subroutine call. Indeed, subroutines can now be reentered, not just accidentally, but intentionally, to express simpler recursive solutions to problems. The ability to cooperate more with less coordination with programmers from other parts of the software: that’s the very definition of modularity.

Sadly, the generalization of call stacks to first-class continuations in the 1970s, and later to delimited control in 1988 and beyond is still not available in most programming languages, eschewing another advance in modularity, wherein programmers could otherwise abstract over the execution of some fragment of code without having to worry about transformations to their control structure, e.g. for the sake of non-deterministic search, robust replaying of code in case of failure, security checks of code behavior, dynamic discovery and management of side-effects, etc.

On a different dimension, separately compiled object files, as implemented by FORTRAN (1956), provided third-class modularity through an external linker. Later developments like typechecked second-class Modules à la Modula-2 (1978), Higher-Order Modules à la ML (1985), typeclasses à la Haskell (or traits in Rust), interfaces à la Java, and much more, provided second-class modularity as part of a language itself. Finally, objects in Smalltalk-72 (even before Smalltalk adopted inheritance in 1976), or first-class modules in ML  (Russo 1998), provided first-class modularity.

4.1.5 Modularity and Complexity🔗

Modularity used correctly can tremendously simplify programs and improve their quality, by enabling the solutions to common problems to be solved once by experts at their best, and then shared by everyone, instead of the same problems being solved over and over, often badly, by amateurs or tired experts.

Use of modules also introduces overhead, though, at development time, compile-time and runtime alike: boiler plate to define and use modules, name management to juggle with all the modules, missing simplifications in using overly general solutions that are not specialized enough to the problems at hand, duplication of entities on both sides of each module’s interface, extra work to cover the “impedance mismatch” between the representation used by the common solution and that used by the actual problems, etc.

Modularity used incorrectly, with too many module boundaries, module boundaries drawn badly, resolved at the wrong evaluation stage, can increase complexity rather than reduce it: more parts and more crossings between parts cause more overhead; the factoring may fail to bring simplification in how programmers may reason about the system; subtle underdocumented interactions between features, especially involving implicit or mutable state, can increase the cognitive load of using the system; attempts at unifying mismatched concepts only to then re-distinguish them with lots of conditional behavior will cause confusion rather than enlightenment; modules may fail to offer code reuse between different situations; programmers may have to manage large interfaces to achieve small results.5050A notable trend in wrongheaded “modularity” is myopic designs, that achieve modest savings in a few modules under focus by vastly increasing the development costs left out of focus, in extra boilerplate and friction, in other modules having to adapt to the design, in inter-module glue being made more complex, or in module namespace curation getting more contentious. For instance, the once vastly overrated and overfunded notions “microkernels” or “microservices” consist in dividing a system in a lot of modules, “servers” or “services” each doing a relatively small task within a larger system, separated by extremely expensive hardware barriers wherein data is marshalled and unmarshalled across processes or across machines. Each service in isolation, that you may focus on, looks and is indeed simpler than the overall software combining those services; but this overall software kept out of focus was made significantly more complex by dividing it into those services. Another myopic design that is much rarer these days is to rewrite a program from a big monolithic heap of code in a higher level language into a lot of subroutines in a lower-level language (sometimes assembly language), boasting how vastly simpler each of these subroutines is to the previous program; yet obviously the sum total of those routines is much more complex to write and maintain than a similarly factored program written in an appropriate higher level language (that indeed the original language might not be). While myopic designs might offer some small performance improvement in terms of pipelining, locality and load-balancing for very large worksets, they offer no improvement whatsoever in terms of modularity, quite the contrary: (1) The modules must already exist or be made to exist at the language level, before the division into services may be enacted. Far from providing a solution to any problem for the programmer, these techniques require programmers to already have solved the important problem of module factoring before you can apply them, at which point they hinder rather than help. (2) Given the factoring of a program into modules, these techniques add runtime barriers that do not improve safety compared to compile-time barriers (e.g. using strong types, whether static or dynamic). (3) Yet those runtime barriers vastly decrease performance, and even more so by the compile-time optimizations they prevent (whether builtin or user-defined with e.g. macros). (4) The interface of each module is made larger for having to include a specific marshalling, and the constraints related to being marshalled. This problem can be alleviated by the use of “interface description languages”, but these languages tend to be both poorer and more complex than a good programming language’s typesystem, and introduce an impedance mismatch of their own. (5) Any alleged benefits from dividing in multiple distributed processes, whether in terms of failure-resistance, modularity, safety or performance are wholly lost if and when (as is often the case) persistent data all ends up being centralized in database services, that become a bottleneck for the dataflow. (6) The overall system is not made any smaller for being divided in smaller parts; actually, all the artificial process crossings, marshallings and unmarshallings, actually make the overall system noticeably larger in proportion to how small those parts are. Lots of small problems are added at both runtime and compile-time, while no actual problem whatsoever is solved. (7) These designs are thus actually detrimental in direct proportion to how much they are followed, and in proportion to how beneficial they claim to be. They are, technically, a lie. (8) In practice, “successful” microkernels import all services into a monolithic “single server”, and successful microservices are eventually successfully rebuilt as vertically integrated single services. In the end, the technical justification for these misguided designs stem from the inability to think about meta-levels and distinguish between compile-time and runtime organization of code: Modularity is a matter of semantics, as manipulated by programmers at programming-time, and by compilers at compile-time; the runtime barrier crossings of these myopic designs cannot conceivably do anything to help about that, only hinder. Now, there are sometimes quite valid socio-economical (and not technical) justifications to dividing a program into multiple services: when there are many teams having distinct incentives, feedback loops, responsibilities, service level agreements they are financially accountable for, etc., it makes sense for them to deploy distinct services. Indeed, Conway’s Law states that the technical architecture of software follows its business or management architecture. Finally, it is of note that some systems take a radically opposite approach to modularity, or lack thereof: instead of gratuitous division into ever more counter-productive modules, some prefer wanton avoidance of having to divide code into modules at all. For instance, APL reduces the need for modules or even subroutines by being extremely terse, and by shunning abstraction in favor of concrete low-level data representations (on top of its high-level virtual machine rather than of the lower-level model of more popular languages), to the point of replacing many routine names by common idioms—known sequences of combinators. (The many talks by Aaron Hsu at LambdaConf are an amazing glimpse at this style of programming.) The programmer can then directly express the concepts of the domain being implemented in terms of concrete APL’s tables and functions, stripped of all the unnecessary abstractions, until the solution is both so simple and task-specific that there is no need for shared modules. By using his terse combinators to directly manipulate entire tables of data at a time, a competent APLer can find a complete solution to a problem in fewer lines of code than it takes for programmers in other languages just to name the structures, their fields and accessors. Admittedly, there is only so much room in this direction: as the software grows in scope, and the required features grow in intrinsic complexity, there is a point at which it is becomes big to fit wholly in any programmer’s mind, then it must be chipped away by moving parts into other modules, notably by reusing common algorithms and data structures from libraries rather than inline specialized versions. But in practice, a lot of problems can be tackled this way by bright enough developers, especially after having been divided into subproblems for socio-economic reasons.

4.1.6 Implementing Modularity🔗

To achieve modularity, the specification for a software computation is divided into independently specified modules. Modules may reference other modules and the subcomputations they define, potentially specified by many different people at different times, including in the future. These references happen through a module context, a data structure with many fields or subfields that refer to each module, submodule, or subcomputation specified therein. When comes time to integrate all the module specifications into a complete computation, then comes the problem of implementing the circularity between the definition of the module context and the definitions of those modules.

With third-class modularity, the module context and modules are resolved before the language processor starts, by whatever preprocessor external to the language generates the program. With second-class internal modularity, they are resolved by some passes of the language-internal processor, before the program starts. In either of the above cases, a whole-program optimizer might fully resolve those modules such that no trace of them is left at runtime. Without a whole-program optimizer, compilers usually generate global linkage tables for the module context, that will be resolved statically by a static linker when producing an executable file, or dynamically by a dynamic loader when loading shared object files, in either case, before any of the programmer’s regular code is run (though some hooks may be provided for low-level programmer-specified initialization).

At the other extreme, all third-class or second-class module evaluation may be deferred until runtime, the runtime result being no different than if first-class internal modularity was used, though there might be benefits to keeping modularity compile-time only in terms of program analysis, synthesis or transformation. For local or first-class modules, compilers usually generate some kind of “virtual method dispatch table” (or simply “virtual table” or “dispatch table” or some such) for each modularly defined entity, that, if it cannot resolve statically, will exist as such at runtime. Thus, Haskell typeclasses become “dictionaries” that may or may not be fully inlined. In the case of OO, prototypes are indeed typically represented by such “dispatch table” at runtime—which in Class OO would be the type descriptor for each object, carried at runtime for dynamic dispatch.

In a low-level computation with pointers into mutable memory, the module context is often being accessed through a global variable, or if not global, passed to functions implementing each module as a special context argument, and each field or subfield is initialized through side-effects, often with some static protocol to ensure that they are (hopefully, often all) initialized before they are used. In a high-level computation without mutation, each module is implemented as a function taking the module context as argument, the fields are implemented as functional lenses, and the mutual recursion is achieved using a fixpoint combinator; lazy evaluation may be used as a dynamic protocol to ensure that each field is initialized before it is used.5151It is hard to ensure initialization before use; a powerful enough language makes it impossible to predict whether that will be the case. In unsafe languages, your program will happily load nonsensical values from uninitialized bindings, then silently corrupt the entire memory image, “dance a fandango on core”  (Raymond and others 1996), cause a segmentation fault and other low-level failures, or even worse, veer off into arbitrary undefined behavior and yield catastrophically wrong results to unsuspecting users. The symptoms, if any, are seen long after the invalid use-before-init, making the issue hard to pin-point and debugging extremely difficult unless you have access to time-travel debugging at many levels of abstraction. In not-so-safe languages, a magic NULL value is used, or for the same semantics just with additional syntactic hurdles, you may be forced to use some option type; or you may have to use (and sometimes provide out of thin air) some default value that will eventually prove wrong. In the end, your program will fail with some exception, which may happen long after the invalid use-before-init, but at least the symptoms will be visible and you’ll have a vague idea what happened, just no idea where or when. Actually safe languages, when they can’t prove init-before-use, will maintain and check a special “unbound” marker in the binding cell or next to it, possibly even in a concurrency-protected way if appropriate, to identify which bindings were or weren’t initialized already, and eagerly raise an exception immediately at the point of use-before-init, ensuring the programmer can then easily identify where and when the issue is happening, with complete contextual information. In even safer languages, lazy evaluation automatically ensures that you always have init-before-use, and if the compiler is well done may even detect and properly report finite dependency cycles; you may still experience resource exhaustion if you generate infinite new dynamic dependencies, but so would you in the less safe alternatives if you could reach that point. Safest languages may require you to statically prove init-before-use in finite time, which may be very hard with full dependent types, or very constraining with a more limited proof system, possibly forcing you to fall back to only the “not-so-safe” alternative. But this technology is onerous and not usable by programmers at large. Some languages may let you choose between several of these operation modes depending on compilation settings or program annotations. Interestingly, whichever safety mode is used, programmers have to manually follow some protocol to ensure init-before-use. However the lazy evaluation approach minimizes artificial constraints on such protocol, that when not sensible might force them to fall back to the not-so-safe variant. The init-before-use issue is well-known and exists outside of OO: it may happen whenever there is mutual recursion between variables or initial elements of data structures. However, we’ll see that “open recursion”  (Cardelli 1992; Pierce 2002), i.e. the use of operators meant to be the argument of a fixpoint combinator, but also possibly composition before fixpointing, is ubiquitous in OO, wherein partial specifications define methods that use other methods that are yet to be defined in other partial specifications, that may or may not follow any particular protocol for initialization order. Thus we see that the simplest, most natural and safest usable setting for OO is: lazy evaluation. This may come at a surprise to many who mistakenly believe the essence of OO is in the domain it is commonly applied to (defining mutable data structures and accompanying functions as “classes”), rather than in the semantic mechanism that is being applied to these domains (extensible modular definitions of arbitrary code using inheritance). But this is no surprise to those who are deeply familiar with C++ templates, Jsonnet or Nix, and other systems that allow programmers to directly use unrestricted OO in a more fundamental purely functional setting wherein OO can be leveraged into arbitrary programming and metaprogramming, not just for “classes” stricto sensu. In the next subsection, I argue the case from the point of view of modularity rather than initialization safety; however, both can be seen as two aspects of the same argument about semantics.


The more programmers must agree on a protocol to follow, the less modular the approach. In a stateful applicative language, where the various modular definitions are initialized by side-effects, programmers need to follow some rigid protocol that may not be expressive enough to capture the modular dependencies between internal definitions, often leading to indirect solutions like “builder” classes in Java, that stage all the complex computations before the initialization of objects of the actually desired class.

Exercise 4.1 (Easy) Identify languages with each of first-class, second-class, third-class and fourth-class module systems. Maybe the same language across the years.

Exercise 4.2 (Easy) Pick one of the modularity breakthroughs I listed. Does it actually make code more modular? Compare code written without said breakthrough to code written with it, and how much that code needs to be modified to accommodate for a desired change.

Exercise 4.3 (Easy) Consider software projects you have written or used. Identify what are the units of modularity, and for each unit, what are its interface vs its implementation. How much of the interface is formal, versus how much is informal?

Exercise 4.4 (Easy) Consider various programming interactions you are having with colleagues, members of a community, or authors of libraries. How much do you and other people have to synchronize for your software to work well with each other? Did you have to modify the code of other people’s software? To read the code? To read only an interface? What did they need to do with respect to your code? How much cooperation could you achieve, with how much coordination?

Exercise 4.5 (Medium) Use a preprocessor to achieve third-class modularity for a language lacking internal modularity, splitting code into many files. For instance, generate instructions for your LLM from a template that mixes project-specific instructions with generic and conditional shared instructions. Or, if you manage several Unix machines, generate some machine-wide (in /etc) or personal configuration file (in ~/.* of ~/.config/*) from a script specialized with machine-specific parameters.

Exercise 4.6 (Medium) Pick one of the features I list as making a language more modular, at random. Pick a language with the feature, and a program using that feature heavily. Explain how to reproduce the effect of that program without using the language feature. Does it indeed involve authors of part of a program having to learn more about other parts of the program, having to manually enforce more complex invariants?

Exercise 4.7 (Medium) Find an example of a system with too much modularity, or modularity where it doesn’t belong, actually making things worse.

Exercise 4.8 (Hard) Identify a language with some modularity features that are less modular than could be: the feature still requires programmers to manually curate redundancies within or across files, to tightly couple changes in multiple locations, etc. Use macros or a preprocessor to reduce the coupling and offer a more modular abstraction (though the language ecosystem will not become more modular without other people adopting this innovation).

Exercise 4.9 (Research) Find a more modular design pattern to use in an existing language ecosystem; possibly patch the language implementation, standard library, or key piece of infrastructure, to support this pattern. Provide backward compatibility for better results. See how hard it is not just to implement, but to get it adopted.

4.2.1 Extending an Entity🔗

Extensibility is the ability to take a software entity and create a new entity that includes all the functionality of the previous entity, and adds new functionality, refines existing functionality, or otherwise modifies the previous entity. Extensibility can be realized inside or outside of a programming language.

4.2.2 First-class to Fourth-class Extensibility🔗

External Extensibility is the ability to extend some software entity by taking its code then reading it, copying it, editing it, processing it, modifying it, (re)building it, etc. Extensibility is much easier given source code meant to be thus read and written, but is still possible to reverse-engineer and patch binary code, though the process can be harder, less robust, less flexible and less reusable. Thus, external extensibility is always possible for any software written in any language, though it can be very costly, in the worst case as costly as rewriting the entire extended program from scratch. When done automatically, it’s third-class extensibility. When done manually, it’s fourth-class extensibility. The automation need not be written in the same language as the software being extended, or as its usual language processor, though either may often be the case.

Internal or Intra-linguistic extensibility, either first-class or second-class, by contrast, is the ability to extend, refine or modify a software entity without having to read, rewrite, or modify any of the previous functionality, indeed without having to know how it works or have access to its source code, only having to write the additions, refinements and modifications. Second-class extensibility happens only at compile-time, and is quite restricted, but enables more compiler optimizations and better developer tooling. First-class extensibility may happen at runtime, and is less restricted than second-class extensibility but more so than external extensibility in terms of what modifications it affordably enables, yet less restricted than either in terms of enabling last-minute customization based on all the information available to the program.

These notions of extensibility are complementary and not opposite, for often to extend a program, you will first extract from the existing code a shared subset that can be used as a library (which is an extra-linguistic extension), and rewrite both the old and new functionality as extensions of that library (which is an intra-linguistic extension), as much as possible at compile-time for efficiency (which is second-class extensibility), yet enough at runtime to cover your needs (which is first-class extensibility).

Finally, as with modularity, the lines between “external” and “internal”, or between “second-class” and “first-class”, can often be blurred by reflection and “live” interactive environments. But these demarcations are not clear-cut objective features of physical human-computer interactions. They are subjective features of the way humans plan and analyze those interactions. To end-users who won’t look inside programs, first-class, second-class, third-class, and if sufficiently helpless even fourth-class, are all the same: things they cannot change. For adventurous hackers willing to look under the hood of the compiler and the operating system, first-class to fourth-class are also all the same: things they can change and automate, even when playing with otherwise “dead” programs on “regular” computing systems. The demarcations are still useful though: division of labor can be facilitated or inhibited by software architecture. A system that empowers an end-user to make the simple changes they need and understand, might prove much more economical than a largely equivalent system that requires a high-agency world expert to make an analogous change.

4.2.3 A Criterion for Extensibility🔗

A design is more extensible if it enables developers to enact more kinds of change through smaller, more local modifications compared to alternative designs that require larger (costlier) rewrites or more global modifications, or that prohibit change (equivalent to making its cost infinite).

Extensibility should be understood within a framework of what changes are or aren’t “small” for a human (or AI?) developer, rather than for a fast and mindless algorithm.

Thus, for instance, changing some arithmetic calculations to use bignums (large variable-size integers) instead of fixnums (builtin fixed-size integers) in C demands a whole-program rewrite with non-local modifications to the program structure; in Java it involves changes throughout the code—straightforward but numerous—while preserving the local program structure; in Lisp it requires minimal local changes; and in Haskell it requires one local change only. Thus, with respect to this and similar kinds of change, if expected, Haskell is more extensible than Lisp, which is more extensible than Java, which is more extensible than C.

Extensibility does not necessarily mean that a complex addition or refactoring can be done in a single small change. Rather, code evolution can be achieved through many small changes, where the system assists developers by allowing them to focus on only one small change at a time, while the system tracks down the remaining necessary adjustments.

For instance, a rich static typesystem can often serve as a tool to guide large refactorings by dividing them into manageably small steps—as extra-linguistic code modifications—making the typechecker happy one redefinition at a time after an initial type modification. This example also illustrates how Extensibility and Modularity usually happen through meta-linguistic mechanisms rather than linguistic ones, i.e. through tooling outside the language rather than through expressions inside the language. Even then, internalizing the locus of such extensible modularity within the language enables dynamic extension, runtime code sharing and user-guided specialization as intra-linguistic deployment processes that leverage the result of the extra-linguistic development process.

4.2.4 Historical Extensibility Breakthroughs🔗

While any software is externally extensible by patching the executable binary, the invention of assembly code made it far easier to extend programs, especially with automatic offset calculations from labels. Compilers and interpreters that process source code meant for human consumption and production, along with preprocessors, interactive editors, and all kinds of software tooling, greatly facilitated external extensibility, too. Meanwhile, software that requires configuration through many files that must be carefully and manually kept in synch is less extensible than one configurable through a single file from which all required changes are automatically propagated coherently (whether that configuration is internal or external, first-class to fourth-class). Whenever multiple files must be modified together (such as interface and implementation files in many languages), the true units of modularity (or in this case extensibility) are not the individual files—but each group of files that must be modified in tandem; and sometimes, the units of extensibility are entities that span parts of multiple files, which is even more cumbersome.

Higher-level languages facilitate external extensibility compared to lower-level ones, by enabling programmers to achieve larger effects they desire through smaller, more local changes that cost them less. Thus, FORTRAN enables more code extensibility than assembly, and Haskell more than FORTRAN. Languages with higher-order functions or object orientation enable greater internal extensibility by allowing the creation of new in-language entities built from existing ones in more powerful ways. To demonstrate how OO enables more extensibility, consider a course or library about increasingly more sophisticated data structures: when using a functional language with simple Hindley-Milner typechecking, each variant requires a near-complete rewrite from scratch of the data structure and all associated functions; but when using OO, each variant can be expressed as a refinement of previous variants with only a few targeted changes.

4.2.5 Extensibility without Modularity🔗

Before delving deeply into how OO brings together extensibility and modularity, it is worth explaining what extensibility without modularity means.

Operating Systems, applications or games sometimes deliver updates via binary patch formats that minimize data transmitted while maximizing changes effected to the software. Such patches embody pure extensibility with total lack of modularity: they are meaningful only when applied to the exact previous version of the software. Text-based diff files can similarly serve as patches for source code, and are somewhat more modular, remaining applicable even in the presence of certain independent changes to the source code, yet are still not very modular overall: they are fragile and operate without respecting any semantic code interface; indeed their power to extend software lies precisely in their not having to respect such interfaces.

The ultimate in extensibility without modularity would be to specify modifications to the software as bytes concatenated at the end of a compressed stream (e.g. using gzip or some AI model) of the previous software: a few bits could specify maximally large changes, ones that can reuse large amounts of information from the compressor’s model of the software so far; yet those compressed bits would mean nothing outside the exact context of the compressor—maximum extensibility, minimum modularity.

Interestingly, these forms of external extensibility without modularity, while good for distributing software, are totally infeasible for humans to directly create: they vastly increase rather than decrease the cognitive load required to write software. Instead, humans use modular forms of extensibility, such as editing source code as part of an edit-evaluate-debug development loop, until they reach a new version of the software they want to release, after which point they use automated tools to extract from the modularly-achieved new version some non-modular compressed patches.

As for internal extensibility without modularity, UML, co-Algebras or relational modeling, as previously discussed in OO isn’t a Model of the World, fail to model OO precisely because the “classes” they specify are mere types: they lack the module context that enables self-reference in actual OO classes. As in-language entities, they can be extended by adding new attributes, but these attributes have to be constants: they may not contain any self-reference to the entity being defined and its attributes.

4.2.6 Extensibility and Complexity🔗

Extensibility of software entities means that variants of these software entities may be reused many times in as many different contexts  (Johnson and Foote 1988), so more software can be achieved for fewer efforts.

Now, external extensibility through editing (as opposed to e.g. preprocessing) means that these entities are “forked”, which in turn reintroduces complexity in the maintenance process, as propagating bug fixes and other changes to all the forks becomes all the harder as the number of copies increases. External extensibility through preprocessing, and internal extensibility, do not have this issue, and, if offered along a dimension that matters to users, enable the development of rich reusable libraries that overall decrease the complexity of the software development process.5252Interestingly, detractors of OO will often count “code reuse” as a bad aspect of OO: they will claim that they appreciate inheritance of interfaces, but not of implementation. Many OO language designers, as of Java or C#, will say the same of multiple inheritance though not of single inheritance. Yet, many practitioners of OO have no trouble reusing and extending libraries of OO classes and prototypes, including libraries that rely heavily on multiple inheritance for implementation. It is quite likely that users bitten by the complexities yet limitations of multiple inheritance in C++ or Ada may see that it does not bring benefits commensurable with its costs; and it is also quite likely that users fooled by the absurd “inheritance is subtyping” slogan found that code written under this premise does not quite work as advertised. These disgruntled users may then blame OO in general for the failings of these languages to implement OO, or for their believing false slogans and false lessons propagated by bad teachers of OO.

Note that often, the right way to reuse an existing software entity is not to reuse it as is (internal extensions), but first to refactor the code (external extensions) so that both the old and new code are extensions of some common library (internal extensions). Then the resulting code can be kept simple and easy to reason with. Internal and external extensibility are thus mutual friends, not mutual enemies.

By decreasing not only overall complexity, but the complexity of incremental changes, extensibility also supports shorter software development feedback loops, therefore more agile development. By contrast, without extensibility, developers may require more effort before any tangible incremental progress is achieved, leading to loss of direction, of motivation, of support from management and of buy-in from investors and customers. Extensibility can thus be essential to successful software development.

4.2.7 Implementing Extensibility🔗

To enable extensibility, a software entity must be represented in a way that allows semantic manipulation in dimensions meaningful to programmers. By the very nature of programming, any such representation is enough to enable arbitrary extensions, given a universal programming language, though some representations may be simpler to work with than others: they may enable programmers to express concisely and precisely the changes they want, at the correct level of abstraction, detailed enough that they expose the concepts at stake, yet not so detailed that the programmer is drowned in minutiae.

Now, in the case of second-class internal extensibility, or of first-class internal extensibility in a less-than-universal language, representations are no longer equivalent, as only a subset of computable extensions are possible. This kind of limited extensibility is not uncommon in computing systems; the restrictions can help keep the developers safe and simplify the work of language implementers; on the other hand, they may push developers with more advanced needs towards relying external extensibility instead, or picking an altogether different language.

In a pure functional model of extensibility, an extension is a function that takes the original unextended value and returns the modified extended value. In a stateful model of extensibility, an extension can instead be a procedure that takes a mutable reference, table or structure containing a value, and modifies it in-place to extend that value—sometimes using “hot-patches” that were not foreseen by the original programmer.

Exercise 4.10 (Easy) Find examples for first-class, second-class, third-class and third-class extensibility.

Exercise 4.12 (Medium) Which variants of extensibility above have you used? If you haven’t tried them all, can you try one you haven’t used before?

Exercise 4.13 (Medium) Consider various programming interactions you are having with colleagues, members of a community, or authors of libraries. What are pieces of software you might want to extend but cannot extend in practice without reimplementing it completely? What prevents you? How could you (or the original authors) modify the software to make it more extensible?

Exercise 4.14 (Hard) Use some text-processing tools to achieve third-class extensibility for a language lacking internal extensibility, by programmatically extending some existing code without modifying the original function. You may insert markers in the original code for where things should be edited, without modifying its semantics; the third-class extension should use those markers, or contextual information, to generate modified code that extends the original one; simple modifications to the original file should be automatically reflected in the extended file after re-running the third-class extension. Notice how much harder this is than with modularity, because you have to deal non-trivially with programs as input, not just output.

Exercise 4.15 (Hard) With the help of an AI if needed, write a simple numerical program, say polynomial interpolation using Newton’s or Lagrange’s method, with floating point numbers. How much do you need to modify it to work with arbitrary-precision rational numbers? With numbers from finite field F_q, yielding a Reed-Solomon code (say with q=256)? Can you write a version that shares the logic between different number fields, and gets instantiated into a variant with a specific field in a single line, or two to the most? Compare the situation in C, Java, Lisp, Haskell.

Exercise 4.16 (Research) Identify some existing software you actually use, that should be internally extensible in some way, but isn’t. Formalize a reasonable use case as code that ought to work if it were indeed extensible. Propose a change making the software extensible that way, that would make your use case actually work. Implement the change, enjoy your extension. Get your change accepted upstream by the maintainers.

4.3.1 A Dynamic Duo🔗

Modularity and Extensibility work hand in hand: Modularity means you only need to know a small amount of old information to make software progress. Extensibility means you only need to contribute a small amount of new information to make software progress. Together they mean that one or many finite-brained developers can better divide work across time and between each other, and make more software progress with a modular and extensible design, tackling larger problems while using less mental power each, compared with using less-modular and less-extensible programming language designs. Together they enable the organic development of cooperative systems that grow with each programmer’s needs without getting bogged down in coordination issues.

Remarkably, though, you can have each of modularity and extensibility separately, and that isn’t the same as having the two together. For instance, first-class modules in ML are units of modularity, on which you can do dynamic dispatch, and that you can transform with “functors”, functions that take modules as parameters and return modules as a result. But somehow you cannot define an extension in a modular way. First-class modules, while units of modularity with respect to dispatch, and units of extension with respect to functors, remain second-class with respect one crucial aspect of modularity: resolving many modular definitions from many people together into a single program.

Early examples of Modularity and Extensibility together that pre-date fully-formed OO include of course classes in Simula 1967  (Dahl and Nygaard 1967), but also precursor breakthroughs like the “locator words” of the Burroughs B5000  (Barton 1961; Lonergan and King 1961), and Ivan Sutherland’s Sketchpad’s “masters and instances”  (Sutherland 1963), that both inspired Kay, or Warren Teitelman’s Pilot’s ADVISE facility  (Teitelman 1966), that was influential at least in the Lisp community and led to method combination in Flavors and CLOS.5353There were definitely exchanges between the Smalltalk and Interlisp teams at PARC: In the 1970s, Kay got “inheritance” from Bobrow’s KRL, who in return got “object-oriented” and applied inheritance to procedures. Lispers quickly copied Kay’s OO design as a mechanism to define code rather than just to represent data. In the 1980s Bobrow did work on Smalltalk projects like PIE as well as Lisp projects like LOOPS, but it seems that—maybe after Kay’s and many others’ departure from PARC—the Smalltalk team stopped following or understanding OO developments from the Lisp world, and Interlisp had much more influence on the MIT Lispers than on the co-located Smalltalkers.

4.3.2 Modular Extensible Specifications🔗

A modular extensible specification specifies how to extend a previous value, but in a modular way: the extension is able to use some modular context to refer to values defined and extended by other pieces of code.

At this point, I reach the end of what can be clearly explained while remaining informal. I must introduce a formal model of modularity, extensibility, and the two together, to further convey the ideas behind OO without resorting to handwaving. The last task to carry informally is therefore a justification of my approach to formalization.

4.4.1 Why a Formal Model?🔗

The current section was largely appealing to well-established concepts in Computing. Inasmuch as it can be understood, it is only because I expect my readers to be seasoned programmers and scientists familiar with those concepts. My most complex explanations were in terms of functions from a modular context to a value, or from some (original) value to another (extended) value (of essentially the same type). As I try to combine these kinds of functions, the complexity is greater than can be explained away in a few words, and the devil will be in the details.

A formal model allows one to precisely define and discuss the building blocks of OO, in a way that is clear and unambiguous to everyone. This is all the more important when prevailing discourse about OO is full of handwaving, imprecision, ambiguity, confusions, and identical words used with crucially different meanings by different people.

4.4.2 Why a Minimal Model?🔗

If I can express classes in terms of prototypes, prototypes in terms of specifications, or multiple and single inheritance in terms of mixin inheritance, then I must do so, until I reduce OO to its simplest expression, and identify the most fundamental building blocks within it, from which all the usual concepts can be reconstituted, explained, justified, evaluated, generalized, and maybe even improved upon.

4.4.3 Why Functional Programming?🔗

Functional Programming (FP) is a computational model directly related to formal or mathematical logic whereby one can precisely reason about programs, their semantics (what they mean), how they behave, etc. The famous Curry-Howard Correspondence establishes a direct relationship between the terms of the λ-calculus that is the foundation of FP, and the rules of logical deduction. That correspondence can also be extended to cover the Categories of mathematics, and more.

Therefore, in an essential sense, FP is indeed the “simplest” paradigm in which to describe the semantics of OO and other programming paradigms: it is simultaneously amenable to both computation and reasoning with the least amount of scaffolding for bridging between the two.

4.4.4 Why an Executable Model?🔗

While I could achieve a slightly simpler algorithmic model by using a theoretical variant of the λ-calculus, I and other people would not be able to directly run and test my algorithms without a costly and error-prone layer of translation or interpretation.

A actual programming language that while very close to the λ-calculus comes with both additional features and additional restrictions, will introduce some complexity, and a barrier to entry to people not familiar with this particular language. But it will make it easy for me and my readers to run, to test, to debug, and to interact with the code I offer in this book, and to develop an intuition on how it runs and what it does, and later to extend and to adapt it.

My code will also provide a baseline for implementers who would want to use my ideas, and who may just port my code to their programming language of choice, and be able to debug their port by comparing its behavior to that of the original I provide. They can implement basic OO in two lines of code in any modern programming language, and have a full-featured OO system in a few hundreds of lines of code.

4.4.5 Why First-Class?🔗

The most popular form of OO is second-class, wherein all inheritance happens at compile-time when defining classes. But for some programmers to use OO as a second-class programming construct, language implementers still have to implement OO as a first-class construct within their compilers and other semantic processors. Anyone’s second-class entities are someone else’s first-class entities. And you still don’t fully understand those entities until you have implemented them, at which point they are first class. Thus, every useful minimal semantic model is always a first-class model, even if “only” for the implementation of a meta-level tool such as a typechecker.

4.4.6 What Precedents?🔗

I was flabbergasted when I first saw basic OO actually implemented in two function definitions, in the Nix standard library  (Simons 2015). These two definitions can be ultimately traced in a long indirect line to the pioneering formalization by Bracha and Cook  (Bracha and Cook 1990), though the author wasn’t aware of the lineage, or indeed even that he was doing OO;5454Peter Simons, who implemented prototypes as a user-level library in Nix as “extensions”, wrote in a private communication that he did not not know anything about their relationship to Prototypes, Mixins or OO, but semi-independently reinvented them and their use, inspired by the Haskell support code by Russell O’Connor, and by examples and discussions with Andres Löh and Conor McBride; These inspirers unlike Simons were well-versed in OO literature, though they are usually known to advocate FP over OO.


however, Nix also implements conflation, a crucial element missing from Bracha and Cook.

I will deconstruct and reconstruct this formalization. Then, on top of this foundation, I will be able to add all the usual concepts of OO, developed by their respective authors, whom I will cite.

4.4.7 Why Scheme?🔗

The Algorithmic Language Scheme is a minimal language built around a variant of the applicative λ-calculus, as a dialect in the wider tradition of LISP. It has many implementations, dialects and close cousins, a lot of documentation, modern libraries, decades of established lore, code base, user base, academic recognition. It also has macro systems that allow you to tailor the syntax of the language to your needs.

Some other languages, like ML or Haskell, are closer to the theoretical λ-calculus, but come with builtin typesystems that are way too inexpressive to accept the λ-terms I use. I suspect that systems with dependent types, such as in Rocq, Agda or Lean, are sufficiently expressive, but the types involved might be unwieldy and would make it harder to explain the basic concepts I present. I leave it as an exercise to the reader to port my code to such platforms, and look forward to the result.

Nix, that directly provides λ-calculus with dynamic typing, is lazy, which actually makes the basic concepts simpler. But it would require more care for implementers trying to port such an implementation to most programming contexts that are applicative. Also, Nix is more recent, less well-known, its syntax and semantics less recognizable; the Lindy effect means it will probably disappear sooner than Scheme, making this book harder to read for potential readers across time. Finally, Nix as compared to Scheme, is missing a key feature beyond the basic λ-calculus, that I will use when building multiple inheritance: the ability to test two specifications for equality.

Therefore, I pick Scheme as the best compromise in which to formalize OO.

Exercise 4.17 (Easy, Required) Install on your computer an implementation of the programming language Scheme, read the tutorial (if necessary), and play with it. I personally use Gerbil Scheme  (Vyzovitis 2016); but if you are a beginner, you will probably find it much easier to use the closely related language Racket  (Felleisen et al. 2015); or for a plain Scheme experience, we recommend Chez Scheme, that is very fast. You can also play with it on websites like replit. Another option is for you to do all exercises in your own programming language of choice, which will be much easier if your language at least support first-class higher-order functions, and either dynamic typing, or recursively constrained (sub)types; you’re on your own to translate the problems and their solutions in said language of your choice.

Exercise 4.18 (Easy, Required) Locate file util/pommette.scm that comes with the source code for this book, e.g. at https://github.com/metareflection/poof. It contains all the examples in the book, and more, so you can run them, copy/paste them, modify them, play with with them, etc. See in the Makefile how to run it with your favorite implementation (currently supported: Gerbil Scheme, Chez Scheme, Racket).

Exercise 4.19 (Medium, Recommended) If you are not yet familiar with the λ-calculus, read a tutorial about it, for instance Bertot (2015). You don’t have to absorb the entire Barendregt and others (1984) though. Just understand the basics, how they map to higher-order functions in your favorite language, or how to implement them (e.g. as “closures”) if not available in said favorite language. Your language tutorial might already include a section on such functions.

Exercise 4.20 (Medium, Recommended) If you did exercise 3.10, compare your previous answers with mine. See what surprised you—what you agreed and disagreed with before you read this chapter, and how your understanding has evolved already.

Exercise 4.21 (Hard, Recommended) Based on this informal explanation of modularity and extensibility, and before you read the next chapter, build your own minimal models of what “modularity” and “extensibility” could mean in terms of pure functional programming with first-class entities, which would be “internality”. In each case, make a first model that can adequately describe what you think it means; then strip it to the barest minimum, removing any feature not strictly necessary, anything that couldn’t be implemented by specializing a function argument, refactoring it down until nothing can be removed. Bonus if you can then put them together to mean something greater than either apart. Save your answer to compare with the treatment in Minimal OO.

5.1.1 Extensions as Functions🔗

I will start by formalizing First-Class Extensibility in pure FP, as it will be easier than modularity, and a good warmup. To make it clearer what kind of computational objects I am talking about, I will be using semi-formal types as fourth-class entities, i.e. purely as design-patterns to be enforced by humans. I leave a coherent typesystem as an exercise to the reader, though I will offer some guidance and references to relevant literature (see Types for OO).

Now, to extend to some computation returning some value of type V, is simply to do some more computation, starting from that value, and returning some extended value of some possibly different type W. Thus, in general an “extension” is actually an arbitrary transformation, which in FP, will be modeled as a function of type V → W.

However, under a stricter notion of extension, W must be the same as V or a subtype thereof: you can add or refine type information about the entity being extended, or adjust it in minor ways; you may not invalidate the information specified so far, at least none of the information encoded in the type. When that is the case, I will then speak of a “strict extension”.

Obviously, if types are allowed to be too precise, then any value v is, among other things, an element of the singleton type that contains only v, at which point the only allowed transformation is a constant non-transformation. Still, in a system in which developers can explicitly declare the information they intend to be preserved, as a type V if any (which funnily is non-trivial if not Any), it makes sense to require only extensions that strictly respect that type, i.e. functions of type V → V, or W ⊂ V ⇒ V → W (meaning V → W under the constraint that W is a subtype of V, for some type W to be declared, in which case the function is also of type V → V).5555And even without static types, the pure lazy functional language Jsonnet  (Cunningham 2014) allows programmers to specify dynamically checked constraints that objects must satisfy after they are instantiated (if they are, lazily). These constraints can ensure a runtime error is issued when a desired invariant is broken, and cannot be disabled or removed by inheriting objects. They can be used to enforce the same invariants as types could, and richer invariants too, albeit at runtime only and not at compile-time.

5.1.2 Coloring a Point🔗

5.1.3 Extending Arbitrary Values🔗

A record (indexed product) is just a common case because it can be used to encode anything. Mathematicians will tell you that products (indexed or not) give a nice “cartesian closed” categorical structure to the set of types for values being extended. What it means in the end is that you can decompose your specifications into elementary aspects that you can combine together in a record of how each aspect is extended.

5.1.4 Applying or Composing Extensions🔗

The ultimate purpose of an extension ext is to be applied to some value val, which in Scheme syntax is written (ext val).

Now if I were discussing second-class extensions in a restricted compile-time language, composition might not be definable, and not expressible unless available as a primitive. That would make extensions a poorer algebra than if they could be composed. With composition, strict extensions for a given type of values are a monoid (and general extensions are a category). Without composition, extensions are just disjointed second-class constants without structure. I will show later that this explains why in a second-class setting, Single inheritance is less expressive than mixin inheritance and multiple inheritance.

5.1.5 Top Value🔗

Now, sooner or later, composed or by itself, the point of an extension is to be applied to some value. When specifying software in terms of extensions, what should the initial base value be, to which extensions are applied? One solution is for users to be required to somehow specify an arbitrary base value, in addition to the extension they use.

A better solution is to identify some default value containing the minimum amount of information for the base type V that is being strictly extended. Each extension then transforms its “inherited” input value into the desired extended output value, possibly refining the type V along the way, such that the initial type is the “top” type of this refinement hierarchy. The initial base value is also called a “top value” ⊤, and somewhat depends on what monoidal operation is used to extend it as well as the domain type of values.

• For the type Record of records, ⊤ = empty-record the empty record.

• For the type Number of numbers, ⊤ = 0 if seen additively, or 1 if seen multiplicatively, or -∞ (IEEE floating-point number) seen with max as the operator, or +∞ with min.

• For the type Pointer of pointers into a graph of records, ⊤ = null, the universal null pointer.5656Hoare called his 1965 invention of null his “billion dollar mistake”  (Hoare 1965, 2009). Now, to Hoare’s credit, his invention of classes in the same article, for which he vaguely suggests the semantics of single inheritance as Dahl and Nygaard would implement after his article, yet that he (and they) wrongfully assimilate to subtyping, was a trillion dollar happy mistake. Overall, the effect of his article  (Hoare 1965) was probably net vastly positive.
  
  
  

• For the type Type of types (in a compiler, at the meta-level), ⊤ = Any, the top type (“contains everything, about which you know nothing”) that you refine, or the bottom type ⊥ = Nothing (“contains nothing, about which you know everything”) that you extend.

• For any function type in a language with partial functions, ⊤ = abort, a function that never returns regularly, and instead always aborts regular evaluation and/or throws an error.

• For the type Lazy of lazy computations, which would be an appropriate default in a language with lazy evaluation, even and especially a pure functional language with partial functions, such as Haskell or Nix, ⊤ = (lazy ⊥) is a universal top value, where ⊥ = (abort) is a computation that never returns (but may issue an abnormal termination, if the language supports that). Indeed, (lazy ⊥) carries no useful information but can be passed around, and has “negative infinite” information if you try to force, open or dereference it, which is much less than the 0 information provided by a regular null value. In Scheme, one may explicitly use the delay primitive to express such laziness, though you must then explicitly force the resulting value rather than having the language implicitly force computations whenever needed.

• Last but not least for the type Any of arbitrary values of any type, which would be an appropriate default in a language with eager evaluation, any value could do as default, but often there is a more colloquial default. In C, you would use 0 in integer context and the NULL pointer in pointer context. In modern C++, similarly but with the nullptr instead of NULL. In Java, null. In Lisp, NIL. In Scheme, the false boolean #f, or, in some dialects, a special unit value (void) (the null value ’() being traditionally used only for lists). In JavaScript, undefined, null or an empty record {}. In Python, None. Various languages may each offer some value that is easier to work with as a default, or some library may offer an arbitrary value to use as such. Some strongly typed applicative languages will offer no universal such value, though, and then some ad hoc arbitrary value must be provided for each type used.

5.1.6 Here there is no Y🔗

Looking at the type signature (V → V) → V for the process of obtaining a value from a strict extension (and every extension is strict for the top type), one may be tempted to say “I know, this is the type of the fixpoint combinator Y” and propose the use of said combinator.

The idea would indeed work in many cases, as far as extracting a value goes: for any lazy type V (and similarly for function types), any extension that would return a useful result applied to (lazy ⊥) passing it as argument to the lazy Y combinator would also yield a result. And indeed the results will be the same if the extension wholly ignores its argument, as is often the intent in those situations. Typically, you’d compose extensions, with one “to the right” ignoring its argument, overriding any previous value (or lack thereof, as the default default is a bottom computation), and returning some default value that is more useful in context (including not being a bottom computation); further extensions “to the left” then build something useful from that default value.

However, if there is no such overriding extension, then the results would not necessarily be the same between applying the extension or passing it to Y. For instance, given the extension (λ (x) (lazy-cons 1 x)) for some lazy-cons function creating a co-inductive stream of computations (as opposed to an inductive list of values as with the regular Scheme cons), applying the extension to (lazy ⊥) yields a stream you can destructure once, yielding 1 as first value, and aborting with an error if you try to destructure the rest. Meanwhile, applying the Y combinator yields an infinite stream of 1’s.

Then comes the question of which answer is more appropriate. Using the Y combinator only applies to functions and lazy values, the latter being isomorphic to nullary functions that always return the same cached result; it doesn’t apply and therefore isn’t appropriate in the general case of eager values. Meanwhile, applying extensions to a top value is always appropriate; it also corresponds better to the idea of specifying a value by starting from no specific information then refining bit by bit until a final value is reached; it does require identifying a type-dependent top value to start from, but there is an obvious such value for the types where the fixpoint combinator applies; finally, it is easier to understand than a fixpoint combinator and arguably more intuitive.

All in all, the approach of applying extensions to a top value is far superior to the approach of using a fixpoint combinator for the purpose of extracting a value from an extension. Thus, as far as one cares about extensibility: here, there is no Y.5757With apologies to Primo Levi  (Levi 1947).

Exercise 5.1 (Easy) Discuss what top values may be appropriate or inappropriate for the follow types: boolean, string, comparison function, integer, floating-point number, point (record of two coordinates x and y), in Scheme, and/or in your favorite language. Justify your choices.

Exercise 5.2 (Easy) Write an extension for ASCII strings that downcases the contents (converts all letters to lowercase), and another that capitalizes the string (makes the first letter uppercase). Do the two extensions commute when you compose them? (i.e. are the results the same when you switch the order? or else does the order matter?)

Exercise 5.3 (Easy) Write an extension that takes records representing a rectangle of given length and width, that extend them with a new field area, being the area of the rectangle.

Exercise 5.4 (Medium) Write an “discount” extension (discount-spec percent), of the form (λ (_self price) ...) that takes a price and reduces it by some specified percentage. The percentage being a first argument to pass to the extension; or, if you want to be nitpicky, to the function that creates the actual extension as a closure. Note: using binary floating point numbers is malpractice in the context of accounting, that may get you fired or sued. Always use integers (multiples of the minor unit of accounting) or fixed-point decimal numbers (in terms of the major unit of accounting), and round to the nearest multiple of the applicable minor unit (e.g. one cent of a dollar, for retail prices in the USA in 2026).

Exercise 5.5 (Medium) The text argues against using Y combinator for extensibility. Create an example demonstrating the difference between applying an extension to a top value and using the Y combinator on the extension. Show a case where they produce different behaviors. Is the difference merely a matter of performance, or one of semantics? In your example, which best corresponds to the notion of extending a specification?5858Hint: you may define a lazy stream extension: (λ (x) (lazy-cons 1 x)). Apply it to top = (lazy ⊥) and compare the behavior to that of (Y f). What happens when you force the first few elements?

Exercise 5.6 (Hard) Identify some domain on which to apply extensibility: for instance, configuration files for a given program you use. Define an appropriate type for these configurations, a top value and some simple extensions for that types. If possible, reuse existing parsers and printers (e.g. for JSON, YAML, .INI, etc.), or else build simple ones.

5.2.1 Modeling Modularity (Overview)🔗

End-users are provided with a “linked” program as a resolved module context from which they can invoke a programmer-defined “main” entry-point with their choice of arguments.

5.2.2 Records🔗

Before I model modularity as such, I shall delve deeper into the modeling of records, that are the usual substrate for much of modularity.

Record Nomenclature I will follow Hoare  (Hoare 1965) in calling “record” the concrete representation of data that contains zero, one or many “fields”. A typical low-level implementation of records is as consecutive “words” (or “characters”) of “computer store” or “storage space”, all of them typically mutable. But for the sake of studying semantics rather than performance, this book will discuss higher-level implementations, immutable, and without notion of consecutive words. By contrast, Hoare uses “object” to refer to more abstract entities from the “problem” being “modeled”, and an “object” has higher-level “attributes”. An object and some or all of its attributes might be simply represented as a record and its fields, but other representations are possible.

Other authors at times have used other words for records or other representations of the same concept: struct, structure, data structure, object, table, hash-table, tuple, named tuple, product, indexed product, entity, rows, etc. Their fields in various traditions and contexts may have been called such things as: methods, slots, attributes, properties, members, variables, functions, bindings, entries, items, keys, elements, components, columns, etc. Mapping which terms are used in any given paper to those used in this or another paper is left as an exercise to the reader.

Typing Records I could be content with a simple type Record, but then every access would be require some kind of type casting. Instead, I will propose slightly more elaborate types.

Given types V, W, X... for values, I, J... for identifiers or other indexes, consider records or sets of bindings as values of an index product ∏R = i:I → Rᵢ wherein to each value i in the index set I, the record will associate a value of type Rᵢ, where R is a schema of types, a function from I to Type.

To simplify this model, a pure functional record of type ∏R can be viewed as a function indexed by the domain I of indexes to Rᵢ for each i. When invoked on a value not in I, the function may return any value, or diverge. To further simplify, and for the sake of modeling records as first-class functions, when using Scheme, for indexes I will use symbols (interned strings) instead of identifiers (that in Scheme are symbols enriched with scoping and provenance information, used for second-class macro-expansion).

Implementing Records I will call identifier some large or infinite type of values over which equality or inequality can be decided at runtime by using a suitable primitive, or calling a suitable function. Since I use Scheme for my examples, I will use the symbols for identifiers (that I will later extend with booleans), the equal? primitive for testing equality, and the (if condition then-clause else-clause) special form for conditionals. In other programming languages that lack symbols as a builtin functionality, they can be implemented as interned strings, or instead of them, uninterned strings or numbers can be used as identifiers. And if somehow you only care about the pure λ-calculus, there are many embeddings and encodings of booleans, unary or binary numbers, and lists or trees thereof, that will do.

Programming languages usually already provide some data structure for records with second-class identifiers, or “dictionaries” with first-class identifiers, or have some library that does. For instance, while the core Scheme language has no such data structure, each implementation tends to have its own extension for this purpose, and there are multiple standard extensions for records or hash tables. Be mindful, though, that mutable variants of these data structures (e.g. mutable hash-tables) may not be appropriate to use in the context of pure functional programming that I am currently discussing, though they might be used (with caution) in the context of mutable objects. Also, many papers and experiments use a linked list of (key, value) pairs, known in the Lisp tradition as an alist (association list), as a simple implementation for records; alists don’t scale beyond a few hundreds of elements, but don’t need to in the context of the present experiments. Nevertheless to make the semantics of records clear, I will provide a trivial purely functional implementation, that has even more scaling issues, but that is even simpler.

Note how this trivial implementation does not support getting a list of bindings, or removing a binding. Not only does one not need these features to implement OO,6060I generate HTML for my presentations using exactly this implementation strategy. The Scheme implementation I use has builtin record support, and there are now somewhat portable libraries for records in Scheme; but I made it a point to use a minimal portable object system to show the feasability and practicality of the approach; and this way the code can be directly ported to any language with higher-order functions.


they constitute a “reflection” API that if exposed would interfere with various compiler optimizations, the use of which is actively rejected when statically typing records. However, there are other reasons why my implementation is not practical for long-running programs: it leaks space when a binding is overridden, and the time to retrieve a binding is proportional to the total number of bindings (including overridden ones) instead of being logarithmic in the number of visible bindings only as it could be in a pure functional implementation based on balanced trees, or constant time, for a stateful implementation based on either known field offsets within an array, or hashing.6161The nitpicky would also account for an extra square root factor due to the limitations of physics (Ernerfeldt 2014).

Merging Records Given a list of bindings as pairs of an identifier and a value, you can define a record that maps each identifier to the value in the first binding with that identifier in the list, if any (or else, errors out, diverges, returns null, or does whatever a record does by default). Conversely, given a list of identifiers and a record, you can get a list of bindings as pairs of an identifier and the value that the record maps it to. Most practical implementations of records support extracting from a record the list of all identifiers it binds; but this “reflection” feature is not necessary for most uses of records, and indeed breaks the record abstraction that some typesystems enforce. Indeed, the trivial implementation I will use, wherein records are functions from identifier to value, doesn’t support this feature; and some more elaborate implementations will deliberately omit runtime reflection, and only support second-class knowledge of what identifiers are bound in a record.

Finally, given a list of records and for each record a set of identifiers (that may or may not be the set of all identifiers bound by it, possibly extracted via reflection), you can merge the records along those sets of identifiers, by converting in order each record to a list of bindings for its given set of identifiers, appending those lists, and converting the appended result to a record.

5.2.3 Modular definitions🔗

Now I can introduce and model the notion of modular definition: a modular definition is a way for a programmer to specify how to define an entity of some type E given some modular context, or just module context, of type C. The module context contains all the available software entities, that were defined in other modules by other programmers (or even by the same programmer, at different times, who doesn’t presently have to hold the details of them in their limited brain). And the simplest way to model a modular definition as a first-class value is as a function of type C → E, from module context to specified entity.6262A Haskeller may well interpret “modular” in this book as meaning “in the reader monad of a module context”, in that a modular something will be a function from the module context to that something. This is correct, but beware that this is only half the story. The other half is in what it means for something to be a module context, rather than any random bit of context. And we’ll see shortly that the answer involves open recursion and fixpoints. Informally, modular means that locally you’re dealing with part of a whole, and globally, the whole will be made out of the parts in the end.

Typically, the module context C is a set of bindings mapping identifiers to useful values, often functions and constants, whether builtin the language runtime or available in its standard library. Now, I already introduced types for such sets of bindings: record types. And as a language grows in use and scope, the module context will include further libraries from the language’s wider ecosystem, themselves seen as sets of bindings of their respective record types, accessed hierarchically from a global module context, that now contains “modules” (records) as well as other values (or segregated from regular values at different levels of the module hierarchy). In any case, the global module context is typically a record of records, etc., and though many languages have special restrictions on modules as second-class entities, for my purpose of modeling the first-class semantics of modularity, I may as well consider that at runtime at least, a module is just a regular record, and so is the global module context, of type C = ∏R.

For instance, I could modularly specify a function ls-sorted that returns the sorted list of filenames (as strings) in a directory (as a string), from a module context of type ∏R that provides a function ls of type String → List(String) and a function sort that sorts a list of strings:

Note how in the above code snippet, I model records as functions from symbol to value, and to extract a binding from a record, one thus calls it with a symbol as single argument. The functions extracted are then chained together, as in the compose function I defined earlier (that I could have used if I extracted it from the module context, or could otherwise assume it was a language builtin).

5.2.4 Open Modular Definitions🔗

Now, programmers usually do not specify just a single entity of type E, but many entities, that they distinguish by associating them to identifiers. That is, they modularly define a module of type ∏P. A modular module definition is thus “just” a function from record to record: the input record is the modular context of type ∏R, and the output record is the specified module of type ∏P. I will say that the identifiers bound in ∏R are required by the modular definition (or referenced by it), whereas the identifiers bound in ∏P are provided by the modular definition (or defined by it).

In the end, programmers could somehow specify how their modular definition will extend the module context, with whatever merges they want, however deeply nested—which will lead them to modular extensibility. But for now, I will abstract over which strategy is used to assemble many modular definitions together.

5.2.5 Linking Modular Module Definitions: Y🔗

I will call a modular module definition “closed” when, after whatever assembly of individual modular definitions happened, it specifies the global module context of an entire program, wherein every entity required is also provided. A closed modular module definition is thus of type ∏R → ∏R.

Then comes the question: how can I, from a closed modular module definition, extract the actual value of the module context, of type ∏R, and thereby realize the program that was modularly specified?

This module realization function I am looking for is of type (C → C) → C where C = ∏R. Interestingly, I already mentioned a solution: the fixpoint combinator Y. And whereas it was the wrong solution to resolve extensions, it is precisely the right solution to resolve modular definitions: the Y combinator “ties the knots”, links each reference requiring an entity to the definition providing it, and closes all the open loops. It indeed does the same in a FP context that an object linker does in the lower-level imperative context of executable binaries: link references in open modular definitions to defined values in the closed result.

If there remain identifiers that are required but not provided, there will be an error—or non-termination, or some default value that will not make sense, at runtime, or at compile-time, depending on how sophisticated the exact implementation is (a typechecker might catch the missing requirement, for instance). If there remain identifiers that are provided but not required, and they are not otherwise (meant to) be used via reflection, then a “tree shaker” or global dead code optimizer may eliminate them.

5.2.6 Digression: Scheme and FP🔗

Function Arity Functional Programming usually is written with unary functions (that take exactly one argument), and to express more than one argument, you “curry” it: you define a function of one argument that returns a function that processes the next argument, etc., and when all the arguments are received you evaluate the desired function body. Then to apply a function to multiple arguments, you apply to the first argument, and apply the function returned to the second argument, etc. The syntax for defining and using such curried functions is somewhat heavy in Scheme, involving a lot of parentheses. By contrast, the usual convention for Functional Programming languages is to do away with these extra parentheses: in FP languages, two consecutive terms is function application, which is left-associative, so that or even just f x y is syntactic sugar for ((f x) y); and function definition is curried, so that λ x y . E is syntactic sugar for λ x . λ y . E.

Thus, there is some syntactic discrepancy that makes code written in the “native” Functional style look ugly and somewhat hard to follow in Scheme. Meanwhile, colloquial or “native” Scheme code may use any number of arguments as function arity, and even variable numbers of arguments, or, in some dialects, optional or keyword arguments, which does not map directly to mathematical variants of Functional Programming; but it is an error to call a function with the wrong number of arguments.

One approach to resolving this discrepancy is to just cope with the syntactic ugliness of unary functions in Scheme, and use them nonetheless, despite Lots of Insipid and Stupid Parentheses.6363Detractors of the Lisp language (that like many languages was customarily written in uppercase until the mid-1980s, and is usually capitalized since) and its many dialects and derivatives, among which Scheme is prominent, invented the backronym “Lots of Insipid and Stupid Parentheses” to deride its syntax. While Lispers sometimes yearn for terser syntax—and at least one famous Schemer, Aaron Hsu, jumped ship to APL—to them, the parentheses, while a bit verbose, are just a familiar universal syntax that allows them to quickly understand the basic structure of any program or data, even when they are unfamiliar with the syntactic extensions it uses. By contrast, in most “blub” languages, as Lispers call non-Lisp languages  (Graham 2001a), parentheses, beyond function calls, carry the emotional weight of “warning: this expression is complex, and doesn’t use the implicit order of operations”. Non-Lispers see parentheses as lacking cues from the other kinds of brackets their languages have; but these cues in Lisp are present, just in the head identifier of an expression. Matching parentheses can also be confusing, especially when not using the parentheses-aware, indentation-enforcing, semi-structured text editors that Lispers have been using since the 1970s, or when failing to format code properly (which those editors also help automate). Ironically, the syntactic and semantic abstraction powers of Lisp allow for programs that are significantly shorter than their equivalent in a mainstream language like Java, and as a result have not just fewer parentheses overall, but fewer brackets of any kind. It is therefore not the number of parentheses, but their density, that confuses mainstream programmer, due to unfamiliarity and emotional connotations. Now, it may well be that the same abstraction powers of Lisp make it unsuitable for a majority of programmers, incapable of mastering such abstraction. As an age of AI programmers approaches that will have abstraction powers vastly superior to the current average human programmer, it remains to be seen what kind of syntaxes will make them more efficient, when working in isolation, with each other, or with humans. And maybe even statistical AIs will need the rapid feedback of algorithmic editors to balance their parentheses.

A second approach is to adopt a more native Scheme style over FP style, with a variety of different function arities, making sure that a function is always called with the correct number of arguments. This approach blends best with the rest of the Scheme ecosystem, but may hurt the eyes of regular FP practitioners, and require extra discipline (or extra debugging) to use.

The macros defining λ, def and @ fit within fifty lines of code. Production-quality Scheme might use native Scheme style instead, for extra performance; but the performance penalty for curried code should remain relatively small, especially with a sufficiently optimizing compiler. I will thus write (f x y) where functional programmers write f x y or (f x) y, (λ (x y) expr) where functional programmers write λ x . λ y . expr or λ x y . expr, and (def (foo x y) expr) where functional programmers write foo x y = expr or f = λ x . λ y . expr. And the code will actually run in Scheme after a short prelude.

The second, major, issue with the applicative Y is that the pure applicative λ-calculus by itself has no provision for sharing non-fully-reduced computations, only for sharing (fully-reduced) values;6666You could of course emulate sharing by implementing state monadically, or through a virtual machine interpreter, inside the applicative λ-calculus, and then reimplementing your entire program on top of that richer calculus. But that would be a global transformation, not a local one, and in the end, it’s the new stateful paradigm you would be using, not the pure applicative λ-calculus anymore.


therefore the fixpoint computations are duplicated, and any information used along the way will have to be recomputed as many times as computations are duplicated, which can grow exponentially fast as the computation involves deeper sub-computations. In some cases, the eager evaluation may never terminate at all when lazy evaluation would, or not before the end of the universe. And of course, if there are any non-idempotent side effects, they too will be potentially duplicated a large number of times.

There are several potential alternatives to the practically inapplicable applicative Y combinator: (1) a stateful Y combinator, (2) a lazy Y combinator, or (3) a second-class Y combinator.

A third solution, often used in programming languages with second-class OO only (or languages in which first-class functions must terminate), is for the Y combinator (or its notional equivalent) to only be called at compile-time, as a metaprogram, and only on modular definitions that abide by some kind of structural restriction that guarantees the existence and well-formedness of a fixpoint, as well as e.g. induction principles to reason about said fixpoint. Also, the compile-time language processor usually doesn’t expose any side-effect to the user, such that there is no semantic difference whether its implementation is itself pure or impure, and uses a fixpoint combinator or any other representation for recursion. Since I am interested in first-class semantics for OO, I will ignore this solution in the rest of this book, and leave it as an exercise for the reader.

I have implemented variants of my minimal OO system in many combinations of the above solutions to these two issues, in Scheme and other languages. For the rest of this book, I will adopt a style where most functions are unary, but the syntax to define and use them implicitly uses curry with def and λ; I will also be assuming Y = Yes (eager, stateful) as my fixed-point operator, unless explicitly mentioned otherwise. As a result, the reader should be able both to easily copy and test all the code in this book at their favorite Scheme REPL, and also easily translate it to any other language that sports first-class higher-order functions.7070I can’t leave the topic of the Y combinator without citing Oleg’s fantastic page on the topic, even though it doesn’t directly address any of my concerns above: Kiselyov (2024).


.

And with these issues settled, I will close this digression and return to rebuilding OO from first principles.

5.3.1 Modular Extensions🔗

One can combine the above extensibility and modularity in a minimal meaningful way, as modular extensibility. I will call “modular extension” a modular definition for an extension. Thus, given a module context of type C (typically a record with C = ∏R), a type V for the “inherited” value being extended and W for the extended value being “provided”, an (open) modular extension is a function of type C → V → W. When W is the same as V, or a subtype thereof, I will call it a strict (open) modular extension. When W = V = ∏P for some record type ∏P, I will call it a modular module extension. When C = V = W, I will call it a closed modular extension, which as I will show can be used as a specification for a value of that type.

5.3.2 Composing Modular Extensions🔗

5.3.3 Closing Modular Extensions🔗

A closed modular extension is a function of type C → C → C, i.e. a modular extensible module specification where C = V = W. In the common case that C is a record, this means that an extension is provided for every identifier required.

5.3.4 Default and non-default Top Type🔗

5.3.5 Minimal OO Indeed🔗

The above functions mix and fix are indeed isomorphic to the theoretical model of OO from Bracha and Cook  (Bracha and Cook 1990) and to the actual implementation of “extensions” in nixpkgs  (Simons 2015).7474My presentation of mixin inheritance is actually slightly more general than what Bracha, Cook or Simons did define, in that my definition is not specialized for records. Indeed, my closed modular extensions work on values of any type; though indeed to fully enjoy modularity, modular extensions work better when the module context is a record, or somehow contains or encodes a record. But my theory also importantly considers not just closed modular extensions, but also the more general open modular extensions, for which it is essential that they universally apply to target values of any type, with a module context of any type. I can therefore claim as my innovation a wider, more general understanding of mixin inheritance, of which there is no evidence in earlier publications.


. This style of inheritance was dubbed “mixin inheritance” by Bracha and Cook;7575The name “mixin” originally comes from Flavors  (Cannon 1979), inspired by the ice cream offerings at Emack & Bolios. As for the concept itself, it was inspired both by previous attempts at multiple inheritance in KRL  (Bobrow and Winograd 1976) or ThingLab  (Borning 1977), combined with the ADVISE facility  (Teitelman 1966). However, Flavors offers full multiple inheritance (and was the first system to do it right), whereas the “mixins” of Bracha and Cook are a more rudimentary and more fundamental concept, that does not include automatic linearization of transitive dependencies. Also, “mixins” in Flavors are not distinguished by the language syntax or by the compiler; they are just abstract classes not meant to be instantiated, but to be inherited from (the word “abstract class” didn’t exist back then); a mixin in Flavors need not make sense as a base class, and can instead be inherited as part of many different hierarchies. Since the word implies no special processing by the compiler or by the human operator, it can be dispensed with in the original context, and gladly assigned a new, useful, technical meaning. But that doesn’t mean the context that made the word superfluous should be forgotten, quite the contrary. I will get back to Flavors when I discuss multiple inheritance.


and the two functions, that can easily be ported to any language with first-class functions, are enough to implement a complete object system.

Now, where performance or space matters, you would use an encoding of records-as-structures instead of records-as-functions. Then, instead of calling the record as a function with an identifier, you would invoke a dereference function with the record as first argument and the identifier as second argument. But with some small overhead, the records-as-functions encoding is perfectly usable for many simple applications.7676I notably use this technique to generate all my slides in a pure functional way in Racket (a close cousin of Scheme). Interestingly, I could define a generic specification for slides that indicate where they are in the presentation, highlighting the name of each new section in an otherwise constant list of all sections. That specification uses the self context to extract the list of sections in the presentation, including sections not yet defined. It might seem impossible in an eager language, and without side-effects, to import data from slides that will only be defined later into a whichever slide is being defined now; and yet the Y combinator achieves this feat, and although I use the stateful Y for performance, a pure applicative Y also works without too much slowdown, because the substructures I recursively examine remain shallow.


Also, in a more practical implementation, the inherited value in the field-spec would be made lazy, or would be wrapped in a thunk, to avoid unneeded computations (that might not even terminate); or for more power, the compute-value function would directly take super as its second argument, and (super method-id) would only be computed in the second branch. In a lazy context, lazy-field-spec could also directly use extend-lazy-record to add a binding to a record without having to eagerly compute the bound value.

Whichever way simple modular extensions are defined, they can thereafter be composed into larger modular extensions using the mix function, and eventually instantiate a target record from a modular extension using the fix function. Since I will be using records a lot, I will use the specialized fix-record function above. Note that since my targets are records, my minimal object system is closer to Prototype OO than to Class OO, though, as I will show, it doesn’t offer “prototypes” per se, or “objects” of any kind.

5.3.6 Minimal Colored Point🔗

5.3.7 Minimal Extensibility and Modularity Examples🔗

5.3.8 Interaction of Modularity and Extensibility🔗

Without extensibility, a modular module specification need never access the identifiers it specifies via the global module context (self), since it can more directly access or inline their local definition (though it may then have to explicitly call a fixpoint locally if the definitions are mutually recursive, instead of implicitly relying on a global fixpoint via the module context).

The interaction between modularity and extensibility therefore expands the scope of useful opportunities for modularity, compared to modularity without extensibility. Programming with modularity and extensibility is more modular than with modularity alone. This makes sense when you realize that when the software is divided into small modular extensions many of which conspire to define each bigger target, there are more modular entities than when there is only one modular entity for each of these bigger targets. Modular extensibility enables modularity at a finer grain.

There is another important shift between modularity alone and modularity with extensibility, that I quietly smuggled in so far, because it happened naturally when modeling first-class entities using FP. Yet this shift deserves to be explicitly noted, especially since it is not quite natural in other settings such as existed historically during the discovery of OO or still exist today for most programmers: Modularity alone was content with a single global module context that everyone linked into, but the whole point of extensibility is that you will have many entities that will be extended in multiple different ways; therefore when you combine the two, it becomes essential that module contexts be not a single global entity, but many local entities. This shift from singular and global to plural and local is essential for Class OO, and even more so for Prototype OO.

Exercise 5.15 (Easy) Reproduce the examples from the chapter. Then define your own points of various colors and names, with 2d or 3d coordinates, with or without using specifications.

Exercise 5.16 (Easy) Verify that idModExt is indeed a neutral element for the composition of modular extensions via mix. What happens if you instantiate it with (fix top)?

Exercise 5.17 (Easy) Write a specification that defines polar coordinates for a 2d point with defined cartesian coordinates, and another specification the other way around. Test your specifications with various points. What happens if you compose those two specifications, try to instantiate them, and extract coordinates?

Exercise 5.18 (Medium) Prove that mix is associative. Test it in practice.

Exercise 5.19 (Medium) Write modular extensible specifications that rely on base-bill-of-parts to contribute a chassis, axles, wheels, etc., where, to simplify, each part is just a string, e.g. "front left wheel", and each specification contribute one or many parts. Define overall specifications for a toy car, a toy truck, a toy motorcycle, a toy bicycle, while trying to share as much code as possible between the different toys. You may define functions that take arguments, manipulate strings, and return specifications. Use the parts and part-count functions on each of your complete specifications.

Exercise 5.20 (Medium, Recommended) If you did exercise 4.21, compare your previous formalization with mine. See what surprised you—how your formalization of modular extensibility compares to mine: whether they are equivalent, which can be expressed in terms of the other, which is more minimal, what insights you missed, what features I left out (at least so far), and how your understanding has evolved already.

Exercise 5.21 (Hard, Recommended) Based on this minimal model of OO as modular extensibility, and on the informal explanations in What Object Orientation is — Informal Overview, sketch how you would (1) rebuild Prototype OO as a layer on top of the model, (2) rebuild Class OO on top of Prototype OO, and (3) assign Types to OO. Assume mixin inheritance for now, i.e. via using the mix function. Save your answer to compare with the treatment in Rebuilding OO from its Minimal Core.

Exercise 5.22 (Hard) Define an API for manipulating records, as a set of methods. Provide an implementation of that API with functions in the style I used. Provide another implementation of it with alists as in 5.9. Provide another implementation of it with balanced binary trees (say, red-black trees). Define that red-black-tree implementation in multiple specifications: one for binary trees, an abstract one for balancing and rebalancing based on some metadata, a more concrete one for red-black-trees. Along the way, you may also have to define an API for order and comparisons. In the end, you will have bootstrapped a more efficient representation for records from a simple one. Write functions to convert between the two. Notice the limitations in one direction. Can you use alist- or tree- based records directly with the Y combinator? If not, explain why not, and consider if wrapping in a thunk, delay or once may help. With or without wrapper, do it.

Exercise 5.23 (Research) Port this minimal OO system to your language of choice. What issues are you facing and why? Can you make the system usable? Make a library out of it that you actually use? (See for instance the slides next to the source code for this book, at https://github.com/metareflection/poof.) Can you attract users beside yourself? What patches to your language implementation did you need, or would you need to implement the system better? If your language has static types, how do you deal with them?

6.1.1 What did I just do?🔗

In the previous chapter, I reconstructed a minimal yet recognizable model of OO from first principles, the principles being modularity, extensibility, and first-class entities. I will shortly extend this model to support more features (at the cost of more lines of code). Yet my “object system” so far has no classes, and indeed no objects at all!

I defined my system in two lines of code, that can be similarly defined in any language that has higher-order functions, even a pure functional language without mutation; and indeed Nix defines its “extension” system similarly (Simons 2015). But there is indeed one extra thing Nix does that my model so far doesn’t, wherein Nix has prototype objects and I don’t: conflation.

6.1.2 Conflation: Crouching Typecast, Hidden Product🔗

Notional Pair

Prototype object systems have a notion of “object”, also known as “prototype”, that can be used both for computing methods, as with my model’s record targets, and for composing with other objects through some form of inheritance, as with my model’s specifications. How can these two very different notions be unified in a single entity? Very simply: by bundling the two together as a pair.

The type for a prototype, Proto = Spec × Target, is thus notionally the product of the type Spec for a specification and the type Target for its target. Giving more precise types for Spec and Target may involve types for fixpoints, subtyping, existential types, etc. See Types for OO.

However, the notions of specification and target and this notional product all remain unmentioned in the documentation of any OO system that I am aware of. Instead, the product remains implicit, hidden, and the prototype is implicitly typecast to either of its factors depending on context: when calling a method on a prototype, the target is used; when composing prototypes using inheritance, their respective specifications are used, and then the resulting composed specification is wrapped into a pair consisting of the specification and its target.

Trivial Implementation

My implementation below makes this product explicit, where I use the prefix pproto to denote a prototype implemented as a pair. I use the cons function of Scheme to create a pair, and the functions car and cdr to extract its respective first and second components. In a more practical implementation, a special kind of tagged pair would be used, so the runtime would know to implicitly dereference the target in the common case, without developers having to painfully maintain the knowledge and explicitly tell the program when to dereference it (most of the time). If more data is to be conflated with the specification and its record (such as debugging information, static type annotations, etc.), a record could be used for all these kinds of data and metadata, instead of a pair.7878In Clojure, for instance, native data types all come with a meta accessor for an immutable record of arbitrary metadata. All data elements except the “main” one could be stored in that record.

The function pproto←spec is used to define a prototype from a specification, and is used implicitly when composing prototypes using inheritance with the pproto-mix function. The function spec←pproto extracts the specification from a prototype, so you may inherit from it. The function target←pproto extracts the target from a prototype, so you may call methods on it:

First Issue: Incomplete Specifications

There is an important catch, however: the whole point of specifications is that most specifications are not complete, and cannot be instantiated without error or divergence. In an abstract mathematical model where you can manipulate failing terms, that’s not a problem. But for a concrete implementation, that’s an issue.

To be able to uniformly conflate a specification and its target, some device must be used to delay the evaluation of the target, or delay potential errors and divergence until after the target is computed, when a further attempt is made to use the target. Otherwise, an invalid target, which is a necessarily common case, would prevent access to the specification, defeating the entire point of conflation.

The simplest device to delay evaluation of the target is lazy evaluation: Proto = Spec × Lazy Target. In second-class Class OO, the target is a descriptor for type, that itself can always be computed without error in finite time, though the type may be empty, and trying to use it may result in static or dynamic errors. Execution in a latter stage of computation (runtime vs compile-time) can be seen as the ultimate form of delayed evaluation.

Note how in our representation of records as function so far, we already delay the potentially non-terminating or error-throwing behavior, until the time that the function is invoked. The function definition itself is guaranteed to terminate early on. The actual computations within are protected by λ-abstractions. Thus, delay and force are not necessary to prevent an invalid target from causing an error when computing the product.

Second Issue: Recursion

Now, there is a subtle issue with the above implementation: when a target recursively refers to “itself” as per its specification, it sees the target only, and not the conflation of the target and the specification. This is not a problem with second-class OO, or otherwise with a programming style involving strictly stratified stages of evaluation wherein all the specifications are closed before any target is instantiated; then at one stage you consider only specifications, at the other, you consider only targets. And runtime recursion only happens during that other, latter stage.

But with a more dynamic style of programming where no such clear staging is guaranteed, lack of support for recursion is insufficient for full first-class OO: it means programs and programmers must deal with two different kinds of entities, conflated or unconflated, depending on whether they are specified as second-class entities before recursion happens, or produced during the recursion as first-class entities. Tracking which kind you are dealing with at which time can be a big limitation, that is extremely complex, time-consuming, and bug-prone to lift or work around.7979Metaobjects are a typical use case where you don’t (in general) have a clean program-wide staging of specification and targets: to determine the meta methods, you partially instantiate the “meta” part of the objects, based on which you can instantiate the rest.

As is often the case in software, if you need to access some information (here, the specification) that existed at some point but isn’t available anymore, your best bet is to stop throwing away the useful information during the computation, but keep it conflated with whichever entity should have remembered the information (here, the target in a recursive reference).

6.1.3 Recursive Conflation🔗

In a dynamic first-class OO language, the conflation of specification and target into a single entity, the prototype, must be recursively seen by the target when instantiating the specification. This is achieved by having the instantiation function compose a “magic” wrapper specification in front of the user-given specification before it takes a fixpoint. Said magic wrapper will wrap any recursive reference to the target into an implicit conflation pair of the specification and the target.8080Abadi and Cardelli (1996b) struggle with variants of this problem, and fail to find a solution, because they want to keep confusing target and specification even though at some level they can clearly see they are different things. If they had conceptualized the two as being entities that need to be distinguished semantically, then must be explicitly re-grouped together as a pair, they could have solved the problem and stayed on top of the λ-calculus. Instead, they abandon such attempts, and rebuild their own syntactic theory of a variant of the λ-calculus just for object, with hundreds of pages of greek symbols that still fail to properly modeling objects, in an insanely complex abstraction inversion  (Baker 1992). Their futile theory can neither enlighten OO practitioners, nor make OO interesting to mathematical syntax theoreticians.


Here is an implementation of that idea, wherein I prefix function names with qproto:

Now, it is not unusual in software for access to records, recursive or not, to be wrapped inside some kind of reference type: pointer into memory, index into a table, key into a database, cryptographic hash into a content-addressed store, location into a file, string or identifier used in a hash-table or tree, etc. In the case of recursive data structures implemented as data in contiguous regions of memory, such level of indirection is inevitable, as there is no way to have a contiguous region of memory of some size contain as a strict subset a contiguous region of memory of the same size, as would be required for a data structure to directly include an recursive element of the same type.8181Exception: If after simplifying unit types away the only element of a structure is an element of the same structure. At which point it’s just an infinite loop to the same element, the type is isomorphic to the unit type, and can be represented as a trivial data structure of width zero. But if there is any other data element that isn’t a unit type, direct recursion would mean infinite copies of it, one for each recursive path, which can’t fit in finite memory.

This use of a reference wrapper can be seen as an instance of the so-called “Fundamental theorem of software engineering”  (Wikipedia 2025a): We can solve any problem by introducing an extra level of indirection. But more meaningfully, it can also be seen as the embodiment of the fact that, computationally, recursion is not free. While at some abstract level of pure logic or mathematics, the inner object is of the same type as the outer one, and accessing it is free or constant time, at a more concrete level, recursion involves fetching data from another memory region. In the best case of a simple sequence of data, the sequence can be a contiguous array of memory and this fetching is constant time; in general, this fetching goes through the memory caching hierarchy, which logically requires a number of bits that grows logarithmically with the size of the working set, and physically requires a latency which grows as the square root of that size (Ernerfeldt 2014).

Importantly, isomorphic as it might be at some abstract level, the reference type is not equal to the type being referenced, and is not a subtype of it. Thus, the necessary reference wrapper extension is crucially not a strict extension with respect to the type being wrapped. This proves that it is a bad idea to require all extensions to always be strict (which would beg the question of which type to be strict for, or lead to the trivial answer that of being strict for the top type, for which all extensions are trivially strict). The reference wrapper, pure isomorphism at one level, yet effectful non-isomorphism at another (requiring access to disk, database, network, credentials, user interface, etc.), also illustrates that one man’s purity is another man’s side effect (to channel Alan Perlis). For instance, with merkleization, a reference uniquely identifies some pure data structure with a cryptographically secure hash that you can compute in a pure functional way; but dereferencing the hash is only possible if you already know the data based on which to compute and verify the hash, that you indexed into a database that you need some side-effect to consult. Many OO languages have an implicit builtin reference wrapper, as opposed to, e.g., explicit pointers as in C++; but the reference semantics doesn’t disappear for having been made implicit.

6.1.4 Conflation for Records🔗

If the target type can be anything, including an atomic value such as small integers, then there’s nowhere in it to store the specification, and the conflation of specification and target must necessarily involve such a wrapping as I showed earlier. But if the target type is guaranteed to be a (subtype of) Record, it is possible to do better.

In the Nix extension system, a target is a record (called an attrset in Nix), mapping string keys to arbitrary values, and the modular extension instantiation function fix’ stores the specification under a “magic” string "__unfix__". The advantage is that casting a prototype (called “extension” in Nix) to its target is a trivial zero-cost identity no-op; the slight disadvantage is that the target must be a record, but that record cannot use arbitrary keys, and must avoid the magic string as key. As a minor consequence, casting to a specification becomes slightly more expensive (table lookup vs fixed-offset field access), whereas casting to a target (the more common operation by far) becomes slightly cheaper (free vs fixed-offset field access). The semantics are otherwise essentially the same as for my implementation using pairs.

6.1.5 Conflation with User Application of Self🔗

One simple encoding of objects conflates specification and target in a way that is subtly different from the previous one. It is notable for being used by Yale T Scheme  (Adams and Rees 1988; Rees and Adams 1982), and after it by YASOS  (Dickey 1992), and also for being the essence of the JavaScript object system  (Eich 1996): a prototype is a record of methods encoded as functions that take the record itself as parameter.

The subtle difference is that instead of taking a resolved module context as first argument, functions take as first argument an unresolved record of functions that themselves take the same unresolved record as first argument. Callers, whether from outside the object or recursively from inside, must constantly be aware of the calling convention and pass the record as argument to all methods after extracting the methods from the record. At no point in this encoding is there a handle on a fully resolved target, only to the half-resolved specification.8282The encoding can be considered as being based on the duplication combinator D rather than on the fixpoint combinator Y. D is sometimes known as the self-application operator U (see Digression: Scheme and FP) in the context of computing fixpoints, and can also be viewed as half of Y. That is why we can speak of Y-encoding and U-encoding of recursion schemes, and also why, when comparing the two, I like to write U-encoded specifications as using half rather than self as the name of the first variable, essentially, you have self = (half half) and super = (hyper half). Most implementations traditionally switch the order of arguments between that half and method-id but that is immaterial to the semantics.

In T and after it YASOS, an operation can abstract over the calling convention providing a regular functional interface to the functionality, as well as a locus to define an operation-specific default behavior, and potentially more (see also generic functions in CLOS). Meanwhile, inheritance is supported by an operate-as function that extracts a method from an ancestor prototype, then calls it to the “real” self as first argument: single or mixin inheritance are simply about chaining calls to the method for the next ancestor. T or YASOS themselves do not offer builtin infrastructure to locate the next ancestor, but it is trivial to roll your own for single inheritance by having each object delegate to the known next ancestor (Single Inheritance). Mixin inheritance can be achieved by abstracting over the super object (i.e. function that takes it as argument and returns the half-resolved record), though it requires a bit of infrastructure to dynamically skip over objects that do not handle a message (Mixin Inheritance). A uniform field in which to store the super object (if any) could help in both cases above. Multiple inheritance can be done as a layer above mixin inheritance, or else by a change in protocol wherein methods take a “method resolution continuation” argument in addition to the “self” argument (Multiple Inheritance).

In the end, this specialized object encoding is efficient, which is why it has been adopted, in many variants, by many implementations of many languages. But it comes with significant complexity, both technical and conceptual. It also sets objects apart from other kinds of records or values, with their own distinct query protocol, when my fixpoint encoding allows any value of any type to be the target of a specification, after which it follows the same protocol as any other value of that type. Also, this encoding giving you conflation for free is both a blessing and a curse. A blessing because the object implicitly embodies both target and specification without extra effort. A curse because this costlessness historically contributed to blurring the lines between specification and target, and therefore to the ongoing confusion between them, making their conceptual conflation harder to untangle.

Often efficiency is important at runtime, yet simplicity is even more important at the conceptual layer, for programmers to understand the software they work with. That is why I describe this most common implementation strategy last instead of first, and leave its details as an exercise to the reader.

6.1.6 Small-Scale Advantages of Conflation: Performance, Sharing🔗

First, note how, if a specification is pure functional, i.e. without side-effects, whether state, non-determinism, I/O, or otherwise, then indeed there is only one target, uniquely specified up to behavioral equality: recomputing the target multiple times will lead to the same result in all contexts. It thus makes sense to consider “the” target for a specification, and to see it as but another aspect of it. Caching the target value next to the specification can then be seen simply as a performance enhancement. Indeed, in case of recursive access to the target, this performance enhancement can grow exponentially with the depth of the recursion, by using a shared computation instead of repeated recomputations (see the related discussion on the applicative Y combinator in Digression: Scheme and FP).

If on the other hand, the specification has side-effects (which of course supposes the language has side-effects to begin with), then multiple computations of the target value will lead to different results, and caching a canonical target value next to the specification is not just a performance enhancement, but a critical semantic feature enabling the sharing of the state and side-effects of a prototype between all its users. Meanwhile, if some users explicitly want to recompute the target, so as to get a fresh state to be modified by its own set of side-effects, they can always clone the prototype, i.e. create a new prototype that uses the same specification. Equivalently, they can create a prototype that inherits from it using as extension the neutral element (rproto←spec idModExt).

Now, plenty of earlier or contemporary Prototype OO languages, from Director and ThingLab to Self and JavaScript and beyond, support mutation yet also offer objects as conflation of two aspects: one for inheritable and instantiatable specification, another one for the instantiated target that holds mutable state and that methods are called against. However, the two aspects might not be as neatly separated in these stateful languages as in pure functional languages, because the mutation of the internals of the specification, in languages that allow it, may interact with the target state and behavior in weird ways. This mutation is not usually idiomatic in production code, but may be heavily relied upon during interactive development, or as part of implementing advanced infrastructure.

Last but not least, if your choice of representation for specifications and targets is such that instantiating a specification may itself issue side-effects such as errors or non-termination or irreversible I/O—then it becomes essential to wrap your target behind lazy evaluation, or, in Scheme, a delay form. Thus you may still define prototypes from incomplete erroneous specifications, and use them through inheritance to build larger prototypes, that, when complete, will not have undesired side-effects. Once again, Laziness proves essential to OO, even and especially in presence of side-effects.

6.1.7 Large-Scale Advantage of Conflation: More Modularity🔗

Remarkably, conflation is more modular than the lack thereof: thanks to it, programmers do not have to decide in advance when each part of their configuration is to be extended or instantiated. Indeed, if only using unconflated specifications and targets, one would have to choose, for each definition of each identifier in each (sub)module, whether to use a specification or its target. And when choosing to maintain a specification for the purpose of extensibility, the programmer may still want to explicitly bind an identifier to the target, and another one to the specification, for the sake of state sharing, and sanity, and not having to remember the hard way the “shape” of the nested extensions to replace by the values when instantiating the target. Thus, users would end up doing by hand in an ad hoc way what conflation gives them systematically for free.

Furthermore, users cannot know which of their definitions they themselves, or other users, might later want to extend. A simple service will often be made part of a larger service set, in multiple copies each slightly tweaked; its configuration, complete and directly instantiable as it may be for its original author, will actually be extended, copied, overridden, many times, in a larger configuration, by the maintainers of the larger service set.

6.1.8 Implicit Recognition of Conflation by OO Practitioners🔗

The notion of a conflation of specification and target, that I presented, is largely unknown by OO developers, and seems never, ever, to have been made explicit in the literature until I published Rideau et al. (2021), that itself remained confidential. And yet, the knowledge of this conflation is necessarily present, if implicit, if not across the community of OO practioners, at the very least among individual OO implementers—or else OO wouldn’t be possible at all. Sixty years of crucial information you don’t know you know!

Common practitioners of OO have long implicitly recognized the conflated concepts of specification and target. Back in 1979, Flavors  (Cannon 1979) introduces the concept of a mixin as a flavor meant to be inherited from, but not to be instantiated, by opposition to an instantiatable flavor; however, the nomenclature only stuck in the Lisp community (and even there, flavors yielded to classes though the term mixin stayed). In other communities, the decade-later terms of art are abstract classes and concrete classes (Goldberg and Robson 1983; Johnson and Foote 1988): an abstract class is one that is only used for its specification—to inherit from it; a concrete class is one that is only used for its target type—to use its methods to create and process class instances. Experienced practitioners recommend keeping the two kinds of classes separate, and frown at inheriting from a concrete class, or trying to instantiate an abstract class.

Theorists have also long implicitly recognized the conflated concepts when developing sound typesystems for OO: for instance, Fisher  (Fisher 1996) distinguishes pro types for objects-as-prototypes and obj types for objects-as-records; and Bruce  (Bruce 1996) complains that “the notions of type and class are often confounded in object-oriented programming languages” and there again distinguishes subtyping for a class’s target type (which he calls “subtyping”) and for its open specification (which he calls “matching”). Yet though they offer correct models for typing OO, both authors fail to distinguish specification and target as syntactically and semantically separate entities in their languages, leading to much extraneous complexity in their respective typesystems.

Implementers of stateful object systems at runtime may not have realized the conflation of entities, because they are too focused on low-level mechanisms for “delegation” or “inheritance”. By contrast, writers of compilers for languages with second-class Class OO may not have realized the conflation because at their level it’s all pure functional specification with no target until runtime. One group of people though, must explicitly deal with the conflation of specification and target embodied as a first-class value: implementers of pure functional prototype systems. Nix  (Simons 2015) explicitly remembers the specification by inserting the __unfix__ attribute into its target records; and Jsonnet  (Cunningham 2014) must do something similar under the hood, though it is hidden under much complexity in the implementation. Yet the authors of neither system make note of it in their documentation as a phenomenon worthy of remark. Though they implicitly rediscovered the concept and made it flesh, they failed to realize how momentous the discovery was, and shrugged it off as yet another one of those annoying implementation details they had to face along the way.

Finally, the confusion between target and specification can be seen as a special case of the confusion between object and implementation discussed in Chiba et al. (2000), wherein you can see the specification as implementing the target. But though these authors saw a more general case in a wider theory with far reaching potential, they do not seem to have noticed this common case application.

Thus, through all the confusion of class OO languages so far, both practitioners and theorists have felt the need to effectively distinguish specification and target, yet no one seems to have been able to fully tease apart the concepts up until recently.

Exercise 6.6 (Hard) Assuming you did exercise 5.22, write a variant of rproto that uses your representation of records as data structures rather than as functions from symbol to value.

6.2.1 A Class is a Prototype for a Type🔗

Having elucidated Prototype OO in the previous sections, including its notion of Object, a.k.a. Prototype, as conflation of Specification and Target, I can now fully elucidate Class OO including its notion of Class: A Class is a Prototype for a Type. Or, to be pedantic, a class is a prototype, the target of which is a type descriptor, i.e. a record describing a type together with methods associated with the type.

The target type of a class is usually, but not always, a record type (indexed product, structure, struct, named tuple), at which point the descriptor will also describe its fields; it may also be an enumeration type (indexed sum, enum, variant, discriminated union, tagged union), at which point the descriptor will also describe its alternatives; and while this is less common in Class OO, a class’s target could really describe any kind of type: function, number, array, associative array, etc.

The target of a class may be a runtime type descriptor, that describes how to create, recognize, and process elements of the type in the same evaluation environment that the type exists in; or, as is often the case in second-class Class OO, the target may be a compile-time type descriptor, that describes how to generate code for entities of that type to be executed in a further stage of evaluation; or it may be both.

Whichever kind of type descriptors are used, Class OO is but a special case of Prototype OO, wherein a class is a prototype for a type, i.e., the conflation of a modular extension for a type descriptor, and the type descriptor that is the fixpoint of that specification. Thus, when I claimed in OO isn’t Classes Only that the situation of classes in OO was similar to that of types in FP, I meant it quite literally.

6.2.2 Simple First-Class Type Descriptors🔗

Since I do not wish to introduce a Theory of Compilation in this book in addition to a Theory of OO, I will only illustrate how to build first-class Class OO, at runtime, on top of Prototype OO. I will use a technique described by Lieberman  (Lieberman 1986), and no doubt broadly similar to how many Class OO systems were implemented on top of Javascript before web browsers ubiquitously adopted ES6 classes (International 2015).

As for “class methods” (also known as “static methods” in C++ or Java), they can be regular methods of the type descriptor, or there can be a method class-methods in the type descriptor containing a record of them.

6.2.3 Parametric First-Class Type Descriptors🔗

There are two main strategies to represent parametric types: “function of descriptors” vs “descriptor of functions”.

In the “function of descriptors” strategy, a parametric type is represented as a function from type descriptor to type descriptor: the function takes a type parameter as input, and returns a type descriptor specialized for that parameters as output. As it computes the specialized descriptor, it can apply various specializations and optimizations, pre-selecting code paths and throwing away cases that do not apply, allowing for slightly better specialized code, at the expense of time and space generating the specialized descriptor. This representation allows for uniform calling conventions for all type descriptors satisfying the resulting monomorphic interface, regardless of whether it was obtained by specializing a parametric type or not. This strategy is notably used during the “monomorphization” phase used within C++ compilers when expanding templates. It is useful when trying to statically inline away all traces of type descriptors before runtime, but in a dynamic setting requires creation of more descriptors, or some memoization mechanism.

In the “descriptor of functions” strategy, a parametric type is represented as a type descriptor the methods of which may take extra parameters in front, one for the type descriptor of each type parameter. Methods that return non-function values may become functions of one or more type parameters. Thus, the type descriptor for a functor F may have a method map that takes two type parameters A and B and transforms an element of P A into an element of P B. This strategy eliminates the need to heap-allocate a lot of specialized type descriptors; but it requires more bookkeeping, to remember which method of which type descriptor takes how many extra type descriptor parameters.

Both strategies are useful; which to prefer depends on the use case and its tradeoffs. A given program or compiler may use both, and may very well have to: even using the “descriptor-of-functions” strategy, you may still have to generate specialized type descriptors, so that you may pass them to functions that expect their parametric type descriptors to only take N type parameters, and are unaware that these were specialized from more general parametric type descriptors with N + M type parameters (where M > 0). This unawareness may stem from any kind of dynamic typing, or from a choice to avoid generating many copies of the code for each value of M as the depth of parametric constructors varies. And even using the “function-of-descriptors” strategy, you may want to maintain collections of functions that each take one or many descriptors as arguments, especially when such collections contain a large number of functions, only one or a few of which are to be used at a time per tuple of descriptor arguments, and this tuple of descriptor arguments itself changes often.

Even fixpoints can be done differently in the two strategies: the “function-of-descriptors” strategy leads to generating descriptors that embed the fixpoints so that clients never need to know they were even fixpoints; whereas the “descriptor-of-functions” strategy leads to descriptors the calling convention of which requires clients to systematically pass the descriptor itself to the methods it contains so as to close the fixpoint loop.

6.2.4 Class-style vs Typeclass-style🔗

Now, there are two common styles for using type descriptors: Class-style and Typeclass-style.

In Class-style, each type element (known in this style as “class instance”, “instance”, or “object”) carries its own type descriptor. To this end, the type descriptor is conflated with the type element in the same way that specifications are conflated with their targets (see Recursive Conflation, Conflation for Records). As mentioned before, this can be very cheap when the type elements are records (see Conflation for Records, Simple First-Class Type Descriptors): just add a special field with a “magic” key.

In Typeclass-style, by contrast, type descriptors and type elements are kept distinct and separate. There is emphatically no conflation. Type-descriptors are passed “out of band” as extra variables (see second-class “dictionaries” in Haskell  (Wadler and Blott 1989), or first-class “interfaces” in “Interface-Passing Style”  (Rideau 2012)). This is efficient in another way, because you can pass around a few type descriptors that do not change within a given algorithm, and not spend time wrapping and unwrapping conflations.

There is an isomorphism between class-style and typeclass-style type descriptors, to the point that a simple transformation can wrap objects written in one style and their methods so they follow the calling convention of the other style.8383To go from Class-style to Typeclass-style, simply extract the type descriptor, class metaobject, vtable, etc., from an object, and make that your type descriptor. For “typeclasses” that are parameterized by many types, use a record that contains each of those descriptors for each of those types as fields. To go from Typeclass-style to Class-style, you can wrap every value or tuple of values into a record of the values and the typeclass they are supposed to be used with. When invoking typeclass functions, unwrap the values from those records to use them as arguments; and wrap the results back into records that conflate the values and an appropriate typeclass. This is the same trick that we used with recursive conflation. You just need to know which arguments and results of which method to wrap or unwrap. Note how the values associated with typeclasses can be “naked” primitive values that need not be records, just like the fields of class instances.


Simple metaprograms that enact this transformation have been written in Lisp  (Rideau 2012) in the simple case of functions in which the self-type only appears directly as one of the (potentially multiple) arguments or (potentially multiple) return values of a method. Such automation could be generalized to work with any kind of higher-order function types, where occurrences of the self-type in arbitrary position require suitable wrapping of arguments and return values, in ways similar to how higher-order contracts wrap arguments and return values with checks (Findler and Felleisen 2002). Note how similarly, metaprograms have been written to transform pure objects into mutable objects that store a current pure value, or mutable objects into linear pure objects that become invalid if a use is attempted after mutation.

Thus, programming with either (A1) classes or (A2) typeclasses, wherein objects are either (B1) mutable or (B2) pure, is a matter of style, with some tradeoffs with respect to performance, ease of reasoning, between the four combined styles. You could add more style variants, such as data representation as (C1) a graph of records, or (C2) tables of entities, (D1) dynamically typed, or (D2) statically typed, etc. In the end, programs in one style can be mechanically transformed into programs in another style, and vice versa. Some programs, given the kind of data they are expected to work on at runtime, may be better compiled onto one of those styles, if not directly written in it. But if programmers have to deal with conceptual issues that are more natural in a different style, they may be better off writing their programs in the style that works for them, and pay the price of automatic or manual translation later.

Interestingly, all this section’s discussion was about styles for target programs. Type descriptors can be used in any and all of those styles without any OO whatsoever.8484Indeed, Haskell typeclasses are multi-type descriptors with modularity but without inheritance, and so their Rust equivalent called “traits”— not to be confused with Scala “traits”, that are single-type descriptors with multiple inheritance. Modules in SML or OCaml can also offer “typeclass-style” type descriptors without modular extensibility through inheritance. Non-OO class-style type descriptors are also possible. For instance, Gambit Scheme allows users to define new data structures, and to declare the equivalent of methods that specialize how values of those new types will be printed, or tested for equality; these methods are not part of any actual object system capable of inheritance, yet each “structure” record carries the equivalent of a type descriptor field in “class style” so that the system knows which method to use. It is possible to layer an actual OO class system on top of such non-OO “class-style” mechanism, and indeed the Gerbil Scheme object system is built atop Gambit Scheme’s non-OO structure facility.


And OO can be used at runtime or compile-time to specify and generate type descriptors in any and all of those styles, as well as non-type-descriptor targets. OO is completely agnostic as to whether you write in any particular style or another. OO is about specifications for programs and parts of programs. Although it was historically developed in the context of the style (A1, B1, C1, D1) of dynamic graph of mutable classes (Smalltalk, Lisp, JavaScript), or the style (A1, B1, C1, D2) of static graph of mutable classes (Simula, C++, Java), OO can well accommodate any style. I wrote OO in both Typeclass-style (A2) and pure-style (B2)  (Rideau 2012, 2020), and I have no doubt you could write OO to manipulate tables (C2) instead of record graphs (C1). There is no reason why you couldn’t use OO to specify programs in the (A2, B2, C2, D2)-style of static tables of pure functional typeclasses: this combination would make for a nice hypothetical language to statically specify pure transformations on tables of uniform data, with applications to modeling neural networks, physics engines or 3d video pipelines.

6.2.5 A Class is Second-Class in Most Class OO🔗

In most Class OO languages, the semantics of Class OO are fully evaluated at compile-time, in a “type-level” evaluation stage. The class specifications, and the type descriptors they specify, are second-class entities: they are not available as first-class values subject to arbitrary programming at runtime. Class OO then is a special case of Prototype OO, but only in a restricted second-class language—a reality that is quite obvious when doing template metaprogramming in C++.

Some dynamic languages, such as Lisp, Smalltalk, Ruby or Python, let you programmatically use, create, inspect or modify classes at runtime, using some reflection mechanisms. The regular definition and usage of classes involve dedicated syntax, such that restricting yourself to the language fragment with that syntax and never using reflection would be equivalent to classes being second-class; but the reflection mechanisms ultimately make classes into first-class entities. Indeed, the second-class semantics of classes are often implemented in terms of those first-class mechanisms, that are thus just as powerful, or more so.

Static languages lack such full-powered runtime reflection mechanisms (or they would arguably be dynamic languages indeed). Some lack any runtime reflection at all; but many offer read-only runtime reflection, whereby users can inspect classes created at compile-time, yet not create new ones: such capabilities can notably simplify I/O, property-based testing, debugging, etc. A few static language implementations may even offer limited ability to modify existing classes at runtime, but often void the compiler’s warranty for those who use them.

6.2.6 Type-Level Language Restrictions🔗

The language in which second-class classes are defined and composed in static languages is almost never the same as the “base” language in which the programmer specifies first-class computations (e.g. C++, Java, C#), but instead a distinct type-level language, deliberately restricted in expressiveness so as to enable static analysis and optimizations, in which the types and the base-level functions operating on them are being modularly and extensibly specified.

Programming language designers put restrictions on their type-level language as they attempt to keep them both (1) sound, and also, inasmuch as possible (2) terminating in finite and practically guaranteed short time. These attempt sometimes succeed, but more often than not utterly fail, because computational power and/or logical contradiction emerge from unforeseen interactions as the languages grow in complexity over time (see OO Type Practice).8585Even the C preprocessor, with annoying rules added to “guarantee” termination in finite time, ends up allowing arbitrary metaprogramming in practice  (Hirrolot 2021). Henry Baker tried to explain it in old posts on USENET that I never understood, stupidly believing the guarantees, even though I could myself prove that the “finite time” of termination could easily be made longer than the age of the universe.


The attempts do usually succeed, however, at making these type-level languages require a completely different mindset from the “base language”, and very roundabout design patterns, to do anything useful, a task then reserved for experts.

Computationally powerful or not, the type-level language of a Class OO language is almost always very different from the base language: the type-level languages tend to be pure functional or logic programming languages with pattern-matching and laziness but without any I/O support; this is in stark contrast with the base languages, that themselves tend to be eager stateful procedural languages with lots of I/O support and often without pattern-matching or laziness (or limited ones as afterthoughts).

6.2.7 More Popular yet Less Fundamental🔗

Class OO was historically discovered (1967), nine years before Prototype OO (1976), and remains overall more popular in the literature and in practice: most popular OO languages only offer Class OO; and even though the arguably most popular OO language, JavaScript, may have started with Prototype OO only  (Eich 1996), people were constantly reimplementing classes on top—and twenty years later, classes were added to the language itself (International 2015).

And yet I will argue that Prototype OO is more fundamental than Class OO: as I demonstrated above, Class OO can be easily expressed in terms of Prototype OO and implemented on top of it, such that inheritance among classes is indeed a special case of inheritance among the underlying prototypes; however the opposite is not possible, since you cannot express Prototype OO’s first-class entities and their inheritance in terms of Class OO’s second-class entities and their inheritance.

At best, Prototype OO can be implemented on top of those dynamic languages that offer full-powered reflection so that prototypes can be classes; but even then it is unclear how much these mechanisms help, compared to directly implementing prototypes. There could be code sharing between the two; yet trying to fit prototypes on top of classes rather than the other way around is what Henry Baker dubbed an abstraction inversion  (Baker 1992), i.e. putting the cart before the horse.

6.3.1 Dynamic Typing🔗

One could just say that objects are of a monomorphic type Record, and that all accesses to methods are to be dynamically typed and checked at runtime, with no static safety. Many OO languages, like Smalltalk, Lisp, Ruby, Python, JavaScript, Jsonnet, Nix, etc., adopt this strategy.

Advantages of dynamic typing include the ability to express programs that even the best static typesystems cannot support, especially when state-of-the-art typesystems are too rigid, or not advanced enough in their OO idioms. Programs that involve dependent types, staged computation, metaprogramming, long-lived interactive systems, dynamic code and data schema evolution at runtime, etc., can be and have been written in dynamically typed systems that could not have been written in existing statically typed languages, or would have required reverting to unitypes with extra verbosity.

On the other hand, system-supported static types can bring extra performance and safety, help in refactoring, debugging programs, some forms of type-directed metaprogramming, and more. Even without system enforcement, thinking in terms of types can help understand what programs do or don’t and how to write and use them. I have already started to go deeper by describing records as indexed products. Let’s see how to model OO with more precise types.

6.3.2 Partial Record Knowledge as Subtyping🔗

In a language with static types, programmers writing extensible modular definitions should be able to specify types for the entities they provide (an extension to) and require (a complete version of), without having to know anything about the types of the many other entities they neither provide nor require: indeed, these other entities may not have been written yet, and by other people, yet will be linked together with his modules into a complete program.

Now, with only modularity, or only extensibility, what’s more second-class only, you could contrive a way for the typechecker to always exactly know all the types required, by prohibiting open recursion through the module context, and generating magic projections behind the scenes (and a magic merge during linking). But as I previously showed in Interaction of Modularity and Extensibility, once you combine modularity and extensibility, what’s more first-class, then open recursion through the module context becomes the entire point, and your typesystem must confront it.

Strict extensibility, which consists in monotonically contributing partial knowledge about the computation being built, once translated in the world of types, is subtyping. In the common case of records, a record type contains not just records that exactly bind given identifiers to given types, but also records with additional bound identifiers, and existing identifiers bound to subtypes. Record types form a subtyping hierarchy; subtyping is a partial order among types; and function types monotonically increase with their result types, and decrease with their argument types. Then, when modularly specifying a module extension, the modular type for the module context, that only contains “negative” constraints about types for the identifiers being required, will match the future actual module constraint, that may satisfy many more constraints; meanwhile, the “positive” constraints about types for the identifiers being provided may satisfy many more constraints than those actually required from other modules using it.

6.3.3 The NNOOTT: Naive Non-recursive OO Type Theory🔗

The simplest and most obvious theory for typing OO, that I will dub the Naive Non-recursive Object-Oriented Type Theory (NNOOTT), consists in considering subclassing (a relation between specifications) as the same as subtyping (a relation between targets). Thus, in this theory, a subclass, that extends a class with new fields, is (supposedly) a subtype of the parent “superclass” being extended.

In Prototype OO, the value inherited holds the methods defined so far by the ancestors; the value provided consists in new methods and specialization of existing methods; the top value is an empty record. In Class OO, that value inherited holds methods and fields defined so far by the ancestors; the value provided consists in the new or specialized fields and methods; the top value is a type descriptor for an empty record type. In both cases, the context required may narrowly define a prototype or class, but may also more broadly define an entire namespace.

This model is simple and intuitive, and has good didactic value to explain how inheritance works: given two “mixin” specifications, you can chain them as child and parent; the combined specification requires a context with all the information required from either child or parent; the inherited information must contain all information expected by the parent, and all information expected by the child that isn’t provided by the parent; the provided information contains all information provided by either child or parent.

However, this “Naive Non-recursive OO Type Theory”, as the name indicates, is a bit naive indeed, and only works in simple non-recursive cases. Yet the NNOOTT is important to understand, both for the simple cases it is good enough to cover, and for its failure modes that tripped so many good programmers into wrongfully trying to equate inheritance and subtyping.

6.3.4 Limits of the NNOOTT🔗

The NNOOTT works well in the non-recursive case, i.e. when the types of fields do not depend on the type of the module context; or, more precisely, when there are no circular “open” references between types being provided by a modular extension, and types it requires from the module context. In his paper on objects as co-algebras, Bart Jacobs characterizes the types for the arguments and results of his methods as being “(constant) sets”  (Jacobs 1995),8787Jacobs is particularly egregious in smuggling this all-important restriction to how his paper fails to address the general and interesting case of OO in a single word, furthermore, in parentheses, at the end of section 2, without any discussion whatsoever as to the momentous significance of that word. A discussion of that significance could in itself have turned this bad paper into a stellar one. Instead, the smuggling of an all-important hypothesis makes the paper misleading at best. His subsequent paper  (Jacobs 1996) has the slightly more precise sentence I also quote, and its section 2.1 tries to paper over what it calls “anomalies of inheritance” (actually, the general case), by separating methods into a “core” part where fields are declared, that matter for typing inheritance, and for which his hypothesis applies, and “definitions” that must be reduced to the core part. The conference reviewing committees really dropped the ball on accepting those papers, though that section 2.1 was probably the result of at least one reviewer doing his job right. Did reviewers overall let themselves be impressed by formalism beyond their ability to judge, or were they complicit in the sleight of hand to grant their domain of research a fake mantle of formal mathematical legitimacy? Either way, the field is ripe with bad science, not to mention the outright snake oil of the OO industry in its heyday: The 1990s were a time when IBM would hire comedians to become “evangelists” for their Visual Age Smalltalk technology, soon recycled into Java evangelists. Jacobs is not the only one, and he may even have extenuating circumstances. He may have been ill-inspired by Goguen, whom he cites, who also abuses the terminology from OO to make his own valid but loosely-related application of Category Theory to software specification. He may also have been pressured to make his work “relevant” by publishing in OO conferences, under pains of losing funding, and he may have been happy to find his work welcome even though he didn’t try hard, trusting reviewers to send stronger feedback if his work hadn’t been fit. The reviewers, unfamiliar with the formalism, may have missed or underestimated the critical consequences of a single word; they may have hoped that further work would lift the limitation. In other times, researchers have been hard pressed to join the bandwagon of Java, Web2, Big Data, Mobile, Blockchain or AI, or whatever trendy topic of the year; and reviewers for the respective relevant conferences may have welcomed newcomers with unfamiliar points of view. Even Barbara Liskov, future Turing Award recipient, was invited to contribute to OO conferences, and quickly dismissed inheritance to focus on her own expertise, which involves modularity without extensibility—and stating her famous “Liskov Substitution Principle” as she did  (Liskov 1987); brilliant, though not OO; that said, she did use the word “object-oriented” in print as far back as Jones and Liskov (1976) to describe her style of programming, one month before Bobrow published the memo on KRL-0 that first used it right, so she did have a stake in the name, though her definition happily didn’t prevail. Are either those who talk and publish what turns out not to be OO at all at OO conferences, or those who invite them to talk and publish, being deliberately misleading? Probably not, yet, the public can be fooled just the same as if dishonesty were meant: though the expert of the day can probably make the difference, the next generation attending or looking through the archives may well get confused as to what OO is or isn’t about as they learn from example. At the very least, papers like that make for untrustworthy identification and labeling of domains of knowledge and the concepts that matter. The larger point here being that one should be skeptical of papers, even by some of the greatest scientists (none of Jacobs’, Goguen’s nor Liskov’s expertises are in doubt), even published at some of the most reputable conferences in the field (e.g. OOPSLA, ECOOP), because science is casually corrupted by power and money, and only more cheaply so for the stakes being low. This particular case from thirty years ago is easily corrected in retrospect; its underlying lie was of little consequence then and is of no consequence today; but the system that produced dishonest science hasn’t been reformed, and I can but imagine what kind of lies it produces to this day in topics that compared to the semantics of OO are both less objectively arguable, and higher-stake economically and politically.


which he elaborates in another paper  (Jacobs 1996) as meaning «not depending on the “unknown” type X (of self).» This makes his paper inapplicable to most OO, but interestingly, precisely identifies the subset of OO for which inheritance coincides with subtyping, or, to speak more precisely, for which subtyping of modular extensions coincides with subtyping of their targets.

Indeed, in general, specifications may contain so called “binary methods” that take another value of the same target type as argument, such as in very common comparison functions (e.g. equality or order) or algebraic operations (e.g. addition, multiplication, composition), etc. and beyond these, specifications may actually contain arbitrary higher-order functions involving the target type in zero, one or many positions, both “negative” (as an overall argument) or “positive” (as an overall result), or as parameters to type-level functions, “templates”, etc. These methods will break the precondition for subclassing being subtyping.

And such methods are not an “advanced” or “anomalous” case, but quintessential. The very first example in the very first paper about actual classes  (Dahl and Nygaard 1967), involves recursive data types: it is a class linkage that defines references suc and pred to the “same” type, that classes can inherit from so that their elements shall be part of a doubly linked list. This example, and any data structure defined using recursion, will defeat the NNOOTT if examined closely. Not only is such recursion a most frequent occurrence, I showed above in Interaction of Modularity and Extensibility that while you can eschew support for fixpoints through the module context when considering modularity or extensibility separately, open recursion through module contexts becomes essential when considering them together. In the general and common case in which a class or prototype specification includes self-reference, subtyping and subclassing are very different, a crucial distinction that was first elucidated in Cook et al. (1989).

Now, the NNOOTT can be “saved” by reserving static typing to non-self-referential methods, whereas any self-reference must dynamically typed: wherever a recursive self-reference to the whole would happen, e.g. in the type of a field, programmers must instead declare the value as being of a dynamic “Any” type, or some other “base” type or class, so that there is no self-reference in the type, and the static typechecker is happy. Thus, when defining a list of elements of type A, you could not write the usual recursive formula List(A) = 1 + A*List(A) or the fixpoint List(A) = Y (λ Self . 1 + A*Self), and would just write List(A) = 1 + A*Any. Similarly, for trees with leaves of type B, you couldn’t write the recursive formula Tree(B) = B + List(Tree(B)), and would instead write just the non-recursive and dynamically typed Tree(B) = B + List(Any)).

To compensate for the imprecision of the typesystem when retrieving an element of the desired self-type, some kind of explicit dereference, typecast (downcast), or coercion is required from the programmer; that operation may be either safe (with a dynamic runtime check), or unsafe (program may silently misbehave at runtime if called with the wrong argument). In some languages, self-reference already has to go through pointer indirection (e.g. in C++), or boxing (e.g. in Haskell, when using a newtype Fix generic constructor for fixpoints, while the open modular definition goes into a “recursion scheme”); thus the NNOOTT does not so much introduce an extra indirection step for recursion as it makes an existing indirection step obvious—and makes it dynamically rather than statically typed. In other words, it makes us realize once again that recursion is not free.

6.3.5 Why NNOOTT?🔗

The NNOOTT was implicit in the original OO paper  (Dahl and Nygaard 1967) as well as in Hoare’s seminal paper that inspired it  (Hoare 1965).8888Hoare probably intended subtyping initially indeed for his families of record types; yet subclassing is what he and the Simula authors discovered instead. Such is scientific discovery: if you knew in advance what lied ahead, it would not be a discovery at all. Instead, you set out to discover something, but usually discover something else, that, if actually new, will be surprising. The greater the discovery, the greater the surprise. And you may not realize what you have discovered until analysis is complete much later. The very best discoveries will then seem obvious in retrospect, given the new understanding of the subject matter, and familiarity with it due to its immense success.


It then proceeded to dominate the type theory of OO until debunked in the late 1980s  (Cook et al. 1989). Even after that debunking, it has remained prevalent in popular opinion, and still very active in academia and industry alike, and continually reinvented even when not explicitly transmitted  (AbdelGawad 2014; Cartwright and AbdelGawad 2013). And I readily admit it’s the first idea I too had when I tried to put types on my modular extensions, as you can see in Rideau et al. (2021).

The reasons why, despite being inconsistent, the NNOOTT was and remains so popular, not just among the ignorant masses, but even among luminaries in computer science, is well worth examining.

• The NNOOTT directly follows from the confusion between specification and target when conflating them without distinguishing them (Prototypes as Conflation). The absurdity of the theory also follows from the categorical error of equating entities, the specification and its target, that not only are not equivalent, but are not even of the same type. But no one intended for “a class” to embody two very distinct semantic entities; quite on the contrary, Hoare, as well as the initial designers of Simula, KRL, Smalltalk, Director, etc., were trying to have a unified concept of “class” or “frame” or “actor”, etc. Consequently, the necessity of considering two distinct entities was only fully articulated in the 2020s(!).

• In the 1960s and 1970s, when both OO and type theory were in their infancy, and none of the pioneers of one were familiar with the other, the NNOOTT was a good enough approximation that even top language theorists were fooled. Though the very first example in OO could have disproven the NNOOTT, still it requires careful examination and familiarity with both OO and Type Theory to identify the error, and pioneers had more urgent problems to solve.

• The NNOOTT actually works quite well in the simple “non-recursive” case that I characterized above. In particular, the NNOOTT makes sense enough in the dynamically typed languages that (beside the isolated precursor Simula) first experimented with OO in the 1970s and 1980s, mostly Smalltalk, Lisp and their respective close relatives. In those languages, the “types” sometimes specified for record fields are often but suggestions in comments, dynamic checks, sometimes promises made by the user to the compiler; and if they are actual static guarantees that only works outside of the recursive case, well, that is already most of the benefit of static guarantees when most of the work is not that recursive case. It takes an advanced functional programming language or style, or a rare care for total correctness, for the recursive case to dominate the issue, which was never a mainstream concern.

• Even in the 1980s and 1990s, theorists and practitioners being mostly disjoint populations, did not realize that they were not talking about precisely the same thing when talking about a “class”. Those trained to be careful not to make categorical errors might not have realized that others were doing it in ways that mattered. The few at the intersection may not have noticed the discrepancy, or understood its relevance, when scientific modeling must necessarily make many reasonable approximations all the time. Once again, more urgent issues were on their minds.

• Though the NNOOTT is inconsistent in the general case of OO, as obvious from quite common examples involving recursion, it will logically satisfy ivory tower theorists or charismatic industry pundits who never get to experience cases more complex than textbook examples, and pay no price for dismissing recursive cases as “anomalies”  (Jacobs 1996) when confronted with them. Neither kind owes their success to getting a consistent theory that precisely matches actual practice.

• The false theory will also emotionally satisfy those practitioners and their managers who care more about feeling like they understand rather than actually understanding. This is especially true of the many who have trouble thinking about recursion, as is the case for a majority of novice programmers and vast majority of non-programmers. Even those who can successfully use recursion, might not be able to conceptualize it, much less criticize a theory of it.

6.3.6 Beyond the NNOOTT🔗

The key to dispelling the “conflation of subtyping and inheritance”  (Fisher 1996) or the “notions of type and class [being] often confounded”  (Bruce 1996) is indeed first to have dispelled, as I just did previously, the conflation of specification and target. Thereafter, OO semantics becomes simple: by recognizing target and specification as distinct, one can take care to always treat them separately, which is relatively simple, at the low cost of unbundling them apart before processing, and rebundling them together afterwards if needed. Meanwhile, those who insist on treating them as a single entity with a common type only set themselves for tremendous complexity and pain.

That is how I realized that what most people actually mean by “subtyping” in extant literature is subtyping for the target of a class (or prototype), which is distinct from subtyping for the specification of a class (or prototype), variants of the latter of which Kim Bruce calls “matching”  (Bruce et al. 1997). But most people, being confused about the conflation of specification and target, fail to conceptualize the distinction, and either try to treat them as if it were the same thing, leading to logical inconsistency hence unsafety and failure; or they build extremely complex calculi to do the right thing despite the confusion. By having a clear concept of the distinction, I can simplify away all the complexity without introducing inconsistency.

One can use the usual rules of subtyping  (Cardelli and Wegner 1986) and apply them separately to the types of specifications and their targets, knowing that “subtyping and fixpointing do not commute”, or to be more mathematically precise, fixpointing does not distribute over subtyping, or, said otherwise, the fixpoint operator is not monotonic: If F and G are parametric types, i.e. type-level functions from Type to Type, and F ⊂ G (where ⊂, sometimes written ≤ or <:, is the standard notation for “is a subtype of”, and for elements of Type → Type means ∀ t, F t ⊂ G t), it does not necessarily follow that Y F ⊂ Y G where Y is the fixpoint operator for types.8989The widening rules for the types of specification and their fixpoint targets are different; in other words, forgetting a field in a target record, or its some of its precise type information, is not at all the same as forgetting that field or its precise type in its specification (which introduces incompatible behavior with respect to inheritance, since extra fields may be involved as intermediary step in the specification, that must be neither forgotten, nor overridden with fields of incompatible types). If the two entities are treated as a single one syntactically and semantically, as all OO languages so far have done, then their typesystem will have to encode in a weird way a pair of subtly different types for each such entity, and the complexity will have to be passed on to the user, with the object, and each of its field having two related but different declared types, and potentially different visibility settings. Doing this right involves a lot of complexity, both for the implementers and for the users, at every place that object types are involved, either specified by the user, or display to him. Then again, some languages may do it wrong by trying to have the specification fit the rules of the target (or vice versa), leading to inconsistent rules and consistently annoying errors. A typical way to record specification and target together is to annotate fields with visibility: public (visible in the target) yet possibly with a more specific type in the target than in the specification (to allow for further extensions that diverge from the current target); fields marked protected (visible only to extensions of the specification, not in the target); and fields marked private (not visible to extensions of the specification, even less so to the target; redundant with just defining a variable in a surrounding let scope). I retrieve these familiar notions from C++ and Java just by reasoning from first principles and thinking about distinct but related types for a specification and its target. Now, my opinion is that it is actually better to fully decouple the types of the target and the specification, even in an “implicit pair” conflating the two: Indeed, not only does that means that types are much simpler, that also mean that intermediate computations, special cases to bootstrap a class hierarchy, transformations done to a record after it was computed as a fixpoint, and records where target and specification are out of sync because of effects somewhere else in the system, etc., can be safely represented and typed, without having to fight the typesystem or the runtime.

Notice how the type self of the module context is recursively constrained by self ⊂ required self), whereas the type super of the value in focus being extended is constrained by super ⊂ inherited self, and the returning a value is of type provided self ∩ super, and there is no direct recursion there (but there can be indirectly if the focus is itself referenced via self somehow). Those familiar with universal quantifiers may also notice how the quantification of self and super, in absence of reflective capabilities, pretty much forces those functions to be well-behaved with respect to gracefully passing through any call to a method they do not define, override or otherwise handle. Finally, notice how, as with the simpler NNOOTT variant above, the types self and referenced self refer to the module context, whereas the types super and provided self refer to some value in focus, that isn’t at all the same as the module context for open modular extensions in general.

In the fix function, I implicitly define a fixpoint self via suitable recursive subtyping constraints. I could instead make the last constraint a definition self = Y (inherited ∩ provided) and check the two subtyping constraints about top and referenced. As for the type of mix, though it looks identical with ModExt as the NNOOTT type previously defined with NModExt, there is an important but subtle difference: with ModExt, the arguments being intersected are not of kind Type as with NModExt, but Type → Type, where given two parametric types f and g, the intersection f∩g is defined by (f∩g)(x) = f(x)∩g(x). Indeed, the intersection operation is defined polymorphically, and in a mutually recursive way for types, functions over types, etc.

6.3.7 Typing Advantages of OO as Modular Extensions🔗

By defining OO in terms of the λ-calculus, indeed in two definitions mix and fix, I can do away with the vast complexity of “object calculi” of the 1990s, and use regular, familiar and well-understood concepts of functional programming such as subtyping, bounded parametric types, fixpoints, existential types, etc. No more self or MyType “pseudo-variables” with complex “matching” rules, just regular variables self or MyType or however the user wants to name them, that follow regular semantics, as part of regular λ-terms.9191Syntactic sugar may of course be provided for optional use, that can automatically be macro-expanded away through local expansion only; but the ability to think directly in terms of the expanded term, with simple familiar universal logic constructs that are not ad hoc but from first principles, is most invaluable.


OO can be defined and studied without the need for ad hoc OO-specific magic, making explanations readily accessible to the public. Indeed, defining OO types in term of LaTeX deduction rules for ad hoc OO primitives is just programming in an informal, bug-ridden metalanguage that few are familiar with, with no tooling, no documentation, no tests, no actual implementation, and indeed no agreed upon syntax much less semantics…9292See Guy Steele’s keynote “It’s Time for a New Old Language” at the Principles and Practice of Parallel Programming 2017 conference about the “Computer Science Metanotation” found in scientific publications.


the very opposite of the formality the authors affect.

Not having OO-specific magic also means that when I add features to OO, as I will demonstrate in the rest of this book, such as single or multiple inheritance, method combinations, multiple dispatch, etc., I don’t have to update the language to use increasingly more complex primitives for declaration and use of prototypes or classes. By contrast, the “ad hoc logic” approach grows in complexity so fast that authors soon may have to stop adding features or find themselves incapable of reasoning about the result because the rules for those “primitives” boggle the mind.9393Authors of ad hoc OO logic primitives also soon find themselves incapable of fitting a complete specification within the limits of a conference paper, what’s more with intelligible explanations, what’s more in a way that anyone will read. The approach is too limited to deal even with the features 1979 OO  (Cannon 1979), much less those of more modern systems. Meanwhile, readers and users (if any) of systems described with ad hoc primitives have to completely retool their in-brain model at every small change of feature, or introduce misunderstandings and bugs, instead of being able to follow a solidly known logic that doesn’t vary with features.


Instead, I can let logic and typing rules be as simple as possible, yet construct my object features to be as sophisticated as I want, without a gap in reasoning ability, or inconsistency in the primitives.

My encoding of OO in terms of “modular extension”, functions of the form mySpec (self : Context, super : Focus) : Focus, where in the general “open” case, the value under Focus is different from the Context, is also very versatile by comparison to other encodings, that are typically quite rigid, specialized for classes, and unable to deal with OO features and extensions. Beyond closed specifications for classes, or for more general prototypes, my ModExt type can scale down to open specifications for individual methods, or for submethods that partake in method combination; it can scale up to open specifications for groups of mutually defined or nested classes or prototypes, all the way to open or closed specifications for entire ecosystems.

More importantly, my general notion of “modular extension” opens an entire universe of algebraically well-behaved composability in the spectrum from method to ecosystem; the way that submethods are grouped into methods, methods into prototypes, prototypes into classes, classes into libraries, libraries into ecosystems, etc., can follow arbitrary organizational patterns largely orthogonal to OO, that will be shaped the evolving needs of the programmers, yet will at all times benefit from the modularity and extensibility of OO.

OO can be one simple feature orthogonal to many other features (products and sums, scoping, etc.), thereby achieving reasonability, i.e. one may easily reason about OO programs this way. Instead, too many languages make “classes” into a be-all, end-all ball of mud of more features than can fit in anyone’s head, interacting in sometimes unpredictable ways, thereby making it practically impossible to reason about them, as is the case in languages like C++, Java, C#, etc.

6.3.8 Typing First-Class OO🔗

I am aiming at understanding OO as first-class modular extensibility, so I need to identify what kind of types are suitable for that. Typing individual prototypes that only contain fields of concrete primitive types is easy. The hard part is to type classes with abstract methods, and more generally specifications wherein the type of the target recursively refers to itself through the open recursion on the module context.

Happily, my construction neatly factors the problem of OO into two related but mostly independent parts: first, understanding the target, and second, understanding its instantiation via fixpoint.

I already discussed in Rebuilding Class OO how a class is a prototype for a type descriptor: the target is a record that describes one type and a set of associated functions. The type is described as a table of field descriptors (assuming it’s a record type; or a list of variants for a tagged union, if such things are supported; etc.), a table of static methods, a table of object methods, possibly a table of constructors separate from static methods, etc. A type descriptor enables client software to be coded against its interface, i.e. being able to use the underlying data structures and algorithms without having to know the details and internals.

A first-class type descriptor is a record whose type is existentially quantified:  (Cardelli and Wegner 1986; Mitchell and Plotkin 1988; Pierce and Turner 1993) as per the Curry–Howard correspondence, it is a witness of the proposition according to which “there is a type T that has this interface”, where the interface may include field getters (functions of type T → F for some field value F), some field setters (functions of type T → F → T for a pure linear representation, or T → F 1 if I denote by a “function” with side-effects), binary tests (functions of type T → T → 2), binary operations (functions of type T → T → T), constructors for T (functions that create a new value of type T, at least some of which without access to a previous value of type T), but more generally any number of functions, including higher-order functions, that may include the type T zero, one or arbitrarily many times in any position “positive” or “negative”, etc. So far, this is the kind of thing you could write with first-class ML modules, which embodies first-class modularity, but not modular extensibility.

Now, if the typesystem includes subtypes, extensible records, and fixpoints involving open recursion, e.g. based on recursively constrained types  (Eifrig et al. 1995b,a), then those first-class module values can be the targets of modular extensions.

And there we have first-class OO capable of expressing classes.

Regarding subtyping, however, note that when modeling a class as a type descriptor, not only is it absolutely not required that a subclass’s target should be a subtype of its superclass’s target (which would be the NNOOTT above), but it is not required either that a subclass’s specification should be a subtype of its superclass’s specification. Indeed, adding new variants to a sum type, which makes the extended type a supertype of the previous, is just as important as adding fields to a product type (or specializing its fields), which makes the extended type a subtype of the previous. Typical uses include extending a language grammar (as in Garrigue (2000)), defining new error cases, specializing the API of some reified protocol, etc. In most statically typed OO languages, that historically mandate the subclass specification type to be a subtype of its superclass specification types, programmers work around this limitation by defining many subclasses of each class, one for each of the actual cases of an implicit variant; but this coping strategy requires defining a lot of subclasses, makes it hard to track whether all cases have been processed; essentially, the case analysis of the sum type is being dynamically rather than statically typed.

Note on Types for Second-Class Class OO Types for second-class classes can be easily deduced from types for first-class classes: A second-class class is “just” a first-class class that happens to be statically known as a compile-time constant, rather than a runtime variable. The existential quantifications of first-class OO and their variable runtime witnesses become unique constant compile-time witnesses, whether global or, for nested classes, scoped. This enables many simplifications and optimizations, such as lambda-lifting (making all classes global objects, modulo class parameters), and monomorphization (statically inlining each among the finite number of cases of compile-time constant parameters to the class), and inlining globally constant classes away.

However, you cannot at all deduce types for first-class classes from types for second-class classes: you cannot uninline constants, cannot unmake simplifying assumptions, cannot generalize from a compile-time constant to a runtime variable. The variable behavior essentially requires generating code that you wouldn’t have to generate for a constant. That is why typing first-class prototypes is more general and more useful than only typing second-class classes; and though it may be harder in a way, involving more elaborate logic, it can also be simpler in other ways, involving more uniform concepts.

6.3.9 First-Class OO Beyond Classes🔗

My approach to OO can vastly simplify types for it, because it explicitly decouples concepts that previously people implicitly conflated: not only specifications and their targets, but also modularity and extensibility, fixpoints and types.

By decoupling specifications and targets, I can type them separately, subtype them separately, not have to deal with the extreme complexity of the vain quest of trying to type and subtype them together.

By decoupling modularity and extensibility, I can type not just closed specifications, but also open specifications, which makes everything so much simpler, more composable and decomposable. Individual class, object, method, sub-method specifications, etc., can be typed with some variant of the C → V → V pattern, composed, assembled in products or co-products, etc., with no coupling making the unit of specification the same as the unit of fixpointing.

Finally, with typeclass-style (as in Class-style vs Typeclass-style), the unit of fixpointing need not be a type descriptor; it could be a value without an existential type, or a descriptor for multiple existential types; it could be a descriptor not just for a finite set of types, but even an infinite family of types, etc. In an extreme case, it can even be not just a type descriptor, but the entire ecosystem — a pattern actively used in Jsonnet or Nix (though without formal types).

To build such records, one may in turn make them the targets of modular extensions, such that first-class OO can express much more than mere “classes”, especially so than second-class classes of traditional Class OO. First-class OO can directly express sets of cooperating values, types and algorithms parameterized by other values, types and algorithms.

6.3.10 OO Type Theory🔗

Types for OO is a vast topic of which I am not a specialist, for which I am incapable of producing and presenting the Ultimate Theory. Instead, I invite you to read some of the better papers I’ve managed to identify and collect in my annotated bibliography, with the hope that the notes I wrote on these papers will be helpful to you.9494Inasmuch as I’m still alive to write a next edition to this book, I appreciate your feedback in updating or improving the list below, as well as this book in general.

My very favorite papers are Eifrig et al. (1995b,a), that have the exact right approach to types for OO: start from a sound, minimal yet expressive enough general-purpose type theory, then build OO in a couple of simple λ-terms under this type theory. A decade or two later come Kiselyov and Lämmel (2005) and Gale (2015), who also have the right attitude of just building OO on top of a general-purpose FP language, but choose Haskell as a now-practical substrate instead. Also, I love Allen et al. (2011) because it shows you can just type multiple dispatch and multiple inheritance, topics that most type theorists don’t even try to address when considering OO, even though it could have been three even greater papers if things were factored the right way.

Then come papers that bring useful insight, though they ultimately fail to offer a positive solution to the actual problem designing good OO with good types, because it is incompatible with some of their self-inflicted assumptions or constraints: Pierce and Turner (1993), Pierce (2002), Oliveira (2009), Amin et al. (2016), Black et al. (2016), Jones et al. (2016).

Now there are papers that successfully type OO, and should be praised for it and for their other innovations—yet take the bad approach of starting with a toy calculus, which cannot generalize to anything useful in practice, often with much complexity and many restrictions so as to maintain conflation of specification and target. I am impressed but I want to tell the authors: look, not a single soul cares one damn about your toy object system—not even yourself, obviously, since not even you care to use it to build any real software with it. And your approach cannot possibly scale to a real object system. Instead, you’ve rested logic on top of brittle OO, when logic should instead be the solid foundation on top of which to build OO. A travesty, an inversion of right and wrong, and a waste of tremendous brainpower. Rémy (1994), Fisher et al. (1994), Fisher (1996), Bruce (1996), Bruce et al. (1997).

Finally, some publications are just bad cases of the NNOOTT, with heaps of pointless formalism piled on top to hide just how misguided the authors are, even though most of them came even after the NNOOTT had been utterly debunked. They should serve as cautionary tales for how even brilliant minds can go wrong and have a negative impact on science when they become attached to flawed assumptions they can’t let go even after these assumptions have been debunked: Cardelli (1984), Cardelli and Wegner (1986), Abadi and Cardelli (1996b,a), Cartwright and AbdelGawad (2013), AbdelGawad (2014).

6.3.11 OO Type Practice🔗

I shook my head at theorists who put types on top of toy object systems rather than underneath; but at least those I cited produced sound typesystems. What then shall I say about practitioners who do this at industrial scale on top of object systems so overgrown that no one can conceivably hold them in their head, much less reason about their logical soundness? On what quicksands are they having millions of programmers build billions of lines of actual code? What a waste at world-wide scale.

Thus, for instance, building a typesystem on top of Java has occupied the minds of hundreds of top computer scientists over decades, publishing at top conferences, pouring billions of dollars in research and engineering into creating the best possible system given these constraints. Could this typesystem pass the minimal bar for a typesystem, that of being sound? No—types give you no guarantees  (Amin and Tate 2016). At the same time the expressiveness of the typesystem was deliberated stunted and restricted so the typesystem could guarantee termination in reasonable finite time. Did that succeed? Also no—typechecking is Turing-equivalent  (Grigore 2017). Programmers are deliberately deprived of the power to do good, but the power to do bad hasn’t been stopped one bit.