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-