In the general framework of automatic garbage collection, this paper considers the specific case of strongly typed languages. The problem is much more complex when no typing information is stored in objects themselves at runtime. Omitting this information saves the cost of storing and maintaining it for all objects, but it makes it impossible to use the only well-known techniques for conventional dynamically typed programming languages.
The idea developed in the paper is to reconstruct the typing information at runtime, when garbage collection becomes necessary. An image of compile-time type information must exist at runtime, and it is used together with the runtime tree of activation frames. Since reconstruction is needed only just before garbage collection, one can assume better storage and time performances than when complete type information is handled for all objects.
The paper describes the scheme for type reconstruction and its implementation for a peculiar situation, namely an experimental parallel programming language for an experimental multiprocessor architecture. It is not clear whether this peculiar case adds anything specific to the problem considered.
The process of garbage collection is divided into the phases of live-object detection and dead-object reclamation. Only the first phase is considered, and more specifically its object identification subphase. The performance of type-reconstructed garbage collection is compared, using several benchmarks, to those of conservative garbage collection, which does not use type information, and of compiler-directed storage reclamation, which does not use garbage collection. The conclusions one can draw from this comparison are not striking.
It would be interesting to study the application of the ideas developed in this paper to more conventional programming languages.