How Xanadu Works: technical overview

One particular conversation I’ve overheard several times, often in the context of web and standards development, has always intrigued me. It goes something like this:

You know, Ted Nelson’s hypertext system from the 60′s had unbreakable, two-way links. It was elegant. But then came along Tim Berners-Lee and HTML, with its crappy, one-way, breakable links, and it took over the world.

The general moral of the story is usually about avoiding over-thinking problems and striving for simplicity. This has been rolling around in the back of my mind ever since the first time I heard the story. Is it an accurate assessment of reality? And how exactly did Nelson’s system, called Xanadu (R), manage the trick of unbreakable super-links? Even if the web ended up going in a different direction, there still might be lessons to learn for the current generation of people building things that run (and run on) the web.

Nelson’s book Literary Machines describes the system in some detail, but it’s hard to come by in the usual channels like Amazon, or even local bookstores. One place does have it, and for a reasonable price too: Eastgate Systems. [Disclosure: I bought mine from there for full price. I'm not getting anything for writing this post on my blog.] The book has a versioning notation, with 93.1 being the most recent, describing the “1993 design” of the software.

Pause for a moment and think about the history here. 1993 is 16 years ago as I write this, about the same span of time between Vannevar Bush’s groundbreaking 1945 article As We May Think (reprinted in full in Literary Machines) and Nelson’s initial work in 1960 on what would become the Xanadu project. As far as software projects go, this one has some serious history.

So how does it work? The basic concepts, in no particular order, are:

  • A heavier-weight publishing process: Other than inaccessible “privashed” (as opposed to “pub”lished) documents, once published, documents are forever, and can’t be deleted except in extraordinary circumstances and with some kind of waiting period.
  • All documents have a specific owner, are royalty-bearing, and work through a micropayment system. Anyone can quote, transclude, or modify any amount of anything, with the payments sorting themselves out accordingly.
  • Software called a “front end” (today we’d call it a “browser”) works on behalf of the user to navigate the network and render documents.
  • Published documents can be updated at will, in which case unchanged pieces can remain unchanged, with inserted and deleted sections in between. Thus, across the history of a document, there are implicit links forward and backward in time through all the various editions and alternatives.
  • In general, links can jump to a new location in the docuverse or transclude part of a remote document into another, and many more configurations, including multi-ended links, and are granular to the character level, as well as attached to particular characters.
  • Document and network addressing are accomplished through a clever numbering system (somewhat reminiscent of organic versioning, but in a way infinitely extensible on multiple axes). These address, called tumblers, represent a Node+User+Document+Subdocument, and a minor variant to the syntax can express ranges between two points therein.
  • The system uses its own protocol called FEBE (Front End Back End) which contains at several verbs including on page 4/61: RETRIEVEV (like HTTP GET), DELETEVSPAN, MAKELINK, FINDNUMOFLINKSTOTHREE, FINDLINKSFROMTOTHREE, and FINDDOCSCONTAINING [Note that "three" in this context is an unusual notation for a link type] Maybe 10 more verbs are defined in total.

A few common themes emerge. One is the grandiose scope: This really is intended as a system to encompass all of literature past, present, and future, and to thereby create a culture of intellect and reshape civilization. “We think that anyone who actually understands the problems will recognize ours approach as the unique solution.” (italics from original, 1993 preface)

Another theme is simple solutions to incredibly difficult problems. So the basic solution to unbreakable links is to never change documents.  Sometimes these solutions work brilliantly, sometimes they fall short, and many times they ends up somewhere in between. In terms of sheer vision, nobody else has come close to inspiring as many people working on the web. Descriptions of what today we’d call a browser would sound familiar, if a bit abstract, even to casual users of Firefox or IE.

Nothing like REST seems to have occurred to Nelson or his associates. It’s unclear how widely deployed Xanadu prototypes ever were, or how many nodes were ever online at any point. The set of verbs in the FEBE protocol reads like that a competent engineer would come up with. The benefits of REST, in particular of minimizing verbs and maximizing nouns, are non-obvious without a significant amount of web-scale experience.

Likewise Creative Commons seems like something the designers never contemplated.  “Ancient documents, no longer having a current owner, are considered to be owned by the system–or preferably by some high-minded literary body that oversees their royalties.” (page 2/29) While this sounds eerily like the Google Books settlement, this misses the implications of truly free-as-in-beer content, but equally misses the power of free-as-in-freedom documents. In terms of social impact there’s a huge difference between something that costs $0 and $0.000001.

In this system anyone can include any amount of any published document into their own without special permission. In a world where people writing Harry Potter Lexicons are getting sued by the copyright industry, it’s hard to imagine this coming to pass without kicking and screaming, but it is a nice world to think about. Anyway, in Xanadu per-byte royalties work themselves out according to the proportion of original vs. transcluded bytes.

Where is Google in this picture? “Two system directories, maintained by the system itself, are anticipated: author and title, no more” (page 2/49) For additional directories or search engines, it’s not clear how that would work: is a search results page a published or privashed document? Does every possible older version of every result page stick around in the system? (If not, links to/from might break) It’s part of a bigger question about how to represent and handle dynamic documents in the system.

On privacy: “The network will not, may not monitor what is written in private documents.” (page 2/59) A whole section in chapter 3 deals with these kinds of issues, as does Computer Lib, another of Nelson’s works.

He was early to recognize the framing problem: how in a tangle of interlinked documents, to make sense of what’s there, to discern between useful and extraneous chunks. Nelson admits to no general solution, but points at some promising directions, one of which is link typing–the more information there is on individual links, the more handles there are to make sense of the tangle. Some tentative link types include title, author, supersession, correction, comment, counterpart, translation, heading, paragraph, quote, footnote, jump-link, modal jump-link, suggested threading, expansion, citation, alternative version, comment, certification, and mail.

At several points, Nelson mentions algorithmic work that makes the system possible. Page 1/36 states “Our enfilade data structures and methods effectively refute Donald Knuth’s list of desirable features that he says you can’t have all at once (in his book Fundamental Algorithms: Sorting and Searching)”. I’m curious if anyone knows more about this, or if Knuth ever got to know enough details to verify that claim, or revise his.

So was the opening anecdote a valid description of reality? I have to say no, it’s not that simple. Nelson rightly calls the web a shallow imitation of his grand ideas, but those ideas are–in some ways literally–from a different world. It’s not a question of “if only things had unfolded a bit differently…”. To put it even more strongly, a system with that kind of scope cannot be designed all at once, in order to be embraced by the real world it has to be developed with a feedback loop to the real world. This in no way diminishes the value and influence of big ideas or the place that Roarkian stick-to-your-gunnedness has in our world, industry, and society. We may have gotten ourselves into a mess with the architecture of the present web, but even so, Nelson’s vision will keep us aspiring toward something better.

I intend to return to this posting and update it for accuracy as my understanding improves. Some additional topics to maybe address are: a more detailed linking example (page 2/45), comparing XLink to Xanadu, comparing URIs and tumblers, and mention the bizarre (and yet oddly familiar if you’ve ever been inside a FedEx Kinkos) notion of “SilverStands”.

For more on Nelson, there is the epic writeup in Wired. YouTube has some good stuff too.

Comments are welcome. -m

Xanadu is a registered trademark, here used for specific identifying purpose.

4 Responses to “How Xanadu Works: technical overview”

  1. Dorian Taylor http://doriantaylor.com/

    The bidirectional linking capacity of Xanadu has confused me for some time. I cannot for the life of me imagine how bidirectional links could exist across organizational boundaries. It seems the only way they could happen is through some sort of escrow (which I assume to be Xanadu or its franchisees/licensees). Likewise with enforcing micropayments (of which I assume the big X gets a cut).

    The other thing I found strange was the per-byte pricing. How is the price set? Does it start at parity and change up or down with demand? But it’s data, you can just make more of it (in fact it’s harder not to), so wouldn’t raising the price more than linearly relative to demand be artificial inflation?

    What about the fact that not all symbols are bytes? Do I get a 25% discount if I only fill 6 of 8 bits of every byte? Do I need to pay a royalty to ANSI, ISO or the Unicode Consortium for interpreting bytes as characters? What about Unicode, anyway? Different prices for different encodings? What about other, longer data structures that make no sense if not complete? Could I cheat by requesting content with missing pieces and fill them in heuristically? What about conventional (e.g. GZip) compression? (Sorry, don’t mean to harangue…)

    I haven’t gotten my hands on a copy of Literary Machines or Computer Lib (or Dream Machines, or Geeks Bearing Gifts) yet, so perhaps I’m missing something. I have read the Gary Wolf and other articles, and played with ZigZag demos, and whatever else I could find and manage to run. From the information I have so far though, Xanadu appears as if it is a conceived as a centrally planned and controlled monopoly that gets the last word on content, and I don’t know how good of an idea that is in general.

    If the cost of a decentralized and democratized hypertext system is the enforcement of bidirectional links and micropayments, that seems like a reasonable trade-off. In my experience, the Web’s technological underpinnings don’t completely preclude those behaviours on a voluntary basis. The same goes for hyperaddressability and transclusion (albeit via copying). Otherwise, Nelson’s ongoing jihad on opaque files and strict hierarchies in my opinion is completely sound. Despite that, I cannot perceive what mechanism would insulate Xanadu from moral hazard.

  2. Mark Bernstein http://www.eastgate.com/

    I find this a very fine summary of Xanadu, especially useful because (naturally) the original description didn’t use terms like “browser” that had not yet been invented.

    It’s important to understand that Xanadu assumed one true repository. At the time, it seemed the only way; the idea of a decentralized and democratized hypertext system seemed a fantasy, and even Xanadu’s central storage service and payments strategy was widely dismissed as utopian.

  3. Tweets that mention How Xanadu Works: technical overview | Micahpedia — Topsy.com http://topsy.com/tb/url4.eu/pXbg

    [...] This post was mentioned on Twitter by hrjn_rss, YC Hacker News. YC Hacker News said: How Xanadu Works: technical overview: http://bit.ly/6Ynp97 Comments: http://bit.ly/6l59Zl [...]

  4. uberVU – social comments http://www.ubervu.com/conversations/dubinko.info/blog/2009/11/22/how-xanadu-works/

    Social comments and analytics for this post…

    This post was mentioned on Twitter by hrjn_rss: How Xanadu Works: technical overview: Comments http://url4.eu/pXbg