line
acm acm

20 Years of the
ACM SIGPLAN Conference on Programming Language Design and Implementation (1979 - 1999):
A Selection

line

Introduction

The ACM SIGPLAN Conference on Programming Language Design and Implementation (PLDI) and its logical 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 the ACM Special Interest Group on Programming Languages (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 the nomination of 174 distinct papers. Each committee member then voted for 60 of these 174. 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 and discussed the final selection of all 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 selection criteria 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 also 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 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 provided two complete sets of nominations from the entire collection. Thanks to the community members for their thoughtful nominations (their names are listed below). I am very grateful to Jim Burrill, Gem Naivar, and Bill Yoder who helped by sending emails, assembling the web pages, and writing scripts that made this process go smoothly.

I would also like to thank Mark Mandelbaum and Roxanne Carcaterra at ACM headquarters who helped to stock the ACM digital libraries with the proceedings we needed. A special thanks to David Presberg who donated his entire collection of SIGPLAN proceedings and NOTICES, which expanded ACMs incomplete SIGPLAN archives. Our committee was thus able to access all the proceedings and papers from 1979 to 1999 using the ACM digital library, which made our work much more manageable.

I hope you enjoy reading this collection.

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
Community nominators

Saman Amarasinghe Ganesan Ramalingam Patricia C. Goldberg
David Bernstein David Grove Norman Ramsey
Rastislav Bodik Katsuro Inoue Sara Porat
Jeffrey Chen Jose Nelson Amaral Vivek Sarkar
Andrew Chien Katayama Takuya Sun C. Chan
Dekel Eliezer Patrick Logan Shingo Takada
Alain Deutsch Mikheev Vitaly Peter Thiemann
Dawson Engler Markus Mock Todd Proebsting
Anton Ertl Ikuo Nakata Vinod Grover
Chris Fraser Karl Ottenstein Michael Wolfe

Selected Papers by Year

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

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

  3. 1979
    Automatic Storage Optimization
    by Janet Fabri

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

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

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

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

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

  9. 1984
    Register Allocation by Priority-based Coloring
    by Frederick Chow and John Hennessy

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

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

  12. 1984
    Efficient Compilation of Lazy Evaluation
    by Thomas Johnsson

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

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

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

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

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

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

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

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

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

  22. 1988
    Control Flow Analysis in Scheme
    by Olin Shivers

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

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

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

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

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

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

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

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

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

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

  33. 1991
    Soft Typing
    by Robert Cartwright and Mike Fagan

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

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

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

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

  38. 1993
    Space Efficient Conservative Garbage Collection
    by Hans-Juergen Boehm

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

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

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

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

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

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

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

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

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

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

  49. 1999
    A Fast Fourier Transform Compiler
    by Matteo Frigo

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