Conference Record

of

POPL® '95

The 22nd ACM SIGPLAN-SIGACT
Symposium on
Principles of Programming Languages®



Papers Presented at the Symposium

San Francisco, California
22-25 January 1995


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-Second Annual ACM Symposium on Principles of Programming Languages. Also included is a corrigendum to a paper presented at the Twenty-First Symposium. The papers were selected by the program committee from a collection of 155 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 three 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 attended the two-day meeting at which the program was chosen.

The symposium was preceded by a day of activities that included two workshops, a tutorial, and two invited lectures.

Conference Committee

General Chair
Ron K. Cytron (Washington University)

Treasurer
Siddhartha Chatterjee (The University of North Carolina at Chapel Hill)

Publicity
Michael Hind (State University of New York at New Paltz)

Program Chair
Peter Lee ( Carnegie Mellon University)

Program Committee
Rance Cleaveland (North Carolina State University)
Radhia Cousot (Ecole Polytechnique)
Carl A. Gunter (University of Pennsylvania)
Fritz Henglein (University of Copenhagen)
Joxan Jaffar (IBM T. J. Watson Research Center)
Simon Peyton Jones (Glasgow University)
Samuel Kamin (University of Illinois)
Peter Lee (Carnegie Mellon University)
John Reppy (AT&T Bell Laboratories)
Barbara G. Ryder (Rutgers University)
David Ungar (Sun Microsystems Labs, Inc.)
Mitchell Wand (Northeastern University)
Daniel Weise (Microsoft Research)

 


Contents and Schedule



Sunday, 22 January 1995


Workshop: 8:30-17:30 Chaired by UDAY REDDY (University of Illinois)The Second ACM SIGPLAN Workshop on STATE in Programming Languages

Workshop: 8:30-15:00 Chaired by MICHAEL ERNST (Microsoft Research)The First ACM SIGPLAN Workshop on Intermediate Representations

Tutorial: 15:30-18:30 Chaired by RON CYTRON (Washington University)RICHARD KENNER (New York University): Targeting and Retargeting the GNU Optimizing Compiler

Invited Lecture: 19:00-20:30
Chaired by PETER LEE (Carnegie Mellon University)
ALEX AIKEN AND NEVIN HEINTZE (U.C. Berkeley and Carnegie Mellon University): Constraint-Based Program Analysis

Invited Lecture: 20:30 - 22:00
Chaired by BARBARA RYDER (Rutgers University)
THOMAS MARLOWE (Seton Hall University): Abstract Interpretation and Data Flow Analysis: Building Bridges

Monday, 23 January 1995


Session 1: 8:30 - 10:00 Chaired by CARL GUNTER (University of Pennsylvania)

Isolating Side Effects in Sequential Languages......1
JON G. RIECKE (AT&T Bell Laboratories) and RAMESH VISWANATHAN (Stanford
University)

Sequential Algorithms, Deterministic Parallelism, and Intensional Expressiveness .......13
STEPHEN BROOKES and DENIS DANCANET (Carnegie Mellon University)

Using Functor Categories to Generate Intermediate Code .........25
JOHN C. REYNOLDS (Imperial College of Science, Technology, and Medicine, and
Carnegie Mellon University)

Session 2: 10:30 - 12:30 Chaired by DANIEL WEISE (Microsoft Research)

Demand-driven Computation of Interprocedural Data Flow.........37
EVELYN DUESTERWALD, RAJIV GUPTA, and MARY LOU SOFFA (University of
Pittsburgh)

Precise Interprocedural Dataflow Analysis via Graph Reachability .......49
THOMAS REPS, SUSAN HORWITZ, and MOOLY SAGIV (University of Wisconsin)

A Linear Time Algorithm for Placing ø-nodes .......62
VUGRANAM C. SREEDHAR and GUANO R. GAO (McGill University)

An Extended Form of Must Alias Analysis for Dynamic Allocation .......74
RITA ALTUCHER and WILLIAM LANDI (Siemens Corporate Research)


Session 3: 14:00 - 15:30 Chaired by RANCE CLEAVELAND (North Carolina State University)

Reasoning about Rings ................. 85
E. ALLEN EMERSON and KEDAR S. NAMJOSHI (University of Texas at Austin)

Verifying Infinite State Processes with Sequential and Parallel Composition . . .....95
AHMED BOUAJJANI (VERIMAG), RACHID ECHAHED (LGI-IMAG), and PETER
HABERMEHL (VERIMAG)

Structured Operational Semantics as a Specification Language........107
BARD BLOOM (Cornell University)

Session 4: 16:00 - 18:00 Chaired by FRITZ HENGLEIN (University of Copenhagen)

Generic Polymorphism .......118
CATHERINE DUBOIS (Université Evry Val d'Essonne) and FRANÇOIS ROUAIX and
PIERRE WEIS (INRIA Rocquencourt)

Compiling Polymorphism Using Intensional Type Analysis .......130
ROBERT HARPER and GREG MORRISETT (Carnegie Mellon University)

Applicative Functors and Fully Transparent Higher-Order Modules.......142
XAVIER LEROY (INRIA Rocquencourt)

Higher-Order Functors with Transparent Signatures.......154
SANDIP K. BISWAS (University of Pennsylvania)




Tuesday, 24 January 1995


Session 5: 8:30 - 10:00 Chaired by MITCHELL WAND (Northeastern University)

Structural Decidable Extensions of Bounded Quantification.......164
SERGEI G. VOROBYOV (Centre de Recherche en Informnatique de Nancy and INRIA
Lorraine)

Lower Bounds on Type Inference with Subtypes.......176
MY HOANG and JOHN C. MITCHELL (Stanford University)

Positive Subtyping.........186
MARTIN HOFMANN and BENJAMIN PIERCE (University of Edinburgh)



Session 6: 10:30 - 12:35 Chaired by SIMON PEYTON JONES (Glasgow University)

The Geometry of Interaction Machine.......198
IAN MACKIE (Imperial College of Science, Technology, and Medicine)

The Semantics of Future and Its Use in Program Optimizations .......209
CORMAC FLANAGAN and MATTHIAS FELLEISEN (Rice University)

Total Correctness by Local Improvement in Program Transformation .......221
DAVID SANDS (University of Copenhagen)

The Call-by-Need Lamda Calculus ........233
ZENA M. ARIOLA (University of Oregon), MATTHIAS FELLEISEN (Rice University),
JOHN MARAIST and MARTIN ODERSKY (Universität Karlsruhe), and PHILIP
WADLER (University of Glasgow)



Session 7: 14:00-15:30 Chaired by JOXAN JAFFAR (IBM Watson Research Center)

Unification Factoring for Efficient Execution of Logic Programs....... 247
S. DAWSON, C. R. RAMAKRISHNAN, I. V. RAMAKRISHNAN, K. SAGONAS,
S. SKIENA, T. SWIFT, and D. S. WARREN (SUNY at Stony Brook)

Separation Constraint Partitioning - A New Algorithm for Partitioning Non-strict Programs into Sequential Threads ....... 259
KLAUS E. SCHAUSER (University of California at Santa Barbara) and DAVID
E. CULLER and SETH C. GOLDSTEIN (University of California at Berkeley)

Default Timed Concurrent Constraint Programming ........272
VIJAY A. SARASWAT (Xerox PARC), RADHA JAGADEESAN (Loyola University), and VINEET GUPTA (Xerox PARC)



Session 8: 16:00-18:00 Chaired by JOHN REPPY (AT&T Bell Laboratories)

A Language with Distributed Scope ........286
LUCA CARDELLI (Digital Equipment Corporation, Systems Research Center)

A Formal Model of Procedure Calling Conventions..........298
MARK W. BAILEY and JACK W. DAVIDSON (University of Virginia)

Obtaining Sequential Efficiency for Concurrent Object-Oriented Languages.......311
JOHN PLEVYAK, XINGBIN ZHANG, and ANDREW A. CHIEN (University of Illinois at Urbana-Champaign)

Optimizing an ANSI C Interpreter with Superoperators .......322
TODD A. PROEBSTING (University of Arizona)


Wednesday, 25 January 1995


Session 9: 8:30 - 10:00 Chaired by SAM KAMIN (University of Illinois)

Monad Transformers and Modular Interpreters............... 333
SHENG LIANG, PAUL HUDAK, and MARK JONES (Yale University)

Structuring Depth-First Search Algorithms in Haskell..........344
DAVID J. KING (University of Glasgow) and JOHN LAUNCHBURY (Oregon Graduate Institute of Science and Technology)

Time and Space Profiling for Non-Strict Higher-Order Functional Languages .......355
PATRICK M. SANSOM and SIMON L. PEYTON JONES (University of Glasgow)

Session 10: 10:30 - 12:00 Chaired by RADHIA COUSOT (École Polytechnique)

A Type System Equivalent to Flow Analysis.......367
JENS PALSBERG (Aarhus University) and PATRICK O'KEEFE (Watertown, MA)

Parametric Program Slicing....... 379
JOHN FIELD and G. RAMALINGAM (IBM T.J. Watson Research Center) and FRANK TIP (CWI)

A Unified Treatment of Flow Analysis in Higher-Order Languages .......393
SURESH JAGANNATHAN (NEC Research Institute) and STEPHEN WEEKS (Carnegie
Mellon University)

Corrigendum: Decidable Bounded Quantification .......408
GIUSEPPE CASTAGNA (LIENS(CNRS)) and BENJAMIN C. PIERCE (University of Edinburgh)