line
acm acm

20 Years of PLDI (1979 - 1999):
A Selection

line

Introduction

The ACM SIGPLAN Conference on Programming Language Design and Implementation (PLDI) and its predecessor, the Symposium on Compiler Construction, are a forum where researchers have presented original work on practical issues in the design, development, implementation, and use of programming languages. At the appointment of ACM SIGPLAN, our committee compiled a selection of what we found to be the 50 most influential papers published in PLDI from 1979 through 1999 into a special SIGPLAN proceedings.

We began by soliciting nominations from the committee and community at large. At least three committee members carefully reviewed all the papers in each year. We received 351 nominations from the community and the committee, resulting in 174 distinct papers nominations. Each committee member then voted for 60 of these 175. Excluding the top 29 papers, we voted again with 15 votes among the additional 45 papers that had garnered at least one vote in the previous round. We held a conference call to discuss the final selection of papers. We discussed conflict papers towards the end of the selection process, and the person with a conflict hung up and called back upon email notification. Of the 50 papers, 16 papers include one or more committee members as authors. Our primary criterion were impact and technical excellence.

The final issue will contain retrospectives from the authors, and we are in the process of notifying the authors and requesting retrospectives.

We hope this project will have many positive effects. The collection will highlight and honor papers that made a large impact on the field. We hope academics and practitioners will use it as a reading list for training and that beginning graduate students will use it to study for area exams. We hope our selection will serve to reemphasize early papers that may no longer be getting the attention (and citations!) they deserve. With the retrospectives, authors will discuss how the history of the work, and how the paper influenced their own and other subsequent people's work.

I would like to thank the committee for their outstanding efforts to assemble the best possible selection by reading through the old proceedings and thoughtfully examining the works of their colleagues. I would especially like to thank Guy Steele and Keith Cooper, both of whom examined all of the proceedings and thus providing two complete sets of nominations from the entire collection. I would also like to thank Jim Burrill who helped me assemble web pages and scripts and helped me make this process go smoothly as possible.

Sincerely,
Kathryn S. McKinley
Editor


Organizing Committee
Editor
Kathryn S. McKinley
The University of Texas at Austin

Program Committee
Keith D. Cooper, Rice University
Jack W. Davidson, The University of Virginia
Susan Eggers, The University of Washington, Seattle
Charles N. Fischer, The University of Wisconsin, Madison
Ken Kennedy, Rice University
Jim Larus, Microsoft Research
Peter Lee, Carnegie Mellon University
Barbara Ryder, Rutgers University
Michael D. Smith, Harvard University
Mary Lou Soffa, The University of Pittsburgh
Guy Steele, Sun Microsystems
Philip Wadler, Avaya Labs
Mark Wegman, IBM Research

Selected Papers by Year

1979
Code Generation in a Machine-Independent Compiler
by Roderic G. G. Cattell, Joseph M. Newcomer, and Bruce W. Leverett

1979
Efficient Computation of LALR(1) Look-Ahead Sets
by Frank DeRemer and Thomas J. Pennello

1979
Automatic Storage Optimization
by Janet Fabri

1982
An Overview of the PL.8 Compiler
by Marc Auslander and Martin Hopkins

1982
gprof: A Call Graph Execution Profiler
by Susan L. Graham, Peter B. Kessler, and Marshall K. Mckusick

1982
Optimization of Range Checking
by Victoria Markestein, John Cocke, and Peter Markstein

1982
Register Allocation and Spilling via Graph Coloring
by Gregory J. Chaitin

1984
Automatic Loop Interchange
by John R. Allen and Ken Kennedy

1984
Register Allocation by Priority-based Coloring
by Frederick Chow and John Hennesey

1984
Automatic Generation of Peephole Optimizations
by Jack W. Davidson and Christopher W. Fraser

1984
Parallel Processing: A Smart Compiler and a Dumb Machine
by Joseph A. Fisher, John R. Ellis, John C. Ruttenburg, and Alexandru Nicolau

1986
Interprocedural Dependence Analysis and Parallelization
by Michael Burke and Ron Cytron

1986
Interprocedural Constant Propagation
by David Callahan, Keith D. Cooper, Ken Kennedy, and Linda Torczon

1986
Efficient Instruction Scheduling for a Pipelined Architecture
by Philip B. Gibbons and Steven S. Muchnick

1986
ORBIT: An Optimizing Compiler for Scheme
by David Kranz, Richard Kelsey, Jonathan Rees, Paul Hudak, James Philbin, and Norman Adams

1986
Global Register Allocation at Link Time
by David W. Wall

1988
Real-time Concurrent Collection on Stock Multiprocessors
by Andrew W. Appel, John R. Ellis, and Kai Li

1988
Interprocedural Side-Effect Analysis in Linear Time
by Keith D. Cooper and Ken Kennedy

1988
Interprocedural Slicing Using Dependence Graphs
by Susan Horwitz, Thomas Reps, and David Binkley

1988
Software Pipelining: An Effective Scheduling Technique for VLIW Machines
by Monica Lam

1988
Control Flow Analysis in Scheme
by Olin Shivers

1988
Register Windows vs. Register Allocation
by David W. Wall

1989
Coloring Heuristics for Register Allocation
by Preston Briggs, Keith D. Cooper, Ken Kennedy, and Linda Torczon

1989
Customization: Optimizing Compiler Technology for SELF, A Dynamically-Typed Object-Oriented Programming Language
by Craig Chambers and David Ungar

1989
On-The-Fly Detection of Access Anomalies
by Edith Schonberg

1990
Improving Register Allocation for Subscripted Variables
by David Callahan, Steve Carr, and Ken Kennedy

1990
Analysis of Pointers and Structures
by David R. Chase, Mark Wegman, and F. Kenneth Zadeck

1990
How to Read Floating-Point Numbers Accurately
by William D. Clinger

1990
How to Print Floating-Point Numbers Accurately
by Guy L. Steele Jr., and Jon L. White

1990
Fast Breakpoints: Design and Implementation
by Peter B. Kessler

1990
Profile Guided Code Positioning
by Karl Pettis and Robert C. Hansen

1991
Soft Typing
by Robert Cartwright and Mike Fagan

1991
Predicting Program Behavior Using Real or Estimated Profiles
by David W. Wall

1991
A Data Locality Optimizing Algorithm
by Michael E. Wolf and Monica Lam

1992
Lazy Code Motion
by Jens Knoop, Oliver Ruthing, and Bernhard Steffen

1992
A Safe Approximate Algorithm for Interprocedural Pointer Aliasing
by William Landi and Barbara G. Ryder

1993
Space Efficient Conservative Garbage Collection
by Hans-Juergen Boehm

1993
The Essence of Compiling with Continuations
by Cormac Flanagan, Amr Sabry, Bruce F. Duba, and Matthias Felleisen

1993
Balanced Scheduling: Instruction Scheduling When Memory Latency is Uncertain
by Daniel R. Kerns and Susan J. Eggers

1994
ATOM: A System for Building Customized Program Analysis Tools
by Amitabh Srivastava and Alan Eustace

1996
Optimizing ML with Run-Time Code Generation
by Peter Lee and Mark Leone

1996
TIL: A Type-Directed Optimizing Compiler for ML
by David Tarditi, Greg Morrisett, Perry Cheng, Chris Stone, Robert Harper, and Peter Lee

1998
Improving Data-flow Analysis with Path Profiling
by Glenn Ammons and James R. Larus

1998
Thin Locks: Featherweight Synchronization for Java
by David F. Bacon, Ravi Konuru, Chet Murthy, and Mauricio Serrano

1998
Complete Removal of Redundant Computations
by Rastislav Bodik, Rajiv Gupta, and Mary Lou Soffa

1998
The Design and Implementation of a Certifying Compiler
by George C. Necula, and Peter Lee

1999
On Bounding Time and Space for Multiprocessor Garbage Collection
by Guy E. Blelloch and Perry Cheng

1999
A Fast Fourier Transform Compiler
by Matteo Frigo

1999
An Evaluation of Staged Run-Time Optimizations in DyC
by Brian Grant, Matthai Philipose, Markus Mock, Craig Chambers, and Susan J. Eggers