Scaling Synthesis

Search IconIcon to open search

Prune Structural Editor

Last updated March 18, 2023

A structural editor can make a DSL approachable to end-users structural editor (post below because the original source is facebook) reference: https://m.facebook.com/nt/screen/?params=%7B%22note_id%22%3A994298340981590%7D&path=%2Fnotes%2Fnote%2F&refsrc=deprecated&_rdr

Prune: A Code Editor that is Not a Text Editor

Authored by Kent Beck and Thiago Hirai

You want to change the tree structure of a program. You figure out what series of text editing operations, operations that manipulate a 2D grid of characters, are equivalent to the change in the tree you desire. What a waste of time and energy.

Programmers waste energy translating tree transformations into character grid transformations

Religious editor wars are a symptom that the whole paradigm of editing programs with a text editor is broken. Text editors for code have been universally used for decades, however.

Prune lets programmers edit the tree structure directly using commands invoked by typing and rendering the resulting code in a familiar textual format. However, it’s time for someone else to pick up the torch of tree-based editing.

In Prune, programmers transform the tree directly

# The Dream

Prune is a code editor that operates directly on the tree structure of the code. While it renders code in a familiar textual format, it doesn’t offer text editing operations. Programs are created and edited by creating, deleting, and re-organizing nodes in the program’s abstract syntax tree.

Prune grew out of hundreds of hours of observing programmers editing programs with text editors. Proficient users spent considerable energy learning and optimizing their use of the editor. Unskilled users spent considerable energy using the editor badly. Perhaps the problem is not their skill, but the whole idea of using a text editor, a very general tool, for the specific task of program editing.

Structure editors have been around for decades, yet they never caught on for mainstream usage. Prune would have to be substantially better to have a chance of being adopted. While our overall goal was to reduce the cognitive load of manipulating programs, “cognitive load” is hard to measure, so we chose three quantifiable goals:

# Tree Transformations

The fundamental operation in Prune takes one program tree and produces another. For example, making a statement conditional is a single operation:

1
cache = computeValue; ==> if (!cache) {   cache = computeValue; }

This transformation is one of a class of “wrap” transformation–take the current selection, make it a child of a new node, and replace the selection with the new node. Other “wraps” are looping over a statement or statements, surrounding statements with an exception handler, and returning the value of an expression. Mirror “unwrap” transformations replace a parent node with one or more of its children, such as making a statement unconditional only executing it once instead of in a loop. Other transformations create nodes, delete nodes, and reorder nodes.

The transformations are all atomic, in that they take a syntactically correct program and produce another syntactically correct program. This is one way Prune helps reduce errors–programs are syntactically correct by construction. The transformations compose–each takes a tree and a selection and produces a tree and a selection that can act as the input to another transformation. Once we had a basic library of transformations, we found that we could sometimes synthesize new transformations by composition instead of having to write new code to manipulate the tree. The transformations are also reversible, a property lacking in many text editors that have been enhanced to work on code.

# TBD Node

One serendipitous discovery that deserves special mention is the TBD node, used above. Some transformations require two or more parameters. For example, creating a binary expression requires a left side, a right side, and an operator. In a panic we added a special node to the tree representing code to be filled in later. We found it useful in many situations and it never intruded on our work as users of Prune. It did require us to modify the pretty printer we used (esprima), but it was well worth it.

One piece of interface philosophy we carried through Prune is that the editor should allow the user to build a tree by introducing nodes in any order. We have so little experience coding through tree transformations that we have no confidence we have found the most efficient sequence (if one exists).

# Typeahead

One of the risks we identified at the beginning of the project was the number of distinct transformation. If hundreds or thousands of distinct transformations were required to program effectively no one would want to learn them all.

It turns out that a hundred or so transformation suffice for editing JavaScript (our source and our target language). Even a hundred transformations is a lot to remember. When we measured our performance editing samples of code, we found selecting transformations and entering identifiers to be a bottleneck.

To accelerate editing and make Prune feel more familiar, we created a typeahead. When the user begins typing, Prune can guess what tree transformation is implied. For example, typing “if” implies a conditional, a guess that is confirmed when a space follows. The If transformation is invoked at that point, leaving the typeahead ready for input at the condition.

With practice, pruning with the typeahead feels a little like just typing. However, all the “noise” characters, put there just to make the parser happy, like parentheses and curly braces appear automatically. Typeahead adds to the efficiency of editing, reduces keystrokes, and makes Prune more approachable.

# The Project

Prune began as a part-time project, motivated, as mentioned earlier, by watching programmers struggle with text editors. The first prototype was completely simulated on paper, just enough to validate that reducing the keystroke count was possible.

With that bit of evidence in hand, the authors applied for a Hackamonth. After a year with the same team, Facebook engineers are encouraged to take a month and work on something unrelated. It’s considered reasonable to fail attempting an ambitious hack, so off we went. Early in the project we created a Facebook-only group devoted to Prune, which slowly accumulated interested members as we posted the results of experiments, demo videos, and the occasional plea for someone to put us out of our misery.

After the first month we had a version of Prune that we were able to frequently use to add features to Prune. However, reflection on usage showed that our pure “invoke transformations through key bindings” wasn’t going give us the efficiency we wanted. We applied for a second month to implement and measure the typeahead.

At the end of the second month the developers and those who were interested in embedding Prune in their tools met to discuss its future. In the end we struck a rock we had identified in our first presentation–programmers don’t spend that much time manipulating programs compared to all the other things they do. Doing the math, enabling a few hundred programmers to do a 50% better job (an ambitious goal) of a task requiring 10% of their time just doesn’t make economic sense.

However, we were surprised by what we learned working on Prune and we hope the ideas live and grow. That’s why we are publishing this, in hopes that a graduate student somewhere won’t mind a project that takes over his or her life and brings joy to (eventually) millions.

# The Lessons

# Future

One of the curses and blessings of programming at Facebook is there is no shortage of impact work, so both of us reluctantly decided to move on. We still believe in the promise of tree-based editing and would love to use a completed version of Prune. We hope to encourage someone out there to take up the torch. Here are a few tips if it’s you:

Happy pruning.