NOTE: (June 2018): the article below describes the situation as of mid 2017. Experiments with this an approach as in this article may be found in “nerf0”. The current situation differs in at least 3 ways from the one desribed in this article. [1]: in the present version of the project “replace” has been replaced with “extend” (which may only extend history, rather than replace with an arbitrary history; [2]: The notes “insert” and “extend” may take only a single child note; [3]: notes are now denoted using an s-expression rather than the Pythonic notation in the below.

The proposed alternative is to make changes to programs the primitive building blocks, instead of the programs that result from such changes. In this view, the means of construction are seen as equally important as the constructed artifacts. The idea is simply that, to be able meaningfully to reason about change, it is easier to keep the actual change at hand than to guess what it might have been.

The decision to abandon text files as a possible input format has an important consequence for the roadmap of this project: editors that create text files are plentiful, but the type of editor that could be used to create changes as a primitive has yet to be designed. The first step in the project is therefore to design and implement such an editor.

This will allow us to get some feedback on what works and what doesn’t, and on what the major challenges for such an editor are.

Also, importantly, it will allow us to actually create the inputs for the yet to be designed programming language.

In the below, we will sketch some important properties of such an editor.

Means of combination

The first goal for our editor was mentioned already: the changes to programs shall be primitive entities in our editor. The second goal is that it shall be possible to combine these primitives in meaningful ways.¹

The most straightforward such combination is to take of a linear sequence of such changes; we’ll call this a “history”.

A more subtle means of combination arises when editing hierarchically structured documents, such as computer programs. Hierarchical documents, by definition, compose larger parts out of smaller parts. This leads to the question: how do the histories of the parts relate to their sub-parts?

For the editor presented below, the answer is: the histories between relate in a meaningful way. In particular, the history of some part of our program will be composed of the histories of its subparts.

Structured editing

In the above we’ve established three things: first that we need to create an editor for computer programs, second that changes shall be its primitives and third that histories of changes shall be meaningfully composable along the lines of the document’s structure.

These goals point strongly in the direction of a structured editor, meaning an editor that is aware of the document’s structure. There are two main reasons for this:

1. To establish a good inventory of primitive operation of change: If we would treat the structure of the edited document as a black box, we could not say anything meaningful about changes to it. We must thus take the opposite approach and acknowledge the document’s structure.

2. To be able to compose and decompose histories along structural lines — that we need to acknowledge the document’s structure to be able to do this should be obvious.

Incidentally, structured editing brings with it many other advantages: certain classes of incorrect programs cannot be constructed, there is no need to write a parser, meaningful reporting on errors is much easier etc. etc. We shall gladly make use of such advantages, but they are not the initial cause for the decision.

Finally, note that the decision to create a structured editor rather than an unstructured one incurs no extra cost on our implementation. Because a radical departure from the main paradigms of text editing is the starting point of our design, we are free to drop any defaults from that paradigm, such as the fact that everything is unstructured text.

Structure: S-Expressions

So far we have established that the editor to be is to be a structured editor and that its primitives will be the changes to some structure. Now then, before we can turn our attention to those primitives, we must first decide what that structure looks like.

For the first prototype, I have decided on the simplest thing that could possibly work: s-expressions.

S-Expressions are

• an atom (some symbol or value), or
• a list of 0 or more s-expressions²

With these two types of elements we can build tree like structures with at the leaves either empty lists or atoms.

The primary motivation for picking such a minimal syntax is a practical one: the scope of the project is rather large as it stands and a programming language family which is expressed in S-Expressions is readily available (Lisp).

From a usability perspective, S-Expressions are also desirable. There are only two kinds of S-Expression (atoms & lists) and the mapping between S-Expressions and their visual representation is very straightforward. Since the structure of the program is readily visible, the programmer needs not create a separate mental model of it in their head; this makes structured editing feasible.

Most advances in programming language research in the last few decades, most notably in type systems, have been made in ML and its derivatives. To be able to incorporate those while retaining elegance an upgrade to a less minimal syntax may be required at some point. However, for the first version of the editor a minimal syntax is sufficient — the focus on change as a primitive will yield sufficient insights to make the experiment worthwhile.

A Clef for Construction

Having established what the structure of our documents will be, we can turn our attention to the primitives of construction. In other words, we’ll have to decide on a set of operations to construct and modify S-Expressions. We’ll call such a set of primitives a Clef³.

This is just as much a design decision as picking the syntax of the language in the first place. Here too, the space from which we can choose is infinite.⁴ The forces working on this decision are similar too; they are roughly:

• Adding more elements to the clef potentially allows for more precise descriptions of history and expressions of intent (good).
• Adding more elements imposes an implementation cost (bad).
• Adding more elements imposes a mental burden on the programmer (bad).
• Adding more elements increases the risk that multiple equivalent mechanisms exist to construct the same result, even in cases when there is no meaningful underlying reason for this (bad).

In the below I will present a particular clef as decided upon (for now); leaving the description of the thought-process of the decision itself to another (yet to be written) article.

The clef defines the following operations:⁵

• BecomeAtom atom — Out of nothingness, spawn a given atom; or replace an existing atom with the given atom.
• BecomeList — Out of nothingness, spawn an empty list.
• Insert index history — For a list, insert at the index the s-expr that can be constructed from the history; shifting items to the right as required.
• Delete index — For a list, delete the element at the index; shifting items to the left as required.
• Replace index history — For a list, replace the element at the index with the s-expr that can be constructed from the history.

Using this clef we can both construct any s-expressions from scratch and modify any given s-expression into any other (a formal proof is left as an exercise to the reader). As an example, consider a possible way to construct the s-expression (+ (* 6 9) 12):

• BecomeList — starting with an empty list expression
• Insert 0 (BecomeAtom +)) — as the first item, insert the history which consists of the creation of the atom +
• Insert 1 ... — as the second item, insert the result of the following history:
  • BecomeList — starting with an empty list (sub)expression
  • Insert 0 (BecomeAtom *)) — introducing the atoms one…
  • Insert 1 (BecomeAtom 6)) — by one…
  • Insert 2 (BecomeAtom 9)) — by one.
• Insert 2 (BecomeAtom 12)) — similar to the construction of +

The above example is quite trivial, because the order of construction is precisely identical to the ordering of the result. In practice the order might be quite different, and might also include deletions (and therefore: insertions whose effects are not visible in the final result).

Another history leading to the same result is shown below. Note that the indices are not the same as in the first example, but the result is the same.

• BecomeList
• Insert 0 (BecomeAtom 12)) — we start with a single element 12
• Insert 0 (BecomeAtom +)) — to the left of it, we introduce the +
• Insert 1 ... — assuming the same history on the ellipses as in the first example

Importantly, the clef also allows us to express the histories of larger parts of our document as being composed of the histories of their subparts.

To see how this is so, consider the following: The s-expressions form a tree. If the history of a given node is extended by some change, we can apply Replace on its parent node, providing the node’s index in the parent and the extended history. Because this Replace represents a change at the level of the parent, we can repeat this process until we reach the root of the tree. Using this mechanism, the same example might look like this:

• BecomeList

• Insert 0 (BecomeAtom +))

• Insert 1 ... — We start by adding an empty sub-expression…
  • BecomeList
• Replace 1 ... — which is then extended with *
  • BecomeList
  • Insert 0 (BecomeAtom *))
• Replace 1 ... — and extended with 6
  • BecomeList
  • Insert 0 (BecomeAtom *))
  • Insert 1 (BecomeAtom 6))

• Insert 2 (BecomeAtom 12)) — intermezzo on the top-level

• Replace 1 ... — and extended with 9
  • BecomeList
  • Insert 0 (BecomeAtom *))
  • Insert 1 (BecomeAtom 6))
  • Insert 2 (BecomeAtom 9))

This example makes a number of things clear: first that we can see the full ordering of events from the top level, and that work on sub-expressions may be arbitrarily interleaved. In the example above this is demonstrated by the insertion of the atom 12 before the completion of the sub-expression (* 6 9)

Second, that from each sub-level we see the ordering of events relevant to that sub-level. In this case, the precise ordering of the creation of the atoms *, 6 and 9.

Third, it shines some light on some challenges. Namely, the example as given is horribly verbose, which makes it hard to read for humans and has implications on the performance characteristics of the implementation. For both these problems solutions have already been found, which will be presented in the next parts.

Conclusion

This concludes the most basic introduction to the editor.

We’ve seen the goal: having change available as a primitive, and being able to meaningfully express compositions over change. We’ve seen that it is a structured editor and why this should be so.

We’ve also encountered the first design decisions: the decision for s-expressions as a basic syntax, and a particular choice for a clef and how this is sufficient for the stated goals.

In the upcoming parts we’ll show the current prototype in action, and will discuss some of the open questions and implementation details.