Eiffel, one of three object-oriented programming languages after C++ and Smalltalk, is user-friendly, consistent, and relatively easy to learn. In this book, Eiffel is used to introduce the basic principles of computer science from an object-oriented perspective. KEY TOPICS: Introduces the idea of "modeling" first, and then "programming" as only one part of the overall process; details the object-oriented approach to problem solving; covers the construction of Eiffel classes; explains polymorphism as a design principle. MARKET: For software development professionals new to object technology and Eiffel.
1. Programming and Software.
1.1 Computer science. 1.2 Computer programs. 1.3 Programming languages. 1.4 Structured and object-oriented programming. 1.5 Common software tools. 1.6 Programming. 1.6.1 Programming languages. 1.7 Goals of this book. 1.8 Exercises.
2.1 Object, objects everywhere. 2.1.1 Ordinary objects. 2.1.2 Objects as abstractions. 2.2 The object model. 2.2.1 An object model example. 2.2.2 The noun-verb and noun-noun metaphors. 2.2.3 Internal state. 2.2.4 Object scenarios and messages. 2.2.5 Parameters. 2.3 Relationships among objects. 2.3.1 Inheritance. 126.96.36.199 Classification. 2.3.2 Aggregation. 2.3.3 Uses relationship. 2.4 Abstract data type. 2.5 Producers and consumers. 2.6 Object modeling. 2.6.1 Analysis. 188.8.131.52 Aggregation relationship. 184.108.40.206 Uses relationship. 220.127.116.11 Inheritance relationship. 2.6.2 Analysis of an elevator. 2.6.3 Design. 2.7 Summary. 2.8 Exercises. 2.9 References.
3.1 Programming. 3.2 The Eiffel Language. 3.3 Creating and destroying objects. 3.4 Basic types, default values, and assignment. 3.5 Ordinary or reference type objects. 3.6 Copying objects. 3.7 Cloning. 3.8 Basic operators with examples. 3.9 Branching. 3.10 Iteration (loop). 3.11 Routines. 3.12 Arrays. 3.13 Strings. 3.14 Basic input and output. 3.15 Mathematical routines and “number crunching.” 3.16 Files and secondary storage. 3.17 Summary. 3.18 Exercises.
4.1 Introduction. 4.2 Problems versus their instances. 4.3 A taste of algorithms-some simple examples. 4.3.1 Algorithms for finding smallest and largest array values. 4.3.2 Simple sorting algorithm. 4.4 The efficiency of algorithms. 4.5 Computing faster. 4.5.1 Illustrative example- subvector problem for arrays. 4.6 Some more sorting. 4.6.1 Bubble-sort. 4.6.2 Gap-sort-a magic number and a fast variant of bubble-sort. 4.6.3 Insertion-sort. 4.7 Hard problems. 4.7.1 Traveling salesperson problem. 4.7.2 Knapsack problem. 4.8 Concluding remarks. 4.9 Summary. 4.10 Exercises. 4.11 References.
5.1 Dice. 5.1.1 Random number generators. 5.1.2 Implementation of die class. 5.2 Constant attributes. 5.3 A horse race using unusual dice. 5.3.1 Analysis and design of horse race game. 5.3.2 A four-way race. 5.4 Summary. 5.5 Exercises. 5.6 References.
6.1 An overview of the components of an Eiffel class. 6.2 Creation. 6.2.1 Subclass creation. 6.2.2 More advanced subclass creation. 6.3 Inheritance. 6.3.1 Extension-subtypes. 6.3.2 Specialization-the redefine subclause. 6.3.3 Selective export-the export subclause. 6.3.4 Renaming inherited routines-the rename subclause. 6.3.5 The select subclause. 6.4 Abstract classes using Eiffel's deferred class facility. 6.5 Storage versus computation: attributes versus routines. 6.6 Protecting and documenting routines-assertions and programming by contract. 6.6.1 Account classes revisited with assertions. 6.6.2 Propagation of assertions through inheritance. 6.7 Summary. 6.8 Exercises.
7.1 Stack. 7.1.1 Static implementation of stack. 7.1.2 Dynamic implementation. 7.2 Unordered list with duplicates not allowed. 7.2.1 Interface to UNORDERED_LIST class. 7.2.2 Implementation of class UNORDERED_LIST. 7.2.3 Discussion of implementation. 18.104.22.168 The data model. 22.214.171.124 Internal routine find. 126.96.36.199 Public routine item_before. 188.8.131.52 Public routine insert_front. 184.108.40.206 Public routine insert_back. 220.127.116.11 Public routine insert_before. 18.104.22.168 Public routine remove. 22.214.171.124 Public routines remove_front and remove_back. 126.96.36.199 Public routines remove_after and remove_before. 188.8.131.52 Public routine reverse_sequence. 7.3 Unordered list with duplicates allowed. 7.4 The stack revisited. 7.5 The queue. 7.6 Summary. 7.7 Exercises. 7.8 References.
8.1 The mechanics of recursion. 8.2 Relationship between recursion and iteration. 8.3 Recursion used in design. 8.3.1 Binary search of sorted arrays. 8.3.2 Quicksort-an efficient recursive sorting algorithm. 8.3.3 Binary search tree. 8.4 One final and more advanced but important application of recursion-depth-first search of a graph and airline connection problem. 8.5 Some parting comments about recursion. 8.6 Summary. 8.7 Exercises.
9.1 Late-binding and polymorphism. 9.2 A case study that features polymorphism. 9.2.1 Specifications. 9.2.2 The analysis and design. 9.2.3 Implementation details. 9.2.4 Output. 9.3 Version 2-improved design and implementation. 9.3.1 Revised implementation. 9.4 Summary. 9.5 Exercises.
Interface to String Class.
Interface to Class PLAIN_TEXT_FILE.
There is a strong need for a CS 1 book that from the very beginning presents the basic principles of computer science from an object-oriented perspective and is supported by a friendly, consistent, and relatively easy to learn object-oriented programming language. An object-oriented perspective represents a further evolution in the trend to emphasize abstractions in computer problem solving and the use of abstract data types in particular in early computer science courses.
This book is aimed at the beginning computer science student enrolled in a rigorous computer science curriculum. It is also aimed at practicing software development professionals new to the object paradigm who wish a gentle introduction to many features of the Eiffel language and the object paradigm.
This book presents the basic ideas of object modeling from the very beginning. Before a student learns to "program," he or she should be introduced to modeling. It is important that the beginning student as well as practicing software development professionals view programming as only part of the intellectual process associated with software development and computer science. Booch class and object scenario diagrams are introduced early as a means of providing notational support and more importantly support for the notion of object modeling.
The object-oriented perspective is quite distinct from the older traditional approach of having students learn the rudiments of programming from the bottom up. That is, first learn about scalar types, variables, assignment operations, branch and loop program control structures, and much later the concept of functional abstraction. Although in recent years functions have been introduced earlier in some CS 1 books, it is often the case that they are first introduced in the middle of the book.
Using an object-oriented perspective, functions and the underlying data model that they are manipulating are introduced from the very beginning. The class is introduced early as a frame from which to introduce and implement simple algorithms and provide a model for objects.
Some computer science departments have been moving towards C or C++ to support CS 1. This author believes that this is a grave mistake. Although both of these languages are commercially important and widely used outside of the university, which probably accounts for their adoption as a CS 1 language, they are poor candidates to support CS 1. Both languages are complex, are relatively hard to read, provide relatively little safety to the beginning programmer, and are relatively inconsistent (particularly C++). They both require the student to take a fairly low-level systems view quite early. It therefore becomes quite challenging for the beginning student to master low-level details and at the same time develop a high-level vision and sensitivity concerning the safe construction of software systems. The Eiffel language is much better suited for this task.
Eiffel is quite readable, friendly, and consistent. The dangerous artifact of pointers is totally missing.
Memory management is handled automatically. Eiffel's assertion handling mechanism provides an opportunity to emphasize safe and defensive programming. Its clean and simple syntax and semantics for handling generic components, late-binding, and inheritance allow a student to focus on the fundamental concepts of software construction and algorithm design without having to become distracted with the myriad of complex language details required, for example, if one uses C++.
Chapter 1 provides a short historical perspective related to computation and computers.
Chapter 2 introduces the concept of objects and object modeling. Objects as abstractions of reality are presented. The noun-verb metaphor, the notion of state, object scenarios and messages, classification, inheritance, aggregation and the uses relationship are introduced. An introduction to object-oriented programming is provided through a simple example. Some of the Booch analysis and design notation and the concepts behind the notation are introduced.
Chapter 3 introduces the reader to the world of programming using Eiffel. The basic elements of an Eiffel software system are presented. These include creating and destroying objects, basic types, reference versus value semantics, object assignment, object copying, object cloning, branching, iteration, and the construction of routines. In addition the use of basic Eiffel libraries is introduced.
Chapter 4 focuses on the design of algorithms. A graduated set of problems of increasing complexity are used to illustrate the rudiments of algorithm design and develop sensitivity to algorithm complexity.
Chapter 5 presents the reader with some first examples of complete Eiffel software systems. A preview is provided concerning the use of inheritance, late-binding, and assertions. A pair of ordinary dice are simulated. Then a pair of unusual non-standard dice are constructed using inheritance. A race horse game to be played by a person against the computer is built that uses the non-standard dice. Finally, a counterfeit coin weighing game is created that allows a person to play with the assistance of the computer.
Chapter 6, "The Construction of Eiffel Classes," presents more detail related to the various sections of an Eiffel class and their use. Object creation, routine redefinition and renaming, and export scope are among the topics covered. The important facility of assertion handling is presented in this chapter.
Chapter 7 discusses the issue of building reusable container classes. Several classic container classes are presented including STACK, QUEUE, UNORDERED_LIST, ORDERED_LIST, DEQUE, and SET. The BIT data type is introduced and used as part of the implementation of SET.
Chapter 8 introduces recursion as a design technique. First the mechanics of recursion are presented. The relationship between recursion and iteration is discussed and illustrated. Several smaller examples that illustrate recursive designs are presented including binary search of an array and quicksort. The chapter ends with an intermediate sized example involving a depth-first search of a graph. The reader is introduced to the flavor of more advanced algorithm design, an important foundation subject in computer science.
Chapter 9 presents polymorphism and late-binding as a design principle. After illustrating the principle with a simple and somewhat sterile example, an initial and improved version involving the analysis, design, and implementation of a complete software system are presented. Booch class and object scenario diagrams are used to support the analysis and design.
I would first like to thank Paul Becker, publisher at Prentice Hall, for his support and encouragement from this project's inception to its completion.
I am in debt to several outstanding reviewers who have provided extremely useful and constructive criticism of the first-draft manuscript.
Jim McKim of the Hartford Graduate Center, friend, Eiffel mentor, and outstanding critic, has examined every line of code in this manuscript and has made many useful suggestions. As before, Jim, my simple words of thanks are really not enough to thank you for your efforts way above and beyond the call of duty. The entire Eiffel community owes you many thanks for the continuing contributions that you are making.
Brian Henderson Seller, from the University of Technology in Sydney, has provided many helpful comments, particularly regarding the sections of the book dealing with object modeling.
Meilir Page Jones, President of Wayland Systems, has provided tremendous help in his critical but extremely constructive review of the manuscript. His many annotations in the first-draft manuscript have provided significant help in improving the book.
I am particularly appreciative of the timely help provided by Jim, Brian, and Meilir because I know how busy they are. Thank you all for finding the time to fit this manuscript review into your busy schedules.
I thank Margaret Reek for looking at a near final version of the manuscript and providing useful and constructive comments.
I wish to thank Interactive Software Engineering in Santa Barbara for continuing to provide me with their latest Eiffel software. It is my hope that the Professional Version of Eiffel for MSDOS/Windows will make this elegant language much more accessible to students and professionals alike.
I wish to thank Bertrand Meyer, the original designer and implementor of Eiffel, for his encouragement and support.
I also wish to thank Rock Howard and Madison Cloutier and everyone at Tower Technology for their technical support, tremendous encouragement and latest Eiffel products. Their outstanding contributions to the Eiffel community are noteworthy.
With great love and appreciation, I thank my wife Hanne for her help, constructive criticism, and continual encouragement.