# Tag-free garbage collection for object oriented languages

I'm looking around for a good garbage collection technique for my language and found this paper, where Benjamin Goldberg describes a garbage collection technique for strongly typed languages, which removes the need for type information during runtime.

Briefly, this is done by placing a pointer to a garbage collection function right after a function call, directly in the compiled code. They then extend this to support ML-like parametric polymorphism.

Now my question: Has there been any work on how this technique could be implemented in an object oriented language, where much functionality is implemented through indirect calls using pointers in a virtual table?

• What do you see as being a problem? What matters is that each entity knows its own storage identity. – babou Jul 9 '14 at 0:03
• Yes, but in my scenario it's not known at compile-time which function is called, and thus the gc_routine (terminology from the paper) to call during garbage collection is not known at compile-time. I'm looking for a solution to this problem, without resorting to an interpreted GC method. – MathiasVP Jul 9 '14 at 10:41
• I tried to answer your question, as made more precise in the comment, but I am wondering if that is really the problem you have in mind. Comments are welcome. – babou Jul 9 '14 at 21:34
• it sounds like you simply need runtime indirection in the gc system that matches the function indirection. note there are many garbage collection schemes, its just a matter of finding one that matches your language design.... – vzn Jul 12 '14 at 17:56

Like Häagen-Dazs ice-cream, Object Orientation comes in many flavor, though with more nuts and bananas. Hence it is hazardous to answer your question stated in very general terms. Specific OO languages could have unexpected features that might raise problems with virtual methods. I fear that trying to imagine what kind of features could make things go wrong is a bit of a fruitless exercise. It is better to try answering precise questions.

The basic principle of tag-free GC is that, at any time, you should be able to inspect the memory starting from the stack, and know the actual type of all chunks of live allocated memory (because that is precisely what the GC will need to work). This implies also to know, at each call point of a function/method, the current state of activation block of the caller, whether on the stack or on the heap, i.e. the current variables of the block and their state of initialisation. The necessary structural information can be stored as data descriptors to be interpreted, or as executable gc-routines for better GC efficiency. The important point of tag-free GC is that this information can be determined statically, in order to be stored once with the code rather than with each instance of a type or class or of function activation. When this information can change dynamically, as is the case with polymorphic types, it must be possible to compute it by tracing and compounding static type information through the dynamic call sequence.

The fact that a method is virtual and called through a virtual table is not in itself a problem. A caller does not need to know what it is calling as it has no importance regarding GC for its own activation record. The callee is supposed to know itself (the compiler sees to it), and carry whatever information it need. The information may be incomplete as in the case of polymorphism, and must be completed from other type information available in the call sequence. Actually, in a language like ML, where functions can be passed as parameters, or put in tuples, the caller may not know what function it is actually calling.

What matters is that the caller knows where in its code it calls the callee, so as to determine the state of its activation block during the call. This is statically dependent on the call point, and can thus be inferred from the callee return address,(in various ways depending on technical variations used by different authors). The corresponding gc-routine can thus be found in some way from that return address. For example, it can be in the code right after the call, but other equivalent techniques could be considered. So if the callee is interupted by GC, it will be possible to do the GC for the callers activation record. The caller does no GC work for the callee, only for its own activation record.

What may be a problem is making sure that the callee does know the actual type of all the values that are passed to it (as in polymorphism). More precisely, it must be possible to find that information when the GC occurs and must deal with the activation record of the actual method that is access through a virtual.

I believe that being more precise on this last issue is dependent on the actual features and classe/objects structures of the OO language, on its typing organization.

But, as the caller does not need to know the callee, I do not see that indirect calls can be a problem.

Another point (answering the OP's comment) is that the issue here is not whether GC is performed from compiled code or interpreted from descriptors, but whether it needs dynamic tag for type information.

Suggestion: to find more work on this, take your favorite search engines (and other web resources) and look for papers citing the Goldberg papers or its mains references. Apply the procedure recursively, adding occasional keywords such as object oriented or virtual.