Programming Languages and Systems (TOPLAS)


Search Issue
enter search term and/or author name


ACM Transactions on Programming Languages and Systems (TOPLAS), Volume 1 Issue 1, July 1979

Backtracking in a Generalized Control Setting
Gary Lindstrom
Pages: 8-26
DOI: 10.1145/357062.357063
Backtracking is a powerful conceptual and practical programming language control structure. However, its application in general has been limited to global control over recursive programs. In this paper we explore the coherence and utility of...

Programming by Refinement, as Exemplified by the SETL Representation Sublanguage
Robert B. K. Dewar, Arthur Grand, Ssu-Cheng Liu, Jacob T. Schwartz, Edmond Schonberg
Pages: 27-49
DOI: 10.1145/357062.357064
“Pure” SETL is a language of very high level allowing algorithms to be programmed rapidly and succintly. SETL's representation sublanguage adds a system of declarations which allow the user of the language to control the data...

The Compilation of Loop Induction Expressions
Richard L. Sites
Pages: 50-57
DOI: 10.1145/357062.357065
In an optimizing compiler, it is often desirable to compile subscript expressions such as Abase-2 + I*2 so that the value of the expression is available in a register and is simply incremented whenever I is incremented, thus avoiding the...

Incremental Parsing
Carlo Ghezzi, Dino Mandrioli
Pages: 58-70
DOI: 10.1145/357062.357066
An incremental parser is a device which is able to perform syntax analysis in an incremental way, avoiding complete reparsing of a program after each modification. The incremental parser presented extends the conventional LR parsing algorithm...

Code Generation and Storage Allocation for Machines with Span-Dependent Instructions
Edward L. Robertson
Pages: 71-83
DOI: 10.1145/357062.357067
Many machine languages have two instruction formats, one of which allows addressing of “nearby” operands with “short” (e.g. one word) instructions, while “faraway” operands require “long” format...

A New Approach to Proving the Correctness of Multiprocess Programs
Leslie Lamport
Pages: 84-97
DOI: 10.1145/357062.357068
A new, nonassertional approach to proving multiprocess program correctness is described by proving the correctness of a new algorithm to solve the mutual exclusion problem. The algorithm is an improved version of the bakery algorithm. It is...

A Hierarchical Approach to Formal Semantics With Application to the Definition of PL/ CS
Robert L. Constable, James E. Donahue
Pages: 98-114
DOI: 10.1145/357062.357069
We describe a means of presenting hierarchically organized formal definitions of programming languages using the denotational approach of D. Scott and C. Strachey. As an example of our approach, we give the semantics of PL/CS, an instructional...

Morris's Garbage Compaction Algorithm Restores Reference Counts
David S. Wise
Pages: 115-120
DOI: 10.1145/357062.357070
The two-pass compaction algorithm of F.L. Morris, which follows upon the mark phase in a garbage collector, may be modified to recover reference counts for a hybrid storage management system. By counting the executions of two loops in that...

A fast algorithm for finding dominators in a flowgraph
Thomas Lengauer, Robert Endre Tarjan
Pages: 121-141
DOI: 10.1145/357062.357071
A fast algorithm for finding dominators in a flowgraph is presented. The algorithm uses depth-first search and an efficient method of computing functions defined on paths in trees. A simple implementation of the algorithm runs in...

A Deterministic Attribute Grammar Evaluator Based on Dynamic Scheduling
Ken Kennedy, Jayashree Ramanathan
Pages: 142-160
DOI: 10.1145/357062.357072
The problem of semantic evaluation in a compiler-generating system can be addressed by specifying language semantics in an attribute grammar [19], a context-free grammar augmented with “attributes” for the...