Re: Building a Lattice

chased@rbbb.Eng.Sun.COM (David Chase)
Fri, 18 Dec 1992 21:13:04 GMT

          From comp.compilers

Related articles
Building a Lattice (1992-12-15)
Re: Building a Lattice chased@rbbb.Eng.Sun.COM (1992-12-18)
Re: Building a Lattice (1992-12-19)
Re: Building a Lattice (1992-12-22)
| List of all articles for this month |

Newsgroups: comp.compilers
From: chased@rbbb.Eng.Sun.COM (David Chase)
Organization: Sun
Date: Fri, 18 Dec 1992 21:13:04 GMT
Keywords: theory
References: 92-12-083 (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

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

Post a followup to this message

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