Safety verification of Ada programs using software fault trees

The software fault-tree analysis technique is explained. It is then extended to allow its use on a more complex language involving such features as concurrency and exception handling. Ada is used as the example language because many safety-critical projects are using or planning to use Ada. It also contains complex, real-time programming facilities found in other languages used in these types of projects. Software fault-tree analysis uses failure-mode templates to generate the fault tree. The templates provided can be used to define the procedures for applying the technique to programs written in most other declarative languages. To explain the use of the templates an example Ada program, for a traffic-light-control system, is analyzed. The cost and practicality of the method and its implications for software reuse are assessed. The application of the safety analysis procedures to requirements modeling and specification languages is considered     

Concurrent programming in the Ada® language: The polling bias

The rendezvous is an important concept in concurrent programming—two processes need to synchronize, i.e. rendezvous, to exchange information. The Ada programming language is the first programming language to use the rendezvous as the basis of its concurrent programming facilities. Our experience with rendezvous facilities in the Ada language shows that these facilities lead to and encourage the design of programs that poll. Polling is generally, but not always, undesirable because it is wasteful of system resources. We illustrate and examine the reasons for polling bias in the Ada language. We give suggestions on how to avoid polling programs, and suggest changes to the rendezvous facilities to eliminate the polling bias. The ramifications of these changes to the implementation of the Ada language are also discussed. Although we have focused on the rendezvous facilities in the Ada language our analysis is also applicable to other languages. A polling bias can occur in any concurrent programming language based on the rendezvous mechanism if it does not provide appropriate facilities.     

Facilitating Mixed Language Programming in Distrbuted Systems

An approach for facilitating mixed language programming in distributed systems is presented. It is based on adding a generic remote procedure call facility to each language, and the use of a type system to describe procedural interfaces, as well as data to be transferred between procedures. This type scheme also specifies a machine-independent representation for all data. By defining standard mappings for each programming language, the data conversions required for cross-langauge calls may be performed, automatically in most cases, by active agents that provide the interface between program components written in different languages. When necessary, explicit control of the conversation is possible. A prototype implementation of a system based on this approach has been constructed on a collection of machines running Berkeley UNIX®.     

A lingua franca for concurrent logic programming

Two of the more important concurrent logic programming languages with nonflat guards are GHC and Parlog. They balance the requirements of having clean semantics and providing good control facilities rather differently, and their respective merits are compared and contrasted. Since concurrent logic programming would benefit from both, but neither language is able to express all the programs expressible in the other language, a lingua franca of these languages is defined and justified. A method is given for translating GHC and Parlog to and from it. The method preserves the arities and execution conditions of each clause. It enables a lingua franca implementation to support both languages transparently, and to provide a simple concurrent logic programming language suitable for programming in its own right     

Correct and Robust Programs

The design of programs which are both correct and robust is investigated. It is argued that the notion of an exception is a valuable tool for structuring the specification, design, verification, and modification of such programs. The syntax and semantics of a language with procedures and exception handling are presented. A deductive system is proposed for proving total correctness and robustness properties of programs written in this language. The system is both sound and complete. It supports proof modularization, in that it allows one to reason separately about fault-free and fault-tolerant system properties. Since the programming languages considered closely resembles CLU or Ada, the presented deductive system is easily adaptable for verifying total correctness and robustness properties of programs written in these, or similar, languages.     

An architecture for processing graph-grammar applications

We propose a six-layer architecture for processing graph-grammar applications. The layers and the transformations between them are formally described and concepts for their implementation are given. Especially we introduce the syntax and semantics of a graph-grammar implementation language. Graph-grammar productions will be translated into programs of this language to have a basis for their implementation into programs written in commonly available programming languages.     

Mixed language programming

Subroutines for numerical computation have in the past been written mainly in Fortran and in Algol 60, whereas most programming in the future is expected to be in more advanced languages, for example in Ada. It seems to be a great waste if it will become necessary to convert all existing numerical software into the new languages. What is needed is a facility to include subroutines written in the old languages into programs being written in the newer languages. In this paper an automatic procedure to facilitate the use of mixed languages is suggested, the purpose of the paper is to indicate the desirability for providing the required facilities, and to encourage discussion and further research in the area of mixed language programming.     

A concurrent abstract interpreter

Abstract interpretation [6] has been long regarded as a promising optimization and analysis technique for high-level languages. In this article, we describe an implementation of aconcurrent abstract interpreter. The interpreter evaluates programs written in an expressive parallel language that supports dynamic process creation, first-class locations, list data structures and higher-order procedures. Synchronization in the input language is mediated via first-class shared locations. The analysis computes intra- and inter-threadcontrol anddataflow information. The interpreter is implemented on top of Sting [12], a multi-threaded dialect of Scheme that serves as a high-level operating system for modern programming languages.     

Performance of multi-tasking and synchronization mechanisms in the programming language SR

High-level language primitives for concurrent programming exist in languages such as Ada and Modula-2. However, each of these languages provides only a single means for specifying multitasking and synchronization, essential in the implementation of concurrent systems. The SR language provides several mechanisms for specifying multi-tasking and synchronization, so it can be used to explore the performance of various communication techniques. This paper presents performance results for SR's multi-tasking and synchronization mechanisms and discusses the effects of the generated code, the run-time support and the hardware on these results. These results are compared with those for similar mechanisms in other languages, leading to some general conclusions about the performance of process communication primitives. These performance results can be used by programmers to make design choices that allow systems programs written in high-level languages to meet real-time performance specifications.     

Aspects as Modular Language Extensions

Extensible programming languages and their compilers use highly modular specifications of languages and language extensions that allow a variety of different language feature sets to be easily imported into the programming environment by the programmer. Our model of extensible languages is based on higher-order attribute grammars and an extension called “forwarding” that mimics a simple rewriting process. It is designed so that no additional attribute definitions need to be written when combining a language with language extensions. Thus, programmers can remain unaware of the underlying attribute grammars when building customized languages by importing various extensions. In this paper we show how aspects and the aspect weaving process from Aspect-Oriented Programming can be specified as a modular language extension and imported into a base language specified in an extensible programming language framework.     

Static and Dynamic Characteristics of XPL Programs

One use of performance measurement techniques is in the study of operational characteristics of programs written in high-level programming languages. Information derived from such studies can be used to construct benchmark programs and synthetic workloads,^1,2detect inefficiencies in programming language implementation, and suggest possible improvements in the design of computers.^3,9,10Our main interest is in the latter area: the discovery of primitive operations, implied by the semantics of a programming language, that can be added to the firmware or hardware of a computer to improve overall system performance. These computer architecture optimization techniques have been applied in several studies^3,9and have been used commercially to design efficient pseudo machines for the Burroughs B1700.^10,12     

Event associations in SNOBOL4 for program debugging

An event association facility for the SNOBOL4 programming language is described. This facility permits the execution of a programmer-defined function to be associated with the occurrence of a specified event. The events with which associations can be made are those applicable to program debugging. Associations can be made with events such as variable referencing, statement execution, program interruption, function call and return, and execution-time errors. By making event associations available at the source-language level, debugging aids can be written in SNOBOL4 itself, using the full capabilities of that language. As illustrated by several examples, this approach facilitates the implementation of simple yet powerful debugging aids written in the same language as the programs to be debugged. Event associations provide a mechanism for the unification of the existing SNOBOL4 debugging facilities, and a basis for the addition of other events. The implementation of event associations is also described.     

CBack: A simple tool for backtrack programming in C

Backtrack programming is such a powerful technique for problem solving that a number of languages, especially in the area of artificial intelligence, have built-in facilities for backtrack programming. This paper describes CBack, a simple, but general tool for backtrack programming in the programming language C. The use of the tool is illustrated through examples of a tutorial nature. In addition to the usual depth-first search strategy, CBack provides for the more general heuristic best-first search strategy. The implementation of CBack is described in detail. The source code, shown in its full length, is entirely written in ANSI C and highly portable across diverse computer architectures and C compilers.     

Generic procedures: An implementation and an undecidability result

Modern programming languages allow the user to define new data types. This increases the desirability of having generic procedures as they reduce programming effort and program size, allow for portability across types and are a means of abstraction.

A simple but powerful notation for incorporating generic procedures in a language is proposed along with an efficient macro-like compile time technique for implementing them.

Unfortunately, pathological recursive procedure call sequences create an undecidability problem for the suggested implementation technique. A proof is given for the above undecidability problem and practical remedies for avoiding it are suggested.     

An electronic form system—an experience in prototyping

A prototype electronic form system was implemented to test the feasibility of a high level form definition mechanism. This mechanism is based on the concept of abstract data types in programming languages. This paper briefly discusses prototypes in general and describes the prototype electronic form system—specific objectives, design decisions, the implementation and evaluation. The prototype has proven invaluable in providing a better understanding of the facilities that should be included in a form definition language and of the implementation issues. Success of the prototype can be attributed to keeping prototype objectives in perspective throughout its implementation and ensuring that the objectives were not violated by any design decisions or implementation restrictions.     

Monaco—A domain-specific language solution for reactive process control programming with hierarchical components

In this paper, we present Monaco – a domain-specific language for developing event-based, reactive process control programs – and its visual interactive programming environment. The main purpose of the language is to bring process control programming closer to domain experts. Important design goals have therefore been to keep the language concise and to allow programs to be written that reflect the perceptions of domain experts. Monaco is similar to Statecharts in its expressive power, but adopts an imperative notation. Moreover, Monaco uses a state-of-the-art component approach with interfaces and polymorphic implementations, and enforces strict hierarchical component architectures that support hierarchical abstraction of control functionality. We present the main design goals, the essential programming elements, the visual interactive programming environment, results from industrial case studies, and a formal definition of the semantics of the reactive behavior of Monaco programs in the form of labeled transition systems.     

Linear programs in a simple reversible language

Very simple reversible programming languages can be useful for the study of reversible transformations. For this purpose we define simple reversible language (SRL), a very simple reversible language, and analyse its properties. The language SRL is similar to the “loop” languages that have been used by several authors to characterise the set of primitive recursive functions. There are, however, important differences: SRL has domain instead of and only reversible programs can be written in SRL. The reversibility of linear homogeneous SRL programs is related to the fact that the corresponding set of matrices has the algebraic structure of a group. We show that such programs implement exactly the linear transformations corresponding to the group of integer positive modular matrices, while in ESRL, an extended version of SRL, the set of transformations that can be implemented by linear homogeneous programs corresponds exactly to the group of integer modular matrices.     

Measuring the Performance and Behavior of Icon Programs

The importance of the ability to measure the performance of programs written in high-level languages is well known. Performance measurement enables users to locate and correct program inefficiencies where automatic optimizations fail and provides a tool for understanding program behavior. This paper describes performance measurement facilities for the Icon programming language, and shows not only how these facilities provided insight into program behavior, but also how they were used to improve the implementation.     

Broadcasting Sequential Processes (BSP)

Communication in a broadcast protocol multiprocessor (BPM) is inherently different from that in distributed systems formed by explicit links between processors. A message broadcast by a processor in a BPM is received directly by all other processors in the network instead of being restricted to only one processor. Broadcasting is an inexpensive way of communicating with a large number of processors on a BPM. In this paper I will describe a new approach to user-level distributed programming called broadcast programming, i.e., distributed programs written as cooperating broadcasting sequential processes (BSP). Existing concurrent programming languages do not provide facilities to exploit the broadcast capability of a BPM. The idea of distributed programs written as BSP is tailored to exploiting a BPM architecture but is not restricted to such an architecture-however, implementation of the broadcast capability may not be as efficient on other architectures. I will illustrate the utility and convenience of broadcast programming with many examples. These examples will also be used to explore the suitability and advantages of BSP and to determine appropriate facilities for BSP.     

SPiCE: a system for translating Smalltalk programs into a Cenvironment

Smalltalk-80 (hereafter referred to as Smalltalk), which is one of the most productive programming languages/environments, is very well suited for prototyping of applications but it is less well suited for delivering applications because applications can neither run in isolation from the Smalltalk environment nor be combined with other programs written in other languages. One way to make Smalltalk suitable for delivering applications is to translate Smalltalk into a compiler language such as C. By translating Smalltalk code into portable and interoperable C code, it is possible to deliver a stand-alone version of Smalltalk applications, and to develop an application partly in Smalltalk and partly in C. However, there are some difficulties in translating Smalltalk code into such a C code. First, the execution model of Smalltalk, which creates activation records as objects, is very different from that of C, and second, Smalltalk and C have very different approaches to storage management. We have implemented SPiCE, a system for translating Smalltalk into C. Our approach to the translation is to create runtime replacement classes implementing the same functionality of Smalltalk classes that are inherently part of the Smalltalk execution model, and to provide semi-conservative real-time compacting garbage collection that works without language support