Programming Languages and Systems (TOPLAS)


Search Issue
enter search term and/or author name


ACM Transactions on Programming Languages and Systems (TOPLAS), Volume 11 Issue 4, Oct. 1989

Code generation using tree matching and dynamic programming
Alfred V. Aho, Mahadevan Ganapathi, Steven W. K. Tjiang
Pages: 491-516
DOI: 10.1145/69558.75700
Compiler-component generators, such as lexical analyzer generators and parser generators, have long been used to facilitate the construction of compilers. A tree-manipulation language called twig has been developed to help...

A generalization of Dijkstra's calculus
Greg Nelson
Pages: 517-561
DOI: 10.1145/69558.69559
Dijsktra's calculus of guarded commands can be generalized and simplified by dropping the law of the excluded miracle. This paper gives a self-contained account of the generalized calculus from first principles through the semantics of...

Concurrency in heavily loaded neighborhood-constrained systems
Valmir C. Barbosa, Eli Gafni
Pages: 562-584
DOI: 10.1145/69558.69560
Let G be a connected undirected graph in which each node corresponds to a process and two nodes are connected by an edge if the corresponding processes share a resource. We consider distributed computations in which processes...

Synchronization of asynchronous processes in CSP
Rajive Bagrodia
Pages: 585-597
DOI: 10.1145/69558.69561
Many concurrent programming languages including CSP and Ada use synchronous message-passing to define communication between a pair of asynchronous processes. Suggested primitives like the generalized alternative command for CSP and the symmetric...

I-structures: data structures for parallel computing
Arvind, Rishiyur S. Nikhil, Keshav K. Pingali
Pages: 598-632
DOI: 10.1145/69558.69562
It is difficult to achieve elegance, efficiency, and parallelism simultaneously in functional programs that manipulate large data structures. We demonstrate this through careful analysis of program examples using three common functional...

On the productivity of recursive list definitions
Ben A. Sijtsma
Pages: 633-649
DOI: 10.1145/69558.69563
Several related notions of the productivity are presented for functional languages with lazy evaluation. The notion of productivity captures the idea of computability, of progress of infinite-list programs. If an infinite-list program is...

A denotational semantics for Prolog
Tim Nicholson, Norman Foo
Pages: 650-665
DOI: 10.1145/69558.69564
A denotational semantics is presented for the language Pro.og. Metapredicates are not considered. Conventional control sequencing is assumed for Prolog's execution. The semantics is nonstandard, and goal continuations are used to explicate the...

Some comments on “A solution to a problem with Morel and Renvoise's 'Global optimization by suppression of partial redundancies'”
Arthur Sorkin
Pages: 666-668
DOI: 10.1145/69558.214513
Abstract: Drechsler and Stadel presented a solution to a problem with Morel and Renvoise's “Global Optimization by Suppression of Partial Redundancies.” We cite some earlier generalizations of Morel and Renvoise's algorithm that...