POPL '96 Advance Program The 23rd Annual ACM SIGACT--SIGPLAN Symposium on Principles of Programming Languages St. Petersburg Beach, Florida 21--24 January 1996 Sponsored by ACM SIGPLAN and SIGACT SUNDAY, 21 January 1996 A full day of activities has been arranged to precede the main conference. A workshop will extend through most of the day. Concurrently there will be a tutorial in the afternoon. Due to the relatively large number of sequentially presented papers, there will be only one invited lecture, and it will be presented Sunday evening. As always, the invited lecture is free to conference at- tendees; however, fees are required to attend the workshop or the tutorial. 9:00--17:00 Workshop 20th Anniversary Scheme Workshop The Scheme programming language was born twenty years ago in the programming languages research of Gerald Sussman and Guy Steele. It has flourished in the programming languages re- search and computer science education communities, has become an IEEE and ANSI standard, and has recently enjoyed growing acceptance in industry. Gerald Sussman will deliver a keynote address entitled ``Proce- dural epistemology''. The remainder of the program will con- sist of invited talks and panel discussions that emphasize histori- cal perspective, future directions, and pedagogical possibilities of Scheme. Please see http://www.cs.indiana.edu/psw/ for details. Workshop Program Committee Chair: Chris Haynes (Indiana University) chaynes@cs.indiana.edu Members: Suresh Jaganathan (NEC Research Laboratories) John Ramsdell (Mitre Corporation) Carolyn Talcott (Stanford University) 13:00--17:00 Tutorial Chair: Hans-J. Boehm Code Optimization in Modern Compilers Krishna V. Palem (Courant Institute of Mathematical Sciences, NYU) and Vivek Sarkar (IBM Santa Teresa Laboratory) The primary goal of this tutorial is to provide an overview of state-of-the-art code optimization techniques used in compilers for modern processors. The performance gap between optimized and unoptimized code continues to widen as modern processors have evolved to include hardware features such as superscalar and pipelined functional units, and sophisticated memory hierarchies. Compile-time code optimization is critical to automatically har- nessing the high performance offered by modern processors. The tutorial is self-contained and begins with an overview of the design of optimizing compilers. Selected state-of-the-art opti- mizations such as instruction scheduling, register allocation and optimizations for memory hierarchies are then discussed in de- tail, using a quantitative framework to explain the key princi- ples. Issues related to interactions among individual optimiza- tions are also discussed. The optimizations covered in this tuto- rial are most relevant for RISC processors, and third-generation programming languages such as C and Fortran. 19:30--20:30 Invited Lecture Chair: Vijay Saraswat Java: Why we did the things we did James Gosling (Sun Microsystems) MONDAY, 22 January 1996 9:00--10:30 Chair: Daniel Weise Is it a Tree, a DAG, or a Cyclic Graph? A Shape Analysis for Heap-Directed Pointers in C. (Rakesh Ghiya and Laurie J. Hendren) (McGill University) Solving Shape-Analysis Problems in Languages with Destructive Updating. (Mooly Sagiv and Thomas Reps) (University of Wisconsin) and Reinhard Wilhelm (Universitat des Saarlandes) Points-to Analysis in Almost Linear Time. Bjarne Steensgaard (Microsoft Research) 11:00--12:30 Chair: Zhong Shao What Are Principal Typings and What Are They Good For? Trevor Jim (Massachusetts Institute of Technology) Putting Type Annotations to Work. Martin Odersky (University of Karlsruhe) and Konstantin Laufer (Loyola University Chicago) Using Parameterized Signatures to Express Modular Structure. Mark P. Jones (University of Nottingham) 14:00--16:00 Chair: Edward Wimmers Faster Checking of Software Specifications by Eliminating Isomorphs. (Daniel Jackson, Somesh Jha, and Craig A. Damon) (Carnegie Mellon University) Optimization and Relaxation in Constraint Logic Languages. (Kannan Govindarajan and Bharat Jayaraman) (SUNY at Buffalo) and Surya Mantha (Xerox Corporation) Pure versus Impure LISP. Nicholas Pippenger (University of British Columbia) On the Complexity of Beta-Reduction. Andrea Asperti (Universita Degli Studi Di Bologna) 16:30--18:00 Chair: Benjamin Zorn Filter Fusion. (Todd Proebsting and Scott A. Watterson) (University of Arizona) `C: A Language for High-Level, Efficient, and Machine- Independent Dynamic Code Generation. (Dawson R. Engler, Wilson C. Hsieh, and M. Frans Kaashoek) (Massachusetts Institute of Technology) A General Approach for Run-Time Specialization and its Application to C. (Charles Consel and Francois Noel) (University of Rennes) Reception TUESDAY, 23 January 1996 8:30--10:30 Chair: Hanne Riis Nielson Discovering Auxiliary Information for Incremental Computa- tion. (Yanhong A. Liu, Scott D. Stoller, and Tim Teitelbaum) (Cornell University) From Region Inference to von Neumann Machines via Region Representation Inference. Lars Birkedal (Carnegie Mellon University), Mads Tofte (University of Copenhagen), and Magnus Vejlstrup (NKT Elektronik) A Practical and Flexible Flow Analysis for Higher-Order Languages. J. Michael Ashley (Indiana University) Trace-Based Program Analysis. (Christopher Colby and Peter Lee) (Carnegie Mellon University) 11:00--12:30 Chair: Preston Briggs Iterated Register Coalescing. Lal George (AT&T Bell Labs) and Andrew W. Appel (Princeton University) Generating Machine Specific Optimizing Compilers. (Roger Hoover and Kenneth Zadeck) (IBM T. J. Watson Research Center) Minimum Cost Interprocedural Register Allocation. (Steven M. Kurlander and Charles N. Fischer) (University of Wisconsin---Madison) 14:00--16:00 Chair: Philip Wadler Type-Directed Partial Evaluation. Olivier Danvy (Aarhus University) A Modal Analysis of Staged Computation. (Rowan Davies and Frank Pfenning) (Carnegie Mellon University) Typed Closure Conversion. Yasuhiko Minamide (Kyoto University) and (Greg Morrisett and Robert Harper) (Carnegie Mellon University) Revisiting Catamorphisms over Datatypes with Embedded Functions (or, Programs from Outer Space). (Leonidas Fegaras and Tim Sheard) (Oregon Graduate Institute of Science & Technology) 16:30--18:00 Chair: Steven Lucco Concurrent Haskell. Simon Peyton Jones (University of Glasgow), Andrew Gordon (University of Cambridge), and Sigbjorn Finne (University of Glasgow) A Provably Time-Efficient Parallel Implementation of Full Speculation. (John Greiner and Guy E. Blelloch) (Carnegie Mellon University) Static Analysis to Reduce Synchronization Costs in Data- Parallel Programs. (Manish Gupta and Edith Schonberg) (IBM T. J. Watson Research Center) WEDNESDAY, 24 January 1996 8:30--10:30 Chair: Vijay Saraswat Functional Computation as Concurrent Computation. Joachim Niehren (German Research Center for Artificial Intelligence (DFKI)) Composing Processes. Kohei Honda (University of Manchester) Linearity and the Pi-Calculus. Naoki Kobayashi (University of Tokyo), Benjamin C. Pierce (University of Cambridge), and David N. Turner (University of Glasgow) The Reflexive CHAM and the Join-Calculus. (C'edric Fournet and Georges Gonthier) (INRIA Rocquencourt) 11:00--12:30 Chair: Robert Cartwright Bisimilarity for a First-Order Calculus of Objects with Subtyping. (Andrew D. Gordon and Gareth D. Rees) (University of Cambridge) An Interpretation of Objects and Object Types. (Mart'in Abadi and Luca Cardelli) (Digital Systems Research Center) and Ramesh Viswanathan (Isaac Newton Institute for Mathematical Sciences) Proving the Correctness of Reactive Systems Using Sized Types. (John Hughes, Lars Pareto, and Amr Sabry) (Chalmers University) ST. PETERSBURG Located on the Gulf of Mexico, St. Petersburg and the Bay Area averages 361 sunny days per year. The average day tempera- ture in January is 70.8 F (21.5 C) while the average nighttime temperature is 54.6 F (12.5 C). Local area attractions include Busch Gardens, Lowry Park Zoo, The Pier, Adventure Island, and The Florida Aquarium. The TradeWinds, a four-diamond beach resort located on an island 7 miles long and 1/4 mile wide, spans 18 lush acres dotted with meandering waterways, charming white foot bridges and Victorian gazebos. TRANSPORTATION Airport transfers are available from both Tampa International and St. Petersburg/Clearwater Airports directly to the resort through THE LIMO, INC. Tradewinds also features an on-site Avis Rent-A-Car office. AVIS: +1 (813) 360-2127 THE LIMO, INC.: (813) 572-1111. Driving Directions from Tampa International Airport: Take the lane to I-275 South, ``to St. Petersburg''. Exit I-275 South at the Pinellas Bayway (Exit 4) to St. Petersburg Beach. Turn Right, and Tradewinds is on the left about 1.5 miles north. General Chair Hans-J. Boehm boehm@parc.xerox.com Xerox Palo Alto Research Center 3333 Coyote Hill Road Palo Alto, CA 94304 +1 (415) 812--4435 Treasurer Ryan Stansifer ryan@cs.fit.edu Florida Institute of Technology +1 (407) 768--8000, ext. 7156 Conference Program Committee Chair: Guy L. Steele Jr. (Sun Microsystems Laboratories) guy.steele@east.sun.com Members: Preston Briggs (Tera Computer Company) Robert Cartwright (Rice University) Rance Cleaveland (North Carolina State University) Susan Horwitz (University of Wisconsin---Madison) David Loveman (Digital Equipment Corporation) Steven Lucco (Carnegie-Mellon University) Hanne Riis Nielson (Aarhus University) William Pugh (University of Maryland) Vijay Saraswat (Xerox Palo Alto Research Center) Zhong Shao (Yale University) Philip Wadler (University of Glasgow) Daniel Weise (Microsoft Research) Edward Wimmers (IBM Almaden Research) Benjamin Zorn (University of Colorado) Information and documents concerning the POPL '96 confer- ence and workshops are available in electronic form by (FTP) ftp://parcftp.xerox.com/pub/popl96/ (WWW) ftp://parcftp.xerox.com/pub/popl96/popl96.html