Spider | Previous | Next | Table of Contents | Index | Program List | Copyright

Ada 95 Problem Solving and Program Design

M. B. Feldman and E. B. Koffman

Preface

Familiar Themes
General Organization of the Book
Program Design Issues
Ada Issues
Summary
Program Library Availability
Acknowledgements

This book's first edition (1992) was one of the first CS1-oriented works to use Ada as the language of discourse and is currently a best-seller in its field. It was inspired by, and borrowed much material from, the successful books by Elliot Koffman using Modula-2 and Pascal, the latter now in its fifth edition.

This second edition uses Ada 95 as its language of discourse. The Ada 95 language standard was adopted early in 1995 by the International Standards Organization and the American National Standards Institute; the language governed by the standard is very similar to the 1983 original but contains a number of very interesting extensions. For our purposes, these extensions are mainly in the newly added standard libraries and the language features giving fuller support to object-oriented programming.

As with the first edition, no previous programming experience is assumed or required here; this book can genuinely be used by students who are real novices. Indeed, the first edition has been used with success in a large number of CS1-level courses. While the book is generally oriented to the first-term student of programming, there is more material here than is usually covered in a first course. Chapters 10 through 16 focus on abstract data types, generics, recursion, dynamic data structures, inheritance-oriented programming, and concurrency. They can be used selectively in a fairly advanced first course or as part of a second-level course.

In addition to making the obvious changes to conform to the Ada 95 standard, we have added new material on stacks and queues, object-oriented programming, and concurrent programming; reorganized many examples, and removed some redundant ones. Finally, we have included a continuing project, "spider graphics," as a recurring theme throughout the book. The spider is introduced first in Chapter 3 and reappears as appropriate in a number of later chapters.

Familiar Themes

Readers acquainted with the Koffman works will find some familiar themes in this book. These are not at all related to the language of discourse of the book, but are rather general teaching devices that have met with success:

General Organization of the Book

The order of presentation is designed to do justice both to modern programming concepts and to the power of Ada. Each chapter presents a balanced mixture of a number of important language and computing issues. These are organized in a number of rubrics; most chapter section headings give the main rubric of the section as well as the specific topic, to orient teacher and student alike to the flow of material in a given rubric from chapter to chapter. The rubrics are as follows:

Program Design Issues

We present top-down design or refinement of a program right from the start, but make only rare use of top-down implementation through procedure stubs and the like. It is crucial to foster habits of design for reusability very early, and this argues for early emphasis of packages and the reusable functions and procedures they provide.

Functions are presented very early: They are used in Chapter 3 and written in Chapter 4. Procedure calls are introduced early in Chapter 2 because input/output in Ada requires them, but procedures are not written until Chapter 6. We believe functions are more intuitive than procedures, and, in Ada, cannot have IN OUT ("variable") parameters. Since functions in Ada are not restricted in their result type--arrays and records as well as scalars can be returned--this early exposure to functions will pay off later in encouraging students to use functional notation where possible. Introducing functions early allows us to introduce the writing of packages early (again in Chapter 4).

Enumeration types are introduced very early (Chapter 3). Enumerations are a useful structure for representing a set of values without regard to their internal representation. Students of other languages have a hard time seeing the utility of enumerations because they are so hard to read and display. In Ada, the input/output library provides a generic package for reading and displaying enumeration values. Furthermore, enumerations serve as a useful vehicle for motivating generic instantiation (for Enumeration_IO) and attributes (Pos, Val, Succ, Pred) very early in the game.

Records and arrays are presented together in Chapter 8, with records first. Other books have introduced arrays of scalars early, with arrays of records as an "advanced" topic. We prefer to allow arrays of records to be as natural as arrays of integers.

Design of abstract data types (ADTs) is introduced systematically beginning in Chapter 10. Ada.Calendar is seen as an ADT, and the discussion continues with ADTs for calendar dates, monetary quantities, employee records, and multiple spiders. Unconstrained array types are treated along with generics in Chapter 11; multi-dimensional arrays and variant records are introduced in Chapter 12. Chapter 13 presents an introduction to recursion. Dynamic data structures, in the form of one-way linked lists and binary trees, as well as subunits and LIMITED PRIVATE types, are introduced in Chapter 14, with applications to stacks and queues. Tagged records are introduced in Chapter 15; these are are seen to be supportive of the type extension (inheritance) now seen as essential to full object-oriented programming. Finally, Chapter 16 introduces the important concept of concurrent programming, introducing Ada's task types and protected types as language-provided constructs for concurrency.

Concepts of object-oriented programming (OOP) are introduced throughout the book as appropriate. While it is true that type extension and dynamic polymorphism are now seen as necessary to "full" OOP, it is essential for the student to understand that these are not sufficient. Ada's strong support for packages, generics, exceptions, private types, and subprogram overloading--like their equivalents in other languages--play important roles as well. The idea of an object as having state (value) and behavior (appropriate operations) is introduced beginning in Chapter 2, and "object thinking" is pervasive in the book. Type extension per se is an advanced topic that cannot be understood without a good grounding in the other topics, and so it is deferred until Chapter 15.

Assertions are introduced in Chapter 6 as structured comments and used consistently thereafter to document loop invariants and pre- and post-conditions for subprograms. We encourage the development of programs from their documentation; in case studies, the steps of the algorithm and the various assertions are written before the program is developed, and become comments as the program is refined.

We encourage appropriate use of comments but do not get carried away with them; the programs and the book would be far too long if we used industrial-strength comment conventions. Furthermore, students often respond with overkill to teachers' demands for comments, writing foolishness like

    Count := Count + 1;       -- add 1 to Count 
 

Ada Issues

It is important in introducing Ada to beginners (and we assume no previous programming experience, in any language, in this book) to introduce them, step by step, to the power of this rich language without overwhelming them. Here is a list of a number of Ada capabilities and how we have handled them:

Summary

This book's first edition incorporated a great deal of new material intended to introduce the beginning programmer to the power of Ada, while building on the successful pedagogy of the earlier Koffman works. We believed at the time, and still believe, that the completely redesigned presentation order and the kind of new material we have introduced do justice to first courses in computing using Ada. The first edition's success among teachers of Ada--in a number of cases, even serving as critical "ammunition" in moving Pascal-based courses to Ada--confirms the soundness of the approach

The present edition builds on the success of the first, reorganizing original material and adding much new Ada 95 material. Our intention is that this book serve as an important aid to teachers ready to introduce students to Ada 95.

Program Library Availability

It is intended that teachers make the full set of about 200 programs and packages available to their students, so that they need not waste time keying them in. Programs are available on the Addison-Wesley electronic servers, on various Ada-related servers and CD-ROMs, and on the ftp server at The George Washington University. The archive files at GW are

ftp://ftp.gwu.edu/pub/ada/courses/cs1code.tar.Z

for UNIX users, and

ftp://ftp.gwu.edu/pub/ada/courses/cs1code.zip

for DOS users. The program files are named according to GNAT conventions for the respective operating systems.

Acknowledgements

Many of the programs in this book are direct adaptations of their counterparts in the first edition, which have been thoroughly tested using a number of Ada 83 compilers. The Ada 95 versions of these, and all the new programs, have been tested using the GNU-NYU Ada 95 Translator (GNAT), running on an IBM-compatible computer under MS-DOS, an Apple Macintosh under MachTen, and a Sun-SPARC computer under Solaris, and using Intermetrics AdaMagic under Solaris. The authors acknowledge the School of Engineering and Applied Science Computing Facility at The George Washington University for having provided the Solaris computing resources.

The authors are indebted to the following educators who served as formal reviewers: Kevin Bowyer, Fred Ives, Trudy Levine, Jaime Nino, S. Ron Oliver, Larry F. Sells, and Robert A. Willis Jr. Robert Dewar and Ed Schonberg also offered helpful suggestions, and John Dalbey provided the original Spider package.

The editorial and production staff, including Lynne Doran Cote, Patsy DuMoulin, Diane Freed, Katherine Harutunian, Amanda Sylvester, Bob Woodbury, and Nancy Young, deserve hearty thanks for their expert and always good-natured assistance. Also to be thanked are Don Reifer and Charles Engle of the Ada Joint Program Office and Arra Avakian, Kathleen Mahoney, Mike Ryer, Dennis Struble, and Tucker Taft of Intermetrics, for funding and overseeing much of the revision project.

Finally, Ruth, Ben, and Keith Feldman have done it again, cheering from the sidelines, always there with logistical help, patience and loving care.

Bethesda, Maryland

Michael B. Feldman

Philadelphia, Pennsylvania

Elliot B. Koffman


Spider | Previous | Next | Table of Contents | Index | Program List | Copyright

Copyright ©1996 by Addison-Wesley Publishing Company, Inc.