Week 44: TAOCP 2.3.5 Lists and Garbage Collection

General lists that can share sublists and even contain themselves, reference counting, and garbage collection by marking reachable nodes. It includes the famous trick of marking without an auxiliary stack by temporarily reversing links (Schorr-Waite).

Time About 9 hours this week

Why it matters

You wrote a mark-sweep collector for clox in week 14. This section shows the same problem with tight memory, and link reversal is a classic example of clever pointer manipulation.

Before you start

2.3.1 Traversing Binary Trees
Crafting Interpreters ch 26 (Garbage Collection)

How to approach it

Compare Knuth's marking algorithms to your clox gray stack. Trace the link-reversal marking algorithm on a small graph on paper; it is tricky and worth drawing every step.

Exercises

Work every exercise rated 10 to 20; most are about tracing the algorithm by hand or tweaking one step, which is exactly the skill you want. Pick one or two rated 20 to 25 that involve modifying the algorithm and implement your modification in a real language with tests. Skip HM exercises unless you enjoy calculus, and treat anything rated 40+ as a research problem, not homework.

Traps

Reference counting cannot reclaim cycles. Knuth explains why; make sure you can too.
In link reversal, forgetting to restore a link on the way back up.