Type constraints express subtype relationships between the types of program expressions, for example, those relationships that are required for type correctness. Type constraints were originally proposed as a convenient framework for solving type checking and type inference problems. This paper shows how type constraints can be used as the basis for practical refactoring tools. In our approach, a set of type constraints is derived from a type-correct program P . The main insight behind our work is the fact that P constitutes just one solution to this constraint system, and that alternative solutions may exist that correspond to refactored versions of P . We show how a number of refactorings for manipulating types and class hierarchies can be expressed naturally using type constraints. Several refactorings in the standard distribution of Eclipse are based on our work.

Full-featured integrated development environments have become critical to the adoption of new programming languages. Key to the success of these IDEs is the provision of services tailored to the languages. However, modern IDEs are large and complex, and the cost of constructing one from scratch can be prohibitive. Generators that work from language specifications reduce costs but produce environments that do not fully reflect distinctive language characteristics.

In this poster, we present our vision of refactoring support for languages with a partitioned global address space memory model as embodied in the X10 programming language. We examine a novel refactoring, extract concurrent, that introduces additional concurrency within a loop by arranging for some user-selected code in the loop body to run in parallel with other iterations of the loop. We discuss the mechanisms and challenges for implementing this refactoring and how development of this refactoring provides insight for designing future refactorings.

Type safety and expressiveness of many existing Java libraries and their client applications would improve, if the libraries were upgraded to define generic classes. Efficient and accurate tools exist to assist client applications to use generic libraries, but so far the libraries themselves must be parameterized manually, which is a tedious, time-consuming, and error-prone task. We present a type- constraint-based algorithm for converting non-generic libraries to add type parameters. The algorithm handles the full Java language and preserves backward compatibility, thus making it safe for existing clients. Among other features, it is capable of inferring wildcard types and introducing type parameters for mutually-dependent classes. We have implemented the algorithm as a fully automatic refactoring in Eclipse. We evaluated our work in two ways. First, our tool parameterized code that was lacking type parameters. We contacted the developers of several of these applications, and in all cases they confirmed that the resulting parameterizations were correct and useful. Second, to better quantify its effectiveness, our tool parameterized classes from already-generic libraries, and we compared the results to those that were created by the libraries' authors. Our tool performed the refactoring accurately-in 87% of cases the results were as good as those created manually by a human expert, in 9% of cases the tool results were better, and in 4% of cases the tool results were worse.

Programming language design remains a vital field, with interest in languages targeting concurrency, scripting, and aspects, as well as in domain-specific languages. Full-featured integrated development environments (IDEs) have become critical to the adoption of new languages. A key factor in the success of these IDEs is the provision of services specifically tailored to the language. However, modern IDE frameworks are large and complex, and the cost of constructing a language-specific IDE from scratch remains prohibitive

As object-oriented class libraries evolve, classes are occasionally deprecated in favor of others with roughly the same functionality. In Java's standard libraries, for example, class Hashtable has been superseded by HashMap, and Iterator is now preferred over Enumeration. Migrating client applications to use the new idioms is often desirable, but making the required changes to declarations and allocation sites can be quite labor-intensive. Moreover, migration becomes complicated---and sometimes impossible---if an application interacts with external components, if a legacy class is not completely equivalent to its replacement, or if multiple interdependent classes must be migrated simultaneously. We present an approach in which mappings between legacy classes and their replacements are specified by the programmer. Then, an analysis based on type constraints determines where declarations and allocation sites can be updated. The method was implemented in Eclipse, and evaluated on a number of Java applications. On average, our tool could migrate more than 90% of the references to legacy classes.

We describe QSketcher, a new environment for composing music for film. The main focus is the support of early stages of the creative workflow, from conception through realization, rather than the order and synchronization of musical fragments with film. This paper describes the design process and rationale, the system, the user environment, and how they relate to one another. Novel aspects of the system include a free-form 'idea space', a main workspace that can be configured to individual needs, an idea capturing facility, a workflow tracking mechanism through which previous workspace states can be examined and restored, and the ability to create a variety of relationships among musical elements.

The optimal state minimization problem is to select a reduced state machine having the best logic implementation over all possible state reductions and encodings. The OPTIMIST (OPTImal MInimization of STates) algorithm (R.M. Fuhrer et al., 1997) was the first general solution to this problem for synchronous finite state machines (FSMs). In this paper, we present the first solution for asynchronous FSMs. This paper makes two contributions. First, we introduce OPTIMISTA (OPTIMIST-Asynchronous), a new algorithm which guarantees optimum 2-level output logic for asynchronous FSMs. In asynchronous machines, output logic is often critical: it usually determines the machine latency. The algorithm is formulated as a binate constraint satisfaction problem, which is solved using a binate solver. The second contribution is a novel alternative result: the unreduced machine itself can be used directly to obtain minimum-cardinality output logic. Thus, this paper presents two approaches: using OPTIMISTA, which simultaneously performs state and logic minimization; or using no state reduction (if output logic cardinality is of sole interest). Extensions for literal optimization, targetted to multi-level logic, are also proposed.

We present a novel method for state minimization of incompletely-specified finite state machines. Where classic methods simply minimize the number of states, ours directly addresses the implementation's logic complexity, and produces an exactly optimal implementation under input encoding. The method incorporates optimal "state mapping", i.e., the process of reducing the symbolic next-state relation which results from state splitting to an optimal conforming symbolic function. Further, it offers a number of convenient sites for applying heuristics to reduce time and space complexity, and is amenable to implementation based on implicit representations. Although our method currently makes use of an input encoding model, we believe it can be extended smoothly to encompass output encoding as well.

This paper presents an automated method for the synthesis of multiple-input-change (MIC) asynchronous state machines. Asynchronous state machine design is subtle since, unlike synchronous synthesis, logic must be implemented without hazards, and state codes must be chosen carefully to avoid critical races. We formulate and solve an optimal hazard-free and critical race-free encoding problem for a class of MIC asynchronous state machines called burst-mode. Analogous to a paradigm successfully used for the optimal encoding of synchronous machines, the problem is formulated as an input encoding problem. Implementations are targeted to sum-of-product realizations. We believe this is the first general method for the optimal encoding of hazard-free MIC asynchronous state machines under a generalized fundamental mode of operation. Results indicate that improved solutions are produced, ranging up to 17% improvement.