THE UNIVERSITY OF MICHIIGAN COMPUTING RESEARCH LABORATORY A PARADIGM FOR TOP-DOWN DESIGN WITH PACKAGES Vaclav Rajlich CRL-TR-31-83 NOVEMBER 1983 Room 1079. East Engineering Building Ann Arbor, Michigan 48109 USA Tel: (313) 763-8000

A Paradigm for Top-down Design with Packages. Va(Ra:: L av Fa'Ij. i.c: h Department (.m)4: (o' C)ompuLt).-er and (onCommunl icati(::in Science UnJi. v:ersc i ttv of Michi. an Arti fi rbo(r, MI 4l81 ~9

f b iI t r c:: t. The paper p) re' tiis ai pariad im t-f or the desi gcn wi th packag -:es. T he par add i:gm c omb i rnes the methodology of stepwi se re (:f i n ement wi th i nrformatio.n hiding pri.nciple. It is based on steps o-f def:initi.on decompositi. on, completion, and abstraction, wh:i c_. h produce clean and wel.:l..de1::i ned pac: kagems. A part cof the parad i gm ar-e the ru:I.es by whi c-h the procedures acqui. re the par amnet ers (called first and second rules -for parameters).'The paradigm is illustrrated by an ex.ample. It is argued that "with'" (clausei o-f: IADA (together with fADA rdr. ec t- nmp.3 1 at:. ct:'o ) ec u::e(: r a e b Ot ton-up pr og r amm i n g i 1. e d:;cour a g i ncIr'l: the.op — d (.owJn pr ogra mmi ngq and hence shc:u 1 d be c: o ns i d e r e d ha -i r m f ul.

:. u I r tr od..:: t i on. Fac:kaqces (somr neti roest al s:) cal l. ed modul es) are general -I - ecoqg ni zed as an imp ortant.f: eatLur e of the new programming I angUiage- [1,e 6. 1:3, If properly us)ed,? they al low a pr'ogrram to be spl i. t into manageable pieces wh; i ich c:an be individual. 1.y designed, cdcl'ed, and tested. They al l1 ow c ooper'ati.:on of several programmers orn one so.ftware pr-ojec. ICf they are powerful. 1 and general en(!)ugh, they ext-,end the l angluaq.e by new constructs and hence they ex?,.tend an applicabili t'y of the.language. They are also intended to play a role of: reusable parts for future programs. These and other- ene-f:i. ts were th e r-eas-ons why pack:ages or modulP es were irnclu.tded intCo ADA and other proQgr.amming languagees.'1"h he basic::dica of the packages is in.formation hiding 7]. Eac h pa ck: age i mipl ements several objects i kI::e procedures, data structur' L es, 4 data types, etc. It is connected to the rest o-f: the pr (::gram t'.hr'ough the's..so -called ispeci-fication (i n other 1 angut..ages a. so c a ]. ed i n t er f: ace). Th e spe) i f i c at ion ]. i sts all.ob j et s (prc(cedure_-. {. functJ(:t;ns, t:ypes var i ab 1 es, etc. ) which are de-Fin:ned i. n the body c)f the pac:kac-ge and are available to the ou.t side ir cr a.:gam. Ho-3weveil t.le ef:i —:i.':i t on I tlhemsel vesI ar'e i nvis:i b ble to h the o ut des i d e. Ien the i-mpl. m emetat i on deta i. I s and r-el ated com:lpl e::i t.i es- re-ma:i.n hi cJdeil:i. nsi'ide t hfe pac: kage. Du r i n 3g t h e p r- c e s.: s'D po F.)- o. gr- am desi c.g ni the role co:f: the c: e is i CJ 1 e r t: d evc-.:. p t - s p e C: i.f ic. at i f n s (c- t: th e p a C k.:: a g e is. A,1. 1. the benef i cial rea.,asons for- using packages will 3. materi- i a ize. e on ly when t he pacl-::age s ar e desiied in a very c aref ulI marlner. The —','peri.ence shows tha t t h e i. f:er-ence between wel.l-designed and po C)ly::) r y- desigrned pa-l:i:acges mtay I-ave a enaor'mnoats intfluence onr the si.:ze, ef. f:ec ti ve.n e-s,; and the c::ost c:f the r-es ti ng program. It was argued that". t.-he c!.::i e -.g: tn o he "r-:iih t" pacl.::ages ii. a1n e-.:-treme-l. y di f fi.ic..t. arkt. pF.ar —ti. cu]. anrly in the situation when the:de.:L gn is-'. Ibased emaily on des:Lgners s intuit ion l. "he des3i gner has t~' f or "ee how his.Cspec:i:at.insW l i are goi i r-to b E i mp) emen t ed, w'- i c: h may b e a f:o r m.::l al b'1 e:- n t e I c: t u.a I t. I-::. I.- 4: a ct, he:. s i'r.equir~edcl g: (:: ) t. h i. Ik f ar a h ea c:l w:i. th a]. 1.a c c omp any iy g q I sk.s -c: o- m i.,A:. ( r -I a l c.i n - (:: r C. e-e. (n r::: i c:.. s t a c (a?.. e I t i. s c c.p: (:) ion that t.ie urcce s'f.].. ce 1 pcxarc a Si ginms have to c.-}f:.i: e rn~ very d et: a [.i r1 c tg s e Ps a nel the stt e s shoul C u i b!lt e 1. rildependrerit of eac:h other- as m'..och as possible. Al.so the par-adig.in sho:'.. u l ( pi rc) v r: de a r i g o r co u metho dol o(Igy wh:i: h wi IL:I 3:'+; er the.f: i. -fr gu..i d.anr-: e to the des1i cgl'ner When the desii gner master-ed the:e; t. a 1i 1 e:1 a4 n c r i g o or u sr o: p eh te d e s -ci (a n h e c a n a w ysre'!t:.ur-n bac:l:: to le es r igo ()r ous arndl. ess detai.lecd met lhodo.ogy, w. t h ~t Les i iorou..s meth:cdoli.ogy:i.rl th-le bacl.::ground. A mong the methods c-.rrent ly:i.n the c:ir-culati: ion th-e desigrner has to choose either the:r i 1nc i p:l. e of' i n (r mnat.:i o-n h i. di n 1c! (as an e amp le, see [:2': i ) or

the rigor (as an ex;ample. see [5 11. 14)). but not both. An overview of the currently used methodologies appears in [43. The paradigm explained here is an extension of the stepwise ref:i rnement [ 1. 2]. Sitepwie r e.f::i rement provides the most uni versal. paradigqm for progr-am desigrn, and it was chosen as the basis for the methodology of this paper. It was extended to include the principle of the information hiding, and hence to cover the design with packages. In particular, the "scope" is the basic unit of the design, rather than a procedure of E12J. Another important difference is the higher level of rigor as compared to C12]. In particular, we included the steps of completion and abstraction, and a thorough treatment of parameters (called "tfirst and second reason for parameters"). The paradigm explained here has one important element of style: All variables are local in the resulting packages, i.e. they never appear as a part of a specification. The packages c: ommunicate via procedure calls and types only. This style is the most elegant style of modular decomposition of the systems, and it was widely advocated in the literatureE[13. Also the resulting packages avoid nesting of procedures, which again was criticized in the literature [..8]. The paper consists of four chapters. Chapter 2 contains the description of the methodology. It describes the basic steps of definition, decomposition: completion, and abstraction, on which the methodology is based. The two reasons for procedure parameters are introduced. Chapter 3 contains an example of the des-;ign in ADA —l i. ke design language. Chapter 4 contains some thou.kghts on conversion of the designs into programs. Chapter- 5 contains a criticism of some ADA constructs *from the point of view of the paradigm. X2. Basic notions. During the program design, the program consists of two parts: ex i sti ng pa rt, which is the part already finished (and possibly stored in the compulter), and intended part_, which consists of everything what has not been done yet CO)]. The role of a step of the design methodology is to add to the existing part, and to subtract from the intended part. There is an interface betwee.,n the two parts of the progranmn. ~ h i c w1 wi l l be cal] led bac.klo C..C i lte:rface. It con nists ori t th.::..b.ir"ct wt-i c:h t-lhve.-:reaiv' tb:;.i,-,n:.'sed in the C::.. i stirg part., I::) *t.i',. -.i9.4 i. t h ae it - he

c:ef:i re: n ec (i:i i i Var i. ab le whose narmesi; have been introdulc:ed but their types ha ve not beenr dec ].ared T h e ln f i n i s h edcl c e: c t s ar-e i n t errelated by t h e f: o I ow i n q rel ati ons: (i) Rel ations "read",'write", and "readwrite" between vari abl es an d pro czc:edur..r es /,: fun cti.ons r; (ii Rel at:i ons "i " " fltt:." and "in out" between unf:ini.shed types,, and procedures/f Lc ttio nrs. This relation describes the mode a —cl type of f (Jr-al parameters of procedLur es f/f unct i on s. E:x.amples of baCcklog inter"f-:aces are in Fig. 2 and F-ii..3. In th-e: i guLre, t.he pr oc:eures / unc:t i ons are deno::ted by rectanglees, t-he variabl].e; are denoted by ovalsii, and the types are denoted by d i-. aT i on ds a Rel I a't- i s ar e ot e d b a r r o w poi nt i i n t h e d:i. r e t i o fn co.f t he i. n. e mati. o f 1 (: w. F' rc:eur - un cti. on s, r n d types al -so c:ontai n t. he names)i o-f all pack ages in which they were Li SC d u..C:_ O pe o f: v air-:i a b ]. e o r type V i s t h e set of: all 1 pr oc:edures/.functi ons related to V,. Scc)ope oaf a proc:edure F'.s the pr"ocecHIure itsel f. The mnethodc:)l ogy of this: paper is based on the f(:). I owi ng s:t eps: (i ) clef i ni ti on (ii) decomposition and compl.eti.on (:i i i ) a b s t r ac ti or n. Each of-": t.hese stepsE r'emove!s cert ai n ob j ects f rIom the back::l(c). nt:er.f:ac e and may acid new ones tc) it. Each of them also acdds one pac:: i- ag e t c) the ex' isting par t of: t h e program. "The steps are desc:r.ibed in the following way: (i ) D)e:; i ni ti on.................................................. Def inn i. t I(aI-o i s s tep. in which we def:ine one or several un::i. nis.l-ed objects in ter-ms o(f the primi ti.ves of the programming.1 rangur)iage. If the oub je:::t. is a prloc::edL.tre. we will def:ine it}s body. I:f:i.t is a variatble., we wi.l. giv.e its, type. If: it is a type, we wi l 1 def:ine its representation. These objects are then removed f rocm the backlog interface. An i nlmportanlt property:: definition is that the sma:l 1 est uni.t of de-finition is a scope. Every defin ition step means that In::.!e or several scopes are de'f:i. ned at once. A procedure c an be ful. 1y defined onl.y i.f all related objects (variables:, types) are clef:irled in the same step. If procedure F' is r-elated to varia.bles V V1.e-, Vi V r, and to types'11. T'2, s;ane step, thenr pr oc:tclur e F' c:an be 4ful y def:ineed. I4: one or more variables and/or types remain unidefinled, then I)rocedLtre FP can be def:i. ned only partally. It.:':s body will have to c:ontain calls of new un-fini nshed prcc:edLr-es F::1. F' P2,... F":'k which will be rel ated to t:he va riables/typIes whi.c:h1 remai ined undefinted.

Atn i: mporta-lnt. ru I e is; t-.he r'-ule whic:h we will cal I f: rst r-e..aso for pr s.rar ame...t. ers. It is explained in the following way: Let P be a pr'oc:edure which is rel.ated t o variables V1. V24' V. Vn where var-iables V1, YV, t Vm wer e def ined vari. abl es V (m+1l ) def i ned with new unf ni shed procedure PF being called in its body. The procedur-e F'P will] have actual parameters V1, V2,... Yvam, i.e. the body of P'S will be procedure P1 is beg i n PF" (V1.4 V2I-,.. q VmIn) e nid F' I The rule (can be iusti4:1ie dl by the -following reasoninng: Ea(:h definiti.on step pr-oduc::es a pack-:age. As r-emar-ked earlier-: we allow t h-e communic cati on between pack:i::ages thr'ough procedure par ameters only, disallowing direct accessibility of data. Procedure PF may inherit all r-el at:ionships o:f the original procedur'e P, i.e. it may be related to all var-i. a. bles VI V2,..,Vn. However the de:':i r'it iLons of thesie var iiables wi I1. be spread over at least two pac:k ages: ="' Ile c u r-rent t pac kFage wher-e V1I V2,.. Vm are def inedl an d somne u4:ture pacl::ages where both PF' and some of the variables V(m+l).4... Vn will be de-fined. Then there is the need for the parameter.; F. (V 1. V2,... Vn) A s anr e.x:ample of: a step whe re i:ir-st reason for par-ametersa wa-; applied, see package DEFINE.....D of ec: t i n:3 (ii) Decompo(si tion arniCd comp lTn 3 etio gnF Decompos i t i. on a nd co:mpl eti on i s another step of: the meth-1n odoloqg y. In i.t, we decompose an unfinished object A into -!se-veral smaller unfini-shed objects A1, A'. St An. If obiect A i.s a variable, type, and pr-ocedLCure, then objects A, A2, An w:i. 1. al s o ) be variables, types aned pr'c:edur-es, respectively. Moreover i.f A was related to P, then a nonempty subset of A1, A2q Th e step C)of d( e C(cp o pos:. ti on i s u.u a i1 y tarted with a decomposi ti on of a var i at:ble or- a type. Then the rel1ated F-proced vur'es/f funcctinors5 are der:omposdecl. -1Then the completion fol lows. In th're substep Of compl1 (?t ion we ins-;pect al1. new uni:irl:ished (:)1I.- ects andci try t. det. er.i n whether they can uf fr)nc:tion correct:l. y or I- whetherl they need t-o be rel-ated to some addcitional ob jects.'TI- e re a r etwo. i t a t. i oris wh i ch r-e(ui r-e i n tr oduct i. on o: n e w: jec::ts: irs Ft, two proc:eldur e may need tc commu.nicate with each hei:.hr.,I arnid hernc: there is a need 4;or a new valriable which will a.:ci. i tate this communi ca::tion. ecr, vari ab.es may need an i:nit.i. a 1:i z i -g procedures::el.r whi:::h wi.l set- t he initial va J.ues. None of these newv objects were introduced by decomposit iton, hence we lhave to have the spec:i.:xl sub~step of: complet.io~n. Anri e.xisting part of the program is c.omE!.ete w-hen rio new cobjects can be irntroduced by the process of (complletion, i.e. all communi cations among

pr:oceddcrl-es have beenl sier ved by appr o priate var i ab les, and all variables have been properly initialized. The;tep of decomnposCit:ion and (:(::)mpletion again produces a p) a ck: age. (:i iii) Abs;t r -act i on. Ab stt r ca t:i on is a spec: i. a:l. c:ase o: de-fini.tion inn whi (-.h a var-iable V is decl]ar-ed to be c-f type T" where r is an unfinished type. As;in every def nintiti, o -he whole scopef of var-iable V has to-) be de-fined. I-f V is read by procedure P, then the body of F' vwill ca:L a rnew uni::nis-hed prcD cedure F1 (V: in T). This acti on wi ll be cal led second rea.s:.on] for pr!Tameters. The puLrpose c)of a btstrac t:i on step is to replace several. sim ilm] laarr un:finished variables by one type, and similar unfinished p ro- (:c: e d u.. r eds by cron e more abstrac t: procedure. The reason i. s ec:rnom:i cal bacl::l gc i1 nter-face will be si mpli fied. because several variables and pruocedures will be replaced by a smaller number of n1ewly i ntrloduced types and pr(c::)cedures, respectively. As shown i.ii the e xample;-f the nextt section, the procedures (r.func(-t. iosii may ac:qui re everal parameters either through 4 i rst C) r s e c: o -d r- e a s; o \ (:) r- t c:) t.h. Hence i. f we have pr- oce d u.r-e F' (V 1, V2,..Vn) whic 1- a rleady h als severtal p ar amet er s and it:i s il~n scope of a vari.able W which is being defined, then its body wil I contain a call of proc:edur'e P1. (V1,V2..," Vn W) When pac:: a c;agesi ar e pr a duce.ld e i by these steps, then the r- ecsu il ting program consists of: pac 1-ages or g an ied by the r' elationship o. f procu:edure c:a lls into a directed acyclic graph. In [:? I,I this rela. ti onship was c alled the relationship of "seni or i t y" The resulti i nc program consis st of several 1 avers of vYi.r-tal machines, where the formerly de-fined backlog interfaces 1ave bec::ome the virtutal aci nes. Th le Sdesign methodolo. gy decsribed by these steps is directly *at pp 1 i c ab 1. e t a 1. I moduL e or pac kage-or i e n t ed p r (:) g r a mm:L g. aguaes:i ncl g eudi rg new odulalr langutages l ike ADA Modul a —2 or 1M1ESA EA1C I6 13].: In the next section:ar the methodology will:l be exp-i e. a i n-d on an e amp 1 C, tsin rg an ADA —l.ike language f or the d.e m o n s t r a t i o) n An examrle.. In thi is secti3on, we shall 1 illustrate t.h:e paradigm orn the f fo:l. owing geometri cal. probi. em: Findr: t:he int:ersec::.:iron uf t.wo 1 irnes LN1 arnd ILN2 and -find two points, B on l.ine LN1 with distance 1.0. fro m the intersection, see Fig. 1.

1...N2 D D FIi g. 1 The probl.em wi. ll be so;lved( in thi;s s;ec(t:iorl with the use of an GADA — I i ke des i C. n 1an g uag e. It should be i mmed i. atel y unlderstandable to anyonle familiar with ADA or any other pac[k:age or module-oriented higher- -l].evel ].anguage. The "used in" clause precedes ever.y pacl::kage definition. It c:onsists of: an e.:,ec:u table part which is al.most identical to ADA, and a graphical part which descr:ibes back:1log interface. The main difference with ADA is the occurance of "used in" c].ause prec eding each package. The clause l ists all packag-es which use the objects of the given pack::age. As the start, 1.the whole prchoblem is solved as a call o.f one procedure: pr'oced(ure MAIN is b. eg i n l1A I N 1\: end; The pr,cedure MAIN-1. i; dec'omposed i n the folo wing way: used in MAIN; p ac l: age DEC(MF:'OSE..MA I N 1. is procecdure MAIN1 end DE.C(]OMPOSE'_ MAIN1; package body DECOMFPOSE.....MAIN1 is procedure MIAINi is b eg i n RF-'AD Li1:1 READI) L..N2 READ D; I. N'TE R l E: C 1" I 0 N; F I ND P'TS WR I'T'E _A; WRI TE.B; end MAINI1; end DECOMPOSE MnAINi; In this te'.'xt, REALD) LiLN 1. REtAD L. N2: and READI:O.) read input data -forl 1 irnes LN1., LN2 and di.stande D, r-especti vely FProcedure INTEIRSE:lCTIO' N -f inds the inter-setionr of LN1. and r LN2. P'rocredcure F-IND.. F'TS finds pointsP n artd B, and proceduitres WFRITE..A ancd WRITE.... B print them out. "JUsed in" clause i.ndicates that procedure MAtINI is called inr subpr-ogram MAtIN.

In the subsequent c(:mpletion, we will introduce variables LN1, LN2' D, X, A, and B whi.c:h wll. 1 faci.cjiA tate- the commu..iciaation between the procedure.s. Their- role i s the same as in Figure 2. They will not appear as a part of the executable program, but will become a part ocf back-.:og interface of Fig.2. IREAD LNI in DECOMPOISE MAlN T i < LN1 ) _,.1 - -- READLN2 in DECOMPOSE - MAI:NI. LN2> IREADD in DECOMPOSE MA IN1,...'',D J JINTERSECTION in DECOMPOSE MAIN1 X)!FIND PTS in DECOMPOSE MAINI N iWRITE A in DECOMF)OSE _MAIUN I. -WRITE B in DECOMPOSE MAIN1 I — Fig. 2. Note that backlog interface contains some additional information which does not appear in the previous package, like names of the variables, their relationship to procedures, etc. Nex.t step is definition of D, which will produc:e the foll. owing package: used in DECOMPOSE. MA I N; package DEFINE _ is procedure READ_ D; procedure F IN _F'-IS; end DEFINED; package body DEFINE...)D; D:float; procedure READ_D is begin put ("Enter the distance:"); get (D); end READ D; proced-.tr-e FIND....PTS i. begi n FIND 1\. PT S (D) end FIND.I.F:'' S; end DEFINE D; In thi.s step, we def:ined variable [) and procedures READ_.D FIND_ PTS of its -scope. In case cof procedure RE-AD.D, we were able to define the body oCf: the procedu re c (ompletely us;ing the standard

constructs of the underlying language ADA. In case of procedure FIND_ PTS, observe that the procedure is in scope of several vari ab 1 es: D, L.N 1., E. Only one of these variables is being def i ned i n t.h i.s ste:3 hr:c_:i —. t: h1-Ie body (3f: the p roced r e mu s t cronltain a i a]: 1 t:O a suprLt: oc.: - c)edur-e with acit. ual parameter D, following the first reason f:or parameters. By a coincidence, the call of the subprocedure is the only statement of the body of FIND _FPTS. The subprocedure was named FIND_ PTS(D:in float), i.e. it reuses the name of the original procedure, which is allowed by the principle of overloading in nDA. "Used in" clause indicates where the procedures of the package are called. Note that the information in backlog interface of Fig 2o was useful for both determining the scope of D) and determining the "used in" c: lause. New backlog interface is in Fig. 3. [READ LN1 in DECOMI-'OSE MAIN1 1. — -. LN1 I'READ LN2 in DECOMPOSEM I N1\1 I ALN2,'T ERSECTI ON in D)ECO1MFOSE M I 1 I Nk: X) FIND_PTS(D: i n float) in DEF I NED A i WRITE A in DECOMPOFSE _MIN1 jWRIT E -B in DECOMPOSE MAIN1"NI Fig.:. I C) ".

Nex t step i s a step of abstracti on. We observe that variables LN1 and LN2 are of the same type, and hence can be defined in the following g pa::age: used in DECOMPOSE_ MAI NN1; package ABSTRACT.. LN 1i s procedure READ LNl.; procedure READ LN2-; procedure INTERSECTION; procedure FIND PTS(D: in float); end ABSTRACT LN; pack age body TFABSTRACT LN is LN1, LN2: LN; procedure REA-D...LN1 is begin R::EAD LN (LN 1) end READ LN1; procedure READ LN.L2 is begin REAiD LN(L12); end REOAD LN2; procedure I NTERSECT ION; begin I NTERSECT IO1N ( LN 1 LN2) end INTERSECTION; procedure - IND FTS (D; i n f 1 oat) i s begin FIND.F..TS(D(D,LN1); end ABSTRACT. LN; Note that in this:step, the second reason for parameters was applied in definition of all procedures of the package body. New undefined type LN appears in -the current backlog interf ace of: Fig.4.,READ LN(LN:out LN) in BSTRANCT_LN r —- N>$L in ABSTRACTLN' _....................... iINTERSECTION(LNI... LN2': in LhN) in ABSTRACT LN'- -' X FIND_PTS(D: in flcat;'LN1i:in LN) in ABSTRACT LN'' A WR I TE _A in DECOMFPOSE M I N 1 ^ Fig. 4. 1i

Nex.t step is again a step of abstraction, in which points A, B. and X are declared to be of the same type. In the step: all procedures of scopes of A, B, and X are also defined: used in DECOMPOSE...MAINI1, i BS"TRACT_LN; package ABSTRACT_PT is procedure INTERSECT ION (LN.1,LN2: in LN); procedure FIIND PTS(D:in float;LNI:in LN); procedure WRITE-_A procedure WRITE B; end ABSTRACTFT; package body ABSTRACT.-.PT i s X,A,B:PT; procedure INTERSECTION(LNI:LN2:.in LN) is begin I NTERSE C:T I ON (LN 1,LN24 X) end I N'T'ERSECT I ON; procedure FIND T'PTS(D::in float;LN1:i.n LN;AEB:out PT); begin FIND_ TS (D,LN1, X, A. B) end FIND I).F PTS; procedure WRITE A; begin WR ITE PT (A) end WRI TE. A:; procedure WRITE...B; begin WFR I TE-_F'' ( E ); end WRITE B; end ABSTRACT_PT; The new bac:klog interface is in Fig. 5. iREAD"LN(LN1:out LN) in ABESTRACTLN LN in ABSTRACT LN, - \ABSTRACT PT INTERSECTION(LN1,LN2: in iLN;X: out PT) in ABSTRACT PT' [FI'ND PTS (D: in float;LN1: in 1LN;X: in'PT;A.B:. out PTF)" i in ABSTRACT' T....T.....i PT........).., in ABSTRACT. ~: PT...........i WRITE PT (:(A in PT):i n ABSTRACT FPT -'.. PT i n ABSTRACT FP1 Fig. 5. 12

In the last st ep, we wi. 1 I def i ne? both F:T and LN. Anralternative option woul d be to de-fine only one of them and postpone the definition of: the other to the following step. We will give only speci.fic atti on s: her-e; The body of the pack:age is left to the reader. use d i n A5BTRANCT...\1. A A BiSTRAC TPT; package DEFINE_ L.L. is type LN is private; type PT is private; procedure READ...LN(LN1:.out LN); procedure INTERSE(CT I ON (LN1,LN2: i.n LN;X:out PT); procedure FIND. T.PTS (D: i n fl oat;LNI.:in LN; X i n PT; A,B:out PT); procedure WRITE PT(A:in PT); private; type LN is re(cord X....iECTION, Y SEC" "ION:-float; end record; type PT is record X, Y: float; end record; end DEFINE ALL; 4. Conversion of d_.es.i.gr.n.i.n. t.C prqgrams. The paradigm explained in the previous two sections o:fers a rigorous method of program design. It is obvious that the designs are already very cllose to the iuture programs. In fact, there are only two deficiencies which have to be removed: (i)'The pact:lages a-re very small. (ii) The packages crontain "used in" clauses which do not have any ccounterpart in (IDA. The f:ir'st deficiency is removed by merging s;everal steps of the methodology into one so that a reasonably sized packages are achieved. This is done by a tex'tual processing of the design of in the -following way: Suppose that we have two design packages A and B which we want tto merge together, then we will macroex.pand bodies of procedures and definitions o.f types o.f B in places of pr'ocedure calls arnd vartltle declarations in A, respectively. Moreover we wi. l copy variiabl.e declarations and "used in" clauses from both (A and B into the resulting pack Sage. To remove the second def ici ency, note that "used i n" relationship is an inverse! relationship to the combination of "with" and "use" clause of ADfA. H~ence if we have two packages P and R which are related in the des!ign in the fol lowing way: 1.:3

itsed in n a a s pa(-[:age FP; used l n in P package R; end F; then replacing "used in" by a combination of "with" and "use" will give US with R...; Use R pac::age F'; end P; with... use.. package R; end R; L.et Lis demnc)it1lrate the proceciss of c::onversion on the desiqn from the previous Isection. As the first step, we may merge procedure MArIN with packages- DEIOIIMFPOSEMlMIxN1 and DEFINE.... D to produce one compilatlion unit called NEW...MAIN. Similarly packages ABSTRACT-LN and AEBST'RACT FlT l may be merged into one package ABSTRACT. Then we will replace "used in" clauses by "with" and "use" clauses.l The res.u.lting program in nDA is the following one: with AEBSTRACT; use, BSTRC.T; procedure NEW MIIAIN ij.si D:flosat:; begin REnD.iLN; READf L N'2 get. (D) INTERSECT I ON; F INID i-TS ( ); WR TE A; WRI r TE E-; end NEW M IAN; with...; use..14

w:t. tVi: I:.f". NE LL... 7 t. — l.':i.L 41=:.. f-LL.~. pac.l.:ag(:ABiST' (:\C'': L. I.i.F ( pI' (c"ed'rl'Te FR E () l) L NC"T p r oced ure F pr oc eduL r r-e.? ti. IN' i; pack:: ag e bod jy; A 1 cA'I T "i Si X,, L: F'' 1 )r- o c e dvur c- I'- i "fl C'L;1. i. s begs i. n1 e n d F"'1'S - n i.. i':.: I.... 1 i. end r I A 1t N 1; begin R E1A D._I (I.,i: IJ ") p -oZ ed -: e RIEA[).....I 1 D:. n -f- I I a t I b er'..]F. n' 3:; IN 1) A!....:' T ( L.'. i.,; ) I e:.J F:- I T. I:i \ " D r-'.0 (-: e d..I r r' e;: J'4"I" E'., 1': L S beg i. n Fit l.)' l L 1, IA B 1; en ri F::'I N.1 _I::1 (; i-j) — o edure WF., i1! beg i n WR,'I" E'. F:'1 ( A); cit c: I.: (a2-'39Tk'&.( e.. WI:..:. "['..... A;. — s c nchange:wevr we may need t spec E. i i. y 5. UF e uid wd i th et ei c of.)(Xi cn i der Ved harofu le mI-. C a i o-sh i p f oe c.is i. i s pre C:Omj)~t 1 1 at 1:i o! 1 How. h F..e.v.e. - ths e p.-f:i cr e,: sec.. r ii J:t.':i n d m t teld t. hat th D e F w]i t..I F A 1~ ~ ~~~p-~tl il h l..5 al\1) d "L t.1.56C"':]. L.'.. t...t.~v~.;.E!,.(::i,''t> C)1'- a[).~ r-.t:r —; c-,ai)E::ei a sp c al p-r.-1!:1.;l- r~? whe c?:,-1J61., i. fl ni 1''1q

- og r am by t:op C. c:lc)Jrl met:.I:l) illE.- r eaiso;n i.o t -that. t rnring t.he to::.) down desi. grl, we may:knohw what proc-) edurei. var:i able s, c)r typeis are needed but. t we d o nlo: t t::rnr:w whi.c-h comp)i 1 at i on uni. t they wi. 1. be d (. t: i n ed i l::- h::H crncl eer' t.: ent of the " w i. t h n -id t oSe e c: a LseE; c: a-n be det.erfminr(dc c:)rlnly c.f:t. el-t the whol].e! pFlrCgr-afn (Corl' mcost. of the p-) r () c! Ir a in ) w a s d e s:i. g n e (:1, T h:i. s o n t r' a s t sn h a r p) 1. y w i t h t I- e bo - t )m —U p desi g n. The par-acligm of bottom(T -— uIp de:i. gn i s based o n th e idea of e:-' t:ensi.on of; t h he -: i s t. i ri (.- 1 an ai g (-I:) y (Jy a(:-.1(::! i t:.: ( na ] (: on s t r u o:, t F a F:'r th i. s p I.r p c)e 5 u ) C and "wi t h " C::]. 1t..auses are c::(: ) mpleti el nat:r..r. al becaus;e i ( )wer c:m:)i 1 lati onr units are de.signed before tl-ihe. higher units are. T"['hen ~t..I-ee:ir r' c n plr'ob ]. em to) (:leter mi ne i n whi(::h c:-mp i.t i on urn i t tlne pVr- o:cedures, types., etc. ar-e de:ined, i.e. it is poss:ible to dt e t m r' i n e w i't-".. n: ":. a u s i m m e d i at e:I. 1l Hence we hatl v t'o c (nc u1 d e that "wi th and "use" cI auses a, d t. he e - C eri": o.f c:::p::)Ti i [L aJt -:. i. c) i In ( -d a ) n (Z ou r age b ot t f:m- p pl-: r- ammi ng,, w h i 1 e di sco. cJu:'. i. ng the to)p —-dcown pro grammi. ng:i n a ob ut t! a t:i a ]. way. t- w a" r(.: u e d m any t i thnaet.h-a t t.he to p p -d (own I-)ara- a d i gm is prf r e-f' er" ab. e to: the bottoml.....up one [12]. Hence these t.w o pr a mm i n g c:o n r: t r u.t (::t; en? n- c: r g e a n i rnf er' i Or p r T::r a m r i In C!;rac-t i. ce, ^anrd Shol-.lI:.l c:e c:cnsi. derecl 1iarmf:l. F e f:. fr e n c: e!s. 1i] nd a F:'r.:)gr fnrafi ng q.._a n ageu(. Iii ailit.a"y!standard MI I_-STD 1 E15.':'J] B c,:. c:)h, h S o f t w a r- e En g i n eer i n g wt. t h ca, "r h e B e.n j am i n Ummlr n c ls Fiub 1. Co, Men l::.- Fiar k CA, 1. 9833. C[-;] Clar'-keq L. i Wi. ledem. C. Wol. f, LA.L.. Nesti nqg. i n Ada F:'r!- am ijr s I: or Ithe- i rd f-:, Ij. gpla n Not ice Nov. 198C, 1 39; Q- 145. t::X q r F:' re e.,, W a sF Ws e r ma n- A.'f o'f t w a r- e e v e ]. o me n t MIlet.:t(hodol og i e s andl A(-da, Re s. Rep-. -'he Un i'vcrs::i. t:y o-f; Cal]. i: or ia, l-rv-i. hen CA. [.J ac l.::r 11yi i y<.;tmrr I:v'-tee l.'I: opn)on tM, I:r e nrt:i c:e -Ha:L l, E ng 1 e wood(i C".:: s, J., 198 f:. ti].L L. au r t;tH-. e C., a'. eLr i t h wa:i.t. e, E. The Impact of Mesa on B,/ym -stem Desi gn, FProc. 4th. I nternati onal Con f: er ence on So f: t ware En lcneer i ing, lEE Cata og Nc.'79CHI4'79...5C 1979 174 — 18 2. i::.:1] FParna.r s, D.! L.r.,ri. lc Sof:tware for Ease of: E',xtensmicnr and C o 1 act: r i n, Il-:- KE "1r ar. o:) n S o-f t: w a r-e Eng i neer i n Marc:h 1. 97 9 [:::1 Ra.j i c h, V., - i. erar c:h i.c: al. vs. El oc:: Str-uctoure, I n* r: I -a t). r. ion Flrocessing Machines, Vol. 21, Academia P'rague 1979,q ~'-::3.16

:? Rxaji::h V1, f'- r o ]i. emi; of I'odul.1: I ICterc tonnect. on Lang cUage. i r H i. b b a r d F:'. G., Sc: h u m a n, Con stru t i n] (C X Qi i a l i ty 0c t wa' e'E Nor-th-Holland 1978q, 1471.... 52. [1,:1) Ra.jL ich, lV..,-ep:i pwL(;. Ref- i nement. Reev ist F'dtedev, s.I Rp CR FK L....... TR -;13-.8, Comput i ng Re;e-ar-ch Labor-atory Univer-sity of Mi chi igar, Arn Arbor, MI. L 1] R o s s; Da' T. S (: h,m a nl rt t r, JS ) t rn u ct t u r es f r Requirements Def i ni t i on, IEEE Tr'ans. on So-f:tware Eng i neer- i ng, Jan. 19'77, 615. i L. 12', ] Wi rt.h N1 q r- o3gram D)evelonpment by t tepwi s e Ref i nement, Communications of f "ACM, Apr-il 1971, 2 21-227. I[ 1:] Wi r- t h No. M i: --.C R e.. R. ep. L36, ETH, Inst i tut.: ur 111 nf:ormat1ik:, Z r i: M ar'h 1:982 [:1. 4:] Y()t tr"d (:n, E., Con r-st: aI t i ne..., L.L.. Stlr uc:: ture Des ign I'r en t:i Lc — Hall, Enq lewooc C.i. f f NJ. i 1.: 79. 1;7