Conference Record
of
Papers Presented at the Symposium
Paris, France
15-17 January 1997
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 36 accepted papers and one invited paper presented at POPL'97, the Twenty-Fourth Annual ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages. POPL'97 addresses fundamental principles and important innovations and accomplishments in the design, definition, analysis, and implementation of programming languages, programming systems, and programming interfaces. Both practical and theoretical papers on principles and innovations were solicited.
The papers were selected by the program committee from among 225 technical
summaries submitted in response to the call for papers. All program committee
members but one were able to attend the two-day selection meeting. The principle
selection criteria were significance, originality, relevance, correctness,
and clarity. Each summary received at least four reviews, done by the program
committee members or their subreferees (their names appear below). Assignments
to committee members were based on the summaries' subject areas and the
members' areas of expertise.
The SIGPLAN and SIGACT special-interest groups of the Association for Computing Machinery sponsored POPL'97 and four adjacent workshops: AAS'97, CW'97, FOOL-4, and DSL'97. Additional support for POPL'97 has been generously provided by the following agencies and institutions:
Centre National de la Recherche Scientifique
Commission of the European Communities (DG-III)
DIKU, University of Copenhagen
École des Mines de Paris
École Normale Superieure
École Polytechnique
Institut National de Recherche en Informatique et Automatique
Ministère de l'Éducation Nationale, de l'Enseignement Supérieur
et de la Recherche
Conference Committee
General Co-chairs
PETER LEE, Carnegie Mellon University
FRITZ HENGLEIN, University of Copenhagen
Local Arrangements Chair
RADHIA COUSOT, CNRS & École Polytechnique
Treasurer
EDOARDO BIAGIONI, Carnegie Mellon University
Program Chair
NEIL D. JONES, University of Copenhagen
Program Committee
ALEX AIKEN, University of California, Berkeley
HARALD GANZINGER, Max Planck Institute
ALESSANDRO GIACOLONE, ECRC, Munich
MASAMI HAGIYA, University of Tokyo
CHRIS HANKIN, Imperial College, London
LUDDY HARRISON, Connected Components
LAURIE HENDREN, McGill University
MANUEL HERMENEGILDO, Technical University of Madrid
NEIL D. JONES, University of Copenhagen
FRANK PFENNING, Carnegie Mellon University
WILLIAM PUGH, University of Maryland
DAVID SCHMIDT, Kansas State University
MARY SHEERAN, Chalmers Technical University
DOAITSE SWIERSTRA, Utrecht University
Invited Talk: 9:00-10:00 Chaired by Fritz Henglein (University
of Copenhagen)
Computing on Proofs
Gilles Kahn (INRIA, Sophia Antipolis)
Session 1: 10:30-12:30 Chaired by Laurie Hendren (McGill University)
Fast and Accurate Flow-Insensitive Points-To Analysis .......1
Marc Shapiro and Susan Horwitz (University of Wisconsin-Madison)
Partitioning Dataflow Analyses Using Types .......15
Erik Ruf (Microsoft Research)
Shape Types.......27
Pascal Fredet and Daniel Le Métayer (IRISA/INRIA, Campus de
Beaulieu, Rennes)
Objective ML: A Simple Object-Oriented Extension of ML.......40
Didier Rémy and Jérôme Vouillon (INRIA Rocquencourt)
Session 2: 14:00-16:00 Chaired by Frank Pfenning (Carnegie Mellon
University)
Rolling Your Own Mutable ADT - A Connection between Linear Types
and Monads -......54
Chih Ping Chen and Paul Hudak (Yale University)
Search and Imperative Programming .......67
Krzysztof R. Apt (University of Amsterdam) and Andrea Schaerf (Università
di Roma)
A Unified Computation Model for Functional and Logic Programming.......80
Michael Hanus (Informatik II, RWTH Aachen)
Call by Need Computations to Root-Stable Form .......94
Aart Middeldorp (University of Tsukuba)
Session 3: 16:30-18:30 Chaired by Luddy Harrison (Connected Components)
Proof-Carrying Code .......106
George C. Necula (Carnegie Mellon University)
Is "Just in Time" = "Better Late than Never"? .......120
Michael P. Plezbert and Ron K. Cytron (Washington University, St. Louis)
Parameterized Types for Java .......132
Andrew C. Myers, Joseph A. Bank, and Barbara Liskov (MIT)
Pizza into Java: Translating Theory into Practice .......146
Martin Odersky (University of Karlsruhe) and Philip Wadler (University of
Glasgow)
Invited Talk: 9:00-10:00 Chaired by William Pugh (University of Maryland)
Automatic Parallelization, Whence It Came, Where It's Going
Paul Feautrier (Université de Versailles St. Quentin)
Session 4: 10:30-12:30 Chaired by William Pugh (University of Maryland)
Determining the Idle Time of a Tiling.......160
Karin Hogstedt, Larry Carter, and Jeanne Ferrante (University of California,
San Diego)
Model Checking for Programming Languages using VeriSoft .......174
Patrice Godefroid (Bell Labs, Lucent Technologies)
Synchronization Transformations for Parallel Computing .......187
Pedro Diniz and Martin Rinard (University of California, Santa Barbara)
Maximizing Parallelism and Minimizing Synchronization with Affine Transforms
.......201
Amy W. Lim and Monica S. Lam (Stanford University)
Session 5: 14:00-16:00 Chaired by David Schmidt (Kansas State University)
A Curry-HouJard Foundation for Functional Computation with Control
.......215
C.-H. Luke Oong and Charles A. Stewart (Oxford University Computing Laboratory)
The Pi-calculus in Direct Style .......228
Gérard Boudol (INRIA, Sophia Antipolis)
Behavioral Equivalence in the Polymorphic Pi-calculus .......242
Benjamin C. Pierce (Indiana University) and Davide Sangiorgi (INRIA, Sophia
Antipolis)
Comparing the Expressive Power of the Synchronous and the Asynchronous
Pi-calculus .......256
Catuscia Palamidessi (Università di Genova)
Session 6: 16:30-18:30 Chaired by Alex Aiken (University of California,
Berkeley)
Program Fragments, Linking, and Modularization .......266
Luca Cardelli (Digital Equipment Corporation)
Minimal Typings in Atomic Subtyping .......278
Jakob Rehof (University of Copenhagen)
Typing Algorithm in Type Theory Pith Inheritance .......292
Amokrane Saïbi (INRIA Rocquencourt)
Type Checking Higher- Order Polymorphic Multi-Methods .......302
François Bourdoncle (École des Mines de Paris) and Stephan
Merz (Universität München)
Invited Talk: 9:00-10:00 Chaired by Neil D. Jones (University of
Copenhagen)
Types as Abstract Interpretations ........316
Patrick Cousot (École Normale Superieure)
Session 7: 10:30-12:30 Chaired by Manuel Hermenegildo (Technical
University of Madrid)
Infinitary Control Flow Analysis: a Collecting Semantics for Closure
Analysis .......332
Flemming Nielson and Hanne Riis Nielson (University of Aarhus)
Automatic Verification of Parameterized Linear Networks of Processes
.......346
David Lesens, Nicolas Halbwachs, and Pascal Raymond (VERIMAG)
On the Complerity of Escape Analysis .......358
Alain Deutsch (INRIA Rocquencourt)
A Demand-Driven Set-Based Analysis .......372
Sandip K. Biswas (University of Pennsylvania)
Session 8: 14:00-16:00 Chaired by Chris Hankin (Imperial College,
London)
Denotational Semantics Using an Operationally-Based Term Model .......386
Mitchell Wand and Gregory T. Sullivan (Northeastern University)
Constraints to Stop Higher- Order Deforestation .......400
Helmut Seidl (Universität Trier) and Morten H. Sørensen (University
of Copenhagen)
Reducing Nondeterminism while Specializing Logic Programs .......414
Alberto Pettorossi, Maurizio Proietti, and Sophie Renault
(University of Roma Tor Vergata)
From SOS Rules to Proof Principles: An Operational Metatheory for
Functional Languages .......428
David Sands (Chalmers University of Technology and University of Goteborg)
Session 9: 16:30-18:30 Chaired by Doaitse Swierstra (Utrecht University)
Relational Parametricity and Units of Measure.......442
Andrew J. Kennedy (LIX, École Polytechnique)
High Level Reading and Data Structure Compilation .......456
Robert Paige and Zhe Yang (New York University)
PolyP a Polylypic Programming Language Extension.......470
Patrik Jansson and Johan Jeuring (Chalmers University of Technology and
University of Göteborg)
First-class Polymorphism with Type Inference .......483
Mark P. Jones (University of Nottingham)