Representation Sharing for Prolog
By
PHUONG-LAN NGUYEN UCO, Angers, France
BART DEMOEN K.U.Leuven, Belgium
Abstract
Representation sharing can reduce the memory footprint of a program by sharing one representation between duplicate terms. The most common implementation of representation sharing in functional programming systems is known as hash-consing. In the context of Prolog, representation sharing has been given little attention. Some current techniques that deal with representation sharing are reviewed. The new contributions are: (1) an easy implementation of input sharing for findall/3; (2) a description of a sharer module that introduces representation sharing at runtime. Their realization is shown in the context of the WAM as implemented by hProlog. Both can be adapted to any WAM-like Prolog implementation. The sharer works independently of the garbage collector, but it can be made to cooperate with the garbage collector. Benchmark results show that the sharer has a cost comparable to the heap garbage collector, that its effectiveness is highly application dependent, and that its policy must be tuned to the collector.
Bibtex (Use it for references)
@article{KEYWORD,
journal = {Theory and Practice of Logic Programming},
publisher = {Cambridge University Press},
author = {Phuong-Lan Nguyen and Bart Demoen},
title = {Representation sharing for Prolog},
volume = {13},
number = {1},
year = {2013},
pages = {71-106}
}