[Date Prev][Date Next][Thread Prev][Thread Next][Author Index][Date Index][Thread Index]

Protocol Reduction: Tuples, Positions, & CoordinateSpaces



In thinking about retiring the old Tuple protocol, I realized that
Tuples are actually used for two very different things: to iterate
over a set of elements (this use to be replaced with iterators), and
as positions in multi-dimensional coordinate spaces.  I believe that
for this latter use iterators are quite inappropriate.  For one thing,
it is wierd to think in terms of iterating through the coordinates of
a position as being *the* interface to a position.  

Also, the superclass "Iterator" doesn't specify that its elements are
actually ordered, only its subclasses do.  It would be a particular
subclass (I think either QueueIterator or RevQueueIterator) which
would be the replacement for Tuple.  On the other hand, Tuple &
PartiallyOrdered are both subclasses of Position.  Clearly, without
multiple inheritance, Tuples cannot be a subclass of both Iterator &
Position without

either 1) Position being a subclass of Iterator, which would be broken
because PartiallyOrdereds (positions in BasicSpaces) are definitely
not Iterators;

or 2) Iterator being a subclass of Position, which would seem broken
because the separate dimensions would only be distinguished by their
iteration order, which wouldn't in general be defined.

Alternatively, one could consider a position in a multi-dimensional
coordinate space to be a side-effect-free integer table.  Let's refer
to a side-effect-free table as a SEFTable, and an integer SEFTable as
a SEFIntTable.  (No, I am definitely not suggesting these as names,
they're awful.  I just need names for now until we figure out what to
call these.)  Let's diagram a SEFTable as:

	{ key1 -> value1, key2 -> value2 }

In that case, a position in a 
	cross (list (basicSpace (cat_Float), basicSpace(cat_PackOBits)))
that we used to diagram as:

	[ Float(2.1), PackOBits("a") ]

would instead be diagrammed as:

	{ 0 -> Float(2.1), 1 -> PackOBits("a") }

In other words, when tuples are used as positions in multi-dimensional
coordinate spaces, we take them not so much to be an ordering of the
component dimensions as a naming of them.  The PackOBits dimension
would be considered as dimension number 1 instead of the dimension
that we encounter second in iteration order.  

Note that in the code, Tuples used as multi-dimensional positions are
typically accessed with the "elem" message, whereas Tuples used to
iterate through a set of objects are typically accessed through
"first" and "rest".  "elem" turns into the SEFTable message "get"
while "first" and "rest" turn into "iterand" and "withoutIt".

However, if we represent multidimensional positions as SEFIntTables,
we've still got our inheritance problem: SEFIntTable wants to be a
subclass of SEFTable & a subclass of Position.  Clearly, a Position
cannot be a subclass of a SEFTable, as a PartiallyOrdered isn't a
SEFTable by any stretch of my imagination.  The alternative, that a
SEFTable is a subclass of Position, is quite interesting.  In fact, I
think it leads to a very elegant and powerful generalization of
Xanadu's notion of coordinate space, altogether with relatively minor
impact on the code (I hope).  All this from constraing the type
distinctions to fit within a single inheritance framework!  (I don't
think there's any general "Single Inheritance Constraint Leads to Good
Generalizations" principle here, but there may be.)

This generalization leads to an mutually recursive definition of
SEFTable & CoordinateSpace.  Recall that for a given SEFTable there is
a CoordinateSpace such that all keys in that SEFTable are Positions in
that CoordinateSpace.  For a SEFIntTable, the CoordinateSpace is
"basicSpace (cat_Integer)".  CoordinateSpaces still come in two
flavors: BasicSpaces (constructed as above), and CompositeSpaces.
We used to compose a CompositeSpace by:

	cross (list (basicSpace (cat_Float), basicSpace (cat_PackOBits)))

I.e., a CompositeSpace would describe itself using a Tuple of
component coordinate spaces (one for each dimension).  Instead, a
CompositeSpace would be composed by:

	cross (sefIntTable (pair (integer(0), basicSpace (cat_Float)),
			    pair (integer(1), basicSpace (cat_PackOBits))))

(Of course, we may redefine "list", or define a new function that acts
like "list", that returns a SEFIntTable instead of a Tuple, in which
case the two expressions above would be equivalent.)

In this case, the dimensions are named 0 and 1 respectively.  The
Position in such a coordinate space that we diagrammed above would be
composed by the expression:

	sefIntTable (pair (integer(0), float(2.1)),
		     pair (integer(1), packOBits ("a")))

In all composite coordinate spaces in which we express the composition
with a SEFIntTable, the dimensions would be named with integers.  If
we express the composition with a SEFTable whose domain is of some
other CoordinateSpace, then it would be positions of that
CoordinateSpace that would be the names of our dimensions.  Let's say
that the pseudo-constructor for SEFTables was parameterized much like
that above for SEFIntTables, except that in addition the first
parameter was the CoordinateSpace of keys into that SEFTable.  Then we
could equivalently write the above examples as:

	cross (sefTable (basicSpace (cat_Integer),
			 pair (integer(0), basicSpace (cat_Float)),
			 pair (integer(1), basicSpace (cat_PackOBits))))

	sefTable (basicSpace (cat_Integer),
		  pair (integer(0), float(2.1)),
		  pair (integer(1), packOBits ("a")))

If we wanted to label our dimensions with PackOBits instead of
Integers, we could just as easily write:

	cross (sefTable (basicSpace (cat_PackOBits),
			 pair (packOBits("X"), basicSpace (cat_Float)),
			 pair (packOBits("Y"), basicSpace (cat_PackOBits))))

	sefTable (basicSpace (cat_PackOBits),
		  pair (packOBits("X"), float(2.1)),
		  pair (packOBits("Y"), packOBits ("a")))

The above transition parallels the evolution of relational database
technology from having a sequence of columns (each column named by a
number in the sequence) to having a set of named columns (each column
labeled by an identifier).

I am content to say for now that version 1 of our system only supports
composite coordinate spaces built from a SEFIntTable type composition
of component (dimension) coordinate spaces, in which case things
always map directly to what we're now doing with Tuples.  It is this
assumption that leads me to expect that we are talking about a minor
modification.  This is simply a special case restriction that we would
now be checking for in order to turn off.  The type hierarchy in our
code will not only allow the generalization later, it will cry out for
it.  I also feel confident that the generalization can be had later
without much pain (as I think I have a trick such that the MDSE only
needs to support compositions of the first kind, and all others can be
transparently mapped onto that).

Note that I have no idea what this generalization is good for.  It
just strikes me as the kind of elegant & powerful construct that, once
available, gets used well for many things.  In any case, given the
above plans for getting rid of Tuples, it would be more complicated to
have kept the code from crying out for this generalization.

Comments?