Shimon Cohen

EECS Department
University of California, Berkeley
Technical Report No. UCB/CSD-84-178
May 1984

http://www2.eecs.berkeley.edu/Pubs/TechRpts/1984/CSD-84-178.pdf

In this paper we discuss the important problem of implementing MVS (Multi Version Structures) like Arrays, Hash-Tables, Sets, in logic programming Languages (i.e. PROLOG). One can define pure PROLOG predicates which will behave like arrays, etc. but the question is how efficient these predicates are compared to the equivalent operations in PASCAL, C or LISP. Obviously the problem in logic programming languages that you are not allowed to change the structure of logic terms and variables' values, in logic programming you are only allowed to instantiate variables (once).

We discuss:
(1) What kind of MVS we want to have in PROLOG
(2) The problems to implement them.
(3) The alternative solutions.

We show how to implement arrays efficiently by introducing "Multi Version Arrays". Arrays which differ slightly from each other will be implemented using one physical array, thus the cost of updating an array while retaining the old array will be small. It is also possible (using our method) to "go back" to older versions and start modifying them (without any damage to other versions). We show how to execute parallel operations with such arrays and how to use "Multi Version Arrays" to implement sets as hashtables (not lists). Sets are important and diverse data structures with many special cases, in order to take advantage of this phenomena we propose to add some specifications (while "creating" the set) which will enable the system (compiler) to choose the most efficient internal representation (the internal representation will be transparent to the user).

BibTeX citation:

@techreport{Cohen:CSD-84-178,
    Author = {Cohen, Shimon},
    Title = {Multi-Version Structures in PROLOG},
    Institution = {EECS Department, University of California, Berkeley},
    Year = {1984},
    Month = {May},
    URL = {http://www2.eecs.berkeley.edu/Pubs/TechRpts/1984/5961.html},
    Number = {UCB/CSD-84-178},
    Abstract = {In this paper we discuss the important problem of implementing MVS (Multi Version Structures) like Arrays, Hash-Tables, Sets, in logic programming Languages (i.e. PROLOG).  One can define pure PROLOG predicates which will behave like arrays, etc. but the question is how efficient these predicates are compared to the equivalent operations in PASCAL, C or LISP.  Obviously the problem in logic programming languages that you are not allowed to change the structure of logic terms and variables' values, in logic programming you are only allowed to instantiate variables (once).  <p>  We discuss:  <br />(1) What kind of MVS we want to have in PROLOG  <br />(2) The problems to implement them.  <br />(3) The alternative solutions.  <p>  We show how to implement arrays efficiently by introducing "Multi Version Arrays". Arrays which differ slightly from each other will be implemented using one physical array, thus the cost of updating an array while retaining the old array will be small. It is also possible (using our method) to "go back" to older versions and start modifying them (without any damage to other versions). We show how to execute parallel operations with such arrays and how to use "Multi Version Arrays" to implement sets as hashtables (not lists). Sets are important and diverse data structures with many special cases, in order to take advantage of this phenomena we propose to add some specifications (while "creating" the set) which will enable the system (compiler) to choose the most efficient internal representation (the internal representation will be transparent to the user).}
}

EndNote citation:

%0 Report
%A Cohen, Shimon
%T Multi-Version Structures in PROLOG
%I EECS Department, University of California, Berkeley
%D 1984
%@ UCB/CSD-84-178
%U http://www2.eecs.berkeley.edu/Pubs/TechRpts/1984/5961.html
%F Cohen:CSD-84-178