Conference Record

of

POPL® '97

The 24th ACM SIGPLAN-SIGACT
Symposium on
Principles of Programming Languages®



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

 


Contents and Schedule



Wednesday, January 15, 1997


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)

Thursday, January 16, 1997


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)

Friday, January 17, 1997


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)