[ CelesOrion's Home Page ]

A list of helpful papers (with my reading notes)

A Unified Theory of Garbage Collection

I found this paper especially illuminating when you have seen too many debates on reference counting and so-called "garbage collection". It provides a unified view that the reference counting and tracing approaches are duals of each other. And the efforts to improve one of them will drive it to approximate the other. Here are some interesting points:

• In the fix-point formulation described in the paper, there might be multiple fix-points of an object graph with cycles. E.g. [a->b, b->a] have 2 fix-points, [rc(a)=0, rc(b)=0] and [rc(a)=1, rc(b)=1]. The tracing gradually approaches the former while the RC approaches the latter. Unfortunately, in this case, the former least fix-point, is what we actually want to reach (i.e. both objects are dead).
• (Classic) reference counting has an incremental nature while sacrificing the throughput due to the immediate update of counters.
• To make tracing incremental, it's common to use read & write barriers, which are essentially the same operation with the increase and decrease of counters when doing assignments in a typical RC approach.
• Most hybrid GC approaches can be sketched by showing which method in the dual is used to manage the references of different kinds. E.g. from roots to heap objects, heap objects to heap objects, heaps objects to another heap objects (when there are multiple heaps).

Compiling without Continuations

I'm happy to see another unification in intermediate representation (IR) used by compilers. It has been a long time for the imperative language camp to use IR in SSA form in their compilers. But for the functional language camp, there's still a folklore of CPS IR. Though proved to be equivalent to SSA form, the CPS IR still remains the problem of being totally unreadable for humans. In this paper, I'm pleased to see the de facto standard compiler of Haskell used a direct style IR, extending lambda calculus in A-normal form with join points. It gives a closer correspondence between these two kinds of IR. Basically, the join points can be regarded the counterparts of basic blocks (with parameters) in the SSA form, and the functions are just functions. Of course, due to the different attitudes towards high-order functions, data types, etc. in the two camps, the concrete compilation process and focus are still not very similar.