home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #30 / NN_1992_30.iso / spool / comp / lang / prolog / 2243 < prev    next >
Encoding:
Text File  |  1992-12-16  |  2.6 KB  |  53 lines
  1. Newsgroups: comp.lang.prolog
  2. Path: sparky!uunet!mcsun!sunic!sics.se!lhe
  3. From: lhe@sics.se (Lars-Henrik Eriksson)
  4. Subject: Re: Array implementations?
  5. In-Reply-To: gregory@cs.sfu.ca's message of Mon, 14 Dec 1992 18:55:40 GMT
  6. Message-ID: <LHE.92Dec16122322@yang.sics.se>
  7. Sender: news@sics.se
  8. Organization: Swedish Institute of Computer Science, Kista
  9. References: <FAWCETT.92Dec10103127@iron.cs.umass.edu> <1992Dec14.110410.25384@ecrc.de>
  10.     <1992Dec14.185540.2981@cs.sfu.ca>
  11. Date: Wed, 16 Dec 1992 11:23:22 GMT
  12. Lines: 39
  13.  
  14. In article <1992Dec14.185540.2981@cs.sfu.ca> gregory@cs.sfu.ca (Gregory Sidebottom) writes:
  15.  
  16.    Yes, *access* is in constant time, *update* is not.  The only way to
  17.    way to change a value in an array in Prolog implemented using
  18.    structures is to copy it except put the new element where the old one
  19.    was.  This takes linear time and space.  With trees, it takes log time
  20.    and space on average, since you only have to traverse and copy one
  21.    path in the tree.
  22.  
  23.    Now you may be able to hack constant time access and update arrays
  24.    into Prolog using assert/retract or by linking with some C code and
  25.    using assignment, but that wouldn't be very Prolog like.  You would
  26.    lose most of the advantages of Prolog and might as well use a
  27.    procedural language.  
  28.  
  29.    There is some research in the functional programming language
  30.    community into providing logical versions of arrays with constant time
  31.    access and update for the way arrays are usually used.  The idea is
  32.    that if you change a value in an array by making a new copy, usually,
  33.    you don't need to look at the old copy ever again.  If the compilers
  34.    can recognize this 'single threaded' use of arrays, it safely
  35.    implement the array operations using destructive assignment.  An
  36.    approach for non-single threaded uses is to keep the original array
  37.    and each reference to the array is associated with a set of changes
  38.    that have taken place.  This can also can give close time constant
  39.    time and space performance in many applications.  
  40.  
  41. This idea was described (and implemented) for logic programming at
  42. least as early as 1984.
  43.  
  44.   Eriksson and Rayner: Incorporating Mutable Arrays into Logic Programming,
  45.   Proceedings of the Second International Logic Programming Conference,
  46.   Uppsala University, Sweden, 1984.
  47.  
  48. --
  49. Lars-Henrik Eriksson                            Internet: lhe@sics.se
  50. Swedish Institute of Computer Science           Phone (intn'l): +46 8 752 15 09
  51. Box 1263                                        Telefon (nat'l): 08 - 752 15 09
  52. S-164 28  KISTA, SWEDEN                         Fax: +46 8 751 72 30
  53.