An Engineer’s Guide to the Docuverse

Introduction

Project Xanadu® is the original hypertext project — the brainchild of Ted Nelson, and the result of careful and passionate work by innumerable clever people over the course of nearly sixty years. Because of the length of its development period, the project has spawned and used many ideas of varying importance, and particularly important ideas have had many names. Because its history spans several eras of computing, ideas spawned by the project that were once considered radical have become commonplace and other ideas that were once commonplace have become forgotten and become radical again. Over this time, most documentation available to the public has been written by Ted, and intended for a non-technical or semi-technical audience.

I had the opportunity to work on Xanadu for five or six years, after spending years as a fan, trying to piece together a general idea of the project from scattered documentation. This gave me the privilege of being able to ask Ted for clarification on both technical and philosophical points, and it also gave me a better view of how different ideas and terms fit into different eras.

Xanadu has a poor reputation in many technical communities. Part of this is due to the popularity of a misleading and in parts factually incorrect 1995 Wired article about the project. However, I consider a larger issue to be the project’s tendency (normal through the 1980s but now very strange) to default to secrecy (even with regard to ostensibly non-secret ideas) and to consider any public release of information in terms of PR. This ultimately meant that most available information was lacking in technical detail or had its technical detail hidden behind a general-audience-friendly front. With a few exceptions (such as Udanax Green / xu88’s FeBe manual), there are no complete, well-organized, publicly-released explanations of Xanadu concepts aimed at engineers. Engineers have, as a side effect, failed to understand how certain ideas fit together and have filled in gaps in the explanation with ideas already familiar to them.

Xanadu concepts are, to a great extent, an alternate (and alien) universe. They were developed earlier than their rough general-computing counterparts in many cases, and are not widely understood outside of the community of former and current Xanadu developers.

I aim to write the guide I would have liked to have been able to read, back before Ted found me and invited me to the project. With any luck, this will clear up some misconceptions, introduce some unfamiliar ideas, and prepare people who are interested in joining the project with enough background to understand the internal documentation quickly.

This document is not intended as an introduction to Xanadu as a whole. In particular, I cannot & will not review the long chronology of the project, although when appropriate I will mention the time period in which something was developed in order to provide context to particular technical decisions. Explaining the historical importance of Xanadu and providing a gentle or gradual introduction to these ideas is also beyond the scope of this document: there is much to be explained and little time, so I will focus on the technical background and assume that readers already have a passing familiarity with Xanadu. For a non-technical introduction and brief chronology, see Ted’s video series Xanadu Basics.

I will be covering only projects I have intimate knowledge of — either from working on them, consulting on them, or immersing myself in their documentation. This leaves large gaps in the chronology (such as xu92 / Udanax Gold), and it means that I cannot adequately cover projects started after 2017 (including the current web-based demo). I will describe a few projects and ideas in passing that I don’t have detailed knowledge of, due to their importance — including OSMIC, xu92, and specialized xu88 enfilade types like the POOMfilade; however, my brief description should not be taken as complete or accurate. I will try to mark these cases clearly.

In some cases, I have independently written open source implementations of some data structures or algorithms developed under Project Xanadu. I will provide links to these when I have them. They are intended as didactic aids — clear examples of implementations — and are often missing optimizations or integrations with other features; they should therefore not be taken as complete or production-ready implementations.

Legal notes

Xanadu®, ZigZag®, and the flaming X logo are registered trademarks. When possible, I will be using the following generic terms: ‘xanalogical’ to refer to a system that incorporates ideas from Xanadu; ‘translit’ or ‘transliterature’ to refer to a xanalogical system for representing hypertext or hypermedia; ‘ZZStructure’ to refer to the underlying data structure and facilities within a ZigZag implementation in the absence of a UI layer.

While I was at one time privy to trade secrets belonging to Project Xanadu, to my knowledge nothing I describe here is subject to currently-live trade secret protection. Furthermore, while I have written code and documentation whose copyright is ceded to Project Xanadu, I am not writing this based on that code and documentation, but instead based on my memories of it. To my knowledge, nothing explained here is secret.

There are several live patents associated with ideas I outline here. Interactive ZigZag interfaces are covered by US262736B1, which was granted in 2001 & so should expire in a few years (while non-interactive ZigZag interfaces are not patent-encumbered at all). Slice intercalation (a means of federating multiple independent zzstructures) is covered by US8682884B2, and is not covered in this document because at the time I worked on the project it was a trade secret; it was granted in 2014. There are two abandoned applications for patents on transpointing windows: one in 2008 and another in 2012; the existence of these applications represents prior art that should ensure that no later patent filed for this technology will be granted. There is an application for a patent on navigable transpointing windows from 2017. And, finally, there is an expired patent on online payment systems. In my experience, the patent status of Xanadu ideas have been no impediment to independent implementation: Ted is generally happy to see his ideas carefully and seriously implemented.

This document is not officially blessed by Project Xanadu, and any inaccuracies are mine. I do not represent Project Xanadu or Ted Nelson.

The aerial overview: key concepts

Work on Xanadu can be divided into two general realms: transliterature, which involves hypertext and hypermedia, and ZigZag, which involves much smaller pieces of data. These realms very occasionally interact (see my section on ZZOGL / FloatingWorld), but for the most part the technologies involved remain separate, and they have distinct and almost contradictory concerns and philosophies.

If we wanted to find a very rough equivalent in the realm of normal computing, transliterature would be word processing while ZigZag would be the use of spreadsheets and databases.

Transliterature, in all its incarnations, involves several concepts missing from or alien to mainstream computing: unique permanent addressing for immutable documents and source data, indirect document delivery, visible connections, and external markup. All of these ideas stem from a single basic idea: the manipulation of immutable sequences of bytes with permanent addresses.

ZigZag’s universe is based around a particular data structure — a generalization of the spreadsheet, wherein a cell can have connections along arbitrarily many named dimensions.

I will focus on transliterature in this document because it has a longer history and more concepts associated with it. It is also what most people associate with the ‘Project Xanadu’ name.

Some effort has been made to develop programming languages that use ZigZag natively, the way spreadsheet formula languages take advantage of spreadsheet structure. There is some discussion here, and here is my contribution to the problem.

Transcopyright

Transcopyright is a concept that gets a lot of push-back from people who don’t really understand what it’s trying to do. I’ll do my best to explain it, with special emphasis on the confusions I have seen.

Transcopyright is a system for monetizing or controlling the distribution of one’s material within a transliterature system. It is not DRM, because it applies to data the same ownership rules that are applied to objects: what one has purchased, one owns in perpetuity, including the right to remix and release remixes.

It is specifically intended to simplify rights negotiations on derivative works, and it uses the same model as RiffTrax: remixers are providing overlay or re-arrangement rules for material already owned by the people downloading the remix. It relies upon permanent addressing for this.

On a technical level, how this works is: when a work subject to transcopyright is published, a one-time pad is generated that is the same length as all the newly-published material in the work. The material is encrypted with that one-time pad, and it is the cyphertext that is published. Anyone can view any span of the cyphertext. Anyone who wants to view a portion of the plaintext must request that portion of the one-time pad from the author or some trusted oracle.

A remix or edit can be downloaded by anyone, but those pieces the viewer doesn’t yet have permission to view will be cyphertext (subject to an ODL entry that blacks it out and provides information about how to purchase the rights to it). One may decide to pay for only the bytes present in the remix. Remixes of things the viewer already owns will not require a second copy.

Once you have a copy of the plaintext, there are no technical mechanisms to prevent you from doing what you like with it. However, etiquette dictates that you do not distribute the plaintext or encryption key beyond a reasonable level, and normal copyright law kicks in at that point. The software itself does not provide the facility to distribute either on your behalf, for material you have not created.

ZZOGL / FloatingWorld

XanaduSpace and XanaSpace use a unique system for handling display, wherein a ZZStructure controls the placement, shape, color, and interaction profile of objects in 3d space. This is called ZZOGL (for ZigZag OpenGL) or FloatingWorld (FW for short).

FW is an extreme form of the ‘property orientation’ model mentioned in the ZigZag section. In it, cells correspond either to object heads (around which properties coalesce) or property values.

Starting from a cell representing the start of the structure (the zzogl head), one dimension represents the draw order. We iterate over objects along this dimension twice. During the first pass, we calculate sizes and locations; during the second pass, we draw using our calculated sizes and locations.

Each object calculates its location with respect to some other object within a location-offset DAG. Its parent’s size in three dimensions is multiplied by a vector of between 0 and 1 (the ‘parentcenter’ — the point on the parent with respect to which we move), we add the delta, and then position it on a point on ourselves (size * center).

pos = parent.pos+(parent.size*(parent.center-parentcenter))+delta-(size*center)

This kind of dynamic relative positioning made it possible to represent relatively complex relationships between objects. We used it to display both transliterature and ZigZag systems.

There were a couple kinds of objects:

• ‘groups’: invisible dummy objects for moving whole groups of objects at the same time
• ‘slabs’: rectangular prisms
• ‘beams’: tetragonal two-dimensional shapes with a solid color
• ‘tetroids’: textured two-dimensional shapes that are shaped like tetris-blocks or paragraphs of text (in other words, a rectangle with at most two smaller rectangles abutting it at top or bottom)

Unfortunately, getting OpenGL to render large quantities of text on top of 3d objects while being responsive enough to edit that text in real time was a difficult problem, and one that we were never able to solve. As a result, XanaduSpace and XanaSpace never had a release.

OSMIC

OSMIC is an alternative document versioning system — a general-purpose journal-based system for tree-based versioning of any byte sequence. Each version is an address in a list of steps. A step can be one of:

• insert bytes at a particular point
• delete bytes from a particular point

A version’s address is, like a tumbler address, a period-separated sequence of numbers. Each time a new version is created, the last number increments. Each time the version tree forks, a new number is added at the end, starting with zero.

While it’s possible to reconstruct a version from scratch by running the journal, it’s also possible to rewind to a particular version by treating every delete as an insert and every insert as a delete. An OSMIC journal can be much larger than the byte string it represents, so a compact representation is important. I am not aware of any work on a compact binary representation of OSMIC journals within Xanadu.

I haven’t worked with OSMIC, but at one time it was suggested that XanaduSpace should be retrofitted with an OSMIC-based system for storing the state and history of the ZZOGL system (and thus, all internal information necessary to display and edit documents).

I have written an open source proof-of-concept implementation of OSMIC. It is not compatible with earlier Xanadu-internal implementations. I have also proposed an alternative high-performance storage system for it.

Transliterature editing

Several systems exist for transliterature editing, some of them released. None of them are, to my mind, satisfying. All are based around selecting and re-ordering spans from existing documents. My implementation is called SPANG and is intended for use with OpenXanadu. XanaduCambridge has a less elaborate, more manual system.

We had pitched a more natural system, wherein selected text could be dragged out of a window to create a new document, or dragged to snap to the end of a document (or to the middle of a document as an insertion) to produce transclusions. We suggested dragging a selected span of text on top of another selected span of text to produce a link between them.

Such a system would require an environment where documents floated and text could be dragged between widgets — in other words, something that the cross-platform graphics libraries we were working with didn’t support.

Formats

On-disk formats (for ZZStructures, EDLs, and ODLs) were constantly in flux while I was at Xanadu. Some were, from my perspective as a professional programmer, abysmal. Most were either based on CSV or key-value pairs. In some cases, they used CSV for mandatory fields and key-value notation for optional fields.

I prefer a subset of YAML or JSON for ZZStructures, because ZZStructures fit that model well. However, since these structures have explicit hierarchy, they were controversial.

Generally speaking, EDL formats have been one line per span, with ordered triples (address, start, end). Whether or not keys are used differs from spec to spec, as does how (or whether) one can specify a whole document without specifying its length.

Generally speaking, ODLs have been lists of addresses pointing to “link” files, and those “link” files contain a type followed by sections called ‘endsets’ that contain one or more spans each. Generally, a link has one or two endsets. If a single endset has non-contiguous spans, the resulting beam resembles a starfish or a hand. I argued in favor of arbitrarily many endsets, each with arbitrary many spans. I also argued in favor of zero-length single-sided links, which I considered to be like bookmarks. I implemented page breaks in XanaSpace as zero-length single-sided links.

There have been arguments over whether or not it is appropriate to support spans that are with respect to the concatext of some document (and if so, how to specify that). Ted has generally been against this feature, and I have generally been in favor of it — both in EDLs and ODLs.

If you’re planning to implement a xanalogical system, compatibility with an existing format will not be a problem: there are no genuine standards, even within the project. However, you should consider the problems mentioned above.