A study of several metrics for programming effort

As the cost of programming becomes a major component of the cost of computer systems, it becomes imperative that program development and maintenance be better managed. One measurement a manager could use is programming complexity. Such a measure can be very useful if the manager is confident that the higher the complexity measure is for a programming project, the more effort it takes to complete the project and perhaps to maintain it. Until recently most measures of complexity were based only on intuition and experience. In the past 3 years two objective metrics have been introduced, McCabe's cyclomatic number v(G) and Halstead's effort measure E. This paper reports an empirical study designed to compare these two metrics with a classic size measure, lines of code. A fourth metric based on a model of programming is introduced and shown to be better than the previously known metrics for some experimental data.     

An experimental COBOL restructuring system

Although COBOL lacks many features required to support structured programming, it can be used to simulate reasonably well-structured programs. This simulation is particularly important for restructuring of poorly structured old programs. This paper describes the formulation of and experiments with a practical methodology for conversion of unstructured COBOL programs into reasonably well-structured equivalents. The discussion includes the overview of an automatic COBOL restructuring system, the results of an experiment with this system and an interpretation of these results.     

On program development effort and productivity

Many claims are made in the literature concerning large productivity increases as a result of the introduction of various new programming tools and techniques. Seldom do the researchers substantiate these claims, however. Further, many of the reported studies have been unsuccessful because much of the existing research is methodologically flawed and poorly grounded in theory. This paper investigates the methodological problems of previous studies and reports the results of a field study conducted to assess the feasibility of conducting controlled studies of the programming process. A field study of COBOL programs from three commercial organizations investigated the effects of programming style (i.e., structured programming) and programmer skill on (i) the effort required to develop programs and (ii) programming productivity; program size was used as a control variable. The results of the study support the underlying concept: that use of disciplined approaches and well-defined variables leads to more readily interpretable and more conclusive results.     

Complexity measures for rule-based programs

Software complexity measures are quantitative estimates of the amount of effort required by a programmer to comprehend a piece of code. Many measures have been designed for standard procedural languages, but little work has been done to apply software complexity concepts to nontraditional programming paradigms. This paper presents a collection of software complexity measures that were specifically designed to quantify the conceptual complexity of rule-based programs. These measures are divided into two classes: bulk measures, which estimate complexity by examining aspects of program size, and rule measures, which gauge complexity based on the ways in which program rules interact with data and other rules. A pilot study was conducted to assess the effectiveness of these measures. Several measures were found to correlate well with the study participants' ratings of program difficulty and the time required by them to answer questions that required comprehension of program elements. The physical order of program rules was also shown to affect comprehension. The authors conclude that the development of software complexity measures for particular programming paradigms may lead to better tools for managing program development and predicting maintenance effort in nontraditional programming environments     

Designing structured cobol programs

COBOL is now more than 20 years old and will probably survive to become much older. Since it has some features which are out of date it is desirable to adapt at least the program style to some standards of modern programming languages. The adaption is not only a matter of style but also of costs of program production and program maintenance. This paper presents constructional rules for programming in COBOL which by-pass some of the drawbacks and allow more readable and more maintainable program structures. Finally a postprocessor is presented, that allows verification of the chosen constructional rules and documentation of the resulting programs.     

A structured COBOL

A version of COBOL that permits structured programming was designed. It was implemented using a pre-processor that outputs standard COBOL. The pre-processor will indiscriminately run programs that are either structured or non-structured, or with very limited restrictions, programs with a mixture of both. A structured IF was included as a modification of the COBOL IF. In line looping was created with a redefinition of the PERFORM, maintaining all of its capabilities and adding a DO UNTIL. The PERFORM was also modified to allow a CASE construct. All new structures are completely nestable.     

A measure of logical complexity of programs

The research in software science has so far been concentrated on three measures of program complexity: (a) software effort; (b) cyclomatic complexity; and (c) program knots. In this paper we propose a measure of the logical complexity of programs in terms of the variable dependency of sequence of computations, inductive effort in writing loops and complexity of data structures.

The proposed complexity mensure is described with the aid of a graph which exhibits diagrammatically the dependence of a computation at a node upon the computation of other (earlier) nodes.

Complexity measures of several example programs have been computed and the related issues have been discussed. The paper also describes the role played by data structures in deciding the program complexity.     

Transformations to Restructure and Re–engineer COBOL Programs

In this paper we describe a COBOL-program restructuring tool currently under development. The tool is constructed using program transformations executed by the TAMPR program transformation system. We discuss the COBOL knowledge embodied in the transformations and how they restructure an example COBOL program developed in the mid–1970s. While the tool is not yet a robust commercial product, early use for restructuring COBOL programs demonstrates the power and flexibility of this transformation–based approach.     

A Complexity Measure

This paper describes a graph-theoretic complexity measure and illustrates how it can be used to manage and control program complexity. The paper first explains how the graph-theory concepts apply and gives an intuitive explanation of the graph concepts in programming terms. The control graphs of several actual Fortran programs are then presented to illustrate the correlation between intuitive complexity and the graph-theoretic complexity. Several properties of the graph-theoretic complexity are then proved which show, for example, that complexity is independent of physical size (adding or subtracting functional statements leaves complexity unchanged) and complexity depends only on the decision structure of a program.     

Resource monitors: A design methodology for operating systems

Resource manager objects are the operating system entities that manage computer system resources. In this paper we extend Hoare's and Brinch Hansen's monitor concept, and introduce a resource monitor language construct that represents a resource manager object. Resource monitors provide requesting processes with implicit synchronization, and do not require separate processes to perform the resource access operations. The resource monitor construct is compared to current language constructs used to structure operating system software. For this purpose we use an evaluation methodology that combines software complexity measurements with program performance measurements. The evaluation itself is carried out in a Concurrent Pascal-like programming environment. The current language constructs have a software complexity that is larger by 37 to 219 per cent over the resource monitor's complexity. The run-time synchronization overhead of programs that use current language constructs is 1.43 to 2.75 times higher than the overhead of programs that use a resource monitor.     

Computer education in times of recession: Should Pascal come first?

In recent years there has been a move towards making computer science courses more practical. In the current recession this seems even more important as employers can avoid candidates with an over-theoretical background.Pascal has become more popular in higher education as a first programming language to teach problem solving and structured programming. Structured programming is required in industry but there is evidence that the approach through Pascal is inadequate. Cognitive psychologists tell us that understanding the context of the problems to be solved is the key to problem solving. Pascal does not function within the commercial context. COBOL, on the other hand, does. By giving COBOL priority, students will gain an essential appreciation of the most common environment that they are likely to find themselves in at the end of their course. With the introduction of structured COBOL, they need not compromise on style either.     

An empirical study of COBOL programs via a style analyzer: The benefits of good programming style

Despite its prominence as the most widely used programming language in industry, there are only a small number of publications on software metrics applied to COBOL [1]. COBSTYLE, a one-pass, line-by-line style analyzer, written in PL/I, is used to analyze 638 COBOL programs. COBSTYLE differs from other style analyzers [2–4] in that it assesses penalty points for abuses in style, and considers to a larger degree, overall program structure. Mean style scores for 23 style characteristics are obtained. The data produced by COBSTYLE, together with programmer efficiency data, are statistically analyzed, yielding results which empirically demonstrate the benefits of good programming style. COBSTYLE scores are shown to have statistically significant correlations with the following:

1. (a) overall performance (as measured by students' final course grade)—at the 0.005 significance level;

2. (b) program correctness—at the 0.01 significance level;

3. (c) total debugging time—at the 0.05 significance level. An important aspect of this study is the “after-the-fact” nature of the methodology; i.e., none of the participants in this experiment were aware that the programs were to be submitted to a style analyzer for analysis.

     

Dynamic analysis of COBOL programs

This paper describes results obtained from a dynamic analysis of 22 typical COBOL programs. The analysis was performed by COBOL DYNAMIC ANALYSIS SYSTEM (COBDAP) which collected data and reported on the dynamic behaviour of COBOL programs.     

RATSNO—an experiment in software adaptability

Adaptable programs are one of the benefits of structured programming. The adaptability of a program is the degree to which it can be transformed into another program that performs a similar, but slightly different, function. While it is clear that the aims of structured programming are best satisfied by the use of modern programming languages, a great number of programmers must use languages such as Fortran. To alleviate this situation, a number of preprocessors have been introduced that give Fortran a more structured facade. This paper describes an experiment performed to test the adaptability of programs written in RATFOR, one of these preprocessors. Judging from the results, the use of a good preprocessor can significantly increase the adaptability of Fortran programs.     

Operating System Models in a Concurrent Pascal Environment: Complexity and Performance Considerations

Empirical observations of computer operating systems have shown that operating systems are designed with one of two object oriented strategies: a process or a monitor oriented approach. This paper compares the two design approaches in a Concurrent Pascal environment. Resource manager programs that are implemented in conformity with each model are evaluated using software complexity measures and program performance measures. The average complexity of resource manager processes is 94 percent larger than the average complexity of resource manager monitors. The runtime synchronization overhead of the process model program is two-eight times higher than that of its counterpart.     

Complexity and undecidability results for logic programming

This paper surveys complexity, degree of uncomputability, and expressive power results for logic programming. Some major decision problem complexity results and other results for logic programming are also covered. It also proves several new results filling in previous gaps in the literature. The paper considers seven logic programming semantics: the van Emden-Kowalski semantics for definite (Horn) logic programs; the perfect model semantics for stratified and for locally stratified logic programs; and the two- and three-valued program completion semantics, the well-founded semantics, and the stable semantics, all for normal logic programs, under skeptical inference. The main results concern expressibility and query complexity/uncomputability in five contexts: for propositional logic programs, for first order logic programs with infinite Herbrand universes on their Herbrand universes (a closed domain assumption), for first order logic programs with infinite Herbrand universes on those universes extended with infinitely many new elements (an open domain assumption), and for logic programs without function or constant symbols evaluated over varying extensional databases (DATALOG-type results, data complexity results only) under both closed and open domain assumptions. Several of the open domain assumption results are new to this paper. Other results surveyed are (1) results about the family of all stable models of a program and (2) decision questions about when a logic program has nice properties with respect to a semantics (e.g., a unique stable model). One decision result, for well-founded semantics, is new to this paper.Work supported in part by NSF grant IRI-8905166.     

An empirical analysis of COBOL programs

This paper describes results obtained from a static analysis of 340 COBOL programs collected from commercial and industrial installations. The analysis was performed by a syntax analyser designed specifically to analyse source program statements, gather detailed information and produce a report on the definition and use of data and language in the programs analysed.     

Generation of correctness conditions for imperative programs

Verification of imperative programs in the sense of Floyd-Hoare is an approach to proving correctness of programs annotated by preconditions, postconditions, and loop invariants. It is based on generation of correctness conditions. In the structured deterministic case, the problem of generation of correctness conditions seems trivial, since it is solved by a syntax-driven algorithm, the complexity of which linearly depends on the number of control constructs. Vice versa, in the unstructured nondeterministic case, it seems a priori clear that the complexity of generation of the correctness conditions exponentially depends on the number of statements in the program. In the paper, an efficient and complete algorithm for the generation of the correctness conditions is presented and justified. It can be used both in the structured deterministic and unstructured nondeterministic cases. The algorithm complexity linearly depends on the number of control constructs and/or program statements.     

Trends in Data Organization and Access Methods

There has been a trend in applications programming over the past fifteen years from highly structured programs and loosely structured data toward loosely structured programs and highly structured data. Transaction oriented systems and other data directed programs make greater demands on the memory hierarchy of a computer system and have given rise to the need for storage media which are to some degree structurable under program control. Overhead in operating systems and large on-line application programs is described as a symptom of "static" and "dynamic" mismatch problems in the storage hierarchy. Some new memory organization techniques beginning to appear on computers may allow greater efficiency in data directed systems since they allow the programmer to store the structure and the content of his data separately.