Structure Sharing and Text Editing

Our structure sharing idea also has a connection with modern text editors! The basic idea is that one can represent edited text by pointing to the original text and indicating how it is to be changed.

We implemented this idea in a text editor in Edinburgh in 1972-3. The original text was kept on disk and the edited text was kept in a doubly-linked chain of records in memory. Each record represented some text and the concatenation of that text represented the edited document. A record represented text either by pointing to a delimited region of text on the disk or by pointing to a character string in memory containing newly typed text.

Using this representation it is easy to implement the basic operations of insert, delete, search, display and save. For example, to insert text at a given point: split the record containing the point and splice in a new record containing the new text.

This idea has three nice features:

When I joined Xerox PARC in 1974, I presented this idea in a technical meeting and it was used by Charles Simonyi in the early implementations of Bravo, which was the precursor of today's WYSIWYG editors. See

The ``Historical Preface'' of the above 1981 tech report gives a brief history.

Our Edinburgh editor, which was like Teco (which we'd used at MIT) but with POP-2 as its command language, was called the ``77-Editor'' because it resided on disk track 77.

[Best Ideas] [Publications] [Research] [Home]