Representing unions of Cartesian products

    > I am looking for an efficient way to store and manipulate unions of
    > Cartesian products.


Sounds similar to object-oriented type lattices to me, with your Cartesian
products corresponding to constructor types at the bottom and abstract or
virtual types forming the unions. I may be way off though.


Take a look at Ait-Kaci et al:
                                        Efficient Implementation of Lattice Operations
                                        Toplas 11(1), 1/89.


    > represents C_1 - C_2. (The operator - denotes the subtraction of sets ...


They also consider relative complements (set difference / but-not). At
least for inheritance lattices (which I tend to visualize as low-degree
except for artificial bottom and top, broad and flat, with few outlyers in
depth), they achieve near O(1) meet, join and relative complement
operations on bit vectors representing compressed transitive closures. A
further compaction called modulation results in O(N log N) space
requirements but may hit efficiency of meet and rel complement depending
on the structure of the lattice.


Heinz W. Schmidt hws@csis.dit.csiro.au
CSIRO, Div Information Technology tel ++61 6 275-0974
and fax ++61 6 257-1052
Aus Natl Univ, Dept Comp Science Canberra, Australia
--

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