Conference Record
of
Papers Presented at the Symposium
St. Petersburg Beach, Florida
21-24 January 1996
Sponsored by the
Association for Computing Machinery
Special Interest Group on Algorithms and Computation Theory (SIGACT)
Special Interest Group on Programming Languages (SIGPLAN)
Foreword
This volume contains 34 papers presented at the Twenty-Third Annual ACM Symposium on Principles of Programming Languages. The papers were selected by the program committee from a collection of 148 technical summaries submitted in response to a call for papers. The principal selection criteria were significance, originality, correctness, and clarity.
The submissions were not formally refereed, but were reviewed by the program committee for presentation at the conference. The program chair assigned each technical summary to at least four committee members, based on each paper's subject area and the members' areas of expertise. In addition, every committee member received copies of each summary and reviewed as many summaries as possible. Every committee member (except one, because of sudden illness) attended the two-day meeting at which the program was chosen.
The symposium was preceded by a day of activities that included a workshop, a tutorial, and an invited lecture.
Conference Committee
General Chair
Hans-J. Boehm (Xerox Palo Alto Research Center)
Treasurer
Ryan Stansifer (Florida Institute of Technology)
Program Chair
Guy Steele (Sun Microsystems Laboratories)
Program Committee
Preston Briggs (Tera Computer Company)
Robert Cartwright (Rice University)
Rance Cleaveland (North Carolina State University)
Susan Horwitz (University of Wisconsin-Madison)
David Loveman (Digital Equipment Corporation)
Steven Lucco (Carnegie Mellon University)
Hanne Riis Nielson (Aarhus University)
William Pugh (University of Maryland)
Vijay Saraswat (Xerox Palo Alto Research Center)
Zhong Shao (Yale University)
Philip Wadler (University of Glasgow)
Daniel Weise (Microsoft Research)
Edward Wimmers (IBM Almaden Research)
Benjamin Zorn (University of Colorado)
Workshop: 9:00-17:00 Chaired by Chris Haynes (Indiana University)
20th Anniversary Scheme Workshop
Invited talks and panel discussions on the history, future, and pedagogical
possibilities of
the Scheme programming language.
Keynote address: Procedural Epistemology
Gerald Jay Sussman (Massachusetts Institute of Technology)
Tutorial: 13:00-17:00 Chaired by Hans-J. Boehm (Xerox Palo Alto Research
Center)
Code Optimization in Modern Compilers
Krishna V. Palem (Courant Institute of Mathematical Sciences, NYU) and
Vivek Sarkar (IBM Santa Teresa Laboratory)
Invited Lecture: 19:30-20:30 Chaired by Vijay Saraswat (Xerox Palo
Alto Research Center)
The Java Programming Language
James Gosling (Sun Microsystems)
Session 1: 9:00-10:30 Chaired by Daniel Weise (Microsoft Research)
Is it a Tree, a DAG, or a Cyclic Graph? A Shape Analysis for Heap-Directed
Pointers in C.......1
Rakesh Ghiya and Laurie J. Hendren (McGill University)
Solving Shape-Analysis Problems in Languages with Destructive Updating.......16
Mooly Sagiv and Thomas Reps (University of Wisconsin) and Reinhard Wilhelm
(Universitat des Saarlandes)
Points-to Analysis in Almost linear Time .......32
Bjarne Steensgaard (Microsoft Research)
Session 2: 11:00-12:30 Chaired by Zhong Shao (Yale University)
What Are Principal Typings and What Are They Good Ford .......42
Trevor Jim (Massachusetts Institute of Technology)
Putting Type Annotations to Work .......54
Martin Odersky (University of Karlsrnhe) and Konstantin Laufer (Loyola
University Chicago)
Using Parameterized Signatures to Express Modular Structure.......
68
Mark P. Jones (University of Nottingham)
Session 3: 14:00-16:00 Chaired by Edward Wimmers (IBM Almaden Research)
Faster Checking of Software Specifications by Eliminating Isomorphs........79
Daniel Jackson, Somesh Jha, and Craig A. Damon (Carnegie Mellon University)
Optimization and Relazation in Constraint Logic Languages
.......91
Kannan Govindarajan and Bharat Jayaraman (SUNY at Buffalo) and Surya Mantha
(Xerox Corporation)
Pure versus Impure LISP .......104
Nicholas Pippenger (University of British Columbia)
On the Complexity of Beta-Reduction .......110
Andrea Asperti (Universita Degli Studi Di Bologna)
Session 4: 16:30-18:00 Chaired by Benjamin Zorn (University of Colorado)
Filter Fusion .......119
Todd Proebsting and Scott A. Watterson (University of Arizona)
'C: A Language for High-Level, Efficient, and Machine-Independent
Dynamic Code Generation........131
Dawson R. Engler, Wilson C. Hsieh, and M. Frans Kaashoek (Massachusetts
Institute of Technology)
A General Approach for Run-Time Specialization and its Application
to C.......145
Charles Consel and François Noël (University of Rennes)
Session 5: 8:30-10:30 Chaired by Hanne Riis Nielson (Aarhus University)
Discovering Auxiliary Information for Incremental Computation
.......157
Yanhong A. Liu, Scott D. Staller, and Tim Teitelbaum (Cornell University)
From Region Inference to von Neumann Machines via Region Representation
Inference.......171
Lars Birkedal (Carnegie Mellon University), Mads Tofte (University of Copenhagen),
and Magnus Vejlstrup (NKT Elektronik)
A Practical and Flexible Flow Analysis for Higher-Order Languages.......184
J. Michael Ashley (Indiana University)
Trace-Based Program Analysis .......195
Christopher Colby and Peter Lee (Carnegie Mellon University)
Session 6: 11:00-12:30 Chaired by Preston Briggs (Tera Computer Company)
Iterated Register Coalescing.......208
Lal George (AT&T Bell Labs) and Andrew W. Appel (Princeton University)
Generating Machine Specific Optimizing Compilers .......219
Roger Hoover and Kenneth Zadeck (IBM T. J. Watson Research Center)
Minimum Cost Interprocedural Register Allocation.......230
Steven M. Kurlander and Charles N. Fischer (University of Wisconsin-Madison)
Session 7: 14:00-16:00 Chaired by Philip Wadler (University of
Glasgow)
Type-Directed Partial Evaluation .......242
Olivier Danvy (Aarhus University)
A Modal Analysis of Staged Computation.......258
Rowan Davies and Frank Pfenning (Carnegie Mellon University)
Typed Closure Conversion.......271
Yasuhiko Minamide (Kyoto University) and Greg Morrisett and Robert Harper
(Carnegie Mellon University)
Revisiting Catamorphisms over Datatypes with Embedded Functions (or,
Programs from Outer Space) ...........284
Leonidas Fegaras and Tim Sheard (Oregon Graduate Institute of Science &
Technology)
Session 8: 16:30-18:00 Chaired by Steven Lucco (Carnegie Mellon University)
Concurrent Haskell .......295
Simon Peyton Jones (University of Glasgow), Andrew Gordon (University
of Cambridge), and Sigbjorn Finne (University of Glasgow)
A Provably Time-Efficient Parallel Implementation of Full Speculation.......309
John Greiner and Guy E. Blelloch (Carnegie Mellon University)
Static Analysis to Reduce Synchronization Costs in Data-Parallel Programs.......322
Manish Gupta and Edith Schonberg (IBM T. J. Watson Research Center)
Session 9: 8:30-10:30 Chaired by Vijay Saraswat (Xerox Palo Alto
Research Center)
Functional Computation as Concurrent Computation .......333
Joachim Niehren (German Research Center for Artificial Intelligence (DFKI))
Composing Processes .......344
Kohei Honda (University of Manchester)
Linearity and the Pi-Calculus ........358
Naoki Kobayashi (University of Tokyo), Benjamin C. Pierce (University of
Cambridge), and David N. Turner (University of Glasgow)
The Reflexive CRAM and the Join-Calculus .........372
Cedric Fournet and Georges Gonthier (INRIA Rocquencourt)
Session 10: 11:00-12:30 Chaired by Robert Cartwright (Rice University)
Bisimilarity for a First-Order Calculus of Objects with Subtyping
.......386
Andrew D. Gordon and Gareth D. Rees (University of Cambridge)
An Interpretation of Objects and Object Types .......396
Martin Abadi and Luca Cardelli (Digital Systems Research Center) and Ramesh
Viswanathan (Isaac Newton Institute for Mathematical Sciences)
Proving the Correctness of Reactive Systems Using Sized Types........410
John Hughes, Lars Pareto, and Amr Sabry (Chalmers University)