Twentieth Annual ACM SIGPLAN-SIGACT Symposium on

Principles of Programming Languages®

Charleston, January 10-13, 1993


Forword | Organizing Committee | Papers Presented | Index

Foreword

    This volume contains 39 papers presented at the Twentieth Annual ACM Symposium on Principles of Programming Languages. The papers were selected by the program committee from a collection of 199 technical summaries submitted in response to a call for papers. The principal selection criteria were originality, significance, 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 three committee members based on the paper’s subject area and the members’ areas of expertise. In addition, every committee member received a copy of all of the summaries and reviewed as many summaries as possible. Every committee member attended the two day meeting at which the program was chosen.  The symposium was preceded by two half-day tutorials. Advanced tutorial lectures were given at the beginning of each of the first two days of the symposium.

-top-

Organizing Committee

Conference Committee

Conference Co-Chairs
Mary Van Deusen (IBM Watson Research Center)
Bernard Lang (INRIA Rocquencourt)

Local Arrangements Chair
Dee Medley (Augusta College)

Treasurer
Paul Kosinski (IBM Watson Research Center)

Program Chair
Susan L. Graham (University of California at Berkeley)

Program Committee

Martin Abadi (DEC Systems Research Center)
Hans-J. Boehm (Xerox PARC)
Ron Cytron (IBM Watson Research Center)
Charles Consel (Oregon Graduate Institute of Science and Technology)
Gilles Kahn (INRIA Sophia Antipolis)
Monica Lam (Stanford University)
James Larus (University of Wisconsin)
Gary Lindstrom (University of Utah)
David MacQueen (AT&T Bell Labs)
Frank Pfenning (Carnegie Mellon University)
Guy L. Steele (Thinking Machines Corp.)

-top-

Papers Presented

Session I: January 11 - Chaired by James Larus (University of Wisconsin)
 

  • Array-Data Flow Analysis and its Use in Array Privatization

  •         Dror E. Maydan, Saman P. Amarasingre,
            Monica S. Lam (Stanford University)
     
  • Automatic Array Alignment in Data-Parallel Programs

  •         Siddhartha Chatterjee, (NASA Ames Research Center),
            John R. Gilbert (Xerox Palo Alto Research Center),
            Robert Schreiber (NASA Ames Research Center),
            Shang-Huateng (MIT)
     
  • A Novel Framework of Register Allocation for Software Pipelining

  •         Qi Ning, Guang R. Gao (McGill University)


    Session II: January 11 - Chaired by Gilles Kahn (INRIA Sophia Antipolis)
     

  • Call by Name, Assignment, and the Lambda Calculus

  •         Martin Odersky, Dan Rabin, Paul Hudak (Yale University)
     
  • On the Orthogonality of Assignments and Procedures in Algol

  •         Stephen Weeks (Carnegie Mellon University)
            Matthias Felleisen (Rice University)
     
  • Imperative Functional Programming

  •         Simon L. Peyton Jones, Philip Wadler (University of Glasgow)


    Session III: January 11 - Chaired by Gary Lindstrom (University of Utah)
     

  • Communicating Reactive Processes

  •         G. Berry (Ecole des Mines de Paris)
            S. Ramesh (IIT Bombay)
            R.K. Shyamasundar (Tata Institute of Fundamental Research)
     
  • Semantics for Communication Primitives in a Polymorphic Language

  •         Atsushi Ohori (Old Electric Industry)
            Kazuhiko Kato (University of Tokyo)
     
  • A Concurrent, Generational Garbaqe Collector for a Multithreaded Implementation of ML

  •         Damien Doligez, Xavier Leroy (Ecole Normale Superieure and INRIA Roquencourt)
     

    Session IV: January 11 - Chaired by Guy L. Steele (Thinking Machines Corp.)
     

  • Separating Stages in the Continuation-Passing Style Transformation

  •         Julia L. Lawall (Indiana University)
            Olivier Danvy (Kansas State University)
     
  • Specifying the Correctness of Binding-Time Analysis

  •         Mitchell Wand (Northeastern University)
     
  • A Natural Semantics for Lazy Evaluation

  •         John Launchbury (University of Glasgow)

     


    Session V: January 12 - Chaired by David MacQueen (AT&T Bell Labs)
     

  • Formal Parametric Polymorphism

  •         Martin Abadi, Luca Cardelli (DEC Systems Research Center)
            Pierre-Louis Curien (CNRS Ecole Normale Superieure)
     
  • Relational Parametricity and Local Variables

  •         P.W. O’Hearn (Syracuse University)
            R.D. Tennent (University of Edinburgh)
     
  • Algebraic Reasoning and Completeness in Typed Languages

  •         Jon G. Riecke (AT&T Bell Labs)
            Ramesh Subrabmanyam (Wesleyan University)


    Session VI: January 12 - Chaired by Charles Consel (Oregon Graduate Institute of Science and Technology)
     

  • Graph Types

  •         Nils Klarlund, Michael I. Schwarbach (Aarhus University)
     
  • Explicit Polymorphism and CPS Conversion

  •         Robert Harper, Mark Lillibridge (Carnegie Mellon University)
     
  • Polymorphism by Name for References and Continuations

  •         Xavier Leroy (Ecole Normale Superieure and INRIA Roquencourt)
     

    Session VII: January 12 - Chaired by Monica Lam (Stanford University)
     

  • Efficient Flow-Sensitive Interprocedural Computation of Pointer-Induced Aliases and Side Effects

  •         Jong-Deok Choi, Michael Burke, Paul Carini (IBM T.J. Watson Research Center)
     
  • Automatic Generation and Management of Interprocedural Program Analyses

  •         Kwangkeun Yi, Williams Ludwell Harrison III (University of Illinois at Urbana-Champaign)
     
  • Static Single Assignment for Explicitly Parallel Programs

  •         Harini Srinivasan , James Hook, Michael Wolfe (Oregon Graduate Institute of Science and Technology)
     
  • Constructing Call Multigraphs Using Dependence Graphs

  •         Arun Lakhotia (University of Southwestern Louisiana)


    Session VIII: January 12 - Chaired by Martin Abadi (DEC Systems Research Center)
     

  • Safe Type Checking in a Statically- Typed Object-Oriented Programming Language

  •         Kim B. Bruce (Williams College)
     
  • Object-Oriented Programming without Recursive Types

  •         Benjamin C. Pierce, David N. Turner (University of Edinburgh)
     
  • A Constructive Logic of Multiple Subtyping

  •         Harry G. Mairson (DEC Cambridge Research Center)
     
  • Stratified Functional Programs and Computational Complexity

  •         Daniel Leivant (Indiana University)
     

    Session IX: January 12 - Chaired by Frank Pfenning (Carnegie Mellon University)
     

  • The 3 R ‘s of Optimizing Constraint Logic Programs: Refinement, Removal and Reordering

  •         Kimbal G. Marriott (IBM T.J. Watson Research Center)
            Peter J. Stuckey (University of Melbourne)
     
  • Layer Sharing: An Improved Structure-Sharing Framework

  •         E. Villemonte De La Clergerie (INRIA Roquencourt)
     
  • Differential Logic Programming

  •         A. Bossi, M. Bugliesi (Universita di Padova)
            M. Gabbrielli, G. Levi, M.C. Meo (Universita di Pisa)
     

    Session X: January 13 - Chaired by Ron Cytron (IBM Watson Research Center)
     

  • Evicted Variables and the Interaction of Global Register Allocation and Symbolic Debugging

  •         Ali-Reza Adl-Tabatabai, Thomas Gross (Carnegie Mellon University)
     
  • Incremental Program Testing Using Program Dependence Graphs

  •         Samuel Bates, Susan Horwitz (University of Wisconsin-Madison)
     
  • Complexity of Bi-Directional Data Flow Analysis

  •         Dhananjay M. Dhamdhere, Uday P. Khedker (LIT Bombay)


    Session XI: January 13 -Chaired by
     

  • Type Checking Type Classes

  •         Tobias Nipkow, Christian Prehofer (Technische Universitat, Munchen)
     
  • Efficient Recursive Subtyping

  •         Dexter Kozen (Cornell University)
            Jens Palsberg, Michael I. Schwartbach (Aarhus University)
     
  • A Sort Inference Algorithm for the Polyadic Pi-Calculus

  •         Simon J. Gay (Imperial College of Science, Technology and Medicine)


    Session XII: January 13 - Chaired by Hans-J. Boehm (Xerox PARC)
     

  • Smartest Recompilation

  •         Zhong Shao, Andrew W. Appel (Princeton University)
     
  • Compositional Analysis of Modular Logic Programs

  •         Michael Codish (KU Leuven, Belgium)
            Saumya K. Debray (University of Arizona)
            Roberto Giacobazzi (Universita di Pisa)
     
  • Extending Record Typing to Type Parametric Modules with Sharing

  •         Maria Virginia Aponte (Conservatoire National des Arts et Metiers and INRIA)
     
  • Quasi-Static Scoping: Sharing Variable Bindings Across Multiple Lexical Scopes

  •         Shinn-Der Lee, Daniel P. Friedman (Indiana University)
     -top-