Sixteenth Annual ACM Symposium on

Principles of Programming Languages

Austin, January 11-13, 1989


Forword | Organizing Committee | Papers Presented | Index

Foreword

    The papers in this volume were presented at the Sixteenth Annual ACM SIGACT-SIGPLAN Symposium on Principles of Programming Languages, held January 11-13, 1989 in Austin, Texas. These 30 papers were selected from a total of 191 summaries submitted in response to the call for papers. Technical excellence and originality were the principal selection criteria, but readability, relevance, and the balance between theory and practice were also taken into account.
    Submissions were not formally refereed, but were reviewed by the program committee. Each summary was specifically assigned to three members of the program committee, but each member of the program committee received a copy of every summary and was encouraged to read as many summaries as possible in addition to those assigned to him. The committee then met for two days and discussed each paper before coming to a consensus on the 30 papers selected for the symposium.
    The committee also wishes to thank the following individuals who assisted us in the reviewing process: Steve Anderson, Andrew Appel, Didier Austry, Eric Bach, Joffroy Beauquier, Frederic Boussinot, Michael Burke, Dominique Clement, Thierry Coquand, Ron Cytron, Tom Dean, Robert de Simone, Joelle Despeyroux, Bruce Duba, Rodney Farrow, Jeanne Ferrante, Charles Fischer, Chris Fraser, George Gonthier, Suzanne Graf, Juan Guzman, Nicolas Halbwachs, Joe Halpern, Laurent Hascoet, Susan Horwitz, Gilles Kahn, Paris Kanellakis, Jean-Jacques Levy, Michel Mauny, Jose Meseguer, Mark Moriconi, Krishna Palem, Raghu Ramakrishnan, Barry Rosen, Jean-Bernard Saint, Marvin Solomon, Didier Vergamini, Mark Wegman, Ed Wimmers, Felix Wu, and Jonathan Young.

-top-

Organizing Committee

Conference Committee

Co-chairs

  • Michael J. O’Donnell (University of Chicago)
  • Stuart Feldman (Bellcore)
  • Local Arrangements

  • Brian Fugate (MCC)
  • Program Committee

  • Gerard Berry (Ecole Nationale Superieure des Mines de Paris)
  • Alan Demers (Xerox Palo Alto Research Center)
  • Joseph Goguen (SRI International)
  • David R. Hanson (Princeton University)
  • Paul Hudak (Yale University)
  • Butler Lampson (Digital Equipment Corporation)
  • David MacQueen (AT&T Bell Laboratories), Chair
  • John Mitchell (Stanford University)
  • Tom Reps (University of Wisconsin - Madison)
  • Moshe Vardi (IBM Almaden Research Center)
  • Ken Zadeck (Brown University)
  • -top-

    Papers Presented

    Tutorial: January 11 - Jeanne Ferrante (IBM T. J. Watson Research Center)

  • The program dependence graph and its uses

  • Session I: January 11 - Chaired by Kenneth Zadeck
     

  • The program dependence graph and vectorization

  •         William Baxter, Henry R. Bauer, III (University of Wyoming)
     
  • A rewriting semantics for program dependence graphs

  •         Rebecca Parsons Selke (Rice University)


    Session II: January 11 - Chaired by Thomas Reps
     

  • An efficient method of computing static single assignment form

  •         Ron Cytron, Jeanne Ferrante, Barry K. Rosen, Mark N. Wegman (IBM T. J. Watson Research Center)
            Kenneth Zadeck (Brown University)
     
  • Resolving circularity in attribute grammars with applications to data flow analysis

  •         S. Sagiv (The Technion)
            0. Edelstein (IBM Israel Scientific Center)
            N. Fancez (The Technion)
            M. Rodeh (IBM Israel Scientific Center)
     
  • Fast interprocedural alias analysis

  •         Keith D. Cooper, Ken Kennedy (Rice University)


    Session III: January 11 - Chaired by David Mac Queen
     

  • How to make ad-hoc polymorphism less ad hoc

  •         Philip Wadler, Stephen Blott (University of Glasgow)
     
  • Typechecking records and variants in a natural extension of ML

  •         Didier Remy (INRIA)
     
  • Extracting Fw ‘s programs from proofs in the Calculus of Constructions

  •         Christine Paulin-Mohring (INRIA and LIENS)
     
  • Polymorphic unification and ML typing

  •         Paris C. Kanellakis (Brown University)
            John C. Mitchell (Stanford University)


    Session IV: January 11 - Chaired by Joseph Goguen
     

  • Moded type systems for logic programming

  •         Katherine A. Yelick (MIT Laboratory for Computer Science)
            Joseph L. Zachary (University of Utah)
     
  • CLP* and constraint abstraction

  •         Timothy J. Hickey (Brandeis University)
     
  • Fully abstract compositional semantics for logic programs

  •         Haim Gaifman (The Hebrew University)
            Ehud Shapiro (The Weizmann Institute of Science)
     

    Tutorial: January 12th - Samson Abramsky (Imperial College of Science and Technology)

  • Concurrent Processes

  • Session V: January 12th - Chaired by Moshe Vardi
     

  • A calculus of higher order communicating systems

  •         Bent Thomsen (Imperial College of Science and Technology)
     
  • A fully abstract trace model for dataflow networks

  •         Bengt Jonsson (Swedish Institute of Computer Science)


    Session VI: January 12th - Chaired by Gerard Berry
     

  • Efficient temporal reasoning

  •         E. Allen Emerson, Tom Sadler, Jai Srinivasan (University of Texas at Austin)
     
  • On the synthesis of a reactive module

  •         Amir Pnueli, Roni Rosner (The Weizmann Institute of Science)
     
  • Synthesis of concurrent systems with many similar sequential processes

  •         Paul C. Attie, E. Allen Emerson (University of Texas at Austin)


    Session VII: January 12th - Chaired by John Mitchell
     

  • The Modula-3 type system

  •         Luca Cardelli (DEC Systems Research Center)
            Jim Donahue, Mick Jordan (Olivetti Research Center)
            Bill Kalsow, Greg Nelson (DEC Systems Research Center)
     
  • Dynamic typing in a statically-typed language

  •         Martin Abadi, Luca Cardelli (DEC Systems Research Center)
            Benjamin Pierce (Carnegie Mellon University)
            Gordon Plotkin (University of Edinburgh)
     
  • Relating models of polymorphism

  •         J. Meseguer (SRI International)
     
  • Generalized conjunctive types

  •         Gennaro Monteleone (Tecsiel)


    Session VIII: January 12th - Chaired by Paul Hudak
     

  • Rewrite, rewrite, rewrite, rewrite, rewrite ...

  •         Nachum Dershowitz (University of Illinois)
            Stephane Kaplan (The Hebrew University)
     
  • Partial order programming

  •         D. Stott Parker (University of California, Los Angeles)
     
  • Temporal logic programming is complete and expressive

  •         Marianne Baudinet (Stanford University)
     

    Session IX: January 13th - Chaired by Alan Demers
     

  • Realistic compilation by program transformation

  •         Richard Kelsey, Paul Hudak (Yale University)
     
  • Continuation-passing, closure-passing style

  •         Andrew Appel (Princeton University)
            Trevor Jim (AT&T Bell Laboratories)
     
  • Copy elimination in functional languages

  •         K. Gopinath, John L. Hennessy (Stanford University)


    Session X: January 13th - Chaired by Butler Lampson
     

  • Incremental computation via function caching

  •         William Pugh, Tim Teitelbaum (Cornell University)
     
  • Unified algebras and modules

  •         Peter D. Mosses (Aarhus University)
     
  • Bisimulation through probabilistic testing

  •         Kim C. Larsen (Aalborg University)
            Arne Skou (The University of Sussex)
     
    -top-