Paper 1-2,3 Semispace Copying by Fenichel and Yochelson (1969) and Cheney (1980)

A LISP Garbage Collector for Virtual Memory Computer

A Nonrecursive List Compacting Algorithm

The two papers were the two early Copying Collector papers. They have very similar approach, and the only difference is how the work list of objects are implemented.

Fenichel and Yochelson used a stack and therefore had a recursive algorithm to go through the work list. Although they suggest an algorithm in TAOP1 p417-419 would make it non-recursive, they did not talk about it because it is too complex. Also, the description of the algorithm in the paper was very confusing and ad hoc. Both researchers were from MIT.

Cheney's implementation is much simpler. It used a FIFO queue to store grey objects hence making the algorithm non-recursive. That's actually a common trick to convert a recursive algorithm into a breadth-first traverse with a help of additional memory space (the queue). The way Cheney demonstrating the algorithm is much more precise and easier to understand. He illustrated the algorithm and explained it step by step in detail, while the Fenichel and Yochelson paper gave a partial pseudo code without much explanation. Jones's description of the algorithm in the TGCH book is probably even better. Chris Cheney was from the real Cambridge. He just vanished after this paper. I cannot find any further research he has done in the area...

The basic idea to make Copying Collector working is a forward pointer from the FROM space to the TO space during the GC. The pointer was created after the object was copied to the TO space, and is made pointing to the copied object in the TO space. It helps all the further references to the object to be updated pointing to the new address in the TO space.