SIGPLAN (PROGRAMMING LANGUAGES) VOL. 34, NO. 1, JANUARY 1999 Contents Sunday 27 September 1998 Session 1: 13h-14h45 Chaired by Takayasu lto On the Runtime Complexity of Type-Directed Unboxing .................................................I Yasuhiko Minamide, Jacques Garrigue (Kyoto University) Building Program Optimizers -with Rewriting Strategies ................................................13 Eelco Visser, Zine-el-Abidine Benaissa, Andrew Tolmach (Pacific Sotware Research Center) Higher-Order Arity Raising .............................................................................27 John Hannan (Pennsylvania State University), Patrick Hicks (St. Vincent Archabbey) A Type Based Sharing Analysis for Update Avoidance and Optimisation ...............................39 Jorgen Gustavsson (Chalmers University) Session 2: 15hl5-16h30 Chaired by Julia Lawall Taming Effects with Monadic Typing ...................................................................51 Richard Kieburtz (Oregon Graduate Institute) The marriage of effects and monads ....................................................................63 Philip Wadler (Bell Laboratories) A Theory of Core Fudgets ..............................................................................75 Colin Taylor (University of Nottingham) Business meeting; 16h30-17h Monday 28 September 1998 Invited talk: 8h45-9h45 Calling hell from heaven and heaven from hell •. . Erik Meijer (University of Utrecht) Session 3: 10hl5~12h Chaired by Daniel P. Friedman PLAN: A Programming Language for Active Networks .................................................86 Michael Hicks, Pankaj Kakkar, Jonathan T. Moore, Carl A. Gunter, Scott Nettles (Univer- sity of Pennsylvania) Modular Object-Oriented Programming with Units and Mixins .........................................94 Robert Bruce Findler, Matthew Flatt (Rice University) Programming with Variable Functions................................................................. 105 Martin Odersky (University of South Australia) YALE: Yet Another Lambda Evaluator Based on Interaction Nets..................................... 117 lan Mackie (Ecole Polytechnique) Session 41 13h30-15hl5 Chaired by Paul Hudak Compiling Standard ML to Java Bytecodes............................................................ 129 Nick Benton, Andrew Kennedy, George Russell (University of Cambridge) Typed Cross-Module Compilation ..................................................................... 141 Zhong Shao (Yale University) H/Direct: A Binary Foreign Language Interface for Haskell............................................ 153 Sigbjom Finne (University of Glasgow), Daan Leijen (University of Utrecht), Erik Meijer (University of Utrecht), Simon Peyton Jones (University of Glasgow) The Spineless Tagless G-machine, naturally ............................................................163 Jon Mountjoy (University of Amsterdam) Session 5: 15h45-17h30 Chaired by Andrew D. Gordon Lava: Hardware Design in Haskell..................................................................... 174 Per Bjesse, Koen Claessen, Mary Sheeran (Chalmers University), Satnam Singh (Xilinx) Lazy Computation with Exact Real Numbers.......................................................... 185 Abbas Edalat, Peter John Potts, Philip? Siinderhauf (Imperial College) Functional Differentiation of Computer Prograins...................................................... 195 Jerzy Karczmarczuk (Universite de Caen) A Distributed Garbage Collector with Diffusion Tree Reorganisation and Mobile Objects .............. 204 Luc Moreau (University of Southampton) Tuesday 29 September 1998 Session 61 8h45-10h Chaired by Hanne Riis Nielson Pragmatic Subtyping in Polymorphic Languages .......................................................216 Johan Nordlander (Chalmers University) A Framework for Type Inference with Subtyping ...................................................... 228 Frangois Pettier (INRIA-Rocquencourt) Cayenne — a language with dependent types.......................................................... 239 Lennart Augustsson (Chalmers University) Session 7: 10h30-12hl5 Chaired by Erik Meijer Recycling Continuations ...............................................................................251 Jonathan Sobel, Daniel P. Priedman (Indiana University) Imperative Streams — A Monadic Combinator Library for Synchronous Programming .................261 Enno Scholz (Daimler-Benz) The Under-Appreciated Unfold ........................................................................273 Jeremy Gibbons (Oxford Brookes University), Geraint Jones (University of Oxford) Fold and Unfold for Program Semantics ............................................................... 280 Graham Hutton (University of Nottingham) Session 81 13h45-15h Chaired by Robert Harper Encoding Types in ML-like Languages .................................................................289 Zhe Yang (New York University) Intensional Polymorphism in Type-Erasure Semantics ................................................. 301 Karl Crary, Stephanie Weirich, Greg Morrisett (Cornell University) Implementing Typed Intermediate Languages ..........................................................313 Zhong Shao, Christopher League, Stefan Monnier (Yale University) A Non-Deterministic Call-by-Need Lambda Calculus .................................................. 324 Ame Kutzner, Manfred Schmidt-Schauft (Goethe Universitat) Posters Land*: an AND with local bindings, a guarded LET* special form ..................................... 336 Oleg Kyselov (Computer Sciences Corporation) Functional Style in C++: Closures, Late Binding, and Lambda Abstractions .......................... 337 Oleg Kyselov (Computer Sciences Corporation) Type Errors Confuse the Programmer................................................................. 338 Bruce J. McAdam (University of Edimburgh) Controlled Temporal Non-Determinism For Reasonning With A Machine Of Finite Speed.............. 339 Robert Ennals (University of Cambridge) Verbose typing........................................................................................ 340 Robert Ennals (University of Cambridge) On Application of Self-Similar Pictures in Education .................................................. 341 Zoran Putnik (Faculty of Yugoslavia) MAP: A Functional Analysis and Design Method...................................................... 342 Dan Russell (Kingstown University) A delegation language to request weather products and a scheme of its interpretation.................. 343 Oleg Kyselov (Computer Sciences Corporation) A Structured Approach to Retrieving Functions by Types ............................................. 344 Nancy Qiuyan An (University of Windsor), Young Park (Amdahl Software Limited) . Frob: Functional Robotics............................................................................. 345 Gary Shu Ling (Yale University) A Functional Programming Approach to Hypermedia Authoring....................................... 346 Daniel Marcos, Pablo Martinez Lopez, Walter Risi (Universidad Nacional de La Plata) A Term Calculus for a Unitary Approach to Normalization ............................................ 347 Claudia Faggian (Universita di Padova) Implementing Design Patterns as Language Constructs ................................................ 348 Yan-David Erlich (Rice University) A lazy CGI namespace in Scheme ..................................................................... 349 Oleg Kyselov (Computer Sciences Corporation) Automating Derivation of Incremental Programs ...................................................... 350 Yuchen Zhang, YanhongA. Lin (Indiana University) Combining CFG and Recursive Functions to Get a New Language..................................... 351 Chen Haiming

________________________________

853.htm


SIGPLAN (PROGRAMMING LANGUAGE)
VOL.34, NO.5, MAY 1999

Cache-Conscious Structure Layout ................................................................................................................1
Trishul M. Chilimbi (University of Wisconsin), Mark D. Hill (University of Wisconsin) and
James R. Larus (Microsoft Research)

Cache-Conscious Structure Definition ...........................................................................................................13
Trishul M. Chilimbi (University of Wisconsin), Bob Davidson (Microsoft Research), and
James R. Larus (Microsoft Research)

9:50am- ll:20am Session II Chair: John Hughes

A Semantics for Imprecise Exceptions ...........................................................................................................25
Simon Peyton Jones (Microsoft Research), Alastair Reid (Yale University), Tony Hoare
(Cambridge University), Simon Marlow (Microsoft Research), and Fergus Henderson
(University of Melbourne)

The Design of a Class Mechanism for Moby ...............................................................................................37
Kathleen Fisher (AT&T Labs, R.esearch) and John Reppy (Bell Labs, Lucent Technologies)

What is a Recursive Module ?................. ........ ..................... ............. .................................................... 50
Karl Crary (Carnegie Mellon University), Robert Harper (Carnegie Mellon University), and
Sidd Puri (Microsoft Corporation)

2:00pm - 3:30pm Session III Chair: Harini Srinivasan

Load-Reuse Analysis: Design and Evaluation ........................................................................................64
Rastislav Bodi'k, Rajiv Gupta, and Mary Lou Soffa (University of Pittsburgh)

Pointer Analysis for Multithreaded Programs ........................................................................................77
Radu Rugina and Martin Rinard (Massachusetts Institute of Technology)

Pointer Analysis for Programs with Structures and Casting ................................................................91
Suan Hsi Yong, Susan Horwitz, and Thomas Reps (University of Wisconsin)

4:00pm - 5:00pm Session IV Chair: Zhong Shao

On Bounding Time and Space for Multiprocessor Garbage Collection................................................. 104
Guy E. Blelloch and Perry Cheng (Carnegie Mellon University)

Support for Garbage Collection at Every Instruction in a Java Compiler ..............................................118
James M. Stichnoth, Guei-Yuan Lueh, and Michal Cierniak (Intel Corporation)

5:00pm - 5:30pm SIGPLAN Open Meeting
6:00pm - 7:30pm Student Poster Session




Storage Assignment Optimizations to Generate Compact and Efficient Code on
Embedded DSPs ............................................................................................................................................128
Amit Rao (Synopsis, Inc.) and Santosh Pande (University of Cincinnati)

Enhanced Code Compression for Embedded RISC Processors .......................................................................139
Keith D. Cooper (Rice University) and Nathaniel Mcintosh (Hewlett-Packard Corporation)

9:50am - ll:20am Session VI Chair: David Wall
Using Node Merging to Enhance Graph Coloring ........................................................................................... 150
Steven R. Vegdahl (University of Portland)

Control CPR: A Branch Height Reduction Optimization for EPIC Architectures ..............................................155
Michael Schlansker (Hewlett-Packard Laboratories), Scott Mahike (Hewlett-Packard
Laboratories), and Richard Johnson (Transmeta Corp.)

A Fast Fourier Transform Compiler ............................................................................................................... 169
Matteo Frigo (Massachusetts Institute of Technology

2:00pm - 3:30pm Session VII Chair: Kath Knobe
A New Framework for Debugging Globally Optimized Code ........................................................................ 181
Le-Chun Wu (University of Illinois), Rajiv Mirani (Hewlett-Packard Company), Harish Patil
(Compaq Computer Corporation), Bruce Olsen (Hewlett-Packard Company), and Wen-rnei
W. Hwu (University of Illinois)

A Theory of Type Qualifiers ....................................................................................................................... 192
Jeffrey S. Foster, Manuel Fahndrich, and Alexander Aiken (University of California, Berkeley)

Static Single Assignment Form for Machine Code ......................................................................................... 204
Alien Leung (New York University) and Lal George (Bell Labs)

4:00pm - 5:00pm Session VIII Chair: Michael Burke
Industrial Panel: Trends in the Future of Industrial Computing
Jim Rhyne (IBM Corporation), Steven Lucco (Microsoft), Edward Felten (Princeton
University), Guy L. Steele, Jr. (Sun Microsystems), Joe Paradise (MIT Media Lab)

5:00pm - 5:30pm Program Committee Chair's Report
8:00pm - 10:30pm Reception and ACM SIGPLAN Awards Ceremony
Tuesday, 4 May 1999

8:30am - 9:30am Session IX Chair: Chau-Wen Tseng
New Tiling Techniques to Improve Cache Temporal Locality ......................................................................... 215
Yonghong Song and Zhiyuan Li (Purdue University)



Improving Cache Performance of Dynamic Applications through Data and Computation
Reorganization at Run Time .......................................................................................................................229
Chen Ding and Ken Kennedy (Rice University)

9:50am - ll:20am Session X Chair: Christian Collberg
Automatic Inference of Models for Statistical Code Compression............................................................... 242
Christopher W. Fraser (Microsoft Research)

Compressing Java Class Files .................................................................................................................... 247
William Pugh (University of Maryland)

Whole Program Paths ................................................................................................................................ 259
James R. Larus (Microsoft Research)
2:00pm - 3:30pm Session XI Chair: Anton Erti

Finite-State Code Generation .................................................................................................................... 270
Christopher W. Fraser and Todd A. Proebsting (Microsoft Research)

Efficient Incremental Run- Time Specialization for Free ..............................................................................281
Renand Marlet, Charles Coiisel, and Philippe Boinot (IRJSA/INRIA/University ofRennes 1)

An Evaluation of Staged Run-Time Optimizations in DyC ......................................................................... 293
Brian Grant, Matthai Philipose, Markus Mock, Craig Chambers, and Susan J. Eggers
(University of Washington)
4:00pm - 4:15pm PLDF99 Awards Ceremony

Presentation of PLDI'99 Best Presentation and Most Innovative Paper Awards) selected by
onsite voting by registrants
4:15pm - 6:00pm National Compiler Infrastructure Progress Report




_______________________________

853.htm

SIGPLAN (PROGRAMMING LANGUAGES)

FEBRUARY 1999 VOL.34 NO.2

Letter From The Editor
A Correction and Apology 1
Activities
Panel Sessions at SIGPLAN Conferences by Michael Burke 2
Conference Corner
Calendar 4
Calls for Papers 16
The European Scene
EAPLS and ERCIM PLT by Neil jones 19
Functional Programming
Paths between Imperative and Functional Programming by Thomas Ball 21
Practical Parsing Patterns
What to Do With a Dangling Else by Chris Clark 26
Java Reflections
Inner Classes by Brent W. Benson, Jr. 32
Forth
Forth and the Open Terminal Architecture by Paul Frenger 36
Technical Correspondence
Information for Authors 40
Letters to the Editor 41
M. Carlisle, M. Feldman, P. Bigot, A. Syropoulos
Declarative Peephole Optimization Using String Pattern Matching 47
Diomidis Spinellis
A Type System of Logic Objects 52
Dianxiang Xu


________________________________

853.htm


SIGPLAN (PROGRAMMING LANGUAGES) (023)

VOL: 34, NO: 3, MARCH 1999

Table of Contents

A Compacting Incremental Collector and its Performance in a Production Quality Compiler.............................................. 1
Martin Larose and Marc Feeley (Universite de Montreal)

Combining Card Marking with Remembered Sets: How to Save Scanning Time..................................................................... 10
Alain Azagury, Eliot Kolodner, Erez Petrank and Zvi Yehudai (IBM Haifa Research Laboratory)

Barrier techniques for Incremental Tracing.............................................................................................................................. 20
Pekka P. Pirinen (Harlequin)

The Memory Fragmentation Problem: Solved?........................................................................................................................ 26
Mark S. Johnstone and Paul R. Wilson (Motorola Somerset Design Center and University of Texas at Austin)

Usin^ Ctcncmlionol Garbage Collection to Implement Cache-Conscious Data Placement..................................................... 37
Tlishlil M. Clulilnbi nnd .Inincs R. Lniiis ( University of Wisconsin-Madison)

One-bit Counts between Unique and Sticky............................................................................................................................ 49
David J. Roth and David S. Wise (Indiana University)

Hierarchical Distributed Reference Counting............................................................................................................................ 57
Luc Moreau (University of Southampton)

Comparing Mostly-Copying and Mark-Sweep Conservative Collection................................................................................. 68
Frederick Smith and Greg Morrisett (Comell University)

A Non-Fragmenting, Non-Moving, Garbage Collector ............................................................................................................ 79
Gustavo Rodriguez-Rivera, Michael Spertus and Charles Fiterman (Geodesic Systems)

Garbage Collection in Generic Libraries................................................................................................................................... 86
Gor V. Nishanov and Sibylle Schupp (Rensselaer Polytechnic Institute)

Memory Managementfor Prolog with Tabling......................................................................................................................... 97
Bart Demoen and Konstantinos Sagonas (Katholieke Universiteit Leuven)

The bits between the lambdas- binary data in a lazy Functional language................................................................ ...... 107
Malcolm Wallace and Colin Runciman (University of York)

A Memory-Efficient Real-Time Non-Copying Garbage Collector......................................................................................... 118
Tian F. Lim, Przemyslaw Pardyak and Brian N. Bershad (University of Washington)

Guaranteeing Non-Disruptiveness and Real-Time Deadlines in an Incremental Garbage Collector..................................... 130
Fridtjof Siebert, (Open Group Research Institute)

A Study of Large Object Spaces.............................................................................................................................................138
Michael W. Hicks, Luke Homof, Jonathan T. Moore and Scott M. Nettles (University of Pennsylvania)

Portable Run-Time Type Description for Conventional Compilers........................................................................................146
Sheetal V. Kakkad, Mark S. Johnstone and Paul R. Wilson (University of Texas at Austin and
Motorola Somerset Design Center)

Compiler Support to Customize the Markand Sweep Algorithm........................................................................................... 154
Dominique Colnet, Philippe Coucaud and Olivier Zendra (INRIA-CNRS-Universite Henri Poincare)

Very Concurrent Mark-&-Sweep Garbage Collection without Fine-Grain Synchronization............................................... 166
Lorenz Huelsbergen and Phil Winterbottom (Bell Laboratories)

Memory Allocation for Long-Running Server Applications.................................................................................................... 176
Per-Ake Larson and Murali Krishnan (Microsoft )

Invited talk: A Brief Introduction to Regions .......................................................................................................................... 186
Mads Tofte (UC Berkeley)


_______________________________

853.htm

SIGPLAN (PROGRAMMING LANGUAGE)
VOL:34, NO:4, APRIL 1999

Activities
Corporate Support and SIGPLAN by Ben Zom 1
Conference Corner
Calendar 3
FCRC '99 16
PLDI ' 99 Advance Program 17
Practical Parsing Patterns
Build a Tree—Save a Parse by Chris dark , 19
Java Reflections
JavaScript by Brent Benson 25
Forth
Parallel Forth by Paul Frenger 28
Resources
Mozart by Peter Van Roy 33
Functional Programming
Microsoft and Yale Conclude Agreement to License Technology for Haskell 35
by John Peterson
Technical Correspondence
Information for Authors 37
Java's Insecure Parallelism 38
Per Brinch Hansen
Early Storage Reclamation in a Tracing Garbage Collector 46

Timothy Harris
Calculating Encoding and Decoding Functions for Prefix Codes 54
Cristobal Pareja-Flores and J. Angel Velazquez-lturbide
Reverse Execution of Programs 61
Bitan Biswas and R. Mali
A Novel Program Representation for Interprocedural Analysis 70
Gagan Agrawal, Shyamala Murthy, and Chandrashekhar Ganid