Set & Table hierarchy

[Ravi Pandya <ravi>]

A number of things bother me about the class hierarchy we worked out
yesterday. Here is a revised class hierarchy, with the following
changes (discussed in detail after):

	(1) All sets and tables are enumerable

	(2) Scrutables have no protocol to change state

	(3) Immutables are subclasses of scrutables

	(4) All actual implementations are mutable subclasses

	(5) Regions and Dsps are immutable by definition

Heaper

	ScruSet<Heaper> :: count() stepper()
		isEmpty() hasMember(x) isSubsetOf(s)
		mutable() immutable()

		ImmuSet :: unionWith(s) intersect(s) minus(s)
			with(x) without(x)
			scrutable() mutable()

		MuSet :: unionWith(s) intersect(s) minus(s)
			with(x) without(x)
			scrutable() immutable()

			HashSet, DiscreteRegionSet, ...

	Region<Position> :: isEmpty() hasMember(x) isSubsetOf(r)
		unionWith(r) intersect(r) minus(r)
		simpleRegionAt(x) simpleRegions() isSimple()
		regionType() simpleUnion(r) [was superUnion]

		DiscreteRegion :: count() stepper(order = NULL)
			with(x) without(x)
			asMuSet() asImmuSet()

			Integer intervals <1, ... 10>

			Real sequences <1.0, 1.5, ... 5.0>

		Rectangles [0.0, 1.0] X [3.0, 5.0]

		Spheres { |foo - (1.0, 1.0)| < 3.5 }

	Predicate<Heaper> :: is(x) and(p) or(p) not(p) implies(p)

		And, Or, Not, etc.

		Filter criteria for backfollows and such

	ScruTable<Position,Heaper> :: count() stepper(order = NULL)
		fetch(x) get(x) hasKey(x)
		domain() domainType() runAt(x) runs()
		mutable() immutable()

		ImmuTable :: store(x,y) copy(region) occlude(table)
			scrutable() mutable()

		MuTable :: store(x,y) copy(region) occlude(table)
			scrutable() immutable()

			HashTable, Array, ...

			TableView, CompositeTable
			[should these be subclasses of Scrutable instead?]

	Dsp<Position> :: of(x) of(region) compose(dsp) minus(dsp) regionType()

		Transforms that take simple regions onto each other

		Composite transforms

ISSUES:

(1) The ImmuSet class in the previous message is really Predicate,
since with a non-enumerable set, all you can do is test for
membership.  Having the abstract superclass doesn't get us any useful
polymorphism: Region->union(Region) should be a Region, and
ESet->union(ESet) should be an ESet, etc.

We could put Sets and Regions under Predicate, and Tables and Dsps
under UnaryFn, but again I don't think that having the abstract
superclass gets us any useful polymorphism. It would also mangle the
names of set combination messages. (and=intersect, implies=subset, ...)

(2) Note that scrutables don't have any protocol for changing
themselves.  In order to do so, you have to make a decision as to
whether they are going to to be mutable or immutable. I would like to
hear what you think about this policy.

(3) The complete separation of immutables from scrutables & mutables
was due to MarkM. He felt that immutables are purely mathematical
objects, while the uses of S&M's are bound to be dominated by the fact
that they have state. The former would be used when the important issue
is membership, the latter when the issue is reference or containment
(as in dependency models).

I find that the original argument for having immutables and mutables
be subclasses of scrutable is still compelling. I think that this is a
case where the abstract superclass really does buy you something. Both
mutables and immutables can take scrutables as arguments to messages
like intersect(), since all they need is to be able to find out the
contents of the other object.

(4) Clearly, we don't want to have three different implementations of
every kind of Set & Table -- scrutable, mutable, and immutable. MarkM
suggested implementing mutables in terms of immutables with the use of
copy-on-write. This is counter to my intuition that the basic
implementation should be mutable, since that is most efficient.

You can make a scrutable out of a mutable by simply casting it to the
superclass, thereby hiding all the protocol to change it.

If an immutable can know that it is the only one pointing at its
mutable, and that there is only one pointer to itself, then it can
simply change the mutable. Otherwise, it makes a copy of the mutable,
changes it, returns a new immutable pointing to that.  I don't believe
that this runs into any of the immediate finalization problems that
the other copy-on-write scheme does.

Thus scrutables are pure abstract classes, and ImmuTables and ImmuSets
are concrete leaf classes holding onto a mutable. All actual
algorithms and data structures are in mutable subclasses.

(5) Dsps and regions are defined to immutable and have copy-on-write
built into the algorithms. This corresponds to what I think will be
the actual usage, both formally (they are mathematical objects) and
practically (they will be used a lot, so efficiency really matters).


Well, I think that is enough for one mail message. The next one will
about the issues that are still unresolved. There aren't many!
	--ravi