Reference Count Here's the main idea to reference counting: 1.Attach a counter to each pair in memory. 2.When a new pointer is connected to that pair, increment the counter. 3.When a pointer is removed, decrement the counter. 4.Any cell with 0 counter is garbage. Consider the following example, and draw the box-and-pointer diagrams below, keeping a ``reference counter'' with each cell. (define a (list 1 2 3)) (set-cdr! a 4) (set-cdr! a a) (set! a 1) Reference Counting can't handle circular data structures! Stop and Copy Here's the main idea to Stop and Copy: 1.Split memory in half (Working memory and Copy memory). 2.Keep a free pointer to the free part of memory. 3.When Memory runs out, stop computation and begin garbage collection. 1.Place scan and free pointers at the start of the Copy memory. 2.Copy the Root Set over to copy memory, incrementing free. In each location that's copied over, put the ``Broken Heart'' token in the car and the forwarding address in the cdr. 3.Starting at the scan pointer, check the car and the cdr. If either is a pointer, look at the location in Working memory. If it's already been copied (i.e. it has a ``Broken Heart''), update the reference. Otherwise, copy the location and put the ``Broken Heart'' in the old location. 4.Repeat until scan = free. 5.Swap the roles of the Working and Copy memory. Mark - Sweep Here's the main idea to Mark-Sweep: 1.Add a Mark Bit to each location in memory. 2.Keep a free pointer to the head of the free list. 3.When Memory runs out, stop computation, clear the Mark Bits and begin garbage collection. 4.Mark 1.Start at the root and follow the accessible structure (keeping a stack of where you still need to go). 2.Mark every cell you visit. 3.Stop when you see a marked cell, so you don't go into a cycle. 5.Sweep 1.Start at the end of memory, and build a new free list. 2.If a cell is unmarked, then it's garbage, so hook it into the free list.