home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #31 / NN_1992_31.iso / spool / comp / lang / pop / 172 < prev    next >
Encoding:
Internet Message Format  |  1992-12-23  |  2.2 KB
  1. Path: sparky!uunet!spool.mu.edu!agate!doc.ic.ac.uk!uknet!bhamcs!axs
  2. From: axs@cs.bham.ac.uk (Aaron Sloman)
  3. Newsgroups: comp.lang.pop
  4. Subject: Re: Dynamic List Implementation
  5. Message-ID: <BzpFyF.F6t@cs.bham.ac.uk>
  6. Date: 23 Dec 92 09:06:15 GMT
  7. References: <116670038@otter.hpl.hp.com>
  8. Sender: news@cs.bham.ac.uk
  9. Organization: School of Computer Science, University of Birmingham, UK
  10. Lines: 46
  11. Nntp-Posting-Host: emotsun
  12.  
  13. sfk@otter.hpl.hp.com (Steve Knight) writes:
  14.  
  15. > Date: 22 Dec 92 14:55:12 GMT
  16. > Organization: Hewlett-Packard Laboratories, Bristol, UK.
  17. >
  18. > I've always been puzzled why POPLOG implements dynamic lists using
  19. > pairs rather than a separate dpair key.  In fact, a dynamic list
  20. > is represented using a pair whose back is a procedure and whose
  21. > front is true.
  22.  
  23. I absolutely agree that this is wrong and wish we had changed it in
  24. Pop-11 instead of following Pop2, just as we introduced a new
  25. data-type for undefs and for booleans. (In Pop2, 0 was false, alas.)
  26.  
  27. I cannot see any reason for the way things are except that the
  28. original Pop2 was implemented on a tiny machine and a new record
  29. type would have required an unacceptable amount of additional space
  30. in the system.
  31.  
  32. One problem with having a different record type for dynamic lists is
  33. that if you expand a dynamic list you would then have to change the
  34. type of the record, since lots of things can be pointing to that
  35. list. Your message did not point out that one of the consequences of
  36. applying "null" to a list is that if it is dynamic and non-null it
  37. gets "solidified" by one step, so that if null(list) returns false
  38. you can then optimise and apply "front", or even "fast_front" to
  39. list.
  40.  
  41. I suspect we would then need three record types
  42.  
  43.     dlist = unexpanded dynamic list
  44.     dnull = empty dynamic list
  45.     pair  = static list, or link for expanded part of dynamic
  46.             list.
  47.  
  48. This is currently handled in Pop11, following Pop2, by changing the
  49. *contents* of the record holding the dynamic list. Changing the
  50. type, by changing the key pointer, would be better, allowing faster
  51. checking.
  52.  
  53. Aaron
  54. -- 
  55. Aaron Sloman, School of Computer Science,
  56. The University of Birmingham, B15 2TT, England
  57. EMAIL   A.Sloman@cs.bham.ac.uk  OR A.Sloman@bham.ac.uk
  58. Phone: +44-(0)21-414-3711       Fax:   +44-(0)21-414-4281
  59.