A root set separates reachable objects from unused allocations.
An explicit heap graph can be traced from roots, marking every referenced object once and classifying allocations that no root can reach.
Which allocations must a storage manager preserve when references form a graph?
- Represent heap objects as identifiers with outgoing references
- Trace every path starting from an explicit root set
- Stop revisiting marked objects when the graph contains a cycle
- Distinguish unreachable allocations without reclaiming them in this model
mark adds an object identifier before following its children. mark-list carries the growing marked set across sibling references, so an object reached through several paths appears once. The first heap leaves garbage and orphan allocated but unreachable from root a.
The second heap contains a cycle from a through b and c back to a. contains? stops the revisit, while mark-roots starts a second traversal from x. unreachable then scans every allocation and classifies only dead outside the marked set. This lesson models tracing and classification, not memory reclamation itself.
(begin
(define (contains? item items)
(cond ((null? items) #f)
((eq? item (car items)) #t)
(else (contains? item (cdr items)))))
(define (children object heap) (cdr (assoc object heap)))
(define (mark object heap marked)
(if (contains? object marked)
marked
(mark-list (children object heap) heap (cons object marked))))
(define (mark-list objects heap marked)
(if (null? objects)
marked
(mark-list (cdr objects) heap
(mark (car objects) heap marked))))
(define (unreachable heap marked)
(cond ((null? heap) '())
((contains? (car (car heap)) marked)
(unreachable (cdr heap) marked))
(else
(cons (car (car heap)) (unreachable (cdr heap) marked)))))
(define heap '((a b c) (b d) (c) (d) (garbage orphan) (orphan)))
(define marked (mark 'a heap '()))
(list (reverse marked) (unreachable heap marked)))- Output
- —
- Value
- —
- Diagnostic
- —
The first program returns ((a b d c) (garbage orphan)). The second returns ((a b c x y) (dead)).
In the first run, follow the root through b to d before returning to c, then watch the heap scan reject marked IDs. In the second run, find the contains? hit that stops the c-to-a cycle and the later traversal from root x.
Change the program before you read the hint.
Add a reference from orphan to a while keeping root a. Predict whether garbage and orphan become reachable.
Show one hint
Reachability follows references outward from roots. A reference from an unreachable object toward a root does not make that object reachable.