NetNews Usenet Archive 1992 #30/NN_1992_30.iso/spool/comp/lang/prolog/2235

Text File | 1992-12-14 | 4.2 KB | 95 lines

Newsgroups: comp.lang.prolog
Path: sparky!uunet!gumby!destroyer!cs.ubc.ca!fornax!gregory
From: [e-mail] (Gregory Sidebottom)
Subject: Re: Array implementations?
In-Reply-To: [e-mail]'s message of Mon, 14 Dec 1992 11:04:10 GMT
Message-ID: <[e-mail]>
Organization: CSS, Simon Fraser University, Burnaby, B.C., Canada
References: <[e-mail]> <[e-mail]>
Date: Mon, 14 Dec 1992 18:55:40 GMT
Lines: 83

In article <[e-mail]> [e-mail] (Joachim Schimpf) writes:

   In article [e-mail], [e-mail] (Tom Fawcett) writes:
   >
   >Michael Covington:
   >>    Here's a reasonable substitute for a 15-element array:
   >>
   >>      f(a,b,c,d,e,f,g,h,i,j,k,l,m,n,o)
   >>
   >>    Use 'arg' to access elements by numbered position.
   >>
   >>    Limitations:
   >>      (1) Intriniscally 1-dimensional (but you can make an array of arrays);
   >>      (2) Some maximum number of elements (maybe 256).
   >
   >
   >Greg Sidebottom:
   >
   >> I would add:
   >>  (3) element update is O(size of array) in time and space, which is
   >>      much worse than O(log size of array) for trees
   >
   >I think element access and update (via arg/3) is constant time, at least in
   >Quintus Prolog.  The QP library file arrays.pl has such an implementation, and
   >states that fetch and access are constant.

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.

   >
   >> Don't think I am Prolog bashing, Prolog is my favorite language.  But
   >> I think if you really need constant time access and update arrays, you
   >> should probably use some other language.

   Let's get that straight: Prolog _has_ constant time access arrays,
   they happen to be called structures, as Michael Covington has
   pointed out correctly.

   Now 'access' in Prolog means unification, which subsumes 'read' and
   'assign once'.

When I hear arrays, I expect access *and* update.  After all, many
applications require the update of arrays as well.

   What you don't have in Prolog, neither in arrays nor elsewhere, is
   destructive assignment. As a consequence, in a situation where you want a
   slightly modified  version of an array that you already have (_and_
   you don't need to keep the old version) you have to make a copy
   where you would otherwise destructively modify the old array.


 ---------------------------------------------------------------------------
    Joachim Schimpf                                 Email   [e-mail]
    European Computer-Industry Research Centre      Phone   [phone]
    Arabellastrasse 17, D-8000 Munich 81, Germany   Fax     [phone]

Greg
--
Greg Sidebottom,                                      | There's not a word that
Expert Systems Laboratory, Centre for Systems Science | goes here that rhymes
Simon Fraser University, Burnaby BC V5A 1S6, Canada   | with anything. -CVB