Author(s)
Structure Sharing and Structure Copying Revisited
Abstract
Various Prolog systems can be classified into two categories: Structure
Sharing (SS) and Structure Copying (SC). The fundamental distinction
of SS and SC is the way of representing structures. SS represents a
structure instance by a two-pointer molecule with one to the structure
skeleton and the other to a binding environment. On the other hand, SC
makes a concrete copy of a structure whenever the structure is matched
against a variable.
SS was used in earlier Prolog implementations while SC has been accepted
as the de facto standard in modern Prolog implementations.
However, analysis and practical comparison of SS and SC shown that
programs can be written which make any one method almost arbitrarily
worse than the other. In this paper, I propose a new Prolog
implementation approach - Program Sharing (PS).
The major contribution of this work is that PS has the advantages of
both SC (representing terms of different types to fit in the size of a
machine word) and SS (low overhead in constructing a dynamic structure
instance), and the concept of program sharing could be used to realize
all special-case instruction-driven unification. PS has been adopted in
the design of a new Prolog abstract machine - the LAM(1/2).
I have implemented an experimental LAM(1/2)-emulator in C. Benchmarks
show that this new approach is very promising in both performance and
memory utilization.
Accepted Papers