NJPLS at Princeton -- 7 December 2001 -- Schedule

10:00am: No-Longer-Foreign: Teaching an ML compiler to speak C ``natively''

Matthias Blume (Bell Labs)

I present a new foreign-function interface for SML/NJ. It is based on the idea of data- level interoperability--the ability of ML programs to inspect as well as manipulate C data structures directly. The core component of this work is an encoding of the complete C type system in ML types. It makes use of a certain ``folklore'' typing trick, taking advantage of the considerable expressive power of ML.

A small low-level component which deals with ``new'' C types (struct or union declarations) as well as program linkage is hidden from the programmer's eye by a simple program-generator tool that translates C declarations to corresponding ML glue code.

10:45am: Adaptive Optimization in the Jikes RVM

Michael Hind (IBM Watson Research Center)

This talk will present an overview of the Jikes Research Virtual Machine (RVM), an open source VM for Java formerly called Jalapeno. In addition to highlighting the various components of Jikes RVM, the presentation will focus on results from the adaptive optimization system and highlight some work in progress.

Further information on the Jikes RVM is available at http://www.ibm.com/developerworks/oss/jikesrvm

11:30am: Lunch

12:45pm: Business meeting

1:00pm: Program Optimization Using Indexed and Recursive Data Structures

Annie Liu (State University of New York at Stony Brook) (POSTPONED to next meeting)

This talk describes a systematic method for optimizing recursive functions using both indexed and recursive data structures. The method is based on two critical ideas: first, determining a minimal input increment operation so as to compute a function on repeatedly incremented input; second, determining appropriate additional values to maintain in appropriate data structures, based on what values are needed in computation on an incremented input and how these values can be established and accessed. Once these two are determined, the method extends the original program to return the additional values, derives an incremental version of the extended program, and forms an optimized program that repeatedly calls the incremental program. The method can derive all dynamic programming algorithms found in standard algorithm textbooks. There are many previous methods for deriving efficient algorithms, but none is as simple, general, and systematic as ours. This is joint work with Scott Stoller. A paper describing this work is to appear in PEPM'02.

1:45pm: A New Automaton for Pattern Matching

Jonathan Eddy (Harvard University)

Pattern matching in languages such as ML is a construct for branching to an expression based on the first pattern from a list that matches the subject tree. A naive automaton that performs this matching might check each pattern in sequence until it finds one that matches. Such an automaton is linear in size with respect to the number of patterns, but is inefficient because it examines nodes in the subject tree more than once. By compiling the pattern match to a decision tree, we examine each node in the subject tree at most once. The size of this decision tree, however, might grow exponentially with the size of the pattern match. Converting the decision tree to a DAG will save only a little space, because it can merge only identical subtrees. Inspired by the continuation-passing style transform, we convert the decision tree to a form where the nodes are functions and the children are parameters. By sharing these functions, we cut the space cost. The new recognizer performs exactly the same steps as the decision tree, but the cost of each step may differ.

2:30pm: Break

3:00pm: How to Synchronize a List

Benjamin Pierce (University of Pennsylvania)

Increased mobility -- of programs between computers, computers between locations, and computers between users -- leads to increased --> -- replication, which leads to inconsistency, which leads to a broad (and growing) range of synchronization technologies. These technologies are not only a fact of life; they are intellectually fascinating and raise a host of challenging questions. I've spent a good part of the last few years on building and specifying a very specific and particular sort of synchronizer -- a file --> -- synchronizer called Unison. More recently, I've been trying to generalize intuitions from this domain to richer domains such as XML synchronization. I'll describe some initial steps in this direction.

3:45pm: Aliasing Analysis using CLA: A Million Lines of C Code in a Second

Nevin Heintze (Research, Agere Systems)

I will describe the design and implementation of a system for very fast points-to analysis. On code bases of about a million lines of unpreprocessed C code, our system performs field-based Andersen-style points-to analysis in less than a second and uses less than 10MB of memory. Our two main contributions are a database-centric analysis architecture called compile-link-analyze (CLA), and a new algorithm for implementing dynamic transitive closure. Our points-to analysis system is built into a forward data-dependence analysis tool that is deployed within Lucent to help with consistent type modifications to large legacy C code bases.

4:45pm: Meeting ends

Last modified: Tue Oct 23 15:34:07 EDT 2001