home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #26 / NN_1992_26.iso / spool / comp / lang / misc / 3617 < prev    next >
Encoding:
Internet Message Format  |  1992-11-12  |  5.6 KB

  1. Path: sparky!uunet!know!cass.ma02.bull.com!think.com!ames!elroy.jpl.nasa.gov!swrinde!emory!sol.ctr.columbia.edu!hamblin.math.byu.edu!hellgate.utah.edu!lanl!cochiti.lanl.gov!jlg
  2. From: jlg@cochiti.lanl.gov (J. Giles)
  3. Newsgroups: comp.lang.misc
  4. Subject: Re: Pointers
  5. Message-ID: <1992Nov12.200950.8846@newshost.lanl.gov>
  6. Date: 12 Nov 92 20:09:50 GMT
  7. References: <1992Nov4.093545.15950@rdg.dec.com> <Bx7oAz.7Lp@mentor.cc.purdue.edu> <1992Nov5.014143.15635@newshost.lanl.gov> <id.6HVU.OC@ferranti.com>
  8. Sender: news@newshost.lanl.gov
  9. Organization: Los Alamos National Laboratory
  10. Lines: 99
  11.  
  12. In article <id.6HVU.OC@ferranti.com>, peter@ferranti.com (peter da silva) writes:
  13. |> In article <1992Nov5.014143.15635@newshost.lanl.gov> jlg@cochiti.lanl.gov (J. Giles) writes:
  14. |> >    First: in both, you should avoid having loops.  In the case of GO TO,
  15. |> >    you should try not to branch backward.  In the case of pointers, you 
  16. |> >    should try to avoid cyclic data structures.
  17. |> 
  18. |> If you think I'm going to give up doubly-linked circular lists because you
  19. |> don't like pointers, you've got another think coming.
  20.  
  21. Ok, give it to me.  You claim I've got it comming, so let's have it.
  22. I collect them you know.
  23.  
  24. Seriously, I'm glad I don't have to maintain your code.  I only
  25. use such things as circular lists when they are the best choice
  26. available - which is almost never.  Yes, I sometimes use them.
  27. But they require extra work (because you can't tell, when traversing
  28. the list, whether you've reached the end of it without additional
  29. information that is not *locally* contained in the list).  They
  30. also have some practical drawbacks by making reference counting
  31. garbage collection schemes much more complicated (so much so that
  32. they are usually abandoned).  Now presumably your circular lists
  33. are at least constrained to have the *whole* list within the cycle.
  34. If you don't do that, then I'm *really* glad I don't have to work
  35. with your code.
  36.  
  37. Lists are somewhat less difficult to allow to cycle than trees
  38. or arbitrary graphs (though the latter *need* to cycle more often).  
  39. If I have to support arbitrary directed graphs, I don't use raw 
  40. pointers at all.  The decreased legibility and reliability of such 
  41. an implementation is not acceptable.  I *may* use pointers *inside* 
  42. the implementation for efficiency reasons, but all the operations 
  43. on them will be handled through an interface which imposes a better 
  44. visible structure on the data.  
  45.  
  46. For example: the graph G is defined as G(V,E), where V is a set of
  47. vertices (which might contain data of some type) and E is a set of
  48. edges.  The set of edges consists of ordered pairs of vertices:and
  49. maybe some information of some data type (since edges and vertices 
  50. are duals of each other, both may be associated with data).  That's 
  51. the *logical* appearance of them, internally they may be implemented 
  52. as pointers between the vertices - however, that implementation is 
  53. irrelevant and can be replaced with other possibilities should more
  54. efficient means for a *given* problem become apparent.
  55.   
  56. All this gives a structured data type to which the theorems and 
  57. algorithms of graph theory can be applied directly.  If I had used 
  58. pointers as my "surface level" implementation, the application of 
  59. graph theory would have been obscured by the pointer manipulations.
  60.  
  61. Not only that, but if a more efficient implementation becomes 
  62. apparent (like storing the set of vertices as a contiguous 
  63. sequence instead of a linked list - more efficient if deleting
  64. and inserting vertices is rare), *if* such a decision is made,
  65. the explicit pointer implementation *you* recommend would have
  66. to be completely rewritten in detail.  All *I* have to do is replace
  67. the access functions (or macros, or whatever abstraction method
  68. I use).
  69.  
  70. |> [...]
  71. |> OK, I'll throw away all my generic symbol table code because it's
  72. |> politically incorrect. Not.
  73.  
  74. I could care less what you do.  I don't have to suffer through
  75. your code.  If you prefer tinkering with arcane sequences of
  76. confusing code, that's your business.  I prefer to write algorithms
  77. which visibly resemble the graph theoretic concepts they implement.
  78.  
  79. My recommendations are just that: recommendations.  If you choose
  80. to follow them, fine.  If not, fine.  Political correctness consists
  81. of more stringent measures: like censorship or the attempt to *force*
  82. others to conform.  I engaged in neither of these.  In fact, I consis-
  83. tently oppose people who recommend actions which *force* others to
  84. conform.
  85.  
  86. So, I will repeat my recommendations in a different form: use pointers
  87. as little as possible; when you have to use them, conceal them under
  88. an interface which implements the *exact* semantics you have in mind;
  89. *NEVER* access your data except through the interface; *IF* a section
  90. of code is found to be a time-critical element then you can expand
  91. your interface routines in-line for better efficiency - but the
  92. code should be written and debugged before you do so.  You should
  93. end up using *raw* pointers as seldom as you use *raw* GOTOs.
  94.  
  95. |> [...]
  96. |> As for your analogies, an analogy is like instant coffee.
  97.  
  98. C.A.R. Hoare proved that the concepts of pointers and GOTOs are
  99. *isomorphic* - which is a lot stronger than a mere analogy.  The
  100. consequence of this observation is that *any* valid argument against
  101. GOTOs is equally valid against pointers.  Period.  As I keep saying,
  102. you cannot do any coding at all without GOTOs, it's just that most 
  103. of the ones you use are hidden under an interface (IF/ELSE, DO/ENDDO,
  104. SELECT/CASE, procedure calls, etc.) which capture the *specific* semantics
  105. of the flow control the user has in mind.  The same kinds of interfaces
  106. need to be designed and applied to data structures to eliminate *raw*
  107. pointer instances.
  108.  
  109. -- 
  110. J. Giles
  111.