This book develops a theory of objects as a foundation for object-oriented languages and programming. Our theory provides explanations for object-oriented notions in terms of a few basic primitives, and can be useful for the design and understanding of programming languages.

There is a well-established theory of functions, the -calculus, that serves as a foundation for procedural languages. Our treatment of object-oriented languages largely parallels existing literature on procedural languages. However, our theory of objects is self-contained; it is the first that does not require explicit reference to functions or procedures.

We study object calculi, which are formalisms at the same level of abstraction as function calculi, but based exclusively on objects rather than functions. Unlike function calculi, object calculi are designed specifically for clarifying features of object-oriented languages. There is a wide spectrum of relevant object calculi, just as there is a wide spectrum of function calculi. We investigate untyped, simply-typed, and polymorphic calculi, with both functional and imperative semantics.


The material in this book is based on research that we carried out during the past three years; some of this material has appeared in conference and journal articles. In the development of our ideas, we built on previous work on the foundations of object-oriented programming as represented, for example, by the collection of papers edited by Gunter and Mitchell. That body of work produced an understanding of subtyping and several explanations of objects in terms of functions and records. We discuss some of those previous results in the course of the book.

The chapters of this book are grouped in four main parts, bracketed between a Prologue and an Epilogue. The initial part, the Review, contains a general non-technical explanation of object-oriented concepts. Part I describes untyped and simply-typed formalisms for objects and classes. Part II discusses polymorphism, data abstraction, and the Self type, along with their connections to subtyping and subclassing. Part III investigates subtyping between type operators, which is more powerful than simple subtyping and supports more flexible inheritance (for example, for binary methods). The final sections of the book contain an Appendix summarizing our type rules, a list of figures, a list of tables, a list of notations, and a list of languages.


The intended audience of the book consists of computer scientists, professionals, and senior and graduate students with an interest in modern language issues. The Review is accessible to programmers familiar with at least one object-oriented language. It provides a general, concise, and language-independent perspective on object-oriented concepts, and should make up for lack of broad knowledge about objects. An acquaintance with the -calculus and with type systems is helpful background for the rest of the book. Part I is technical but relatively easy; it does not assume much expertise or skill in programming-language theory. Parts II and III are more challenging.

Subsets of this book are suitable for advanced courses on the theory, design, and structure of programming languages, even if not entirely devoted to object-oriented languages. The book can be used to complement standard object-oriented analysis, design, and programming texts.

 Luca Cardelli