Seventeenth Annual ACM Symposium on

Principles of Programming Languages®

San Francisco, January 17-19, 1990


Forword | Organizing Committee | Papers Presented | Index

Forward

    The papers in this volume were presented at the Seventeenth Annual ACM SIGACT-SIGPLAN Symposium on Principles of Programming Languages, held January 17-19, 1990 in San Francisco, California.  The program committee received 185 technical summaries, from which it selected 31 for presentation and publication. The submissions were not formally refereed, but were reviewed by the program committee with selected outside assistance. Each summary was assigned to at least three specific members of the committee for review. However, the committee members were strongly encouraged to read more summaries if possible, and ultimately each was read on average by almost four commmittee members. Technical quality, originality, relevance, and clarity were the primary criteria
for selection.

-top-

Organizing Committee

Conference Committee

Conference Chair
Frances E. Allen, IBM T.J. Watson Research Center

Registration Chair
Alex Aiken, IBM Research Almaden

Local Arrangements Chair
Stan Osborne, San Francisco State University

Book Exhibit Chair
Prof. Thomas J. Marlowe, Seton Hall University

Program Committee
Samson Abramsky, Imperial College
Andrew Appel, Princeton University
Luca Cardelli, DEC Systems Research Center
Saumya Debray, University of Arizona
Matthias Felleisen, Rice University
Jeanne Ferrante, IBM T.J. Watson Research Center
Susan Horwitz, University of Wisconsin-Madison
Paul Hudak, Chair, Yak University
Jayadev Misra, University of Texas
Ravi Sethi, AT&T Bell Laboratories

-top-

Papers Presented

Tutorial: January 17th - Henk Barendregt, Nijmegen University

  • Introduction to the Lambda Cakulus

  • Session I: January 17th - Chaired by Andrew Appel
     

  • On Laziness and Optimality in Lambda Interpreters: Tools for Specification and Analysis

  •         John Field (Cornell University)
     
  • An Algorithm for Optimal Lambda Cakulus Reduction

  •         John Lamping (Xerox PARC)


    Session II: January 17th - Chaired by Matthias Felleisen
     

  • Explicit Substitutions

  •         M. Abadi, L. Cardelli (DEC SRC),
            P.L. Curien (Ecole Normale Superieure),
            J.J. Levy (INRIA Rocquencourt)
     
  • A Formulae-as-Types Notion of Control

  •         Timothy 0. Griffin (Rice University)
     
  • Implicative Formulae in the Proofs of Computations’ Analogy

  •         Andrea Asperti, Gian Luigi Ferrari, Roberto Gorrieri (Universita di Pisa)


    Session III: January 17th - Chaired by Samson Abramsky
     

  • Computable Process

  •         Yiannis N. Moschovakis (UCLA)
     
  • The Chemical Abstract Machine

  •         Gerard Berry (Ecole des Mines de Paris)
            Gerard Boudol (INRIA Sophia-Antipolis)
     
  • Interaction Nets

  •         Yves Lafont (Ecole Normale Superieure)


    Session IV: January 17th - Chaired by Ravi Sethi
     

  • Toward a Typed Foundation for Method Specialization and Inheritance

  •         John C. Mitchell (Stanford University)
     
  • Inheritance is Not Subtyping

  •         William R. Cook, Walter L. Hill, Peter S. Canning (HP Laboratories)
     
  • A Type System for Smalltalk

  •         Justin 0. Graver, Ralph E. Johnson (University of Illinois)


    Tutorial: January 18th - John Hughes, University of Glasgow
    Introduction to Abstract Interpretation


    Session V: January 18th - Chaired by Paul Hudak
     

  • A Relationship Between Abstract Interpretation and Projection Analysis

  •         Geoffrey Burn (GEC Hirst Research Center)
     
  • On Determining Lifetime and Aliasing of Dynamically Allocated Data in Higher-order Functional Specifications

  •         Alan Deutsch (Ecole Polytechnique)


    Session VI: January 18th - Chaired by Saumya Debray
     

  • Small Domains Spell Fast Strictness Analysis

  •         R.C. Sekar, Shaunak Pawagi, I.V.Ramarkrishnan (SUNY at Stony Brook)
     
  • An Efficient Hybrid Algorithm for Incremental Data Flow Analysis

  •         Thomas J. Marlowe, Barbara G. Ryder (Rutgers University)
     
  • A Finite Presentation Theorem for Approximating Logic Programs

  •         Nevin Heintze (CMU)
            Joxan Jaffar (IBM T.J. Watson Research Center)


    Session VII: January 18th - Chaired by Jayadev Misra
     

  • Program Transformation in the Presence of Errors

  •         John H. Williams, Alexander Aiken, Edward L. Wimmers (IBM Almaden Research Center)
     
  • Making Asynchronous Parallelism Safe for the World

  •         Guy L. Steele, Jr. (Thinking Machines Corporation)
     
  • Concurrent Constraint Programming

  •         Vijay A. Saraswat (Xerox PARC)
            Martin Rinard (Stanford University)
     
  • Parallelism in Logic Programs

  •         Raghu Ramakrishnan (University of Wisconsin-Madison)
     
     

    Session VIII: January 18th - Chaired by Susan Horwitz
     

  • Combining Generational and Conservative Garbage Collection: Framework and Implementations

  •         Alan Demmers, Mark Weiser, Barry Hayes, Daniel Bobrow, Scott Shenker (Xerox PARC)
            Hans Boehm (Rice University)
     
  • Scheduling Time-Critical Instructions on RISC Machines

  •         Krishna Palem (IBM T.J. Watson Research Center)
            Barbara Simons (IBM Almaden Research Center)
     
  • Automata-Driven Indexing of Prolog Clauses

  •         R. Ramesh, I.V. Ramakrishnan, D.S. Warren (SUNY at Stony Brook)
     
     

    Session IX: January 19th - Chaired by Jeanne Ferrante
     

  • Fairness and Hyperfairness in Multi-Party Interactions

  •         Paul C. Attie (University of Texas)
            Nissim Francez (MCC and Technion)
            Orna Grumberg (Technion)
     
  • Relating Total and Partial Correctness Interpretations of Non-Deterministic Programs

  •         Carl A. Gunter (University of Pennsylvania)
     
  • On Oraclizable Networks and Kahn’s Principle

  •         James R. Russell (Cornell University)
     
  • On the Relations Computable by a Class of Concurrent Automata.

  •         Eugene W. Stark (SUNY at Stony Brook)


    Session X:  January 19th - Chaired by Luca Cardelli
     

  • Higher-Order Modules and the Phase Distinction

  •         Robert Harper (CMU)
            John C. Mitchell (Stanford University)
            Eugenio Moggi (University of Edinburgh)
     
  • Safe Run-time Overloading

  •         Francois Rouaix (INRIA Rocquencourt)
     
  • Quasi-static Typing

  •         Satish Thatte (Clarkson University)
     
  • Deciding ML Typability is Complete for Deterministic Exponential Time

  •         Harry G. Mairson (Brandeis University)
    -top-