home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #30 / NN_1992_30.iso / spool / comp / lang / prolog / 2230 < prev    next >
Encoding:
Text File  |  1992-12-14  |  2.6 KB  |  62 lines
  1. Newsgroups: comp.lang.prolog
  2. Path: sparky!uunet!mcsun!Germany.EU.net!ecrc!acrab5!joachim
  3. From: joachim@ecrc.de (Joachim Schimpf)
  4. Subject: Re: Array implementations?
  5. Message-ID: <1992Dec14.110410.25384@ecrc.de>
  6. Sender: news@ecrc.de
  7. Reply-To: joachim@ecrc.de
  8. Organization: European Computer-Industry Research Centre GmbH.
  9. References: <FAWCETT.92Dec10103127@iron.cs.umass.edu>
  10. Date: Mon, 14 Dec 1992 11:04:10 GMT
  11. Lines: 49
  12.  
  13. In article 92Dec10103127@iron.cs.umass.edu, fawcett@iron.cs.umass.edu (Tom Fawcett) writes:
  14. >
  15. >Michael Covington:
  16. >>    Here's a reasonable substitute for a 15-element array:
  17. >> 
  18. >>      f(a,b,c,d,e,f,g,h,i,j,k,l,m,n,o)
  19. >> 
  20. >>    Use 'arg' to access elements by numbered position.
  21. >> 
  22. >>    Limitations:
  23. >>      (1) Intriniscally 1-dimensional (but you can make an array of arrays);
  24. >>      (2) Some maximum number of elements (maybe 256).
  25. >
  26. >
  27. >Greg Sidebottom:
  28. >
  29. >> I would add:
  30. >>  (3) element update is O(size of array) in time and space, which is
  31. >>      much worse than O(log size of array) for trees
  32. >
  33. >I think element access and update (via arg/3) is constant time, at least in
  34. >Quintus Prolog.  The QP library file arrays.pl has such an implementation, and
  35. >states that fetch and access are constant.
  36. >
  37. >> Don't think I am Prolog bashing, Prolog is my favorite language.  But
  38. >> I think if you really need constant time access and update arrays, you
  39. >> should probably use some other language.
  40.  
  41. Let's get that straight: Prolog _has_ constant time access arrays, they happen
  42. to be called structures, as Michael Covington has pointed out correctly.
  43. (In a typed language, the difference between an array and a structure is that
  44. an array is a collection of items of the same type, while a structure groups
  45. together items of different types. In an untyped language like Prolog there is
  46. no need to make this distinction).
  47.  
  48. Now 'access' in Prolog means unification, which subsumes 'read' and 'assign once'.
  49.  
  50. What you don't have in Prolog, neither in arrays nor elsewhere, is destructive
  51. assignment. As a consequence, in a situation where you want a slightly modified
  52. version of an array that you already have (_and_ you don't need to keep the old
  53. version) you have to make a copy where you would otherwise destructively modify
  54. the old array.
  55.  
  56. Modest advertisement: In SEPIA/ECLiPSe we decided to have no arity limit
  57. on structures precisely because of their potential use as arrays. ---------------------------------------------------------------------------
  58.  Joachim Schimpf                                 Email   joachim@ecrc.de 
  59.  European Computer-Industry Research Centre      Phone   +49 89 92699 111
  60.  Arabellastrasse 17, D-8000 Munich 81, Germany   Fax     +49 89 92699 170
  61.  
  62.