THE UNIVERSITY OF MICHIGAN COMPUTING RESEARCH LABORATORY PARADIGMS FOR DESIGN AND IMPLEMENTATION IN ADA Vaclav Rajllch CRL-TR-43-84 October 1984 Room 1079, East Engineering Building Ann Arbor, Michigan 48109 USA Tel: (313) 763-8000 Any opinions, findings, and conclusions or recommendations expressed in this publication are those of the authors and do not necessarily renflect the views of the funding agency. Ada is a registered trademark of the United States Government, Ada Joint Program Office (AJPO)

Abt.s.t: r ac: t. In the paper, three characteristic paradigms of a design and implementation in Ada are described and compared: EBottom-up incremental programming, top-down semiincremental programming, and large-small traditional programming. Several examples i:L lustrate the selection of the correct paradigm for the given set of cir cumstances.

. Introducti on Programming languages Ada [1] and others I 21[ E8J E 15[1 [ 18 1 represent a new generation of languages. They are a culmination of long research in modularity, i.e. the tools and techniques of decomposition of large software systems into smaller pieces. They are also new and powerful software tools, providing extensive help to both the designer and programmer who Uses them. One of the most powerful modularity techniques is the principle of information hiding as outlined by Parnas and others E 1J].CQ The principle can be briefly summarized in the following way: We want to decompose the programs into modules (packages) which will have simpler and more understandable interfaces than the detailed code they are hiding inside. They will be reusable, will localize the impact of the changes in the program, allow cooperation of several programmers on a program, etc. Traditionally, the process of program creation is divided into two phases, the design and implementation, where the purpose o4: design is to find the "right" packages with the properties descri bed above, while purpose of the implementation is to actually produce the code for the packages. The programming language Ada contains elaborate features which support the implementation (i.e. code writing) of programs divided into packages. In this paper, Ada will be used both as a design and implementation language, and several paradigms will be discussed. In Section 2, we describe separate compilation in Ada. Section 3 describes a certain desirable architecture of: Ada programs. Section 4 describes paradigms and li fe-cycles in general, with the emphasis on non —traditional incremental and semi -incremental life-cycles. In Sections 5, 6, and 7, we describe three selected paradigms. The summary in Section 8 contains i several hypothetical examples of: a paradigm selection. 2. Setparate comeilation i.n Ada. The basic building block of Ada programs is a compilation unit; the whole program consists of one or more compilation units [ 1 1. We shal l avoid discussing the compl exi ti es of compilation units in general, and shall concentrate on packages instead; however the paradigms discussed in this paper can be applied to subprograms and generics, too. Each package is associated with two compilation units: packagje specifi:cationl and ~ackage bodY. A package specification is a 1 i s;t of all 1 decl arative items ( i.e. objects, types, subprograms, task:s, exceptions, etc.) which are implemented in

the package and can be used by other packages of the program. A package body contains all relevant definitions. Moreover, a package body can contain other entities, invisible from the outside. Hence the package specification is a "window" of a limited size, which allows only a limited number of the entities of the package to be seen, hiding all the remaining ones. Moreover it hides the implementation details of the visible objects. This principle is called "information hiding principle" i 1n the literature E[1)], and it allows decomposition of large systems into smaller packages, where each package and its interconnections are simpler than the whole program. Hence a programmer who deals with one package does not have to know the whole program, and his task is substantially simplified. A typical program consists of several packages. It must contain both specification and body of each package. Fackages can be interconnected by either with or separate clauses, which determine both the relationships and the order of the compilation. Suppose we have two packages X and Y interconnected by the following "with" clause: with X; package Y is..., Then the order of compilations is given by the following rules: (i) package specifications of both X and Y must be compiled before package bodies are compiled, (ii) specification of X must be compiled before specification of Y is compiled. Hence the possible orders of compilation of packages X and Y are: specification X, body X, specification Y, body Y specification X, specification Y, body X, body Y specification X, specification Y, body Y, body X. Besides the order of compi lation, the "with" clauses determine which package can use items of which package. In the ex ample above, package Y is allowed to use items listed in the specification of X. The "with" clauses organize the pack:ages of a program into a directed acyclic graph (dag). Another way how to organize pac-::ages is to use the "separate" clauses. Suppose we have the following program: pack:age Y is... end Y; package body Y is package D is... end D; package body D is separate; end Y;

separate (Y); package body D is... end D; There is only one order of compilation: specification Y, body Y (includes specification D), body D. Visibility rules are given by the nesting of D in Y. The "separate" c1. auses interconnect -the packages into a tree-structured hierarchy. One program can have the packages interrelated by both "with" and "separate" hierarchies. Hierzarchical architecture for Ada p!-ggrams. In the 1 iterature, two orthogonal hierarchical architectures f or computer programs were described. One deals with the organization of programs into "layers", where interfaces among layers are the so-called "virt ual machines" [53 and it will be called the senior ity hierarchy. The other hierarchy deals with the decomposition of larger objects into smaller parts, and will be called the parent-child hierarchy. A common misconception is to equate these two hierarchies. We shall follow the style of [151 and make a distinction between the two hierarchies. The seniority hierarchy provides an intuitive basis for two important paradigms: top-down and bottom-up. This hi erarchy requires an organization of the packages into directed acyclic graphs E[T32 and hence it is natural to define it by the "with" cl auses of Ada. The virtual machines are then the " cuts:" of the dag. Hence if we have the situation with X; pacl:age Y is...; then Y wi.ll be called senior (to X), and X will be cal]led juLnior (to Y). It should be noted that the "separate" clauses were suggested by some researchers to serve as a tool for the seniority hierarchy [161, particularly in the situation when top — down programming is used. However they are not suitable for this purpose; they f orce tree structure on the system, which constrains the architecture in a substantial way. Ex:ample in [14] illustrates the situation where the tree structure is inadequate. We will use "separate" clauses for a different purpose. The parent-child hierarchy is intuitively characterized by big packages divided into smaller ones. This hierarchy requires a tree-like structure. It is here where the "separate" clauses ca n be utilized. If we have a situation separate (B); package body A is..; then B will be called a parent (of A), and A will be called a child (of ).

The two hierarchies are orthogonal to each other and can be combined in one program. However in that case, a certain element of: s.ityle should be observed: The children of a common parent shlou(ld al;so be ordered by the relation of seniority, even if Ada d(:.)oes nor(::)t r equire such ordering. Then the children will also cr: I-r ate a hierarchical decomposition into layers and virtual machines, which will make it possible to design and program them both top-down and bottom-up. The two hierarchies provide a natural selection or f relationships among the packages. Moreover they provide four basic directions, in which paradigms for the design and implementation may progress: Bottom —up, which progresses in tihe direction -from the junior to the senior packages, top-down which progresses in the exactly opposite direction, i.e. from the senior to the junior packages, large-small paradigm which follows the direction of the "separate" hierarchy, where parent packages are written before the child packages, and the "small-large" paradigm, where child packages are written before the parent p ac ackages. It should be immedi atel 1 y noted that the smal 1-1 arge paradigm is incompatible with both modern programming practices and Ada. It was widely used in the past with less sophisticated programming languages, when separate modules were written by different programmers, and then later "integrated" into one program. It was typical to discover substantial discrepancies and misunderstandings among the programmers during the integration phase, which required substantial revisions in the code. Hence integration was the least predictable and potentially costly phase of the software life-cycle. Because of this cost and uncertainty, and because all other paradigms are superior to small —large paradigm in all respects, it should no longer be used, and is not discussed f urther in this paper. 4. Life-cyce 1 es. The paradigms of the previous section should be distinguished f rom the orthogonal notion of sof:tware "l i f ecycle". The li fe-cycle is a sequence of the stages through which a piece of software has to pass during its life. In this paper, we shal 1 talk about three different lif ecycles: Traditional, incremental, and semi -incremental.'The traditional software life-cycle is well documented in the literature [7], [9], C11], and consists of the following phases: Requirements specEi f ication, where the taski.: is described in a language understandable to both the implementors and the users (answering the question what is to be implemented). An

interesting part of the requirements specification i.s'the verification of the specifications via rapid prototyping [2'1O] As interesting and important the as specifications are, we shall not deal with them in this paper and shall rather concentrate on the re mai) n:i rg Fport i ns o4: the life —cycle. Desi gn, where the algorithms are defined and the system:is decomposed into packages (answering the question how is the system going to be implemented). Imnplementation, where the actual code is writtenq integrated, and tested. Evolution, where the system is being operated and modified according to changing environment or whenever errors are discovered. In the traditional life-cycle, the complete design of the program or the system must be finished, before the implementation starts. Typically, the design language will be completely different from the implementation language. The methods covering the traditional paradigm are well known [1 11 In correspondence to E213, the result of the design phase will be called a workproduct. However Ada allows a departure from this sequence, because it can be used both as a design and implementation language. The departures we will talk about here will be called i ncremenrtal and semi-incremental life-cycles. A characteristic feature of the incremental li-fe-cyc'le is that it uses one language for both design and implementation, and hence it merges the steps of design and implementation into one (for simplicity, we shall use word " i mplementation" to denote this merged step). During the implementation, the program typically is incomplete, i.e. it consists of two parts: the existing part which is the actual program so far stored in the computer, and the i!] tended p aE t, which is everything not yet written. Rt the beginning, the e>xisting part is empty and the whole program is intended. At the end, the intended part is empty and the whole program is existing.'The program implementation is a sequence of incremental steps, each adding something to the ex'isting part and deleting something from the intended part. Rn advantage of the incremental li f e-cycle is the possibility of verification of incomplete designs. Lack of this possibility is one of the major problems with the traditional life-cycle. Another advantage is the saving in the volume of documentation the designers/programmers must produce. n careful scrutiny of most design documents reveal that with the traditional paradigm, the design and implementation overlap to a substantial degree. The incremental life-cyc:le require s support by software ~tools. The programming language must contain constructs which

will allow the incremental steps, where the code written for one step will remain valid for all the remaining steps (unless the programmer changes his mind). It also requires a verification method f or incomplete programs. Tlhe semi inc:remental life —cycle is half-way between inI) c: r~emental and traditional life —cycles. It requires separate phases of: design and implementation, but: these phases can be substantially overlapped. This means that the design language can be easily translated into the programming language, and hence the design at any stage can be easily converted into code and tested. This code may require some modifications when additional steps of design are added, but the modifications are minor and mechanical. Also the semi-incremental life-cycle may require a special work-pEroducntt, which is a document prepared for the purpose of the design only, not a part of the code. Al so there must be methods of verification of incomplete designs translated into code. nda is a software tool which supports several combinations of paradigms and life-cycles. In the following sections, we shall eXplore three most characteristic combinations: bottom-up and incremental, top-down and semi-incremental, and large-small and ktraditional. There are other possibilities like traditional lifecycle with top-down design and bottom-up implementation; brief comment related to these possibilities is in Section 8. 5. Botto-up i ncremen t a l Eogrammi n gq The bottom-up paradigm is based on the intuitive idea of "language extentions", and it is a well-known paradigm. The basic idea is described in the following way: Suppose we want to solve a problem, which can be easily solved using a certain set of operations, objects, types, etc. These entities however are not available in Ada. Then we shall define a package which will provide them, and use this package as the first step towards the sol ut ion of the problem. Intu itively, we see the packages as steps in the extension of Ada, which provide increasingly complex entities needed for the solution. This process of ex.'tention may require several steps, where we extend Ada with entities of one package, and then use these entities in definition of another package which has even better entities, etc., until the problem i.s solved. In the Appendix., there is an example of a solution to the eight queens problem. In the bottom-up approach, package COLUMN is defined first. The package provides type COLUMN and all necessary procedures which deal with it. Then the package BOARD is defined, and finally the problem is solved by definition of The programming 1 anguage Ada provides al necessary

constructs and the order of compilation to support the incremental life-cycle in combination with the bottom-up paradigm. There is no need to change the previously defined pack.ages when a new package is added. The advantages of this programming combination are the *f: olI 1J owi r'l c: - There is no extra design document necessary, hence no e.xtra cost associated with it. In fact, the design is done simultaneously with the implementation, directly in Ada. - The paradigm is very forgiving. If a wrong decision is made at any turn, it does not invalidate the design. It may mean that the the design will be less optimal, containing more code than necessary, but it usually does not mean that we have to redo the whole design from scratch. However the programming combination also has disadvantages: -- A well-known disadvantage of the bottom-up approaches is that there is no guarantee that the final product will satisfy the specifications, or that it wi ll be well. balanced. Some authors considered this disadvantage to be so severe that they ruled out the bottom-up paradigm as generally unsuitable e17). - The paradigm allows only a limited number of people to work on a project. - The paradigm is rather difficult. It is a highly creative act to discover items (i.e. objects, types, etc.) which will be useful for the solution of a particular problem. 6. T[op-down semi-incremental pErgoggrammi ng. The particular methodology on which the top —down paradigm is demonstrated is the refinement methodology (RM) of [13 and [141. Other- top —down methodologies can be found in [E L4, [6, [171, [19, [ 21], etc., but none of them leads to a semii ncremental life —cycle.'The top-down paradigm starts with specification s, which describe the problem to be solved, and serve as a departure point for the design. An important workproduct of RM is the so —called backlog interface. It consists of the objects which have already been used in the existing part, but which were not defined. These objects will be called unfinished obiects. Typi cally, they are: (i) Procedures/functions which have been called but whose bodies have not been defined (ii) Types which already have been used but have not been def i ned ( i i i) Var i ables whose names have been introducl:ed but their

types have not been declared. The unfinished objects are interconnected into data —flow graphs by the following relations: (i ) Rel ations " re(ad," " write" and "readwrite" between variables and procedures/f unct ions (ii) Relations "in", "out", and "in out" between unfini shed types and procedures/fuctions. This relation describes the mode and type of formal parameters of procedures/functions. As in [14], we shall represent backlog interfaces by graphs, where the procedures/functions are denoted by rectangles, the variables are denoted by ovals, and the types are denoted by diamonds. Relations are denoted by arrows pointing in the direction of the information flow. Procedures, functions, and types also contain the names of all packages in which they are used. An example of backlog interface is in Fig. 1. The scope of variable or type V is -the set of all procedures,/functions related to V. The scope of a procedure FP is the procedure itself. The RM methodology is based on the following steps: (i) definition (ii) decomposition and completion ( i ii) abstracti on. Each of these steps removes certain objects from the backlog interface and may add new ones to it. Each of them also adds one tentative package to the e> xisting part of the program. The steps are described in the following way: (i) Definition. Definition is a step in which we define one or several unfinished objects in terms of the primitives of the programming language. If the object is a procedure, we will define its body. If it is a variable, we will give its type. If it is a type, we will define its representation. These objects are then removed from the backlog interface. An important property of definition is that the smallest unit of definition is a scope. Every definition step means that one or several scopes are defined at once. A procedure can be fully defined only if all related objects (variables, types) are defined in the same step. If procedure F is related to variables V1, V2,..., Vn, and to types 1-1, T, T3.., Tm and all these variables and types were defined in the same step, then procedure F can be full y defined. If one or more variables and/or types remain undefined, then procedure' can be defined only partially. It's body will have to contain calls of new unfinished procedures P1, F2...P F Pk which will be related to the variables/types which remained undefined. In this situation, the so-called first reason for parameters has to be appli ed. It is ex plained in the fol lowing way: Let F' be a procedure which is related to variables V1., V2,..., Vn where 1~~~~~~~~~:. = J =

variables V1. V2. Vm were definedq variables V(m+l),... Vn were left undefined (m::n). Then P will be partialy defined with new un f inished procedure FI being called in its body. The procedure P1 will have actual parameters VI, V2, Vm, i.e. the body of F will be procedure PF is begin P1(V 1 V2.., Vm); end'; This rule can be justified by the following reasoning: Each definition step produces a package. For reasons of style, we allow the communication between packages through procedure parameters only, disallowing direct accessibility of data. Frocedure FP1 may inherit all relationships of the original procedure F', i.e. it may be related to all variables V1., V2, V3,,..,Vn. However the definitions of these variables will be spread over at least two packages: The current package where V1., V2....,Vm are defined, and some future packages where both P1 and some of the variables V(m+1),..., Vin will be defined. Then there is the need for the parameters F'1(V1, V2,...Vm). (ii) Decomosition and comepletion. Decomposition and completi on is another step of the methodology. In it, we decompose an unfinished object A into several smaller unfinished objects A1, A2, t..., n. If object A is a variable, type, and procedure, then objects A1, 2,...An will also be variables, types, and procedures, respectively. Moreover if A was related to B, then a nonempty subset of A1, A2q 2 A3;.. iAn will be related to B by the same kind of relations. In the substep of completion, we inspect all. new unfinished objects and try to determine whether they can function correctly or whether- they need to be related to some additional objects. There are two situations which require introduction of new objects: First, two procedures may need to communicate with each other, and hence there is a need for a new variable which will f acilit ate this communication. Second, var i ab l es may need initializing procedures which will set the initial val ues. None of these new objects were introduced by decomposition, hence we must have the special substep of completion. An e.-xisting part of the program is complete when no new objects can be introduced by the process of completi on, i.e. al l communi cati ons among procedures have been served by appropriate variables, and all variables have been properly initialized. The step of decomposition and completion again produces a pac a: g e.

(iii) bsrac. tn r., Abstraction is a special case of definition in which a variable V is declared to be of type T, where T is an unfinished type. As in every definition, the whole scope of variable V has to be defined. If V is read by procedure FP, then the body of P will call a new Lrunfinished procedure Ft (V:in T). This action is called secondc reason for parameters. The purpose of an abstraction step is to replace similar unfinished variables by one type, and similar unfinished procedures by a single more abstract procedure. The reason is economic: the backlog interface will be simplified, because several variables and procedures will be replaced by a smaller number of newly introduced types and procedures, respectively. Again, the abstraction step produces a package. The packages produced by the steps of RM can be directly written in Ada, except for one thing: The "with" clauses cannot be utilized, because it is unclear at the time of introduction, in which pacl:age the individual items of the backlog interface will be located. Hence we use the "used in" clauses, which specify where the items are used instead. The "used in" clauses are the only difference between the actual Ada code and the design. For more details on RM, see 1141. To convert designs into code, note that the "used in" relat ionship is an inverse relationship to the combination of the "with" and "use" clause of ADA. Hence if we have two packages F and R which are related in the design in the following way: package P is... end P; used i n P; package R is... end R; then replacing "used in" by a combination of "with" and "use" will give us with R; use R; pacl-::age F is... end F'; packlage R is end R; Let us illustrate the programming on the example in the Appendix. In that example, the first compilation unit to be implemented is procedure MAIN. The procedure calls several procedures, which in turn communicate with each other through a data structure EBOARD. Hence after the first step, the backlog interface is defined by the graph of Fig...

TRY...RST used in MAIN w REGRESS Cused i i MAIg N PRINT_ RESULTS sed in MAIN Fiig. I In the nex.t step, we shall deal. with the scope ocf the object BOARD, and define package BOARD. The object BOARD will become a local object of the package, defined as an array(1..8) of COLUMN, where COLUMN is an unknown type. Both package specification and body will be de-fined si multaneously: u..tsed in MAIN; pack::age'BOARD is... end BOARD. The bacf:klog interface appears in Fig.. SAFE(A,B: in COLUMN; CD: in INTEGER) return BOOLEAN used in BOARD LAST(A: in COLUMN) return BOOLEAN used in BOAfRD PRF'I NT ROW(A: in COLUMN) used in BO(ARD Fig. 2. In the last step, we shall define the scope of: the type COLUMN. This is done in package COLUMN of the Appendi'. The pack:age (both the specification and the body) will have the form: used in BOARD; package COLUMN is... end COLUMN; After this step, the backlog interface is empty, and hence we are finished with the design. In order to convert the de<sign into code, we have to convert the "uIsed in" clauses into a combination of "with" and "use" clauses. The resultinng program appears in the Appendix. The conversion is straighforward and mechanical, and can be done after each package is added. Hence it

passes ou..r criteria for the semi-incremental life-cycle. The advantages of the top-down semi-incremental programming combination are: - Since the specifications are the departure point for the paradigm, there is a good probability that the specifications goal will be actually accomplished. - The volume of the necessary documentation is small compared to the traditional paradigm. - The paradigm offers a rather detailed guidance to the designer. When the paradigm is mastered, it becomes very natural and easy to use. However the programming combination also has disadvantages: - There is a very small possibility of parallel efforts on the project. - TThe paradigm is less forgiving than the bottom —tp paradigm. Wrong decisions, like wrong decomposition of an item, may make the design unacceptable or competely invalid. The only solution then i s to retrace the wrong deci si on and all consequent decisions, which may be a time-consuming task. 7. Lare-small traditional programming. As remarked earlier, Ada allows the large-small paradigm, where the specifications of the modules are defined first, and then the bodies are defined later. If it turns out that a body of a paci::age is too big, it may be divided into smaller packages by "separate" clauses, and hence this paradigm naturally utilizes the "separate" hierarchy. In the e,'ample in the Appendix, the paradigm requires the specification of the three packages first. Then the bodies can be written in an arbitrary order, or by several programmers in parallel. The compiler will check whether the packages use the items of the other packages correctly, which substantially improves the problems of the integration of the modules into the program. A methodology supporting this paradigm appers in [ 3]. The problem of this paradigm is its unforgiving nature. Whenever an error in the specification of the packages is made, it tends to affect many additional pack:ages, and a ripple effect propagates through the system. Hence the implementation requires a very careful and detailed design, and the design must be completed before the implementation can start. Another problem is the high volume of documentation, because:f.

the de!:ign is a completely separate document than the code. Also )becaus-. of the Unforgiving nature of the paradigm, it i s a di f: i fficul t paradi gm. The advantage is the high parallelis)m of: the implementation ef: f r-t, where once the design hnas been completed, many programmers ( an wor k on the program i.n paral I el, each implementing a different package. 8. Summar y... In the paper we dealt with the most characteri sti c combnination s of paradigms and life-cycles on 1 y. However- other combinations are possible: For ex:.ample, a program can be designed top-down and then implemented bottom-up, or it can be divided into several large packages first (by large-small paradigm) and t h e packages can be implemented with subpackages by bottom-up paradigm, etc. Each of the combinations displays a dif ferent combination of attributes. Hence a manager of a project shout ld caref ul I y evalutate the circumstances of the project, and carefully select the appropriate combination. As an illustration, let us consider' several examples o4: program implementation: - An e:. ploratory program is to be implemented by an individEal. researcher. Eecause of the exp.loratory nature of tnhe program, no requirements speci f i cati ons exiCt. Hence the appropriate combination is the incremental bottom —up combination, which of:fers the highest level of forgiveness (and hence if a wrong decision is made, it can be easily corrected), and lowest volu me of necessary documentation. The disadvantages of: the combination are well compensated for: there is one researcher and hence no need for parallel effort, and the high caliber of the researcher compensates for the higher diff i cl ty f: the paradigm..- An ex.'isting program is to be rewitten in Ada by a team of the programmers. The appropriate combination for this situation is the large-small traditional combination. The combination allows several programmers to proceed with implementation in parallel. All disadvantages are reduced by the fact -that t-he old program already ex.ists and is avai 1able to the programmers. This is particularly true about the lack of forgiveness, and the high volume of necessary documentation; the experience and the design from the old program can be reused. - Another program of a well —:known application area is to be produced by a small team of programmers. The appropri ate combination -for this situation is the top —down semi -i n c r emen tal paradigm. The combination offers the best certainty of compliance w:i.th the specificatio3ns. The impact of the less forgiving nature of the combination is reduced by the fact that the app1 i cati on area is well-known to the programmers. The impact of the l ow

level of parallelism is reduced by the fact that a small team is involved. Fef er e n c es. El] Ada Programming Language, Military standard MIL-STD-1815. [2] Archibald, J.L., Lavenworth, B.M., Power, L.R., Abstract Design and Program Translator: New Tools for Software Design, IBM Systems J. 22o 1983q 170-187. [3] Booch, G., Software Engineering with Ada, The Benjamin Cumming s Publ Co, Menlo Park, CA, 1983. [4] Crew, p., Ward, D., Mungel, G., Analysis of a Prototype Ada Integrated Methodology, Pro. COMPSAC:'83 Conf., IEEE Computer Soc., 598 —6(,4. [5] Dijkstra, E.W., The Structure of THE Multiprogramming System, Communications of ACM 11, 1968, 341-346. E6] Jackson, M., System Development, Prentice-Hall, Englewood Cliffs, NJ., 1983. [7] K::erola, P., Freeman, P., A Comparison of Lifecycle Models, Proc. 5th Intern. Conf. on Software Eng., IEEE/ACM, March 1981, 90-99. [8] Lauer, H.C., Satterthwaite, E. H., The Impact of Mesa on System Design, Proc. 4th. International Conference on Software Engineering, IEEE Catalog No. 79CH1479-5C, 1979, 174-182. [9] Lehman, M.M., Programs, Life —Cycles, and Laws of Program Evolution, IEEE Spectrum, Sept. 1980. ([10] Parnas, D.L., Designing Software for Ease of Extension and Contraction, IEEE Trans. on Software Engineering, March 1979, t11] Pressman, R.S., Software Engineering: A Practitioner's Approach, McGraw-Hill, New York, 1983. [12] Rajlich, V., Problems of Module Interconnection Language, in Hibbard, P.G., Schuman, S.A., Constructing Quality Software, North-Holland 1978, 147-152. [13] Rajlich, V., Stepwise Refinement Revisited, to be published, The Journal of Systems and Computers, 1984.

[14] Rajlich, V., A Paradigm for Top-Down Design with Pac kages, Res. Rep. CLR-TR-31-83, Nov. 1983, Computing Research Lab., 10(]79 East Engineering, Ann Arbor, MI 48109. [:: ] Ra'. i h, V. SNAF. -- A Language and Environment for I-': C)'qr"Amming.. i:n...... the-Large, to be published in F'Proc. IEEE Workshop o:)n I. l.(.. tC(j; f or (Aut omat i on 1984. [16] Wichman, B.A., Is Ada Too Big'? A Designer Answers the Crit.ics, Communications of ACM, Feb. 198Z1., 98 -10t3. [17] Wirth, N., Program Development by Stepwise Refinement, Communications of ACM, April 1971 22 -22' [18] Wirth, N., Modula-2, Res. Rep. 36, ETH, Institut fur Informatik, Zu rich, March 1982. [19] Yourdon, E., Constantine, L.L., Structured Design, PrenticeHall, Englewood Clif.fs, NJ., 1979. [20] Zelk witz, M., Brandstad, II., Proc. ACM SIGSOFT Rapid Prototyping Symposium, Columbia, MDI, April 1981. [21-] Wasserman, F. I., Freeman, P., Porcel la, M., Characteristics of Software Development Methodologies, in Olle, T.W., Sol, H.G., Tullyy, C.J., ed., In-formation Systems Design Methodologies: A Feature Analysis, North Holland, Amsterdam, 1983, 37-62. Appendix. Ei ght CQueens Problem'The f:ollowing example was originally published in [17]: Gi. ven are an 8*8 chessboard and 8 queens which are hosti le to each other. Find a position for each queen (a con-figur at:i (on ) such that no queen may be taken by another queen (i.e. such that every row, column, and diagonal contains at most one queen). A queen placed on the board attacts the squares as in Fig.. X X IiI -I I CI E:,ample of a correct solution is in Fig. 4.

Fig. 4. The solution to the problem is a program consisting of two packages BOARD and COLUMN and a subprogram MAIN. Package COLUMN defines a type COLUMN and several procedures which deal with that type: package IO_ INTEGER is new INTEGER._IO(INTEGER); with IO_INTEGER; use IO_INTEGER; package COLUMN is type COLUMN is private; procedure FIRS]T(A: out COLUMN); function SAFE(A,EB: in COLUMN; C,D: in INTEGER) return BOOLEAN; function LAST(A: in COLUMN) return BOOLERN; procedure NEXT _ROW(A: in out COLUMN); procedure PRINT_ROW(A: in COLUMN); pr i vate subtype COLUMN is INTEGER range 1..8 end COLUMN; package body COLUMN is procedure FIRST(A: out COLUMN) is begin end FIRST; function SAFE (A EB: in COLUMN; C,D: in INTEGER) return BOOLEAN i s begin if A=B or abs (A-EaB)=abs(C —D) then return TRUE; else return FALSE; end if; end SAFE; function LAST(A: in COLUMN) return EBOOLEAN is begin i f =8 then

return TRUE; el se return FALSE; end if; end LAST; pr'ocedure NEXT _ROW((A: in out COLUMN) is ID re C i n end NEXT ROW; procedure PRINT_ROW(A: in COLUMN) is begin PUT (A); end PRINT_ROW; end COLUMN; In pack:age EBOARiD, data structure BOARD is defined as an array of COLUMN, with the assumption -that each column contains one queen only (otherwise the queens attack each other). lso to place 8 queens, it is obvious that each column has to contain ex,%actly one queen. with COLUMN; use COLUMN; pack::age BOARD is procedure TRY FIRST; function NOT_FINISHED return BOOLEAN; function SUCCESFULL return BOOLEAN; procedure ADVANCE; pr ocedure REGRESS; procedure PFR I NT_.RESULT; end EBOARD; package body BOEARD is EBOARD: array (1..8) of COLUMN; I: INTEGER range 1..8; procedure TRY..FIRST is begin I:=1; FIRST(BOARD((1)); end TRYFIRST; f: unction NOT FINISHED return BOOLEAN is K: INTEGER range 1.. 8; N: EOOLEAN; begin i. T:::8 then return TRUE; else begin N: =FALSE; f or 1:: irn 1..'7 1loop i f SAFE (BOAR )(i BEOARD 8E3 )! <, 8 then N: ='TRUE; end i'f; end loop; reteurn N;

end if; end NOT_FINISHED; function SUCCESFULL return BOOLEAN is K:: INTEGER range 1..8; N1: EOOLEAN; begin N: =TRUE; for!:: in 1.. I-1 loop if SAFE (EOARD(k)), BOeARD(I),-::, I) then N:=FALSE; end if; end 1 oop; return N; end SUCCESFULL; procedure ADVANCE is begin I: =I+1; FIRST(BOARD(I)); end ADVANCE; procedure REGRESS is begin while LAST(BOARD(I)) loop I:=I-1; end 1 oop; NEXT ROW (BQOARD(I)); end REGRESS; procedure PRINT_RESULTS is:: INTEGER range 1..8; begin for K: in 1..8 loop F'R INT_ROW (:: ) end loop; end PRINT POSITION; end BOARD; In this package, TRY FIRST initializes the board to the first position, placing the first queen on the board. Boolean *f uncti on NOT FINISHED determines whether we reached the solut ion. Boolean function SUCCESFULL will determine whether it is possible to place another queen on the board. If yes, we will do so in procedure ADVANCE. If not, then we have to change the current situationq which will be done in REGRESS. The last compilation unit is a subprogram main: with BOARD; use BOCARD; procedure MAIN is begin TRY _FIRST; while NOT_FINISHED loop if SUCCESFULL then ADVANCE; else REGRESS; end if;'2 0)

end 1 oop; PRINT_RESULTS; end MAIN;

UNIVERSITY OF MICHIGAN 3 9015 03022 7402