May 1978 - Vol. 21 No. 5

May 1978 issue cover image

Features

Research and Advances

A fast algorithm for copying list structures

An algorithm is presented for copying an arbitrarily linked list structure into a block of contiguous storage locations without destroying the original list. Apart from a fixed number of program variables, no auxillary storage, such as a stack, is used. The algorithm needs no mark bits and operates in linear time. It is shown to be significantly faster than Fisher's algorithm, the fastest previous linear-time algorithm for the same problem. Its speed comes mainly from its efficient list-traversal technique, which folds the processing stack into the structure being built, and from its classification of list cells into nine types, which enables processing operations to be optimized for each type.
Research and Advances

A language extension for expressing constraints on data access

Controlled sharing of information is needed and desirable for many applications and is supported in operating systems by access control mechanisms. This paper shows how to extend programming languages to provide controlled sharing. The extension permits expression of access constraints on shared data. Access constraints can apply both to simple objects, and to objects that are components of larger objects, such as bank account records in a bank's data base. The constraints are stated declaratively, and can be enforced by static checking similar to type checking. The approach can be used to extend any strongly-typed language, but is particularly suitable for extending languages that support the notion of abstract data types.
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

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.
Research and Advances

The SL5 procedure mechanism

This paper describes an integrated procedure mechanism that permits procedures to be used as recursive functions or as coroutines. This integration is accomplished by treating procedures and their activation records (called environments) as data objects and by decomposing procedure invocation into three separate components at the source-language level. In addition, argument binding is under the control of the programmer, permitting the definition of various methods of argument transmission in the source language itself. The resulting procedure mechanism, which is part of the SL5 programming language, is well suited to goal-oriented problems and to other problems that are more readily programmed by using coroutines. Several examples are given.
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.
Research and Advances

New sufficient optimality conditions for integer programming and their application

The purpose of this report is to present a new class of sufficient optimality conditions for pure and mixed integer programming problems. Some of the sets of sufficient conditions presented can be thought of as generalizations of optimality conditions based on primal-dual complementarity in linear programming. These sufficient conditions are particularly useful for the construction of difficult integer programming problems with known optimal solutions. These problems may then be used to test and/or “benchmark” integer programming codes.
Research and Advances

Computer generation of gamma random variables

A new method for generating random variables from the gamma distribution with nonintegral shape parameter &agr; is proposed. This method is similar to two other methods recently given by Wallace and Fishman. It is compared with Fishman's and Ahrens and Dieter's methods. The core storage requirements and programming effort for this method are similar to those of Fishman's method. The proposed method is the same as Fishman's method for 1 ≤ &agr; < 2 and is faster than Fishman's method for 3 ≤ &agr; ≤ 19. Also, the proposed method is much simpler than Ahrens and Dieter's method and is faster for &agr; ≤ 8.
Research and Advances

Optimal shift strategy for a block-transfer CCD memory

For the purposes of this paper, a block-transfer CCD memory is composed of serial shift registers whose shift rate can vary, but which have a definite minimum shift rate (the refresh rate) and a definite maximum shift rate. The bits in the shift registers are numbered 0 to N - 1, and blocks of N bits are always transferred, always starting at bit 0. What is the best shift strategy so that a block transfer request occurring at a random time will have to wait the minimal amount of time before bit 0 can be reached? The minimum shift rate requirement does not allow one to simply “park” at bit 0 and wait for a transfer request. The optimal strategy involves shifting as slowly as possible until bit 0 is passed, then shifting as quickly as possible until a critical boundary is reached, shortly before bit 0 comes around again. This is called the “hurry up and wait” strategy and is well known outside the computer field. The block-transfer CCD memory can also be viewed as a paging drum with a variable (bounded) rotation speed.

Recent Issues

  1. October 2024 CACM cover
    October 2024 Vol. 67 No. 10
  2. September 2024 CACM cover
    September 2024 Vol. 67 No. 9
  3. August 2024 CACM cover
    August 2024 Vol. 67 No. 8
  4. July 2024 CACM cover
    July 2024 Vol. 67 No. 7