Search
Join ACM

Computing Profession

Advertisement

Research and Advances

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. This involves the elucidation of sets of axioms and rules of inference which can be used in proofs of the properties of computer programs. Examples are given of such axioms and rules, and a formal proof of a simple theorem is displayed. Finally, it is argued that important advantage, both theoretical and practical, may follow from a pursuance of these topics.
Research and Advances

A modular computer sharing systems

An alternative approach to the design and organization of a general purpose interactive multiterminal computing system is presented. The system organization described is a conceptually simple arrangement of a bank of interchangeable computers, each of which is a memory/proputor pair, that are assigned to process terminal jobs as they arrive. One of the computers serves as the master or control computer and supervises the collection and distribution of messages from and to the remote terminals. In the simplest form there is a disk drive for each connected terminal. A crosspoint switching network allows any such disk drive to be connected to any computer in the bank, under control of the control computer. Thus, while each active terminal user “occupies” a dedicated disk drive, he may share the computer with many other terminal users in a simple manner. The ratio of users to computers is dependent on both the size and power of the machines used and the computation requirements of the particular mix of users. This system organization is inherently a simpler and therefore more reliable approach to time-sharing computers and has the potential of a highly available system at relatively low cost. Economic configurations are possible for a range of systems sizes that span at least one order of magnitude. Finally, problem programs developed by remote terminal users can be run on a dedicated batch system if compatible computers are used.
, , , and
Research and Advances

A new method for determining linear precedence functions for precedence grammars

The precedence relations of a precedence grammar can be precisely described by a two-dimensional precedence matrix. Often the information in the matrix can be represented more concisely by a pair of vectors, called linear precedence functions. A new algorithm is presented for obtaining the linear precedence functions when given the precedence matrix; this algorithm is shown to possess several computational adavantages.
Research and Advances

An ambiguity in the description of ALGOL 60

When Algorithm 355 [Comm. ACM 12 (Oct. 1969), 562] was originally submitted to the Algorithms Department it contained a construct which pointed up an ambiguity in the description of ALGOL 60 [Revised Report on the Algorithmic Language ALGOL 60, Comm. ACM 6 (Jan. 1963), 1-17]. This ambiguity was not mentioned by Donald Knuth [The Remaining Trouble Spots in ALGOL 60, Comm. ACM 10 (Oct. 1967), 611-618].
Research and Advances

Loader standardization for overlay programs

The overlay capability is described for four of the third generation computer systems: CDC-6000, GE-635, IBM-360, and UNIVAC-1108. A critique of the first three sytems is based on actual experience with a large overlaid trajectory simulation program; a short history and description of this program is presented. A standardization of minimum capabilities for loaders is recommended so that programs which must operate under more than one computer system may be easily converted and maintained. A proposal that overlay software incorporates a memory occupation specification concept instead of the conventional tree structure is delineated. This concept provides more efficient and cost-effective utilization of the memory as well as increasd flexibility in program structure.
Research and Advances

A base for a mobile programming system

An algorithm for a macro processor which has been used as the base of an implementation, by bootstrapping, of processors for programming languages is described. This algorithm can be easily implemented on contemporary computing machines. Experience with programming languages whose implementation is based on this algorithm indicates that such a language can be transferred to a new machine in less than one man-week without using the old machine.
and
Research and Advances

On multiprogramming, machine coding, and computer organization

The author feels that the interrupt feature which is available in most modern computers is a potent source of programming pitfalls and errors, and that it therefore may heavily contribute to the unreliability of programs making use of it. A programming scheme is presented which avoids the concept of the interrupt and permits the specification of concurrent (or pseudoconcurrent) activities in a supposedly more perspicuous manner. It is intended to serve as a basis for the construction of operating systems, which are prime examples of programs with concurrent activities. The scheme includes a set of basic instructions for the generation, termination, and synchronization of parallel processes. A set of routines representing these instructions and thereby simulating a hypothetical machine organization has been implemented and tested on the IBM System/360. Two programs using these instructions, written in PL360, are presented.
Research and Advances

Compact list representation: definition, garbage collection, and system implementation

Compact lists are stored sequentially in memory, rather than chained with pointers. Since this is not always convenient, the Swym system permits a list to be chained, compact, or any combination of the two. A description is given of that list representation and the operators implemented (most are similar to those of LISP 1.5). The system garbage collector attempts to make all lists compact; it relocates and rearranges all of list storage using temporary storage. This unique list-compacting garbage collection algorithm is presented in detail. Several classes of the macros used to implement the system are described. Finally, consideration is given to those design factors essential to the success of a plex processing system implementation.
Research and Advances

The MAD definition facility

One of the first definition facilities for higher level languages is described. Users of the language can define new operators and/or data types into the MAD language, so that their use appears as if they were predefined. Information is given on how one writes definitions, as well as on much of the motivation behind the form in which definitions are written. Some conclusions are drawn about future definitional facilities.
, , and
Research and Advances

Computing capabilities at Argentine and Chilean universities

The author reports on a trip to universities in Argentina and Chile during November 1968, describing university conditions and computing activities. As elsewhere, these universities are experiencing student discontent with the status quo and the solutions they are attempting contrast: Argentina is excluding students from participating in university government; Chile is allowing such participation. University computing service and academic activities are limited. The number of computers is small and so is the capacity, none larger than an IBM 360/40; with some exception, computing science academic programs are rare. This situation is by no means attributable to those responsible for computing developments, who strive for excellence; rather the “system” is hard to overcome. Universities, especially those with strong European traditions, adapt slowly to new academic resources and disciplines; superimposed are the severe technological and economic constraints of the developing nation. Consequently, in the absence of conscious government emphasis on strengthening computing capabilities, future progress may be retarded.
Research and Advances

Block structures, indirect addressing, and garbage collection

Programming languages have included explicit or implicit block structures to provide a naming convenience for the programmer. However, when indirect addressing is used, as in SNOBOL, naming constraints may be introduced. Two modifications to SNOBOL are described, resulting in two desirable consequences: (1) naming constraints disappear even when there is indirect addressing within function definitions; and (2) there is a significant saving in the number of calls to the garbage collector, because some garbage is collected, at little expense, each time a function returns to its calling program. These modifications have been implemented as an extension to a SNOBOL dialect.
Research and Advances

Degree of multiprogramming in page-on-demand systems

A simple stochastic model is described which offers a base for understanding the relationship between the number of programs permitted to share memory (the degree of multiprogramming), drum traffic rates, and central processing unit utilization in page-on-demand, multiprogrammed, time-shared computer systems. The model preserves, as a key feature, the property of page-demand statistics which implies a “burst” of page demands at the beginning of any job or quantum execution. The model, a Markov chain, is analyzed numerically and the results are presented graphically for a wide range of key environment-descriptive parameters. Implications of the results to time-shared system design and programming are discussed, and a calculation of the optimal degree of multiprogramming for a wide range of parameters is presented graphically.
and
Research and Advances

Introducing computing to smaller colleges and universities—a progress report

By technical means that are now routine, computer service for smaller colleges and universities can be provided by remote terminals of a central facility. Access, however, is not enough—effective organizational and educational methodology for introducing computing at such institutions must also be developed. The experience of two years with a statewide network involving 41 institutions is discussed. Lessons include the importance of a separate organization representing the small colleges, the necessity for on-campus training for the institutions, the need for some special programming and documentation to support such users, and the development of curriculum by evolutionary means.
, , , and
Research and Advances

An anomaly in space-time characteristics of certain programs running in a paging machine

The running time of programs in a paging machine generally increases as the store in which programs are constrained to run decreases. Experiment, however, have revealed cases in which the reverse is true: a decrease in the size of the store is accompanied by a decrease in running time. An informal discussion of the anomalous behavior is given, and for the case of the FIFO replacement algorithm a formal treatment is presented.
, , and
Research and Advances

Dynamic space-sharing in computer systems

A formalization of relationships between space-sharing, program behavior, and processor efficiency in computer systems is presented. Concepts of value and cost of space allocation per task are defined and then value and cost are combined to develop a single parameter termed value per unit cost. The intent is to illustrate a possible analytic approach to the investigation of the problems of space-sharing and to demonstrate the method on sample problems.
and
Research and Advances

Time-sharing and batch-processing: an experimental comparison of their values in a problem-solving situation

An experimental comparison of problem-solving using time-sharing and batch-processing computer systems conducted at MIT is described in this paper. This study is the first known attempt to evaluate two such systems for what may well be the predominant user population within the next decade—the professionals who, as nonprogrammers, are using the computer as an aid in decision-making and problem-solving rather than as a programming end in itself. Statistically and logically significant results indicate equal cost for usage of the two computer systems; however, a much higher level of performance is attained by time-sharing users. There are indications that significantly lower costs would have resulted if the time-sharing users had stopped work when they reached a performance level equal to that of the batch users. The users' speed of problem-solving and their attitudes made time-sharing the more favorable system.
Research and Advances

Automated printed circuit routing with a stepping aperture

A computer program for routing interconnections on a two-sided printed circuit board with a regular pattern of lines, pins (terminals), and vias (feed-through holes) is described. In this program, each interconnection is given a planned routing—typically, down from the upper pin, through a via, and horizontally to the lower pin. From the top, a virtual aperture (i.e. a long horizontal slit) is stepped down the board. The planned routing is the basis for rerouting interconnections within the aperture to resolve conflicts for lines and vias below the aperture and to maximize the effective line usage. If a conflict has not been resolved before the aperture arrives at the lower pin, interconnections are deleted to resolve the conflict. Extensions of this technique to the control of crosstalk between routed interconnections and to the problem of obtaining 100 percent interconnect are also discussed.

Shape the Future of Computing

ACM encourages its members to take a direct hand in shaping the future of the association. There are more ways than ever to get involved.

Get Involved

Communications of the ACM (CACM) is now a fully Open Access publication.

By opening CACM to the world, we hope to increase engagement among the broader computer science community and encourage non-members to discover the rich resources ACM has to offer.

Learn More