Sign In

Communications of the ACM

Table of Contents


ACM president's letter: ACM diversity in (a) technical interests and (b) national and international interests


Papers from the second ACM symposium on principles of programming languages


Programming languages, natural languages, and mathematics

Some social aspects of pro gramming are illuminated through analogies with similar aspects of mathematics and natural languages. The split between pure and applied mathematics is found similarly in programming. The development …

Exception handling: issues and a proposed notation

This paper defines exception conditions, discusses the requirements exception handling language features must satisfy, and proposes some new language features for dealing with exceptions in an orderly and reliable way. The proposed …

The intrinsically exponential complexity of the circularity problem for attribute grammars

Attribute grammars are an extension of context-free grammars devised by Knuth as a mechanism for including the semantics of a context-free language with the syntax of the language. The circularity problem for a grammar is to  …

On the complexity of LR(k) testing

The problem of determining whether an arbitrary context-free grammar is a member of some easily parsed subclass of grammars such as the LR(k) grammars is considered. The time complexity of this problem is analyzed both when k …

A fast and usually linear algorithm for global flow analysis (abstract only)

ible graphs is presented. The algorithm is shown to treat a very general class of function spaces. For a graph of e edges, the algorithm has a worst case time bound of O(e log e) function operations. It is also shown that in …

Reduction: a method of proving properties of parallel programs

When proving that a parallel program has a given property it is often convenient to assume that a statement is indivisible, i.e. that the statement cannot be interleaved with the rest of the program. Here sufficient conditions …

Automatic data structure choice in a language of very high level

SETL is a set-theoretically oriented language of very high level whose repertoire of semantic objects includes finite sets, ordered n-tuples, and sets of ordered n-tuples usable as mappings. This paper describes the structure …

ACM forum