Patrick C. McGeer and Alvin M. Despain

EECS Department
University of California, Berkeley
Technical Report No. UCB/CSD-87-356
July 1987

http://www2.eecs.berkeley.edu/Pubs/TechRpts/1987/CSD-87-356.pdf

Two algorithms are considered for implementation in Prolog. It is shown that these algorithms cannot be implemented in pure Prolog and retain their nominal time complexity. It is shown that a generalization of Lisp's rplaca/rplacd construct suffices for these algorithms. We give a method for the implementation of the new construct, rplacarg, on a structure-copying Warren Abstract Machine and discuss implementation for a structure-sharing Warren Abstract Machine. We show how rplacarg may be implemented in CProlog using only pure Prolog constructs and the var construct. We show that var can be implemented in terms of the Prolog not primitive. We show that rplacarg can be used to implement multidimensional arrays efficiently in Prolog.

BibTeX citation:

@techreport{McGeer:CSD-87-356,
    Author = {McGeer, Patrick C. and Despain, Alvin M.},
    Title = {Data Structures and Destructive Assignment in Prolog},
    Institution = {EECS Department, University of California, Berkeley},
    Year = {1987},
    Month = {Jul},
    URL = {http://www2.eecs.berkeley.edu/Pubs/TechRpts/1987/5475.html},
    Number = {UCB/CSD-87-356},
    Abstract = {Two algorithms are considered for implementation in Prolog. It is shown that these algorithms cannot be implemented in pure Prolog and retain their nominal time complexity. It is shown that a generalization of Lisp's rplaca/rplacd construct suffices for these algorithms. We give a method for the implementation of the new construct, rplacarg, on a structure-copying Warren Abstract Machine and discuss implementation for a structure-sharing Warren Abstract Machine. We show how rplacarg may be implemented in CProlog using only pure Prolog constructs and the var construct. We show that var can be implemented in terms of the Prolog <i>not</i> primitive. We show that rplacarg can be used to implement multidimensional arrays efficiently in Prolog.}
}

EndNote citation:

%0 Report
%A McGeer, Patrick C.
%A Despain, Alvin M.
%T Data Structures and Destructive Assignment in Prolog
%I EECS Department, University of California, Berkeley
%D 1987
%@ UCB/CSD-87-356
%U http://www2.eecs.berkeley.edu/Pubs/TechRpts/1987/5475.html
%F McGeer:CSD-87-356