If you can look at a word of memory and differentiate pointers from values, garbage collection can become extremely simple. It's a shame that tagged architectures have largely died out.<p>As an experiment, I tried writing a garbage collector which used high-order bits of a word to identify pointers. The result is about a page of code in Forth:<p><a href="http://hastebin.com/raw/gabunowelo.fs" rel="nofollow">http://hastebin.com/raw/gabunowelo.fs</a><p>This example works exclusively with fixed-size "cons pair" allocations, but generalizing to arbitrary-sized allocations only increases the complexity of the system slightly. Obviously this bitflag technique is not "safe" in general, as arbitrary values on the stacks could produce false positives, but it's easy to imagine a 33-bit or 65-bit architecture that provided the necessary hardware support without such caveats.