Search

Recent advances in technology have made the construction of general-purpose systems out of many small independent microprocessors feasible. One of the issues concerning distributed systems is the question of appropriate language constructs for the handling of communication and synchronization. In his paper, "Communicating sequential processes," Hoare has suggested the use of the input and output constructs and Dijkstra's guarded commands to handle these two issues. This paper examines Hoare's concepts in greater detail by concentrating on the following two issues: 1) allowing both input and output commands to appear in guards, 2) simple abstract implementation of the input and output constructs. In the process of examining these two issues we develop a framework for the design of appropriate communication and synchronization facilities for distributed systems. [ABSTRACT FROM AUTHOR]

Requirements engineering's continuing dependence on natural language description has made it the focus of several efforts to apply language engineering techniques. The raw textual material that forms an input to early phase requirements engineering and which informs the subsequent formulation of the requirements is inevitably uncontrolled and this makes its processing very hard. Nevertheless, sufficiently robust techniques do exist that can be used to aid the requirements engineer provided that the scope of what can be achieved is understood. In this paper, we show how combinations of lexical and shallow semantic analysis techniques developed from corpus linguistics can help human analysts acquire the deep understanding needed as the first step towards the synthesis of requirements. [ABSTRACT FROM AUTHOR]

A global checkpoint is a set of local checkpoints, one per process. The traditional consistency criterion for global checkpoints states that a global checkpoint is consistent if it does not include messages received and not sent. This paper investigates other consistency criteria, transitlessness, and strong consistency. A global checkpoint is transitless if it does not exhibit messages sent and not received. Transitlessness can be seen as a dual of traditional consistency. Strong consistency is the addition of transitlessness to traditional consistency. The main result of this paper is a statement of the necessary and sufficient condition answering the following question: "Given an arbitraiy set of local checkpoints, can this set be extended to a global checkpoint that satisfies P" (where P is traditional consistency, transitlessness, or strong consistency). From a practical point of view, this condition, when applied to transitlessness, is particularly interesting as it helps characterize which messages do not need to be recorded by checkpointing protocols. [ABSTRACT FROM AUTHOR]

A new approach for checkpointing and rollback recovery in a distributed computing system using a common time base is proposed in this paper. First, a common time base is established in the system using a hardware clock synchronization algorithm. This common time base is coupled with the idea of pseudo-recovery points to develop a checkpointing algorithm that has the following advantages: 1) reduced wait for commitment for establishing recovery lines, 2) fewer messages to be exchanged, and 3) less memory requirement. These advantages are assessed quantitatively by developing a probabilistic model. [ABSTRACT FROM AUTHOR]

In this paper, an approach to the modeling of software testing is described. A major aim of this approach is to allow the assessment of the effects of different testing (and debugging) strategies in different situations. It is shown how the techniques developed can be used to estimate, prior to the commencement of testing, the optimum allocation of test effort for software which is to be nonuniformly executed in its operational phase. In addition, the question of application of statistical models in cases where the data environment undergoes changes is discussed. Finally, two models are presented for the assessment of the effects of imperfections in the debugging process. [ABSTRACT FROM AUTHOR]

Basic error recovery problems between interacting processes are first discussed and the desirability of having separate recovery mechanisms for cooperation and competition is demonstrated. The paper then concentrates on recovery mechanisms for processes competing for the use of the shared resources of a computer system. Appropriate programming language features are developed based on the class and inner features of SIMULA, and on the structuring concepts of recovery blocks and monitors. [ABSTRACT FROM AUTHOR]

Design patterns are generic design solutions that can be applied and composed in different applications where pattern-related information is generally implicit in the Unified Modeling Language (UML) diagrams of the applications. It is unclear in which pattern instances each modeling element, such as class, attribute, and operation, participates. It is hard for a designer to find the design patterns used in an application design. Consequently, the benefits of design patterns are compromised because designers cannot communicate with each other in terms of the design patterns they used and their design decisions and trade-offs. In this paper, we present a UML profile that defines new stereotypes, tagged values, and constraints for tracing design patterns in UML diagrams. These new stereotypes and tagged values are attached to a modeling element to explicitly represent the role the modeling element plays in a design pattern so that the user can identify the pattern in a UML diagram. Based on this profile, we also develop a Web service (tool) for explicitly visualizing design patterns in UML diagrams. With this service, users are able to visualize design patterns in their applications and compositions because pattern-related information can be dynamically displayed. A real-world case study and a comparative experiment with existing approaches are conducted to evaluate our approach. [ABSTRACT FROM AUTHOR]

In this paper, we propose a means to enhance an architecture description language with a description of component behavior. A notation-used for this purpose should be able to express the "interplay" on the component's interfaces and reflect step-bystep refinement of the component's specification during its design. In addition, the notation should be easy to comprehend and allow for formal reasoning about the correctness of the specification refinement and also about the correctness of an implementation in terms of whether it adheres to the specification. Targeting all these requirements together, the paper proposes employing behavior protocols which are based on a notation similar to regular expressions. As proof of the concept, the behavior protocols are used in the SOFA architecture description language at three levels: interface, frame, and architecture. Key achievements of this paper include the definitions of bounded component behavior and protocol conformance relation. Using these concepts, the designer can verify the adherence of a component's implementation to its specification at runtime, while the correctness of refining the specification can be verified at design time. [ABSTRACT FROM AUTHOR]

Mathematical software is devoted to solve problems involving matrix computation and manipulation. The main problem limiting the reusability of existing mathematical software is the following: programs are often not initially designed for being reused. Therefore, it is hard to find programs that can be easily reused. In the first part of this paper, we give a programming methodology useful for designing and implementing reusable code. We name unit a portion of code designed and implemented for being reused. Our units are self-contained software components featuring a high degree of information hiding. This way of organizing software facilitates the reuse process and, furthermore, improves the understandability of units. To speed up the implementation process, a system supporting the reusability of units from an existing software library is particularly useful. In the second part of this paper, we report about an easy to use system of this kind. [ABSTRACT FROM AUTHOR]

RELAY is a model of faults and failures that defines failure conditions, which describe test data for which execution will guarantee that a fault originates erroneous behavior that also transfers through computations and information flow until a failure is revealed. This model of fault detection provides a framework within which other testing criteria's capabilities can be evaluated. In this paper, we analyze three test data selection criteria that attempt to detect faults in six fault classes. This analysis shows that none of these criteria is capable of guaranteeing detection for these fault classes and points out two major weaknesses of these criteria. The first weakness is that the criteria do not consider the potential unsatisfiability of their rules; each criterion includes rules that are sufficient to cause potential failures for some fault classes, yet when such rules are unsatisfiable, many faults may remain undetected. Their second weakness is failure to integrate their proposed rules; although a criterion may cause a subexpression to take on an erroneous value, there is no effort made to guarantee that the intermediate values cause observable, erroneous behavior. This paper shows how the RELAY model overcomes these weaknesses. [ABSTRACT FROM AUTHOR]

This paper examines several relations between software testing criteria, exploring whether for each relation R and each pair of criteria, C1 and C2, R(C1, C2) guarantees that C1 is better at detecting faults than C2 according to various probabilistic measures of fault-detecting ability. It is shown that the fact that C1 subsumes C2 does not guarantee that C1 is better at detecting faults. Relations that strengthen the subsumption relation and that have more bearing on fault-detecting ability are introduced. [ABSTRACT FROM AUTHOR]

The most important feature of visual languages is their ability to represent a user's mental concepts pictorially, thus providing for ease of learning and use. In order for this feature to be best exploited, there must be a close connection between the user's mental model of the application environment and the meaning of the icons in the system. Thus, a visual language must be accurately tuned to the application environment to which it is directed. This paper presents a system to generate and interpret customized visual languages in given application areas. The generation is highly automated. The user presents a set of sample visual sentences to the generator. The generator uses inference grammar techniques to produce a grammar that generalizes the initial set of sample sentences, and exploits general semantic information about the application area to determine the meaning of the visual sentences in the inferred language. The interpreter is modeled on an attribute grammar. A knowledge base, constructed during the generation of the system, is then consulted to construct the meaning of the visual sentence. The architecture of the whole system and its use in the application environment of visual text editing (inspired by the Heidelberg Icon Set) enhanced with file management features is reported. [ABSTRACT FROM AUTHOR]

A basic requirement for communication in a heterogeneous computing environment is a standard external data representation. Abstract Syntax Notation One (ASN.1) has been widely used in international standard specifications; its transfer-syntax, the Basic Encoding Rules (BER), is used as the external data representation. This paper presents a HER implementation called the ED library. The ED library includes a number of encoding and decoding routines that may be used as primitive functions to compose encoders and decoders for arbitrarily complicated ASN.1 data-types. Based on the ED library, an ASN.1-C compiler, called CASN1, is designed and implemented to free the protocol implementors from the arduous work of translating protocol-defined data-types and constructing their encoders and decoders. Given an ASN.1 protocol specification, CASNI automatically translates the input ASN.1 modules into C and generates the BER encoders and decoders for the protocol defined data-types. This paper discusses the CASN1 design principles, user interface, and some example applications. The performance of the ED library and generated CASN1 code is also measured and discussed. [ABSTRACT FROM AUTHOR]

In spite of their advantage in removing the overhead of lock maintenance and deadlock handling, optimistic concurrency control methods have continued to be far less popular in practice than locking schemes. There are two complementary approaches to help render the optimistic approach practically viable. For the high-level approach, integration schemes can be utilized so that the database management system is provided with a variety of synchronization methods each of which can be applied to the appropriate class of transactions. The low-level approach seeks to increase the concurrency of the original optimistic method and improve its performance. In this paper we examine the latter approach, and present algorithms that aim at reducing backups and improve throughput. Both the single-site and distributed networks are considered. Optimistic schemes using time-stamps for fully duplicated and partially duplicated database networks are presented, with emphasis on performance enhancement and on reducing the overall cost of implementation. Abstract-A methodology is presented for evaluating the performance of database update schemes in a distributive environment. The methodology makes use of the history of how data are used in the database. Parameters, such as update to retrieval ratio and average file size, can be set based on the actual characteristics of a system. The analysis is specifically directed toward the support of derived data within the relational model. Because concurrency is a major problem in a distributive system, the support of derived data is analyzed with respect to three distributive concurrency control techniques- master/slave, distributed, and synchronized. [ABSTRACT FROM AUTHOR]

This paper defines a family of program test data selection criteria derived from data flow analysis techniques similar to those used in compiler optimization. It is argued that currently used path selection criteria, which examine only the control flow of a program, are inadequate. Our procedure associates with each point in a program at which a variable is defined, those points at which the value is used. Several test data selection criteria, differing in the type and number of these associations, are defined and compared. [ABSTRACT FROM AUTHOR]

In the area of software development, data processing management often focuses more on coding techniques and system architecture than on how to manage the development. In recent years, "structured programming" and "structured analysis" have received more attention than the techniques software managers employ to manage. Moreover, these coding and architectural considerations are often advanced as the key to a smooth running, well managed project. This paper documents a philosophy for software development and the tools used to support it. Those management techniques deal with quantifying such abstract terms as "productivity," "performance," and "progress," and with measuring these quantities and applying management controls to maximize them. The paper also documents the application of these techniques on a major software development effort. [ABSTRACT FROM AUTHOR]

The properties of a capability-based protection mechanism to be incorporated in a language for concurrent programming axe presented. The protection mechanism is that abstractly characterized in terms of a protection model; the components of the protection mechanism, that is, the objects, subjects, and protection rules which govern the accessing to the objects by the subjects, are defined. The paper then concentrates on appropriate programming language features to specify how the protection mechanism may be embedded in an object-oriented programming language which allows an abstract data-type definition. In particular, it is shown how the protection rules can be implemented in the language so that a completely static access control to objects is obtained. [ABSTRACT FROM AUTHOR]

This paper describes Cola, an object-oriented command language for Hydra; Hydra is a capability-based operating system that runs on C.mmp, a tightly coupled multiprocessor. The two primary aspects of Cola, that it is a command language for Hydra, and that it is based on the object paradigm, are examined. Cola was designed to effect a correspondence between capabilities in Hydra and objects that are supported by the language. Cola is based on Smalltalk in that it uses message-passing as a control structure to allow syntactic freedom in the expression of commands to the system. Cola objects are arranged in a hierarchy, and the message-passing mechanism was designed to exploit this structure by automatically forwarding an unanswered message up the hierarchy. Two ramifications of this mechanism, automatic inheritance and shadowing, are discussed. An evaluation of the design decisions is also given. [ABSTRACT FROM AUTHOR]

Different approaches to the generation of test data are described. Error-based approaches depend on the definition of classes of commonly occurring program errors. They generate tests which are specifically designed to determine if particular classes of errors occur in a program. An error-based method called weak mutation testing is described. In this method, tests are constructed which are guaranteed to force program statements which contain certain classes of errors to act incorrectly during the execution of the program over those tests. The method is systematic, and a tool can be built to help the user apply the method. It is extensible in the sense that it can be extended to cover additional classes of errors. Its relationship to other software testing methods is discussed. Examples are included. Different approaches to testing involve different concepts of the adequacy or completeness of a set of tests. A formalism for characterizing the completeness or test sets that are generated by error-based methods such as weak mutation testing as well as the test sets generated by other testing methods is introduced. Error-based, functional, and structural testing emphasize different approaches to the test data generation problem. The formalism which is introduced in the paper can be used to describe their common basis and their differences. [ABSTRACT FROM AUTHOR]

In this paper an M/G/∞ queue is considered that receives a stream of numbered tasks. Results are derived concerning the probabilistic properties of the reordering done by the queue. [ABSTRACT FROM AUTHOR]

This paper is concerned with the formal specification of program modules which control access to resources shared among concurrent processes. The concept of stale space is defined for such program modules and the formal specification is given in terms of a program module invariant and input-output assertions defined on the state space. Examples are provided to illustrate the construction of specifications with this approach. [ABSTRACT FROM AUTHOR]

This paper discusses axiomatic and functional models of the semantics of structured programming. The models are presented together with their respective methodologies (or proving program correctness and for denying correct programs. Examples using these methodologies are given. Finally, the models are compared and contrasted. [ABSTRACT FROM AUTHOR]

This paper, which was initially prepared to accompany a series of lectures given at the 1978 NATO International Summer School on Program Construction, is primarily tutorial in nature. It begins by discussing in a general setting the role of type abstraction and the need for formal specifications of type abstractions. It then proceeds to examine in some detail two approaches to the construction of such specifications: that proposed by Hone in his 1972 paper "Proofs of Correctness of Data Representations," and the author's own version of algebraic specifications. The Hoare approach is presented via a discussion of its embodiment in the programming language Euclid. The discussion of the algebraic approach includes material abstracted from earlier papers as well as some new material that has yet to appear. This new material deals with parameterized types and the specification of restrictions. The paper concludes with a brief discussion of the relative merits of the two approaches to type abstraction. [ABSTRACT FROM AUTHOR]

This paper presents a method for automatically analyzing loops, and discusses why it is a useful way to look at loops. The method is based on the idea that there are four basic ways in which the logical structure of a loop is built up. An experiment is presented which shows that this accounts for the structure of a large class of loops. The paper discusses how the method can be used to automatically analyze the structure of a loop, and how the resulting analysis can be used to guide a proof of correctness for the loop. An automatic system is described which performs this type of analysis. The paper discusses the relationship between the structure building methods presented and programming language constructs. A system is described which is designed to assist a person who is writing a program The intent is that the system will cooperate with a programmer throughout all phases of work on a program and be able to communicate with the programmer about it. [ABSTRACT FROM AUTHOR]

The critical region construct can be usefully extended by adding region entry conditions and replacing the mutual exclusion restriction by a more general restriction. This paper discusses an extended construct of this nature, and presents an implementation approach based on Dijkstra's secretary process concept, with the code for the secretary process generated automatically during program compilation. This type of implementation can produce efficient solu- lions to many complex synchronization problems. It is also applicable in a wide range of hardware/software environments, including many existing systems. The use of the construct is demonstrated by a number of programming examples. [ABSTRACT FROM AUTHOR]

This editorial discusses selected articles about software management that appear in the July 1978 issue of "IEEE Transactions on Software Engineering". The manuscript was inspired by a series of seminars on software management organized by the American Institute of Aeronautics and Astronautics which addressed software management from the viewpoint of the U.S. Defense Department. The first paper manifests the theme of the seminar, that is the Department of Defense is launching a major effort to bring the management of software development under better control. Starting with this global view of the problem, the succeeding papers examine software management from the more restrictive viewpoints of the system developer within the framework of a major procurement agency, the program manager responsible for a system containing an embedded computer resource, and finally the system implementer who gambles his system expertise in an attempt to successfully develop a system on schedule and profit.

It is desirable to have Distributed Database Management System whose behavior and control is as identical as possible to that used in signel site database management systems. Preserving the autonomy of sites which join a DDBMS network is essential to the peace of mind of its managers and users, and more technically, is essential in an environment where sites and communication lines fail. Redundant copies in a distributed system provide locality of reference for reads and the potential for parallel processing.

The above paper' proposes a distributed query optimization algorithm called GENERAL. Lakhani and Wang [4] point out that the results obtained by the algorithm are not optimal. In this correspondence we point out another erroneous fact concerning the assumption of irreducibility of nonjoining attributes. We show that it is possible to generate an efficient semijoin programs with better response time than the one produced by the GENERAL algorithm. [ABSTRACT FROM AUTHOR]

Debugging often involves 1) finding the point of failure (the first statement that produces bad output) and 2) finding and fixing the actual bug. Print statements and debugger break points can help with step 1. Slicing the program back from values used at the point of failure can help with step 2. However, neither approach is ideal: Debuggers and print statements can be clumsy and timeconsuming and backward slices can be almost as large as the original program. This paper addresses both problems. We present callstack-sensitive slicing, which reduces slice sizes by leveraging the series of calls active when a program fails. We also show how slice intersections may further reduce slice sizes. We then describe a set of tools that identifies points of failure for programs that produce bad output. Finally, we apply our point-of-failure tools to a suite of buggy programs and evaluate callstack-sensitive slicing and slice intersection as applied to debugging. Callstack-sensitive slicing is very effective: On average, a callstack-sensitive slice is about 0.31 time the size of the corresponding full slice, down to just 0.06 time in the best case. Slice intersection is less impressive, on average, but may sometimes prove useful in practice. [ABSTRACT FROM AUTHOR]

The Pareto principle is often used to describe how faults in large software systems are distributed over modules. A recent paper by Andersson and Runeson again confirmed the Pareto principle of fault distribution. In this paper, we show that the distribution of software faults can be more precisely described as the Weibull distribution. [ABSTRACT FROM AUTHOR]

Abstract--Functional refinement is beneficial to Object-Oriented (OO) software development, especially for problems with more complex functions. However, the use of functional refinement in OO software development has not received much attention. This paper proposes an enhanced data flow diagram (DFD), called data flow net (DF net), for specifying use-cases through functional decomposition. It proposes a novel approach to complement existing OO software development methods with functional decomposition for realizing use-cases, especially those with more complex functions. In the requirements analysis stage, the proposed approach realizes use-cases through functional refinement and specifies them in DF nets. In the design and implementation stages, it transforms the DF nets systematically and precisely into OO design and implementation. The approach is amenable to automation and a prototype has been developed to support the transformation process. In the development of an OO system, it is seamless to realize some of the use-cases using the proposed approach and the remaining use-cases in the same target system using any existing OO software development methods. [ABSTRACT FROM AUTHOR]

Using design patterns is claimed to improve programmer productivity and software quality. Such improvements may manifest both at construction time (in faster and better program design) and at maintenance time (in faster and more accurate program comprehension). This paper focuses on the maintenance context and reports on experimental tests of the following question: Does it help the maintainer if the design patterns in the program code are documented explicitly (using source code comments) compared to a well-commented program without explicit reference to design patterns? Subjects performed maintenance tasks on two programs ranging from 360 to 560 LOC including comments. Both programs contained design patterns. The controlled variable was whether the use of design patterns was documented explicitly or not. The experiments thus tested whether pattern comment lines (PCL) help during maintenance if patterns are relevant and sufficient program comments are already present. It turns out that this question is a challenge for the experimental methodology: A setup leading to relevant results is quite difficult to find. We discuss these issues in detail and suggest a general approach to such situations. The experiment was performed with Java by 74 German graduate students and then repeated with C++ by 22 American undergraduate students. A conservative analysis of the results supports the hypothesis that pattern-relevant maintenance tasks were completed faster or with fewer errors if redundant design pattern information was provided. Redundant means that the information carried in pattern comments is also available in different form in other comments. The contribution of this article is twofold: It provides the first controlled experiment results on design pattern usage and it presents a solution approach to an important class of experiment design problems for experiments regarding documentation. [ABSTRACT FROM AUTHOR]

This paper describes the design and implementation of an intelligent tutoring system for the Dijkstra-Gries programming methodology as defined by Cries in "The Science of Programming"[12]. The first part of the paper identifies the requirements of intelligent tutoring systems in general and those of the methodology in particular. It shows the suitability of the Smalltalk environment for developing expandable intelligent systems and the compatibility of Smalltalk's object-oriented paradigm with the Gries methodology's goal/plan approach to programming. We then describe how these requirements are met: an overview of the system's support of the methodology and the modules that enable the system to respond intelligently. As an example, a reusable tutorial part is presented, first from a student's perspective, then from an author's perspective. Finally the results of an evaluation of the system drawn from actual student experience are presented. [ABSTRACT FROM AUTHOR]

This paper discusses the problems that a software development organization must address in order to assess and improve its software processes. In particular, the authors are involved in a project aiming at assessing and improving the cur- rent practice and the quality manual of the Business Unit Telecommunications for Defense (BUTD) of a large telecommunications company. The paper reports on the usage of formal process modeling languages to detect inconsistencies, ambiguities, incompleteness, and opportunities for improvement of both the software process and its documentation. [ABSTRACT FROM AUTHOR]

The selection of appropriate test cases is an important issue for conformance testing of protocol implementations as well as in software engineering. A number of methods are known for the selection of a test suite based on the specification of the implementation under test, assumed to be given in the form of a finite state machine. This paper presents a new method which provides a logical link between several of the known methods. Called the "partial W method," it has general applicability, full fault-detection power, and yields shorter test suites than the W method. The second part of the paper discusses various other issues which have an impact on the selection of a suitable test suite. This includes the consideration of interaction parameters, various test architectures for protocol testing, and the fact that many specifications do not satisfy the assumptions made by most test selection methods, such as complete definition, a correctly implemented reset function, a limited number of states in the implementation, and determinism. [ABSTRACT FROM AUTHOR]

This paper proposes a new lower bound on the number of processors and finish time for the problem of scheduling precedence graphs with communication costs. An algorithm (ETF) has been proposed by Hwang [1] for scheduling precedence graphs In systems with interprocessor communication limes. In this paper the notion of the earliest starting time of a task is formulated for the context of lower bounds. A lower bound on the completion time is proposed. A task delay which does not increase the earliest completion time of a schedule is defined. Each task can then be scheduled within a time interval without affecting the lower bound performance on the finish time. This leads to definition of a new lower bound on the number of processors required to process the task graph. A derivation of the minimum time increase over the earliest completion time is also proposed for the case of smaller number of processors. Finally the paper proposes a lower bound on the minimum number of interprocessor communication links required to achieve optimum performance. Evaluation has been carried out by using a set of 360 small graphs. The bound on the finish time deviates at most by 5% from the optimum solution in 96% of the cases and performs well with respect to the minimum number of processors and communication links. [ABSTRACT FROM AUTHOR]

In the event-action model of interactions between the debugging system and the program being debugged, an event will occur on the evaluation of a conditional defined in terms of the program activity if the evaluation yields the value true, and an action is an operation performed by the debugging system on the occurrence of an event. This paper presents a set of mechanisms for expressing conditionals at different levels of abstraction. At the lowest level, we have the simple conditionals, which can be expressed in terms of the values of the pro- gram entities and of the execution of the program statements. Simple conditionals can be grouped to form higher-level compound conditionals, which can be expressed in terms of the state and flow histories. The paper shows that the proposed abstraction mechanisms are powerful tools for monitoring program activity. They adequately support different debugging techniques, and offer the user a considerable degree of control over the debugging experiment. [ABSTRACT FROM AUTHOR]

SLAN-4 ("Software Language-4") was developed to meet the need for a formal tool for specifying and designing large software systems. It provides language constructs for algebraic and axiomatic specifications and also pseudocode constructs for the design step. A major design goal was to ease subsequent refinements of a (given) specification. The design can start with a very informal specification, which can be implemented later using lower level concepts. This paper gives an overview of the SLAN-4 syntax and semantics. It concentrates on the most important aspects of: • abstract data types, • algebraic specification of abstract data types, and • axiomatic specification of modules. Because the pseudocode part of SLAN-4 consists mainly of control structures similar to those in modern high-level programming languages, this element of the language is not separately described. The paper includes an example of how to use SLAN-4, and also the experiences gained in using the language to formally specify a real-world software product of about 18 000 lines of code written in an IBM internal high-level language. [ABSTRACT FROM AUTHOR]

We explain why pre-run-time scheduling is essential if one wishes to guarantee that timing constraints will be satisfied in a large complex hard-real-time system. We examine some of the major concerns in pre-run-time scheduling and consider what formulations of mathematical scheduling problems can be used to address those concerns. This paper provides a guide to the available algorithms. [ABSTRACT FROM AUTHOR]

Diagrams play a central role in software engineering. They are used for specifying design elements such as requirements, concurrent systems, database models and interactive systems. Families of diagrams form visual languages, and creating such diagrams constitutes visual programming. The Visual Programmer's WorkBench (VPW) addresses the rapid synthesis of programming environments for the specification, analysis, and execution of visual programs. A language-based environment for a specific visual language is generated in VPW from a specification of the syntactic structure, the abstract structure, the static semantics and the dynamic semantics of the language. VPW is built around a model of distributed processing based on shared distributed memory. This framework is used both in defining the architecture of the environment and for the execution model of visual languages. The Visual Programmer's WorkBench has been used to experiment with visual programming environments for several visual languages. This paper describes the design of the Visual Programmer's WorkBench and our experience using it to generate a distributed programming environment for a concurrent visual language. [ABSTRACT FROM AUTHOR]

This paper describes the Penelope verification editor and its formal basis. Penelope is a prototype system for the interactive development and verification of programs that are written in a rich sub- set of sequential Ada. Because it generates verification conditions incrementally, Penelope can be used to develop a program and its correctness proof in concert. If an already-verified program is modified, one can attempt to prove the modified version by replaying and modifying the original sequence of proof steps. Verification conditions are generated by predicate transformers whose logical soundness can be proven by establishing a precise formal connection between predicate transformation and denotational definitions in the style of continuation semantics. Penelope's specification language, Larch/Ada, belongs to the family of Larch interface languages. It scales up properly, in the sense that we can demonstrate the soundness of decomposing an implementation hierarchically and reasoning locally about the implementation of each node in the hierarchy. [ABSTRACT FROM AUTHOR]

This paper gives a formal specification of three base Avalon/C++ classes; recoverable, atomic, and subatomic. Programmers derive from class recoverable to define persistent objects, and from either class atomic or class subatomic to define atomic objects. The specifications, written in Larch, provide the means for showing that classes derived from the base classes implement objects that are persistent or atomic, and thus exemplify the applicability of an existing specification method to specifying "nonfunctional" properties. Writing these format specifications for Avalon/C++'s built-in classes has helped to clarify places in the programming language where features interact, to make unstated assumptions explicit, and to characterize complex properties of objects. [ABSTRACT FROM AUTHOR]

This paper addresses the problem of the dependability validation of fault-tolerant computing systems and more specifically the validation of the fault-tolerance mechanisms. The presented approach is based on the use of fault-injection at the physical level on a hardware/software prototype of the considered system. The place of this approach in a validation directed design process, as well as its place with respect to related works on fault-injection, is clearly identified. The major requirements and problems related to the development and application of a validation methodology based on fault injection are presented and discussed. Emphasis is put on the definition, analysis, and use of the experimental dependability measures that can be obtained. The proposed methodology has been implemented through the realization of a general pin-level fault injection tool (MESSALINE) and its usefulness is demonstrated by the application of MESSALINE to the experimental validation of two systems: 1) a subsystem of a centralized computerized inerlocking system for railway control applications and 2) a distributed system corresponding to the current implementation of the dependable communication system of the ESPRIT Delta-4 Project. [ABSTRACT FROM AUTHOR]

Essentially all program translators (both source-to-source translators and compilers) operate via transliteration and refinement. The source program is first transliterated into the target language on a statement-by-statement basis. Various refinements are then applied in order to improve the quality of the output. Although acceptable in many situations, this approach is fundamentally limited in the quality of the output it can produce. In particular, it tends to be insufficiently sensitive to global features of the source program and too sensitive to irrelevant local details. This paper presents an alternate translation paradigm-abstraction and reimplementation. Using this paradigm, the source program is first analyzed in order to obtain a programming-language-independent abstract understanding of the computation performed by the program as a whole. The program is then reimplemented in the target language based on this understanding. The key to this approach is the abstract understanding obtained. It allows the translator to see the forest for the trees, benefiting from an appreciation of the global features of the source program without being distracted by irrelevant details. Translation via abstraction and reimplementation is one of the goals of the Programmer's Apprentice project. A translator which translates Cobol programs into Hibol (a very-high-level business data processing language) has been constructed. A compiler which generates extremely efficient PDP-11 object code for Pascal programs has been designed. Currently, work is proceeding toward the implementation of a general-purpose, knowledge-based translator. [ABSTRACT FROM AUTHOR]

The IC* project is an effort to create an environment for the design, specification, and development of complex systems such as communication protocols, parallel machines, and distributed systems. The basis of this work is the IC* model of parallel computation. In this model, a system is specified by a set of invariant expressions which describe its behavior in time. The novel features of the model include temporal and structural constraints, inherent parallelism, explicit modeling of time, nondeterministic evolution, and dynamic activation. The project also includes the construction of a parallel computer specifically designed to support the model of computation. The model of computation, the status of the project, and the user environment are the content of this paper. [ABSTRACT FROM AUTHOR]

Data flow diagram process decomposition, as applied in the analysis phase of software engineering, is a top-down method that takes a process, and its input and output data flows, and logically implements the process as a network of smaller processes. As used today, the decomposition is performed in an ad hoc manner by an analyst applying heuristics, expertise, and knowledge to the problem. An algebra that formalizes process decomposition is presented using the De Marco representation scheme. In this algebra, the analyst relates the disjoint input and output sets of a single process by specifying the elements of an input/output (I/O) connectivity matrix. A directed acyclic graph is constructed from the matrix and is the decomposition of the process. The paper discusses the graph basis, grammar, matrix, and graph interpretations, and the operators of the algebra. A decomposition procedure for applying the algebra, prototype, and production tools and outlook are also discussed. [ABSTRACT FROM AUTHOR]

Dynamic system configuration is the ability to modify and extend a system while it is running. The facility is a requirement in large distributed systems where it may not be possible or economic to stop the entire system to allow modification to part of its hardware or software. It is also useful during production of the system to aid incremental integration of component parts, and during operation to aid system evolution. The paper introduces a model of the configuration process which permits dynamic incremental modification and extension. Using this model we determine the properties required by languages and theft execution environments to support dynamic configuration. CONIC, the distributed system which has been developed at Imperial College with the specific objective of supporting dynamic configuration, is described to illustrate the feasibility of the model. [ABSTRACT FROM AUTHOR]

How can a program written in pure applicative LISP be reused in a Fortran environment? One answer is by automatically transforming it from LISP into Fortran. In this paper we discuss a practical application of this technique-one that yields an efficient Fortran program. We view this process as an example of abstract programming, in which the LISP program constitutes an abstract specification for the Fortran version. The idea of strategy—a strategy for getting from LISP to Fortran—is basic to designing and applying the transformations. One strategic insight is that the task is easier if the LISP program is converted to "recursive" Fortran, and then the recursive Fortran program is converted to nonrecursive standard Fortran. Another strategic insight is that much of the task can be accomplished by converting the program from one canonical form to another. Developing a strategy also involves making various implementation decisions. One advantage of program transformation methodology is that it exposes such decisions for examination and review. Another is that it enables optimizations to be detected and implemented easily. Once a strategy has been discovered, it can be implemented by means of rewrite-rule transformations using the TAMPR program transformation system. The transformational approach to program reuse based on this strategy has a measure of elegance. It is also practical—the resulting Fortran program is 25 percent faster than its compiled LISP counterpart, even without extensive optimization. [ABSTRACT FROM AUTHOR]

This paper presents a recognition procedure for parallel tasks in the user program written in a conventional programming language. To establish our program model, it describes the parallelism of the program in terms of a process flow graph in which the relationships among processes are of predecessors and successors. And finally it presents a parallel processing scheme which realizes automatically the recognition of parallel tasks and schedules these tasks for parallel execution. [ABSTRACT FROM AUTHOR]

We are concerned with languages in which the programmer has explicit control over the referencing environment of a name. Several modern programming languages, including Ada, Euclid, Mesa, and Modula, implement these control capabilities. This paper describes a simple technique which uses the traditional concepts of a hashed symbol table and lexical level to solve many of the symbol table implementation problems associated with explicit scope control. The primary advantage of this technique is that a single symbol table abstraction can be used to simply and efficiently solve most problems in scope control. [ABSTRACT FROM AUTHOR]