[Date Prev][Date Next][Thread Prev][Thread Next][Author Index][Date Index][Thread Index]
Is the list alive?
- To: udanax@xxxxxxxxxx
- Subject: Is the list alive?
- From: "David G. Durand" <david@xxxxxxxxxxxxxxxxxxx>
- Date: Wed, 26 Jan 2000 15:40:52 -0500
This kind of mail is annoying, but I've received no mail from the
list after the initial acknowledgement.
If there are others working on the code, it would be interesting to
open some dialogue.
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
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
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
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
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
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 Durand dgd@xxxxxxxxx \ david@xxxxxxxxxxxxxxxxxxx
http://cs-people.bu.edu//dgd/ \ Director of Engineering
Graduate Student no more! \ Dynamic Diagrams