Search

With growing interest in distributed computing come demands for techniques to aid in development of correct and reliable distributed software. Controlling, or at least recognizing, complexity of such software is an important part of the development and maintenance process. While a number of metrics have been proposed for quantitatively measuring the complexity of sequential, centralized programs, corresponding metrics for distributed software are noticeable by their absence. Using Ada as a representative distributed programming language, this paper discusses some ideas on complexity metrics that focus on Ada tasking and rendezvous. Concurrently active rendezvous are claimed to be an important aspect of communication complexity. A Petri net graph model of Ada rendezvous is used to introduce a "rendezvous graph," an abstraction that can be useful in viewing and computing effective communication complexity. [ABSTRACT FROM AUTHOR]

It is being recognized that recent programming environments have made significant progress towards improving the programming process. In adhering to this goal of software engineering, this paper introduces a new basis for programming environments. This basis encourages development of software in fragments of various types, called fragtypes. Fragtypes range from a simple expression type to a complete subsystem type. As a result, they are suited to the development of software in an enlarged scope that includes both programming in the small and programming in the large; The paper shows how new proposed operations on fragtypes can achieve unusual effects on the software development process. Fragtypes and their associated construction rules form the basis of the programming environment MUPE- 2, which is currently under development at McGill University. The target and the implementation language of this environment is the programming language Modula-2. [ABSTRACT FROM AUTHOR]

One of the best features of the UNIXTM Shell is that it provides a framework which can be used to build complex programs by interconnecting existing simple programs. However, it is limited to linear combinations of programs, and building of more complex programs must be accomplished by executing sequences of commands. This paper introduces Backus' FP (Functional Programming) as an alter- native command language for UNIX. In FP, programs are true functions and another distinctive feature of FP languages is that they contain functional forms, which are constructs for combining programs to build new programs. Also, the functional style of programming provides a natural way of exploiting parallel machine architecture. In this paper it is shown how to enhance the power of the UNIX Shell by the inclusion of the FP functional forms. The FP-Shell is fully implemented in "C" under UNIX. It interprets standard UNIX commands as FP primitive functions and standard UNIX files as FP system objects. It also serves as a framework for the study of functional programming languages. [ABSTRACT FROM AUTHOR]

In this paper, an integrated life-cycle model is presented for use in a software maintenance environment. This model, which represents information about the development and maintenance of software systems, emphasizing relationships between different phases of the software life cycle, provides the basis for automated tools to assist maintenance personnel in making changes to existing software systems. This model is independent of particular specification, design and programming languages because it represents only certain "basic" semantic properties of software systems: control flow, data flow, and data structure. The software development processes by which one phase of the software life cycle is derived from another are represented by graph rewriting rules, which indicate how various components of a software system have been implemented. This approach permits analysis of the basic properties of a software system throughout the soft- ware life cycle. Examples are given to illustrate the integrated software life-cycle model during evolution. [ABSTRACT FROM AUTHOR]

RTAG is a language based on an attribute grammar notation for specifying protocols. Its main design goals are: 1) to support concise and easily understood expression of complex real-world protocols, and 2) to serve as the basis of a portable software system for automated protocol implementation. This paper summarizes the RTAG language, gives examples of its use, sketches the algorithms used in generating implementations from these specifications, and describes a UNIX®-based automated implementation system for RTAG. [ABSTRACT FROM AUTHOR]

This paper presents a constructive approach to the problem of specifying, implementing, and verifying operations that will give concurrent processes exclusive access to a resource. The method eliminates the need for auxiliary variables and establishes the correctness of a whole class of solutions to the same problem. The solutions are derived directly from the specifications using a language construct called guarded regions. Several new solutions to well-known exclusion problems are presented. [ABSTRACT FROM AUTHOR]

Most current approaches to mechanical program verification transform a program and its specifications into first-order formulas and try to prove these formulas valid. Since the first-order predicate calculus is not decidable, such approaches are inherently limited. This paper proposes an alternative approach to program verification: correctness proofs are constructively established by proof justifications written in an algorithmic notation. These proof justifications are written as part of the program, along with the executable code and correctness specifications. A notation is presented in which code, specifications, and justifications are interwoven. For example, if a program contains a specification ∃x P(x), the program also contains a justification that exhibits the particular value of x that makes P true. Analogously, justifications may be used to state how universally quantified formulas are to be instantiated when they are used as hypotheses. Programs so justified may be verified by proving quantifier-free formulas. Additional classes of justifications serve related ends. Formally, justifications reduce correctness to a decidable theory. Informally, justifications establish the connection between the executable code and correctness specifications, documenting the reasoning on which the correctness is based. [ABSTRACT FROM AUTHOR]

This paper discusses general requirements for architecture definition languages, and describes the syntax and semantics of the subset of the Rapide language that is designed to satisfy these requirements. Rapide is a concurrent event-based simulation language for defining and simulating the behavior of system architectures. Rapide is intended for modelling the architectures of concurrent and distributed systems, both hardware and software. In order to represent the behavior of distributed systems in as much detail as possible, Rapide is designed to make the greatest possible use of event-based modelling by producing causal event simulations. When a Rapide model is executed it produces a simulation that shows not only the events that make up the model's behavior, and their timestamps, but also which events caused other events, and which events happened independently. The architecture definition features of Rapide are described here: event patterns, interfaces, architectures and event pattern mappings. The use of these features to build causal event models of both static and dynamic architectures is illustrated by a series of simple examples from both software and hardware. Also we give a detailed example of the use of event pattern mappings to define the relationship between two architectures at different levels of abstraction. Finally, we discuss briefly how Rapide is related to other event-based languages. [ABSTRACT FROM AUTHOR]

Distributed applications written in Hermes typically consist of a large number of sequential processes. The use of a hierarchy of process clusters can facilitate the debugging of such applications. Ideally, such a hierarchy should be derived automatically. This paper discusses two approaches to automatic process clustering, one analyzing runtime information with a statistical approach and one utilizing additional semantic information. Tools realizing these approaches were developed and a quantitative measure to evaluate process clusters is proposed. The results obtained under both approaches are compared, and indicate that the additional semantic information improves the cluster hierarchies derived. We demonstrate the value of automatic process clustering with an example. It is shown how appropriate process clusters reduce the complexity of the understanding process, facilitating program maintenance activities such as debugging. [ABSTRACT FROM AUTHOR]

We present a programming language called TCEL (Time-Constrained Event Language), whose semantics are based on time-constrained relationships between observable events. Such a semantics infers only those timing constraints necessary to achieve real-time correctness, without overconstraining the system. Moreover, an optimizing compiler can exploit this looser semantics to help tune the code, so that its worst-case execution time is consistent with its real-time requirements. In this paper we describe such a transformation system, which work$ in two phases. First, the TCEL source code is translated into an intermediate representation. Then an instruction- scheduling algorithm rearranges selected unobservable operations and synthesizes tasks guaranteed to respect the original event- based constraints. [ABSTRACT FROM AUTHOR]

The programming tradeoffs between structure-oriented and clause-oriented operations on data structures in Prolog are limited in current implementations of Prolog, because the assertion of clauses that include uninstantiated variables destroys any binding between these variables and those with which they are unified in the execution of the program. In this paper, we propose new built-in predicates for Prolog that allow us to assert predicate variable pointers, which are constants, rather than uninstantiated variables. We show: 1) the possible performance benefits of clause-oriented implementations of data structures over equivalent structure-oriented versions, 2) the logical implications of the proposed built-in predicates, and 3) their practical significance by integrating them in C-Prolog, and evaluating the two different implementations of the symbol table dictionary in Warren's Pseudo-Pascal Compiler example. [ABSTRACT FROM AUTHOR]

The development of correct specifications is a critical task in the software development process. This paper describes an alternative approach for the development of specifications. The approach relies on a specification language for abstract data types and a synthesis system. The system is capable of translating an abstract data type specification into an executable program. This process defines an alternative methodology that provides the necessary tools for the early testing of the specifications and for the development of prototypes and implementation models. [ABSTRACT FROM AUTHOR]

An interprocess communication facility provided by the kernel of the Gutenberg experimental operating system is presented. In Gutenberg all interprocess communication is via channels (ports) which are typed by the service which can be requested on them. Ports are created by reference to their service without using the identifier of the process providing the service, a technique we refer to as functional addressing. By using functional addressing, interprocess transfer of port use privileges, and the new concept of cooperation class introduced in this paper, arbitrary process interconnection topologies can be achieved without any explicit use of process identifiers by processes. We present examples of object sharing with abstract data type managers and data-driven protocols of database query execution to illustrate the methods of constructing systems of cooperating processes using the Gutenberg system. [ABSTRACT FROM AUTHOR]

A formal semantics of a prototyping language for hard real-time systems, PSDL, is given. PSDL provides a data flow notation augmented by application-orientation timing and control constraints to describe a system as a hierarchy of networks of processing units communicating via data streams. The semantics of PSDL is defined in terms of algebraic high-level Petri nets. This formalism combines algebraic specifications of abstract data types with process and concurrency concepts of Petri nets. Its data abstraction facilities are used to define the meaning of PSDL data types, while high-level Petri nets serve to model the casual and timing behavior of a system. The net model exposes potential concurrency of computation and makes all synchronization needs implied by timing and control constraints explicit and precise. Time is treated as state of clocks, and clocks are modeled as ordinary system components. The net semantics provides the basis for applying analysis techniques and semantic tools available for high-level Petri nets. [ABSTRACT FROM AUTHOR]

Genesis is a software-engineering-based programming environment geared to support big software projects. We first discuss a reusability-driven development methodology that advocates software development based on reusability considerations. Then, we discuss the tools and techniques provided in Genesis to support this methodology. We suggest techniques for improving the retrievability, composability, and understandability of software resources. Retrievability is improved by the use of the Entity Specification Language for tying resources through attributes and relations. Composability is improved through a mechanism called functional composition that provides considerably more generality than Unix® pipes for composing programs. Understandability is improved by the use of program abstractors. [ABSTRACT FROM AUTHOR]

Tinkertoy is a graphic interface to Lisp, where programs are "built" rather than written, out of icons and flexible interconnections. It is exciting because it represents a computer/user interface that can easily exceed the interaction speed of the best text-based language editors and command languages. It also provides a consistent framework for interaction across both editing and command execution. Moreover, because programs are represented graphically, structures that do not naturally conform to the text medium can be clearly described, and new kinds of information can be incorporated into pro- grams and program elements. [ABSTRACT FROM AUTHOR]

A preliminary example of program development demonstrates that the control-independent implementation of data types can lead to very inefficient code. The concept of a data space, which emphasizes the interaction between data and control structures, is introduced as a formal model of virtual machines. The model consists of three components: a state space X, an information structure F, and a control component p. Formally, X is a set of objects, F a set of functions with common domain X mapping the states to the value sets of certain data types, and p a partial function X → X. Two important. points of investigation are the characterization of state space structure and the mechanism of implementation. Good state description is characterized by "completeness" and "orthogonality." Either property plays a prominent role for the concept of implementation which, in turn, is formally defined as a mapping from a "virtual" space to a "real" space, via some "macro" space. These notions are illustrated by means of several examples from the area of programming languages. [ABSTRACT FROM AUTHOR]

A technique for syntactic error correction, called pattern mapping, is developed. A pattern is used to describe how to map or change one string into another. Using a preconstructed list of patterns, for each detected error, the first pattern with successful mapping is found and a correction is made based on this pattern. A new error-correction criterion, called minimum distance correction with k correct lookahead symbols, is presented. A measure on patterns is defined to reflect the costs of corrections obtained using patterns. Based on this measure, a list of patterns can be constructed for meeting the new criterion using pattern mapping. The implementation of pattern mapping correction on SLR(1) parsers is discussed. Heuristics for selecting the best correction and for recovering from the failure of pattern mapping are developed. Experimental results for a subset of Algol are summarized and discussed. [ABSTRACT FROM AUTHOR]