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.