Foundations of Object-Oriented Languages: Types and Semantics

✍ Scribed by Kim B. Bruce

• Publisher: The MIT Press
• Year: 2002
• Tongue: English
• Leaves: 405
• Category: Library

✦ Synopsis

This is a useful introduction to the theory behind data types in object oriented (OO) languages. It starts at a very readable pace. The first section (about 100 pages) covers the basics of OO languages and OO features, and establishes a working vocabulary. For example, it introduces the very distinct notions of subclass and subtype early on. That is important, if only because words like "subtype" have different meanings when used by different authors. Barbara Liskov, for example, used a semantic definition for "subtype" in her famous substitutability principle, a definition that can not be checked by automatic tools. Here, the definition talks only about the information you might find in a Java interface or C++ abstract class, and can be checked automatically. This early discussion also defines the problem to be solved: creating programming languages that are richly expressive, that compile to efficient code, and that are rigorously type safe, goals that often conflict. The clear statement of the problem is very informative, by itself, and casual readers might stop at this point.The next brief section defines a mathematical notation, a lambda calculus, for discussing types. In this calculus, a "record" or "struct" keyword is an operator that aggregates other types together into a new unit, and C++ templates are functions that generate new types. This calculus feeds into a formal logic that proves statements about types the same way standard arithmetic proves statements about numbers. This isn't nearly as daunting as a normal proof of program correctness, by the way. Behavioral correctness deals with a program's changes of state over time; this treats the program as a static, compile-time entity. Also, for better or worse, it skips the most of the category theory that often accompanies type formalisms.The remaining 200 pages or so constitute the real meat of the discussion. Bruce takes the first section's intuitive ideas about types and languages, phrases them in the second section's formalism, and uses that language to analyze several small, purpose-built OO languages with different type systems. Along the way, Bruce makes a few remarkable claims. One is that, although multiple inheritance can cause pragmatic problems for developers, it's no big deal for the mathematical tools. The real problem is deciding what you mean by multiple inheritance, where C++ and Eiffel provide only two of the possible answers. (Agreed - coming up with something useful to say is often harder than saying it.) Another is that classes really aren't necessary for strong OO typing. Classes are just names for collections of features, and it's the features in the collections that matter. (I see the theory, but I'm not sure that this leads to practical improvements in language design.) Many of these results are quite clear even if you, like me, skip some of the hairier proofs. This is certainly not a book for a beginner to programming or to OO. It's really about the theory of how languages work. It will be of use to developers who create new languages, compilers, or language-smart CASE tools. I doubt that most others will find information relevant to their work. If you really care about the fussy bits of an OO language's type system, though, this book will be very helpful.//wiredweird

✦ Table of Contents

MIT Press - Foundations of Object-Oriented Languages Types and Semantics 026202523X.pdf......Page 0
Contents......Page 8
List of Figures......Page 12
Preface......Page 16
Part I Type Problems in Object-Oriented Languages......Page 22
Introduction......Page 24
Fundamental Concepts of Object- Oriented Languages......Page 38
Type Problems in Object- Oriented Languages......Page 54
Adding Expressiveness to Object- Oriented Languages......Page 70
Understanding Subtypes......Page 92
Type Restrictions on Subclasses......Page 110
Varieties of Object- Oriented Programming Languages......Page 116
Historical Notes and References for Section I......Page 134
Part I I Foundations: The Lambda Calculus......Page 138
and the Lambda Calculus......Page 140
Calculus......Page 162
Historical Notes and References for Section II......Page 188
Part I I I Formal Descriptions of Object-Oriented Languages......Page 192
SOOL, a Simple Object- Oriented Language......Page 194
A Simple Translational Semantics of Objects and Classes......Page 222
Improved Semantics for Classes......Page 246
SOOL¡¯ s Type System Is Safe (and Sound)......Page 260
Completing SOOL: super, nil, information Hiding, and Multiple Inheritance......Page 284
Historical Notes and References for Section III......Page 304
Part IV Extending Simple Object-Oriented Languages......Page 310
Adding Bounded Polymorphism to SOOL......Page 312
Adding MyType to Object- Oriented Programming Languages......Page 320
Match- Bounded Polymorphism......Page 352
Simplifying: Dropping Subtyping for Matching......Page 370
Historical Notes and References for Section IV......Page 384
Bibliography......Page 388
Index......Page 400