SIMPLE: A program development system

ComputerLm~jt,a~e~,Vol.5, pp. 103 to 114

0096..0551/80/0501-0103502.00/~

¢) Perpmon PressLtd 1980.Printedin Great Britain

SIMPLE: A PROGRAM

DEVELOPMENT

AUGUSTO CELENTANO, PIERLUIGI DELLA VIGNA, CARLO

SYSTEM* GHEZZ~?

and DINO MANDRIOLI lstituto di Elettrotecnica ed Elettronica, Politeenico di Milano, Piazza L. da Vinci 32, 20133 Milano, Italy (Received 5 June 1979; revision received 8 November 1979)

Aistraet--A program development system (PDS) should support a smooth transition between design, development, debugging, testing and final production of a software system. Man-machine interaction, though necessary, should not allow the user to modify the program or its execution state in an unstructured way; rather, disciplined interaction should be enforced by the PDS. After a review of the most desirable features of a PDS, the underlying philosophy of SIMPLE, a PDS which supports the development of Pascal programs, is introduced. The general structure of the SIMPLE system and the basic implementation choices are also discussed. Programming system Top-clown programming Bottom-up programming Modularity Abstraction levels Editing Binding Block-structure Intermediate language Interpreter Interactive programming

1. I N T R O D U C T I O N

Recent results in software engineering have led to the definition of design methodologies and software tools which can be used harmoniously in software production. It is a generally held opinion E1-4] that programming activity should be supported by a complete Program Development System (PDS) which not only helps, but forces a methodology by which the programmer develops systems in a disciplined way by, (a) a top-down refinement and/or a bottom-up aggregation of modules, or (b) abstraction levels. Both (a) and (b) strongly encourage modular programming by suggesting the use of libraries and combining the work of several programmers. In order to enhance the programmer's confidence in the correctness and reliability of his/her program, high quality diagnostics and recovery features should be provided, both at compile-time and run-time by, (a) maximizing static checking whenever possible, and (b) carefully reporting and classifying run-time errors, possibly allowing the execution to be resumed in a safe state. Furthermore, the programmer should be assisted during all the phases of program development, from editing a simple module up to executing a complete program, and most of the activities (e.g. testing and debugging) should be supported even on a partially completed program. The programming environment greatly influences the capabilities offered by such a system: a batch environment could hardly support all the desired features, especially at run-time. An interactive environment, however, may provide too much freedom in acx:essing and modifying the program or its executing state. That is it may allow unstructured programming activity. Ideally, a PDS should be an interactive system with a strong discipline on the user-system dialogue during all the phases of program construction. Finally, while the whole development process should be assisted by the PDS, an efficient execution of the final product should be the concern of a separate compiler (and, possibly, a separate machine). This does not necessarily postpone performance evaluation * Work supported by Consiglio Nazionale delle Ricerche, Centro Studi per l'IngogneHa dei Sistemi per I'Elaborazione delle Informazioni. t Present i ~ l r e u : Department of Computer Science, University of North Carolina at Chapel Hill, New West Hall 035A, Chapel Hill, NC 27514, U.S.A. 103

104

AUGUSTOCELENTANOet al.

of programs to the final execution phase. Information about the most frequently executed portions of code can be obtained by running the program with sample data in the PDS environment and the PDS facilities can be used to modify the program in order to improve its efficiency. In our case, the PDS is implemented on a small machine (a PDP 11/36) while the final products are executed on a large machine (a UNIVAC 1100/80). 2. THE CHOICE OF THE PROGRAMMING LANGUAGE A central issue in the design of a PDS is the choice (or the design) of the programming language. User needs and implementation problems will determine this choice. The recent literature offers a large variety of proposals for new languages which enhance safe programming by including the above-mentioned features (modularity, programming by abstraction levels, provability,... )1-5-8]. Many of these languages, however, are still in an early stage of definition and implementation and there is no general agreement about the features they should provide. All of the languages seem to require a large amount of run-time support which should make their inclusion in an interactive development system quite difficult, especially on a small machine. In view of this unsatisfactory state of the art, one might decide to design a completely new programming language which fits all of the PDS requirements, by including dialogue facilities and constructs for modularization, information hiding and abstraction. This decision would make the design of the entire PDS a formidable task even for a well organized project team. Furthermore, programs developedby such a system would not be compatible with any other system, unless new translators are implemented or the whole PDS is designed to be portable, an even harder job. An alternative, more realistic, approach would be to adopt an existing, practical, widely used and appreciated language, and to slightly modify or augment it to fit the user needs; abstraction, modularization, dialogue facilities can be inserted on top of existing language constructs such as type structure, block structure and input-output procedures. This approach, which is strongly recommended by a number of authors [9-11], has been chosen in our system. We decided to enrich a subset of Pascal, called Pascai-S [12] by introducing modularization and information hiding, but still preserving the possibility of an easy final step of macroprocessing to produce, from a completely developed program, an equivalent strict Pascal-S program which can be processed by any Pascal compiler. In the sequel, a survey of the extensions will be presented, leaving a detailed description to 1"13]. To allow modular programming, and to facilitate the use of libraries, we define a compilation unit, called a module, to be a set of Pascal-S procedures or functions (the main program is considered a priveleged procedure). To allow complete static checking on the module, all external objects (global constants, types, variables and used procedures) must be declared in a requires clause, as shown in Fig. 1. Modules can be assembled into a program by a linker whose input specifies the static nesting structure of the collection of modules. For example, suppose that a, b, c and d are the procedures implemented within modules A, B, C and D respectively and suppose that the structure of the linked program is to be the following: procedure a ( ); procedure b ( ); end {b}; procedure c ( ); procedure d ( ); end {d} ; end {c}; end {a}; Then the linkage command must Specify such a structure, and this can be done by giving either the static nesting tree (SNT) or, equivalently, its linear description (see Fig. 2).

S I M P L E : A program development system

105

nodule er~mple requires t F p e t l - 8rrn~" [ 1 : 1 0 0 ] of l n t q e r ; t2 - r ~ o r d

8].fa : : L n t q e r ;

bet8 : b o o l u n

end; vat v l : t:l; procedure p ( t l ; ~ t:2); funcg£on f ( g l ) : real

procedure

( p a r k : t l ; vsr par2 : t 2 ) ( d - o l a r a t l o n s of couetnnee, types, v a r i a b l e , , procedures and functions Ioc-I to pl}

pl

bqtn

,.,.s (pl}; procedure p2

w,i,,,

" (p2)

m,,,Ims4u~@,

Fig. 1. An example of interface sggcification.

Each procedure (or function) of the module Can contain'any number of local procedures (or functions) at an arbitrary level of static nesting, as is defined in Pascal. This solution allows the construction of programs starting from building blocks (modules) with no predefined limits on the complexity of their internal structure, ranging from the simple use of a collection of separate procedures with no local procedures to a unique module which encloses the entire program. Each linked set of modules itself behaves as a module and, thus, can be kept in the library and later used as a basic building block in constructing a new program.

A

(a}

(b}

B

C

A(BC(D))

Fig. 2. (a) Static nesting tree.(b) Corresponding parenthesized expression.

106

AUGUSTOC~T^NO et al.

For the sake of simplicity, if a module is not a leaf of the SNT, we assume that only one procedure (or function) is enclosed*, otherwise the structure defined by the SNT would be ambiguous. For example, if module C of Fig. 2 were composed of the two procedures CI and C2, the SNT would not specify whether D is to be nested within C1 or C2. During the linking phase, the scope rules of Pascal are used to check the consistency between the specifications in the requires part and the declarations appearing in external modules. Consider the SNT of Fig. 2, where D is the module "example" of Fig. 1. In such a case, tl and t2 must match a declaration of local types tl and t2 appearing either in C or in A; iftl and t2 are declared as local to A, then vl must be local to A or C, and p a n d f m u s t be implemented either in A, B, or C with formal parameters consistent in type, number and parameter passing mode (by value or by reference) with those appearing in the requires clause of D. A detailed, and complete treatment of consistency checks can be found in 1-16]. 3. THE DESIGN OF A PDS In general, we can distinguish among three major steps or phases during the developmerit and verification of modular programs: editing a single module, linking several modules into an executable program, and executing a (possibility incomplete) program; the related activities of testing and debugging are included in the last phase. Corresponding to these activities, three major subsystems can be recognized in a PDS---an editor-parser, a linker, an executor-interpreter. The interaction between the user and the system (dialogue, recovery, transition from one phase to the other) is handled by a monitor, whose task is to discipline the programmer's work. We shall discuss this later. A data base, though not directly involved in the programming activity, is also useful. Since programs are built from separate modules a data base manager is needed to store different versions of both source and compiled modules. Rather than relying upon the standard file system (or data-base management system) of the running machine, a tailored data-base manager provides the necessary bookkeeping facilities, some of which are peculiar to a PDS, such as keeping track of the programruing sessions and organizing successive versions in a partial order by means of a version tree, making it easier to backtrack to older versions. Finally, a set of tools, such as tracers, profilers, cross-rderence generators, can give valuable help during program debugging and optimization. Implementation of these tools, however, can be delayed until the other parts are working; then their desired features are more evident. The requirements the first three subsystems should satisfy, and the criteria that have influenced the choices we made in our system are discussed below. The simple module shown in Fig. 3 is used as an underlying example for this discussion. This module may represent a first step of a step-wise refinement process of a table-handler program. 3.1. The editing phase While creating a module like the one in Fig. 3, the system must check its syntactic correctness and its semantic consistency (in the sense of type declarations) both with respect to the local environment and to the inherited one. If a standard editor provided by the system is used, then syntactic and semantic correctness of the module can be checked in a separate parsing step. However, on-line verification of programs can also be obtained, if an incremental parser [14, 15] is available, in order to adjust the parse-tree of a module without reanalyzing the text corn* Of course, the module may still contain local procedures or functions.

S I M P L E : A program development system

107

nodule TItST

requ~rs8

procedure 8ors ( v e t t n t q s r

mete);

procedure update (vat tntegm: s e t s ; l_~s prolrtm

tntqer

coast type

n " 10; ~udu

tritest);

moss .handler ( i n p u t , output);

- l..n;

lnteSer s e t s - record card : t n d u

{cardtmkLity of s a t } ;

cemtenta : atroy [ t a d u ]

off tntege~

end; v_~_~

4ntSOt : ~attegmr sets; uociLfle: : ~ t e S e z ;

{ i f oesative tl~m deXete L( p o s i t i v e Sham add i f zero then end of operettons}

£ : lntqer; beg 4n

toed (iJttset,cat~l)

{4nitla.1 cm~l:l~tlity};

fo_...rr I : - I to S t r e e t . card do r m l d (intmet. contamt8 [ 1 l ) ;

sort (1oCtet) ; read ( n o d t f t e r ) ; v h t l s a o d J / i e : # 0 do

bes1n update ( t o t t e r ,

modl.fter);

read ( n o d ~ Let) end; fo.__rr i : - 1 t o

Lncoct . card do

w r i t e (:Uatsot.contents I l l ) end end nodule Fig. 3. Table handling module.

pletely after a modification is performed. In our system we have chosen "to separate editing and parsing in an initial version and delayed the use of an incremental parser to a subsequent version. When an error is detected, an appropriate message must be sent to the user's terminal and a correction requested. Recovery procedures can be avoided, since errors are corrected on-line by the user himself. The presence of declarations for external objects assures that programs can be developed both top-down and bottom-up, guaranteeing the consistency of each level without the need for fictitious stubs or drivers [10l. Besides consistency checking it is the editor-parser's task to translate a single module into a suitable internal form. That task will be discussed in Section 4. 3.2. The linking phase During this phase several modules are combined to form a program. Not all of them need to be specified, nor implemented as stubs. In the example of Fig. 3 one could code the main program and, as a separate module, the procedure sort, yet leave the procedure update undefined. The linkcr has two tasks: the usual binding between internal and external references, and verifying the congruence of interfaces among modules. During this verification activity, the linker and user interact to confirm the resolutions adopted for bindings. Diagnostic messages must be issued whenever inconsistencies between local and global names, or undeclared external objects are detected. As noted before, the linked program can still be incomplete. Unspecified external procedures are

108

AUGUSTOCELENTANOet u/.

start~editing ~editing

Iinking~inklngI 1 ing )linkin g ( execution

ecution J ~exresuming

execution

C~ edi tin g

suspension for

error;

simulation

suspension for

/

incompleteness

LC

) edi

ting

execution

linking . ~ v ~

rt linking =

ting

Fig, 4. Activities supported by the PDS.

likely to be present in the early stages of a top-down development, while unresolved global variables are more likely to appear during a bottom-up development. In such cases, the user can direct the system to disregard a reported incompleteness. Discussion of the relation between the internal representation of modules and the linker activity is deferred to Section 4. 3.3. The execution phase

During program development, the purpose of the program execution is to test the program. Execution should be performed both at the single module level and at the level of a collection of linked modules in a way that interacts with the user as clearly as possible. Interaction should be foreseen whenever the execution is suspended, either because an error (such as division by zero, array bounds exceeded, etc.) is discovered by the interpreter, or because an unspecified object (global variable, external procedure) must be accessed*. Whenever an error or an access to an unspecified object occurs, the user should be involved in a recovering phase. A recovery action consists of identifying the origin of the suspension, removing the cause and resuming the execution. The first two steps are the user's responsibility, possibly with suitable help from the system. In the third step, if a suspension occurs because of an error, execution can be restarted or resumed from a safe state, after the error is corrected, but only if the executor has the capability of saving and restoring execution states. In the case of suspension on accessing an unspecified object, execution can be resumed from the point where the interruption occurred, according to a procedure described later in this section. * Strictly speaking, both of these are errors. However. we distinguish between an unintended error, such as array bounds exceeded, and an (intentionally) missing specification. As is shown later, the response of the system is different in the two cases.

S I M P L E : A program development system

109

Because the user should not be allowed to switch freeiy fr0m one activity to another, the system should impose a discipline on the sequence of operations during program development. Figure 4 shows a definition of the allowed transistions among the activities, as they are controlled by the monitor. After each editing session (module creation, successive refinements, or error correction), a call to the linker is required before starting or resuming the execution, even for a program composed of a single module. The dialogue with the linker is essential to confirm that if a user leaves an object unspecified it is deliberate. On execution suspension because of an error trapped by the interpreter, the system enters a state in which the user can examine the values of variables. The ability to directly alter these values, which is provided by many on-line debugging systems, is to be avoided here; it would allow the user to simulate corrections before fixing and removing the bugs, encouraging incoherent debugging. In our case the user is only allowed to correct the code of the procedure, and to restart the execution either from scratch or from a suitably saved safe state (e.g. the first activation of the now corrected procedure). Suspensions due to access to an unspecified object are handled differently for procedures and global variables. For a procedure not yet defined either on-line refinement can take place (editing and checking the procedure, linking, and resuming the execution), or the user can simulate Execution ,suspended at l i n e 20 because of c811 to u,..nspeci f led procedure : update

~tntStt~

D.o you want t o d e f i n e

n~l, i f l e r ~

it?

NO

Do you want t o s~Lmulate i t ? YES

Do you need s l o b a l var4sblesT NO

Psrsmeter v a l u e s are: J~tset.csrd - $

,./~tset.c~.t~t.

(Z) - Z_o

ln__tspt.eontsnts [2] : SO

l n t s e t . c o n t e n t s _ [10) - undefined uedlfleg -

-80

Give output v a l u e s : ~ntset.card = 4 lntset.contents

[ 1 ) - JANE

Do You trent to remme the ~ e ~ , t i o n ~

YES Execution resulted 8.t ~lne 21 : read ( n o d i f i e r ) ; Fig. 5. Dialogue for simulating an undefined procedure. Underlined messages are output by the

system.

I 10

AUGUSTO CELENTANOe t al.

the behavior of the undefined procedure. In the first case (on-line refinement) the procedure is now defined, and no suspension will occur for further accesses. In the second case (simulation) the precedure is still undefined, and a subsequent attempt to call it will cause another suspension. In the case of simulation, a reasonable discipline of memory access could consist of permitting assignment of values only to parameters passed by reference and modification of the global variables visible at the moment of the call. This practice, an example of which is illustrated by the dialogue in Fig. 5, allows the user to control the degree of interaction between the coded program and the simulated stubs. Since the user interaction is confined to the unspecified part, the program state must not be saved, and the execution can be resumed from the instruction following the call of the missing procedure. Access to an undefined global variable is most likely to occur during bottom-up development. Unresolved global variables are collected by the linker and allocated in a static area at the bottom of the execution stack, since they constitute a permanent environment during the execution. Specification consists of assigning initial values to such variables, and this assignment is required only at the first access to them. 4. IMPLEMENTATION CRITERIA A description of the implementation of a PDS is contained in full detail in [13]. In this section we are concerned with only two topics: the choice of the internal representation of modules and the choice of the running machine.

4.1. Internal representation The study of internal representation of programs during translation has traditionally focused the attention on batch environments. The main motivation for introducing intermediate languages is to break the compilation process into neatly separated steps, to reduce the complexity of the translation, to easily perform optimization, to isolate machine dependencies to obtain portability. In an interactive program development system, such as the one described here, the development process is intrinsically split into steps, some of which (e.g., the editingparsing step) can naturally support some translation. In a PDS the choice of the intermediate representation is not dictated by the need of an optimizing translation. This goal is not relevant during program construction and validation. In fact, the PDS is not required to run programs with maximum efficiency*. Its function is to assist the programmer during the design, coding and testing activities. Issues concerning efficient execution of the program are thus delayed to the final compilation, after the product has been thoroughly validated by the PDS. Nor is the choice dictated by the need of retargeting the object code. In fact the only portability issue which might be relevant concerns the whole programming system--(editor-parser, linker, interpreter, etc.). The exigence of exploiting the capabilities of peripheral devices to implement a dialogue manager which is satisfactory for the user, as well as the need for an efficient data-base manager, inhibits system portability at the highest degree. However, to promote portability, most of our system has been coded in FORTRAN and macro facilities have been used extensively in assembler routines. In conclusion, in a PDS the choice of the intermediate representation is mainly affected by the need of optimizing the user-system interaction to the highest degree. This interaction must be done in terms of the source text during all the development phases. Therefore, it seems desirable to keep the level of the internal form as high as possible, yet preserving the possibility of interpreting it in a natural way, and to maintain a full description of the used objects (variables and procedures). For these reasons we have chosen to use the pair (symbol table, syntax tree) as the internal representation of a module, as shown in Fig. 6. * Of course, the delays in systemresponse during the dialogue should be within acccptablelimits to make the system practically usable.

111

SIMPLE: A program development system

procedure body

V1 OPERATORTABLE

while statement

J

: expression

SYMBOL TABLE II

I

var

v~'r

Fig. 6. Internal representation for a module including the statement while a > b do.

The syntax tree and the symbol table are constructed by the editor-parser using an LL,LR mixed technique for syntax analysis. The syntax tree contains as terminal symbols only references to the operator and symbol tables. The keywords are not necessary during the execution phase, and are easily derived from the nonterminal nodes defining the rules used to construct the tree. One tree exists for each procedure defined in a module. The trees are linked by the symbol table which, among the description of all the declared objects, contains a list of the defined procedures with their most significant attributes; among them a pointer to the corresponding syntactic tree. When several modules are later connected at link time, only the symbol tables are affected. Figure 7, displays global and local objects (up and down the double line, respectively) before linking, and resolved and unresolved objects (open and hatched parts, respectively) after linking,. Since the linker fills the symbol tables with the addresses for global variables, only the symbol table and syntax tree of the currently executed module (and, of course, the execution stack) need to be present in memory. The symbol tables and syntax trees of other modules can thus be kept on secondary storage, reducing the main storage requirements of the PDS.

112

AUGUSTOCELENTANOeta[.

(2

?,

Fig. 7. Link a(~(?))~

4.2. Influence of the host machine on the PDS structure We are implementing our PDS SIMPLE on a PDPll/34, under RSX-I1M operating system; the output programs, processed into standard Pascal-S form, are compiled and run on a Univac 1100/80. The limited memory size of the PDP 11/34 (host machine) causes some problems. An entire non-trivial PDS cannot be contained in memory all at once, even if the host machine is dedicated. As a consequence, the subsystems must be overlayed during a programming session, thus increasing processing time. The internal representation for modules also requires large amounts of memory. Therefore the entire program might not be resident in memory, but might be swapped in and out one module at a time. An example of the critical consequences of this limitation follows. Suppose that a set of modules is to be linked into a program and an error is found due to the inconsistency of the declarations of a variable shared between two modules. The user decides to correct the error by changing the declaration in the module where the variable is local. As this is an editing operation and only the linker resides in memory beside the modules, the linker is swapped out and the editor-parser swapped in. After the error correction, linker and editor-parser are exchanged and linking is restarted from scratch. To avoid these time consuming operations, the linker subsystem could be provided with a limited editing capability, restricted to corrections affecting only the symbol table, such as the insertion of a new local declaration. Of course, the appropriate corrections on the text must also be performed, but possibly at a less critical time. 5. FURTHER EXTENSIONS AND STATE OF THE IMPLEMENTATION The introduction stated that a P D S should allow the construction and use of abstract

data types. The scheme adopted in our system is based on the partial specification of the objects imported by a module [16]. Consider the simple example of a module operating on queues of integers. Such a module could be unaware of the implementation of the queue. Its requires part could be the following: requires type queue-int --- unknown; procedure enquene (var queue-int; integer)

SIMPLE: A program development system

113

Inside the module, instances of type queue-int ctift ~ created arid used, but the typechecking mechanism does not permit direct access to the representation, since this information will be known only after linking the module with other modules implementing the abstraction queue-int. This extension obviously requires a more elaborate linking mechanism than the one described before; in fact the offsets of local variables of unspecified type must be envaluated at link time [-13, 16]. Presently, the three basic subsystems (editor-parser, linker, interpreter) run as separate programs called via job control language commands and the interaction is allowed only within a single subsystem. A full interaction between the subsystems according to the finite-state automaton of Fig. 4 as well as the final translation of the collection of modules into a Pascal program to be run on the object computer is now under development. SUMMARY

The programming activity may receive great benefits from a complete Program Development System, which assists the user during all the phases of program construction and verification. The system should encourage, but also enforce, a disciplined programming activity, either by top-down refinements and/or bottom-up aggregation of modules, or by describing the programs by abstraction levels. Modular programming, in which several users access program libraries, should be also encouraged. The programmer's confidence in the correctness and reliability of his programs can be enhanced by high quality diagnostics and recovery features both at compile-time (by maximizing static checking) and at run-time (by carefully reporting errors, and possibly allowing the execution to be resumed in a safe state). The support provided should range over all development phases, from editing a single module up to executing and testing a (possibly incomplete) program. The desired features require the system to be interactive, but should also impose a strong discipline on the user-system dialogue, to avoid too much freedom in accessing and modifying the program or its execution state. These features have been included in a PDS, called SIMPLE, actually under development. The SIMPLE system adopts Pascal-S as programming language. The language has been enriched with constructs for separate compilation and modular programming, but a simple text processor can transform a program written in this enriched Pascal into standard Pascal-S. An editor-parser allows creation and correction of modules. Static checking is accompfished through an interface declaration stating assumptions about imported objects (types, variables, and procedures). A linker assembles a set of modules into a program, verifying the congruence among interfaces according to the scope rules of the language. A high level interpreter provides for the execution phase, allowing incompletely worked our programs to be executed with suitable help from the user when unspecified objects (global variables or procedures) are accessed. In the paper both general requirements about program development systems and the main features of the SIMPLE system are discussed: the main aspects of the implementation and suggested extensions are also addressed. Acknowledoem~ts--We would like to acknowledge the enthusiastic support of M. Paganini, A. Tecchio and E.

Viscuso, who have been responsible for the implementation of the SIMPLE program development system. We would also like to thank M. Jazayeri and the referee for many useful comments that helped us improve the style of this paper. Additional style improvements were suggested by D. Ledford in the final editing stage.

REFERENCES

1. D. O. Bobrow, Requirementsof advancedprogrammingsystemsfor list processing.BBN Report No 2339 (1972). 2. T. E. Cheatham,Somenew directionsin softwaredevelopmenttools. Proc. AICA 77, 3-29 (1977). 3. B. WegbreiL The ECL programming system. Pro