Hi. My name is Ethan,
and today I'm going to be speaking
about tree-edit, which is a package
which aims to bring structural editing
to everyday languages.
So what is structural editing?
The way that we typically
write code today
is working with characters, words,
lines, paragraphs, and so on,
and these objects have no real relation
to the structure of programming languages.
In contrast, tree-edit's editing operations
map exactly to the structure
of the programming language,
which is typically in a tree form
with different types of nodes
such as identifiers, expressions,
and statements. Using this structure
can enable much more powerful
editing operations,
and crucially editing operations
that map much more closely
to the way that we think about code.
tree-edit was inspired by
paredit and lispy,
which are two great
Lisp structural editors.
However, what makes tree-edit unique
is that it can work with many languages,
such as some of the
more mainstream languages like C, Java,
Python, and so on.
So now I'm going to show off tree-edit
in action, working with a Java program.
So we can see on the left,
we have a syntax tree,
and the node in bold is what I call
the current node. So instead of
the concept of a cursor,
where we have a point in 2D space,
we instead work with a current node
which all our editing operations
take place upon.
So we can move up and down,
or rather side to side,
move inwards down to the children
of the tree, back up to the parents.
We can also jump to a node by its type.
So we're going to jump to
a variable declaration.
We can jump to an if statement.
And as you might have noticed,
tree-edit by default
uses a vim-style mode of editing,
so it's a verb, which would be jump,
and then a type,
which would be if statement.
So now I'll show off
the syntax tree modification in action.
So if I delete this deleteme node,
we can see the node is deleted,
and also the comma is removed
since it's no longer needed.
We can add some nodes back in.
Here we just have a placeholder node
called tree, which we can swap out
with whatever we like.
So if we want to put in, for example,
a plus or minus operator,
it'll put these two TREE things here
since there needs to be something there,
but we can go fill them out as we like.
So that's what that is.
Then I'll delete these again.
Next we can see raising.
So if I raise reader,
then it will replace
the outer function call
with the node itself.
I could raise it again.
The opposite operation to that
is wrapping. So I can wrap reader
back into function call,
and I could wrap this again
if I wanted to. So that is wrapping.
We can also do it on a statement level,
so if I want to wrap this
in an if statement,
I can wrap the statement,
and there we go.
And let's just raise it back up,
raise it again.
There we go. Finally, I'll show off
slurping and barfing,
which... a little bit gross words,
but I think it accurately describes
the action, so let me just add
a couple breaks here.
So let's say we want
this if statement and a couple of breaks
to be inside of the while,
so we can just slurp this up,
and if we don't actually want them,
we can barf them back out.
So that's where those words
have come from.
And we can just... delete as we please.
So yeah, that's a quick overview
of the tree editing plugin in action.
So now I want to talk a little bit
about the implementation of tree-edit.
Tree-edit uses the tree-sitter parser
to convert text into a syntax tree.
Tree-sitter is used by GitHub
for its syntax highlighting,
and it's available in a bunch of editors,
including Emacs, so it's
a fairly standard tool.
However, the unique part about tree-edit
is how it performs
correct editing operations
on the syntax tree
and then converts that back into text.
So to do that, we use miniKanren,
and miniKanren is an embedded
domain-specific language
for logic programming.
So what exactly does that mean?
In our case, it's just
an Emacs Lisp library called reazon,
which exposes a set of macros
which enables us to program
in this logic programming style.
I'm not going to get into the details
of how logic programming works.
However, one of the most unique aspects
about it is that we can define
a predicate and then figure out
all the inputs to the predicate
that would hold to be true.
So in this case,
we have our query variable q,
which will be what the output is,
and we are asking for all the values of q
that pass this predicate of
being set-equal to 1 2 3 4.
So if we execute this,
it will take a little time...
It shouldn't be taking this long.
Oh, there it goes.
We can see that it's generated
a bunch of different answers
that are all set-equal to 1 2 3 4.
So it's just a bunch of
different permutations of that.
We can extend this notion
to a parser. In tree-edit, we've defined
a parser in reazon,
and we can use that parser to figure out
any tokens that match the type of node
that we're trying to generate.
If I execute this, we can see
that reazon has generated
these five answers that match
what a try statement is in Java.
Here we can see we can have
an infinite amount of catches
optionally ending with a finally,
and we always have to start
with a try and a block.
We can see this again
with an argument list.
We have the opening and closing
parentheses, and expressions
which are comma delimited.
Now, for a more complex example, and
something that is along the lines
of what's in tree-edit,
is if we have this x here
and we want to insert another expression,
so x, y. We can assert
that there's some new tokens,
and we want an expression
to be in those new tokens,
and we can essentially state
where we want these new tokens to go
within the old list of tokens,
so replacing it
after the previous expression,
before the closed parentheses,
and then we can state
that the whole thing parses.
If we run that, we can see that
as we wanted earlier,
which was a comma and then expression,
we have that here as well.
We can see this again.
Here, the only change is that
we've moved the tokens to be
before the expression.
So we want to put an expression
before this x, so we want something
like y, x,
and if we execute that,
we can see that it is correctly asserted
that it would be an expression
and then a comma afterwards.
One last example is
if we have an if statement
and we want to add an extra block,
we can see that it correctly figures out
that we need an else
in order to have another statement
in an if statement.
So, next steps for tree-edit.
The core of tree-edit is in place
but there's a lot of usability features
to add, and a lot of testing
that needs to be done
in order to iron out any bugs that exist.
I'd like to add support
for as many languages as is possible.
I think my next step
will probably be Python.
There's some performance improvements
that need to be made, since using this
logic programming language
is fairly intensive.
There's some optimizations
both on the library side
and on tree-edit side
that can be made.
Contributors are of course welcome,
as tree-edit is an open source project.
For future work, I think the prospect
of voice controlled development
with tree-edit is actually something
that's really exciting,
since syntax can be very cumbersome
when you're working with
voice control software.
I can envision something like
saying, "Jump to identifier,
add plus operator, jump to if statement,
wrap if statement in while."
So that's something
I'd like to investigate.
I also would just like to
provide the core functionality
of [tree-edit] as something
that can be used as a library
for other projects,
such as refactoring packages,
or other non-Vim-style approaches,
and just making the syntax generation
available for reuse.
Finally, I'd like to thank
the authors of reazon
and elisp-tree-sitter,
which in turn packages
tree-sitter itself,
since tree-edit relies very heavily
on these two packages.
I'd also like to thank
the author of lispy,
since a lot of the design decisions
when it comes to the editing operations
are based very heavily on lispy.
So that's the end of my talk.
Thank you for watching.
[captions by sachac]