Re: Building a Lattice

un027705@wvnvms.wvnet.edu (Jon Beck) writes:
>Can anyone point me to an algorithm for building a lattice? I happen to be
>specifically interested in a lattice whose meet is set intersection, whose
>join is set union, and whose partial ordering function is subset, but of
>course that shouldn't matter to the algorithm.


I've looked at this question for several days, trying to think how to
answer it. I don't think it's a sensible question.


Computer scientists talk about lattices a lot. Sometimes people use them
to help reason about problems. But the idea of implementing a lattice is
harder to get a handle on.


A specific lattice has a meet, a join, a partial ordering, a universe of
values, perhaps including Top and Bottom elements. Note though, that
there's no algorithmic component.


In your example,


join is set union
meet is set intersection
ordering is subset
a lattice element is a set of <something>
top is set of all <something>s
botttom is the empty set


Perhaps you're asking about how to implement the sets and the union,
intersection, and subset operators. Best to consult an algorithms book,
perhaps


The Design and Analysis of Computer Algorithms
Aho, Hopcroft, and Ullman
Addison Wesley


Alternatively, you might be asking about how to declare a lattice type (or
type constructor), perhaps so you can declare many lattices and pass them
around as first-class objects. In a dynamically-typed language like
Smalltalk (or whatever), you'd basically need an object that took three
functions as parameters: the meet, join, and ordering operators. In a
strongly-typed language, the problem is much more difficult (and
interesting). Perhaps it could be done cleanly in Russell; it doesn't
seem to make sense in languages like C++.


>it seems as though a compiler for a language which has multiple
>inheritance should have such an algorithm for building the inheritance
>hierarchy, which for multiple inheritance is a lattice.


It's also a lattice with single inheritance and no inheritance. However,
most compilers don't have a reason to explicitly construct a lattice to
handle type resolution or whatever. Instead, lattices are sometimes
useful to help a language designer reason about the type system of a
particular language.


Preston Briggs
--

Return to the comp.compilers page.
Search the comp.compilers archives again.