Search
Join ACM

Software Engineering and Programming Languages

Advertisement

Research and Advances

Communicating sequential processes

This paper suggests that input and output are basic primitives of programming and that parallel composition of communicating sequential processes is a fundamental program structuring method. When combined with a development of Dijkstra's guarded command, these concepts are surprisingly versatile. Their use is illustrated by sample solutions of a variety of a familiar programming exercises.
Research and Advances

Feedback coupled resource allocation policies in the multiprogramming-multiprocessor computer system

Model studies of some integrated, feedback-driven scheduling systems for multiprogrammed-multiprocessor computer systems are presented. The basic control variables used are the data-flow rates for the processes executing on the CPU. The model systems feature simulated continuous-flow and preempt-resume scheduling of input-output activity. Attention is given to the amount of memory resource required for effective processing of the I/O activity (buffer space assignment). The model studies used both distribution-driven and trace-driven techniques. Even relatively simple dynamic schedulers are shown to improve system performance (as measured by user CPU time) over that given by optimal or near-optimal static schedulers imbedded in identical system structures and workload environments. The improvement is greatest under a heavy I/O demand workload.
and
Research and Advances

Pseudochaining in hash tables

This paper presents pseudochaining as a new collision-resolution method. Pseudochaining is half way between open addressing and chaining. It owes its name to the fact that link fields are present in each cell of the hash table which permits “chaining” of the first overflow items in the table. The efficiency of the method is derived and a tradeoff analysis is given.
and
Research and Advances

On the complexity of computing the measure of ∪[ai,bi]

The decision tree complexity of computing the measure of the union of n (possibly overlapping) intervals is shown to be &OHgr;(n log n), even if comparisons between linear functions of the interval endpoints are allowed. The existence of an &OHgr;(n log n) lower bound to determine whether any two of n real numbers are within ∈ of each other is also demonstrated. These problems provide an excellent opportunity for discussing the effects of the computational model on the ease of analysis and on the results produced.
and
Research and Advances

Interpolation search—a log logN search

Interpolation search is a method of retrieving a desired record by key in an ordered file by using the value of the key and the statistical distribution of the keys. It is shown that on the average log logN file accesses are required to retrieve a key, assuming that the N keys are uniformly distributed. The number of extra accesses is also estimated and shown to be very low. The same holds if the cumulative distribution function of the keys is known. Computational experiments confirm these results.
, , and
Research and Advances

Time, clocks, and the ordering of events in a distributed system

The concept of one event happening before another in a distributed system is examined, and is shown to define a partial ordering of the events. A distributed algorithm is given for synchronizing a system of logical clocks which can be used to totally order the events. The use of the total ordering is illustrated with a method for solving synchronization problems. The algorithm is then specialized for synchronizing physical clocks, and a bound is derived on how far out of synchrony the clocks can become.
Research and Advances

Proving the correctness of heuristically optimized code

A system for proving that programs written in a high level language are correctly translated to a low level language is described. A primary use of the system is as a postoptimization step in code generation. The low level language programs need not be generated by a compiler and in fact could be hand coded. Examples of the usefulness of such a system are given. Some interesting results are the ability to handle programs that implement recursion by bypassing the start of the program, and the detection and pinpointing of a wide class of errors in the low level language programs. The examples demonstrate that optimization of the genre of this paper can result in substantially faster operation and the saving of memory in terms of program and stack sizes.
Research and Advances

An English language question answering system for a large relational database

By typing requests in English, casual users will be able to obtain explicit answers from a large relational database of aircraft flight and maintenance data using a system called PLANES. The design and implementation of this system is described and illustrated with detailed examples of the operation of system components and examples of overall system operation. The language processing portion of the system uses a number of augmented transition networks, each of which matches phrases with a specific meaning, along with context registers (history keepers) and concept case frames; these are used for judging meaningfulness of questions, generating dialogue for clarifying partially understood questions, and resolving ellipsis and pronoun reference problems. Other system components construct a formal query for the relational database, and optimize the order of searching relations. Methods are discussed for handling vague or complex questions and for providing browsing ability. Also included are discussions of important issues in programming natural language systems for limited domains, and the relationship of this system to others.
Research and Advances

Shallow binding in Lisp 1.5

Shallow binding is a scheme which allows the value of a variable to be accessed in a bounded amount of computation. An elegant model for shallow binding in Lisp 1.5 is presented in which context-switching is an environment tree transformation called rerooting. Rerooting is completely general and reversible, and is optional in the sense that a Lisp 1.5 interpreter will operate correctly whether or not rerooting is invoked on every context change. Since rerooting leaves assoc [v, a] invariant, for all variables v and all environments a, the programmer can have access to a rerooting primitive, shallow[], which gives him dynamic control over whether accesses are shallow or deep, and which affects only the speed of execution of a program, not its semantics. In addition, multiple processes can be active in the same environment structure, so long as rerooting is an indivisible operation. Finally, the concept of rerooting is shown to combine the concept of shallow binding in Lisp with Dijkstra's display for Algol and hence is a general model for shallow binding.
Research and Advances

A selective traversal algorithm for binary search trees

The problem of selecting data items from a binary search tree according to a list of range conditions is considered. The process of visiting a minimal number of nodes to retrieve data satisfying the range conditions is called selective traversal. Presented in this paper is an algorithm for selective traversal which uses a tag field for each node in the tree. The algorithm is particularly useful and efficient when examination of data is more time consuming than examination of a tag field.
and
Research and Advances

Automatic error recovery for LR parsers

In this paper we present a scheme for detecting and recovering from syntax errors in programs. The scheme, which is based on LR parsing, is driven by information which is directly and automatically obtainable from the information that is already present in an LR parser. The approach, which is patterned after that of Levy and Graham and Rhodes, appears to provide error recovery which is both simple and powerful.
and
Research and Advances

General equations for idealized CPU-I/O overlap configurations

General equations are derived for estimating the maximum possible utilization of main storage partitions, CPU and I/O devices under different conditions in an idealized CPU-I/O overlap model of multiprogrammed computer systems. The equations are directly applicable to any configuration consisting of sets of identical CPU's, I/O processors, main storage partitions and user tasks. Examples are provided to illustrate the use of the equations to compute effective processing time per record and expected timesharing response time under both balanced and unbalanced resource utilization conditions.
Research and Advances

Characteristics of application software maintenance

Maintenance and enhancement of application software consume a major portion of the total life cycle cost of a system. Rough estimates of the total systems and programming resources consumed range as high as 75-80 percent in each category. However, the area has been given little attention in the literature. To analyze the problems in this area a questionnaire was developed and pretested. It was then submitted to 120 organizations. Respondents totaled 69. Responses were analyzed with the SPSS statistical package. The results of the analysis indicate that: (1) maintenance and enhancement do consume much of the total resources of systems and programming groups; (2) maintenance and enhancement tend to be viewed by management as at least somewhat more important than new application software development; (3) in maintenance and enhancement, problems of a management orientation tend to be more significant than those of a technical orientation; and (4) user demands for enhancements and extension constitute the most important management problem area.
, , and
Research and Advances

Analyses of deterministic parsing algorithms

This paper describes an approach for determining the minimum, maximum, and average times to parse sentences acceptable by a deterministic parser. These quantities are presented in the form of symbolic formulas, called time-formulas. The variables in these formulas represent not only the length of the input string but also the time to perform elementary operations such as pushing, popping, subscripting, iterating, etc. By binding to the variables actual numerical values corresponding to a given compiler-machine configuration, one can determine the execution time for that configuration. Time-formulas are derived by examining the grammar rules and the program representing the algorithm one wishes to analyze. The approach is described by using a specific grammar that defines simple arithmetic expressions. Two deterministic parsers are analyzed: a top-down recursive descent LL(1) parser, and a bottom-up SLR(1) parser. The paper provides estimates for the relative efficiencies of the two parsers. The estimates applicable to a specific machine, the PDP-10, are presented and substantiated by benchmarks. Finally, the paper illustrates the proposed approach by applying it to the analyses of parsers for a simple programming language.
and
Research and Advances

Some basic determinants of computer programming productivity

The purpose of this research was to examine the relationship between processing characteristics of programs and experience characteristics of programmers and program development time. The ultimate objective was to develop a technique for predicting the amount of time necessary to create a computer program. The fifteen program characteristics hypothesized as being associated with an increase in programming time required are objectively measurable from preprogramming specifications. The five programmer characteristics are experience-related and are also measurable before a programming task is begun. Nine program characteristics emerged as major influences on program development time, each associated with increased program development time. All five programmer characteristics were found to be related to reduced program development time. A multiple regression equation which contained one programmer characteristic and four program characteristics gave evidence of good predictive power for forecasting program development time.
Research and Advances

Automated welfare client-tracking and service integration: the political economy of computing

The impacts of an automated client-tracking system on the clients, caseworkers, administrators, and operations of the welfare agencies that use it are reported. The major impact of this system was to enhance the administrative attractiveness of the using agencies in the eyes of funders rather than to increase their internal administrative efficiency. This impact is a joint product of both the technical features of the computer-based system and of the organizational demands placed upon different agencies, administrators, and caseworkers. It illustrates the way “successful” automated information systems fit the political economies of the groups that use them.
Research and Advances

Test data as an aid in proving program correctness

Proofs of program correctness tend to be long and tedious, whereas testing, though useful in detecting errors, usually does not guarantee correctness. This paper introduces a technique whereby test data can be used in proving program correctness. In addition to simplifying the process of providing correctness, this method simplifies the process of providing accurate specification for a program. The applicability of this technique to procedures and recursive programs is demonstrated.
Research and Advances

An interference matching technique for inducing abstractions

A method for inducing knowledge by abstraction from a sequence of training examples is described. The proposed method, interference matching, induces abstractions by finding relational properties common to two or more exemplars. Three tasks solved by a program that uses an interference-matching algorithm are presented. Several problems concerning the description of the training examples and the adequacy of interference matching are discussed, and directions for future research are considered.
and
Research and Advances

Automatic data structure selection: an example and overview

The use of several levels of abstraction has proved to be very helpful in constructing and maintaining programs. When programs are designed with abstract data types such as sets and lists, programmer time can be saved by automating the process of filling in low-level implementation details. In the past, programming systems have provided only a single general purpose implementation for an abstract type. Thus the programs produced using abstract types were often inefficient in space or time. In this paper a system for automatically choosing efficient implementations for abstract types from a library of implementations is discussed. This process is discussed in detail for an example program. General issues in data structure selection are also reviewed.

Shape the Future of Computing

ACM encourages its members to take a direct hand in shaping the future of the association. There are more ways than ever to get involved.

Get Involved

Communications of the ACM (CACM) is now a fully Open Access publication.

By opening CACM to the world, we hope to increase engagement among the broader computer science community and encourage non-members to discover the rich resources ACM has to offer.

Learn More