Carnegie Mellon Rice University Carnegie Mellon jgmorris@ cs. cmu. edu matthias@ cs.
rice. edu rwh@ cs. emu. edu Most specifications of garbage collectors concentrate on the
low-level algorithmic details of how to find and preserve accessible objects. Often, they focus
on bit-level manipulations such as “scanning stack frames,”“marking objects,”'(tagging data,”
etc. While these details are important in some contexts, they often obscure the more
fundamental aspects of memory management: what objects are garbage and why?

Most specifications of garbage collectors concentrate on the low-levél algorithmic details of
hou to find and preserve accessible objects. Often, they focus on bit-level manipulations
such as “scanning stack frames,”“marking objects,”“tagging data,” etc. While these details
are important in some contexts, they often obscure the more fundamental aspects of memory
management: what objects are garbage and why? We develop a series of calculi that are
just low-level enough that we can express allocation and garbage collection, yet are …