A fast garbage collection algorithm for WAM — based PROLOG

Garbage collection for Warren abstract machine is complicated by:•three semantically distinct types of pointers, whose types must be preserved as well as their relative positions;•need for marking used atomic values because of TRAIL compactification;•capability of structures to grow incrementally, i.e. in the wrong direction.Prolog data graphs (DAGs, circular structures would interrput the present algorithm) are represented as linear structures by an invertible pointer reversing transform. Reversal of forward pointers is delayed till needed, so that the algorithm can manage with one pass through the workspace. The technique of delayed reversal enables compactification of (two or more) physically separated memory areas which point at each other.If the workspace contains n used words k of which are active, the complexity of the algorithm is #x03B1; n + β k + OVERHEAD, where OVERHEAD depends on the structure of active data graphs involved.