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-