Search

This paper describes a knowledge-based approach to automate a software design method for concurrent systems. The approach uses multiple paradigms to represent knowledge embedded in the design method. Semantic data modeling provides the means to represent concepts from a behavioral modeling technique, called Concurrent Object-Based Real-time Analysis (COBRA), which defines system behavior using data/control flow diagrams. Entity-Relationship modeling is used to represent a design metamodel based on a design method, called Concurrent Design Approach for Real-Time Systems (CODARTS), which represents concurrent designs as software architecture diagrams, task behavior specifications, and module specifications. Production rules provide the mechanism for codifying a set of CODARTS heuristics that can generate concurrent designs based on semantic concepts included in COBRA behavioral models and on entities and relationships included in CODARTS design metamodels. Together, the semantic data model, the entity-relationship model, and the production rules, when encoded using an expert-system shell, compose CODA, an automated designer's assistant. Other forms of automated reasoning, such as knowledge-based queries, can be used to check the correctness and completeness of generated designs with respect to properties defined in the CODARTS design metamodel. CODA is applied to generate 10 concurrent designs for four real-time problems. The paper reports the degree of automation achieved by CODA. The paper also evaluates the quality of generated designs by comparing the similarity between designs produced by CODA and human designs reported in the literature for the same problems. In addition, the paper compares CODA with four other approaches used to automate software design methods. [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]

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]

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]

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]

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]

In most current locally distributed systems, the work generated at a node is processed there; little sharing of computational resources is provided. In such systems it is possible for some nodes to be heavily loaded while others are lightly loaded, resulting in poor overall system performance. The purpose of load sharing is to improve performance by redistributing the workload among the nodes. The load sharing policies with the greatest potential benefit are adaptive in the sense that they react to changes in the system state. Adaptive policies can range from simple to complex in their acquisition and use of system state information. The potential advantage of a complex policy is the possibility that such a scheme can take full advantage of the processing power of the system. The potential disadvantages are the overhead cost, and the possibility that a highly tuned policy will behave in an unpredictable manner in the face of the inaccurate information with which it inevitably will be confronted. The goal of this paper is not to propose a specific load sharing policy for implementation, but rather to address the more fundamental question of the appropriate level of complexity for load sharing policies. We show that extremely simple adaptive load sharing policies, which collect very small amounts of system state information and which use this information in very simple ways, yield dramatic performance improvements. These policies in fact yield performance close to that expected from more complex policies whose viability is questionable. We conclude that simple policies offer the greatest promise in practice, because of their combination of nearly optimal performance and inherent stability. [ABSTRACT FROM AUTHOR]

Over the last decade there has developed an acute awareness of the need to introduce abstraction and mathematical rigor into the programming process. This increased formality allows for the automatic manipulation of software, increasing productivity, and, even more importantly, the manageability of complex systems. Along these lines, attribute grammars constitute a formal mechanism for specifying translations between languages; from a formal description of the translation a translator can be automatically constructed. In this paper we consider taking this process one step further: given an attribute grammar specifying the translation from language L1 to language L2, we address the question of whether the inverse attribute grammar specifying the inverse translation from L2 to L1 can be automatically generated. We show how to solve this problem for a restricted subset of attribute grammars. This inversion process allows for compatible two-way translators to be generated from a single description. To show the practical feasibility of attribute grammar inversion, we relate our experience in inverting an attribute grammar used as an interface for a formal database accessing language, SQL. The attribute grammar is used to paraphrase SQL database queries in English. [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]

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]

A method for formal description of programming principles is presented in this paper. Programming principles, such as sequential search can be defined and proven even in the absence of an application. We represent a principle as a program scheme which has partially interpreted functions in it. The functions must obey certain input constraints. Use of these ideas in program proving is illustrated with examples. [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]

Shankar and Lam propose a projection method for protocol verification. They claim that the method guarantees the faithfulness of the safety and liveness properties of a protocol system. Although not clearly defined, "faithfulness" (as implied in many places in their article) means "the image protocol system is live (respectively, safe) if and only if the original protocol system is live (respectively, safe)." This paper shows that the "only if" part is not true for certain liveness properties and suggests a remedy. [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]