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