🚀 go-pugleaf

In article <1992Dec14.185540.2981@cs.sfu.ca> gregory@cs.sfu.ca (Gregory Sidebottom) writes:

   Yes, *access* is in constant time, *update* is not.  The only way to
   way to change a value in an array in Prolog implemented using
   structures is to copy it except put the new element where the old one
   was.  This takes linear time and space.  With trees, it takes log time
   and space on average, since you only have to traverse and copy one
   path in the tree.

   Now you may be able to hack constant time access and update arrays
   into Prolog using assert/retract or by linking with some C code and
   using assignment, but that wouldn't be very Prolog like.  You would
   lose most of the advantages of Prolog and might as well use a
   procedural language.  

   There is some research in the functional programming language
   community into providing logical versions of arrays with constant time
   access and update for the way arrays are usually used.  The idea is
   that if you change a value in an array by making a new copy, usually,
   you don't need to look at the old copy ever again.  If the compilers
   can recognize this 'single threaded' use of arrays, it safely
   implement the array operations using destructive assignment.  An
   approach for non-single threaded uses is to keep the original array
   and each reference to the array is associated with a set of changes
   that have taken place.  This can also can give close time constant
   time and space performance in many applications.  

This idea was described (and implemented) for logic programming at
least as early as 1984.

  Eriksson and Rayner: Incorporating Mutable Arrays into Logic Programming,
  Proceedings of the Second International Logic Programming Conference,
  Uppsala University, Sweden, 1984.

--
Lars-Henrik Eriksson                            Internet: lhe@sics.se
Swedish Institute of Computer Science           Phone (intn'l): +46 8 752 15 09
Box 1263                                        Telefon (nat'l): 08 - 752 15 09
S-164 28  KISTA, SWEDEN                         Fax: +46 8 751 72 30