February 1973 - Vol. 16 No. 2

February 1973 issue cover image

Features

Research and Advances

Representation of contours and regions for efficient computer search

A novel computer-searchable representation for the three basic pictorial features, contour maps, region coverage, and line structures, is described. The representation, which has practical storage requirements, provides a rapid means of searching large files for data associated with geometric position as well as with attribute value. An application of this representation to handling terrain information illustrates its utility. The algebraic properties of the data structure make it computationally easy to determine whether a point lies within a closed boundary; compute the area contained by a closed boundary; generate the closed boundary representing the union or intersection of two closed boundaries; and determine the neighboring boundaries to a point and the minimum distances between them and the point.
Research and Advances

The use of grammatical inference for designing programming languages

Both in designing a new programming language and in extending an existing language, the designer is faced with the problem of deriving a “natural” grammar for the language. We are proposing an interactive approach to the grammar design problem wherein the designer presents a sample of sentences and structures as input to a grammatical inference algorithm. The algorithm then constructs a grammar which is a reasonable generalization of the examples submitted by the designer. The implemention is presently restricted to a subclass of operator precedence grammars, but a second algorithm is outlined which applies to a larger class of context-free grammars.
Research and Advances

Reducing the retrieval time of scatter storage techniques

A new method for entering and retrieving information in a hash table is described. The method is intended to be efficient if most entries are looked up several times. The expected number of probes to look up an entry, predicted theoretically and verified by Monte Carlo experiments, is considerably less than for other comparable methods if the table is nearly full. An example of a possible Fortran implementation is given.
Research and Advances

A software design and evaluation system

A critical failure of current software system design and implementation methodology is that the performance of a proposed design is not evaluated before it is actually implemented. In this paper the reasons for this failure are explored, and a new methodology which overcomes many of the difficulties is proposed. A system which integrates performance evaluation with design and implementation is described. This system is based on a simple, high level language which is used to describe the evolving system at all stages of its development. The source language description is used as direct input to performance analysis and simulation routines. Using the performance information obtained from these routines as feedback, the problems which adversely affect performance are detected early enough so that they can be corrected without costly major reimplementation of the proposed system.
Research and Advances

An overview of the ISPL computer systems design

This paper explores the advantages of the concurrent design of the language, operating system, and machine (via microcode) to create an interactive programming laboratory. It describes the synergistic effect that the freedom to move and alter features from one of these domains to another has had on the design of this system (which has not been implemented). This freedom simplified both incremental compilation and the system's addressing structure, and centralized the communication mechanisms enabling the construction of hierarchical subsystems. It also suggested an important new concept for operating systems: separation of the scheduling from the maintenance functions in resource allocation. This separation enables incorporation of new scheduling algorithms (decision of what to do) without endangering the system integration (correctly performing the scheduling decisions).

Recent Issues

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