% -*- Mode: LaTeX -*-
\begin{abstract}

%Dynamic storage management is an integral component of modern
%programming languages.  Storage in such languages may be reclaimed
%{\em explicitly\/}, using deallocation commands, or {\em
%implicitly\/}, using run-time or compile-time garbage collection.
%Because explicit storage management is such a difficult problem, we
%concentrate on garbage collection.

Garbage collectors perform two functions: {\em live-object
detection\/} and {\em dead-object reclamation\/}.  In this paper, we
present a new technique for live-object detection based on run-time
type reconstruction for a strongly-typed, polymorphic language. This
scheme uses compile-time type information together with the run-time
tree of activation frames to determine the exact type of every object
participating in the computation. These reconstructed types are then
used to identify and traverse the live heap objects during garbage
collection.

We describe an implementation of our scheme for the Id parallel
programming language compiled for the *T multiprocessor architecture.
We present simulation studies that compare the performance of
type-reconstructing garbage collection with conservative garbage
collection and compiler-directed storage reclamation.

\end{abstract}
