Tag-free garbage collection for strongly typed programming languages

With the emergence of a number of strongly typed languages with very dynamic storage allocation, efficient methods of storage reclamation have become especially important. Even though no type tags are required for type checking programs written in these languages, current implementations do use tags to support run time garbage collection. This often inflicts a high time and space overhead on program execution. Since the early days of LISP (and Algol68 later on), there have been schemes for performing tag-free garbage collection. In this paper, we describe an improvement of existing methods that leads to more effective storage reclamation in the absence of tags. Garbage collection has also traditionally been viewed as being independent of the particular program being executed. This means that results of compile-time analyses which could increase the effectiveness of garbage collection cannot be incorporated easily into the garbage collection process. This paper describes a method for performing garbage collection 1) in the absence of tagged data, and 2) using compile-time information. This method relies on compiler-generated garbage collection routines specific to the program being executed and incurs no time overhead during execution other then the cost of the garbage collection process itself. We describe tag-free garbage collection methods for monomorphically typed and polymorphically typed languages, and suggest how they might be extended to support parallel languages.