A Chaitin-style register allocator often blocks during its simplification phase because no node in the interference graph has a degree that is sufficiently small. Typically, this is handled by node-splitting, or by optimistically continuing---and hoping that a legal N-coloring will still be found. We observe that the merging of two nodes in a graph causes a reduction in the degree of any node that had been adjacent to both. We have enhanced Chaitin's coloring algorithm so that it attempts node-merging during graph simplification; this often allows simplification to continue, while still guaranteeing a coloring for the graph. We have tested this algorithm using Appel's database of register-coloring graphs, and have compared it with Chaitin's algorithm. The merge-enhanced algorithm yields a better coloring about 8% of the time, and a worse coloring less than 0.1% of the time.

We are implementing a Scheme development system for the Motorola 88000. The core of the implementation is an optimizing native code compiler, together with a carefully designed runtime system. This paper describes our experiences with the 88000 as a target architecture. We focus on the design decisions concerning the runtime system, particularly with respect to data type representations, tag checking, procedure calling protocol, generic arithmetic, and the handling of continuations. We also discuss rejected design alternatives, and evaluate the strengths and weaknesses of the instruction set with respect to our constraints.

There are a number of reasons why a user might want to move data structures between Smalltalk images. Unfortunately, the facilities for doing this in the standard Smalltalk image are inadequate: they do not handle circular structures properly, for example. We have implemented a collection of Smalltalk methods that handles circular structures; in addition, these methods have a number of other advantages over those provided in the standard image. This paper is largely a discussion of the issues that arose during their design, implementation, and use.

Functional and imperative programming languages are characterized and compared with regard to programming style and efficiency. Machine design issues, are characterized by interconnection topology, evaluation strategy, program and data representation, process management, and dynamic optimization techniques; short descriptions of a number of "functional" machines are given in terms of these issues. Multiprocessor issues and systems are particularly emphasized. Outstanding problems in the area are reviewed and an overall evaluation of proposed machines is given.

StarOS is a message-based, object-oriented, multiprocessor operating system, specifically designed to support task forces, large collections of concurrently executing processes that cooperate to accomplish a single purpose. StarOS has been implemented at Carnegie-Mellon University for the 50 processor Cm* multi-microprocessor computer.