In the field of object-oriented programming, theory and practice have been growing apart considerably. Programming language designers and compiler builders struggled with issues like method overriding, multiply inheritance, templates, etc., which bore not much overlap with the features for which theoreticians were developing the underlying theory. Of course, some of the important insights into object-orientation were of great benefit to OO programming, but for some of the issues where practitioners could use some help, theoretical support was lacking.
Giuseppe Castagna, the author of this book, directs his attention to some of these neglected areas. With his PhD research that he finished in 1994, he has made a profound contribution to the theory of object-oriented programming with several break-throughs especially in those neglected areas. This book is a revised and extended version of his PhD thesis. Special effort has been put into making the book readable and interesting for both theoreticians and practitioners.
Castagna deviated from the traditional paths in this field, first of all, by directing his attention mainly towards ad-hoc polymorphism instead of parametric polymorphism [CW85]. Parametric polymorphism is when a function works uniformly on a range of types. In practice, parametric polymorphism is often supported through features like subtyping and templates. Ad-hoc polymorphism is obtained when a function works on several different types and may behave in unrelated ways for each type. This form of polymorphism is often supported through features like method overloading and overriding with late-binding on method invocations.
As mentioned earlier, the majority of theoreticians working on (OO) programming languages focus on parametric polymorphism. Hence, problems specific to ad-hoc polymorphism remained unsolved, many of which are tackled by Castagna. Particularly useful for OO practitioners is that Castagna also pays considerable attention to the question of how the developed theory can be put to use in practical OO programming languages.
The other main aspect in which Castagna deviated from traditional paths is in his approach towards methods. In many languages, methods are thought to be residing within objects. Concepts like method overriding proved difficult to incorporate in formalizations based on this viewpoint. Castagna, however, used instead of such an object-central approach, a message-central approach. In this appoach, methods are thought to be residing not within the objects, but within the messages.
As a basis for his formalizations, Castagna has defined a calculus called &. &-calculus is a simply-typed -calculus with subtyping which he extended with overloaded functions. An overloaded function contains several ordinary functions called branches. It can be applied to an argument in the same way as an ordinary function can. The effect of such an overloaded function application is that the branch best-matching with the argument is chosen and applied (ordinary function application) to the argument. The criterion for best-matching is the run-time type of the argument. In this way, the fundamental concept of type dependence is incorporated in the calculus. This concept is essential to features related to ad-hoc polymorphism like method overriding with late-binding. It allowed Castagna to formalize these features by mapping OO-messages to overloaded functions and the individual methods to the branches of those overloaded functions.
One benefit for OO programming can immediately be gained from this formalization. It has always been a difficult issue which typing restrictions should be placed on method/operator overloading and overriding. One would like to provide the programmer with as much freedom as possible while still retaining type-safety, i.e. avoid run-time errors related to typing. From Castagnas formalization it follows that overloading and overriding are two sides of the same medal. Moreover, the exact typing rules that are necessary and sufficient can be deduced from the typing rules of &-calculus and the formalization OO messages as overloaded functions.
The potential of &-calculus even trancends simple method overloading and overriding. It turns out that the multi-methods of CLOS (methods that have more than one receiver) can also be formalized using &-calculus. Again the exact typing rules for method overloading and overriding in the context of multi-methods can be deduced.
Not only has &-calculus and Castagnas work on formalization of OO programming language potential for practical gains in the form of advanced features w.r.t. type-safe ad-hoc polymorphism. Castagna also once and forall settled a dispute among theoriticians about whether to use a covariant or a contravariant rule for subtyping on function types. I will spare you the details of this debate, but believe me that it caused much controversy. Chapter 5, "Covariance and contravariance: conflict without a cause" (also published as a journal paper [Cas95]) deals specifically with this matter. Castagna points out that in &-calculus, there is room for both and covariance and contravariance each play an important but distinct role.
Parametric polymorphism is not ignored in the book. In part two, ad-hoc and parametric polymorphism are integrated in a calculus with a second-order type system that incorporates overloaded functions. With this calculus, the "loss of information problem," the cause of the necessity in certain languages for the infamous down-casts, could be solved. Furthermore, it can be used to study the interaction between advanced features related to parametric polymorphism like C++'s templates and those related to ad-hoc polymorphism like multi-methods.
Since the book holds valuable gems for both OO programming practitioners and theoreticians in the field of type theory, Castagna has put much effort in making the book readable for both interest groups. He uses several techniques to obtain this. First of all, certain sections are marked with a "dangerous bend" or a "detour" indicating that those sections are difficult or "skippable," respectively. Secondly, there is a small chapter in the beginning of the book that describes which are the most appropriate reading paths for the different interest groups (Castagna distinguishes three: practitioners, teachers, and scholars). Finally, Chapter 2 contains a superb overview of the entire book for the hurried reader. It can also be used to determine which chapters one would like to study in more detail.
Summarizing, this book bridges the gap between theory and practice of OO programming. Without making theoretical concessions, Castagna manages to make typing issues accessible to both practitioners and theoreticians through a well-thought out and clear presentation. The important contributions he has made are a major step forward. I would like to recommend this book especially to OO programming practitioners who would like to obtain a more thorough understanding of the underlying issues, and to teachers and scholars in this field.

Maurice Van Keulen

Review of "Zentralblatt Für Mathematik Und Ihre Grenzgebiete"

The book provides a model for uniform analysis of the basic issues of object-oriented programming. It is a revised and extended version of the author's Ph. D. thesis. The book is self contained and may be used by researchers, teachers and practitioners as well. In a short Presentation, the author hints the reader to the most appropriate reading path. The book contains three parts. The first one, "Introduction", has two chapters. Chapter 1 is about the background of -calculus. Chapter 2 is a quick overview of the book, made chapter by chapter. The main part is the second one, containing the chapters 3 to 10. It is named "Simple Typing" and is devoted to the author's model of object-oriented programming. Chapter 3, "Object-oriented programming", discusses the kernel features of object-oriented programming by means of a mini object-oriented language called "Kernel Object-Oriented Language" (KOOL). It is a functional language and follows the style of Simula. It includes those features considered by the author as necessary for a unified foundation of object-oriented programming (classes, methods, overloading, late binding, inheritance, extended classes, type checking). Chapter 4, "The &-calculus" presents the overloaded-based model. The symbol & is an operator used to glue two functions together in an overloaded one. Thus, the term M&N denotes an overloaded function of two branches, M and N, one of which will be selected according to the type of the argument. Chapter 5, "Covariance and contravariance: conflict without a cause" clarifies the role of these topics in subtyping. The author uses the introduced model to argue that covariance and contravariance appropriately characterise two distinct and independent mechanisms. They are viewed as non antagonistic concepts, each of them having its own use: covariance for specialisation and contravariance for substituitivity. The chapter ends by three "golden rules' that summarise its content: 1. do not use (left) covariance for arrow subtyping; 2. use covariance to override parameters that drive dynamic method selection; 3. when overriding a binary (or n-ary) method, specify its behaviour not only for the actual class but also for its ancestors. Chapter 6, "Strong Normalization" studies the normalization properties of &. It is shown that -calculus is not strongly normalising. It is given a sufficient condition to have strong normalization and are defined two expressive systems that satisfy it. These systems are expressive enough to model object-oriented programming and are used in Chapter 10 to study the mathematical meaning of overloading. Chapter 7 presents three different systems directly issued from &: 1. the extension of & by addition of explicit coercions; 2. a modification of &-calculus with a new reduction rule; 3. a calculus in which regular functions and overloaded ones are introduced by the same abstraction operator, which therefore unifies them. Chapter 8 is devoted to formal interpretation of KOOL language in the introduced overloading based modeL Due to the fact that & is not adequate to a formal study of the properties of object-oriented languages, a new meta language called -object is introduced to prove properties of an object-oriented language. The -object language enriches the &-calculus by some new features (commands to define new types, to work on their representation, to handle the subtyping hierarchy, to change the type of a term or to modify a discipline of dispatching etc.) that are necessary to reproduce the constructs of a programming language and lacking in &. Chapter 9, "Imperative features and other widgets", presents in a less formal manner some features of practical interest which can be included in KOOL. Thus, this functional language can be upgraded to a realistic object-oriented language adding some imperative commands. It may be also used a unique form of application both for overloaded and regular functions. At lest, the type system of KOOL may be modified to implement signatures. Chapter 10, "Semantics", goes deeply inside the following problems poses by the semantics of &-calculus: pre-order relation between types; type-dependent computation; late-binding; impredicativity introduced by the definition of subtyping for the overloaded types. It is underlined that some of these issues can not be handled in the &-calculus. This is a motivation to study in the Part III of the book a second order object-oriented language. This mechanism is base on Girard' system F, which is enriched to correspond to the implementation of fate binding. There are still some features that are not straightforwardly handled, such as super and coerce. In the lest chapter, "Conclusion", the author fixes his book in the frame of other related work.

T. Balanescu (Bucuresti).

Review of "The USENIX Association Newsletter"

The rough history of the prograssion of objct-oriented programming languages from Simula to Smalltalk, Eiffel, C++, CLOS, and Java is known. Most of these languages follow Simula's style. But CLOS and a few others are multiple dispatching. This means that there are discussion of Simula-style programming, but none of the multiple dispatching languages. What is even less known is the way in which "overloading" developed and the paucity of research on it.
Castagna has done a brilliant job of modeling the concepts involved in overloading as well as those needed to compare the different styles of object-oriented programming. This is not an easy read, but you'll come away having learned something.

Peter H. Salus

Back to my home page