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 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]

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 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]

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.

The article introduces the March 1973 issue of the journal ACM Computing Surveys. The journal received various contributions from outstanding authors mostly computer professionals. The journal helped computer people to catch up on the latest ideas concepts and advances in the field. The effect of this change has created new opportunities and challenges for the authors of survey. An increasing number of readers are capable of benefiting from tutorial and survey papers presented at advanced levels. The author provides the characteristics of a paper acceptable by the magazine. A good tutorial paper covering an area of the computer field that has recently become important and better understood will get top priority. The body of the paper should be interesting. The text of the survey can be brief, letting the bibliography that attends it and the index into it be as long and up-to-date as required. An excellent survey article is likely to be given preference over a tutorial that is rated only good.

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]

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]

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]

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 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]

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]

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]

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 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]

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]