% -*- Mode: LaTeX -*-

\begin{abstract}

In tagless implementations of polymorphic languages, the
run-time types of data objects may not be completely determined at
compile-time.  With ML-like static type-checking, a static type
template can be produced for each polymorphic function that may be
instantiated at run-time according to the types of its actual
arguments. Still, as noted in \cite{Goldberg92}, it may not be
possible to reconstruct the types of some objects that are hidden
inside a closure. This creates problems for applications like garbage
collection and source debugging that need to understand the entire
run-time state of the machine.

In this paper, we present a compiler-directed type reconstruction
scheme for ML-like languages that reconstructs complete type
information of all objects at run-time without using universal
type-tags.  Our scheme explicitly propagates compiler generated hints
at run-time whenever there is a danger of losing the type information
otherwise. We show a compilation strategy to automatically detect,
generate and propagate such hints and a type reconstruction algorithm
that uses them in the context of a source debugger \cite{Caro93} for
the Id language \cite{Id90.1}. We also show several compiler
optimizations that reduce the run-time overhead of propagating these
hints.

\end{abstract}


