EnfTheory-D10 === 17.10.19 ENFILADICS: Enfilades and General Enfilade Theory by Theodor Holm Nelson and Mark Miller === PART ONE: PREAMBLE (by Nelson) (I have just noticed that Wikipedia has much more about this than I imagined, which overlaps with the following. I have not tried to make this consistent with that article, which should also be studied.) This is the first publication of general enfilade theory, which allows the construction of special-purpose storage trees for complex data. The story begins with the first enfilade of 1970, then the generalization of the concept in 1979 and later by the Xanadu® team of Gregory, Miller, Green, King and Hill. I invented the first enfilade around 1970, working with Cal Daniels on what might have been the first commercial word processor, had we finished. (See story in POSSIPLEX.) Calling it an "enfilade" was a pun: that was French for "in a file", and also military parlance for an efficient way of shooting at soldiers. The first enfilade was a tree structure for editing text. Our very small computer of 1970 could not hold the text in main memory; the text had to be in external storage. The user saw only a small part of the text, found and presented as needed. Instead of manipulating the text in the computer itself, the text was rearranged by a system of pointers. That was the enfilade. Thus the first enfilade, which we later called the Model T, is an editable tree for sequential content (such as text or movies). (This was also a pun, T for Text and "Model T" meaning the ancient Ford car that began the modern era). Here were its main operations: - FINDING THE Nth CHARACTER. Each node of the tree had a number summing the number of characters beneath, so the nth character could be quickly found below. - CUTTING THE TEXT. If you had to cut the text (for insertion, deletion or rearrangement), the pointer to that text was split. - REARRANGING. You could switch the elements of the tree, rearranging the text. - INSERTION. New text typed by the user was always appended to a single growing block in external storage, and a pointer to that new text was inserted in the tree wherever that new text was supposed to go. In the summer of 1979 I explained this to the Xanadu team, and they generalized it, discovering that special enfilades could be built in various ways. Their insights they called General Enfilade Theory, unpublished until now, in this note. These findings were used in the design of Xanadu Green (formerly called xu88) and another version of the Xanadu concepts, Udanax Gold, which will not fit in this discussion. === PART 2: GENERAL ENFILADE THEORY (by Miller) An enfilade is a tree structure for managing data. The Model T enfilade was one-dimensional, referring to a long row of text characters. But enfilades can be generalized into broader capabilities. An enfilade has two special mathematical properties: upward summation, called WIDative (for widths of content); and downard imposition, called DSPative (for displacement of content). DSPative properties are the dual of WIDative properties. The wids are summaries of the information below them in the tree, such as a bounding box around a bunch of shapes. The dsps displace, alter, transform, twist how the information below it in the tree is interpreted, such as a transformation matrix for scaling, rotating, and displacing graphics or shapes below that node in the tree. In the Model-T, the wids were literally widths. The dsps were encoded implicitly as the sequence of the children of a given node. Enfilades can be generalized to any "spaces" characterized by these mathematical relationships, many of which are not literal geometric spaces. The next big insight is that the wid and dsp functions are associative and reversible. This means that you can rebalance the tree as you like without affecting its meaning. The 1979 design (then called xu88, now called Xanadu Green) used this freedom for b-tree-like balancing, keeping the worst case log-like. To return to our graphics example, bounding boxes are associative, as is matrix multiplication. You can reversibly move a wid through a dsp. So the tree of graphics objects can be rebalanced independent of any separate part-whole hierarchy. =30=