Lambda the Ultimate

You don't give many hints as to what you have found. For example,
is Tolmach's 1994 Tag-free Garbage Collection Using Explicit Type Parameters a useful way into the subject? It seems fairly well cited.

(Disclaimer: this dropped out of Google into my lap; I'm not familiar with this corner of the literature, though it seems interesting.)

There are three strategies that I can think of:

1) Compile the polymorphism away by duplicating code.

2) Use runtime type tags.

3) Pass the a representation of the type of the type variable at run time.

Stack maps can be used only when the stack layout is fixed, which isn't the case when combining unboxed types and polymorphism.

You need something like a bitmask-passing representation. See the post I linked to, and the previous entry linked from it. They explain various representations.

has some papers on the implementation of generics in .NET, which supports unboxed data.

"Representation passing" seems promising. So far, I believe the big challenge is to distinguish pointers from non-pointers on the stack.

A single extra word parameter to polymorphic functions can describe the traceability status of up to 32 type variables, which I presume (so far) the GC root scanner can use together with return-address-indexed stack maps for precise determination of pointer roots on the stack.

Again just so far, I posit heap objects that either 1) are 2-slot header-less values that live in heaps specialized according to slot pointer status (e.g., 4 special 2-slot heap types), or 2) live in "general purpose" heaps of variable sized values but which enjoy a header which describes the trace status of the heap value's slots, a header which will have to be similarly (?) specialized when the heap value has polymorphic slots.

Pointers are 2-machine word aligned, which gives some extra flexibility for storing pointers and immediates in the same location, say for convenient representation of algebraic data type values (e.g., Nil and Cons(car,cdr) - and so forth). So any indication of "pointer" is really just an indication of "potentially pointer" to the GC.

I suppose naturally, I'm concerned about reducing runtime overhead - extra function parameters, heap value words, construction of slot-describing bit-masks and so on - and what might possibly be accomplished more efficiently at compile time vs. runtime, or via caching the most common cases and so on. (An invariant for me is separate compilation and a "regular" system-provided linker.)

And, of course, I'm concerned that some fatal flaw in my reasoning so far will make the whole thing fall apart :-)

Many thanks for the pointers to info and articles so far. If the above sparks recall of any other papers or interesting systems (i.e., source code), I gladly appreciate anything one might toss my way.

S.

edit - I may also reorder pointer and non-pointer values in 2-slot objects, yielding just 3 special 2-slot heap types: PP, PI and II. The goal here is to have either 1) a forwarding pointer into to-space in the first slot of each special 2-word value or 2) a special-case per-heap bit-mask for the no-pointers (II) 2-slot heap type which will indicate the prior per-object copying into to-space of each value in the heap.

Upon waking, I conclude that reading the sources of a real-language implementation of precise GC for a language supporting parametric polymorphism might be the right way to go.

From experience, the smallest language implementation that enjoys this particular feature would be most suitable.

Large projects, with myriad research goals and so many folks banging on them, are often full of TONS of (important, of course) cruft added for research purposes, corner case optimizations, implementation portability and so on - all things that can greatly obscure understanding of the core RTS implementing - in this case - precise GC with parametric polymorphism.

If folks know of small'ish (or not, I guess) open source language implementations that feature such a precise GC scheme, I would greatly appreciate a pointer to the language and its implementation source code.

Thanks!

S.

Can one profitably combine "traditional" stack activation frame maps with a bit mask parameter for any polymorphic parameters? The stack map itself can indicate to the GC stack scanner whether or not a bitmask parameter for polymorphic arguments is present in the activation frame.

Also, I wonder if unboxed doubles passed as a polymorphic argument might just be handled by 2 bits in the bitmask parameter indicating two non-pointer word values? (Well, even if this might allow precise GC, it doesn't account for actual proper code execution within the function, and doesn't allow for passing doubles on the FPU stack in Intel chips.)

I'm greatly interested in natural word representation in order to facilitate fairly seamless integration with C functions calling into the OS and into libraries, ala a more straightforward "FFI".

I do wonder about the impact of stack maps on locality of reference and hence speed of GC, so any thoughts there would be of interest there as well.

As always, all and any input greatly appreciated.

- Scott

.NET, with its runtime specialization, seems like a poor model for me, as separate compilation (including to .so files) is a hard language implementation prerequisite.

This also seems like overkill for just achieving precise stack scanning during GC. And this will require stack maps for the GC scanner even if somehow polymorphic functions and structures are compiled to monomorphic equivalents.

That I can live with, although I seek detailed guidance on stack map design, sharing/compression, return address lookup schemes, etc.

Might it be profitable to treat polymorphic function in a manner akin to C++ templates (compile time specialization), but _only_ specializing based upon the word status (pointer or non-traceable word) and possibly argument sizes greater than a word (e.g., doubles, complex numbers and other such common place candidates for stack passing value arguments) of any polymorphic arguments, associated local and return variables, etc. ???

Then bitmask/representation passing would become unnecessary and regular monomorphic-language style stack maps would suffice for precise GC stack scanning with untagged integer/word (and maybe larger) values for polymorphic arguments/variables.

Am I on the right track here or barking up the wrong tree. I worry about some nuance conflicting with the requirement for separate compilation and, I should have mentioned earlier, the use of a standard system provided "stupid" linker.

Again, any and all advice greatly appreciated !!!

- Scott

It sounds to me like you are asking for the basics - how precise garbage collection can be done at all in the presence of parametric polymorphism.

The usual solution is to implement polymorphism so values of an unknown type are only manipulated by reference (Java, etc), and generating specialized code for each possible type if it appears otherwise (C++ templates). Then the problem is reduced so pointers are in known locations, but you may not know the exact type of the target object, which can be handled by giving every object a standard header including layout information. For an object-oriented language, that can probably be handled as another field in the vtable.

Details for one system can be found in the GHC Commentary: Storage, One notable optimization in marking is recognizing the various object types that have a fixed layout without following the info pointer. Stacks are handled by requiring layout information at a standard location in the stack frame.

Things like Tolmach's type reconstruction are only relevant if you actually want to do something like tagless object representations (and note an object oriented language usually uses a vtable anyway), or if you want to support polymorphism without either boxing or specialization.