CW 571

Bart Demoen and Phuong-Lan Nguyen
Representation sharing for Prolog

Abstract

Techniques to reduce the memory footprint of an application include representation sharing between multiple copies of some data. Representation sharing has been implemented through hash-consing in functional languages. Representation sharing for Prolog was not given that much attention in the past. Here, representation sharing is defined for Prolog implementations in a structure copying environment (basically the WAM), and the specific issues arising from the logical variable and backtracking are analyzed. A high-level algorithm is described, and its properties are derived. An implementation in hProlog is evaluated. The impact of representation sharing depends very much on the application. The cost seems acceptable and the memory gains can be large. Issues related to the representation sharing policy are discussed.

report.pdf (263K) / mailto: B. Demoen