[Haskell-cafe] Garbage collecting pointers

Hi For some time I have been thinking about an idea, which could limit Haskell's memory footprint. I don't know if the idea is crazy or clever, but I would love to hear peoples thoughts about it. The short story is, I propose that the garbage collector should not just reclaim unused memory, it should also diminish the need for pointers, by replacing nested data structures with larger chunks of consecutive memory. In other words, I would diminish the need for pointers for arbitrary recursive data types, just as replacing linked lists with arrays eliminate the need for pointers. I will explain my idea by an example of a data type we all know and love: data List a = Cons a (List a) | Nil each Cons cell uses two pointers - one for the element and one for the rest of the list. If we could somehow merge the element and the rest of the list into consecutive memory, we would be able to eliminate the pointer to the rest of list. On 64 bit architectures merging would save us 8 bytes of "wasted" memory. If we could merge n elements together we could save n*8 bytes of memory. 64 bit pointers are wasteful in another way, as nobody has anywhere near 2^64 bytes of memory. And nobody is going to have that much memory for decades to come. Thus, we could use the 8 most significant bits for something besides pointing to memory, without loosing any significant ability to address our memories. This would be similar to how GHC uses some of the least significant bits for pointer tagging. I suggest using the 8 most significant bits for what could be termed the length of the pointer. A length of zero would mean that the pointer, pointed to a Cons-cell just like we have them today. A length of one would mean that one extra element were embedded into the cons cell. That is, we would have this block of consecutive memory: <Cons marker> <Cons marker> <pointer to rest of list> We could also call this a chunk of length two. A pointer of length two, would mean two embedded list elements (a chunk of length three). And so on... By embedding the "length" of the list in the pointer, it becomes possible that one pointer could point to the beginning of a chunk of n consecutive elements, while another one could point to the middle of the same chunk (but the pointer would be of a different length). This would enable sharing without having to break up into smaller chunks. How should chunks be created? Or if a functions creates a lot of one long chunks, how are they turned into longer chunks. I imagine that it would be the job of the garbage collector, to merge the different elements in a list into larger chunks. Of cause some code, like reading a file, could create chunks directly. I have used list as an example. But I imagine that GHC could do this for any recursively defined data type. I can see few, but big disadvantages also. Mainly, my scheme would complicate dereferencing a pointer, which make the compiled code larger and it might make branch prediction harder. The latter would only be a problem on architectures that are pipelined, but popular processors from Intel and AMD are both heavily pipelined. /Mads