Tài liệu Adaptive Object-Oriented Software The Demeter Method pdf

Adaptive Object-Oriented

Software

The Demeter Method

Karl Lieberherr

College of Computer Science

Northeastern University Boston

Copyright (C) 1996 by Karl J. Lieberherr

All rights reserved by PWS Publishing Company

To order the book, send email to: [email protected]

Put on the Web with permission by Mike Sugarman, PWS.

To Ruth, Andrea and Eva

Produced with Acrobat 4.0.

Author’s email

[email protected]

Contents

Foreword by Gregor Kiczales and John Lamping xxiii

Preface xxv

1 Introduction 1

1.1 EVOLUTIONARY LIFE CYCLE WITH ADAPTIVE SOFTWARE : : : : : 1

1.1.1 How is Adaptiveness Achieved? : : : : : : : : : : : : : : : : : : : : 2

1.1.2 Applications of Adaptiveness : : : : : : : : : : : : : : : : : : : : : : 2

1.1.3 Adaptiveness with the Demeter Method : : : : : : : : : : : : : : : : 2

1.1.4 Demeter Life-Cycle : : : : : : : : : : : : : : : : : : : : : : : : : : : 3

1.1.5 Symmetry Between Adaptive Programs and Customizers : : : : : : 5

1.1.6 Symmetry Between Ob ject Descriptions and Customizers : : : : : : 5

1.2 DISADVANTAGES OF OBJECT-ORIENTED SOFTWARE : : : : : : : : 6

1.3 ADAPTIVE PROGRAMMING : : : : : : : : : : : : : : : : : : : : : : : : : 7

1.4 PROPAGATION PATTERNS : : : : : : : : : : : : : : : : : : : : : : : : : : 10

1.5 CUSTOMIZATION : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 12

1.6 SUMMARY : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 16

1.7 EXERCISES : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 16

1.8 BIBLIOGRAPHIC REMARKS : : : : : : : : : : : : : : : : : : : : : : : : : 17

2 Introduction to Ob ject-Oriented Software 18

2.1 CONCEPTS : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 24

2.1.1 Abstractions : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 26

2.1.2 Classes, Methods, and Delayed Binding : : : : : : : : : : : : : : : : 26

2.1.3 Overloading and Delayed Binding : : : : : : : : : : : : : : : : : : : 30

2.1.4 Reduced Dependencies : : : : : : : : : : : : : : : : : : : : : : : : : 30

2.1.5 Sharing : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 30

2.1.6 Making Instances : : : : : : : : : : : : : : : : : : : : : : : : : : : : 33

2.2 EASE OF EVOLUTION : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 33

2.3 TERMINOLOGY : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 34

2.4 CONVENTIONS : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 35

2.4.1 Symbol Usage : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 36

2.5 EXERCISES : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 36

2.6 BIBLIOGRAPHIC REMARKS : : : : : : : : : : : : : : : : : : : : : : : : : 38

vii

viii CONTENTS

3 From C++ to Demeter 40

3.1 C++ PROGRAM : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 42

3.2 ADAPTIVE PROGRAM : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 55

3.3 EVOLUTION : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 60

3.3.1 Changing Ob ject Structure : : : : : : : : : : : : : : : : : : : : : : : 60

3.3.2 Evolving the Functionality : : : : : : : : : : : : : : : : : : : : : : : 63

3.4 WHAT IS THE PRICE? : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 68

3.5 APPENDIX: FROM C TO C++ : : : : : : : : : : : : : : : : : : : : : : : : 70

3.6 SUMMARY : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 75

3.7 EXERCISES : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 75

3.8 BIBLIOGRAPHIC REMARKS : : : : : : : : : : : : : : : : : : : : : : : : : 76

4 Thinking Adaptively 77

4.1 KEY IDEAS : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 80

4.1.1 Inventor's Paradox : : : : : : : : : : : : : : : : : : : : : : : : : : : : 80

4.1.2 Stepwise Renement : : : : : : : : : : : : : : : : : : : : : : : : : : : 81

4.1.3 Representation/Interface Independence : : : : : : : : : : : : : : : : 81

4.2 MODELING COMPLEX SYSTEMS : : : : : : : : : : : : : : : : : : : : : : 83

4.3 JUSTIFICATION : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 86

4.4 CUSTOMIZATION : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 87

4.5 THE ITINERARY PROBLEM : : : : : : : : : : : : : : : : : : : : : : : : : 88

4.5.1 Customizing the Adaptive Program : : : : : : : : : : : : : : : : : : 90

4.5.2 Transporting Ob jects : : : : : : : : : : : : : : : : : : : : : : : : : : 95

4.6 POSITIONING IN THE HISTORY OF SOFTWARE DEVELOPMENT : : 96

4.7 THE TOOLS : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 99

4.8 EXPERIENCES WITH ADAPTIVE SOFTWARE : : : : : : : : : : : : : : 101

4.9 SUMMARY : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 103

4.10 BIBLIOGRAPHIC REMARKS : : : : : : : : : : : : : : : : : : : : : : : : : 104

5 Adaptive Software by Example 112

5.1 CHANGING REQUIREMENTS : : : : : : : : : : : : : : : : : : : : : : : : : 112

5.2 CUSTOMIZING WITH CLASS DICTIONARIES : : : : : : : : : : : : : : : 116

5.3 OBJECT TRAVERSAL AND TRANSPORTATION : : : : : : : : : : : : : 129

5.4 SUMMARY : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 131

5.5 EXERCISES : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 132

5.6 BIBLIOGRAPHIC REMARKS : : : : : : : : : : : : : : : : : : : : : : : : : 134

5.7 SOLUTIONS : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 134

6 Class Dictionary Graphs and Ob jects 135

6.1 INTRODUCTORY EXAMPLE : : : : : : : : : : : : : : : : : : : : : : : : : 136

6.2 CLASS DICTIONARY GRAPH RULES : : : : : : : : : : : : : : : : : : : : 144

6.2.1 Convenient Extensions : : : : : : : : : : : : : : : : : : : : : : : : : 146

6.3 OBJECTS : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 149

6.3.1 Textual Representation : : : : : : : : : : : : : : : : : : : : : : : : : 150

6.3.2 Size : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 152

CONTENTS ix

6.4 TRANSLATION TO C++ : : : : : : : : : : : : : : : : : : : : : : : : : : : : 152

6.5 PARAMETERIZED CLASSES : : : : : : : : : : : : : : : : : : : : : : : : : 156

6.6 CLASS DICTIONARY GRAPH DESIGN : : : : : : : : : : : : : : : : : : : 157

6.6.1 Why Alternation Classes are Abstract : : : : : : : : : : : : : : : : : 157

6.6.2 Taxonomy and Class Dictionary Graphs : : : : : : : : : : : : : : : : 157

6.6.3 Construction versus Alternation Edges : : : : : : : : : : : : : : : : 161

6.7 SUMMARY : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 163

6.8 EXERCISES : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 163

6.9 BIBLIOGRAPHIC REMARKS : : : : : : : : : : : : : : : : : : : : : : : : : 166

6.10 SOLUTIONS : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 167

7 Propagation Directives 169

7.1 SIMPLE PROPAGATION DIRECTIVES : : : : : : : : : : : : : : : : : : : 171

7.1.1 Edge Patterns : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 178

7.2 SYNTAX SUMMARY FOR PROPAGATION DIRECTIVES : : : : : : : : 179

7.3 APPLYING PROPAGATION DIRECTIVES : : : : : : : : : : : : : : : : : 182

7.4 AVOIDING INFORMATION LOSS : : : : : : : : : : : : : : : : : : : : : : : 182

7.5 FINDING PROPAGATION DIRECTIVES : : : : : : : : : : : : : : : : : : : 185

7.5.1 Evolution of Propagation Directives : : : : : : : : : : : : : : : : : : 187

7.6 TESTING OF PROPAGATION DIRECTIVES : : : : : : : : : : : : : : : : 188

7.7 OPERATIONS ON PROPAGATION DIRECTIVES : : : : : : : : : : : : : 188

7.7.1 Join Operator : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 188

7.7.2 Merge Operator : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 189

7.7.3 Restrict Operator : : : : : : : : : : : : : : : : : : : : : : : : : : : : 189

7.7.4 Propagation Graph Calculus : : : : : : : : : : : : : : : : : : : : : : 190

7.7.5 Propagation Directive Expressions : : : : : : : : : : : : : : : : : : : 191

7.7.6 Customization Space : : : : : : : : : : : : : : : : : : : : : : : : : : 193

7.8 SUMMARY : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 193

7.9 EXERCISES : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 193

7.10 BIBLIOGRAPHIC REMARKS : : : : : : : : : : : : : : : : : : : : : : : : : 199

7.11 SOLUTIONS : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 200

8 Propagation Patterns 202

8.1 CONNECTION TO LAW OF DEMETER : : : : : : : : : : : : : : : : : : : 202

8.2 OBJECT-ORIENTED IMPLEMENTATION : : : : : : : : : : : : : : : : : : 207

8.3 SYNTAX SUMMARY FOR PROPAGATION PATTERNS : : : : : : : : : : 211

8.4 EXAMPLES : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 212

8.4.1 Graph Algorithms : : : : : : : : : : : : : : : : : : : : : : : : : : : : 212

8.4.2 Chess Board : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 219

8.4.3 Painting a Car : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 220

8.4.4 Meal : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 223

8.4.5 Compiler : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 225

8.5 COMPONENTS: SETS OF PROPAGATION PATTERNS : : : : : : : : : : 225

8.6 EDGE WRAPPERS AND VERTEX WRAPPERS : : : : : : : : : : : : : : 229

8.7 PROGRAMMING WITH PROPAGATION PATTERNS : : : : : : : : : : : 234

x CONTENTS

8.7.1 Evolution Histories : : : : : : : : : : : : : : : : : : : : : : : : : : : 234

8.7.2 Three-Stage Development : : : : : : : : : : : : : : : : : : : : : : : : 237

8.7.3 Propagation and Alternation : : : : : : : : : : : : : : : : : : : : : : 237

8.7.4 Wrappers Simulating Inheritance : : : : : : : : : : : : : : : : : : : : 241

8.7.5 Readers and Writers : : : : : : : : : : : : : : : : : : : : : : : : : : : 243

8.8 SUMMARY : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 245

8.9 EXERCISES : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 246

8.10 BIBLIOGRAPHIC REMARKS : : : : : : : : : : : : : : : : : : : : : : : : : 253

8.11 SOLUTIONS : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 254

9 Propagation Pattern Interpretation 255

9.1 HOW TO RUN A PROPAGATION PATTERN : : : : : : : : : : : : : : : : 256

9.1.1 Discussion of the Rules : : : : : : : : : : : : : : : : : : : : : : : : : 259

9.2 CUSTOMIZER RESTRICTIONS : : : : : : : : : : : : : : : : : : : : : : : : 260

9.2.1 Compatibility Restriction : : : : : : : : : : : : : : : : : : : : : : : : 261

9.2.2 Propagation Restriction : : : : : : : : : : : : : : : : : : : : : : : : : 261

9.2.3 Information Loss Restriction : : : : : : : : : : : : : : : : : : : : : : 262

9.2.4 Delayed Binding Restriction : : : : : : : : : : : : : : : : : : : : : : 265

9.2.5 Inheritance Restriction : : : : : : : : : : : : : : : : : : : : : : : : : 269

9.3 PROPAGATION PATTERN PROPERTIES : : : : : : : : : : : : : : : : : : 271

9.3.1 Alternation Property : : : : : : : : : : : : : : : : : : : : : : : : : : 272

9.3.2 Propagation Directive Satisfaction : : : : : : : : : : : : : : : : : : : 272

9.3.3 Propagation Graph Properties : : : : : : : : : : : : : : : : : : : : : 276

9.3.4 Consistent Ordering : : : : : : : : : : : : : : : : : : : : : : : : : : : 276

9.3.5 Robustness Under Class Dictionary Transformations : : : : : : : : : 277

9.3.6 Access Independence : : : : : : : : : : : : : : : : : : : : : : : : : : 279

9.3.7 Method Selection Rule : : : : : : : : : : : : : : : : : : : : : : : : : 279

9.3.8 Split Alternation Class : : : : : : : : : : : : : : : : : : : : : : : : : 280

9.3.9 Symmetry : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 281

9.3.10 No Wrapper Shadowing : : : : : : : : : : : : : : : : : : : : : : : : : 282

9.3.11 Customizer Analysis : : : : : : : : : : : : : : : : : : : : : : : : : : : 282

9.4 OBJECT-ORIENTED IMPLEMENTATION : : : : : : : : : : : : : : : : : : 285

9.4.1 Exiting Alternation Edges : : : : : : : : : : : : : : : : : : : : : : : 286

9.4.2 Wrapper Pushing : : : : : : : : : : : : : : : : : : : : : : : : : : : : 291

9.4.3 Propagation Patterns with Return Types : : : : : : : : : : : : : : : 293

9.5 SUMMARY : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 296

9.5.1 The Flat Demeter Method : : : : : : : : : : : : : : : : : : : : : : : 297

9.6 EXERCISES : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 298

9.7 BIBLIOGRAPHIC REMARKS : : : : : : : : : : : : : : : : : : : : : : : : : 308

9.8 SOLUTIONS : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 308

CONTENTS xi

10 Transportation Patterns 309

10.1 SPECIFYING OBJECT TRANSPORTATION : : : : : : : : : : : : : : : : 309

10.2 TRANSPORTATION CUSTOMIZER RESTRICTIONS : : : : : : : : : : : 312

10.2.1 Type-Correctness : : : : : : : : : : : : : : : : : : : : : : : : : : : : 314

10.2.2 Traversal Restrictions : : : : : : : : : : : : : : : : : : : : : : : : : : 315

10.2.3 Transportation Restrictions : : : : : : : : : : : : : : : : : : : : : : : 315

10.3 TRANSPORTATION PATTERN EXAMPLES : : : : : : : : : : : : : : : : 318

10.3.1 Triples Example : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 320

10.3.2 Avoiding Conditional Statements : : : : : : : : : : : : : : : : : : : 326

10.3.3 DFT Example : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 327

10.4 CODE GENERATION : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 329

10.4.1 Code Generation with Two Transportation Patterns : : : : : : : : : 330

10.4.2 Combining Two Propagation Patterns : : : : : : : : : : : : : : : : : 343

10.5 SUMMARY : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 344

10.6 EXERCISES : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 345

10.7 BIBLIOGRAPHIC REMARKS : : : : : : : : : : : : : : : : : : : : : : : : : 356

10.8 SOLUTIONS : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 356

11 Class Dictionaries 358

11.1 PARSING : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 363

11.2 LL(1) CONDITIONS AND LEFT-RECURSION : : : : : : : : : : : : : : : 369

11.2.1 Left-Recursion : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 371

11.3 SUMMARY : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 372

11.4 EXERCISES : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 374

11.5 BIBLIOGRAPHIC REMARKS : : : : : : : : : : : : : : : : : : : : : : : : : 379

11.6 SOLUTIONS : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 381

12 Style Rules for Class Dictionaries 382

12.1 LAW OF DEMETER FOR CLASSES : : : : : : : : : : : : : : : : : : : : : 382

12.2 CLASS DICTIONARY GRAPH OPTIMIZATION : : : : : : : : : : : : : : 386

12.2.1 Minimizing Construction Edges : : : : : : : : : : : : : : : : : : : : 387

12.2.2 Minimizing Alternation Edges : : : : : : : : : : : : : : : : : : : : : 388

12.3 PARAMETERIZATION : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 390

12.4 REGULARITY : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 393

12.4.1 Regular Structures : : : : : : : : : : : : : : : : : : : : : : : : : : : : 393

12.5 PREFER ALTERNATION : : : : : : : : : : : : : : : : : : : : : : : : : : : : 394

12.6 NORMALIZATION : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 396

12.7 COGNITIVE ASPECTS OF NOTATIONS : : : : : : : : : : : : : : : : : : : 397

12.8 EXTENDED EXAMPLES : : : : : : : : : : : : : : : : : : : : : : : : : : : : 398

12.8.1 VLSI Architecture Design : : : : : : : : : : : : : : : : : : : : : : : : 398

12.8.2 Business Applications : : : : : : : : : : : : : : : : : : : : : : : : : : 400

12.9 SUMMARY : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 401

12.10 EXERCISES : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 402

12.11 BIBLIOGRAPHIC REMARKS : : : : : : : : : : : : : : : : : : : : : : : : : 402

xii CONTENTS

13 Case Study: A Class Structure Comparison Tool 403

13.1 THE DEMETER METHOD : : : : : : : : : : : : : : : : : : : : : : : : : : : 403

13.1.1 The Demeter Method in a Nutshell : : : : : : : : : : : : : : : : : : 404

13.1.2 Design Checklist : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 404

13.1.3 Analysis/Design/Implementation : : : : : : : : : : : : : : : : : : : : 407

13.2 GROWING ADAPTIVE SOFTWARE : : : : : : : : : : : : : : : : : : : : : 407

13.3 PROBLEM FORMULATION : : : : : : : : : : : : : : : : : : : : : : : : : : 410

13.3.1 Class Dictionary Graph Extension : : : : : : : : : : : : : : : : : : : 410

13.3.2 Precise Problem Statement : : : : : : : : : : : : : : : : : : : : : : : 414

13.4 PROBLEM SOLUTION : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 414

13.4.1 Finding the Class Dictionary : : : : : : : : : : : : : : : : : : : : : : 416

13.4.2 Component superclasses : : : : : : : : : : : : : : : : : : : : : : : : : 417

13.4.3 Component partclusters : : : : : : : : : : : : : : : : : : : : : : : : : 419

13.4.4 Component associated : : : : : : : : : : : : : : : : : : : : : : : : : : 422

13.5 SUMMARY : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 425

13.6 EXERCISES : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 425

13.7 BIBLIOGRAPHIC REMARKS : : : : : : : : : : : : : : : : : : : : : : : : : 428

14 Instructional Ob jectives 429

15 Core Concepts and Implementation 453

15.1 INTRODUCTION : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 454

15.1.1 Background : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 454

15.1.2 Our Results : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 455

15.1.3 Example : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 455

15.1.4 Compatibility, Consistency, and Subclass Invariance : : : : : : : : : 461

15.2 THE SEMANTICS OF ADAPTIVE PROGRAMS : : : : : : : : : : : : : : 466

15.2.1 Graphs : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 466

15.2.2 Paths : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 467

15.2.3 Class Graphs : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 468

15.2.4 Ob ject Graphs : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 469

15.2.5 Traversal Specications : : : : : : : : : : : : : : : : : : : : : : : : : 469

15.2.6 Wrappers : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 471

15.2.7 Adaptive Programs : : : : : : : : : : : : : : : : : : : : : : : : : : : 472

15.2.8 The Target Language : : : : : : : : : : : : : : : : : : : : : : : : : : 473

15.3 IMPLEMENTATION OF ADAPTIVE PROGRAMS : : : : : : : : : : : : : 474

15.4 COMPOSITIONAL CONSISTENCY : : : : : : : : : : : : : : : : : : : : : : 477

15.5 RELATED WORK : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 480

15.6 SUMMARY : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 482

15.7 EXERCISES : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 486

15.8 BIBLIOGRAPHIC REMARKS : : : : : : : : : : : : : : : : : : : : : : : : : 496

CONTENTS xiii

16 Theory of Class Dictionaries 497

16.1 CLASS DICTIONARY GRAPHS : : : : : : : : : : : : : : : : : : : : : : : : 497

16.1.1 Semi-Class Dictionary Graphs : : : : : : : : : : : : : : : : : : : : : 498

16.1.2 Class Dictionary Graph Slices : : : : : : : : : : : : : : : : : : : : : 500

16.1.3 Class Dictionary Graphs : : : : : : : : : : : : : : : : : : : : : : : : 501

16.1.4 Ob ject Graphs : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 502

16.1.5 Inductive Class Dictionary Graphs : : : : : : : : : : : : : : : : : : : 507

16.2 CLASS DICTIONARIES : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 508

16.2.1 Denitions : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 509

16.2.2 Flat Class Dictionaries : : : : : : : : : : : : : : : : : : : : : : : : : 512

16.2.3 Languages : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 514

16.3 LL(1) RULES : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 517

16.4 IMPLICATIONS OF LL(1) RULES : : : : : : : : : : : : : : : : : : : : : : : 521

16.4.1 Printing : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 521

16.4.2 Parsing : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 523

16.4.3 LL(1) Rules and Ambiguous Context-Free Grammars : : : : : : : : 527

16.5 DEMETER DATA MODEL SUMMARY : : : : : : : : : : : : : : : : : : : : 527

16.6 SELF APPLICATION : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 527

16.6.1 Self-Describing Class Dictionary Graphs : : : : : : : : : : : : : : : : 529

16.6.2 Parameterized Class Dictionaries : : : : : : : : : : : : : : : : : : : : 529

16.6.3 Ob ject Graphs : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 531

16.6.4 Mapping to C++ : : : : : : : : : : : : : : : : : : : : : : : : : : : : 532

16.7 KNOWLEDGE PATHS AND OBJECT PATHS : : : : : : : : : : : : : : : : 535

16.8 SUMMARY : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 540

16.9 EXERCISES : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 540

16.10 BIBLIOGRAPHIC REMARKS : : : : : : : : : : : : : : : : : : : : : : : : : 541

17 Selfstudy/Teacher's Guide 542

17.1 INTRODUCTION : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 542

17.2 EXPANDED SYLLABUS : : : : : : : : : : : : : : : : : : : : : : : : : : : : 542

17.3 ASSIGNMENT 1 : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 545

17.3.1 Background Tasks : : : : : : : : : : : : : : : : : : : : : : : : : : : : 545

17.3.2 Part 1: C++ Program Completion : : : : : : : : : : : : : : : : : : : 545

17.3.3 Part 2: Laboratory Guide : : : : : : : : : : : : : : : : : : : : : : : : 547

17.4 ASSIGNMENT 2 : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 547

17.4.1 Background Tasks : : : : : : : : : : : : : : : : : : : : : : : : : : : : 547

17.4.2 Ob jectives : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 547

17.4.3 Part 1: Writing a Pocket Calculator in C++ : : : : : : : : : : : : : 547

17.4.4 Part 2: Checking Your Solution with Demeter : : : : : : : : : : : : 549

17.4.5 Part 3: Learning C++ : : : : : : : : : : : : : : : : : : : : : : : : : 550

17.4.6 Part 4: Develop Your Own Class Dictionary Graph : : : : : : : : : 551

17.5 ASSIGNMENT 3 : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 551

17.5.1 Background Tasks : : : : : : : : : : : : : : : : : : : : : : : : : : : : 551

17.5.2 Part 1: Trip Class Dictionary : : : : : : : : : : : : : : : : : : : : : : 552

17.5.3 Part 2: Inventing and Debugging Class Dictionaries : : : : : : : : : 552

xiv CONTENTS

17.5.4 Part 3: Time Consuming : : : : : : : : : : : : : : : : : : : : : : : : 553

17.5.5 Part 4: Redoing the Last Part with Demeter : : : : : : : : : : : : : 554

17.6 ASSIGNMENT 4 : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 554

17.6.1 Background Tasks : : : : : : : : : : : : : : : : : : : : : : : : : : : : 555

17.6.2 Part 1: Writing a Compiler : : : : : : : : : : : : : : : : : : : : : : : 555

17.6.3 Part 2: Compute the Size of an Expression : : : : : : : : : : : : : : 557

17.6.4 Part 3: Compute the Size of a Class Dictionary : : : : : : : : : : : 557

17.7 ASSIGNMENT 5 : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 558

17.7.1 Background Tasks : : : : : : : : : : : : : : : : : : : : : : : : : : : : 559

17.7.2 Part 1: Write Your Own Propagation Pattern : : : : : : : : : : : : 559

17.7.3 Part 2: Evolution of a Programming Tool : : : : : : : : : : : : : : : 559

17.8 LEARNING C++ WITH DEMETER : : : : : : : : : : : : : : : : : : : : : 563

17.8.1 Class Library Generator : : : : : : : : : : : : : : : : : : : : : : : : : 563

17.8.2 Member Function Skeleton Generator : : : : : : : : : : : : : : : : : 563

17.8.3 Simulating the Demeter Library : : : : : : : : : : : : : : : : : : : : 564

18 Glossary 565

18.1 DEFINITIONS : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 565

18.2 QUICK REFERENCE GUIDE WITH SYNTAX SUMMARY : : : : : : : : 578

18.3 SYNTAX DEFINITIONS : : : : : : : : : : : : : : : : : : : : : : : : : : : : 585

18.3.1 Class Dictionary Syntax : : : : : : : : : : : : : : : : : : : : : : : : : 585

18.4 BIBLIOGRAPHIC REMARKS : : : : : : : : : : : : : : : : : : : : : : : : : 588

A Electronic Access 589

Bibliography 591

Index 606

List of Figures

0.1 Tip of an iceberg : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : xxvi

1.1 Implementation of adaptive programming : : : : : : : : : : : : : : : : : : : 4

1.2 Customizer reuse : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 5

1.3 Adaptive program reuse : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 6

1.4 Duplication of class structure in ob ject-oriented programming : : : : : : : : 7

1.5 An innite family of programs denoted by an adaptive program : : : : : : : 8

1.6 Informal description of computeSalary adaptive program : : : : : : : : : : : 9

1.7 Propagation pattern for the computeSalary adaptive program : : : : : : : : : 11

1.8 Class dictionary graph representing conglomerates of companies : : : : : : : 12

1.9 Propagation graph for a customization of the computeSalary adaptive program 14

1.10 Another representation for conglomerates of companies : : : : : : : : : : : : 15

1.11 Propagation graph with code for second customization : : : : : : : : : : : : 15

2.1 Graphical class denition : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 20

2.2 Textual class denition : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 20

2.3 Class settlement and subclasses : : : : : : : : : : : : : : : : : : : : : : : : : 21

2.4 Graphical alternation class denition : : : : : : : : : : : : : : : : : : : : : : 22

2.5 Textual alternation class denition : : : : : : : : : : : : : : : : : : : : : : : 22

2.6 Class dictionary graph : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 27

2.7 Symbol use : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 36

3.1 Conglomerate class dictionary: A view of the C++ program : : : : : : : : : 43

3.2 Traversal code for salary addition : : : : : : : : : : : : : : : : : : : : : : : : 45

3.3 Propagation graph : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 57

3.4 English description of conglomerate : : : : : : : : : : : : : : : : : : : : : : : 59

3.5 Alternative class dictionary : : : : : : : : : : : : : : : : : : : : : : : : : : : : 61

3.6 Alternative class dictionary, textual form : : : : : : : : : : : : : : : : : : : : 62

3.7 Propagation graph for alternative class dictionary : : : : : : : : : : : : : : : 63

3.8 Propagation graph for increasing salary of ocers : : : : : : : : : : : : : : : 65

3.9 Increase salary of top-level ocers : : : : : : : : : : : : : : : : : : : : : : : : 66

4.1 Generic data model : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 79

4.2 Adaptive Software : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 82

4.3 Programming with hooks : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 83

xv

xvi LIST OF FIGURES

4.4 Adaptability of ob ject-oriented program : : : : : : : : : : : : : : : : : : : : 84

4.5 Adaptability of ob ject-oriented program : : : : : : : : : : : : : : : : : : : : 85

4.6 Propagation pattern print itinerary : : : : : : : : : : : : : : : : : : : : : : : 89

4.7 Program customizer Trip 1 : : : : : : : : : : : : : : : : : : : : : : : : : : : : 90

4.8 Program customizer Trip 2 : : : : : : : : : : : : : : : : : : : : : : : : : : : : 91

4.9 Propagation graph Trip 1 : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 91

4.10 Propagation graph Trip 2 : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 92

4.11 Adaptive versus ob ject-oriented : : : : : : : : : : : : : : : : : : : : : : : : : 93

4.12 A textual form of trip class dictionary : : : : : : : : : : : : : : : : : : : : : 94

4.13 Corresponding trip description : : : : : : : : : : : : : : : : : : : : : : : : : : 94

4.14 Propagation pattern with ob ject transportation : : : : : : : : : : : : : : : : 95

4.15 Class dictionary graph, propagation graph, and C++ program : : : : : : : : 96

4.16 Comparison of programming paradigms : : : : : : : : : : : : : : : : : : : : : 97

4.17 Delayed-binding viewpoint : : : : : : : : : : : : : : : : : : : : : : : : : : : : 98

4.18 Demeter : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 102

5.1 Simple container: graphical representation : : : : : : : : : : : : : : : : : : : 113

5.2 Simple container: textual representation : : : : : : : : : : : : : : : : : : : : 113

5.3 One intermediate class : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 114

5.4 Propagation directive : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 114

5.5 Propagation pattern : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 116

5.6 Apple basket ob ject : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 117

5.7 Apple basket class dictionary : : : : : : : : : : : : : : : : : : : : : : : : : : : 118

5.8 Apple basket : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 118

5.9 Class dictionary graph for apple/orange basket : : : : : : : : : : : : : : : : : 121

5.10 Textual form of class dictionary for apple/orange basket : : : : : : : : : : : 121

5.11 Additional C++ code : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 122

5.12 Optimized fruit basket class dictionary : : : : : : : : : : : : : : : : : : : : : 122

5.13 Optimized class dictionary in textual form : : : : : : : : : : : : : : : : : : : 123

5.14 Generated code : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 124

5.15 Class denitions : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 125

5.16 Baskets containing several things : : : : : : : : : : : : : : : : : : : : : : : : 125

5.17 Thing basket : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 126

5.18 Updated propagation pattern : : : : : : : : : : : : : : : : : : : : : : : : : : 127

5.19 Generated code for modied program : : : : : : : : : : : : : : : : : : : : : : 128

5.20 Nested baskets : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 129

5.21 Nested baskets, textual form : : : : : : : : : : : : : : : : : : : : : : : : : : : 130

6.1 Graphical representation of construction class Meal : : : : : : : : : : : : : : 138

6.2 Textual representation of construction class Meal : : : : : : : : : : : : : : : 138

6.3 Graphical representation of construction class ShrimpCocktail : : : : : : : : : 139

6.4 Textual representation of construction class ShrimpCocktail : : : : : : : : : : 139

6.5 Graphical representation of an alternation class without common parts : : : 140

6.6 Textual representation of an alternation class without common parts : : : : 140

6.7 Graphical representation of alternation class with common parts : : : : : : : 141

LIST OF FIGURES xvii

6.8 Textual representation of alternation class with common parts : : : : : : : : 141

6.9 Graphical representation of repetition class, zero or more : : : : : : : : : : : 141

6.10 Textual representation of repetition class, zero or more : : : : : : : : : : : : 141

6.11 Graphical representation of repetition class, one or more : : : : : : : : : : : 142

6.12 Textual representation of repetition class, one or more : : : : : : : : : : : : 142

6.13 Class dictionary graph for lists : : : : : : : : : : : : : : : : : : : : : : : : : : 145

6.14 Connections : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 148

6.15 Denition of associated : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 149

6.16 Class dictionary graph for expressions : : : : : : : : : : : : : : : : : : : : : : 153

6.17 Part-centered versus specialization-centered designs : : : : : : : : : : : : : : 161

6.18 Edge choice : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 162

7.1 Class dictionary graph without inheritance edges, textual : : : : : : : : : : : 171

7.2 Class dictionary graph without inheritance edges, graphical : : : : : : : : : 172

7.3 Class dictionary graph with inheritance edges, textual : : : : : : : : : : : : : 173

7.4 Class dictionary graph with inheritance edges, graphical : : : : : : : : : : : 174

7.5 Semi-class dictionary graph that is not a class dictionary graph : : : : : : : 175

7.6 Syntax summary for propagation directives : : : : : : : : : : : : : : : : : : : 180

7.7 Syntax summary for join and merge : : : : : : : : : : : : : : : : : : : : : : : 180

7.8 Customizer 1: Class dictionary graph Company1 : : : : : : : : : : : : : : : : 186

7.9 Propagation graph calculus : : : : : : : : : : : : : : : : : : : : : : : : : : : : 191

8.1 Programming by hooks : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 203

8.2 Violations of the Law of Demeter : : : : : : : : : : : : : : : : : : : : : : : : 204

8.3 Class dictionary graph to discuss Law of Demeter : : : : : : : : : : : : : : : 205

8.4 Before the Law of Demeter : : : : : : : : : : : : : : : : : : : : : : : : : : : : 205

8.5 After the Law of Demeter : : : : : : : : : : : : : : : : : : : : : : : : : : : : 206

8.6 Class dictionary graph using all features : : : : : : : : : : : : : : : : : : : : 209

8.7 Graph example : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 212

8.8 Graph class dictionary graph : : : : : : : : : : : : : : : : : : : : : : : : : : : 213

8.9 Depth-rst traversal : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 214

8.10 Propagation graph dft (extension at Adjacency) : : : : : : : : : : : : : : : : 214

8.11 Propagation graph uncond dft : : : : : : : : : : : : : : : : : : : : : : : : : : 215

8.12 Propagation graph nd : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 215

8.13 Propagation graph for extended graph data model : : : : : : : : : : : : : : : 218

8.14 Extended graph data model : : : : : : : : : : : : : : : : : : : : : : : : : : : 218

8.15 Chess board class dictionary graph : : : : : : : : : : : : : : : : : : : : : : : 219

8.16 Count pawns : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 219

8.17 Annotated propagation graph : : : : : : : : : : : : : : : : : : : : : : : : : : 220

8.18 Car : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 221

8.19 Painting a car : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 222

8.20 Painting a car, except doors : : : : : : : : : : : : : : : : : : : : : : : : : : : 222

8.21 Painting car doors only : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 222

8.22 Simple counting of X-ob jects : : : : : : : : : : : : : : : : : : : : : : : : : : : 223

8.23 Meal example : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 224

xviii LIST OF FIGURES

8.24 Expressions : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 226

8.25 Compiler : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 226

8.26 Equivalent wrappers : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 231

8.27 Code for test1 in edge wrapper example : : : : : : : : : : : : : : : : : : : : 232

8.28 Code for test2 in edge wrapper example : : : : : : : : : : : : : : : : : : : : 233

8.29 Simplifying the cycle checking problem : : : : : : : : : : : : : : : : : : : : : 235

8.30 Evolution history : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 236

8.31 Classication hierarchy : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 241

8.32 Simulating method inheritance : : : : : : : : : : : : : : : : : : : : : : : : : : 242

8.33 Classication with construction edges : : : : : : : : : : : : : : : : : : : : : : 243

9.1 Interpreter TRAVERSE to run a propagation pattern : : : : : : : : : : : : : 257

9.2 Refrigerator propagation pattern : : : : : : : : : : : : : : : : : : : : : : : : 262

9.3 Propagation directive information loss : : : : : : : : : : : : : : : : : : : : : 263

9.4 Customizer with information loss : : : : : : : : : : : : : : : : : : : : : : : : 263

9.5 Propagation graph : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 264

9.6 Delayed binding restriction violated : : : : : : : : : : : : : : : : : : : : : : : 266

9.7 Propagation graph : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 267

9.8 Bad customizer : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 267

9.9 Class dictionary graph Dish : : : : : : : : : : : : : : : : : : : : : : : : : : : 268

9.10 A propagation pattern : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 268

9.11 Propagation graph for eat/Dish : : : : : : : : : : : : : : : : : : : : : : : : : 269

9.12 A propagation pattern : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 270

9.13 Overlap of restrictions : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 270

9.14 Ordering of wrapper calls : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 277

9.15 Class dictionary graph : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 280

9.16 Class dictionary graph : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 281

9.17 Knowledge paths for ob ject path : : : : : : : : : : : : : : : : : : : : : : : : 284

9.18 Patchwork class dictionary, textual : : : : : : : : : : : : : : : : : : : : : : : 286

9.19 Patchwork class dictionary, graphical : : : : : : : : : : : : : : : : : : : : : : 287

9.20 Propagation graph : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 288

9.21 Traversal code : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 289

9.22 Coping with unintended inheritance : : : : : : : : : : : : : : : : : : : : : : 290

9.23 Car dealer semi-class dictionary graph with traversal code : : : : : : : : : : 291

9.24 Propagation graph for car dealer semi-class dictionary graph : : : : : : : : : 292

9.25 Wrapper pushing : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 292

10.1 Redundant propagation patterns : : : : : : : : : : : : : : : : : : : : : : : : : 310

10.2 Nonredundant propagation pattern : : : : : : : : : : : : : : : : : : : : : : : 310

10.3 Town without a dog catcher : : : : : : : : : : : : : : : : : : : : : : : : : : : 316

10.4 Town with a dog catcher : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 317

10.5 Town of SelfEmployed : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 317

10.6 Transportation restrictions: Disallowed edges : : : : : : : : : : : : : : : : : : 319

10.7 Propagation directive : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 321

10.8 Propagation pattern triples : : : : : : : : : : : : : : : : : : : : : : : : : : : : 322

LIST OF FIGURES xix

10.9 Customizer 1: Class dictionary graph Company1 : : : : : : : : : : : : : : : : 323

10.10 Bringing the actors on stage : : : : : : : : : : : : : : : : : : : : : : : : : : : 323

10.11 After customization of triples with class dictionary graph Company1 : : : : : 325

10.12 Customizer 2: Class dictionary graph Company2 with repetition vertices : : 325

10.13 Work ow management : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 331

10.14 Transporting resources : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 332

10.15 Code for resource transportation : : : : : : : : : : : : : : : : : : : : : : : : : 333

10.16 Code generation with transportation : : : : : : : : : : : : : : : : : : : : : : 334

10.17 Summary: Case 1 : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 334

10.18 Base/Derived-wrappers : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 336

10.19 Summary: Case 2 : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 338

10.20 Summary: Case 3 : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 340

10.21 Summary: Case 4 : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 342

10.22 Transportation pattern terminology : : : : : : : : : : : : : : : : : : : : : : : 345

11.1 Meal language : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 360

11.2 Two grammars dening the same language : : : : : : : : : : : : : : : : : : : 363

11.3 Syntax graph construction : : : : : : : : : : : : : : : : : : : : : : : : : : : : 365

11.4 Syntax graph repetition : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 366

11.5 Syntax graph repetition (nonempty) : : : : : : : : : : : : : : : : : : : : : : : 366

11.6 Syntax graph alternation : : : : : : : : : : : : : : : : : : : : : : : : : : : : 366

11.7 Venn diagram for class dictionaries : : : : : : : : : : : : : : : : : : : : : : : 372

11.8 LL(1), left-recursive, noninductive : : : : : : : : : : : : : : : : : : : : : : : : 373

11.9 LL(1), nonleft-recursive, inductive : : : : : : : : : : : : : : : : : : : : : : : : 373

12.1 Illustration of class dictionary graph slices : : : : : : : : : : : : : : : : : : : 383

12.2 Car and motor : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 384

12.3 Three dimensions of class dictionary design : : : : : : : : : : : : : : : : : : : 385

12.4 a has smaller size than b : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 386

12.5 Class dictionary to be minimized : : : : : : : : : : : : : : : : : : : : : : : : 387

12.6 Optimized class dictionary : : : : : : : : : : : : : : : : : : : : : : : : : : : : 388

12.7 Class dictionary that satises tree property : : : : : : : : : : : : : : : : : : : 390

12.8 Single inheritance class dictionary : : : : : : : : : : : : : : : : : : : : : : : : 390

13.1 Castle building analogy : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 408

13.2 Experimental heating system: class dictionary graph Furnace : : : : : : : : 411

13.3 Example of ob ject-equivalence: ￾1  ￾2 : : : : : : : : : : : : : : : : : : : : : 412

13.4 Example of weak-extension: ￾1  ￾2 : : : : : : : : : : : : : : : : : : : : : : 413

13.5 Example of extension: ￾1  ￾2 : : : : : : : : : : : : : : : : : : : : : : : : : : 413

14.1 Class dictionary : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 432

14.2 C++ translation : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 434

14.3 Ob ject-equivalence : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 435

14.4 Class dictionary and ob ject graph : : : : : : : : : : : : : : : : : : : : : : : : 437

14.5 Ob ject construction : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 438

14.6 Class dictionary : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : :