Previous approaches for adding object-oriented facilities to functional languages like ML have typically introduced new object-oriented constructs distinct from the existing functional constructs, causing programmers to choose between alternative programming styles and yielding a more complicated and less expressive language. We have developed an object-oriented extension of ML that directly generalizes the abilities of existing ML constructs to support a flexible form of object-oriented programming without adding new, distinct features. In particular, we extend ML's datatype and fun declarations to allow hierarchical extension across modules, allowing the programming of traditional object-oriented class hierarchies and methods, but also multiply dispatched methods and methods that dispatch (through pattern-matching) on subcomponents of arguments. Classes and functions can be typechecked and compiled modularly, even in the face of unseen extensions. Our integrated approach allows existing hierarchies to be extended with both new operations and new representations, independently, modularly, and safely, resolving a long-standing conflict between functional and object-oriented programming styles.
Java programs are routinely transmitted over low-bandwidth network connections as compressed class file archives (i.e., zip files and jar files). Since archive size is directly proportional to download time, it is desirable for applications to be as small as possible. This work is concerned with the use of program transformations such as removal of dead methods and fields, inlining of method calls, and simplification of the class hierarchy for reducing application size. Such ``extraction'' techniques are generally believed to be especially useful for applications that use class libraries, since typically only a small fraction of a library's functionality is used. By ``pruning away'' unused library functionality, application size can be reduced dramatically. We implemented a number of application extraction techniques in JAX, an application extractor for Java, and evaluate their effectiveness on a set of realistic benchmarks ranging from 27 to 2,332 classes (with archives ranging from 56,796 to 3,810,120 bytes). We report archive size reductions ranging from 13.4% to 90.2% (48.7% on average).
Joint work with Chris Laffra, Peter Sweeney, and David Streeter.
Global register allocation for architectures such as the Intel x86 is a difficult problem because of the limited number of available registers. A standard Chaitin-style graph coloring allocator can misbehave because most live-ranges have to be spilled. If no considerations are made to the locations of spilled memory, inefficient programs can result. This already difficult resource allocation problem is further complicated in the Standard ML of New Jersey compiler: the translation of the CPS intermediate code into machine code can introduce many copies, which must be effectively eliminated to obtain efficient code.
In this work we describe a scheme that address these problems. Our scheme combines the allocation of registers and spill locations, and is an extension of previous work on compiler controlled memory (CMM). First, like CMM, we extend the conceptual model of the register file with a small set of pseudo memory reigisters, which can be used for holding spilled variables, temporaries and procedure parameters. Secondly, in order to reduce memory accesses and effectively targets these pseudo memory registers, we extend the standard iterated coalescing algorithm with an iterated spill coalescing and propagation phase, which is responsible for coalescing and allocation of spill locations. Spill coalescing combines spilled live-ranges to remove unnecessary memory-to-memory moves, while spill propagation, which undos the harmful effect of overly aggressive register promotion, evicts colorable live-ranges to memory when doing so actually reduces execution cost. We follow this with a spill coloring phase, which compacts the spilled live-ranges to fit a small stack frame.
Joint work with Lal George.
In this talk we describe a language of mobile agents called uPLAN for describing the capabilities of active (programmable) networks. We use a formal semantics for uPLAN to demonstrate how various capabilites provided for programming the network can affect the potential flows of information between users. In particular, we formalize a concept of security against attacks on secrecy by an `outsider' and show how basic protections of this kind are preserved in the presence of programmable network functions like user-customized labeled routing.
Clearly, a world where data is exchanged as labelled trees offers exciting possibilities for computer scientists to contribute technology already proven in academia. XML, recently featured in TV commercials, is a chance for trees to root themselves in practice. An XML document is, kind-of, a representation of a labeled tree. It would be fair to say that the W3C is struggling with the task of coming up with a universal standard for defining XML languages, that is, sets of labelled trees.
I'll present the DSD notation, which is an alternative based on familiar concepts: nonterminals, Boolean logic, and regular expressions. We've mixed these ingredients with a spice of CSS (Cascading Style Sheets) to arrive at a language that