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.