Studies in Ada Style Peter Hibbard Andy Hisgen Jonathan Rosenberg Mary Shaw Mark Sherman Studies in Ada Style Springer-Verlag New York Heidelberg Berlin Peter Hibbard Andy Hisgen Jonathan Rosenberg Mary Shaw Mark Sherman Department of Computer Science Carnegie-Mellon University Schenley Park Pittsburgh, Pa. 15213 Library of Congress Cataloging in Publication Data Main entry under title: Studies in Ada style. Includes bibliographical references. 1. Ada (Computer program language) 1. Hibbard, Peter. QA76.73.A35S88 001.64'24 81-9323 AACR2 This research was sponsored by the National Science Foundation under Grant MCS77-03883 and by the Defense Advanced Research Projects Agency (DOD), ARPA Order No. 3597, monitored by the Air Force Avionics Laboratory Under Contract F33615-78-C-1551. The views and conclusions contained in this document are those of the authors and should not be interpreted as representing the official policies, either expressed or implied, of the National Science Foundation, the Defense Advanced Research Projects Agency, or the US Government. © 1981 by Springer-Verlag New York Inc. All rights reserved. No part of this book may be translated or reproduced in any form without written permission from Springer-Verlag, 175 Fifth Avenue, New York, New York 10010, U.S.A. The use of general descriptive names, trades names, trademarks, etc. in this publication, even if the former are not especially identified, is not to be taken as a sign that such names, as understood by the Trade Marks and Merchandise Marks Act, may accordingly be used freely by anyone. 9 8 7 654 3 2 ISBN-13 978-0-387-90628-7 e-ISBN-13 978-1-4684-0139-4 DOL 10.1007/978-1-4684-0139-4 Table of Contents Introduction 1 Pa rt I The Impact of Abstraction Concerns on Modern Programming Languages 1. The Impact of Abstraction Concerns on Modern Programming Languages 5 1.1 Issues of Modern Software 5 1.2 Historical Review of Abstraction Techniques 5 1.2.1 Early Abstraction Techniques 7 1.2.2 Extensible Languages 7 1.2.3 Structured Programming 8 1.2.4 Program Verification 9 1.2.5 Abstract Data Types 10 1.2.6 Interactions Between Abstraction and Specification Techniques 11 1.3 Abstraction Facilities in Modern Programming Languages 12 1.3.1 The New Ideas 13 1.3.2 Language Support for Abstract Data Types 14 1.3.3 Generic Definitions 16 1.4 Practical Realizations 17 1.4.1 A Small Example Program 17 1.4.2 Pascal 19 1.4.3 Ada 22 1.5 Status and Potential 26 1.5.1 How New Ideas Affect Programming 26 1.5.2 Limitations of Current Abstraction Techniques 27 1.5.3 Further Reading 28 Pa rt II Programming in Ada: Examples 1. Introduction to Example Programs 31 2. An Implementation of Queues 33 2.1 Description 33 2.2 Implementation 34 2.3 Program Text 34 2.4 Discussion 37 2.4.1 Use of Limited Private Types 37 2.4.2 Initialization and Finalization 39 2.4.3 Passing Tasks as In Out Parameters 40 2.4.4 Passing Discriminants to Tasks 40 2.4.5 The Elements Array 41 2.4.6 Remove as a Procedure 41 ii 3. A Simple Grnph Package Providing an Iterator 43 3.1 Description 43 3.2 Specifications 43 3.3 Program Text 44 3.4 Discussion 50 3.4.1 The Algorithm 50 3.4.2 Information Hiding 53 3.4.3 In/In Out Parameters 54 3.4.4 Using the Iterator 54 3.4.5 Iterators Versus Generic Procedures 55 3.4.6 Separate Compilation 56 4. A Console Driver for a PDP-11 59 4.1 Description 59 4.2 Implementation 60 4.3 Program Text 60 4.4 Discussion 63 4.4.1 Use of a Package to Surround the Task 63 4.4.2 Distinction Between Task Types and Tasks 63 4.4.3 Resetting and Terminating the Terminal Driver 64 4.4.4 Interfacing to Devices 65 5. Table Creation and Table Searching 67 5.1 Description 67 5.2 Implementation 68 5.3 Program Text 69 5.4 Discussion 75 5.4.1 Use of The Package 75 5.4.2 Use of the Search Function 75 5.4.3 Use of Packages 76 5.4.4 The Type of the Entries in the Table 77 5.4.5 Use of a Private Type for the Pointers to the Table 79 5.4.6 Nesting a Generic Package Within a Generic Package 79 5.4.7 String Comparisons 79 5.4.8 Use of Integers in Find 80 6. Solution of Laplace's Equation with Several Ada Tasks 81 6.1 Description 81 6.2 Implementation 82 6.3 Program Text 85 6.3.1 A Protected Counter Task Type 85 6.3.2 Parallel Relaxation Procedure 87 6.4 Discussion 94 6.4.1 Use of Shared Variables 94 6.4.2 Updates of Shared Variables From Registers 94 6.4.3 Generics and Generic Instantiation 94 6.4.4 Scheduling of Ada Tasks Onto Processors 95 References 97 List of Figu res Figu re 1-1: Declarations for Fortran Version of Telephone List Program 18 Figure 1-2: Code for Fortran Version of Telephone List Program 19 Figu re 1·3: Declarations for Pascal Version of Telephone List Program 20 Figure 1-4: Code for Pascal Version of Telephone List Program 21 Figu re 1-5: Ada Package Definition for Employee Records 23 Figu re 1-6: Declarations for Ada Version of Telephone List Program 24 Figu re 1-7: Code for Ada Version of Telephone List Program 25 Figu re 2-1: Implementation of a Queue 38 Figu re 3-1: Representation of a Graph 51 Figu re 3-2: State of a Graph Traversal 52 Figu re 3-3: Compilation Order for Graph Facility 57 Figu re 5-1: Initial Probe into Symbol Table 76 Figure 5-2: Locating Lower Limit of Matches 77 Figu re 5-3: Locating Upper Limit of tv1atches 77 Figu re 6-1: Distribution of Tasks 83 Introduction The major problems of modern software involve finding effective techniques and tools for organizing and maintaining large, complex programs. The key concept in modern programming for controlling complexity is abstraction; that is, selective emphasis on detail. This monograph discusses how the Ada programming language provides ways to support and exploit such abstraction techniques. The monograph is organized into two parts. The first part traces the important ideas of modern programming languages to their roots in the languages of the past decade and shows how modern languages, such as Ada, respond to contemporary problems in software development. The second part examines five problems to be programmed using Ada. For each problem, a complete Ada program is given, followed by a discussion of how the Ada language affected various design decisions. These problems were selected to be as practical as possible rather than to illustrate any particular set of language features. Much of this material has appeared previously in print. An earlier version of the first section, by Mary Shaw, was published as "The Impact of Abstraction Concerns on Modern Programming Languages" in the Proceedings of the IEEE special issue on Software Engineering, September 1980, Vol. 68, No.9, pages 1119·1130. It is reprinted with the IEEE's permission. The article has been updated to reflect the revised Ada syntax and semantics. An earlier version of the second part, by Peter Hibbard, Andy Hisgen, Jonathan Rosenberg and Mark Sherman, was issued as a Carnegie· Mellon Computer Science Department Technical Report CMU·CS·80-149, "Programming in Ada: Examples" (now out of print). Some of the programs have been modified in their use of separate compilation. The commentary on the programs has been expanded and illustrations describing their behavior have been added. The Impact of Abstraction Concerns on Modern Programming Languages Mary Shaw (£)1980 IEEE. Reprinted, with permission, from Proceedings of the IEEE, vol. 68, no. 9, pp. 1119-1130, September 1980. The Impact of Abstraction Concerns on Modern Programming Languages 5 1. The Irnpact of Abstraction Concerns on Modern Programming Languages 1.1 Issues of Mode rn Softwa re The major issues of modern software development stem from the costs of software development, use, and maintenance - which are too high - and the quality of the resulting systems - which is too low. These problems are particularly severe for the large complex programs with long useful lifetimes that characterize modern software. Such programs typically involve many programmers, not only during their development but also for maintenance and enhancement after they are initially released. As a result, the cost and quality of software are influenced by both management and software engineering considerations [7,28]. This paper examines one of the themes that run through the history of attempts to solve the problems of high cost and low quality:. the effect of abstraction techniques and their associated specification and verification issues on the evolution of modern programming languages and methods. This theme places a strong emphasis on engineering concerns, including design, specification, correctness, and reliability. The paper begins with a review of the ideas about program development and analysis that heavily influenced the development of current techniques (Section 1.2). Many of these ideas are of current interest as well as of historical importance. This review provides a setting for a survey of the ideas from current research projects that are influencing modern language design and software method· ology (Section 1.3). Section 1.4 illustrates the changes in program organization that have been stimulated by this work by developing an example in two different languages intended for production use, Ada and Pascal. Although Sections 1.2 and 1.3 present a certain amount of technical detail, Section 1.4 illustrates the concepts with an example that should be accessible to all readers. An assessment of the current status and the potential of current abstraction techniques (Section 1.5) concludes the paper. 1.2 Historical Review of Abstraction Techniques Controlling software development and maintenance has always involved managing the intellectual complexity of programs and systems of programs. Not only must the systems be created, they must be tested, maintained, and extended. As a result, many different people must understand and modify them at various times during their lifetimes. This section identifies one set of ideas about managing program complexity and shows how those ideas have shaped programming languages and methodologies over the past ten to fift8en years. 6 Historical Review of Abstraction Techniques Section 1.2 A dominant theme in the evolution of methodologies and languages is the .development of tools for dealing with abstractions. An abstraction is a simplified description, or specification, of a system that emphasizes some of the system's details or properties while suppressing others. A good abstraction is one in which information that is significant to the reader (i.e., the user) is emphasized while details that are immaterial or diversionary, at least for the moment, are suppressed. What we call "abstraction" in programming systems corresponds closely to what is called "analytic modelling" in many other fields. It shares many of the same problems: deciding which characteristics of the system are important, what variability (i.e., parameters) should be included, which descriptive formalism to use, how the model can be validated, and so on. As in many other fields, we often define hierarchies of models in which lower-level models provide more detailed explanations for the phenomena that appear in higher· level models. Our models also share the property that the description is sufficiently different from the underlying system to require explicit validation. We refer to the abstract description of a model as its specification and to the next lower-level model in the hierarchy as its implementation. The validation that the specification is consistent with the implementation is called verification. The abstractions we use for software tend to emphasize functional properties of the software, emphasizing what results are to be obtained and suppressing details about how this is to be achieved. Many important techniques for program and language organization have been based on the principle of abstraction. These techniques have evolved in step not only with our understanding of programming issues, but also with our ability to use the abstractions as formal specifications of the systems they describe. In the 1960's, for example;the important developments in methodology and languages were centered around functions and procedures, which summarize a program segment in terms of a name and a parameter list. At that time, we only knew how to perform syntactic validity checks, and specification techniques reflected this: "specification" meant little more than "procedure header" until late in the decade. By the late 1970's, developments were centered on the design of data structures, specification techniques drew on quite sophisticated techniques of mathematical logic, and programming language semantics were well enough understood to permit formal verification that these programs and specifications were consistent. Programming languages and methodologies often develop in response to new ideas about how to cope with complexity in programs and systems of programs. As languages evolve to meet these ideas, we reshape our perceptions of the problems and solutions in response to the new experiences. Our sharpened perceptions in turn generate new ideas which feed the evolutionary cycle. This paper explores the routes by which these cyclic advances in methodology and specification have led to current concepts and principles of programming languages.