Search

The purpose of this paper is to indicate something of the nature of "good programming." In this context, programming is taken to mean the entire process of communication between humans and computers. The programming process is sub- divided into nine tasks, and an elementary discussion of each of these tasks is presented. Although the paper is primarily directed to the student or novice programmer, more experienced people may find it a worthwhile aid in codifying or reinforcing their experience. [ABSTRACT FROM AUTHOR]

Time and time again software projects, though undertaken by people of considerable intellectual ability, fail. This will doubtless be a continuing phenomenon, because software production is indeed a difficult task requiring wide-ranging skills. Certainly, no single paper can suddenly solve all the problems of software writing and eliminate the failures. The scope of this paper is limited to four stages in the execution of software projects, namely the planning, coding, testing, and final usage. These four crucial areas contain pitfalls that have been responsible for a large proportion of software failures, and it is hoped this paper will help avoid some of them. [ABSTRACT FROM AUTHOR]

This paper discusses the hidden-surface problem from tile point of view of sorting. The various surfaces of an object to be shown in hidden-surface or hidden-line form must be sorted to find out which ones are visible at various places on the screen. Surfaces may be sorted by lateral position in the picture (X I'), by depth (Z), or by other criteria. The paper shows that the order of sorting and the types of sorting used form differences among the existing hidden-surface algorithms. To reduce the work of sorting, each algorithm capitalizes on some coherence property of the objects represented. ‘Scan-line coherence,’ the fact that one TV scan line of output is likely to be nearly the same as the previous TV scan line, is one commonly used kind of coherence. ‘Frame coherence,’ the fact that the entire picture does not change very much between successive frames of a motion picture can be very helpful if it is applicable. By systematically looking for additional kinds of coherence and untried sorting orders and sorting types, the paper is able to suggest two promising new approaches to the hidden-surface problem. The first, a combination of three existing algorithms, is promising because it would capitalize on both frame and scan-line coherence. The second new approach would sort in the order Y, Z, X, … the only sorting order for which an existing algorithm could not be found. [ABSTRACT FROM AUTHOR]

The concept of "process" has come to play a central role in many efforts to master the complexity of large computer systems. The purpose of this paper is to discuss useful methods of structuring complex processes, and to relate these to the problems of improving the quality of large computer systems. Two distinct ways of structuring systems are presented, namely, process combination, and process abstraction; these are then used to discuss such topics as concurrency, synchronization, multiprogramming, interpreters, and programmable processors. This discussion is based on a set of precise definitions for such concepts as "process," "processor," "computation," "combination," and "abstraction." The paper relates these definitions to both current research and practical applications, with particular concern for the problems of the performance, reliability, and modifiability of computer systems. [ABSTRACT FROM AUTHOR]

A sparse matrix is defined to be a matrix containing a high proportion of elements that are zeros. Sparse matrices of large order are of great interest and application in science and industry; for example, electrical networks, structural engineering, power distribution, reactor diffusion, and solutions to differential equations. While conclusions within this paper are primarily drawn considering orders of greater than 1000, much is applicable to sparse matrices of smaller orders in the hundreds. Because of increasing use of large order sparse matrices and the tendency to attempt to solve larger order problems, great attention must be focused on core storage and execution time. Every effort should be made to optimize both computer memory allocation and execution times, as these are the limiting factors that most often dictate the practicality of solving a given problem. Indexing algorithms are the subject of this paper, as they are generally recognized as the most important factor in fast and efficient processing of large order sparse matrices. Indexing schemes of main interest are the bit map, address map, row-column, and the threaded list. Major variations of the indexing techniques above mentioned are noted, as well as the particular indexing scheme inherent in diagonal or band matrices. The concluding section of the paper compares the types of methods, discusses their suitability for different types of processing, and makes suggestions concerning the adaptability and flexibility of the major existing methods of indexing algorithms for application to user problems. [ABSTRACT FROM AUTHOR]

In this paper, several theoretical aspects of multiprocessing are surveyed. First, we look at the language features that help in exploiting parallelism. The additional instructions needed for a multiprocessor architecture; problems, such as mutual exclusion, raised by the concurrent processing of parts of a program; and the extensions to existing high-level languages are examined. The methods for automatic detection of parallelism in current high-level languages are then reviewed both at the inter and intra statement levels. The following part of the paper deals with more theoretical aspects of multiprocessing. Different models for parallel computation such as graph models, Petri nets, parallel flowcharts, and flow graph schemata are introduced. Finally, prediction of performance of multiprocessors either through analysis of models or by simulation is examined. In an appendix, an attempt is made toward the classification of existing multiprocessors. [ABSTRACT FROM AUTHOR]

The Vienna Definition Language (VDL) is a programming language for defining programming languages. It allows us to describe precisely the execution of the set of all programs of a programming language. However, the Vienna Definition Language is important not only as one definition technique among many others but as an illustration of a new information-structure-oriented approach to the study of programming languages. The paper may be regarded as a case study in the information structure modeling of programming languages, as well as an introduction to a specific modeling technique. Part 1 includes a brief review and comparison of techniques of language definition, and then introduces the basic data structures and data structure manipulation operators that are used to define programming languages. Part 2 considers the definition of sets of data structures. Part 3 introduces the notation for specifying VDL instructions, and illustrates the definition of a simple language for arithmetic expression evaluation by giving the complete sequence of states (snapshots) that arise during the evaluation of an expression. Part 4 defines a simple block structure language in VDL and considers certain basic design issues for such languages in a more general context. Part 5 introduces an alternative definition of the block structure language defined in Part 4, proves the equivalence of the two definitions, and briefly reviews recent work on proving the equivalence of interpreters. An Appendix considers the definition of VDL in VDL. This paper may be read at a number of different levels. The reader who is interested in a quick introduction to the basic definition techniques of VDL need read only Section 1.3 and Part 3. The reader who is interested in a deeper understanding of block structure languages should emphasize Part 4, while the reader concerned with proofs of equivalence of interpreters will be interested in Part 5. [ABSTRACT FROM AUTHOR]

Using a tutorial and expository approach, this paper assesses the performance of some simple, idealized input, output, and compute overlap configurations. Equations are given for one- and two-channel configurations that have one, two, and three partitions of main storage. The objectives of the paper are to gain insight into bounds on system throughput performance and to give equations useful for checking computer simulation. [ABSTRACT FROM AUTHOR]

The literature is surveyed beginning with the first paper published in 1951. At that time microprogramming was proposed primarily as a means for designing the control unit of an otherwise conventional digital computer, although the possible use of a read/write control memory was noted. The survey reveals the way in which interest has successively developed in the following aspects of the subject: stored logic, the application of microprogramming to the design of a range of computers, emulation, microprogramming in support of software, and read/write control memories. The bibliography includes 55 papers. [ABSTRACT FROM AUTHOR]

The article presents an overview of papers presented in the December 1974 issue of the periodical "acm computing surveys." All papers selected for publication in this issue cover a range of viewpoints about good programming. There is no fixed set of rules according to which clear, understandable and provable programs can be constructed. There are guidelines ofcourse but the individual programmer's style, his clarity of thought and creativity contribute significantly to the outcome. The first two papers in the issue deal with the relationship between better programming and environment.

Computer programs can be written many different ways and still achieve the same effect. Until recently, programmers have had little reason to favor one method of expressing code over another. We have come to learn, however, that functionally equivalent programs can have extremely important stylistic differences. Good programming style cuts across application areas, technique and language. Programs written with good style are easier to read and understand, and often smaller and more efficient, than those written badly. Yet few programmers have ever been taught what style is, as we can see from even cursory inspection of their code. Even the techniques of structured programming do not ensure that code will be good; "structured" programs can be just as bad as their unstructured counterparts. This paper is a survey of some aspects of programming style, primarily expression and structure, showing by example what happens when principles of style are violated, and what can be done to improve programs. To add the ring of truth to our discussion, the examples are all taken verbatim from programming textbooks. [ABSTRACT FROM AUTHOR]

Binary search trees are an important technique for organizing large files because they are efficient for both random and sequential access of records, and for modification of a file. Because of this, they have received a great deal of attention in recent years, and their properties are now better understood than those of most other file organization methods. This paper surveys the main results which have been obtained. [ABSTRACT FROM AUTHOR]

New direction in Artificial Intelligence research have led to the need for certain novel features to be embedded in programming languages. This paper gives an overview of the nature of these features, and their implementation in four principal families of AI languages: SAIL; PLANNER/CONNIVER; QLISP/INTERLISP; AND POPLER/POP-2. The programming features described include: new data types and accessing mechanisms for stored expressions; more flexible control structures, including multiple processes and backtracking; pattern matching to allow comparison of data item with a template, and extraction of labeled subexpressions; and deductive mechanisms which allow the programming system to carry out certain activities including modifying the data base and deciding which subroutines to run next using only constraints and guidelines set up by the programmer. [ABSTRACT FROM AUTHOR]

The LR syntax analysis method is a useful and versatile technique for parsing deterministic context-free languages in compiling applications. This paper provides an informal exposition of Lit parsing techniques emphasizing the mechanical generation of efficient LR parsers for context-free grammars. Particular attention is given to extending the parser generation techniques to apply to ambiguous grammars. [ABSTRACT FROM AUTHOR]

This paper describes various forms of line drawing representation, compares different schemes of quantization, and reviews the manner in which a line drawing can be extracted from a tracing or a photographic image. The subjective aspects of a line drawing are examined. Different encoding schemes are compared, with emphasis on the so-called chain code which is convenient for highly irregular line drawings. The properties of chain-coded line drawings are derived, and algorithms are developed for analyzing line drawings to determine various geometric features. Procedures are described for rotating, expanding, and smoothing line structures, and for establishing the degree of similarity between two contours by a correlation technique. Three applications are described in detail: automatic assembly of jigsaw puzzles, map matching, and optimum two-dimensional template layout. [ABSTRACT FROM AUTHOR]

This paper describes the evolution of language features for multiprogramming from event queues and semaphores to critical regions and monitors. It suggests that the choice of language concepts should be guided by two simple principles: First, it should be possible to understand a concurrent program in time- independent terms by an effort proportional to its size; secondly, it should be possible to state assumptions about invariant relationships among program components and have these assumptions checked automatically. The central problems of multiprogramming are illustrated by annotated algorithms written in a well-structured programming language. [ABSTRACT FROM AUTHOR]

The process of selecting a computer is very complex, involving much technical detail and much economic approximation. Because of the substantial investment which many organizations have in computers, it is of significant benefit to use selection procedures which minimize computer costs as much as possible within the numerous difficult constraints always present in computer selections. The issues involved in such selections are so complex, the needs and economies are so variable, and the trade-offs which must be made are so qualitative that it is not meaningful to suggest a single, universal approach to selection. Instead of attempting such a recommendation, this paper provides a framework and a basis from which the user can confidently determine a selection approach which is appropriate to his own circumstances. An exposition of the basic considerations underlying selection is presented, followed by a detailed analysis of the steps in the selection process, including alternative approaches to carrying out these steps. An account of procedures used by various organizations is given. Finally, a bibliography, organized by subject matter, is included to facilitate deeper investigation of the issues raised. An appendix contains an attempt at comparison of some major computers. [ABSTRACT FROM AUTHOR]

This paper is a tutorial on the methods used to control the transmission of digital information on data communication links. Simple models of data communication systems are introduced and terminology for describing their functions and operation is established. Various graphical methods of representing communication control procedures are discussed and used to describe significant features of communication control procedures in detail. [ABSTRACT FROM AUTHOR]

The purpose of this paper is to point out the significant quantity of work in progress on techniques that will enable programmers to prove their programs correct. This work has included: investigations in the theory of program schemas or abstract programs; development of the art of the informal or manual proof of correctness; and development of mechanical or semi-mechanical approaches to proving correctness. At present, these mechanical approaches rely upon the availability of powerful theorem-provers, development of which is being actively pursued. All of these technical areas are here surveyed in detail, and recommendations are made concerning the direction of future research toward producing a semi mechanical program verifier. [ABSTRACT FROM AUTHOR]

This is a tutorial paper on the linking and loading stages of the language transformation process. First, loaders are classified and discussed. Next, the linking process is treated in terms of the various times at which it may occur (i.e., binding to logical space). Finally, the linking and loading functions are explained in detail through a careful examination of their implementation in the IBM System/360. Examples are presented, and a number of possible system trade-offs are pointed out. [ABSTRACT FROM AUTHOR]

The bibliography appearing at the end of this article lists 37 sorting algorithms and 100 books and papers on sorting published in the last 20 years. The basic ideas presented here have been abstracted from this body of work, and the best algorithms known are given as examples. As the algorithms are explained, references to related algorithms and mathematical or experimental analyses are given. Suggestions are then made for choosing the algorithm best suited to a given situation. [ABSTRACT FROM AUTHOR]

The proliferation of programming languages has raised many issues of language design, definition, and implementation. This paper presents a series of ten mini-languages, each of which exposes salient features found in existing programming languages. The value of the mini-languages lies in their brevity of description and the isolation of important linguistic features: in particular, the notions of assignment, transfer of control, functions, parameter passing, type checking, data structures, string manipulation, and input/output. The mini-languages may serve a variety of uses: notably, as a pedagogical tool for teaching programming languages, as a subject of study for the design of programming languages, and as a set of test cases for methods of language implementation or formal definition. [ABSTRACT FROM AUTHOR]

This paper is a survey of current methods for the on-line creation and editing of computer programs and of ordinary manuscript text. The characteristics of on-line editing systems are examined and examples of various implementations are described in three categories: program editors, text editors, and terminals with local editing facilities. [ABSTRACT FROM AUTHOR]

This paper describes the internal structure of a time-sharing system in some detail. This system is dedicated to providing remote access, and has a simple file structure. It is intended for use in a university type environment where there are many short jobs that will profit from one- or two-second turnaround. Despite its simplicity, this system can serve as a useful introduction to the problems encountered by the designers of any time-sharing system. Included are a discussion of the command language, the hardware organization toward which the design is oriented, the general internal organization, the command sequences, the CPU scheduler, handling of interrupts, the assignment of core space, execution and control of the user's program, backup storage management, and the handling of errors. [ABSTRACT FROM AUTHOR]

An analysis of the two earliest sets of instruction codes planned for stored program computers, and the earliest extant program for such a computer, gives insight into the thoughts of John yon Neumann, the man who designed the instruction sets and wrote the program, and shows how several important aspects of computing have evolved. The paper is based on previously unpublished documents from the files of Herman H. Goldstine. [ABSTRACT FROM AUTHOR]

This is a tutorial paper describing the construction of a basic simulation model for a disk-based multiprogrammed computer system. First, the job processing sequence of the system to be simulated is described and techniques for generating the simulated job mix are discussed. The structure of simulation models, events, and events scheduled are then introduced. A simulation model for the multiprogrammed system is presented and the event routines comprising the model are discussed. The use of GPSS, SIMSCRIPT, and FORTRAN in constructing a simulation model is reviewed. [ABSTRACT FROM AUTHOR]

The application of computers for controlling process units is now about ten years old. The applications have progressed from the experimental stages of early development to a well-established (economically speaking) control practice. This has not been without some anxious moments and a few outright failures. These have not been forgotten, but current successes are proving beyond any doubt that digital computers are capable of generating an attractive economic return on the investment required for their installation. This paper has three objectives: first, to acquaint those outside the process industries of the general process control problem in order that they may appreciate some of the requirements imposed on a control computer; second, to describe the computer hardware normally considered for process control; third, to present the general philosophy of the real-time software systems required for process control. [ABSTRACT FROM AUTHOR]

This paper surveys the use of the computer in the humanities and fine arts, and indicates the relevance of available hardware and software for those applications areas. The first section covers (a) pattern recognition and analysis in art, architecture, music, and literature (with an emphasis upon the latter), and (b) pattern construction, or synthesis, in art, architecture, music, and language. In the second section, data representation and manipulation are described with reference to: first, transformation of the artifact into a form suitable for the computer; second, internal data storage and manipulation; and, third, output. The three types of artifacts dealt with are: aural, or auditory; visual, including both nonalphameric and alphameric forms; tactile. A discussion of data structures and of data manipulation occupies the subsection on internal data storage and manipulation, and the brief commentary on output concentrates on aural and visual modes. [ABSTRACT FROM AUTHOR]

This tutorial paper is presented at an intermediate level, which assumes that the reader already has either some elementary knowledge of PL/I or a more general familiarity with other high level languages. An attempt is made to break fresh ground by addressing a question concerning the design philosophy of PL/I, namely whether it is possible for the more experienced programmer to grasp the deeper structure and achieve complete mastery of a language with such broad scope. (It is not concerned with showing how easily parts of the language may be used for simple applications, although several introductory texts are cited.) The method of the exposition is first to dispose of certain preprocesses which may be performed, and then to organize the major part of the material under two heads, static aspects and dynamic aspects. The static aspects are those essentially related to inspection rather than execution of a program; the dynamic part of the discussion outlines the semantics in terms of the internal storage, external storage, and flow of control in a conceptual PL/I machine. Every statement and type of object in the language is given a place in this scheme. [ABSTRACT FROM AUTHOR]

A set of detailed functional specifications is presented here for typewriter-like terminals (e.g. teletypewriters) to be used on-line with time-sharing computer systems. The emphasis is on the functions to be provided (rather than on the specifics of the implementation of such functions), as well as on user needs and on human factors relevant to such terminals. None of the features described presents any major technological or manufacturing problems. Thus, this paper can be viewed as a statement, offered for the benefit of the manufacturers and designers of such terminals, of user needs which exist in this area, as well as an in-depth tutorial on the subject topic. [ABSTRACT FROM AUTHOR]

Queueing models of time-sharing algorithms have been appearing in the literature with increasing frequency. This survey delineates the parameters which distinguish the different analytic models and presents the research results of most of the papers to date. The techniques used in analyzing various round-robin models and multiple-level queue models both with and without priorities are emphasized. The results indicated provide the system designer with a number of degrees of freedom with which to synthesize a time-shared processing system and point out needed research directions. An annotated bibliography is provided. [ABSTRACT FROM AUTHOR]

In this addendum to my previous paper "Virtual Memory," a true expression for paging drum efficiency is derived, and an assumption commonly used in analysis of rotating storage devices is shown to be erroneous. [ABSTRACT FROM AUTHOR]