home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #31 / NN_1992_31.iso / spool / comp / compiler / 2060 < prev    next >
Encoding:
Text File  |  1992-12-22  |  2.8 KB  |  72 lines
  1. Newsgroups: comp.compilers
  2. Path: sparky!uunet!world!iecc!compilers-sender
  3. From: preston@dawn.cs.rice.edu (Preston Briggs)
  4. Subject: Re: Building a Lattice
  5. Reply-To: preston@dawn.cs.rice.edu (Preston Briggs)
  6. Organization: Rice University, Houston
  7. Date: Sat, 19 Dec 1992 18:18:26 GMT
  8. Approved: compilers@iecc.cambridge.ma.us
  9. Message-ID: <92-12-092@comp.compilers>
  10. References: <92-12-083@comp.compilers>
  11. Keywords: theory
  12. Sender: compilers-sender@iecc.cambridge.ma.us
  13. Lines: 57
  14.  
  15. un027705@wvnvms.wvnet.edu (Jon Beck) writes:
  16. >Can anyone point me to an algorithm for building a lattice? I happen to be
  17. >specifically interested in a lattice whose meet is set intersection, whose
  18. >join is set union, and whose partial ordering function is subset, but of
  19. >course that shouldn't matter to the algorithm.
  20.  
  21. I've looked at this question for several days, trying to think how to
  22. answer it.  I don't think it's a sensible question.
  23.  
  24. Computer scientists talk about lattices a lot.  Sometimes people use them
  25. to help reason about problems.  But the idea of implementing a lattice is
  26. harder to get a handle on.
  27.  
  28. A specific lattice has a meet, a join, a partial ordering, a universe of
  29. values, perhaps including Top and Bottom elements.  Note though, that
  30. there's no algorithmic component.
  31.  
  32. In your example,
  33.  
  34.     join is set union
  35.     meet is set intersection
  36.     ordering is subset
  37.     a lattice element is a set of <something>
  38.     top is set of all <something>s
  39.     botttom is the empty set
  40.  
  41. Perhaps you're asking about how to implement the sets and the union,
  42. intersection, and subset operators.  Best to consult an algorithms book,
  43. perhaps 
  44.  
  45.     The Design and Analysis of Computer Algorithms
  46.     Aho, Hopcroft, and Ullman
  47.     Addison Wesley
  48.  
  49. Alternatively, you might be asking about how to declare a lattice type (or
  50. type constructor), perhaps so you can declare many lattices and pass them
  51. around as first-class objects.  In a dynamically-typed language like
  52. Smalltalk (or whatever), you'd basically need an object that took three
  53. functions as parameters: the meet, join, and ordering operators.  In a
  54. strongly-typed language, the problem is much more difficult (and
  55. interesting).  Perhaps it could be done cleanly in Russell; it doesn't
  56. seem to make sense in languages like C++.
  57.  
  58. >it seems as though a compiler for a language which has multiple
  59. >inheritance should have such an algorithm for building the inheritance
  60. >hierarchy, which for multiple inheritance is a lattice.
  61.  
  62. It's also a lattice with single inheritance and no inheritance.  However,
  63. most compilers don't have a reason to explicitly construct a lattice to
  64. handle type resolution or whatever.  Instead, lattices are sometimes
  65. useful to help a language designer reason about the type system of a
  66. particular language.
  67.  
  68. Preston Briggs
  69. -- 
  70. Send compilers articles to compilers@iecc.cambridge.ma.us or
  71. {ima | spdcc | world}!iecc!compilers.  Meta-mail to compilers-request.
  72.