Re: Building a Lattice

un027705@wvnvms.wvnet.edu (Jon Beck) writes:
>Can anyone point me to an algorithm for building a lattice?


Go grubbing around in copies of the JACM from the last two or three years.
Look for an article whose title contains "efficient implementation" and
"lattice operations" in it. (I'm afraid that's the best reference I can
give your; perhaps someone will have better information, or a neatly
organized stack of JACMs close at hand.)


>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.


Ok, but...


>I'm posting here because 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.


You might want to provide a little bit more context here. If you are
really doing your "is subtype of" implicitly, that is


        "I am a foo" = "I do the things a foo can do"


as opposed to


        "I am a foo" = "the programmer said my base type is a foo"


then you have a lattice, but if it is the second choice, then all you get
is a partial order, and not (necessarily) a lattice.


If you are also doing run-time type checking, you ought to verify that the
type system you are using is in fact useful. I think that traveling up
and down in a DAG (or partial order, or lattice) is wrong, for instance.
(I think this because I think that classes should act like black boxes
with defined interfaces, and that their internals should not be affected
by where they are inherited.)


David Chase
Sun
--

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