July 1972 - Vol. 15 No. 7

A source of ideas for automata theory—the study of the brain—has been pushed aside in mathematical development of the theory. This paper suggests the ways in which automata theory might evolve over the next 25 years if it is to contribute to an understanding of how the brain processes information.

Following the fixpoint theory of Scott, the semantics of computer programs are defined in terms of the least fixpoints of recursive programs. This allows not only the justification of all existing verification techniques, but also their extension to the handling, in a uniform manner of various properties of computer programs, including correctness, termination, and equivalence.

Numerical mathematics is viewed as the analysis of continuous algorithms. Four of the components of numerical mathematics are discussed. These are: foundations (finite precision number systems, computational compexity), synthesis and analysis of algorithms, analysis of error, programs and program libraries.

A brief history of integer and continuous nonlinear programming is presented as well as the current obstacles to practical use of these mathematical programming techniques. It is forecast that the useful contributions to nonlinear programming actually made in the next few years are more likely to be consolidations than theoretical breakthroughs. These contributions are likely to be the documentation of standard test problems, construction of user oriented software, and comparisons of currently known algorithms to demonstrate which techniques are best for specific problems.

A list of a number of natural developments for the field of algebraic manipulation is given. Then the prospects for a general theory of functions defined by ordinary differential equations are discussed. The claim is made that recent developments in mathematics indicate that it should be possible to algorithmically generate many properties of solutions to differential equations. Such a theory is preferable to a less general effort to make algebraic manipulation systems knowledgeable about the usual special functions (e.g. exponential, hypergeometric).

An attempt is made to predict the developments of the next 25 years in the field of computer architecture. Standardized, inexpensive microcomputers on a single chip are predicted. These will be used extensively to provide logical functions for noncomputational devices and incidentally for the design of superscale computers.

Future systems that combine computers, digital terminals, and communications equipment present design optimization problems that require reconsideration of the traditional functional responsibilities of the respective subsystems. Several “standard” interfaces, by means of which computers and digital terminals connect to the communications systems will be required. When specifying these interfaces, consideration must be given to problems of coordination, synchronization, error control, signaling, stream multiplexing, and switch control, in addition to minimizing the technological interdependence of specific subsystem designs. A focus on some of the problems is obtained in a discussion of a detailed specification for a paticular computer-communications system interface.

This paper presents a proposal for structured representation of multiprogramming in a high level language. The notation used explicitly associates a data structure shared by concurrent processes with operations defined on it. This clarifies the meaning of programs and permits a large class of time-dependent errors to be caught at compile time. A combination of critical regions and event variables enables the programmer to control scheduling of resources among competing processes to any degree desired. These concepts are sufficiently safe to use not only within operating systems but also within user programs.

An overview of the current and future positions with respect to operating system performance is given. While a great deal of information and a large number of models for subsystems have been developed, gaps still exist in our knowledge. Because of the severe interactions between the various subsystems of an operating system, an overall model of the total system must be developed to be able to analyze and design the performance aspects of an operating system Although such total system designs are exceptional today, it is projected that they will become increasingly more common and necessary in the near future. Such a design philosophy will clearly have a severe impact on the way we go about modularizing operating and computer systems.

Models constitute a useful means of investigating computer system performance. This paper examines the interrelationships between models and other methods for evaluating the performance of computer systems and establishes circumstances under which the use of a model is appropriate.

In spite of impressive gains by PL/I, Fortran and Cobol remain the languages in which most of the world's production programs are written and will remain so into the foreseeable future. There is a great deal of theoretical interest in Algol 68 and in extensible languages, but so far at least they have had little practical impact. Problem-oriented languages may very well become the most important language development area in the next five to ten years. In the operating system area all major computer manufacturers set out to produce very ambitious multiprogramming systems, and they all ran into similar problems. A number of university projects, though not directly comparable to those of the manufacturers, have contributed greatly to a better understanding of operating system principles. Important trends include the increased interest in the development of system measurement and evaluation techniques, and increased use of microprogramming for some programming system functions.

This paper discusses both the history and future of programming languages ( = higher level languages). Some of the difficulties in writing such a history are indicated. A key part of the paper is a tree showing the chronological development of languages and their interrelationships. Reasons for the proliferation of languages are given. The major languages are listed with the reasons for their importance. A section on chronology indicates the happenings of the significant previous time periods and the major topics of 1972. Key concepts other than specific languages are discussed.

Some observations are made on steps to be taken toward the creation of better mathematical software. These steps suggest the need for a coordinated effort and the creation of a center to focus activities in this area.

List processing systems should be designed to facilitate production of large programs to manipulate large complex symbolic data stores. This paper presents an overview of a number of system features which the author feels are important to improve the productivity of programmers working in such domains. A systems view is taken, rather than focusing just on language features, since algorithms must be not only coded in a language form, but debugged, modified, made efficient, and run on data. Because of this general framework, the requirements specified are applicable to the design of advanced programming systems for a wide range of applications. Three aspects of programming systems are highlighted: good interactive facilities, programmable control structures, and sophisticated data communication mechanisms. Interactive features are described to facilitate program composition, entry, testing, debugging, editing, optimization, and packaging. Implementation of a generalized environment structure model specified would allow programming of various control regimes including multiprocesses, coroutines and backtracking. Alternative methods of procedure invocation required include invocation by pattern and by monitoring condition. The need for extended data forms, storage management, and extensibility are stressed, as is the duality of data retrieval and function evaluation. Syntax directed input and output of data would facilitate use of complex data stores.

Data base management systems have grown rapidly in their power and complexity over the 15-year history of data processing on commercially available computers. The original concepts have split, and new terms have been adopted to name and refer to these concepts. The Data Structure Diagram graphic technique is used to illustrate the splitting of the concepts and the structural relations which exist between these concepts at each point in the evolution.

A pessimistic forecast is given of what can be expected to happen in the application of computers to the physical sciences.

System development is categorized from a generational point of view that parallels the commonly described computing system generations. For each generation, the scope of development projects and the technological world view of the system developer are examined.

The use of the computer in the language-oriented humanities for exhaustive listing of detail (as in indices and concordances) is widespread and accepted as desirable. The implications of the computer for a “science” of the humanities—a science entailing gathering data for the construction and testing of models—are neither widely recognized nor accepted. This paper argues that the computer's major role as to language analysis in the humanities will be the establishing of such a science. Thus, for those areas of the humanities for which rigor and precision are necessary (e.g. analyzing literature or teaching a student to write a composition) the computer can be a critically important facilitator.

A survey is given of computer applications to the instructional process which suggests how the computer professional can contribute to effective educational systems.

This brief survey of the use of computers in urban society covers the broad range of activities found in any city. The future scope of applications is limited only by the imagination and inventiveness of future system designers, programmers, analysts, and decision makers. The computer can be, if properly used, with respect for human dignity and civil liberty, a significant factor in improving the efficiency of the urban process. It is expected that the benefits of such computer usage will outweigh the costs and that we may look forward to an expansion of such usage.

The current role of computers in automatic document processing is briefly outlined, and some reasons are given why the early promise of library automation and of the mechanization of documentation processes has not been fulfilled. A new dynamic document environment is then outlined in which clustered files are searched and information is retrieved following an interactive user-controlled search process. Methods are described for an automatic query modification based on user needs, and for a continuous reorganization of the stored information as a function of earlier file processing and of normal collection growth. The proposed procedures provide powerful tools for information retrieval and for the control of dynamic library collections in which new items are continually added and ones are retired.

The early origins of mathematics are discussed, emphasizing those aspects which seem to be of greatest interest from the standpoint of computer science. A number of old Babylonian tablets, many of which have never before been translated into English, are quoted.

Plankalkül was an attempt by Konrad Zuse in the 1940's to devise a notational and conceptual system for writing what today is termed a program. Although this early approach to a programming language did not lead to practical use, the plan is described here because it contains features that are standard in today's programming languages. The investigation is of historical interest; also, it may provide insights that would lead to advancements in the state of the art. Using modern programming terminology, the Plankalkül is presented to the extent it has been possible to reconstruct it from the published literature.

Many U.S. histories of the digital computer field have tended to be impersonal, with heavy emphasis on eastern universities and commercial developments. This article records the events of the early years in a personal way. The people, organizations, technologies, and computers of the 1945-55 period in the western part of the United States are described as they happened.

The period preceding the founding of ACM was dominated by the first large computer ENIAC. Its characteristics, described here, foreshadow later developments.

The relationship of computers and automation to employment is part of the more general relation of technological change to employment. The most obvious effect is that increases in productivity due to technology can eliminate jobs. Technology affects the individual worker, in the nature and amount of his work, and in his attitudes toward that work. Technological change affects the occupational structure of the entire labor force. Because of the central importance of these effects, the impact of technology has been the subject of extensive study by economists, sociologists, political scientists, and psychologists. Even within a single discipline, studies are often contradictory, and conclusions are colored by political overtones. We wish to delineate some of the issues, and present arguments given to support different viewpoints.