Programming Languages and Systems (TOPLAS)


Search Issue
enter search term and/or author name


ACM Transactions on Programming Languages and Systems (TOPLAS), Volume 16 Issue 3, May 1994

Program optimization and parallelization using idioms
Shlomit S. Pinter, Ron Y. Pinter
Pages: 305-327
DOI: 10.1145/177492.177494
Programs in languages such as Fortran, Pascal, and C were designed and written for a sequential machine model. During the last decade, several methods to vectorize such programs and recover other forms of parallelism that apply to more advanced...

Path analysis and the optimization of nonstrict functional languages
Adrienne Bloss
Pages: 328-369
DOI: 10.1145/177492.177497
The functional programming style is increasingly popular in the research world, but functional languages still execute slowly relative to imperative languages. This is largely because the power and flexibility of functional languages restrict...

Efficient register allocation via coloring using clique separators
Rajiv Gupta, Mary Lou Soffa, Denise Ombres
Pages: 370-386
DOI: 10.1145/177492.177499
Although graph coloring is widely recognized as an effective technique for register allocation, memory demands can become quite high for large interference graphs that are needed in coloring. In this paper we present an algorithm that uses the...

Debugging optimized code without being misled
Max Copperman
Pages: 387-427
DOI: 10.1145/177492.177517
Correct optimization can change the behavior of an incorrect program; therefore at times it is necessary to debug optimized code. However, optimizing compilers produce code that impedes source-level debugging. Optimization can cause...

Improvements to graph coloring register allocation
Preston Briggs, Keith D. Cooper, Linda Torczon
Pages: 428-455
DOI: 10.1145/177492.177575
We describe two improvements to Chaitin-style graph coloring register allocators. The first, optimistic coloring, uses a stronger heuristic to find a k-coloring for the interference graph. The second extends...

Metalevel building blocks for modular systems
Suresh Jagannathan
Pages: 456-492
DOI: 10.1145/177492.177578
The formal definition of any namespace device found in a programming language can be given in terms of transformations on a semantic environment. It is worthwhile, therefore, to consider the implications of incorporating environments as bona...

On the adequacy of graph rewriting for simulating term rewriting
J. R. Kennaway, J. W. Klop, M. R. Sleep, F. J. de Vries
Pages: 493-523
DOI: 10.1145/177492.177577

Parallel programming with control abstraction
Lawrence A. Crowl, Thomas J. LeBlanc
Pages: 524-576
DOI: 10.1145/177492.177584
Parallel programming involves finding the potential parallelism in an application and mapping it to the architecture at hand. Since a typical application has more potential parallelism than any single architecture can exploit effectively,...

A compiler approach to scalable concurrent-program design
Ian Foster, Stephen Taylor
Pages: 577-604
DOI: 10.1145/177492.177612
We describe a compilation system for the concurrent programming language Program Composition Notation (PCN). This notation provides a single-assignment programming model that permits concurrent-programming concerns such as...

Some comments on “a denotational semantics for Prolog”
Bijan Arbab, Daniel M. Berry
Pages: 605-606
DOI: 10.1145/177492.177605
Two independently derived denotational semantics for Prolog are contrasted, Arbab and Berry's for the full language and Nicholson and Foo's for a databaseless language. Using the ideas suggested by the former, the latter can be easily extended...

Denotational abstract interpretation of logic programs
Kim Marriott, Harald Søndergaard, Neil D. Jones
Pages: 607-648
DOI: 10.1145/177492.177650
Logic-programming languages are based on a principle of separation “logic” and “control.”. This means that they can be given simple model-theoretic semantics without regard to any particular execution mechanism (or proof...

Suspension analyses for concurrent logic programs
Michael Codish, Moreno Falaschi, Kim Marriott
Pages: 649-686
DOI: 10.1145/177492.177656
Concurrent logic languages specify reactive systems which consist of collections of communicating processes. The presence of unintended suspended computations is a common programming error which is difficult to detect using standard debugging...

On the occur-check-free PROLOG programs
Krzysztof R. Apt, Alessandro Pellegrini
Pages: 687-726
DOI: 10.1145/177492.177673
In most PROLOG implementations, for efficiency occur-check is omitted from the unification algorithm. This paper provides natural syntactic conditions that allow the occur-check to be safely omitted. The established results apply to most...

TransformGen: automating the maintenance of structure-oriented environments
David Garlan, Charles W. Krueger, Barbara Staudt Lerner
Pages: 727-774
DOI: 10.1145/177492.177697
A serious problem for programs that use persistent data is that information created and maintained by the program becomes invalid if the persistent types used in the program are modified in a new release. Unfortunately, there has been little...

A linear-time scheme for version reconstruction
Lin Yu, Daniel J. Rosenkrantz
Pages: 775-797
DOI: 10.1145/177492.177705
An efficient scheme to store and reconstruct versions of sequential files is presented. The reconstruction scheme involves building a data structure representing a complete version, and then successively modifying this data structure by applying...

Reasoning about probabilistic parallel programs
Josyula R. Rao
Pages: 798-842
DOI: 10.1145/177492.177724
The use of randomization in the design and analysis of algorithms promises simple and efficient algorithms to difficult problems, some of which may not have a deterministic solution. This gain in simplicity, efficiency, and solvability results...

Model checking and modular verification
Orna Grumberg, David E. Long
Pages: 843-871
DOI: 10.1145/177492.177725
We describe a framework for compositional verification of finite-state processes. The framework is based on two ideas: a subset of the logic CTL for which satisfaction is preserved under composition, and a preorder on structures which captures...

The temporal logic of actions
Leslie Lamport
Pages: 872-923
DOI: 10.1145/177492.177726
The temporal logic of actions (TLA) is a logic for specifying and reasoning about concurrent systems. Systems and their properties are represented in the same logic, so the assertion that a system meets its specification and the assertion that...

Adding fair choice to Dijkstra's calculus
Manfred Broy, Greg Nelson
Pages: 924-938
DOI: 10.1145/177492.177727
The paper studies the incorporation of a fair nondeterministic choice operator into a generalization of Dijkstra's calculus of guarded commands. The generalization drops the law of the excluded miracle to allow commands that correspond to...

A bounded first-in, first-enabled solution to the l-exclusion problem
Yehuda Afek, Danny Dolev, Eli Gafni, Michael Merritt, Nir Shavit
Pages: 939-953
DOI: 10.1145/177492.177731
This article presents a solution to the first-come, first-enabled -exclusion problem of Fischer et al. [1979]. Unlike their solution, this...

Coordinating first-order multiparty interactions
Yuh-Jzer Joung, Scott A. Smolka
Pages: 954-985
DOI: 10.1145/177492.177739
A first-order multiparty interaction is an abstraction mechanism that defines communication among a set of formal process roles. Actual processes participate in a first-order interaction by...

How to securely replicate services
Michael K. Reiter, Kenneth P. Birman
Pages: 986-1009
DOI: 10.1145/177492.177745
We present a method for constructing replicated services that retain their availability and integrity despite several servers and clients being corrupted by an intruder, in addition to others failing benignly. We also address the issue of...

Lazy and incremental program generation
J. Heering, P. Klint, J. Rekers
Pages: 1010-1023
DOI: 10.1145/177492.177750
Current program generators usually operate in a greedy manner in the sense that a program must be generated in its entirety before it can be used. If generation time is scarce, or if the input to the generator is subject to...

Controlled grammatic ambiguity
Mikkel Thorup
Pages: 1024-1050
DOI: 10.1145/177492.177759
A new approach to ambiguity of context-free grammars is presented, and within this approach the LL and LR techniques are generalized to solve the following problems for large classes of ambiguous grammars:...

Recognizing substrings of LR(k) languages in linear time
Joseph Bates, Alon Lavie
Pages: 1051-1077
DOI: 10.1145/177492.177768
LR parsing techniques have long been studied as being efficient and powerful methods for processing context-free languages. A linear-time algorithm for recognizing languages representable by LR(k) grammars has long been known. Recognizing...