ACM DL

Programming Languages and Systems (TOPLAS)

Menu

Search Issue
enter search term and/or author name

Archive


ACM Transactions on Programming Languages and Systems (TOPLAS), Volume 19 Issue 3, May 1997

On the use of regular expressions for searching text
Charles L. A. Clarke, Gordon V. Cormack
Pages: 413-426
DOI: 10.1145/256167.256174
The use of regular expressions for text search is widely known and well understood. It is then surprising that the standard techniques and tools prove to be of limited use for searching structured text formatted with SGML or similar markup...

Kleene algebra with tests
Dexter Kozen
Pages: 427-443
DOI: 10.1145/256167.256195
We introduce Kleene algebra with tests, an equational system for manipulating programs. We give a purely equational proof, using Kleene algebra with tests and commutativity conditions, of the following classical result: every while...

Formal derivation of efficient parallel programs by construction of list homomorphisms
Zhenjiang Hu, Hideya Iwasaki, Masato Takechi
Pages: 444-461
DOI: 10.1145/256167.256201
It has been attracting much attention to make use of list homomorphisms in parallel programming because they ideally suit the divide-and-conquer parallel paradigm. However, they have been usually treated rather informally and ad hoc in the...

Optimal control dependence computation and the Roman chariots problem
Keshav Pingali, Gianfranco Bilardi
Pages: 462-491
DOI: 10.1145/256167.256217
The control dependence relation plays a fundamental role in program restructuring and optimization. The usual representation of this relation is the control dependence graph (CDG), but the size of the CDG can grow quadratically with the input...

Specifying representations of machine instructions
Norman Ramsey, Mary F. Fernández
Pages: 492-524
DOI: 10.1145/256167.256225
We present SLED, a specification language for Encoding and Decoding, which describes, abstract, binary, and assembly-language representations of machine instructions. Guided by a SLED specification, the New Jersey Machine-Code Toolkit generates...

Slicing real-time programs for enhanced schedulability
Richard Gerber, Seongsoo Hong
Pages: 525-555
DOI: 10.1145/256167.256394
In this article we present a compiler-based technique to help develop correct real-time systems. The domain we consider is that of multiprogrammed real-time applications, in which periodic tasks control physical systems via interacting with...