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

Is the list alive?



This is a repost of my earlier mail, as requested by Roger Gregory. This is a spare time project for me, so I haven't been able to update this at all, but here it is, for what it's worth.


I have made a few resources available (on a relatively low-powered machine in my house):

http://grendel.conlang.org/~dgd/udanax/ is a rough and ready Smalltalk browser created from the export files on the udanax.com web site.

A few of the root classes in the Gold source tree are not present in the distributed files (Object, some others) When you select those classes fromt he TOC, you get a 404. There are only about 5-6 classes missing, so don't let the few broken links discourage you -- there's a lot of code there.

http://grendel.conlang.org/~dgd/green_doc/cxref.html is an HTML cross reference listing created with the free cxref tool. It lets you browse by function and file.

Here's what I've learned and some of the questions that I still have.

I was waiting for more than a decade in anticipation of seeing how Xanadu (now Udanax) actually works. I've not found that the raw source code provides clear and easy answers to that question, although some general features are rather clear. I'd encourage anyone with overview insights to contribute to do so.

My own examination shows that the fundamental "model-T" enfilade appears to be a balanced tree of totally ordered content addresses. The simplest approach to managing such a data structure for multiple versions, with data sharing, is to use a technique that I've always called "copy-to-root". The udanax code instead inserted some sort of node representing a permutation or alteration in place at every ancestor where the child relations change for a given version. I believe that these "node-level diffs" are called "orgls", but can't quite tell.

The loaf/crum management is a basic explicitly managed virtual memory, with in memeory use-counts managed in the code. Link management is based on a "2-D" enfilade which seems to manage starting points and widths of linked areas, with linked lists of pointers to the original data in the I-stream.

Again, any verification of this stuff would be welcome.

The Smalltalk code is more scrutable, but also more ambitious. It seems to contain a certain amount of dead code, as well as many classes for process management and the like that are not so closely related to the fundamental algorithms (at least the pure data management ones).

The key generalization seems to have been to generalize the original algorithsm. The original code seems to be very specialized to the management of permutations (+ insertions + deletions) of a total ordering, as that ordering changes to create multiple versions, as well as to the efficient location of sequence elements in arbitrary states of that sequence based on a fundamental identity (i-stream address).

In the generalized code, the sequence is replaced by an arbitrary address space, which can be any algebraic structure (set of items with significant relations between them). Contents are associated directly (by identity) with elements of the address space by a mapping. Operations are represented by transformations (or complete replacement, or incremental replacement?) of the address->data mappings. This means that handling n-d (and indeed arbitrary) topologies can be handled uniformly within a single structure. I assume that this structure is the fabled Ent.

I don't quite understand how WIDativity and DSPativity are used to enable the efficient creation of compositional maps for this. I get lost in the code, but the Ent seems to be a hierarchical representation of a series of maps. The top level represents large scale rearrangements, and yields a precise state when composed with the smaller scale maps whose results form its input. Such a composition is a way to retrieve a single state of the base address space. However, there must be an efficient way to select from alternative maps at each level, so that a particular state can be selected.

This might be a big tree, with hashtables at each node, with elements of the hashtable being alternative maps for that node, keyed off of the version identifier of a given state (a Bert, right?).

Any insights into this would be appreciated.

  -- David

--
_________________________________________
David Durand              dgd@xxxxxxxxx  \  david@xxxxxxxxxxxxxxxxxxx
http://cs-people.bu.edu//dgd/             \  Director of Engineering
    Graduate Student no more!              \  Dynamic Diagrams
--------------------------------------------\  http://www.dynamicDiagrams.com/
                                             \__________________________
_________________________________________
David Durand              dgd@xxxxxxxxx  \  david@xxxxxxxxxxxxxxxxxxx
http://cs-people.bu.edu//dgd/             \  Director of Development
    Graduate Student no more!              \  Dynamic Diagrams
--------------------------------------------\  http://www.dynamicDiagrams.com/
                                             \__________________________