**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...