The concurrency models of Ada and occam—a practical comparison

A comparison of the concurrency models of Ada and occam is presented. This comparison is performed in terms of an Ada-to-occam compiler. A subset of the Ada programming language may be compiled allowing a study of how programs and algorithms expressed using the Ada concurrency model can be mapped to the occam concurrency model. The resultant occam code may then be executed on a transputer. This paper describes the Ada and occam concurrency models, highlights the major differences between them, discusses the problems encountered in trying to map concurrent Ada programs to equivalent occam programs as a result of these differences and explains how these problems were overcome in the present compiler.     

Structured FORTRAN preprocessors generating optimized output

Usually a structured FORTRAN program is transformed into a standard FORTRAN program by means of a one-pass preprocessor. In this case, several problems are caused by the many redundant continue and goto statements that a preprocessor generates. These problems include: (i) the generated FORTRAN program is not easy to read; (ii) the size of files to store the related programs becomes large; (iii) the total time increases for executing both the FORTRAN compiler and the output program itself. This paper presents a new scheme for constructing a one-pass preprocessor that generates the optimized FORTRAN code by suppressing the redundant statements. By employing this scheme we have constructed our own preprocessors for Westran (one of the Structured FORTRAN languages) and Ratfor and measured these against the traditional preprocessors for the Westran and Ratfor languages. One of the results is as follows. The total time for users, namely ‘preprocessing time + FORTRAN compiling time’ is rather less than the traditional ones. This is due to the fact that to suppress the input/output of the redundant statements from/to files contributes to the decreasing of both preprocessing and compiling times, and this compensates completely the time-overhead of the optimization process.     

Distributing concurrent Ada programs by source translation

This paper tackles the practical aspects of obtaining a distributed version of an Ada program. It proposes the use of an adapter, which can be a methodology or an automatic translator. The adapter accepts source of a concurrent Ada program, adds communication and control tasks, and produces source for a single distributed Ada program, which can then be compiled and run on a multi-processor computer. The original program can consist of packages and tasks, and both of these can be classed as virtual nodes. The process of adaption does not alter the contents of any package in the original program, so that the method is directly applicable to systems that make use of library and generic packages. The communication between virtual nodes, which would normally reside as one per processor, is via messages on a ring, but the protocols are kept as simple as possible, and the messages are fully checked Ada types, rather than byte strings. The method has been applied to programs of the client-server model, and could be adapted for other rendezvous-based languages such as occam.     

Computer generation of robot dynamics equations and the related issues

Two programs have been developed using the computer algebra system REDUCE to generate the dynamics equations of motion for robot manipulators. One of these programs is based on a Lagrange formulation and the other utilizes a recursive Newton-Euler formulation. Both programs produce equivalent scalar symbolic expressions for the generalized actuator forces, but the program based on the recursive Newton-Euler formulation is more efficient for the generation of equations. These programs have been used to generate the dynamics equations of manipulators with as many as six degrees of freedom. The efficiency of computing forces using the generated scalar symbolic expressions is compared with the efficiency of a numerical algorithm (implemented in FORTRAN '77) based on the recursive Newton-Euler formulation. Force computation by the method of symbolic equations is shown to be more efficient than the numerical recursive Newton-Euler algorithm. The technique of symbolic equations is also better adapted to multi-CPU processing.     

Specifying Ada server tasks with executable formal grammars

The author shows how a class of concurrent programming problems can be specified with formal grammars. These grammars, more powerful than path expressions, translate readily into Ada server tasks using the rendezvous and select-statement, though they may also be applied to other synchronization constructs. The grammars may be used to clarify informal specifications, to compare different specifications, and to analyze the behavior of implementations of such specifications. They may also be easily converted into Prolog programs that can be executed to generate the strings of events accepted by a grammar or by the Ada task being modeled. The automated translation from Ada to such grammars, and from grammatical specifications to Ada is discussed. The former facilitates the analysis of Ada programs; the latter yields Ada code of high quality     

ARTK-M2: A kernel for Ada tasking requirements: An implementation and an automatic generator

A run-time kernel, ARTK-M2, supporting Ada tasking semantics is discussed; full support for task creation, synchronization, communication, scheduling, and termination is provided, together with all options of the Ada rendezvous. An implementation in Modula-2 is presented and a method for automatically translating Ada programs into semantically equivalent Modula-2 programs with corresponding kernel calls is introduced. A parser generator and an attribute grammar were used for the automatic translation. A subset of the Ada Compiler Validation Capability was processed to test the implementation and to illustrate the translation mechanism. The kernel is applicable to the study of real-time control systems; it can also serve as a baseline for studying implementation alternatives of Ada concepts, such as new scheduling algorithms, and for analysing new language constructs. Work is under way to implement some of the changes to the Ada tasking model being proposed as a result of the language revision (Ada9X). Finally, through proper extensions, ARTK-M2 can form an integral part of programming tools such as an Ada compilation system and a distributed kernel for multi-processing environments.     

Monitoring for Deadlock and Blocking in Ada Tasking

We present a deadlock monitoring algodrithm for Ada tasking programs which is based on transforming the source program. The transformations introduce a new task called the monitor, which receives information from all other tasks about their tasking activities. The monitor detects deadlocks consisting of circular entry calls as well as some noncircular blocking situations. The correctness of the program transformations is formulated and proved using an operational state graph model of tasking. The main issue in the correctness proof is to show that the deadlock monitor algorithm works correctly without having simultaneous information about the state of the program. In the course of this work, we have developed some useful techniques for programming tasking applications, such as a method for uniformly introducing task identifiers. We argue that the ease of finding and justifying program transformations is a good test of the generality and uniformity of a programming language. The complexity of the full Ada language makes it difficult to safely apply transformational methods to arbitrary programs. We discuss several problems with the current semantics of Ada's tasks.     

Concurrent Ada dead statements detection

In a concurrent environment, due to schedule, race conditions and synchronisation among concurrent units, some program statements may never be executed. Such statements are dead statements and have no influence on the programs except making them more difficult to analyse and understand. Since the execution of concurrent programs is non-deterministic, it is hard to detect dead statements. In this paper, we develop a data flow approach to detect dead statements for concurrent Ada programs. In this method, concurrent Ada programs are represented by concurrent control flow graphs in a simple and precise way, and detecting rules are extracted by analysing program behaviours. Based on these rules, a dead statement detecting algorithm is proposed.     

Measurement of language-supported reuse in object-oriented and object-based software

A major benefit of object-oriented software development is the support for reuse provided by object-oriented and object-based languages. Yet, measures and measurement tools that quantify such language-supported reuse have been lacking. Comprehensive reuse measures, particularly for reuse with modifications, are necessary to evaluate the status of reuse in an organization and to monitor improvements. We develop a set of measurable reuse attributes appropriate to object-oriented and object-based systems and a suite of measures that quantify these attributes. One of our major objectives is to measure reuse in software written in the object-based language Ada. A set of suitable primitive reuse measures are expressed in Ada Reuse Tables. These tables support the flexible use of primitive measures in programs with nested packages and subprograms, and Ada generic packages. We designed and implemented a prototype Ada Reuse Measurement Analyzer (ARMA) to generate measurement values from Ada programs. ARMA produces a reuse data representation and a corresponding forest representation of an Ada system that contain the information necessary to produce the primitive measures. Developers can use the representations to produce customized reports to satisfy a wide range of measurement goals. We use ARMA to measure primitive reuse attributes for a set of industrial Ada software. We also show that ARMA can be used to generate a set of component access and package visibility measures.     

Administrators and multiprocessor rendezvous mechanisms

This paper discusses rendezvous on multiprocessors. Three different approaches are compared, represented by three specific systems: Ada, Harmony and BNR Pascal. All three permit tasks to run on multiple processors and use blocking communications primitives, but there are significant differences. For example, control over replying to messages out of sequence and over the allocation of tasks to processors is omitted in Ada, but is available in Harmony. The approach represented by BNR Pascal follows a middle road between Harmony and Ada: a low level protocol, invisible to the programmer, is used to ensure communications reliability, but the programmer is aware of when a rendezvous is remote. If performance considerations and verbosity and robustness are ignored, all three approaches are equivalent. To illustrate this equivalence, and to demonstrate clearly the complexity of the Ada rendezvous, an Ada rendezvous administrator written using Harmony is described. A second method of adapting Harmony to Ada is also presented, in which the Harmony primitives are modified to be closer to Ada. In practice, using Harmony primitives directly will usually result in better programs. It is argued that something very much like the rendezvous adminstrator is needed for any actual implementation of the Ada rendezvous.     

Problems with determining package cohesion and coupling

The cohesion and coupling guidelines described by Yourdon, Constantine and Myers have proved useful aids for the design of modular programs. They have also provided direction for the evaluation of existing modules, pointing to those candidates for restructuring during perfective maintenance. For languages like Ada, where support for a higher-level of abstraction is provided in the form of a package, subprogram heuristics are inadequate. This paper examines existing guidelines and taxonomies for the Ada package and proposes extensions to these schemes. These package-level schemes are applied in a case study of an existing Ada program.     

Direct solution of large systems of linear equations

A very efficient computer subroutine for the direct solution of large numbers of simultaneous linear equations is presented. Basically the program uses Gauss elimination on positive-definite symmetrical systems. The specific features are that systems of very large size and bandwidth can be solved and that all operations on zero elements are eliminated. Also, the program is very simple and can be incorporated into existing programs with a minimum of effort. The amount of backup storage available on the computer used will govern the maximum size of the system which can be solved. A FORTRAN IV listing of the subroutine is given.     

Test-case generation with IOGen

The IOGen static-analysis tool for a subset of Ada addresses part of the problem of verification of software reliability. It uses a technique based on symbolic execution and produces a set of I/O pairs that represent execution paths through a program. The authors present IOGen's design and demonstrate how to use it to test programs and validate Ada software interfaces. Although IOGen is specific to an Ada subset, the same technique can be applied to any language with a grammar that uses a left-to-right scan with one look-ahead token producing a leftmost derivation (an LL(1) grammar)     

Extensions to the C programming language for enhanced fault detection

The acceptance of the C programming language by academia and industry is partially responsible for the ‘software crisis’. The simple, trusting semantics of C mask many common faults, such as range violations, which would be detected and reported at run-time by programs coded in a robust language such as Ada.

1 Ada is a registered trademark of the U.S. Government (Ada Joint Program Office)

This needlessly complicates the debugging of C programs. Although the assert macro lets programmers add run-time consistency checks to their programs, the number of instantiations of this macro needed to make a C program robust makes it highly unlikely that any programmer could correctly perform the task. We make some unobtrusive extensions to the C language which support the efficient detection of faults at run-time without reducing the readability of the source code. Examples of the extensions are automatic checking of error codes returned by library routines, constrained subtypes and detection of references to uninitialized and/or non-existent array elements.     

Analysis of parallelism in nested DO loops

The execution time of FORTRAN programs can be decreased by putting solutions to problems in their maximally parallel forms. The most important issue is the DO-loop. In this study nested DO-loops were considered and analysis of parallellism was performed on matrix multiplication using a PROLOG program. When processed by the AIDS system, the maximally parallel graph was produced. This indicates the number of processors that could be used in parallel to execute the FORTRAN program. The study shows that the maximally parallel program can run in considerably less time than that needed to run the original sequential FORTRAN program. N×N matrix multiplication programs are speeded up by a time-saving ratio that is always greater then (1:N²), but it cannot exceed (1:N³), since N³ is the maximum number of processors used in parallel at any time. These time-saving ratio evaluations assume that all operations have equal execution time and initialization overhead is ignored.     

程序潜在最大并行程度分析方法及其实现

现有的并行编译器不能充分地识别和开发程序潜在并行性。此文提出了一种新的程序最大并行度分析方法，这一方法可开发程序循环一级的并行性。     

Data dependency graphs for Ada programs

A compositional method of constructing data dependency graphs for Ada programs is presented. These graphs are useful in a program development environment for analyzing data dependencies and tracking information flow within a program. Graphs for primitive program statements are combined together to form graphs for larger program units. Composition rules are described for iteration, recursion, exception handling, and tasking, as well as for simpler Ada constructs. The correctness of the construction and the practicality of the technique are discussed     

Verifying general safety properties of Ada tasking programs

The isolation approach to symbolic execution of Ada tasking programs provides a basis for automating partial correctness proofs. The strength of this approach lies in its isolation nature; tasks are symbolically executed and verified independently, and then checked for cooperation where interference can occur. This keeps the verification task computationally feasible and enhances its compositionality. Safety, however, is a more appropriate notion of correctness for concurrent programs than partial correctness. The author shows how the isolation approach to symbolic execution of Ada tasking program supports the verification of general safety properties. Specific safety properties that are considered include mutual exclusion, freedom from deadlock, and absence of communication failure. The techniques are illustrated using a solution to the readers and writers problem