Keynote: Is Code Optimization Research Relevant?
Bill Pugh
University of Maryland
Many papers are published on compiler optimizations that improve the performance of some set of benchmark programs. But I believe that much of this research has had little impact on the ability of developers to quickly produce reliable and efficient software. Unfortunately, research that does address these problems is often hard to publish. I will talk about this problem, and possible directions to try to improve the situation.
Toward Effective Component Verification: Deriving an Efficient Program Analysis from a High-level Specification
John Field
IBM T.J. Watson Research Center
The Canvas project at IBM Research and Tel-Aviv University aims to help ease the use of software components by allowing the component designer to specify component _conformance_ constraints in a natural way, and providing the client code developer with automated software _certification_ tools to determine whether the client satisfies the component's conformance constraints.
In this talk, we describe some initial steps toward this goal by showing how to systematically _derive_ efficient and precise certification algorithms from a formal specification of the Concurrent Modification Problem (CMP), which can arise from misuse of iterators in the Java 2 Collection Classes. One of the algorithms we describe runs in polynomial time for a large class of Java applications. One interesting aspect of CMP is that it expresses an interrelationship between a ``temporal'' property (the order in which certain methods are called), and ``spacial'' properties (the relationship between a collection object and iterator objects defined on it). Many program verification systems or analysis techniques have been specialized for one of those two domains, but CMP requires that both types of properties be verified in an integrated way.
We report preliminary benchmarking results for a prototype implementation of our efficient certification algorithm (HCMP), along with results for a more conventional algorithm (VCMP). The results show that HCMP is not only more precise than VCMP, it is also more efficient in practice.
Joint work with G. Ramalingam, IBM T.J. Watson Research Center, and Alex Warshavsky and Mooly Sagiv, Tel-Aviv University.
Efficient Object Sampling via Weak References
Alexander Garthwaite
Sun Labs
The performance of automatic memory management may be improved if the policies used in allocating and collecting objects had knowledge of the lifetimes of objects. To date, approaches to the pretenuring of objects in older generations have relied on profile-driven feedback gathered from trace runs. This feedback has been used to specialize allocation sites in a program. These approaches suffer from a number of limitations. We propose an alternative that through efficient sampling of objects allows for on-line adaption of allocation sites to improve the efficiency of the memory system. In doing so, we make use of a facility already present in many collectors such as those found in Java(tm) virtual machines: weak references. By judiciously tracking a subset of allocated objects with weak references, we are able to gather the necessary statistics to make better object-placement decisions.
Tangible Computation Bricks: Building-blocks for Physical Microworlds
Tim McNerney
MIT Media Lab
Learning activities that involve computation do not necessarily need to involve a computer. The approach presented in this talk avoids user interfaces which need a screen, keyboard, and pointing device, offering instead physical building-blocks augmented with embedded microprocessors. Using these techniques offers computational learning experiences without the cognitive overhead required by many computer-based learning tools. This talk introduces a general-purpose, constructive tangible user interface device, the Tangible Computation Brick. It describes several tangible programming languages that can be implemented with a handful of Bricks and applied in a variety of domains. The talk focuses on one language that was designed for scientific exploration, and discusses informal observations on test subjects. This system is easy to teach to novices, and it is successful at allowing students to focus on the learning task at-hand instead of being distracted by the user interface.
Ferret: Programming Language Support for Multiple Dynamic Classification
Bard Bloom
IBM T.J. Watson Research Center
We introduce a concept of multiple dynamic classification, a powerful generalization of single-inheritance OO, and a language Ferret which implements it. Multiple classification allows Male, Female, and Married to be subclasses of Person, arranged so that a single Person object may be both Male and Married, but may not be both Male and Female. Dynamic classification allows classes to change: a Person may acquire or lose Married status.
The subclasses are true subclasses. Married carries fields (e.g., spouse) which are specific to married people. Methods may be defined on classes, and even on Boolean combinations of class: Male & Married. Ferret provides a generalization of superclass calls, so that the methods for Male & Married can be based on those for Male and Married, without losing other classifications like Employee. Ferret has mutators, analogous to constructors but applicable when objects change class. The resulting language is powerful and highly expressive.
Type-Based Hot Swapping of Running Modules
Dominic Duggan
Stevens Institute of Technology, Hoboken NJ
While dynamic linking has become an integral part of the run-time execution of modern programming languages, there is increasing recognition of the need for support for replacing running libraries, particularly in long-lived server applications. The interesting challenge for such a facility is to allow the new library to change the types exported by the original library, while preserving type safety. An example is upgrading IPv4 routers to handle IPv6. I will discuss an approach I have been developing to solve this general problem, in the context of type systems for module languages. I will discuss problems with other approachs that have been proposed (and sometimes implemented), and explain how this approach avoids those problems. If there is time, I will relate this approach to the broader context of module languages. In particular, although some of the type-theoretic concepts originate from the SML90 module language, this approach to hot swapping is more readily applicable to object-oriented languages such as Java and C#.