Values are responsible for their garbage

A value in IvoryScript may contain references to other values. A list may refer to its tail, a closure may retain captured values and a pointer may refer to another allocated cell.

A garbage collector therefore needs to know which values are reachable from the values it encounters.

IvoryScript makes this knowledge type-directed. A type whose values may contain references provides an instance of Mark_GC:

      class Mark_GC a where {
         mark_GC :: a -> Void
      }
   

The result is Void because marking has an effect but denotes no resulting value.

A pointer provides a simple example:

      instance Mark_GC Ptr b | instance Mark_GC b where {
         inline mark_GC ptr =
            case ptr of {
               Null ->  #!Void;
               Ptr x -> if markPtr_GC ptr then mark_GC x
            }
      }
   

A null pointer contains nothing further to mark. For a non-null pointer, markPtr_GC marks the referenced cell and indicates whether its contents still need to be considered. If so, mark_GC is applied to the contained value according to its own type.

The same principle applies to constructed values. Their representation determines which components may contain references, and the corresponding marking operation follows those components.

This is particularly significant for closures. A closure may retain the values associated with its free variables. Those captured values form part of the reachable value graph and are marked according to their types in the same way as other contained values.

The garbage collector therefore does not require a central description of every possible value representation. This is ordinary mark and sweep garbage collection, with the marking of values expressed through the type system - each type supplying the information required to follow references contained by its values.

Thus a value's type determines how values reachable from it are marked. In that sense, values are responsible for their garbage.