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

*To*: <xanatech>*Subject*: Protocol Reduction: Tuples, Positions, & CoordinateSpaces*From*: Mark S. Miller <mark>*Date*: Tue, 10 Oct 89 13:22:25 PDT

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?

- Prev by Date:
**Weekly Planning meeting, 10/3** - Next by Date:
**Garbage collection & zeroed memory** - Previous by thread:
**Weekly Planning meeting, 10/3** - Next by thread:
**Garbage collection & zeroed memory** - Index(es):