Programming Languages and Systems (TOPLAS)


Search Issue
enter search term and/or author name


ACM Transactions on Programming Languages and Systems (TOPLAS), Volume 2 Issue 1, Jan. 1980

And/Or Programs: A New Approach to Structured Programming
David Harel
Pages: 1-17
DOI: 10.1145/357084.357085
A simple tree-like programming/specification language is presented. The central idea is the dividing of conventional programming constructs into the two classes of and and or subgoaling, the subgoal tree itself...

Global Context Recovery: A New Strategy for Syntactic Error Recovery by Table-Drive Parsers
Ajit B. Pai, Richard B. Kieburtz
Pages: 18-41
DOI: 10.1145/357084.357086
Described is a method for syntactic error recovery that is compatible with deterministic parsing methods and that is able to recover from many errors more quickly than do other schemes because it performs global context recovery. The method...

Distributed Termination
Nissim Francez
Pages: 42-55
DOI: 10.1145/357084.357087
Discussed is a distributed system based on communication among disjoint processes, where each process is capable of achieving a post-condition of its local space in such a way that the conjunction of local post-conditions implies a global...

An Axiomatic Approach to Information Flow in Programs
Gregory R. Andrews, Richard P. Reitman
Pages: 56-76
DOI: 10.1145/357084.357088
A new approach to information flow in sequential and parallel programs is presented. Flow proof rules that capture the information flow semantics of a variety of statements are given and used to construct program flow proofs. The method is...

On the performance of balanced hashing functions when the keys are not equiprobable
Christos H. Papadimitriou, Philip A. Bernstein
Pages: 77-89
DOI: 10.1145/357084.357089
The cost (expected number of accesses per retrieval) of hashing functions is examined without the assumption that it is equally probable for all keys to be present in the table. It is shown that the obvious strategy—trying to balance the...

A Deductive Approach to Program Synthesis
Zohar Manna, Richard Waldinger
Pages: 90-121
DOI: 10.1145/357084.357090
Program synthesis is the systematic derivation of a program from a given specification. A deductive approach to program synthesis is presented for the construction of recursive programs. This approach regards program synthesis as a...

Uniform Random Generation of Balanced Parenthesis Strings
D. B. Arnold, M. R. Sleep
Pages: 122-128
DOI: 10.1145/357084.357091
The empirical testing of error repair schemes for skeletons of source programs in a block-structured language leads to the problem of generating balanced parenthesis strings in a uniform random manner. An efficient generator which works from...

A Note on Median Split Trees
Douglas Comer
Pages: 129-133
DOI: 10.1145/357084.357092
The median split tree is an elegant technique for searching static sets of keys when the frequency of access is highly skewed. This paper generalizes the median split search technique, relates it to sequential search and binary search, discusses...

Corrigendum: “A New Approach to Proving the Correctness of Multiprocess Programs”
Leslie Lamport
Page: 134
DOI: 10.1145/357084.357093