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