Sign In

Communications of the ACM

Table of Contents


The first quarter century


Sequential formula translation

The syntax of an algorithmic language such as ALGOL is conveniently described as a sequence of states indicated by an element called cellar. Transitions are controlled by admissible state-symbol pairs which may be represented …

A syntax directed compiler for ALGOL 60

Although one generally thinks of a compiler as a program for a computer which translates some object language into a target language, in fact this program also serves to define the object language in terms of the target language …

Use of tree structures for processing files

In data processing problems, files are frequently used which must both be searched and altered. Binary search techniques are efficient for searching large files, but the associated file organization is not readily adapted tos …

Solution of a problem in concurrent programming control

A number of mainly independent sequential-cyclic processes with restricted means of communication with each other can be made in such a way that at any moment one and only one of them is engaged in the “critical section” of its …

ELIZA — a computer program for the study of natural language communication between man and machine

ELIZA is a program operating within the MAC time-sharing system of MIT which makes certain kinds of natural language conversation between man and computer possible. Input sentences are analyzed on the basis of decomposition rules …

Programming semantics for multiprogrammed computations

The semantics are defined for a number of meta-instructions which perform operations essential to the writing of programs in multiprogrammed computer systems. These meta-instructions relate to parallel processing, protection  …

An improved hash code for scatter storage

Introduced is a hash coding method based on fixed-point division rather than multiplication or logical operations. This new method allows the hash table to have almost any length. Also a new method of handling collisions is discussed …

Scatter storage techniques


The working set model for program behavior

Probably the most basic reason behind the absence of a general treatment of resource allocation in modern computer systems is an adequate model for program behavior. In this paper a new model, the “working set model,” is developed …

The structure of “THE”-multiprogramming system

A multiprogramming system is described in which all activities are divided over a number of sequential processes. These sequential processes are placed at various hierarchical levels, in each of which one or more independent  …

An axiomatic basis for computer programming

In this paper an attempt is made to explore the logical foundations of computer programming by use of techniques which were first applied in the study of geometry and have later been extended to other branches of mathematics. …

An efficient context-free parsing algorithm

A parsing algorithm which seems to be the most efficient general context-free algorithm known is described. It is similar to both Knuth's LR(k) algorithm and the familiar top-down algorithm. It has a time bound proportional to …

The quadratic quotient method: a hash code eliminating secondary clustering

Secondary clustering as a cause of hash code inefficiency is discussed, and a new hashing method based on its elimination is presented. Comparisons with previous methods are made both analytically and empirically.

A relational model of data for large shared data banks

Future users of large data banks must be protected from having to know how the data is organized in the machine (the internal representation). A prompting service which supplies such information is not a satisfactory solution …

Program development by stepwise refinement

The creative activity of programming—to be distinguished from coding—is usually taught by examples serving to exhibit certain techniques. It is here considered as a sequence of design decisions concerning the decomposition of …

A technique for software module specification with examples

This paper presents an approach to writing specifications for parts of software systems. The main goal is to provide specifications sufficiently precise and complete that other pieces of software can be written to interact with …

A statistical study of the accuracy of floating point number systems

This paper presents the statistical results of tests of the accuracy of certain arithmetic systems in evaluating sums, products and inner products, and analytic error estimates for some of the computations. The arithmetic systems …

The UNIX time-sharing system

UNIX is a general-purpose, multi-user, interactive operating system for the Digital Equipment Corporation PDP-11/40 and 11/45 computers. It offers a number of features seldom found even in a larger operating systems, including …

Ethernet: distributed packet switching for local computer networks

Ethernet is a branching broadcast communication system for carrying digital data packets among locally distributed computing stations. The packet transport mechanism provided by Ethernet has been used to build systems which can …

A method for obtaining digital signatures and public-key cryptosystems

An encryption method is presented with the novel property that publicly revealing an encryption key does not thereby reveal the corresponding decryption key. This has two important consequences: Couriers or other secure means …

Communicating sequential processes

This paper suggests that input and output are basic primitives of programming and that parallel composition of communicating sequential processes is a fundamental program structuring method. When combined with a development of …