% -*- Mode: LaTeX -*-

\section{Introduction}

Polymorphic programming languages provide the flexibility of code
reuse by allowing objects with different types to share the same
pattern of computation. A simple example is the polymorphic {\tt
length} function that counts the number of elements in a list of any
type. But this feature creates problems for applications like garbage
collection and source debugging that need to know the exact type of
every object participating in a computation at run-time. 

Traditionally, programming environments of dynamically-typed languages
such as Lisp maintain this type information in the form of run-time
tag descriptors on each object. Such implementations pay the price of
universal tag management either in complex specialized hardware or in extra
memory space and time for managing the tags in software \cite{Appel89}.

Recently, several type reconstruction schemes have been proposed for
statically-typed polymorphic languages like ML \cite{SML90} that do
not incur the run-time tag management overhead
\cite{Appel89,Goldberg91,Goldberg92}.  In these schemes, static type
information is combined with clues from the dynamic state of the
machine (the call stack) in order to reconstruct the exact types of
run-time objects when required.  Unfortunately, these schemes are not
able to reconstruct complete type information for all run-time objects
in the presence of higher-order functions \cite{Goldberg92}. Types of
objects hidden inside the environment part of a closure are sometimes
not reconstructible because the computation that produced the closure
may have terminated and no run-time clue is available.

In this paper, we propose a general scheme for reconstructing the full
run-time types of all objects without using universal type-tags while
incurring a small run-time overhead controlled explicitly by the
compiler. Our scheme can be viewed as a compiler-directed explicit
tagging of objects, though the extra tag information is generated only
where necessary and propagated explicitly at run-time in order to
reduce overhead. We present our scheme in the context of a source
debugger \cite{Caro93} for the Id programming language \cite{Id90.1}
which is a parallel, non-strict, polymorphic language with a
Hindley/Milner type system \cite{Damas82,Milner78}. The main thrust of
the paper is to show that explicit tagging needs to be done in very
few cases that plug the informational holes in the previous schemes
and that it can be set up by the compiler automatically with minimal
run-time overhead and support.

The outline of the paper is as follows.  First, in
Section~\ref{problem} we describe the problem of type reconstruction
in more detail showing examples where complete reconstruction is not
possible without some run-time book-keeping. In
Section~\ref{framework}, we set up the reconstruction problem in a
theoretical framework and characterize the minimum information that
needs to be propagated at run-time to allow complete type
reconstruction.  Then, we present our compilation scheme for
propagating this information in Section~\ref{compile} and the type
reconstruction algorithm used by the Id debugger in
Section~\ref{reconstruct}. In Section~\ref{optimize}, we show a series
of compiler optimizations and variations on our compilation scheme
that may further reduce the book-keeping overhead of the current
scheme.  Finally, Section~\ref{conclude} presents conclusions and
directions for future work.

