## July 20 '95 Seminar Minutes

### Attendance

About 20 people attended the seminar.
### 10:00am Jens Palsberg,
Type Inference with Selftype

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.

### 11:30am Dave MacQueen,
A second try at implementing higher-order functors

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.

### 2:00 pm Lal George,
Iterated register coalescing

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.