Re: Presentation on Xanalogical Data Structures

[Jeff Rush <jeff@xxxxxxxxxx>]

Hi Steve.  Glad you enjoyed the slides.

On Mon, 2004-08-09 at 14:58, Steve Witham wrote:
> Jeff--
> 
> Thanks for the PDF of your slides.  I just got back from a conference
> in Toronto.
> 
> I would like to see a presentation of your zoomed-out, larger-scale
> stuff, the data block server, etc. someday.

Alright, I'll work toward producing something.  Feedback so far has been
people are more concerned with seeing it all run than learning the nuts
and bolts algorithms.


> Some things to fold into your presentation if you ever give it
> again, or maybe into your own archaeological work:
> 
> 1) I have a picture (enclosed) that shows the idea of Xanadu as
> virtual documents implemented as mappings into shared "stuff".
> Then it shows how you can follow a link that was made to an old
> document into a new version of the document, because you follow the
> link mapping into the stuff, then follow the backwards mapping from
> that stuff to the linked-to document version.  This is a very important
> thing that the Xanadu implementations made possible: having versions
> and fine-grained links that work together.

Is that drawing one of yours or something you found of the original
Xanadu team?  Yes, once I have enfilades and I/V streams implemented,
this is an exciting area of study.

> 2) Xanadu was not intended just for plain, un-marked-up text.
> I think you're confusing what someone was saying about an implementation
> point, which is this: Xanadu holds the plain, unmarked text in one
> place, and the markup in a completely separate place: links that point
> into the main text and say this span should be bold, italic, a certain
> font, color, or whatever.  Also, they concentrated on storing plain text
> and links, figuring they would assign exact link types for text
> attributes later.

I spoke imprecisely; I should have said *embedded* markup.  I knew they
intended to use links for such and I've put together a few notes.  I've
got a link type for "presentation", with subtypes for font, face, color,
etc.  And then a link type for "organization" for sections, chapters,
paragraphs, headers, titles, etc.  And probably another forking link
type for representing conventional MIME types.

And I plan on having a XHTML <==> Xanadu Links converter, so that when a
document is exported from Xanadu, it is delivered as marked up XHTML. 
And vice versa for importing.

> 3) I think between bignums and tumblers, there is a middle category
> called multihumbers or something.  These are the transfinite numbers.
> Tumblers have the zeros in them, marking off the main parts
> (server.0.user.0.document.0.position), and they don't follow
> transfinite arithmetic at those divisions.  They are really just a
> way of representing tuples of transfinite numbers, tuples with
> fixed numbers of parts, like four.

I really need to google for a good reference on transfinite numbers. 
I've just been lazy, figuring my tumbler understanding is sufficient for
what I need at the moment.

> 4) The presentation could use pictures of a tree insertion, deletion,
> rearrangement and copy, noting that the addresses of the characters in the
> unchanged subtrees all change, but that that's okay because of the
> way addresses are dealt with.  A picture of rearrange really gets the
> idea of enfilades across, I think.  Having the same section repeated
> twice in one document, but sharing the same subtree, i.e., copy, also is
> impressive (to me).

Producing simple diagrams that express complex ideas is hard, but VERY
valuable in this project.  I'm working on creating such.  I bounce back
and forth between code development and documenting/presentation.  The
book _Literary Machines_ has some falsehoods about tumblers, such as
that there is no use for negative values.  Green uses those for WIDs in
lots of places, especially along the secondary axis for 2-dimensional
enfilades where you can't avoid them (ie. if you order a 2-d mapping by
one of the dimensions and allow arbitrary mappings, there are bound to
be times when the second dimension is not in increasing order).

> 5) A picture of a permutation enfilade as a graph that starts out a
> straight line, but then gets rearranged, would be good.  The fact that
> this uses a 2D enfilade to do the same thing as the original 1D
> enfilade that you described (as I would too) is a little funny, but
> the thing that the permutation enfilade adds is that you can follow
> it backwards from stuff (istream) address to position in the virtual
> document (vstream).

Such a picture would be useful and I appreciate the suggestion.  I've
created a pencil drawing where I bend the tumbler line 90 degrees, so
that the V-stream is horizontal and the I-stream is vertical, with a
POOM relating the two.

http://www.sunless-sea.net/Sketches/stream_sketch.gif

I haven't totally figured out -where- the V-stream and I-stream reside
on the tumbler line, whether within versions or in the subflooring
between versions and documents.

> 6) You seem a little unsure on orgls and istream.  Orgles are used for
> two things: documents and links.  That is, each document, and each
> link, is represented by an orgl.  In fact, documents and links are
> exactly the same thing except where they live in the address space
> and how they're used.
> 
> The basic idea is that Xanadu maps server.0.user.0.document.0.position
> addresses to stuff.  But in detail, it's like this: internally, each
> new document (orgl), link (orgl) or character gets an istream address.
> Then the granfilade maps istream addresses, of both orgls and
> characters, to physical locations.

Yes, I've got that documents are empty POOMs hanging off the granfilade,
and characters are static chunks hung off the granfilade in the I-stream
subintervals.  Links I wasn't sure of yet.

> The fact that orgls have istream addresses means that links can refer
> to documents and links themselves, and not just to their contents.

Links within the spanfilade seem to have an extra integer stuck onto the
front of their tumbler address, in one case the digit 4.  I suspect it
is either an endpoint id, or some internal indicator of link kind (not
type, I know that is an endpoint itself).

> The mapping from document ID (server.0.user.0.document) to istream
> address must be by a convention where the one space just maps straight
> into a section of the other.  The document orgls are what map
> the link-orgls' positions in v-space to i-space.

Orgls *seem* to be POOMs but sometimes they appear to be conceptually
more.  To be precise, orgls are where in the coordinate space POOMs
suspend from (ie. leaves on the granfilade), not the POOMs themselves
right?

> Anyway, by convention, all the stuff mapped (by a document's orgl) at
> the beginning "half" of a document is
> characters, and all the stuff in the second half is orgls,
> representing links.  Inside link-orgles there can be both characters
> and other orgles, depending on what the link is for.

How is the "half" represented?  Literally a '5' digit in the tumbler
delineating a separate subinterval or something else?

> 7) The spanning enfilade assists in the backwards-mapping part of link-
> following and finding.  The problem is that the v-to-i mapping is many
> to one: many documents, versions, links, even places in the same document,
> can link to the same character.  The information to follow the mapping
> backwards is in the orgls, but if you only want to find links from
> one document to text in another document, you have a potentially huge
> search on your hands: follow every character to its istream position,
> then follow that back to every place it's used.
> 
> The spanfilade ignores the ordering of stuff mapped by orgles, and just
> treats it like sets.  Then you can intersect the set of stuff contained
> in the target document, with the set of stuff linked to by the linking
> document, and you get a much narrower collection of span-orgl pairs
> that need to be traced backwards using the permutation enfilades.

The spanfilade is still a mystery to me.  I've focused on the text
rearrangement portion so far, and am about to dive into the links side.

> Not sure whether, if you want to search based on all the stuff linked-to by a
> document, it's all mapped by the document's top orgl, or do
> you have to look at what's mapped by its collection of link orgls?
> Maybe they originally get a continuous range of istream addresses, but
> as you modified the document that would change...
> 
> AFAIK, FWIW, YMMV!!!!
> 
>   --Steve

Definitely magic stuff.  One question - in explaining all of Xanadu, say
in a book or presentation, would you start at the top and work down to
the details, or start with the details and assemble the architecture
piece by piece?  As you see in my presentation, I've been teaching from
the bottom up but I find I lose students who lack the understanding of
why we are doing all this.  But I don't yet have a cool GUI demo to
excite them.  On other projects, I find I personally learn better from
the bottom up, so that things don't seem so magical at the top.  But
then I'm a detail-oriented person.  Learning computers it was easier for
me to learn address spaces, CPU caches, etc. first, then work up to
operating systems, applications and GUIs.  But I can see how someone
interesting in GUI design can be really bored learning about address
spaces, even though they'll need some conceptual basis to understand
segmentation faults, wild pointers and such.

I've also been trying to produce something like the seven-level ISO
diagram of the Xanadu Green architecture, so I can break down a
presentation into digestible chunks.  My recoding efforts have been
working from the bottom up too.

+---
| links
+---
| docs, versions
+---
| SPANs, ORGLs
+---
| I, V streams
+---
| granfilade
+---
| DSP/WID/enfilade trees | tumbler math
+---
| CRUMs, LOAFs, subtree persistence
+---

Basically a roadmap of the concepts that need to be learned to
understand Xanadu fully, similar to how the TCP/IP protocol tends to be
taught.

-Jeff Rush