ACM DL

Programming Languages and Systems (TOPLAS)

Menu

Search Issue
enter search term and/or author name

Archive


ACM Transactions on Programming Languages and Systems (TOPLAS), Volume 17 Issue 2, March 1995

Combining analyses, combining optimizations
Cliff Click, Keith D. Cooper
Pages: 181-196
DOI: 10.1145/201059.201061
Modern optimizing compilers use several passes over a program's intermediate representation to generate good code. Many of these optimizations exhibit a phase-ordering problem. Getting the best code may require iterating optimizations until a...

Experimental results from dynamic slicing of C programs
G. A. Venkatesh
Pages: 197-216
DOI: 10.1145/201059.201062
Program slicing is a program analysis technique that has been studied in the context of several different applications in the construction, optimization, maintenance, testing, and debugging of programs. Algorithms are available...

A reexamination of “Optimization of array subscript range checks”
Wei-Ngan Chin, Eak-Khoon Goh
Pages: 217-227
DOI: 10.1145/201059.201063
Jonathan Asuru proposed recently an enhanced method for optimizing array subscript range checks. The proposed method is however unsafe and may generate optimized programs whose behavior is different from the original program. Two main flaws in...

A worst case of circularity test algorithms for attribute grammars
Pei-Chi Wu, Feng-Jian Wang
Pages: 228-232
DOI: 10.1145/201059.201064
Although the circularity test problem for attribute grammars (AGs) has been proven to be intrinsically exponential, to date, a worst case for the existing circularity test algorithms has yet to be presented. This note presents a...

Supporting dynamic data structures on distributed-memory machines
Anne Rogers, Martin C. Carlisle, John H. Reppy, Laurie J. Hendren
Pages: 233-263
DOI: 10.1145/201059.201065
Compiling for distributed-memory machines has been a very active research area in recent years. Much of this work has concentrated on programs that use arrays as their primary data structures. To date, little work has been done to address the...

Efficient implementation of adaptive software
Jens Palsberg, Cun Xiao, Karl Lieberherr
Pages: 264-292
DOI: 10.1145/201059.201066
Adaptive programs compute with objects, just like object-oriented programs. Each task to be accomplished is specified by a so-called propagation pattern which traverses the receiver object. The object traversal is a recursive descent via the...

Optimization of functional programs by grammar thinning
Adam Webber
Pages: 293-330
DOI: 10.1145/201059.201067
We describe a new technique for optimizing first-order functional programs. Programs are represented as graph grammars, and optimization proceeds by counterexample: when a graph generated by the grammar is found to contain an unnecessary...

On the complexity of dataflow analysis of logic programs
Saumya K. Debray
Pages: 331-365
DOI: 10.1145/201059.201068
It is widely held that there is a correlation between complexity and precision in dataflow analysis, in the sense that the more precise an analysis algorithm, the more computationally expensive it must be. The details of this relationship,...

A complete calculus for the multialgebraic and functional semantics of nondeterminism
Michal Walicki, Sigurd Meldal
Pages: 366-393
DOI: 10.1145/201059.201070
The current algebraic models for nondeterminism focus on the notion of possibility rather than necessity and consequently equate (nondeterministic) terms that one would intuitively not consider equal....

Matching-based incremental evaluators for hierarchical attribute grammar dialects
Alan Carle, Lori Pollock
Pages: 394-429
DOI: 10.1145/201059.201071
Although attribute grammars have been very effective for defining individual modules of language translators, they have been rather ineffective for specifying large program-transformational systems. Recently, several new attribute grammar...