Programming Languages and Systems (TOPLAS)


Search Issue
enter search term and/or author name


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

A simple interprocedural register allocation algorithm and its effectiveness for LISP
Peter A. Steenkiste, John L. Hennessy
Pages: 1-32
DOI: 10.1145/59287.59289
Register allocation is an important optimization in many compilers, but with per-procedure register allocation, it is often not possible to make good use of a large register set. Procedure calls limit the improvement from global register...

Row replacement algorithms for screen editors
Eugene W. Meyers, Webb Miller
Pages: 33-56
DOI: 10.1145/59287.59290
Interactive screen editors repeatedly determine terminal command sequences to update a screen row. Computing an optimal command sequence differs from the traditional sequence comparison problem in that there is a cost for moving the cursor over...

Scheduling expressions on a pipelined processor with a maximal delay of one cycle
David Bernstein, Izidor Gertner
Pages: 57-66
DOI: 10.1145/59287.59291
Consider a pipelined machine that can issue instructions every machine cycle. Sometimes, an instruction that uses the result of the instruction preceding it in a pipe must be delayed to ensure that a program computes a right value. We assume...

Typed representation of objects by functions
J. Steensgaard-Madsen
Pages: 67-89
DOI: 10.1145/59287.77345
A systematic representation of objects grouped into types by constructions similar to the composition of sets in mathematics is proposed. The representation is by lambda expressions, which supports the representation of objects from function...

Distributed FIFO allocation of identical resources using small shared space
Michael J. Fischer, Nancy A. Lynch, James E. Burns, Allan Borodin
Pages: 90-114
DOI: 10.1145/59287.59292
We present a simple and efficient algorithm for the FIFO allocation of k identical resources among asynchronous processes that communicate via shared memory. The algorithm simulates a shared queue but uses exponentially fewer...

Efficient implementation of lattice operations
Hassan Aït-Kaci, Robert Boyer, Patrick Lincoln, Roger Nasr
Pages: 115-146
DOI: 10.1145/59287.59293
Lattice operations such as greatest lower bound (GLB), least upper bound (LUB), and relative complementation (BUTNOT) are becoming more and more important in programming languages supporting object inheritance. We present a general technique for...

Verifying temporal properties without temporal logic
Bowen Alpern, Fred B. Schneider
Pages: 147-167
DOI: 10.1145/59287.62028
An approach to proving temporal properties of concurrent programs that does not use temporal logic as an inference system is presented. The approach is based on using Buchi automata to specify properties. To show that a program satisfies a given...