The Loaf Question
What do you do with a working ent?
January 21, 2008 (Updated January 28, January 29, 2008, February 15, 2008)
As far as I know there have been no working ents in the world since the early '90s. Now I've got one, and I'm making it pose for snapshots.
This is the data structure created for the Xanadu® project between 1988 and 1992, and may be the most complex data structure in the world. At the very least, it's fiendishly hard to comprehend by reading the literature and the code. Hence the pictures.
It was designed to hold all the knowledge in the world. You tell it secrets, and they are dutifully stored away in an ever-branching, walking tree of long memory. It knows everything it's ever been told. It knows who told it. And if you change your mind, it remembers both the new secret, and the old, and what parts of the new secret were taken from the old. It remembers if you've combined two or more secrets. It can tell you what secrets contain other secrets, even secrets that have since been changed. It knows what secrets simply refer to other secrets. It knows every revision of everything it's ever been told to remember.
Here is a picture of what gets built when you ask it to store the word "foo." (Click the cropped image to see the whole thing.) I believe this is the simplest possible structure for the ent. An "FeWork" is a "front-end" representation of a work (document).
This time the work was created to read "Howdy doody", and then revised so it reads "Good bye." You can see the bert canopy developing at the upper right and the sensor canopy on the lower right. I'm not sure what to call the thing that's growing in the upper left, but it's part of the canopy as well. (February 15, 2008 update: I no longer think this is a canopy. I think it's the HTrees described here.)
The picture on the left shows a simple stored string, but the canopy has expanded dramatically because another work has been stored which refers to the first.
The one on the right shows the same structure from the point of view of the other work. I think the "boo" off in the left-hand corner is the name of the lock which has been placed on the work. (Just say "boo" to get in.)
Here is a picture of a structure where one work transcludes another. Transclusion is essentially quoting by reference -- the transcluding work actually contains a chunk of the work being transcluded. The DspLoafs indicate a displacement in the range of text being included, and you can see that the same text has been included by two different OVirtualLoafs.
The BeGrandMap, which functions as a sort of global registry for a server. I like how the Ent looks like it's on a walk to a deep, dark forest. This is in fact the only actual Ent object in the entire system, and it hasn't yet been used to store anything, so there's just the one link to the trace canopy. (February 15, 2008 update: I no longer think this is a canopy. I think it's the HTrees described here.)
This one is my favorite. It apparently demonstrates a bug: if E1 = {x -> E2, y -> E3}, then E1 transcluders may be triggered by another separately created Edition containing E1 & E2. So I guess my Ent is actually still broken, after all.
(Added January 28, 2008) Range transclusion, without the canopy. Wherever you see a branch (SplitLoaf, OVirtualLoaf, OPartialLoaf), there is a distinction between regions in the coordinate space. The "myIn" branch is everything within the distinction, and the "myOut" is everything outside the distinction. I believe an OrglRoot represents a particular edition of a work.
About the softwareThe software was built on David Jones' amazing Udanax-Gold2Java project and the JUNG visualization library. I've taken David's work and stripped out dozens of translated classes I deemed unnecessary, and refactored the remaining ones into sensible packages. The original Smalltalk code depended on the ability of one object to "become" a different class, which is not easily done in Java. This prevented the tests on the most interesting part of the code from functioning, so I added a cheesy hack. This thread describes most of the modifications I've made to the translated Udanax-Gold source.
The visualization stuff was this weekend's hack. I wasted half a day looking for something which would provide these kinds of diagrams for a running Java application, and eventually realized that I had to write it myself. The graphing code uses reflection to walk the object tree starting with the object marked "primary" in the diagram. A list of objects visited is kept to avoid infinite recursion. These diagrams were done with a maximum distance from the primary object of 50.
Many objects are not included in the graphs, including Java primitives, flockinfos, caches, sets, arrangements, sequences, regions, spaces, orders, and counters. The nodes are initially arranged randomly with some biases. Bert stuff is shoved to the upper right of the screen, sensors are placed at the lower-right side, and anything marked "canopy" is sent to the upper left. Everything else is placed randomly, then processed by a Fruchterman-Reingold algorithm for up to 5,000 cycles. I then move stuff around by hand until I like it.
I should note that the colors in these pictures aren't precisely right. Sensors are gold, the bert canopy is brown, and that thing in the upper-left corner is green, which I believe are close enough to the traditional colors. However, red is supposed to be for content and blue for history, but I'm not using them consistently here. Neither am I respecting the North-South orientation of the Ent.
(Added January 29, 2008, updated February 15, 2008) The javadoc for this project can be found here, and downloaded as a single file here (5.4 MB zip).
Text and images copyright ©2008 by Gary Teter. All rights reserved. WireHose and the eyeball-and-arrows logo are trademarks of Gary Teter. Xanadu is a registered trademark of Project Xanadu, and is used here without permission. I've been a fan of Ted Nelson's work since his stint as editor of Creative Computing magazine.
