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).
Title
Multi-Version Structures in PROLOG
Published
1984-05-01
Full Collection Name
Electrical Engineering & Computer Sciences Technical Reports
Other Identifiers
CSD-84-178
Type
Text
Extent
28 p
Archive
The Engineering Library
Usage Statement
Researchers may make free and open use of the UC Berkeley Library’s digitized public domain materials. However, some materials in our online collections may be protected by U.S. copyright law (Title 17, U.S.C.). Use or reproduction of materials protected by copyright beyond that allowed by fair use (Title 17, U.S.C. § 107) requires permission from the copyright owners. The use or reproduction of some materials may also be restricted by terms of University of California gift or purchase agreements, privacy and publicity rights, or trademark law. Responsibility for determining rights status and permissibility of any use or reproduction rests exclusively with the researcher. To learn more or make inquiries, please see our permissions policies (https://www.lib.berkeley.edu/about/permissions-policies).
