| Home > Publications > Reports > Informatics (CW) |
CW 289
B. Demoen
Prolog and abduction 4 writing garbage collectors
Abstract
It seems silly and impractical: to write a garbage collector (for a Prolog engine) in Prolog itself. However, there are at least three advantages in doing so: (1) one gets a runnable specification of the garbage collector, (2) it can enhance understanding of the algorithms involved without having to worry about gory pointer details, (3) the garbage collector written in Prolog can be used for debugging its implementation in a lower level language. We show how a sliding collector can be specified in Prolog in a reasonably declarative way, how it can be executed best within a tabling environment, and how it was of use during the development of the heap garbage collectors of BinProlog, XSB and more recently ilProlog. We indicate how the Prolog implementation can reconstruct the classical Morris algorithm. We also specify the garbage collection process in an abductive formalism and speculate on how constraints on the abductive solver can retrieve well-known algorithms.
report.pdf / mailto: B. Demoen