The metavariable self is fundamental in object-oriented languages. Typing self in the presence of inheritance has been studied by Abadi and Cardelli, Bruce, and others. A key concept in these developments is the notion of selftype, which enables flexible type annotations that are impossible with recursive types and subtyping. Bruce et al. demonstrated that, for the language TOOPLE, type checking is decidable. Open until now has been the problem of type inference with selftype.
We present a type inference algorithm for a type system with selftype, recursive types, and subtyping. The example language is the object calculus of Abadi and Cardelli, and the type inference algorithm runs in nondeterministic polynomial time.
Higher-order functors were first added to SML/NJ in version 0.93. This implementation evolved from the earlier first-order module implementation, but this evolution was not very graceful. In 1993-94 Mads Tofte and I defined an operational semantics for higher-order functors, and this spring I decided to replace the implementation of the module system with a new design derived explicitly from the operational semantics. In this talk I will describe the semantics and the implementation derived from it. The key points are factoring of the static representations of modules into stable and volatile parts, and the use of a simple lambda-calculus language to compute the volatile information. I'll try to abstract some general lessons for module system design from the exercise.
An important function of any register allocator is to target registers so as to eliminate copy instructions. Graph-coloring register allocation is an elegant approach to this problem. If the source and destination of a move instruction do not interfere, then their nodes can be coalesced in the interference graph. Chaitin's coalescing heuristic could make a graph uncolorable without spilling; Briggs demonstrated a conservative coalescing heuristic that preserves colorability. But Briggs' algorithm is too conservative, and leaves too many move instructions in our programs. We show how to interleave coloring reductions with Briggs's coalescing heuristic, leading to an algorithm that is safe but much more aggressive.