Download View/Open - Calhoun: The NPS
Transcript
NAVA;. MOiTTiiJ£Ui i . -^ 3 SCHOOL i A 93943-5002 LPOS MOJIBEBY, NAVAL moittb; NAVAL POSTGRADUATE SCHOOL Monterey, California 7w^ ^ "7. f DESIGN AND IMPLEMENTATION OF AN EXPERT USER INTERFACE FOR THE COMPUTER AIDED PROTOTYPING SYSTEM by Henry G. Raum 9 » B December 1988 Thesis Advisor: Approved Luqi for public release; distribution is unlimited T2422RO iclassified Cla?sificaiion of this pace :urit> REPORT DOCUMENTATION PAGE Report Security Classification Unclassified 1 Secunt\ Classification Authoni\ Approved Performing Organization Report Number(s) Name Address (city, state, onterev, Name CA (If Applicable) Address (city, state, 7b Address Monterey, 8b Office Symbol (city, stale, CA Personal Author(s) Procurement Instrument Identification Number 9 Source of Funding Numbers 1 aster's Proieci No | Task No | Worx Design and Implementation of an Expert User Interface for the 1- nn Access.or \c Computer Henrv G. Raum 1 Thesis 3b Time Covered 14 Dale of Report (year, month.day) 1 5 Page Count December 1988 To From Supplementary Notation The views expressed in this thesis are those 92 of the author and do not reflect the official or position of the Department of Defense or the U.S. Government. )licy Cosati Codes Group Id | System T>pe of Report a and ZIP code) 93943-5000 Program Elemor. Number ided Prototyping unlimited. Applicable) and ZIP code) Title (Include Security Classification) is Name of Monitoring Organization Naval Postgraduate School and ZIP code) (If for public release; distribution 7a 37 93943-5000 of Funding/Spwnsoring Organization Markings Monitoring Organization Report Number(s) 5 6b Office Symbol of Performing Organization Postgraduate School Restrictive Distribution Availability of Report 3 Declassification/DowTigrading Schedule ival h 1 Subgroup Abstract (corainue on reverse Subject Terms (continue on reverse 8 if necessary and identify by block number) Rapid Prototyping, Computer Aided Software Engineering (CASE). Ada, Real-Time, Embedded Systems User if Interface, Expert System, necessary and ideruify by block number This thesis builds on previous work done in the development of the Computer Aided Protot>'ping System -APS) and the Prototype System Description Language (PSDL). The increases in the size and complexity of iftware projects have caused system designers to reevaluate traditional software engineering methodologies, apid prototyping is a method that allows the validation of system requirements and design early in the ;veIopment cycle. The need for this type of tool is particularly critical in the development of real-time embedded stems. CAPS is one such system. CAPS is a complex system that consists of many individual software tools. An expert user interface that tides the software designers through the development and execution of a prototype is described in this thesis. Distribution/Availability of Abstract ' |X| a ) unclassLfied/unlimiied Name Luqi FORM I same as 2 repwn I I DTIC users of Responsible Individual 1473, 84 MAR 1 Abstract Security Classification Unclassified 22b Telephone (Include Area code) (408) 646-2735 83 APR edition may be used until exhausted All other editions are obsolete 22c Office SymbolT. 52Lq security classification of this page Unclassified Approved for public release; distribution is unlimited DESIGN AND IMPLEMENTATION OF AN EXPERT USER INTERFACE FOR THE COMPUTER AIDED PROTOTYPING SYSTEM by Henry G./Raum Captain, United States Marine Corps B.S., United States Naval Academy, 1980 Submitted in partial fulfillment of the requirements for the degree of MASTER OF SCIENCE IN COMPUTER SCIENCE from the NAVAL POSTGRADUATE SCHOOL December 1988 ABSTRACT This thesis builds on previous work done in the development of the Computer Aided Prototyping System (CAPS) and the Prototype System Description Language (PSDL). The increases system designers Rapid prototyping and design early in the size and complexity of software projects have caused to reevaluate traditional is a method in the software engineering methodologies. that allows the validation of development cycle. particularly critical in the The need system requirements for this type of tool is CAPS is development of real-time embedded systems. one such system. CAPS is a complex system that consists of many individual software tools. An expert user interface that guides the software designers through the development and execution of a prototype is described in this thesis. Ill 1 » '> TABLE OF CONTENTS I. INTRODUCTION A. 1 DESCRIPTION OF SOFTWARE ENGINEERING METHODOLOGIES II. 2 1. Traditional Software Engineering Paradigm 2 2. Prototyping in Software Engineering 3 B. OBJECTIVES 4 C. ORGANIZATION 5 BACKGROUND A. DESCRIPTION OF CAPS 1. 2. 3. B. 6 Architecture of 6 CAPS 6 Module a. The User b. The Software Base and Rewrite System 7 c. The Execution Support System 8 Description of Interface PSDL Elements of b. Example of PSDL The CAPS 9 PSDL a. 6 9 10 14 Process a. Prototype Design 15 b. Prototype Construction 15 c. Prototype Execution 17 d. Prototype Debugging and Modification 19 PRINCIPLES OF THE USER INTERFACE 20 Expert System and Sequence Control 20 1. IV III. 2. DataEntr)' 22 3. Data Entry Methods 22 DESIGN OF THE USER INTERFACE 24 A. BOURNE SHELL SCRIPTS AND UNIX OPERATING SYSTEM 24 B. PROTOTYPE CONSTRUCTION 25 C. D. E. 1. The Design Database 25 2. The Graphic Editor 11 3. The Syntax Directed Editor 27 4. The Software Base 27 5. The User Interface 28 6. Sequence Control 29 PROTOTYPE EXECUTION 31 1. The Translator 32 2. The 32 3. The Dynamic Scheduler 33 4. Sequence Control 33 Static Scheduler PROTOTYPE DEBUGGING AND MODIHCATION 34 1. The Debugger 34 2. Modifying the Prototypes 34 a. Modifying an Operator 35 b. Consistency of Views 36 TOP LEVEL USERS MANUAL 36 1. The Caps Command 36 2. The Construct Command 37 3. The Execute Command 37 . The Modify Command 4. EVOLUTION OF THE USER INTERFACE 39 IMPLEMENTATION OF THE USER INTERFACE 40 F. IV. A. THE LINK STATEMENT ANALYZER 40 B. SEQUENCE CONTROL IN THE USER INTERFACE 43 C. D. V. 38 1 Implementation of the Construction Subsystem 43 2. Implementation of the Execution Support System 45 3. Implementation of Debugging and Modification 46 EXAMPLE BOURNE SHELL SCRIPTS 1. The Construct 2. The Graphic Editor 47 47 Script Script FUTURE IMPLEMENTATION CONCLUSIONS 49 51 52 A. FEASIBILITY ISSUES 52 B. BEN^RTS OF THE STUDY 52 C. RECOMMENDATIONS 53 L Primary Data Entry 53 2. Prototype Modification 53 3. Execution Monitoring 54 D. APPLICATION OF CAPS IN THE DEPARTMENT OF DEFENSE AND THE DEPARTMENT OF THE NAVY ^4 GRAMMAR 56 APPENDIX A. PSDL APPENDIX B. BRAIN TUMOR TREATMENT SYSTEM EXAMPLE 59 APPENDIX C. PASCAL PROGRAM NODES.P 62 APPENDIX D. INPUT AND OUTPUT LINK ANALYZER 71 VI APPENDIX E. BOURNE SHELL SCRIPTS 73 REFERENCES 75 BIBLIOGRAPHY 77 INITIAL DISTRIBUTION LIST 78 Vll LIST OF FIGURES 4 Figure 1. The Prototyping Method Figure 2. The Architecture of Figure 3. Graphic Decomposition 10 Figure 4. PSDL Operator Specification 11 Figure 5. PSDL Operator Implementation 12 Figure 6. PSDL Data Type Figure 7. PSDL Figure 8. Execution Support System 18 Figure 9. Sequence Control Dialogs 21 Figure 10. Operator Decomposition 30 Figure 11. Conceptual Figure 12. Declaration Section of Nodes.p 41 Figure 13. Input and Output of Nodes.p 42 Figure 14. Construct Script 48 Figure 15. Graphical Editor Script 50 CAPS Specification and Implementation 14 17 Construction DDB 7 Structure vm 32 LIST OF ABBREVIATIONS CAPS Computer Aided Prototyping System DDB DFD Design Database DOD DON Department of Defense DS Dynamic Scheduler ESS Execution Suppx)rt System GE Graphic Editor MCP MET MRT Minimum Calling Period Maximum Execution Time Maximum Response Time PSDL Prototype System Description Language SB Software Base SDE TR Syntax Directed Editor Translator UI User Interface Data Flow Diagram Department of the Navy IX NAVA moitt: I. Over INTRODUCTION the last twenty years, exceeded those in software is computer hardware have in development. This "software improved performance of systems problem advancements is expected [Ref. 7:p. that the users of the software crisis" 11]. far must be resolved The most if significant systems often do not understand software engineering and the software engineers do not understand the needs of the users. As a result, poor requirements analysis often leads traditional software engineering coding is paradigm complete. This results in to an improper design. testing of the much wasted system effort as is In the done only after improper specifications are coded. An alternate approach to software engineering model of the eventual program is is started. One system prototyping. In this quickly constructed and tested. evaluate the design of the system and coding is make modifications, if The goal is the Ada®^ program that performing correctly. Ada is Computer This system constructs a prototype from System Description Language (PSDL) and generates an executable model of the real-time system. This model Office is to necessary, before the implements the prototyping methodology that specifications described in the Prototyping ^ a [Ref. 2:p. 69] Aided Prototyping System (CAPS). an method can be executed and modified until the is actually prototype is [Ref. 3] a registered trademark of the U.S. Government, Ada Joint Program CAPS Defense that all that applicable to the Department of the is (DOD) because generates an it embedded systems in DOD be Ada® Navy (DON) and Department prototype. implemented in demonstrates use of the language constructs makes The users of this system may not be familiar with even have any software engineering expertise. For With the requirement Ada®, an Ada® prototype CAPS more attractive. PSDL or CAPS this reason, interface that guides the user through the production of may and not an intelligent user of the prototype is required. This thesis will describe the design and implementation of such a user interface. The remainder of this chapter will describe the traditional and rapid protot>'ping software engineering methods and a description of the elements and processes of A. the CAPS CAPS system. This will include and an overview of PSDL. DESCRIPTION OF SOFTWARE ENGINEERING METHODOLOGIES. 1. Traditional Software Engineering Paradigm The model", is traditional software engineering a systematic, paradigm, often called the "waterfall sequential approach [Ref. 2:p. 13]. This model begins with requirements analysis and continues with functional specification, design, coding and testing. environment it Requirements analysis defines the scope of the system, and the will operate in, while the functional specification describes interfaces to the proposed system and the functions of that system. includes the stage decomposition and detailed design. The data structures, software architecture and procedural details are key issues at this stage. where the designed system a high level The design is written into a programming language. The coding stage is form usable by the computer, normally Finally, testing is done. These tests not only show that the program meets and specifications, but determines the requirements these requirements produce the desired results. The much fact that [Ref. 4] coding and testing occurs so criticism of the "waterfall model". late in the difficult for the It is process has brought customer to furnish complete requirements before the process begins. In large software systems can lead to a disaster if a discovered until testing. 2. major oversight in the requirement analysis phase this is not [Ref. 2:p. 15] Prototyping in Software Engineering. In response to the problems in the "waterfall model" that is well suited to the iterative nature of the When software systems. new approach a software engineering, called prototyping, has been devised. method if Prototyping is to a development of many the customers requirements cannot be completely determined or there are questions about the suitability of proposed algorithims or what the human interface should be, prototyping allows a can be tested and modified. model After testing the prototype, a new to be built which set of improved specifications can be used in the coding phase. Figure requirements is 1 illustrates how, in this method, testing and refinement of done before the actual product cost savings can be realized because code is is engineered. Significant time and not being written for incomplete and erroneous specifications. The complex and uncertain timing requirements of realtime embedded systems makes them good candidates for prototyping. P^ef. 2] The problem with prototyping is the cost of developing the prototype itself. Paper prototypes are easy to construct, but do not Working prototypes can show the system. In the show the dynamic nature of the system. the feel of the program, but are limited to a subset of Computer Aided Prototyping System the entire system is modeled. The time required to build this prototype is greatly use of syntax directed and graphic editors, reusable contained execution and debugging system. CAPS Ada® modules system, executing that prototype and measuring software engineering effort, CAPS falls and a self- attempts to validate the timing embedded systems by constructing aspects of real-time reduced through the its a prototype of the entire As performance. part of the between the requirements analysis and coding phases. Requirements Analysis i I ' \ Develop Prototype 1 ' Test and Evaluation of Prototype ' 1 Engineer Product Figure B. 1. The Prototyping Method OBJECTIVES This thesis describes the design and implementation of an expert user interface for CAPS. The primary objective is to define the proper use of database, graphic, and operating systems technology in the design of the interface. Secondly, this thesis will explore the use of expert can free the user from many system technology to produce an interface that of the details of the system operation. In this way, an error free prototype can be produced quickly and easily. C. ORGANIZATION Chapter CAPS, background research and includes a description of System Description Language (PSDL) and the principles of outlines the II the Prototype the user interface in software systems. Chapter III describes a design for the user interface to include the interfaces between CAPS and the user as well as those between the various elements of the system. This chapter includes a users manual and recommendations for future implementation. Chapter IV outlines the implementation of the design, both what has been done and what is recommended Chapter V for future implementation. contains conclusions and recommendations of this research. BACKGROUND II. The Computer Aided Prototyping System tools that enable the user to A. a complex collection of software produce executable prototypes of large real-time embedded systems. This chapter detail. is outlines the components of CAPS and PSDL in Finally the principles of the user interface are investigated. DESCRIPTION OF CAPS 1. Architecture of CAPS CAPS consists of many software tools that each have a part in the production of the prototype. The position of each component in the overall system is illustrated in Figure 2. a. A brief description of the components follows. The User Interface Module. This module consists of two editors, a syntax directed editor and a graphical editor. become Together these editors produce the PSDL program that will the prototype. (1) The Syntax Directed Editor and proper syntax of PSDL. It is an editor that knows the key words insures grammatically correct PSDL as it guides the user through the production of the program. (2) of The Graphic Editor PSDL components is an editor that describes the decomposition by the use of enhanced data flow diagrams. It is in these diagrams that the user "creates" the program. (3) The Design Database is the structure that stores the elements of the system under construction. This database is organized to handle the hierarchical nature of the top-down development of the system. abihty to keep a history of the prototype The design database when changes are Software Rewrite Base System made. [Ref. also has the 4:p. 29] 1 User Interface Design Syntax Data Directed Base Graphic Editor Editor T Execution Support System Translator Dynamic Debugger Static Scheduler Scheduler Figure 2. Architecture of Figure b. 2. Caps The Architecture of CAPS The Software Base and Rewrite System Together the software base and rewrite system give retrieve reusable Ada® components CAPS for construction of the prototype. its ability to (1) The Rewrite System. The purpose of provide a method for mapping This all the rewrite system equivalent specifications to one common is to form. called the normalized form. is (2) The software base is a database of reusable PSDL are indexed and searched for based on Ada® components specifications. Ada® module that fulfills the desired function. prototype there is that This will provide an In the production of a rapid no time for browsing a software library by name, as in a yellow pages type of index. [Ref. 5:pp. 68-69] c. The Execution Support System The Execution Support System (ESS) scheduler, a dynamic scheduler and a debugger. CAPS PSDL is to produce a program PSDL consists of a translator, a static While the purpose of the rest of program, the function of the into a executable Ada® ESS is to translate the prototype that tests the real-time aspects of the designed system. (1) The Translator. translator starts with the retrieved in the software base and adds to PSDL to produce an (2) critical Ada® module The that in the control constants described in can be scheduled. Static Scheduler. components together them Ada® components The static scheduler links all of the time an executable schedule that can demonstrate the real-time aspects of the system. (3) time critical The Dynamic Scheduler. The dynamic scheduler adds components (4) to the system to produce an overall schedule. The Debugger. The debugger provides an user and the executing prototype. the non- The user may be asked interface between the to correct a problem the prototype or be presented with statistics on the operation of the prototype. in Description of 2. PSDL The Prototype System Description Language language that this used at the Ada® an executable prototyping design level. The user can define the specifications in language and these specifications are used reusable then is is components. If a suitable module is not found the decomposed by drawing an enhanced data flow diagram level operators, the data streams control constraints. (1) some operator that includes is lower between these operators, as well as timing and PSDL Operators are the basic component in Operators. can represent functions or arrival of PSDL [Ref. 5:p. 68] Elements of a. software base of to search the state PSDL. They machines. These operators can be triggered by the input (sporadic) or at fixed time intervals (periodic). When triggered the operator will fire (produce output) based on input values and the value of the internal state variable in of the case the state machine. [Ref. 6:pp. 12-13] Operators are called atomic base, otherwise they are called composite and diagram. if they can be found in the software must be decomposed with a data flow Figure 3 shows such a decomposition. Data streams respective input and output of the composite operator and B, and C are newly created operators that may be s is w and z are the the state variable. A, atomic or composite themselves. [Ref. 5] (2) Data Streams. A data stream represents the flow of data between two operators. This communication can be sampled stream. A data flow a data flow stream is never in the form of a data flow stream or stream can be thought of as a lost and is always acted on FIFO in the queue. In this a way order of arrival. A sampled stream can be thought of many as a single memory cell. This data can be used times or written over before use, depending on the rate of its input and use. [Ref. 3] Figure Graphic Decomposition 3. Data flow streams must be used when each piece of data represents a unique transaction. in a current w,x,y,and z, A sampled stream can simulate a sensor parameter such as temperature. with x and y being the (3) new that is only interested In Figure 3, the data streams are data streams created in the decomposition. Timing and Control Constraints. The real-time nature of prototypes requires timing and non-procedural control constraints in time in critical which operator has a that operator Maximum Execution Time, which can complete execution after it fires. is the the PSDL. Each maximum time Control Constraints give conditional requirements on the firing of operators. b. Example of PSDL. To illustrate the system that was defined PSDL program the example of the Hyperthermia in the conceptual research for This example illustrates a CAPS [Ref. 3] will be used. dynamic real-time environment that is easy to understand. One approach combating cancer is to destroy tumorous cells One way to do this is with a hyperthermia system, which uses a microwave generator connected to a fine tuner and matching to selectively with heat. control system to produce and deliver controlled, local heating directly to the 10 tumors. A computerized control system adjusts power output automatically to maintain the temperature in accordance with the treatment plan. The hyperthermia system has four subsystems: a computer system, an operator's panel, a microwave generator, and a temperature sensor. The subsystem is the software that receives input from the temperature sensor and produces control commands to operate the whole system. The software controls the rest of the system, which is typical of real-time critical embedded systems. (1) in Figure list, 4. a state [Ref. 4:p. 30] PSDL Specification. The operator The Specification includes list (if operator is is found OPERATOR this the operator PSDL name, an input list, as shown an output a state machine), optional exception declarations timing information. This specification match described in is composite operator is is used to search the software base. decomposed in the implementation and If no part. Brain_tumor_treatment_system SPECIFICATION INPUT patient_chart: treatment_switch : medical_history, boolean OUTPUT treatment_finished: boolean STATES temperature: real INITIALLY 37.0 DESCRIPTION {This is an English description of the operator specificatioa} ENTD Figure 4. PSDL Operator Specification Timing constraints may be added to a specification in the following ways: • Maximum • Maximum Response Time (MRT) • Minimum Execution Time (MET) which places a maximum time on the execution of an operator from initiation to completion. has slightly different meanings for sporadic and periodic operators. It is the time between the start of the period and the moment of the last output of an operator for periodic operators and is the time between arrival of new data and the moment of output for sporadic operators. (MCP) is required for any sporadic operator with the minimum time from the arrival of one set of data to the arrival of the next. [Ref. 6:pp. 20-21] an Calling Period MRT and is 11 PSDL (2) Implementation. The implementation part of consists of the graph (data flow diagram), a constraints for the newly created operators. Figure 3 would appear in PSDL list of new PSDL data streams and control The data flow diagram shown as the link statements shown after the in keyword GRAPH in Figure 5. A link statement is of the form: data_stream.from_operator:met->to_operator [Ref. 7:p. 26] The from . operator, in the case of an input, and the to operator, in the case of an output, will be represented by the keyword EXTERNAL. The maximum execution time of the operator, and the colon, are omitted for non-time critical operators. The Data Stream part lists the new internal data streams named in the graphical decomposition. IMPLEMENTATION GRAPH temperature.EXTERNAL -> hyperthermia_system patient_chart.EXTERNAL -> hyperthermia_system -> hyperthermia_system treatment_s witch. EXTERNAL treatment_power.hyperthermia_system -> simulated_patient treatment_fmished.hyperthermia_system -> EXTERNAL temperature. simulated_patient -> hyperthermia_system DATA STREAM treatment_power real : CONTROL CONSTRAINTS OPERATOR hyperthermia_system PERIOD 200 ms BY REQUIREMENTS OPERATOR simulated_patient PERIOD 200 ms DESCRIPTION {some shutdown text about it} END Figure 5. PSDL Operator The Implementation Constraint part of PSDL. These section Implementation is completed with the Control control constraints include data triggers, periods, conditionals, timers and exceptions. interconnections between operators. 12 This information is used to define The most common control method The period operator. shown is The data in the period and data trigger. Figure 5 and indicates the synchronous timing of the trigger examples of data triggers is is Two used to indicate control from arriving data. are: OPERATOR A TRIGGERED BY ALL x,y,z. OPERATOR B TRIGGERED BY SOME v,w. The by ALL inputs are present, while the by V or w trigger causes the operator to fire SOME trigger fires the operator when all three when any value of [Ref. 3:p. 17] arrives. Conditional Constraints add an IF predicate to the data trigger. This boolean condition must be satisfied before the operator will fire. Examples of the conditional constraint are: OPERATOR A TRIGGERED if b<10. OPERATOR X OUTPUT y if z: A reset, and its timer is critical. used as an internal state that can be started, stopped, current time read by the operator to allow that operator to do timing control if necessary. It is also possible to raise exceptions in exceptions can be user or system defined and are raised catastrophic conditions are encountered. handler at the The exception is its own PSDL. These when unusual or handled by an exception highest level of the program. Data Streams utilize the operator as implementation section as shown in Figure 6. operators needs to be discussed. 13 both its specification and Therefore, only the construction of TYPE medical_histor)' SPECIFICATION OPERATOR get_tumor_diameter SPECIFICATION INPUT patient_chart: medical_hi story, tumor_location: string OUTPUT diameter: real EXCEPTIONS no_tumor MAXIMUM EXECUTION TIME 5 ms DESCRIPTION {This is an English description of the operator} ENT) IMPLEMENTATION tuple[tumor_desc: map[from: string, to: real], ...] OPERATOR IMPLEMENTATION GRAPH patient_chart.EXTERNAL-->tuple.get_tumor_desc tumor_location.EXTERNAL-->map.fetch diameter.map.fetch:4ms-->EXTERNAL td.tuple.get_tumor_desc:lms-->map.fetch DATA STREAM td: tumor_desc CONTROL CONSTRAINTS OPERATOR map.fetch EXCEPTIONS no_tumor IF not(map.has(tumor_location, td)) END Figure 3. 6. PSDL Data Type Specification and Implementation The CAPS Process There are four major elements in the CAPS process: prototype design, construction, execution and debugging/modification. prototype design, actually takes place outside design a system, but rather to test The initial step, called CAPS. The purpose of CAPS is not to and validate that design. Construction takes place in the user interface portion of the system, while execution takes place in the 14 execution support system. Debugging and modification requires action in both the user interface and execution support systems. a. Prototype Design. The design of a decision as to what Then requirements the prototype starts with an analysis of the problem and part or parts of the proposed system are to be prototyped. for the prototype are generated. These requirements are usually written in English, but could be specified in a Example requirements given in more formal notation. English taken from the hyperthermia example are: Shutdown. Microwave power must drop to zero within 300 ms of turning off the treatment switch. Temperature Tolerance. After the system stabilizes, the temperature must be kept between 42.4°C and 42.6°C Maximum Temperature. The temperature must never exceed 42.6°C. Startup Time. The system must stabilize within 5 minutes of turning on the treatment switch. The system must shut down automatically when the temperature has been above 42.4°C for 45 minutes. [Ref. 3:pp. 28-29] Treatment Time. The requirements are refined by asking the customer questions determine exactly what the requirements mean and if they are complete. With the completion of the preliminary design, the construction of the prototype b. Prototype to may begin. Construction. Construction of the prototype involves the use of the syntax directed editor, graphic editor, design database, rewrite system, software base 15 and the sequence control of the and is CAPS user interface. This process is illustrated in Figure 7 described below. To start the system, the represents the entire prototype is PSDL produced specification of the operator that in the syntax directed editor. After this specification has been normalized in the rewrite system a search of the software Ada® modules base of reusable is This search by specifications performed. produces no match, one match, or many matches. In the case of a single match, Ada® component is used as the implementation part of the operator. match must be resolved and then the single resolved component there is no match, the operator is enhanced data flow diagram. creates children operators of the current operator. produced that frontier. operator At If the is is multiple used. When a candidate for decomposition. Decomposition of an operator takes place the production of the is A that in the graphic editor In this with diagram the editor In effect a multiway tree is rooted at the original operator and has atomic operators as operator is its a candidate for decomposition, but the designer feels the it may would be atomic with this too simple for further decomposition, this point, this operator implementation.The design database keeps track of be simply coded in Ada®. newly written code all as its the nodes created in the decomposition. The primary structure for the responsibility of this database PSDL components of each operator in a hierarchical nature of the prototype construction. 16 to provide a storage way that maintains the is Create Specification I Rewrite Specifications I Search Software Base many matches no match I one match Decompose? yes Resolve no 1 Decompose Code Component Operators Retrieve Component 1 ^' / / / ^' Create Insert New Nodes Implementation Figure The user tools in the system. moment and 7. PSDL Construction interface controls the flow of data and the use of the various This control includes calling the proper tool at any given the repetition of the constructive process until all leaf operators in the design database tree are atomic. c. Prototype Execution. Execution of the prototype occurs in the execution support system (ESS), through the use of the translator, static scheduler, 17 dynamic scheduler and the debugger as illustrated in Figure 8. The input to the ESS is the PSDL program that was previously constructed. PSDL Static Debugger Scheduler T Static coupled Schedule Ada modules Dynamic Scheduler T Dynamic Schedule i Compiler/Linker T Debugger Executable Ada code Figure The PSDL into Ada® first 8. Execution Support System component in the ESS is the translator, which translates source code. The atomic operators are tempered by the control constraints of the composite operators and executable 18 Ada® packages are produced. This collection of modules in the execution of the prototype. The Static is used by the static and dynamic schedulers [Ref. 8:pp. 7-8] Scheduler also utilizes components with real-time constraints after PSDL as input. schedules It all checking the compatibility of these timing constraints between operators. The Dynamic Scheduler combines the non-time critical components of the time critical static schedule and the prototype into a piece of executable code called the dynamic schedule. This schedule executed. This execution d. is is Ada® compiled, linked and finally the test of the prototype and the design it represents. Prototype Debugging and Modification. The debugging and modification phase of the CAPS process actually takes place over the entire system and utilizes all the various tools. takes place in two places, first at The debugging the time of the execution of the static scheduler, at which time problems with timing constraints that would prohibit the production of the static schedule are identified and corrected, and secondly, during the execution of the dynamic schedule. At that time problems with the dynamic execution of the prototype are determined. In order to resolve these problems, a modification user interface. is used in the This modification can go to any position in the defined prototype and modify specifications and control constraints. interpret mode The user interface must and make changes and, through the use of the design database, carry this change through the levels of decomposition. This could require new searches of the software base, deletion of existing operators or construction of any changes are made, the modified PSDL program must 19 new operators. be run through the If ESS done again. This process will be iteratively until the prototype performs as desired or demonstrates problems in original requirements. B. PRINCIPLES OF THE USER INTERFACE The user must do more than merely provide for data that the interface as CAPS, also not enough complex software engineering system, such interface of a entr>' and display. It is simply provide a loose collection of software tools, rather provide sequence control, user guidance and data protection as well. provides all A it must system that these functions and unites the tools into a single system can be said to provide a software engineering environment. Expert System and Sequence Control. 1. In order for software to provide all the functions of the user to interface, have to be system The it is system must rely on expert system technology. This expert system does not based used interface to in an Artificial Intelligence imply an ability to must be able language, rather the term expert guide the user through the desired processes. to interpret what the user is doing at any time and provide support. This expert system must communicate with the user to find out what they want intentions. to do at any moment when the system cannot be sure of the users This type of expert system is also referred to as "mutual consultation" [Ref. 9:p. 212]. While attempting to guide the user through a sequence of operations, important to remember to allow the user to remain in control. achieving this goal good to is to experienced user may One method allow the experienced user some flexibility of control. have an interface that it is of It is can guide the user through the system, but an regard such a system as "too restrictive". [Ref. 10:p. 48] 20 One is of the benefits of a system that requires few control actions by the user reduced memor>' load on the user. The user does not have do next if all possible uses. memory load on the user is to remember what Another way the system can perform that function. system can reduce the to apply all to that this expert known information to This frees the users from needing to remember what they have already done. Four methods of sequence control are given training requirements. A software engineering tool should limit the use of the dialogs that require high amounts of user training. graphics tool, but limiting the make in Figure 9 with their relative This can not be avoided in a number of commands the user needs to know can the system easier to use. In a software engineering tool the interface should allow the user to concentrate on the developing software, rather than the developmental tool. This will increase the users productivity. DIALOG TYPE REQUIRED USER TRAINING Question and answer Little/none Menu Selection Little/none Command Language High Graphic Interaction High Figure The expert 9. Sequence Control Dialogs interface will insure that the user order to produce the needed prototype component. must "know" all is placed in the proper tool in Additionally, this interface the aspects of the developing software, so that the consistency of data entered in the different tools can be maintained. 21 The syntax and semantics of PSDL are an important part of this intelligent interface. This enables the interface to insure a valid protot>pe. Data Entry. 2. Many entry. PSDL of the Once again same principles that applied to sequence control apply to data the system should try to limit the number of input actions required by the user and also reduce the memor>' load on the user. In order to provide the most efficient form of data entry, the interface designers should consider textual, system driven and graphical inputs. Regardless of the method, there are some underlying qualities that any interface should provide. Data should only be entered once and the system should be able to access this information wherever it is needed. The user should not be asked to reenter information that was already input. Feedback should be provided during data entry. This includes displaying keyed entries character by character and giving an indication of mouse-down and mouse-up events in a graphics tool. Data entry should be user paced. The system should not run away from a novice user, but at the same time it should be able to accommodate the speed of expert users. 3. Data Entry Methods. The interface. three data entry It is When methods described above When have a place in the important to choose the proper method for a particular task. a program is being developed the naming of elements and the description of arithmetic expressions are two tasks that input. all possible, this input should be 22 seem done with the best suited for textual aid of a syntax directed editor such as the Cornell Program Synthesizer. This system allows the user to enter information without the frustrating syntactic details normally encountered. This can be a tremendous help when of the programming language. Graphical data entry graphic technology form top faster it is is not ver}' familiar with the grammar [Ref. 11] a very important area. is With recent advances in possible for the user to enter information in a pictorial and more concisely than down refinement the user is possible in textual only environments. of a software system is a logical use of graphic editing. The The decomposition from one level into many lower level components can be easily represented by the human mind that people prefer pictures over entry is final method of data flow diagram. In general, words desirable for this purpose. The in a in a is 152] through the use of questions and response system driven interface. This system asks the user questions and takes different actions based on the response of the user. Although this it can be stated for describing structures, so graphical data [Ref. 12: p. interface it has its place in the user interface when method is the users cannot be given more restrictive, freedom to enter anything they want. At the cost of flexibility, the user can be guided to enter only information that is valid. User interface design is more than just providing a method information from user to machine and back. The overriding factor is to get the keeping the user in control and this control should only be limited in situations where possible errors would greatly degrade the system. 23 DESIGN OF THE USER INTERFACE. III. In Chapter II, CAPS was introduced and discussed as a group of individual In this chapter, the design of an interface that links these tools components. together into a single software engineering tool will be described. The design of the interface includes the specification of the inputs and outputs of the individual components as well as a complete description of the previously undefined design database. The interfaces involved in the the construction, execution and debugging/modification of the prototype will be described. introduction to the A. Bourne Shell Scripts of the However, a Unix^ operating system is brief necessary. BOURNE SHELL SCRIPTS AND UNIX OPERATING SYSTEM The Bourne Shell Script is a in a single file called a script. way to perform a The Bourne if-then-else logic, case statements, of Unix set commands contained Shell provides string-valued variables, and for and while loops. In short, all the constructs required to control the operation of the system are available. Within the shell, all Unix commands can be environment [Ref. many they 13]. utilized, thus providing a very powerful control The Unix System allows written in different languages. become executable Unix Writing the interface in the system components. An files Once and for a collection of different tools, the individual programs are compiled, their source is transparent to the system. Bourne Shell allowed it additional benefit of the to be on a higher level than the Unix system is the ability to communicate with separate system components with the Unix argument and 2 UNIX is a trademark of AT&T Bell Laboratories. 24 the shared Unix in the files. Any function required by the user interface could be performed Unix environment. PROTOTYPE CONSTRUCTION B. The Design Database (DDB), Software Base (SB), Graphic Editor (GE), Syntax Directed Editor (SDE), and the Rewrite System are utilized construction of the PSDL prototype. A description in the of the interface and function of each of these components as well as the function of the user interface in the coordination of the construction effort will be presented. 1. The Design Database. The Design Database development of the PSDL is hierarchical a program. This structure storage structure for the is a multiway tree with each node containing: • PSDL PSDL • Graphic Record • PSDL • Specification part Implementation part (Graph or (if implementation Control Constraints part The Specification (if is Ada®) Graph) implementation Graph). part can be further divided to obtain the various elements of the specification. In particular, inputs, outputs, states, and is MET individually. it can be broken into operator name, The Implementation part consists of the link statements produced in the Graphic Editor or written or retrieved code. to The Graphic Record is the data used only by the Graphic Editor that Ada® is used redraw the data flow diagram. Each operator. level of the tree The database is is produced by the decomposition of the parent able to recognize the relation of parent and child. This allows queries of the type find child and find parent, as well as a search by operator 25 name. Finally the DDB order to produce the DDB The must be able PSDL program. inputs are: GE) Graphic Record (from PSDL PSDL PSDL Implementation (Graph or Ada®) Control Constraints Specification Commands The complete to traverse the entire tree in a breadth first (from UI). DDB PSDL outputs are the same as the inputs with the addition of the program. The following operations were designed to enable the DDB to aid in the construction and modification of the prototype. • Create Root Node. This operation allows for the creation of a tree of operators in the database. • Create Child Node. This operation creates a new node for information storage and sets the parent-child relationship between this new node and its parent. • Store Property. This operation stores a PSDL Dart (Specification, Implementation or Control Constraints), subpart ((operator Name, Input List, Output List, State List or Maximum Execution Time), or Grapnic record in the • • Get Property. This operation retrieves these same properties from the Get Children. This operation returns the names of named • • named node. all DDB. the children of the operator. Delete Node. This operator removes the named operator from the DDB. Because of the hierarchical nature of the DDB, this operation will effectively remove the entire subtree that is rooted at the named operator. Traverse Tree. DDB This operation that collects the performs a breadth-first traversal of the into a single program. PSDL components 26 2. The Graphic Editor The Graphic Editor (DFD). is It is the part of is CAPS where most of done. The decomposition of a the actual creation of the drawing data flow diagrams a graphics tool for PSDL the input of the prototyf>e descroption Operator into lower level operators defines new nodes in the tree structure. The operators and data streams are entered here. GE can also show the DFD all editor insures a valid decomposition by checking the consistency of inputs, outputs, execution times. The The names of states and maximum of the parent operator to aid the user in retaining the place of a single operator in the prototype [Ref. 14]. Inputs to the its maximum GE include operators name, input, output, and state execution time. The outputs from the GE are the statements and the Graphic Record. The operations performed by the lists PSDL GE and link include drawing operators data streams, inputs, and outputs showing parent DFD, and loading and storing the Graphic Record. 3. The Syntax Directed Editor. The Syntax Directed Editor produces syntax checks existing PSDL specifications and produces Input to the its output 4. is SDE is The files. PSDL SDE reads PSDL and partial PSDL specifications produced in the UI and in and completes Control Constraints. the partial syntactically correct syntactically correct PSDL PSDL specification and control constraints. The Software Base The Software Base of reusable Ada® modules has two module and a maintenance module. The maintenance module creation and upkeep of the database. query involved with the All records must be stored by specification so that they can later be searched 27 is parts; a PSDL by the same specification. Although this part of the system is not utilized in the construction of the prototype, it should enjoy the same interface as the query module. [Ref. 15] The one or more 5. module receives quer>' Ada® modules The User The user the PSDL meet those that specification part and returns zero, specifications. Interface. interface has two main functions during the construction of the prototype; sequence control of the construction effort, and the insurance of The sequence continuity of the level-to-level decomposition of the operators. control is performed by utilizing the if-then-else logic of the consistency of the decomposition In the is Bourne Shell. The harder to achieve. decomposition of an operator, a number of child operators are produced through the use of the data flow diagram. Although this decomposition can produce any number of new operators with any number of data streams between them, the inputs and outputs of the system of child operators must be exactly the same as those of the parent. reading in an input and output outputs and that the if all The GE will not allow is any other inputs or maximum not valid. Additionally the Graphic Editor can check to execution time for any of the children does not exceed that of the parent. Finally, a state variable in a child decomposition as a self must also exist in the components, ape, bee, shown in DFD loop or a intemal connection between two operators. Figure 10 shows the decomposition of the operator top into operator top, insure this by these inputs and outputs are not utilized the user will be notified decomposition ensure that the list. The Graphic Editor can cat, and dog. Figure 10(b) Figure 10(a), because 28 it is its lower level a valid decomposition of the has the same inputs and outputs (a and The c). GE inclusion in the would produce PSDL the link statements stated, the four operators ape, bee, cat, four child nodes of the node top in the is in Figure 10(c) for implementation. As previously of these operators shown DDB. These nodes and dog represent the are created, but the known about them. not the only thing name Actually the link statements can be used to determine the inputs, outputs, names of any state variables, and maximum reads the link statements and determines a partial specification. The Production of streams. all specification has the this is in There PSDL is Interface of the information required to produce names but not the types of the data specification helps to ensure error free prototypes by relieving the user of the need to entered and The User execution times of these operators. PSDL remember what he has previously keeping with the guideline that data should be entered only once. one additional place where the User Interface creates part of the program. The Implementation followed by a Data Stream List. This part of in the statements. To complete consists of link statements consists of the internal data streams that list DFD. The UI appends were drawn PSDL the DataStream List the Implementation part of the each of these data streams must be added in the to the PSDL end of the link operator, the type of SDE. Sequence Control. 6. The construct module consists of a loop that continues while there are nodes in the DDB without an implementation part. The found in the DDB and match is its found, that node specification is is 29 incomplete node used to search the Software Base. considered atomic and the implementation section of that operator. first If there is Ada® code is is If a placed in the no match the user is asked to 75 ms (a) 10 ms state 20 ms 10 (b) a.EXTERNAL-->ape ab.ape:10ms-->bee ac.ape:10ms-->cat bc.bee:20ms-->cat b.cat:30ms-->EXTERNAL state. cat:30ms-->cat cd.cat:30ms-->dog dc.dog:10ms-->cat (c) Figure 10. Operator Decomposition 30 ms either decompose operator or write the again atomic and the is Finally, if the user chooses to the DFD Ada® is implementation. Ada® in the hand coding is done, this code becomes the implementation decompose the operator, the Graphic Editor part. draws and produces the link statements. The User Interface reads these link statements and writes the partial specification for nodes If DDB are created for each then called to complete the PSDL new all newly created operators. The Syntax operator. New directed editor is for the original composite operator. The construct loop ends when During the creation of a prototype, all leaf a rapid nodes of the growth in the DDB number are atomic. of nodes is Eventually the Ada® implementation for more of the lower level operators would be found in the SB and expected, as the high level operators are decomposed. the growth of the tree would stop. The construction process deals only with the production of operators. New data streams are produced in each operator. If these data streams are not atomic they must be defined in PSDL. All user defined data streams (ds) would appear outside the tree of operators on a level operator. Exceptions (ex) would also appear global type definition in Pascal. in the DDB at this level, equal to the root which is Figure 11 illustrates this structure. similar to a The tree of operators contains both composite operators (co) and atomic operators (ao). C. PROTOTYPE EXECUTION Protot>T)e execution utilizes the Translator (TR), Static Scheduler (SS), and Dynamic Scheduler (DS) to produce an executable prototype the design and requirements of the actual system. 31 in Ada®, that can test / / co3 co2 \ \ ^\\ \ / \ \ ao4 ao3 co4 ao2 • • • |ex1 ^"^ \ col ao1 ds2 ds1 root ^ ao5 DO 5 ( S \ / \ / ao6 \ ao7 Figure 11. Conceptual 1. \ ao9 ao8 DDB Structure The Translator The taking the translator in Ada® CAPS translates the PSDL into Ada®. This is done by implementation of the atomic operators and adding the control constraints of the composite operators to produce a group of loosely coupled Ada® modules. [Ref. 16] The breadth 2. first input to the translator traversal of the The The is the DDB. The PSDL program output is that was produced the package of Ada® in the modules. Static Scheduler Static Scheduler can be produced. If it is produces a schedule of time crirical operators, if one impossible to produce a valid schedule because of the timing constraints set in the construction of the prototype, the user will be notified by the Debugger. This process will be described section. 32 in the debugging and modification 3. The Dynamic Scheduler The Dynamic Scheduler produces a dynamic version of the static that includes a schedule of time critical operators, a collection of operators and an exception handler that adds the ability to run non-time is the debugger. critical operators in schedule non critical The Dynamic Scheduler conjunction with the static schedule. The produced dynamic schedule tasks and the exception handler. The higher it is falls behind its and the debugger will be To that consists of it reaches a designated milestone in amount of excess time schedule at two priority task is the schedule of time ahead of schedule the secondary task, (non-time operators) will be executed for the prototype Ada® program a This task will execute until critical operators. the schedule, if is time. critical In the event that the any milestone, an exception will be raised started. aid in debugging, a trace and a graphical representation of the executing prototype are planned. The trace will the time that it is entered. This information performance of the prototype is the list is critical name when of the operator and the actual real-time The run time being evaluated. status of the prototype could be displayed by presenting the user with a tree that represents the nodes of the DDB. The node on the frontier of the tree that corresponds to the operator currently executing would be highlighted. ability to 4. This would give the user the watch the actual execution of the prototype. Sequence Control. The Translator and Static Scheduler may be executed simultaneously in a multitasking environment. produced and a non-time any order, or After the Static Schedule critical operators identified, these 33 in is operators must be grouped package for use in a compiled and used in in the Dynamic Scheduler. The Translator output is both the Static Schedule and the non-time critical package. These two packages then become part of the Dynamic Schedule, which must be compiled and linked before it is executed. PROTOTYPE DEBUGGING AND MODIFICATION. D. The debugging of the prototype takes place during the execution of the Static Scheduler, while the static schedule the dynamic schedule of being produced, and during the execution of the prototype. parts because exceptions caused many is by static The Debugger must be broken problems arise before compilation, two while of the dynamic timing problems of a real-time system will not occur until the prototype has been compiled and is executing. [Ref. 17] The Debugger. 1. The Debugger has two methods of The into first is correcting problems in the prototype. through direct user interaction with the prototype and the second is through the Syntax Directed Editor and the Graphical Editor in the modification mode . The Debugger gives the user a chance to make small changes to the prototype in the ESS. This allows rapid feedback as to the results of the change. The problem with The only way 2. to this make method of modification, that these a permanent change to the prototype changes are temporary. is with the SDE or GE. Modifying the Prototypes. There are many problems involved modification of a PSDL prototype. in implementing the facilities for the These problems stem from the operators in the hierarchical structure of the down. is In addition there are both graphical 34 DDB fact that inherit information both up and and textual views of an operator. These A views actually hold different versions of the same information. view requires a change If an operator deleted the simple solution is This action should record a historical version of the prototype was an improper choice, that this deletion A deletion would this is The addition of entered. added to the DDB very severe and the at this time. a new operator DFD it is later DFD is first new shown mode subtree is (and link defined. as simple as a deletion. is DDB version of the prototype could be and the construction tree both deletetion and insertion the changes If also require the modification of the Construction continues until the reflect the to delete the entire is statements) of the parent operator, where the deleted operator is one in the other. subtree that has that operator as a root. operator in Modifying an Operator. a. restored. change The new of the user interface is completely defined. In of the parent operator must be modified to in its subtree. The most significant problem in modifying an operator occurs when small changes in the specifications or control constraints of an operator are made. A change Equally as in the specification could cause changes in every node of likely, a specification complex operator if change could cause an atomic operator the search of the software base search on modified specifications may yield a it at a child node may cause for the decomposition of the parent. 35 it to become a that was not previously with an atomic operator. This level-to-level consistency problem can Also a change to subtree. no longer yields a match. The match obtainable, therefor deleting a subtree and replacing its move up the tree as well. be different from the node required b. Consistency of Views. A change of a textual component of graphic representation. An example the implementation section of a is name the PSDL PSDL may be carried over to the of a data stream, that operator, is must be reflected changed in in the link statement and also in the graphic record. The graphical view of a change might be the best indication of the problems caused by deletions or changes. More prototype modification, if present in the construction E. same assurances of the mode effort is required in the area of PSDL valid prototypes that are are expected during modification. TOP LEVEL USERS MANUAL The top level users manual contains the four commands; execute and modify. This section describes these when the user will be in for each system 1. these commands commands and are executed. component, particularly the The SDE and GE, caps, construct, the environment individual user manual should also be consulted. The Caps Command. The caps command the user interface portion of three remaining is how the user initiates CAPS. From CAPS this point the and it places the user in user can initiate one of the commands. caps <newj)roto_name> The optional argument contains the constructed. If the If the argument DDB is this name will not used and the DDB is is Enter the root node name root node. When construction mode name the empty, . The response DDB is empty as the execution of a new be used prototype that to create a new is to root node. empty, the user will be asked to this to query will be used to create the the user will always be placed in the and modification modes would not apply. 36 be The Construct Command. 2. The construct command mode In this the user is is used directed into the to place the user in the construction SDE and GE to create the mode. PSDL program. construct This command will place the user in the location The process construction can begin or continue. production of a complete and valid the SDE and these tools retrieval of GE when PSDL is where the directed by the UI PSDL to insure the program. The particular aspects of both users manuals should be reviewed in order to properly utilize they are called. components in the The search of DDB, the Software Base, the storage and and the semantic checking of the UI are all transparent to the user. The user is advised of the results of the software search and the completion of the construction with the below dialogs. • Software Search Complete - no match found. This notifies the user that the search for an Ada® implementation for the given specification was unsuccessful. This would be followed by the question: Do you want to decompose, y or n. Based on the response the user will be placed in the GE or Ada® editor. • implementation found. This indicates a Software Search Complete successful retrieval of an Ada® implementation. The user is then asked to choose the next operator for implementation. • Select the next operator for implementation. This dialog presents the user with a list of incomplete operators. The user then enters the name of the desired operator. This question will follow the completion of any implementation. • Construction Complete. This message indicates the completion of the PSDL prototype. The user is then placed in the UI portion of CAPS where execution or modification can be selected. 3. The Execute Command. The execute command places where the constructed prototype is the user in the Execution Support executed 37 to test the real-time System performance. execute This command one does not exist the user is When placed back in the UI. Static checks for the existence of a completed prototype. first warned, No Completed a complete prototype is If Prototype Available, and available, the Translator, Scheduler and Dynamic Scheduler called in succession. The use of these components, as well as the The user is Ada® compiler and linker, informed of the status within the ESS is transparent to the user. with the below messages. Translation Complete. Static Scheduler Complete. Dynamic Scheduler Complete. Compilation Complete. Linking Complete. Execution Complete. In the event of a problem in the scheduling or execution of the prototype, the user will be notified by the Debugger. temporary corrections to the All permanent changes the modify the users manual for the make through the use of Debugger should be consulted for dialogs. The Modify Command. The modify command is in the appropriate editor form of any commands, messages and 4. the option to prototype in an attempt to achieve proper execution. must be made command. The The user has is placed in the modification used to mode make changes to the prototype. that insures that all consistently throughout the various levels in the The user changes are made DDB. modify This modified. command asks the user to Enter the The user must then call the SDE 38 or GE to name of the Operator make to be the required change to the operator. The UI insures that the appropriate changes are and lower levels of the will arise as these F. out. Depending on to enter the construction The design of this area in the higher user will be asked to resolve the questions that changes are carried might be required prototype. DDB. The made of CAPS is mode to the changes made the user complete the modified not complete. EVOLUTION OF THE USER INTERFACE. The current design of CAPS is in an evolutionary stage. As CAPS changes design of the User Interface must change to keep the system performing. present time, only a part of the total system has been implemented. functions of CAPS are implemented changes 39 to the interface will the At the As more of the be required. IMPLEMENTATION OF THE USER INTERFACE. IV. The user components of the implemented since interface has not been completely CAPS all of the have not been implemented. The link statement analyzer of UI has been implemented and have been tested and proved is described here. The means of sequence control be feasible for use to in the implementation of the This chapter will outline the implementation of the link analyzer as well interface. as a plan for the implementation for the remainder of the User Interface and the Dynamic Scheduler. A. THE LINK STATEMENT ANALYZER. The link statement analyzer specification for the is called nodes because newly created operators and is used it writes the partial to create new nodes in the DDB. The program was written in Pascal, because that familiar to the author. Berkley Pascal system, it was used because, can run on the Sun Workstation® The declaration structure that is section of nodes. p used. operators are stored in the linked list 3 its two end points. Sun Workstation® is remainder of the in Figure 12 describes the storage link statements are parsed and the of operators. Within a given operator a inputs, outputs, and states as well as the operator as like the and the Unix Operating System. shown program the In this State variables are determined ^ was the language most Maximum list of Execution Time are stored. by the existence of a data stream with the same Graphically this would appear as a self loop. There a registered trademark of 40 Sun Microsystems, Inc. list of internal data streams collected for inclusion in the Implementation section of the parent operator. The storage structure is built up as each link statement is read in succession. program CreateNodes (input, output); (* Global Constants *) const period = colon = ':'; arrow = blank = '.'; '-'; • '; EXTERNAL = EXTERNAL (* 72 blanks *) type = packed array = DataPti ^DataType; DataType = record Name: stringSO; stringSO [0..79] of char; (* Node for Linked List of Nodes *) Link: DataPtr; end; (* DataType *) OperPtr = Operator; Operator = record OpName: (* Node (* Head Pointer of Linked List of Operators *) (* Operator Name *) stringSO; InputList: DataPtr; to Input List *) InListTail: DataPtr; (* Tail Pointer to Input List *) OutputList: DataPtr; (* Head Pointer to Output List *) Output List OutListTail: DataPtr; (* Tail Pointer to StateList: DataPtr; (* StateListTail: DataPtr; (* Tail Pointer to State List *) Execution Time *) ( * MET: Head Maximum StringSO; Link: OperPtr; end; (* Operator *) var OpHead: OperPtr; (* OpTail: OperPtr; (* Tail of Operator List *) DataHead: DataPtr; (* DataTail: DataPtr; (* Tail of Head of Operator List Head of Data List Data List *) *) Figure 12. Declaration Section of Nodes.p 41 *) Pointer to State List *) *) After the link statements are read into the data structure, specification parts for each new node create neu' nodes in the command. be used to with each file being the input for the create new node In addition to creating the child nodes, the PSDL implementation consists of DDB, all new state variables. section for the parent These files will are written into dynamically created files. node is Data Stream part of the produced. This data stream internal data streams created in the decompositions that are not The creation of both a child node and the Data Stream nodes. p are illustrated in Figure 13. This figure illustrates that were produced in the partial specification of the GE Nodes. p is to how (Figure 13(a)) are used by the is in UI to produce the 13(b)). The entire shown in Appendix D. All of the semantic PSDL is included in the nodes. p program. produce proper included as an important part of the construction subsystem. ab.ape:10s->bee ac.ape:10s-->cat bc.bee:20s-->cat c.cat:30s-->EXTERNAL state.cat:30s-->cat cd.cat:30s-->dog a.EXTERNAL-->ape dc.dog:10s->cat (a) NewNode.Ol OPERATOR ape SPECIFICATION INPUT a OUTPUT ab ac MAXIMUM EXECUTION TIME list the link statements newly defined operator, ape, (Figure input and output of this example checking required list 10s (b) Figure 13. Input and Output of Nodes.p 42 SEQUENCE CONTROL B. The Sequence Control of THE USER INTERFACE. IN the construction and execution subsystems has been designed and tested. Complete implementation can be started of CAPS the elements are operating. The goal of the construction subsystem is the production of the DDB operator must be written and the root node in the createRootNode command. This command command the user types the subsystem caps. DDB to the are fully defined. called node.list. When new empty is s node.list do The will first specification. is a loop that The user executed by the UI when is met the construction interface maintains a is this function in the name on second. The invoked to DDB list name removed from Bourne is is all the elements of nodes in a added the list. list. When this the completion of the command the first line in the file ddb.in and the name places the operator's specification in the file is from the Base by placing it This specification in the file psdl.spec is DDB specification on the ddb.out. The SDE is is called then sent to the Software and then executing the 43 PSDL executed with the complete and syntactically check the specification. This editor ddb.out. test- Shell. this the partial specification is retrieved command SDE file to this The command: while complete. step in the construction To do executed until operators are created, their the prototype perform is through the use of the getProperty command. This with the is After this requirement these operators are fully defined, they are node.list DDB created with the entered. is The prototype construction operators PSDL Before the construction process can begin the specification of the root prototype. As all Implementation of the Construction Subsystem. 1. of the when file Software _Base. response to the query' is empty, otherwise the Ada® The command been found. If it read from the code test-s has, the do added followed by the retrieved a If there is is no match, the used by the UI to determine code will be appended PSDL comment. To form of a SB_out. file is is in this file. SB_out Ada® file this, the Ada® words to the Ada® code which is if a match has Implementation in the and the operator name are surrounded by the brackets of PSDL comment. If no match decompose tested. the code the DDB found A the operator. When in the software search, the user is asked if they want to string-valued variable containing the users response is the response is negative, the user is placed in an editor, currently vi, Ada® where the is implementation that is retrieved with the is written. The Ada® code is handled the same as from the Software Base. The implementation command storeProperty with the operator is stored in name followed by the Implementation section placed in ddb.in. When the user wishes to data flow diagram and given the are files made from its decompose, the Graphic Editor is called and the corresponding link statements are produced. The GE is graph.name, graph.in, graph.out, graph.state and graph.met which data retrieved from the specification part of PSDL. The GE outputs graph.link and graph.pic are the link statements and graphical record respectively. Graph.pic is also an input, but The user interface it will be empty unless a DFD already exists. creates graph.name, graph.in, graph.out, graph.state, and graph.met by getting the specification part of the node as described above, scanning for the information and writing and graph.link are produced DDB it in the appropriate file. in the by writing the key words The output GE. The implementation section files is graph.pic stored in the IMPLEMENTATION and GRAPH to the file ddb.in 44 p ddb.in and then concatenating the files then stored using the storeProperty While reading needed dynamically produce of new executing the it. The file dcih.in is command. the link statements to determine the internal data streams produce psdl.ds the new nodes are to number graph.link and psdl.ds to files named NewNode.OJ identified. to operators in the decomposition. command createChildNode The program nodes. NewNodeXX depending on the The new nodes NewNode for each file. To execute createChildNode, ddb.in must have the name of the new node on the followed by the name of the parent node and then the by are created partial specification first line produced by the link analyzer. The loop being all executed is nodes are traverse first traversal is executed. With the of the concatenated to the DDB file. to the file psdl for use by is This the name of the performed and the PSDL complete when the root node in ddb.in PSDL , a breadth for each operator specification for the entire prototype is is moved Implementation of the Execution Support System. System involves the Dynamic Scheduler, and the piped to the executable file the Execution Support coordination of the Translator, Static Scheduler, compiler and linker as well. To execute translator. This that is Execution Support System. The implementation of Ada® nodes fully described with the leaf atomic operators. The construction of the prototype command 2. until all a prototype, the file psdl is first program generates a package of loosely coupled Ada® components each represent one of the leaf nodes of the prototype. This package TL.a and is used by both the Static and Dynamic Schedules. 45 is called The Static Schedule is produced by executing the preprocessor called psdl_reader with psdl piped as psdl_reader, called operator. info, Static _Scheduler. A output. The is input. its attribute The output grammar file from the input to the next program, called Static _Scheduler produces a static scheduler, SS.a, as secondary output of the Static_Scheduler is the list of non-time its critical operator NTC.out. Both SS.a and NTC.out are used by the Dynamic Scheduler executable schedule called DS.a. This output schedule, which must be compiled and linked before execution. name of the executable prototype code is is to produce an written in Ada®, After schedule completion, the changed to be the same as the root operator. Implementation of Debugging and Modification. 3. The debugger, as previously described, is broken into two Scheduler debugger and the executing prototype debugger. embedded in the Execution Support System although it is parts; the Static Both parts are not part of the execution of the prototype. If the debugger gets direct input from the user this information used to try to keep the prototype executing. the debugger writes the error read it and attempt to message is the problems become too large into the file information where the user can modify the prototype. The modification process DDB When is equipped with all is not completely defined at this time, but the the operations that should be required. In addition to the operations that were previously discussed in the construction of the prototype, there are the getParent and getChildren the deletNode command for the commands for moving around removal of unneeded operators. 46 the tree and The getParent command The name of wherever output is that is it the nodes parent needed. The list is called with the command is getChildren placed in the The deletNode command simply entire subtree of the DDB C. ddb.in and in its will require that a historical version is defined, additional operators EXAMPLE BOURNE SHELL SCRIPTS commands that implemented at the The in the list in the mode is illustrated in is of incomplete operators to the user, >> ddb.in DDB These was not is places the who file getChoice. This file displays The command cat choice of the choice operator and the keyword SPECIFICATION, found in the file getProperty to retrieve the specification uses ddb.in is then selects the next operator for stored in the file choice. name Figure 14. This script empty, signifying a complete prototype. loop calls the executable implementation. The choice spec UL Script. script for the construct command illustrate the sequence control of the and have not been tested because the a loop that executes until the file node. list first mode time of this writing. The Construct 1. Shell scripts of the construct have been tested for use scripts are not complete, the node named subsystem will be required. the construction The following example Bourne The very similar except that the ddb.out. file be saved. As the modification process from is deletes the from the DDB. This command in the various tools in ddh.in. placed in standard output and can be piped to is of child nodes and known nodes name spec, in the DDB. 47 file ddb.in. The command of the operator from the while node. list do test-s getChoice ddb.in cat choice spec getProperty SDE ddb.out mv ddb.out psdl.spec » » temp cat ddb.in psdl.spec mv temp ddb.in storeProperty Software_Base if test-s SB_out then echo "Software Search Complete addlmpl - implementation found" else echo "Software Search Complete - no match found" echo "Do you want to decompose, y or n." read x if test $x = y then GE else adaEditor addAdalmpl fi fi done echo "Construction Complete" Figure 14. Construct Script The output from the DDB, completed and syntax checked. The file psdl.spec, which commands create SPECIFICATION is file is the file it moved with and the completed specification search of the would sent to the fail SDE, where mv command the SB The next it is to the three temp with the operator's name, the keyword command is initiated results of the search are placed in the file empty and then is the input file for the Software Base. ddb.in where the storeProperty The ddb.out, the test-s stores in the it. This file is moved to DDB. by the command Software _Base. The SB command. 48 it in out. If there is If there is no match this file is an implementation in the file, the user is message "Software Search Complete notified with the implementation found", and the executable program makelmpl program creates a PSDL IMPLEMENTATION This called. is - implementation section by placing the keywords and Ada in the file ddb.in. The operator name and PSDL comment retrieved code, surrounded by the brackets ({}) of a the are concatenated to complete ddb.in. no implementation If command "y" the found "Software Search Complete decompose, y or n" is is GE is The . K the user does SB, the user script for the is Ada® notified with the read into the variable x GE is demonstrated not want to decompose, the by addAdalmpl which adds the is no match found" and asked "Do you want response user's The called. - in the Ada® implementation the response in the next section. editor to the if to called followed is PSDL operator just as addlmpl does. When prototype is node.list is empty, complete. The user all is the operators are completely defined, notified with the command " and the Construction Complete". 2. The Graphic Editor The GE script, The primary purpose of shown Script. the in Figure 15, is GE embedded script is to get the inputs Graphical Editor, and then store the outputs back in the The executable the proper keywords outputs, states and file getlnputs calls the in the file ddb.in, maximum well as the graphic record, if to in the construct script. from the DDB, call the DDB. DDB command getProperty retrieve the operator , with name, inputs, execution time from the operator specification, as one was previously produced. This information 49 is placed in the files graph.name, graph.in, graph.out, graph.states, graph.met, and graph.pic respectively. These files are the The command graph puts inputs to the the user in the editor where the The outputs of the decomposition of the operator are produced. graphic record graph.pic and the link statements in the is GE. file DFD the GE that defines are the new graph.link. Graph.link piped to the link analyzer nodes, where the partial specification of the newly defined nodes and the data stream list are created. get_inputs graph nodes < graph. links cat graph. links psdl.ds » psdl.imp » ddb.in cat choice Imp Graph psdl.imp SDE ddb.in storeProperty ddb.in cat Graphic graph.pic StoreProperty » createNodes Figure 15. Graphical Editor Script The commands Graph.link psdl.ds psdl.imp >> done by first » psdl.imp and cat choice Imp Graph ddb.in produce the implementation of a composite operator. This combining the IMPLEMENTATION, operator name. link statements in the file imp, and The PSDL implementation must add the types and data stream is GRAPH stream list. The keywords added as well as the are then sent to the to the data streams in the data list. is SDE where the user The user may also add any optional control constraints. The StoreProperty command section and the graphic record. The cat is used to store both the implementation command for the storage. 50 in between sets up the file ddb.in The last NewNode.XX, DFD, and executable command that were created creates a node in the file createNodes takes the in the script, in the DDB UI name and file operator defined in the the ddb.in with the the partial specification, in command. The new operator name, NewNode.XX, for each new command. operator before executing the createChildNode D. new with the createChildNode createNodes must load the parent operator for each of the form: files FUTURE IMPLEMENTATION. There are two aspects first is to the future implementation of the User Interface. The implementation of the designed features of the system. As the individual components are completely provide the features of the system to the user. all implemented the UI will need to be After all expanded to the logical considerations of the interface are fully tested, the second part of the implementation can begin. The second phase is more directly involved with the Human Factors Engineering of the system. Presently the major considerations are what the system does, what information is to be passed and which tool should be invoked next. The follow on work should be more involved with and received from the via the mouse, user. The use of a how more graphic would be more compatible with system. 51 the information is presented to interface with a response the primarily graphic input of the CONCLUSIONS V. The goal of CAPS and CAPS from to this thesis was to determine the requirements of a user interface for design such an interface. This expert interface will help transform a collection of software engining tools, into a usable system for rapid prototyping. FEASIBILITY ISSUES. A. The work done in this thesis demonstrates that a user interface that supports the construction, execution and modification of an executable prototype can be produced. First the requirements of interface were defined. These included data entry, data protection, communication between elements and sequence control. A design of an interface that could support these requirements was then produced. Key aspects were tested and the implementation outiined. This interface, along with the demonstration of the feasibility of most of the components of CAPS, has shown demonstrate that this embedded systems. It built. The next step is to must be shown minimum that CAPS can construct and execute these user training. BENEFITS OF THE STUDY The primary of system can be prototyping effort can aide in the production of real-time prototypes quickly with B. that the benefit of the CAPS. CAPS work done on the user interface is the advancement has demonstrated the potential for significant time and cost savings in the production of these real-time system. If the user interface can be powerful and friendly enough to promote the users interest in the system then CAPS will be more readily used. 52 A secondary benefit of this research is in the area Other software engineering tools might be able systems. aspects of the CAPS user interface. entry and display could utilize the the two views. The use of some C. of user interfaces for other the A to utilize some of and textual data tool that uses both graphical same type of control of data consistency between Bourne shell scripts might a be a useful model for other system as well. RECOMMENDATIONS. There are three recommendations for the improvement of CAPS. recommendations include the addition of two new areas of work change in the The done in the original design of SDH. As CAPS called for the majority of the data entry to be the system has been developed, the DFD operators and data streams are defined in information from the GE to produce the is PSDL. partial names data streams and GE, and the Xynpc must be added in the link statements, would eliminate complete the specifications and data stream 2. in the GE has proven to be the the first place where the new The UI already uses specification of the constructed operators and the data stream declaration. Currently the SDE. The the newly GE only inclusion of types the need to return to the SDE lists. Prototype Modification. A mode system and a primary method of data entry. primary tool for the entry of new data. The in the to the These Primary Data Entry. 1. to the method of prototype modification must be provided. that not only allows assurances of valid PSDL changes to the prototype, but prototypes as the construction 53 A modification provides the same mode is required. Until this modification subsystem is in place, the rapid debugging of the prototype will not be possible. 3. Execution Monitoring. The current design of CAPS Some means execution of the prototype. the execution of the prototype of producing both a trace and a view of would greatly improve the verify the prototype's performance. to does not include a means of monitoring the The ability to trace a one of the original requirements would aid ability to problem in the validation or debug and in the execution modification of these requirements. D. APPLICATION OF CAPS IN THE DEPARTMENT OF DEFENSE AND THE DEPARTMENT OF THE NAVY. The substantial investment in real-time embedded systems in DOD and DON points out the tremendous need for a tool such as executable prototype in Ada® that CAPS. Since CAPS produces an can be used to system before coding. MIL-H-48655B calls for test the design of a software requirements analysis, functional specification and verification before the actual coding of the system [Ref. 19]. Rapid Prototyping supports written in Ada®, of real-time so it All this objective. seems that CAPS is embedded systems in the tool that best supports the production embedded systems. Although CAPS is not yet a complete system, does hold promise as an important tool for software engineering in There tactical is much interest in the rapid existing, method it DOD and DON. development and acquisition of software for systems in the Navy, as shown outlines a DOD are to be in OPNAVNOTE 5000. This instruction for accelerated acquisition of tactical systems through the use of "off the shelf" hardware and rapidly produced developmental 54 software [Ref. 20]. The production of the use of a software tool like this software could be accelerated through CAPS. Rapid prototyping has demonstrated a potential the inherent to be one possible solutions to problems of producing large real-time systems with traditional software engineering methodologies. CAPS shows engineering tool. 55 promise as a practical software ) APPENDIX A. PSDL GRAMMAR = psdl psdl = (component} component = data_t>q>e operator Start i data_t>pe = "type"id type_spec typejmpl operator = "operator"id operator_spec operator_impl type_spec = "specification" [type_decl] {"operator" id operator_spec [functionality] "end" type_impl = "implementation" "ada" id "{"text")" "implementation" type_name ("operator" id operator_impl} "end" operator_spec = "specification" (interface) [functionality] "end" operatorjmpl = "implementation" "ada" id "(" text ")" I I type_decl = "implementation" psdl_impl id_list ":" functionality type_name = [keywords] ("," id_list ":" type_name} [informal_desc] [formal_desc] psdl_impl = data_flow_diagram [streams] [timers] [control_constraints] [informal_desc] "end" type_name = I id "[" type_decl "]" id = attribute [reqmts_trace] = id (","id } keywords = "keywords" id_list informal_desc = "description" "{" text formal_desc = "axioms" "(" text "}" data_flow_diagram = "graph" (link) streams = "data stream" type_decl timers = "timer" id_list interface id_list "}" = generic_param attribute input I output I states I exceptions I I timing_info generic_param = "generic" type_decl input = "input" type_decl = "output" type_decl = "states" type_decl "initially" exceptions = "exceptions" id_list output states expression_list 56 } timing_info = ["maximum execution time" time] ["minimum calling p)eriod" time] ["maximum response time" time] reqmts_trace = "by requirements" id_list link = id "." id [":" time] "->" id control_constraints = "control constraints" {constraint} constraint = "operator" id ["triggered" [trigger] ["if' predicate] [reqmts_trace]] ["period" time [reqmts_trace]] ["finish within" time [reqmts_trace]] constraint_options ( = "by trigger id_list all" "by some" id_list constraint_options = "output" id_list "if predicate [reqmts_trace] I I I "exception" id timer_op id ["if' ["if' predicate] [reqmts_trace] predicate] [reqmts_trace] timer_op = "read timer" "reset timer" I "start timer" I "stop timer" I = expression ("," expression} = time integer [unit] unit= "ms" "sec" "min" "hours" expression = constant expression_list I I I lid type_name "." id predicate = relation {bool_op relation = simple_expression "(" I expression_list ")" relation} simple_expression rel_op simple_expression simple_expression = [sign] integer [unit] I [sign] real I ["not"] id I string I I ["not"] boolean_constant I booLop = "and" rel_op real = = integer = "or" "<=" "<" I integer I "." ["not"] "(" predicate ")" ">" I I "=" ">=" I I integer digit {digit} "false" boolean_constant = "true" integer numeric_constant = real = boolean constant constant numeric constant I I I 57 ":" "/=" I = + char = any digit = "0 letter = "a II Sign , 11 !t ft - I printable character except "}" 9" .. "_" "A Z" alpha_numeric = letter digit id = letter {alpha_numeric} string = (char) .. z" I .. I I text = {char} 58 APPENDIX B. BRAIN TUMOR TREATMENT SYSTEM EXAMPLE OPERATOR Brain_tumor_treatment_system SPECIFICATION INPUT patient_chart: medical_history, treatment_switch : boolean boolean OUTPUT treatment_finished: STATES temperature: real INITIALLY 37.0 DESCRIPTION [This is an English description END IMPLEMENTATION GRAPH temperature. EXTERNAL--> of the operator } hyperthermia_system patient_chart.EXTERNAL--> hyperthermia_system treatment_switch.EXTERNAL — > hyperthermia_system treatment_power.hyperthennia_system — > simulated_patient treatment_finished.hyperthermia_system --> EXTERNAL temperature. simulated_patient -> hyperthermia_system DATA STREAM treatment_power real : CONTROL CONSTRAINTS OPERATOR hyperthermia_system PERIOD 200 ms BY REQUIREMENTS OPERATOR simulated_patient PERIOD 200 ms DESCRIPTION {some text about shutdown it} END OPERATOR hyperthermia_system SPECIFICATION INPUT temperature rreal, patient_chart:medical_history, treatment_switch: boolean OUTPUT treatment_power: real» treatment_finished: boolean MAXIMUM EXECUTION TIME 100 ms BY REQUIREMENTS temperature.tolerance MAXIMUM RESPONSE TIME 300 ms BY REQUIREMENTS shutdown KEYWORDS medicaLequipment, temperature_control, 59 hyperthermia, brain_tumors DESCRIPTION { } END IMPLEMENTATION GRAPH temperature. EXTERNAL --> start_up temperature. EXTERNAL --> maintain patient_chart.EXTERNAL --> start_up treatment_switch.EXTERNAL --> safety_control estimated_power.start_up --> safety_control estimated_power.maintain — >safety_control treatment_finished. maintain --> safety_control treatment_finished.start_up --> safety_control treatment_power.safety_control — > EXTERNAL DATA STREAM estimated_power: real TIMER treatment_time CONTROL CONSTRAINTS OPERATOR start_up TRIGGERED IF -42.4 > temperature BY REQUIREMENTS maximum_temperature STOP TIMER treatment_time RESET TIMER treatment_time EF temperature <= OPERATOR maintain TRIGGERED by all temperature, treatment_time IF temperature 37.0 >= 42.4 BY REQUIREMENTS maximum_temperature OUTPUT treatment_fmished IF treatment_time >= 45 BY REQUIREMENTS treatment.time START TIMER treatment_time BY REQUIREMENTS treatment_time, temperature_tolerance END OPERATOR start_up SPECIFICATION INPUT patient_chart: medical_history, temperature: real OUTPUT estimated_power: real, treatment_finished: boolean EXCEPTIONS errl, err2, err3 BY REQUIREMENTS temperature_tolerance 60 min DESCRIPTION } { END IMPLEMENTATION Ada OPERATOR start_up maintain SPECIFICATION INPUT temperature: real OUTPUT estimated_power: real, treatment_finished: boolean MAXIMUM EXECUTION TIME 90 ms BY REQUIREMENTS DESCRIPTION { temperature_tolerance } ENT) IMPLEMENTATION Ada maintain OPERATOR safety_control SPECIFICATION INPUT treatment_switch, treatment_fmished: boolean, estimated_power: real OUTPUT treatment_power: real BY REQUIREMENTS shutdown MAXIMUM EXECUTION TIME 10 ms BY REQUIREMENTS temperature.tolerance DESCRIPTION { } END IMPLEMENTATION Ada safety_control OPERATOR simulated_patient SPECIFICATION INPUT treatment_power OUTPUT temperature DESCRIPTION ( : : real real } END IMPLEMENTATION ADA simulated_patient 61 APPENDIX program CreateNodes C. PASCAL PROGRAM nodes.p (inpul,output); (* Global Constants *) const period = '.'; colon = ':'; arrow = blank = '-'; '; ' EXTERNAL = 'EXTERNAL (* 72 blanks (* Node for (* Node of Linked List of Operators *) *) type = packed array = ^DataType; DataPtr DataType = record Name: stringSO; stringSO [0..79] of char; Linked List of Nodes *) Link: DataPtr; end; (* DataType *) OperPtr = '^Operator; Of>erator = record OpName: Name stringSO; (* Operator InputList: DataPtr; (* Head InListTail: DataPtr; (* Tail Pointer to Input List *) OutputList: DataPtr; (* Head *) Pointer to Input List *) Pointer to Output List *) Output List *) Pointer to State List *) OutListTail: DataPtr; (* Tail Pointer to StateList: DataPtr; (* StateListTail: DataPtr; (* Tail Pointer to State List *) MET: (* Maximum Execution Time OpHead: OperPtr; (* Head of Operator OpTail: OperPtr; (* Tail of DataHead: DataPtr; (* StringSO; Head *) Link: OperPtr; end; (* Operator *) var DataTail: DataPtr; Operator List *) Head of Data List (* Tail of List *) Data *) List *) C procedure ReadToken(delimeter:char; var token: StringSO); (* Reads PSDL Link statements from standard input, one token at *) (* a time. Delimeters are: period, colon, var 62 arrow and End of Line *) ; ndx:integer; ch: char; begin ndx (* initialize *) := 0; read(ch); while (ch o dehmeter) and do (not eoln) begin by character token[ndx] := ch; (* Gets token character read(ch); (* until delimeter or eoln *) ndx := ndx + 1 (* while*) end; (* Gets last character *) eoln then token[ndx] := ch; if *) if delimeter = arrow then (* be fore end of line *) begin (* read(ch); read(ch); eoln then readln; end; rest of arrow *) (* if *) end; if remove (* ReadToken (* resets Hne *) *) -*) (= procedure ReadOperMet(var Operl, Met: stringSO); (* Reads PSDL Link statements from standard input, one token at *) (* a time. Determines Operatorl and Maximum Execution Time *) var ndx:integer; ch: char; begin ndx (* initialize *) := 0; read(ch); while (ch o colon) and (ch o arrow) do begin by character Operl [ndx] :=ch; (* Gets token character read(ch); (* until delimeter or eoln *) ndx :=ndx+ end; 1; (* while*) ch = colon then begin (* if ndx end of Une *) := 0; read(ch); while ch o arrow do begin Met[ndx] (* Gets token := ch; 63 by character *) *) (* until delimeter or eoln *) read(ch); ndx := 1; (* while*) end; end; ndx + (* if *) (* read(ch); read(ch); end; (* remove rest of arrow *) ReadOperMet*) *) (' function OpSearch (Head: OperPtr; Target: stringSO): OperPtr; (* Searches Operator List for Target string, returns pointer *) (* to target if found, otherwise NIL *) begin Head = nil then OpSearch := nil if (* else if Head^.OpName = Target then OpSearch := Head empty (* target list *) found *) else OpSearch end; /* OpSearch(Head^.Link, Target); := _ Op Add procedure *\ _ (var Head: OperPtr; varTail: Op>erPtr; Target: stringSO); (* Adds new Operator to end of linked list *) var p: OperPtr; (* temp pointer *) empty *) begin if Head = nil then (* List is begin new(p); (* Create new head node *) Head := p; Tail := p; p^.OpName := Target; p^.InputList := list *) nil; p'^.OutputList := nil; p^.OutListTail := p^.Link := new nil; p^.InListTail := end (* (* Initialize nil; nil; if *) (* List not else empty *) begin new(p); (* Tail'^.Link := p; 64 Add new node after tail *) Tail := Tail^.Link; p^.OpName := Target; (* Initialize new lists *) p^.InputList := nil; p/^.InListTail := nil; p^.OutputList := nil; p^.OutListTail := p^.StateList := nil; nil; p^.StateListTail := p^.Link end (* else nil; := nil; end; *) OpAdd (* *) *) (* function Search (Head: DataPtr; Target: stringSO): DataPtr; Searches Data Listfor Target string, returns pointer *) (* to target if found, otherwise NIL *) begin (* Head = if nil Search := else if then (* nil empty list *) Head'^.Name = Target then Search := Head (* target found *) else Search := Search(Head^.Link, Target); end; (* Search *) (* *) procedure Add (var Head: DataPtr; var Tail: DataPtr; Target: stringSO); (* Adds new Data to end of linked lists *) var (* p: DataPtr, Temp pointer *) begin if Head = nil then (* List is empty (* Create new node *) begin new(p); *) Head := p; Tail := p; p^.Name := Target; p^iink := nil; end (* Initialize new lists *) (*if*) (* List not else 65 empty *) begin Add new node (* new(p); after tail *) Tail^.Link := p; Tail := Tail^.Link: p^.Name p^.Link := end (* else end; (* (* Initialize := Target; new lists *) nil; *) OpAdd *) *) (* procedure LoadDataStructure(var OpHead, OpTail: OperPtr; var DataHead, DataTail: DataJ^); (* Loads tokens into Data Structures *) var Current: OperPtr; (* Data, Met: stringSO; (* Temp pointer *) PSDL Tokens *) Operl,Oper2: stringSO; begin Data := blank; Operl := blank; (* Initialize Strings *) Met := blank; Oper2 := blank; while not eof do begin (* Get tokens *) ReadToken(period,Data); ReadOperMet(Oper 1 ,Met); ReadTokenC ',0per2); if Operl o EXTERNAL then (* Keyword EXTERNAL is not *) (* an Operator *) Current := OpSearch(OpHead,Operl); if Current = nil then begin begin (* Add Operator 1 *) OpAdd(OpHead,OpTail,Operl); Current := OpSearch(OpHead,Operl); end; (* if *) Currenf^.MET := Met; (* Enter Add Data to Operators Output Operl = Oper2 then (* if Maximun Execution Time List *) begin if Search(Current^.StateList,Data) = nil then Add(Current^.StateList,Current^.StateListTail, Data); end else 66 *) if Search(CuiTent^.OutputList,Data) = nil then Add(Currenl^.OutputList,Current^.OulLislTail, Dam); (* if *) end; Oper2 if o EXTERNAL then begin (* Keyword EXTERNAL Operator (* an is *) Current := OpSearch(OpHead,Oper2); if Current = nil then (* Add Operator 2 *) begin OpAdd(OpHead,OpTail,Oper2); Current := 0pSearch(0pHead,0per2); (* if *) end; Add Data (* if to Operators Input List *) Operl = Oper2 then begin if Search(Current^.StateList,Data) = nil then Add(Current^.StateList,Current^.StateListTail, Data); end else Search(Current'^.InputList,Data) if = nil then Add(Current^.InputList,Current'^.InListTail, Data); end; (* if *) (* Enter o o new Data Streams and (Oper2 internal o in Data List *) ((Operl EXTERNAL) EXTERNAL)) and (Operl Oper2) then if Search(DataHead,Data) = nil then Add(DataHead,DataTail,Data); (* Reset Strings *) Data := blank; if Operl Met := blank; Oper2 end end; := blank; := blank; (* while *) (* LoadDataStnicture *) *) (* procedure WriteString(var File:text; Str: stringSO); var ndx: integer; begin ndx := 0; while Str[ndx] o " do begin 67 not *) write(File,Str[ndx]); ndx :=ndx + (* while *) end; end; 1; (* WriteString *) *) (* procedure MakePSDL(Head: OperPtr); (* Generates partial PSDL Specification for each new Operator *) (* in the Graphical decomposition *) type stringlO = packed array [0.,9] of char; var (* Current: OperPtr; Temp pointers *) InTemp: DataPtr; OutTemp: DataPtr; State Temp: DataPtr; OutFile: text; NodeName: (* stringlO; Unix file name *) begin Current := Head; NodeName := 'NewNode.Ol'; while Currento (* First file name *) do nil begin rewrite(OutFile,NodeName); (* output PSDL (* Create new file *) *) write(OutFile;OPERATOR '); WriteString(OutFile,Current^.OpName); writeln(OutFile); writeln(OutFile); writeln(OutFile,'SPECIFICATION'); writeln(OutFile); InTemp := if InTemp Current^.InputList; o nil (* Generate Input then begin write(OutFile;iNPUT '); WriteString(OutFile,InTemp'^.Name); writeln(OutFile); InTemp := InTemp^.Link; while InTemp nil do o begin write(OutFile; '); WriteString(OutFile,InTemp^,Name); writeln(OutFile); InTemp := InTemp^. Link; 68 list *) (* while *) end; N\Titeln(OutFile); end; (* if *) OutTemp := if OutTemp Current^.OutputList; o then nil (* Generate begin write(OutFile;OUTPUT Output '); WriteString(OutFile,OutTemp'^.Name); writeln(OutFile); OutTemp := OutTemp^. Link; while OutTemp nil do o begin write(OutFile,' '); WriteString(OutFile,OutTemp^.Name); wTiteln(OutFile); OutTemp := OutTemp^.Link; (* while *) end; writeln(OutFile); end; (* if *) StateTemp := Currenf^.StateList; if StateTemp nil then o (* Generate State hst *) begin write(OutFile;STATE '); WriteString(OutFile,StateTemp^.Name); writeln(OutFile); StateTemp := State Temp'^.Link; while StateTemp nil do o begin write(OutFile; '); WriteString(OutFile,StateTemp^.Name); writeln(OutFile); StateTemp end; := StateTemp^ .Link; (* while *) writeln(OutFile); end; (* if *) write(OutFile,'MAXIMUM EXECUTION TIME WriteString(OutFile,Cun-ent^.MET); writeln(OutFile); writeln(OutFile); Current := Currenf^.Link; (* Dynamically create new ifNodeName[9] = file '9'then begin 69 name *) '); list *) ; NodeName[9] NodeName[8] end := '0'; := succ(NodeName[8]); := succ(NodeName[9]); (* if *) else NodeName[9] (* while *) end; end; MakePSDL (* (*-- *) - - *) procedure MakeDataStream (Head: DataPtr); (* Generate PSDL Data Stream *) var Temp: DataPtr; Outfile: text; begin rewrite(Outfile,'psdl.ds'); writeln(Outfile); if Head o nil then begin Temp := Head; write(Outfile,'DATA STREAM '); WriteString(Outfile,Temp^.Name); writeln(Outfile); Temp := Temp'^.Link; while Temp o nil do begin write(Outfile,' '); WriteString(Outfile,Temp^.Name); write In(Outfile); Temp end; := Temp^.Link; (* while *) writeln(Outfile); end; end; (* (* if *) (* MakeDataStream *) *) main *) LoadDataStructure(OpHead, OpTail, DataHead, DataTail); begin (* MakePSDL(OpHead); MakeDataStream(DataHead ) (* main *) end. 70 APPENDIX D. INPUT AND OUTPUT LINK ANALYZER LINK STATEMENTS ab.ape:10s-->bee ac.ape:10s-->cat bc.bee:20s— x:at b.cat:30s-->EXTERNAL state.cat:30s-->cat cd.cat:30s-->dog aEXTERNAL-->ape dc.dog:10s-->cat NEWLY CREATED NODES NewNode.OL OPERATOR ape SPECIFICATION INPUT a OUTPUT ab ac MAXIMUM EXECUTION TIME 10s NewNode.02: OPERATOR bee SPECIFICATION INPUT ab OUTPUT be MAXIMUM EXECUTION TIME 20s NewNode.03: OPERATOR cat SPECIFICATION INPUT ac be dc OUTPUT b cd STATE state MAXIMUM EXECUTION TIME 30 71 NewNode.04: OPERATOR dog SPECIFICATION INPUT cd OUTPUT dc MAXIMUM EXECUTION TIME Data Stream part for OPERATOR 10s top: DATA STREAM ab ac be cd dc 72 APPENDIX E. BOURNE SHELL SCRIPTS CONSTRUCT SCRIPT: while test-s node. list do getChoice ddb.in cat choice spec getProperty SDE ddb.out mv ddb.out psdl.spec » cat ddb.in psdl.spec mv temp » temp ddb.in storeProperty Software_Base SB_out then echo "Software Search Complete addlmpl if test-s - implementation found' else echo "Software Search Complete - no match found" echo "Do you want to decompose, y or n." read x if test $x = y then GE else adaEditor addAdalmpl fi fi done echo "Construction Complete" GRAPHIC EDITOR SCRIPT: getjnputs graph nodes < graph. links cat graph. links psdl.ds cat choice » psdl.imp Imp Graph psdl.imp » ddb.in SDE ddb.in 73 storeProperty Graphic graph. pic StoreProperty createNodes cat » ddb.in 74 REFERENCES 1. Booch, G., Software Engineering with Ada®, 2nd ed., Benjamin Cummings Publishing Co., Inc., 1987. 2. Pressman, Hill R., Software Engineering: Book Company, A Beginners Guide, pp. 1-93, McGraw- 1988. 3. Luqi, Rapid Prototyping for Large Software System Designs, Dissertation, University of Minnesota, Duluth, Minnesota, 1986. 4. Luqi, Berzins, V., "Rapidly Prototying Real-Time Systems," V. 5, pp. 25-36, September 1988. IEEE Software, 5. Luqi, Ketabchi, M., "A Computer Aided Protyping System," V. 5, pp. 66-72, March 1988. IEEE Software, 6. Janson, D., A Static Scheduler for the Computer Aided Prototyping System: An Implementation Guide, Master's Thesis, Naval Postgraduate School, Monterey, California, 7. Doctoral March 1988. O'Hern, T., A Conceptual Level Design for a Static Scheduler for Hard RealTime Systems, Master's Thesis, Naval Postgraduate School, Monterey, California, March 1988. 8. Naval Postgraduate School, Technical Report NPS52-88-009, Automated Translation from a Prototyping Language into Ada®, by C. Moffitt, II, and Luqi,pp. 7-10, April 1988. 9. The Mitre Corporation, Guidelines for Designing User Interface Software, U.S. Department of Commerce, National Technical Information Service, August 1986. 10. Dumas, 11. Teitelbaum, T., and Reps, T., "The Cornell Program Synthesizer: A SyntaxDirected Programming Environment," Connunications of the ACM, v. 24:9, pp. 563-573, September 1981. J., Designing User Interfaces for Software, Prentice-Hall, 1988. 75 C and Languages, pp. 155-157, Plenum Press, 1986. 12. Shi-Kuo, 13. Sun Microsystems, Doing More with UNIX: Beginner's Guide, pp. 123-149, others, Visual 1986. 14. Thorstenson, R., A Graphical Editor for the Computer Aided Prototyping System (CAPS), Master's Thesis, Naval Postgraduate School, Monterey, California, 15. Galik, D., December 1988. A Conceptual Design of a Software Base Management System for the Thesis, Naval Postgraduate Computer Aided Prototyping System, Master's School, Monterey, California, December 1988. 16. Altizer, C, Implementation of a Language Translator for a Computer Aided Prototyping System, Master's Thesis, Naval Postgraduate School, Monterey, California, 17. December 1988. Wood, M., An Execution Support System for Rapid Prototyping, Master's December 1988. Thesis, Naval Postgraduate School, Monterey, California, L., A Scheduler for Critical Timing Constraints, Master's Thesis, Naval Postgraduate School, Monterey, California, December 1988. 18. Marlowe, 19. Department of Defense, Military Specification MIL-H-48655B, Human Engineering Requirements for Military Systems, Equipment and Facilities, 31 January 1979. 20. Department of the Navy, OPNAV NOTICE 5000, Navy Rapid Prototyping and the Research Development and Acquistion Process, 20 February 1988. 76 BIBLIOGRAPHY Barstow, D., and others, Interactive Programming Environments, McGraw-Hill Book Company, 1984. Department of Defense, Military Standard MIL-STD-1472C, Human Engineering Design Criteria for Military Systems, Equipment and Facilities, 1 September 1983. McDermid, J., Intergrated Project Support Environments, Peter Peregrinus Ltd., 1985. A Design of a Syntax-Directed Editor for CAPS, Master's Thesis, Naval Postgraduate School, Monterey, California, December 1988. Porter, S., Sanders, M., and McCormick, E., McGraw-HiU Book Company, Human 1987. 77 Factors in Engineering and Design, INITIAL DISTRIBUTION LIST 1 . Defense Technical Information Center Cameron Station Alexandria, 2. Library, VA 22304-6145 Code 0142 Naval Postgraduate School Monterey, CA 93943-5002 3. Commandant of the Marine Corps Code TE 06 Headquarters, U.S. Marine Corps Washington, 4. DC 20380-0001 Commanding General Marine Corps Research, Development and Acquistion Command (Code C2A) Attn. CAPT H.G. Raum, USMC Washington, DC 20380-0001 5. Office of Naval Research Office of the Chief of Naval Research CDR Michael Gehl, Code 1224 N. Quincy Street 800 Attn. Arlington, VA 22217-5000 6. Space and Naval Warfare Systems Attn. Dr. Knudsen, Code PD 50 Washington, DC 20363-5100 7. Ada Joint Command Program Office OUSDRE(R&AT) Pentagon Washington, 8. DC 20301 Naval Sea Systems Attn. CAPT Joel Command Crandall National Center #2, Suite Washington, DC 7N06 22202 78 9. Office of the Secretary of Defense Attn. CDR Barber STARS Program Office DC 20301 Washington, 10. Office of the Secretar>' of Defense Attn. Mr. Joel Trimble STARS Program Office Washington, 11. DC Commanding 20301 Officer Naval Research Laboratory Code 5150 Attn. Dr. Elizabeth Washington, 12. DC Wald 20375-5000 Navy Ocean System Center Attn. Linwood Sutton, Code 423 San Diego, Califomia 92152-500 1 3. National Science Foundation Attn. Dr. William Washington, 14. DC Wulf 20550 National Science Foundation Division of Computer and Computation Research Attn. Dr. Peter Washington, 15. National Science Foundation Director, Atm. Dr. PYI Program C. Tan Washington, 16. Freeman 20550 DC DC 20550 Office of Naval Research Computer Science Division, Attn, Dr. Van Tilborg 800 N. Quincy Arlington, VA Code 1 133 Street 22217-5000 79 17. Office of Naval Research Applied Mathematics and Computer Science, Code 1211 Attn. Mr J. Smith 800 N. Quincy Arlington, 18. VA Street 22217-5000 Defense Advanced Research Projects Agency (DARPA) Integrated Strategic Technology Office (ISTO) Attn. MAJ Mark Pullen, USAF 1400 Wilson Boulevard VA 22209-2308 Arlington, 19. Defense Advanced Research Projects Agency Director, Naval Technology Office 1400 Wilson Boulevard Arlington, VA 2209-2308 20. National Science Foundation (DARPA) Director of Computer and Computation Research Attn. Dr. Tom Keenan Washington, DC 20550 21. Defense Advanced Research Projects Agency Director, Strategic Technology Office 1400 Wilson Boulevard Arlington, VA 2209-2308 (DARPA) 22. Defense Advanced Research Projects Agency (DARPA) Director, Prototype Projects Office 1400 Wilson Boulevard Arlington, VA 2209-2308 23. Defense Advanced Research Projects Agency Director, Tactical Technology Office 1400 Wilson Boulevard Arlington, VA 2209-2308 24. COL C. JCS Cox, USAF (J-8) Nuclear Force Analysis Division Pentagon Washington, DC 20318-8000 80 (DARPA) 25. LTCOL Kirk Lewis, USA JCS (J-8) Nuclear Force Analysis Division Pentagon Washington, DC 20318-8000 26. U.S. Air Force Systems Command Rome Air Development Center A. DiNitto, 13441-5700 Griffis Air Force Base, RADC/COEAttn. Mr. Samuel NY 27. U.S. Air Force Systems Command Rome Air Development Center RADC/COE Attn. Mr. William E. Rzepka NY 13441-5700 Griffis Air Force Base, 28. Professor Luqi Code 52LQ Naval Postgraduate School Computer Science Department Monterey, CA 93943-5000 81 Jr. Thesis R245235 c.l Rauffi Detiign and implementation of an expert user interface for the Computer Aided Prototyping System. ;j$/