Typed Image-based Programming with Structure Editing

Jonathan Edwards [email protected] 0000-0003-1958-79672 independentSan DiegoUS and Tomas Petricek [email protected] University of KentCanterburyUK

(2021)

Abstract.

Many beloved programming systems are image-based: self-contained worlds that persist both code and data in a single file. Examples include Smalltalk, LISP, HyperCard, Flash, and spreadsheets. Image-based programming avoids much of the complexity of modern programming technology stacks and encourages more casual and exploratory programming. However conventional file-based programming has better support for collaboration and deployment. These problems have been blamed for the limited commercial success of Smalltalk. We propose to enable collaboration in image-based programming via types and structure editing.

We focus on the problem of schema change on persistent data. We turn to static types, which paradoxically require more schema change but also provide a mechanism to express and execute those changes. To determine those changes we turn to structure editing, so that we can capture changes in type definitions with sufficient fidelity to automatically adapt the data to suit. We conjecture that typical schema changes can be handled through structure editing of static types.

That positions us to tackle collaboration with what could be called version control for structure editing. We present a theory realizing this idea, which is our main technical contribution. While we focus here on editing types, if we can extend the approach to cover the entire programming experience then it would offer a new way to collaborate in image-based programming.

structure editing, operational transformation, version control, schema change, image based programming

^†^†copyright: rightsretained^†^†journalyear: 2021^†^†conference: Human Aspects of Types and Reasoning Assistants; October 19, 2021; Chicago, USA

1. Introduction

Our elders tell stories of the golden age of programming in Smalltalk and LISP machines. These self-contained programming worlds use one language throughout, with all code and data persisted in an image(Sandewall, 1978; Goldberg, 1984). Image-based programming can be much simpler than our modern stack of technologies, each with their own specialized languages and data models. In an image there is no need for a distinct operating system, a file system, a shell language, a build language, a database, and none of the adapters between them. One language within one development environment is used for everything. Image-based programming is thought to encourage exploratory programming(Trenouth, 1991; Kery et al., 2017). Other beloved programming systems are also forms of image-based programming: HyperCard(Goodman and Atkinson, 1987), Flash, and spreadsheets are all self-contained programming worlds persisting code and data together into a programmable document – an image by another name.

Unfortunately collaboration and deployment is harder with image-based programming than with conventional file-based programming. These problems have been blamed for the limited commercial success of Smalltalk(Bracha, 2020). Collaboration in file-based programming is done with version control systems like git(Chacon and Straub, 2014). But adapting that approach to images, like Smalltalk Envy(Malik, 1997; Hammant, 2017), is complicated and clashes with the native style of development. After all, it would be unsatisfying to solve the collaboration problem by importing the complexity of file-based programming.

To develop a new approach to collaborating with images we focus on a propitious special case: schema change, which is the problem of adapting persistent data to match code changes. Version control systems cannot even comprehend schema change, for data and semantics is outside their purview. It is left as a problem for other tools, like Rails Migrations(Rai, 2021), that must be separately coded and then manually coordinated with code changes. From the perspective of image-based programming, where code and data live together harmoniously, it is only natural to expect that collaboration tools should coordinate changes to both code and data. Schema change also serves as a useful entry point because it arises even in solo image programming, allowing us to start in that simpler context.

We use static types. Dynamically typed systems like Smalltalk can handle simple schema changes, such as adding a field to a class, but not much more. General purpose solutions as in Gemstone(Systems, 2015) can be complex and code-intensive.

We claim that, ironically, static typing simplifies schema change. In a dynamically typed language any field can hold any value, so who is to say that value must change? It’s left up to hand-written code. Putting a static type on a field is declarative: it forces a change to the value when the type changes, and tell us the acceptable range of results. The problem is reduced to inferring the appropriate data changes from a change to the type definition. That is a problem more amenable to tooling. To simplify the problem we will start with a clean slate and defer the complexities of retrofitting our approach into existing systems.

1.1. Schema Change with Abstract Structure Editing

Consider editing a record type to rename and reorder a field. If, like version control systems, we look only at the textual changes to the definition then we can’t distinguish that case from deleting the field and inserting a new one with a new name. But that distinction matters for whether the field’s data should be moved or deleted. Text differencing loses too much information.

To determine schema changes we use structure editing(Sandewall, 1978; Teitelbaum and Reps, 1981; Barstow et al., 1984). Instead of defining types with textual syntax we store them as structured values living in the image, and directly manipulate them with a GUI that performs high-level edit operations. For the example of a record type there would be distinct edit operations to insert, delete, move, and rename fields. By capturing type edits at this fine level of granularity we can perform the correct schema changes to the data, knowing to move and rename it rather than delete it.

Structure editing has been justly criticized for lacking the fluidity of text editing. But note that many image-based programming systems already use structure editing to some extent, editing text only at the finer levels of structure like Smalltalk methods and spreadsheet cells. In this paper we abstract away from the user interface issues of structure editing and focus on the semantics: what are the edits, how do they work, and how are they managed? A GUI structure editor provides affordances for these edits, but they might also be surfaced in a vi-style editor or a REPL or an API. We defer such interfaces to future work.

We conjecture that typical schema changes can be handled through structure editing of static types. Given that, the problem of collaborative schema change is reduced to the problem of collaborative structure editing. That immediately suggests collaborative editing systems like Google Docs, which uses the theory of Operational Transformation (OT)(Ellis and Gibbs, 1989; Ressel et al., 1996). However that isn’t the kind of collaboration we need: rather than synchronizing distributed replicas of the same image, we need to support images that are long-lived variants of each other, display their differences, and then allow selected differences to be migrated between them. What we want is a workflow like textual version control, but for structure editing. We call this version control for structure editing. To provide this we adapt the theory of OT to the requirements of version control. That is the main technical contribution of this paper, which we now present.

2. Version Control for Structure Editing

In this section we present the theory of our approach on the simplest possible domain: a single tuple of atomic types. The type of a document (our preferred term for an image) is a tuple of atomic types $(T_{1},\ldots T_{n})$ where $T_{i}\in\{\operatorname{\mathtt{num}},\operatorname{\mathtt{str}},\operatorname{\mathtt{bool}},\operatorname{\mathtt{del}}\}$ . The type $\operatorname{\mathtt{del}}$ marks a term as deleted but retains it as a tombstone(Oster et al., 2006). We define a minimal set of edit operations:

$\begin{array}[]{ll}\operatorname{\mathtt{Ins}}[i,t]&\text{Insert type $t$ at index $i$, shifting indexes $\geq i$ right.}\\ \operatorname{\mathtt{Conv}}[i,t]&\text{Convert index $i$ to have type $t$.}\\ \operatorname{\mathtt{Move}}[i,j]&i\neq j.\text{ Set index $i$ to have the type and value of index $j$ and delete $j$.}\\ \operatorname{\mathtt{Id}}&\text{Does nothing.}\\ \end{array}$

In section 2.3 we present a precise semantics of edits including values. Until then we simplify the discussion by focusing only on changes to types.

Version control is about tracking the differences between variant documents, and migrating changes between them. The simplest situation is where document $B$ is produced from document $A$ with a single edit diff. A change is then made in the original document $A$ and we want to be able to migrate this change into the derived document $B$ . More formally, say that we have an edit pre that modifies $A$ into $A^{\prime}$ . We want to determine the edit post modifying $B$ (into $B^{\prime}$ ) that “does the same thing” ¹¹1The rules in Appendix A define what we mean by “doing the same thing”, but we don’t know how to define this requirement outside the theory.. Since we are tracking the differences between documents we also need to determine the edit adjust that is the new difference between the modified variants $A^{\prime}$ and $B^{\prime}$ . The function $\operatorname{\mathtt{project}}$ produces post and adjust subject to this constraint:

Proposition 0.

$\operatorname{\mathtt{project}}(\mathit{pre},\mathit{diff})=(\mathit{post},\mathit{adjust})\implies\mathit{post}\circ\mathit{diff}=\mathit{adjust}\circ\mathit{pre}$

which is expressed by the commutative diagram 1 in Figure 1. The solid arrows indicate the arguments to $\operatorname{\mathtt{project}}$ and the dashed arrows are the results. Note that unlike in Category Theory, our commutative diagrams are oriented, so rotation or reflection changes their meaning.

1. project

2. retract

3. project & retract

4. no retraction

Figure 1. Commutative diagrams for

\operatorname{\mathtt{project}}

and

\operatorname{\mathtt{retract}}

operations.

\Description

[project and retract diagrams]Commutative diagrams for project and retract operations.

Inversely we can start with post and determine pre and adjust with the function $\operatorname{\mathtt{retract}}$ in diagram 2 in Figure 1 above that expresses the constraint:

Proposition 0.

$\operatorname{\mathtt{retract}}(\mathit{post},\mathit{diff})=(\mathit{pre},\mathit{adjust})\implies\mathit{post}\circ\mathit{diff}=\mathit{adjust}\circ\mathit{pre}$

Projection and retraction are often (but not always) inverses. When they are we state that with Diagram 3 above using all solid arrows.

Retraction is not always possible. Diagram 4 above shows that $\operatorname{\mathtt{Conv}}[1,\operatorname{\mathtt{num}}]$ cannot be retracted through $\operatorname{\mathtt{Ins}}[1,\operatorname{\mathtt{str}}]$ , which created the term being converted. There is no edit that would do the same thing as the $\operatorname{\mathtt{Conv}}$ . We say that the $\operatorname{\mathtt{Conv}}$ edit depends upon the $\operatorname{\mathtt{Ins}}$ edit. Diagram 4 uses crossed-out arrows to indicate an impossible retraction.

We will walk through examples to explain the essential properties of projection and retraction. Their full definition is in Appendix A. To start with, the $\operatorname{\mathtt{Ins}}$ and $\operatorname{\mathtt{Move}}$ operations transform the location of other edits as would be expected:

An important case is overriding of conflicting edits:

As in the above example when $\operatorname{\mathtt{Conv}}$ operations at the same location conflict then the top edit is overridden so that the left and right edits “do the same thing”. The top edit gets “grounded out” by setting the bottom edit to $\operatorname{\mathtt{Id}}$ .²²2This remains valid when we also consider values because, as discussed in section 2.3, the $\operatorname{\mathtt{Conv}}$ operation is lossless.

This example shows that $\operatorname{\mathtt{project}}$ and $\operatorname{\mathtt{retract}}$ are asymmetric, meaning we sometimes cannot flip their diagrams along the diagonal (as in a matrix transpose). This asymmetry expresses that our system does not automatically resolve conflicts, but lets the user chose among possible resolutions (see 2.2). OT obtains symmetry by having timestamps preordain how to resolve conflicts.

Another important case is when duplicate operations “cancel out”: if the left or right edits duplicate the top one then they make no difference when migrated to the other side, so “doing the same thing” demands they ground out to $\operatorname{\mathtt{Id}}$ . Note how in this case $\operatorname{\mathtt{project}}$ and $\operatorname{\mathtt{retract}}$ are not inverses:

$\operatorname{\mathtt{project}}$ : $\operatorname{\mathtt{retract}}$ :

However except for such cases where $\operatorname{\mathtt{project}}$ and $\operatorname{\mathtt{retract}}$ ground out, they are inverses. In other words, if an edit “makes it through” in one direction, it will return back again restored.

Proposition 0.

$\operatorname{\mathtt{project}}(\mathit{pre},\mathit{diff})=(\mathit{post},\mathit{adjust})\land\mathit{post}\neq\operatorname{\mathtt{Id}}\implies\operatorname{\mathtt{retract}}(\mathit{post},\mathit{diff})=(\mathit{pre},\mathit{adjust})$

$\operatorname{\mathtt{retract}}(\mathit{post},\mathit{diff})=(\mathit{pre},\mathit{adjust})\land\mathit{pre}\neq\operatorname{\mathtt{Id}}\implies\operatorname{\mathtt{project}}(\mathit{pre},\mathit{diff})=(\mathit{post},\mathit{adjust})$

$\operatorname{\mathtt{project}}(\operatorname{\mathtt{Id}},\mathit{diff})=\operatorname{\mathtt{retract}}(\operatorname{\mathtt{Id}},\mathit{diff})=(\operatorname{\mathtt{Id}},\mathit{diff})$

2.1. Differencing

The point of version control is to determine the differences between two variants, and migrate selected differences between them. Standard version control is based on heuristic comparison of the variants in reference to an ancestral common state(Khanna et al., 2007). We extend the standard approach in two ways. Firstly, we base our comparisons on the actual history of edits in order to be precise enough to perform schema changes. Secondly, we do not depend on finding a common ancestor. We don’t want to require variants to all live in a single shared repository in which to search for an ancestor. Ancestral comparison also inaccurately identifies as differences those changes that have been duplicated in both descendants (perhaps by cherry picking(Chacon and Straub, 2014)).

The point of the ancestor is to localize changes to one document or the other, for example did one document insert something or did the other one delete it? But since we are recording the edit history of each document we already have all the information we need. We can derive the “optimal ancestor” which we call the agreement $A\&B$ of documents $A$ and $B$ . This derivation also produces two sequences of edits called differences that reconstruct $A$ and $B$ from $A\&B$ . The agreement is optimal in the sense that the differences are minimized, eliminating duplication.

As a starting example, consider the situation where $A$ and $B$ started as $(\operatorname{\mathtt{num}})$ but $A$ inserted a $\operatorname{\mathtt{bool}}$ term and $B$ changed the $\operatorname{\mathtt{num}}$ term into a $\operatorname{\mathtt{str}}$ . We diagram the agreement and differences like this:

Now say that the user edits $A$ to change the second term $\operatorname{\mathtt{num}}$ to be $\operatorname{\mathtt{str}}$ , as in $B$ . In order to adjust the differences we $\operatorname{\mathtt{translate}}$ the edit to $A$ by retracting it backwards to $A\&B$ and then projecting it forwards to $B$ , resulting in the diagram:

Note that in the above diagram the left square is a retraction which has been mirrored to go from left to right. The right-most downward arrow, from $B$ to $B^{\prime}$ , is the translation that “does the same thing” as the edit to $A$ . It is $\operatorname{\mathtt{Id}}$ , which means that the original edit doesn’t make any difference to $B$ (because $B$ had already made the same change). Therefore the edit is “absorbed” into the agreement, as shown in the bottom row of the diagram. Note that $B$ has not changed but the agreement has, and there is no longer any difference between them.

But often edits do make a difference when translated, for example if $A$ had changed the $\operatorname{\mathtt{num}}$ to $\operatorname{\mathtt{bool}}$ , which is different from the change $B$ made:

Here the right-most downwards arrow is not $\operatorname{\mathtt{Id}}$ , and therefore the original edit is in fact increasing the differences between $A$ and $B$ , unlike the previous example. Therefore we do not adjust the agreement – instead we just append the edit to the differences of $A$ to create $A^{\prime}$ , extending the top row of the previous diagram leftward, and leaving $B$ and the agreement unchanged, diagrammed thusly:

Another case to consider is if $A$ was to change the first term of the tuple, which does not exist in $A\&B$ or $B$ . In that case, the edit would not retract back to the agreement, and as in the previous example would be appended to the differences of $A$ .

To handle the general case of multiple differences we define the function $\operatorname{\mathtt{translate}}$ that chains together retracts and projects. If $A$ differs from $A\&B$ with the edit sequence $a_{1\ldots n}$ , and $B$ likewise with $b_{1\ldots m}$ , and given an edit $\epsilon$ to $A$ we retract it through the $a$ edits in reverse order and then project through the $b$ edits in forwards order. This produces an edit $\delta$ to $B$ and adjusted difference sequences $a^{\prime}$ and $b^{\prime}$ . The whole $\operatorname{\mathtt{translate}}$ is undefined if one of the retractions is undefined, meaning that $\epsilon$ depends on one of the $a$ edits. Formally:

$\operatorname{\mathtt{translate}}(\epsilon,a_{1\dots n},b_{1\ldots m})=(\delta,a^{\prime}_{1\dots n},b^{\prime}_{1\ldots m})$ where:

	$\displaystyle\epsilon_{n}$	$\displaystyle=\epsilon$
	$\displaystyle\delta_{0}$	$\displaystyle=\epsilon_{0}$
	$\displaystyle\delta$	$\displaystyle=\delta_{m}$

	$\displaystyle(\epsilon_{i-1},a^{\prime}_{i})$	$\displaystyle=\operatorname{\mathtt{retract}}(\epsilon_{i},a_{i})\ \ \text{for}\ i=1\ldots n$
	$\displaystyle(\delta_{i},b^{\prime}_{i})$	$\displaystyle=\operatorname{\mathtt{project}}(\delta_{i-1},b_{i})\ \ \text{for}\ i=1\ldots m$

Now we can state the general algorithm for difference maintenance. If an edit $\epsilon$ to $A$ translates into $\delta=\operatorname{\mathtt{Id}}$ on $B$ then the edit is absorbed into the agreement and the differences are adjusted into the bottom line of the diagram (leaving $B$ unchanged). If $\delta\neq\operatorname{\mathtt{Id}}$ or is undefined then the edit is appended to the differences of $A$ as shown in this diagram:

The above algorithm incrementally maintains the differences and agreement between two documents as they are edited. Note that it operates on edits and never needs to inspect document states. It is straightforward to rederive the differences from scratch given the edit history of any two documents from a common ancestral state (or their total histories starting from an empty document). This is done by setting the agreement to the common ancestral state, the differences of $B$ to its history from the ancestor, and then applying each of the edits from the history of $A$ . It is correct because:

Proposition 0.

Given two edit histories from the same starting state, the differences calculated will be the same regardless of how the two histories are interleaved.

2.2. Migration

In the previous section we defined the function $\operatorname{\mathtt{translate}}$ to derive the differences between two documents. The $\operatorname{\mathtt{translate}}$ function is also used to migrate individual differences from one document to the other. Returning to where we left off with the last example:

Say the user wants to migrate the last difference of $A$ , which set the second term to $\operatorname{\mathtt{bool}}$ . We remove that edit from $A$ ’s differences and then translate it through to $B$ , producing this diagram:

$B$ has now been changed equivalently to the edit we picked to migrate, and the differences have been adjusted to remove the now agreed-upon edit. Now in this example we conveniently chose to migrate the last difference to $A$ . In the general case we extract the subsequent differences and then append them back to the results of the translation, as in this diagram showing how to migrate the difference $a_{i}$ :

Consider what happens if $a_{1}=\operatorname{\mathtt{Conv}}(1,num)$ and $b_{1}=\operatorname{\mathtt{Conv}}(1,str)$ . Migrating $a_{1}$ will override $b_{1}$ , setting $b^{\prime}_{1}=\operatorname{\mathtt{Id}}$ . We call this a conflict: a merge where one of the $b$ edits is grounded out to $\operatorname{\mathtt{Id}}$ . A conflicting migration overrides differences in the opposite doc. Conflict is symmetric: if $a$ conflicts with $b$ then $b$ also conflicts with $a$ , so the user has the choice of migrating either one and overriding the other. Note that our concept of a conflict is more precise than the merge conflict of textual version control, which means only that changes appear to be occurring on the same text line, and often must be resolved with manual text editing. Many of our edits never conflict (like $\operatorname{\mathtt{Ins}}$ and $\operatorname{\mathtt{Move}}$ ), and conflicts that do occur are definite, and are resolved just by choosing which one wins.

Proposition 0 (Conflict symmetry).

If migrating $a_{i}$ conflicts with $b_{j}$ then migrating $b_{j}$ will conflict with $a_{i}$ .

The key property of migration is that it reduces differences:

Proposition 0 (Convergence).

Repeatedly migrating differences between two documents will terminate with them equal.

Note however that the resultant document value can vary depending on the chosen order of migration. That order determines which of a pair of conflicting edits will dominate.

It is not possible to migrate a difference when it depends on an earlier difference – the dependency must be migrated first. In our implementation we provide the option to automatically migrate all transitive dependencies. We also support migrating all differences (equivalent to merging a branch in traditional version control) by migrating each in turn. Because we “cherry pick” at the granularity of individual edits the user interface can flexibly cluster migrations, say by time or location.

There is a technical problem with migrating $\operatorname{\mathtt{Ins}}$ edits. Proposition 2.4 says we can recompute the differences between two documents from their histories, so the adjusted differences produced by the migrate function must be the same as immediately recalculating them afterwards. This fails when we migrate an $\operatorname{\mathtt{Ins}}$ edit, because we consider all inserts to be distinct. To fix this problem we add a unique identifier to the $\operatorname{\mathtt{Ins}}$ operation and we modify the $\operatorname{\mathtt{project}}$ function to cancel out inserts with the same identifier. We left this detail out of the prior discussion for the sake of simplicity.

2.3. Value Semantics

The preceding discussion was simplified by considering only the type definitions of tuples. We will now incorporate values, and provide a precise semantics of the edit operations.

A document is a typed tuple $(v_{1}\colon T_{1}\ldots v_{n}\colon T_{n})$ where $T_{i}\in\{\operatorname{\mathtt{num}},\operatorname{\mathtt{str}},\operatorname{\mathtt{bool}},\operatorname{\mathtt{del}}\}$ . The type $\operatorname{\mathtt{del}}$ has a single value $\mathtt{null}$ .

The edit operations are:

$\begin{array}[]{ll}\operatorname{\mathtt{Id}}&\text{Does nothing.}\\ \operatorname{\mathtt{Ins}}[i,t,p]&\text{Insert type $t$ at index $i$, shifting indexes $\geq i$ right. $p$ is a unique identifier.}\\ \operatorname{\mathtt{Conv}}[i,t]&\text{Convert index $i$ to have type $t$.}\\ \operatorname{\mathtt{Move}}[i,j]&i\neq j.\text{ Set index $i$ to have the type and value of index $j$ and delete $j$.}\\ \end{array}$

defined as:

	$\displaystyle\operatorname{\mathtt{Id}}\,(v_{1}\colon T_{1}\ldots v_{n}\colon T_{n})$	$\displaystyle=(v_{1}\colon T_{1}\ldots v_{n}\colon T_{n})$
	$\displaystyle\operatorname{\mathtt{Ins}}[i,t,p]\,(v_{1}\colon T_{1}\ldots v_{n}\colon T_{n})$	$\displaystyle=(v_{1}\colon T_{1}\ldots v_{i-1}\colon T_{i-1},\mathtt{null}\colon t,v_{i}\colon T_{i}\ldots v_{n}\colon T_{n})$
	$\displaystyle\operatorname{\mathtt{Conv}}[i,t]\,(v_{1}\colon T_{1}\ldots v_{n}\colon T_{n})$	$\displaystyle=(v_{1}\colon T_{1}\ldots v_{i-1}\colon T_{i-1},v_{i}\colon t,v_{i+1}\colon T_{i+1}\ldots v_{n}\colon T_{n})$
	$\displaystyle\operatorname{\mathtt{Move}}[i,j]\,(v_{1}\colon T_{1}\ldots v_{n}\colon T_{n})$	$\displaystyle=(v^{\prime}_{1}\colon T^{\prime}_{i}\ldots v^{\prime}_{n}\colon T^{\prime}_{n})\text{ where }v^{\prime}_{k}\colon T^{\prime}_{k}=\begin{cases}v_{j}\colon T_{j}&k=i\\ \mathtt{null}\colon\operatorname{\mathtt{del}}&k=j\\ v_{k}\colon T_{k}&\text{otherwise}\\ \end{cases}$

The rules defining projection and retraction are presented in Appendix A.

We allow a document to contain type errors. In the spirit of image-based programming, we handle errors gracefully and allow them to be corrected when convenient. We define a function $\mathtt{conform}$ that takes a document and produces a type-conforming version of it, in which all values either conform to their type or are the special value $\mathtt{error}$ . Programs can only see conforming values. This technique is related to the non-empty holes of Omar et al.(Omar et al., 2017; Omar et al., 2019).

The $\operatorname{\mathtt{Ins}}$ edit gives a new term the value $\mathtt{null}$ , representing an uninitialized value. The $\mathtt{conform}$ function can treat an uninitialized value as an error, or as we do in our implementation, assign a default value based on the type.

The $\mathtt{conform}$ function also handles type conversion. The $\operatorname{\mathtt{Conv}}$ edit just sets the desired type, leaving the existing value in place, which $\mathtt{conform}$ converts if possible or yields $\mathtt{error}$ . By retaining the unconverted value we also allow conversions to compose losslessly, which occurs when we migrate conflicting conversions. Lossless conversions are needed to ensure convergence (Proposition 2.6).

3. Prototype Implementation

Will this theory work in practice? We are building a prototype implementation to find out. We have extended the minimalist theory to a more practical set of datatypes and edit operations. We have also built a GUI to explore how to visually manifest structural version control. We have extended the theory to include:

(1)

Nested records and homogeneous lists, forming a tree.
(2)

Edit operations are located at paths within the tree, expressed as sequences of indexes.
(3)

$\operatorname{\mathtt{Move}}$ carries a subtree across the tree to replace another subtree. This includes the ability to reorder lists.
(4)

Edits to the type of a list are iterated over its elements.
(5)

A rename operation on record fields.
(6)

Differences can be normalized, producing a sequence of edits ordered by location in the tree.
(7)

(pending) Sum types, to gain parity with standard FP datatypes.
(8)

(pending) A wrap operation to replace a location the tree with a record or sum or list containing it. There is an inverse unwrap operation.

Our prototype GUI focuses on viewing the differences between two documents and performing migrations. A central problem of structure editing is to make it as ”fluid“ as text editing. That is not the problem we are working on here, so we edit with a command line. We use infix syntax for edit operations, with the prefixed location formatted as a dotted path of field names and list indexes.

Figure 2 shows an annotated screenshot. A recorded demo can be viewed at https://vimeo.com/manage/videos/631461226.

Refer to caption — Figure 2. Annotated screenshot of difference view

4. Limitations and Opportunities

This is early stage work that raises more questions than it answers:

(1)

Can direct manipulation editing in a GUI compete with the fluidity of text editing?
(2)

Can editing be extended to encompass code, enabling coordinated refactorings across code and data?
(3)

Can complex interrelated schema changes be accommodated? Ambler&Sadalage(Ambler and Sadalage, 2006) cast many such large scale schema changes as refactorings, which we hope to support as structure edits. Nevertheless in some cases it will still be necessary to write code to convert data. How does such code interact with edit migration?
(4)

Can these techniques be retrofitted into existing image-based systems (Smalltalk, LISP), or even text-based ones?

Version control has become a central technology of programming, but we see the chance to enlarge its impact even further:

(1)

Support a larger audience of programmers by providing a simpler and more tractable conceptual model than git (De Rosso and Jackson, 2016).
(2)

Images could be utilized like OS containers, so that deployment becomes version control. Deployment was a major problem in the earlier age of image-based programming.
(3)

We mentioned at the outset that spreadsheets are an example of image-based programming. We would love to have our approach applied to spreadsheets. Instead of making tweaked copies and copy-pasting between them, we could view their differences and migrate changes as needed.

Our long term vision is to use types and structure editing to bring back the benefits of image-based programming to modern programmers. We hope that we have at least incentivised future research on structure editing by identifying two heretofore overlooked benefits:

(1)

Automatic schema change, and
(2)

high-level version control.

5. Related Work

SQL DDL(Alt, 2021) is the standard language for editing relational database schema. It can rename, reorder, and convert the datatype of a column. More complex database conversions can be coded in specialized languages such as Rails Migrations(Rai, 2021). Schema change has been cast as a form of refactoring(Ambler and Sadalage, 2006). Versioning has been built into or added onto databases and other structured data formats(Attic-Labs, 2021; dol, 2021; dbm, 2021; Fitz, 2021) and notebooks(Kery et al., 2017). The theory of lenses has been applied to schema change on data structures(Foster et al., 2007; Litt et al., 2020). Closer to our focus on image-based programming is the work on schema change for Object Oriented Databases(Systems, 2015; Banerjee et al., 1987), version control for Smalltalk(Malik, 1997), and Orthogonal Synchronization(Bracha, 2005).

Research on structure editing has a long history(Sandewall, 1978; Teitelbaum and Reps, 1981; Barstow et al., 1984). One focus has been to enable non-textual projections of code(Czarnecki and Eisenecker, 2000; s.r.o., 2021). Perhaps the most successful structure editor is Scratch(Resnick et al., 2009), providing an easy editing experience for beginners free of syntax errors. Scratch and successor blocks-based languages rely on drag-and-drop gestures, which motivated our inclusion of the $\operatorname{\mathtt{Move}}$ operation. Recent research seeks to match the fluidity of text editing (Kölling et al., 2015; Hempel et al., 2018) and the rigorous semantics of PL theory(Omar et al., 2017; Omar et al., 2019).

Our work repurposes Operational Transformation (OT) (Ellis and Gibbs, 1989; Ressel et al., 1996), which is the theory behind collaborative document editing as in Google Docs. OT supports collaborative editing of a single document, where the central problem is the unpredictable arrival order of edits at distributed replicas. Our need to track and selectively migrate differences between long-lived variants leads to a substantially different and more complex theory. For one thing, we give users the choice of how and when to resolve conflicts, whereas in OT timestamps preordain resolution. This introduces asymmetries into our transformations, violating the Symmetry Property of Ressel et al.(Ressel et al., 1996). The notation of commutative diagrams from Category Theory has proven essential to handle the complexity arising, ironically, from the non-commutativity of edits.

The Categorical Theory of Patches (Mimram and Di Giusto, 2013) implemented in Pijul(Pij, 2021) presents a theory of textual version control based on line-oriented text edits called patches. Intriguingly, a merge is modelled as a categorical pushout, diagrammed like our $\operatorname{\mathtt{project}}$ function, and our $\operatorname{\mathtt{retract}}$ function looks like a pullback. However the asymmetries introduced by overriding conflicts don’t satisfy the definitions of pushout and pullback. We don’t know what to make of this and welcome any insights from Category Theorists.

Our prior work on Subtext (Edwards, 2005, 2006) assigned permanent parent-unique IDs to tree nodes, forming stable paths. However differencing/migrating movement and wrapping/unwrapping operations became complex and confusing. Ultimately we felt forced to adopt an OT-like approach of transforming edit histories in order to have some confidence of correctness. Folk wisdom has it that OT is difficult to get right, but so far we have found the implementation guided by the theory to be robust. Note that unique IDs had to be incorporated into $\operatorname{\mathtt{Ins}}$ operations to support Proposition 2.4, so the status of IDs is still unclear. It would be interesting to see if recent CRDT advances (Kleppmann et al., 2021) could provide an alternative solution.

6. Acknowledgements

We thank Philip Guo, Joel Jakubovic, and the anonymous reviewers for constructive comments.

References

(1)
Alt (2021) 2021. ALTER TABLE, SQL Language Reference. https://docs.oracle.com/en/database/oracle/oracle-database/21/sqlrf/ALTER-TABLE.html#GUID-552E7373-BF93-477D-9DA3-B2C9386F2877
dbm (2021) 2021. DBmaestro: DevOps for Database. https://db.dbmaestro.com/
dol (2021) 2021. Dolt. https://www.dolthub.com/
Rai (2021) 2021. Migrations. https://guides.rubyonrails.org/v3.2/migrations.html
Pij (2021) 2021. Pijul, a sound and fast distributed version control system based on a mathematical theory of asynchronous work. https://pijul.org/
Ambler and Sadalage (2006) S.W. Ambler and P.J. Sadalage. 2006. Refactoring Databases: Evolutionary Database Design. Addison Wesley, USA.
Attic-Labs (2021) Attic-Labs. 2021. Noms. https://github.com/attic-labs/noms
Banerjee et al. (1987) Jay Banerjee, Won Kim, Hyoung-Joo Kim, and Henry F. Korth. 1987. Semantics and Implementation of Schema Evolution in Object-Oriented Databases. SIGMOD Rec. 16, 3 (Dec. 1987), 311–322. https://doi.org/10.1145/38714.38748
Barstow et al. (1984) D.R. Barstow, S.G. Guty, H.E. Shrobe, and E. Sandewall. 1984. Interactive Programming Environments. McGraw-Hill, USA.
Bracha (2005) Gilad Bracha. 2005. Objects as Software Services. http://bracha.org/objectsAsSoftwareServices.pdf
Bracha (2020) Gilad Bracha. 2020. Bits of History, Words of Advice. https://gbracha.blogspot.com/2020/05/bits-of-history-words-of-advice.html
Chacon and Straub (2014) Scott Chacon and Ben Straub. 2014. Pro Git (2nd ed.). Apress, USA.
Czarnecki and Eisenecker (2000) Krzysztof Czarnecki and Ulrich W. Eisenecker. 2000. Generative Programming: Methods, Tools, and Applications. ACM Press/Addison-Wesley Publishing Co., USA, Chapter 11.
De Rosso and Jackson (2016) Santiago Perez De Rosso and Daniel Jackson. 2016. Purposes, Concepts, Misfits, and a Redesign of Git. SIGPLAN Not. 51, 10 (Oct. 2016), 292–310. https://doi.org/10.1145/3022671.2984018
Edwards (2005) Jonathan Edwards. 2005. Subtext: Uncovering the Simplicity of Programming. In Proceedings of the 20th Annual ACM SIGPLAN Conference on Object-Oriented Programming, Systems, Languages, and Applications (San Diego, CA, USA) (OOPSLA ’05). Association for Computing Machinery, New York, NY, USA, 505–518. http://www.subtext-lang.org/OOPSLA05.pdf
Edwards (2006) Jonathan Edwards. 2006. First Class Copy & Paste. Technical Report MIT-CSAIL-TR-2006-037. MIT. http://hdl.handle.net/1721.1/32980
Ellis and Gibbs (1989) C. A. Ellis and S. J. Gibbs. 1989. Concurrency Control in Groupware Systems. In Proceedings of the 1989 ACM SIGMOD International Conference on Management of Data (Portland, Oregon, USA) (SIGMOD ’89). Association for Computing Machinery, New York, NY, USA, 399–407. https://doi.org/10.1145/67544.66963
Fitz (2021) Paul Fitz. 2021. daff. https://paulfitz.github.io/daff/
Foster et al. (2007) J. Nathan Foster, Michael B. Greenwald, Jonathan T. Moore, Benjamin C. Pierce, and Alan Schmitt. 2007. Combinators for bidirectional tree transformations: A linguistic approach to the view-update problem. ACM Transactions on Programming Languages and Systems 29, 3 (May 2007), 17. https://doi.org/citation.cfm?doid=1232420.1232424
Goldberg (1984) Adele Goldberg. 1984. SMALLTALK-80: The Interactive Programming Environment. Addison-Wesley Longman Publishing Co., Inc., USA.
Goodman and Atkinson (1987) D. Goodman and W. Atkinson. 1987. The Complete HyperCard Handbook. Bantam Books, USA.
Hammant (2017) Paul Hammant. 2017. Smalltalk Envy. https://paulhammant.com/2017/09/01/smalltalk-envy/
Hempel et al. (2018) Brian Hempel, Justin Lubin, Grace Lu, and Ravi Chugh. 2018. Deuce: A Lightweight User Interface for Structured Editing. In Proceedings of the 40th International Conference on Software Engineering (Gothenburg, Sweden) (ICSE ’18). Association for Computing Machinery, New York, NY, USA, 654–664. https://doi.org/10.1145/3180155.3180165
Kery et al. (2017) Mary Beth Kery, Amber Horvath, and Brad Myers. 2017. Variolite: Supporting Exploratory Programming by Data Scientists. Association for Computing Machinery, New York, NY, USA, 1265–1276. https://doi.org/10.1145/3025453.3025626
Khanna et al. (2007) Sanjeev Khanna, Keshav Kunal, and Benjamin C. Pierce. 2007. A Formal Investigation of Diff3. In FSTTCS 2007: Foundations of Software Technology and Theoretical Computer Science, V. Arvind and Sanjiva Prasad (Eds.). Springer Berlin Heidelberg, Berlin, Heidelberg, 485–496.
Kleppmann et al. (2021) Martin Kleppmann, Dominic P. Mulligan, Victor B. F. Gomes, and Alastair Beresford. 2021. A highly-available move operation for replicated trees. IEEE Transactions on Parallel and Distributed Systems (2021), 1–1. https://doi.org/10.1109/TPDS.2021.3118603
Kölling et al. (2015) Michael Kölling, Neil C. C. Brown, and Amjad Altadmri. 2015. Frame-Based Editing: Easing the Transition from Blocks to Text-Based Programming. In Proceedings of the Workshop in Primary and Secondary Computing Education (London, United Kingdom) (WiPSCE ’15). Association for Computing Machinery, New York, NY, USA, 29–38. https://doi.org/10.1145/2818314.2818331
Litt et al. (2020) Geoffrey Litt, Peter van Hardenberg, and Henry Orion. 2020. Project Cambria: Translate your data with lenses. https://www.inkandswitch.com/cambria.html
Malik (1997) Vikas Malik. 1997. Smalltalk Envy. http://www.faqs.org/faqs/smalltalk/ENVY-faq/
Mimram and Di Giusto (2013) Samuel Mimram and Cinzia Di Giusto. 2013. A Categorical Theory of Patches. Electronic Notes in Theoretical Computer Science 298 (Nov 2013), 283–307. https://doi.org/10.1016/j.entcs.2013.09.018
Omar et al. (2019) Cyrus Omar, Ian Voysey, Ravi Chugh, and Matthew A. Hammer. 2019. Live Functional Programming with Typed Holes. PACMPL 3, POPL (2019). https://doi.org/10.1145/3290327
Omar et al. (2017) Cyrus Omar, Ian Voysey, Michael Hilton, Jonathan Aldrich, and Matthew A. Hammer. 2017. Hazelnut: A Bidirectionally Typed Structure Editor Calculus. In 44th ACM SIGPLAN Symposium on Principles of Programming Languages (POPL 2017).
Oster et al. (2006) Gerald Oster, Pascal Molli, Pascal Urso, and Abdessamad Imine. 2006. Tombstone Transformation Functions for Ensuring Consistency in Collaborative Editing Systems. In 2006 International Conference on Collaborative Computing: Networking, Applications and Worksharing. 1–10. https://doi.org/10.1109/COLCOM.2006.361867
Resnick et al. (2009) Mitchel Resnick, John Maloney, Andrés Monroy-Hernández, Natalie Rusk, Evelyn Eastmond, Karen Brennan, Amon Millner, Eric Rosenbaum, Jay Silver, Brian Silverman, and Yasmin Kafai. 2009. Scratch: Programming for All. Commun. ACM 52, 11 (Nov. 2009), 60–67. https://doi.org/10.1145/1592761.1592779
Ressel et al. (1996) Matthias Ressel, Doris Nitsche-Ruhland, and Rul Gunzenhäuser. 1996. An Integrating, Transformation-Oriented Approach to Concurrency Control and Undo in Group Editors. In Proceedings of the 1996 ACM Conference on Computer Supported Cooperative Work (Boston, Massachusetts, USA) (CSCW ’96). Association for Computing Machinery, New York, NY, USA, 288–297. https://doi.org/10.1145/240080.240305
Sandewall (1978) Erik Sandewall. 1978. Programming in an Interactive Environment: The “Lisp” Experience. ACM Comput. Surv. 10, 1 (March 1978), 35–71. https://doi.org/10.1145/356715.356719
s.r.o. (2021) JetBrains s.r.o. 2021. MPS: The Domain-Specific Language Creator. https://www.jetbrains.com/mps/
Systems (2015) GemTalk Systems. 2015. Class versions and Instance Migration. https://downloads.gemtalksystems.com/docs/GemStone64/3.2.x/GS64-ProgGuide-3.2/10-ClassHistory.htm
Teitelbaum and Reps (1981) Tim Teitelbaum and Thomas Reps. 1981. The Cornell Program Synthesizer: A Syntax-Directed Programming Environment. Commun. ACM 24, 9 (Sept. 1981), 563–573. https://doi.org/10.1145/358746.358755
Trenouth (1991) J. Trenouth. 1991. A Survey of Exploratory Software Development. Comput. J. 34, 2 (01 1991), 153–163. https://doi.org/10.1093/comjnl/34.2.153 arXiv:https://academic.oup.com/comjnl/article-pdf/34/2/153/1400604/340153.pdf

Appendix A Projection and retraction rules

Equal edits cancel out:

$\operatorname{\mathtt{Id}}$ is a fixpoint:

$\operatorname{\mathtt{Conv}}$ is overridden by conflicting changes:

$\begin{cases}x=\operatorname{\mathtt{Conv}}[i,t]\land t\neq u\\ x=\operatorname{\mathtt{Move}}[i,\_]\end{cases}$

$\operatorname{\mathtt{Conv}}$ passes through independent edits:

$i\neq j\ \land\ \begin{cases}x=\operatorname{\mathtt{Conv}}[j,\_]\\ x=\operatorname{\mathtt{Move}}[j,k]\land i\neq k\\ \end{cases}$

$\operatorname{\mathtt{Ins}}$ doesn’t affect leftward edits:

$i>j\ \land\ \begin{cases}x=\operatorname{\mathtt{Conv}}[j,\_]\\ x=\operatorname{\mathtt{Move}}[j,k]\land i>k\\ \end{cases}$

$\operatorname{\mathtt{Ins}}$ shifts non-leftward edits rightward:

$i\leq j\ \land\ \begin{cases}x=\operatorname{\mathtt{Conv}}[j,u]\land y=\operatorname{\mathtt{Conv}}[j+1,u]\\ x=\operatorname{\mathtt{Move}}[j,k]\land y=\operatorname{\mathtt{Move}}[j+1,k]\land i>k\\ x=\operatorname{\mathtt{Move}}[k,j]\land y=\operatorname{\mathtt{Move}}[k,j+1]\land i>k\\ x=\operatorname{\mathtt{Move}}[j,k]\land y=\operatorname{\mathtt{Move}}[j+1,k+1]\land i\leq k\\ \end{cases}$

$i\leq j\ \land\ p\neq q$

$i>j\ \land\ p\neq q$

Cannot retract an edit at a location through the insert of that location. Not even an insert at that location, because that would not be reversible by a projection.

$\begin{cases}x=\operatorname{\mathtt{Ins}}[i,\_,q]\land p\neq q\\ x=\operatorname{\mathtt{Conv}}[i,\_]\\ x=\operatorname{\mathtt{Move}}[i,\_]\\ x=\operatorname{\mathtt{Move}}[\_,i]\\ \end{cases}$

$\operatorname{\mathtt{Move}}$ moves source to target:

$\begin{cases}x=\operatorname{\mathtt{Conv}}[j,t]\land y=\operatorname{\mathtt{Conv}}[i,t]\\ x=\operatorname{\mathtt{Move}}[j,k]\land y=\operatorname{\mathtt{Move}}[i,k]\land i\neq k\\ x=\operatorname{\mathtt{Move}}[k,j]\land y=\operatorname{\mathtt{Move}}[k,i]\land i\neq k\\ \end{cases}$

Conflicting $\operatorname{\mathtt{Move}}$ edits delete the overridden Move’s source:

$j\neq k$

Can’t project $\operatorname{\mathtt{Conv}}$ through $\operatorname{\mathtt{Move}}$ to its target, because it would retract to the source of the Move.

$\operatorname{\mathtt{Move}}$ passes through edits not to target or source:

$i\neq k\ \land\ j\neq k\ \land\ \begin{cases}x=\operatorname{\mathtt{Conv}}[k,\_]\\ x=\operatorname{\mathtt{Move}}[k,l]\land i\neq l\land j\neq l\\ \end{cases}$