Is the list alive?

["David G. Durand" <david@xxxxxxxxxxxxxxxxxxx>]

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/
                                             \__________________________