A new term representation method for prolog

AbstractVarious Prolog systems can be classified into two categories: Structure Sharing (SS) and Structure Copying (SC). The fundamental distinction between SS and SC is the way in which they represent structures. SS represents a structure instance by a two-pointer molecule with one end toward the structure skeleton and the other toward a binding environment. On the other hand, SC makes a concrete copy of a structure whenever the structure is matched against a free variable. SS was used in earlier Prolog implementations, whereas SC has been accepted as the de facto standard in modern Prolog implementations. However, analysis and practical comparison of SS and SC claim that programs can be written that make any one method almost arbitrarily worse than the other. In this paper, I propose a new Prolog term representation 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 LAM12. I have implemented an experimental LAM12 emulator in C. Benchmarks show that this new approach is very promising in memory utilization and reasonably close to a very good SC-based system in performance