Journal of the ACM (JACM)


Search Issue
enter search term and/or author name


Journal of the ACM (JACM), Volume 24 Issue 1, Jan. 1977

Efficient Algorithms for Shortest Paths in Sparse Networks
Donald B. Johnson
Pages: 1-13
DOI: 10.1145/321992.321993
Algorithms for finding shortest paths are presented which are faster than algorithms previously known on networks which are relatively sparse in arcs. Known results which the results of this paper extend are surveyed briefly and analyzed. A new...

A General Model for the Performance of Disk Systems
Neil C. Wilhelm
Pages: 14-31
DOI: 10.1145/321992.321994
The performance of a disk system is often measured in terms of the length of the waiting line or queue of requests for each of the system's spindles. Thus it is natural to formulate and analyze queueing models of disk systems. While most disk...

A Level Algorithm for Preemptive Scheduling
Edward C. Horvath, Shui Lam, Ravi Sethi
Pages: 32-43
DOI: 10.1145/321992.321995
Muntz and Coffman give a level algorithm that constructs optimal preemptive schedules on identical processors when the task system is a tree or when there are only two processors available. Their algorithm is adapted here to handle processors of...

A Transformation System for Developing Recursive Programs
R. M. Burstall, John Darlington
Pages: 44-67
DOI: 10.1145/321992.321996
A system of rules for transforming programs is described, with the programs in the form of recursion equations. An initially very simple, lucid, and hopefully correct program is transformed into a more efficient one by altering the recursion...

Initial Algebra Semantics and Continuous Algebras
J. A. Goguen, J. W. Thatcher, E. G. Wagner, J. B. Wright
Pages: 68-95
DOI: 10.1145/321992.321997
Many apparently divergent approaches to specifying formal semantics of programming languages are applications of initial algebra semantics. In this paper an overview of initial algebra semantics is provided. The major technical feature is an...

Special Editor's Note
Susan L. Graham
Pages: 96-97
DOI: 10.1145/321992.321998
Three ACM symposia on Principles of Programming Languages, jointly sponsored by SIGACT and SIGPLAN, have now been held. The first symposium was in October 1973, the second in January 1975, and the third the following year. It is now planned that...

An Algorithm for Structuring Flowgraphs
Brenda S. Baker
Pages: 98-120
DOI: 10.1145/321992.321999
This paper describes an algorithm which transforms a flowgraph into a program containing control constructs such as if then else statements, repeat (do forever) statements, multilevel break statements (causing jumps out of enclosing repeats),...

Program Improvement by Source-to-Source Transformation
David B. Loveman
Pages: 121-145
DOI: 10.1145/321992.322000
The use of source-to-source program transformations has proved valuable in improving program performance. The concept of program manipulation is elucidated by describing its role in both conventional optimization and high level modification of...

Code Generation for Expressions with Common Subexpressions
A. V. Aho, S. C. Johnson, J. D. Ullman
Pages: 146-160
DOI: 10.1145/321992.322001
This paper shows the problem of generating optimal code for expressions containing common subexpressions is computationally difficult, even for simple expressions and simple machines. Some heuristics for code generation are given and their...

A Methodology for LISP Program Construction from Examples
Phillip D. Summers
Pages: 161-175
DOI: 10.1145/321992.322002
An automatic programming system, THESYS, for constructing recursive LISP programs from examples of what they do is described. The construction methodology is illustrated as a series of transformations from the set of examples to a program...