Home → Magazine Archive → December 1975 (Vol. 18, No. 12)
Table of Contents
ACM president's letter: ACM diversity in (a) technical interests and (b) national and international interests
Jean E. Sammet
Pages 673-674
Papers from the second ACM symposium on principles of programming languages
Page 675
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 …
Peter Naur
Pages 676-683
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 …
John B. Goodenough
Pages 683-696
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
…
Mehdi Jazayeri, William F. Ogden, William C. Rounds
Pages 697-706
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 …
Harry B. Hunt, Thomas G. Szymanski, Jeffrey D. Ullman
Pages 707-716
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 …
Susan L. Graham, Mark Wegman
Page 716
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 …
Richard J. Lipton
Pages 717-721
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 …
J. T. Schwartz
Pages 722-728
ACM forum
Pages 740-743