Learning Structural Edits via Incremental Tree Transformations
Authors: Ziyu Yao
Frank F. Xu
Pengcheng Yin
Huan Sun
Graham Neubig
Venue: ICLR 2021 Poster (2021)
Keywords: Tree-structured Data
Edit
Incremental Tree Transformations
Representation Learning
Imitation Learning
Source Code

Abstract: While most neural generative models generate outputs in a single pass, the human creative process is usually one of iterative building and refinement. Recent work has proposed models of editing processes, but these mostly focus on editing sequential data and/or only model a single editing pass. In this paper, we present a generic model for incremental editing of structured data (i.e. ''structural edits''). Particularly, we focus on tree-structured data, taking abstract syntax trees of computer programs as our canonical example. Our editor learns to iteratively generate tree edits (e.g. deleting or adding a subtree) and applies them to the partially edited data, thereby the entire editing process can be formulated as consecutive, incremental tree transformations. To show the unique benefits of modeling tree edits directly, we further propose a novel edit encoder for learning to represent edits, as well as an imitation learning method that allows the editor to be more robust. We evaluate our proposed editor on two source code edit datasets, where results show that, with the proposed edit encoder, our editor significantly improves accuracy over previous approaches that generate the edited program directly in one pass. Finally, we demonstrate that training our editor to imitate experts and correct its mistakes dynamically can further improve its performance.

Published as a conference paper at ICLR 2021
LEARNING STRUCTURAL EDITS VIA INCREMENTAL TREE TRANSFORMATIONS
Ziyu Yao*
Frank F. Xu, Pengcheng Yin
The Ohio State University yao. 4 470.0su..ee..
Carnegie Mellon University
(fangzhex, pcy1 n) 8cs cmu.
Huan Sun
Graham Neubig
The Ohio State University sun. 39w0099..ee0.....
Carnegie Mellon University gneubigêcs cmu. edu
ABSTRACT
While most neural generative models generate outputs in a single pass, the human creative process is usually one of iterative building and refinement. Recent work has proposed models of editing processes, but these mostly focus on editing se- quential data and/or only model a single editing pass. In this paper, present generic model for incremental editing of structured data (i.e. "structural edits") "). Particularly, we focus on rree-structure data, taking abstract syntax trees of com- puter programs as our canonical example. Our editor learns to iteratively generate tree edits (e.g. deleting or adding subtree) and applies them to the partially edited data, thereby the entire editing process can be formulated as consecutive, incre- mental tree transformations. To show the unique benefits modeling tree edits directly, we further propose a novel edit encoder for learning to represent edits, well as an imitation learning method that allows the editor to be more robust. We evaluate proposed editor two source code edit datasets, where results show that, with the proposed edit encoder, our editor significantly improves accuracy over previous approaches that generate the edited program directly in one pass. Finally, we demonstrate that training our editor to imitate experts and correct its mistakes dynamically can further improve its performance.
INTRODUCTION
Iteratively revising existing data for a certain purpose is ubiquitous. For example, researchers repet- itively polish their manuscript until the writing becomes satisfactory; computer programmers keep editing existing code snippets and fixing bugs until desired programs are produced. Can we properly model such iterative editing processes with neural generative models?
To answer this question, previous works have examined models for editing sequential data such as natural language sentences. Some example use cases include refining results from first-pass text generation system (Simard et al. 2007 Xia et al.) 2017), editing retrieved text into desired outputs
(Gu al. 2018 Guu al. 2018)) or revising sequence of source code tokens (Yin et al. 2019 Chen et al. 2019 Yasunaga & Liang 2020). These examples make single editing pass by directly generating the edited sequence. contrast, there are also works on modeling the incremental edits of sequential data, which predict sequential edit operations (e.g. keeping, deleting or adding a token)
either in a single pass (Shin et al. 2018 Vu & Haffari 2018 Malmi al. 2019 Dong al. 2019
Stahlberg & Kumar 2020 Iso et al. (020) or iteratively (Zhao et al. 2019 Stern et al. 2019 Gu
et al. 2019 9a b). or modify sequence in a non-autoregressivv way (Lee et al. (2018).
However, much interesting data in the world has strong underlying structure such trees. For ex- ample, a syntactic parse can be naturally represented as a tree to indicate the compositional relations among constituents (e.g. phrases, clauses) in sentence. A computer program inherently is also tree defined by the programming language's 's syntax. In the case that this underlying structure exists, many edits be expressed much more naturally and concisely transformations over the under- lying trees than conversions of the tokens themselves. For example, removing a statement from a
Work done while interning CMU.

---

Published as a conference paper at ICLR 2021
computer program can be easily accomplished by deleting the corresponding tree branch opposed to deleting tokens one by one. Despite this fact, work on editing tree-structured data has been much more sparse. In addition, it has focused almost entirely single-pass modification of structured outputs as exemplified by Yin et al. (2019); Chakraborty et al. (2220) for computer program editing.
In this work, are interested in a generic model for incremental editing of structured data ("struc- tural edits ")) Particularly, we focus on tree-structured data, taking abstract syntax trees of computer programs as our canonical example. We propose neural editor that runs iteratively. At each step, the editor generates and applies a tree edit (e.g. deleting or adding a subtree) to the partially edited tree, which deterministically transforms the tree into its modified counterpart. Therefore, the entire tree editing process can be formulated as consecutive, incremental tree transformations (Fig.
While recent works (Tarlow et al. 2019; Dinella et al. 2020: Brody al. 2020) have also examined models that make changes to trees, our work is distinct from them in that: First, compared with Dinella et al. (2020), we studied different problem of editing rreestructured data particularly triggered by an edit specification (which implies certain edit intent such as code refactoring rule). Second, we model structural edits via incremental tree transformations, while Tarlow et al. (2019) and Brody et al. (2020) predict a complete edit sequence based on the fixed input tree, without applying the edits or performing any tree transformations incrementally. Although Dinella et al. (2200) have explored similar idea, our proposed tree editor is more general owing to the adoption of the Abstract Syntax Description Language (ASDL:; Wang et al. (1997)). This offers our editor two properties: being language-agnone and ensuring grammar validity. In contrast, [Dinella et al.) (2200) include JavaScript-speciff design and employ only ad-hoc grammar checking. Finally, our tree editor supports comprehensive
of operations such as adding or deleting a tree node and copying a subtree, which can fulfill a broad range of tree editing requirements. These operations are not fully allowed by previous work, e.g., Brody et al. (2020) cannot add (or generate) a new tree node from scratch: Tarlow et al. (2019) and Dinella et al. (2200) do not support subtree copying.
We further propose two modeling and training improvements. specifically enabled by and tailored to our incremental editing formalism. First, we propose new edit encoder for learning to represent the edits to be performed. Unlike existing edit encoders, which compress tree differences at the token level (Yin et al.] 2019; HHoag et al.) 2020 Panthaplackel et al., 2020b) jointly encode the initial and the target tree pairs their surface forms (Yin et al.J 2019). )) our proposed edit encoder learns the representation by encoding the sequence of gold tree edit actions. Second, we propose novel imitation learning (Ross et al., 2011)) method to train our editor to correct its mistakes dynamically, given that it can modify any part of tree any time.
We evaluate our proposed tree editor on two source code edit datasets Yin et al. 2019). Our ex- perimental results show that, compared with previous approaches that generate the edited program in one pass, our editor can better capture the underlying semantics of the intended edits, which allows it to outperform existing approaches by more than 7% accuracy in a one-shot evaluation setting. With the proposed edit encoder, our editor significantly improves accuracy over existing tfate-of-the-ar methods on both datasets. We also demonstrate that our editor can become more robust by learning to imitate expert demonstrations dynamically, Our source code is available at https:/ htt.//tttuuuu.... wwm.coomnnueeoee http://eulaaabiiinee
ab/ httb///nccreeetaaa///.mmma _ttte_eeeed___
2 PROBLEM FORMULATION
As stated above, our goal is to create a general-punee purpose editor for tree-structured data. Specifically, we are interested in editing tree structures defined following an underlying grammar that, for every parent node type, delineates the allowable choices of child nodes. Such syntactic tree structures, like syntax trees of sentences or computer programs, are ubiquitous in fields like natural language pro- cessing and software engineering. In this paper we formulate editing such tree structures as revising an input tree C__ into an output tree C.,, according to an edit specification A. As a concrete example, we use editing abstract syntax trees (ASTs) of C# programs, as illustrated in Fig. 1 This figure shows transforming the AST of "x=list. ElementAt (i+1)" (C_) to the AST of "x=list [i+1]" (C4). In this case, the edit specification A could be interpreted as refactoring rule that uses the bracket operator [ ] for accessing elements in a list In practice, the edit specification is learned
'The corresponding Roslyn analyzer in C# can be found at https: tttp::///ghhhh..otee/e thub. wtwab.ccm//osseeee www../////s..r.tt.... Ros huallyynatorr/bccc/aasseeee// http://aaaaaaaaaasaaaaesee
2

---

Published as a conference paper at ICLR 2021
(mz 81
St
Operalor Preciction
[eeette, Add,
{m
copySubiree. Stop)
GENN
LSTM
Node Selection
Node [MethodCel1]
Bumurtui
9t graph-based free encoder
La
& tree history encoder
Add Add[tsken]or
Inpul free:
CopySubbEree [subtteee 91]
list. ZlenentAt (1+1)
edit dececer
(c) Iterative edit generation
Aos
AssignGant
(AesimSimi)
AtskprStmt
Tree: Tree:gt-1 (after editing)
(ummy
Birnentoccesg
(lemutshcoer)
Darmenee
St
Node (Methodial1]
[Dunny]
[Dumny]]]
[Durmny2]
Edit Action ay:
Delate
Add ElementAccess]]
Add token "limt")
CopySubTree
Jow feongil
(b) Edits from "x 1ist. Zlementàt "x list[s+1]" Dummy nodes are
automatically added based on ASDL grammar. The last edit action Stop at 1-5 omnited.
Figure 1: Our proposed neural editor for editing tree-structured data.
by an edit encoder fa from a pair of input-output examples (C",, C+.), and encoded as real-valued edit representation, iee. fa(C', C4) IR. The learned edit representation could then be used to modify C_ in similar way as editing C²_ Onwards we use fa as simplified notation for edit representations.
Revising a tree into another typically involves sequence of incremental edits. For instance, to modify the input tree in the aforementioned example, one may first delete the subtree rooted at the node MethodCall, which corresponds to the code fragment "list. ElementAt (i+1)", and then replace it with an ElementAceess node denoting the bracket operator, etc. formulate this editing process
sequential decision making process ((g1, ((91,a))... ai)....... (gr, (T)), where for each tree Jr at time step f, the editor executes a tree edit action at, deterministically transforming into I++1- In particular, 91 is the initial input tree The process stops at gr when the editor predicts a special Stop action as aT. Denoting Sıa (gI,...,9t) as the tree history and dir = (aI,... ae) the edit history until step then the editing can be framed as the following autoregressive process:
T
p(arrlfa.91) plal
p(aT fa.9IT) II p(a, g1.)). (1)
MODEL
We will introduce neural editor for modeling p(acl-) in 3.1 followed by the edit representation
model fa in 8 3.2
3.1 NEURAL TREE EDITOR
Fig. Ic) illustrates our editor architecture. At each time step, the editor first encodes the current tree Ir and the tree history I1:t- It then employs modular decoder to predict tree edit action a. Next, we will first introduce our tree edit actions and then elaborate the model details.
3.1.1 TREE EDIT ACTIONS
Our editor uses sequence editing actions to incrementally modify a tree-structured input. At each time step, the decoder takes action a to update partially-edited tree dt- Specifically, an action a, consists an operator (e.g. an operator that removes a subtree from gi) with its optional arguments (e.g. the target subtree delete). Importantly, the space of actions is limited to maintain consistency with the underlying syntax of the language. While a number of syntactic formalisms such context free grammar (Chomsky 1956) or tree substitution grammar (Cohn al.) 2010) exist, in this work we choose the ASDL formalism due to its ability to flexibly handle optional and sequential fields (interested readers may reference Wang al. (1997) and Yin & Neubig (2018) for details). Under this framework, we define four types of operators.
Notably, the special case of empty initial trees corresponds code generation from scratch. Thus formulation applics to both tasks of editing existing trees and generating new
3

---

Published as a conference paper at ICLR 2021
Delete operators take tree node n, as argument and remove n, and its descendants from It (e.g. t= 1 in Fig. Ib)). Note that removing arbitrary (child) nodes from Ie might produce syntactically invalid trees, since under the grammar, parent node type would always have fixed set of edge types. For instance, if the node MethodCall and its incoming edge r right were to be removed at = 1, the resulting AST would be syntactically invalid under C#'s grammar, as the node AssignStmi denoting a variable assignment statement is missing a child node representing its right operand. To maintain syntactic correctness (no missing child nodes for any parent nodes), we therefore replace the to- ne-be-deleted node with pseudo Dummy node as a placeholder.
Next, we define an Add operator to add new nodes to gt- The operator first locates a target position by selecting an existing tree node. We consider two cases based on the edge type (or "field") of the target position: for single or optional fields that allow at most one child (e.g. field right in Fig. 1b)) at 1 = 1), the selected tree node has to be their dummy child node (e.g. node Dummy at t = 1) and the Add operator will then replace the dummy node with the new tree node; for sequential fields that accept more than one child (e.g. the field of "statement block" that allows an arbitrary number of statements), the selected tree node can be any child node of the field (including a rightmost dummy node append to every sequential field) and the Add operator will then insert the new node before the selected node. We elaborate this mechanism in A.I For our editor, adding a non non-terminal node (e.g. node ElementAccess in Fig. [b) at / 2) is equivalent selecting a production rule
to derive its field (e.g. AssignStnt night
ElementAccess) As with Delete actions, to ensure there is no missing child node, we instantiate the set of child nodes with dummy nodes for the newly added node based on the underlying grammar, which leads to nodes Dummy1 and Dummy2 at /. 2. Add can also be used to populate empty terminal nodes with actual values (e.g. string token "list" at t = 3). This is the same as picking a token from the token vocabulary.
Additionally, observing that in many cases, revising a tree can be easily done by copying subtree from the initial input gi (e.g. subtree Expr + i in Fig. Ia)) to a new position in the updated tree (e.g. the right child position of node El ElementAcces in Fig. Tb) at 4), we introduce a high-level operator CopySubTree. This operator locates a target position similarly as the Add operator and then copies complete subtree from 91 to the target position in a single step.
Finally, Stop action is used to terminate the iterative tree editing procedure, after which the remain- ing dummy nodes will be cleared. We note that our framework has decoupled the language grammar specifications (handled by ASDL) from the model architecture (corresponding to our language- agnostic model implementation). and thus can be applied to various languages flexibly.
3.1.2 TRFE AND TREE HISTORY ENCODER
Similarly to existing works in learning tree representations (Allamanis et al. 2018: Brockschmidt cet al. 2018, Yin et al. 2019 Hellendoorn et al. 2020), we adopt graph-based encoder learn representations of each tree gt- Specifically, we follow Alllmaanis et al. (2018), and extend 9t into a graph by adding bidirectional edges between parent and child nodes, as well as adjacent sibling nodes. We use gated graph neural network (GGNN, Li et al. (2015) to compute a vector repre- sentation n. for each node n4 on tree gt, and mean-pool (n,) } to represent gt. denoted gt.
An LSTM encoder is used to track the tree history fi:t, i.e denotes vector concatenation. We will introduce how to learn the edit representation fa in 3.2 The updated state 8, is then used to predict edit actions, elaborated next.
LSTM((g;; fa), 8:-1), where [::-]
3.1.3 TREE EDIT DECODER
Our edit decoder predicts an action dt using three components: an operator predictor, node selector, and a value predictor. At each time step t, the decoder's operator predictor first decides which operator op, E (Delete, Add, CopySubTree, Stop} to apply. Next, for operators other than Stop, the node selector predicts a node n, from the tree to locate the target position for applying opt- Finally, if op, E (Add, CopySubTree). the value predictor further determines additional arguments of those operators (denoted as val,, e.g. the to-be-added node for Add). This is summarized as:
p(a st) = p(op, 8t p)))p, st op,)) (val, (s ny).
(2)
Operator Prediction: The operator prediction is a 4-class classification problem. We calculate the probability of taking operator op, as p( ((op,ls.) = softmax (Wap 8t + bop)
4

---

In this section, we present a novel edit encoder which instead shifts the modeling focus completely to the largeted edit actions themselves. Specifically, it learns an edit representation by directly Published as a conference paper at ICLR 2021
Node Selection: Given tree 9t, there could exist arbitrary number of tree nodes. Therefore, we design the node selection module similar to a pointer network (Vinyals et al. 2015). To this end, we learn hidden state node, tanh node emb( (mb((pp)) embeds the previously selected operator op,- In our model, "emb(.)" denotes learnable embeddings. We then calculate the inner product of hodee, and each node representation n4 for node selection.
made) as the "pointer", where
The value predictor predicts an argument cal, for Add and CopySubTree actions. For Add actions, val, denotes the new tree node (corresponding to a production rule or a terminal token) to be added to g.. For CopySubTree actions, valy the subtree from 91 to be copied to Jt- In both cases, we only consider the candidate set {valc} allowable under the grammar constraints. Similarly to the node predictor, the distribution p( ((valel-) is also given by a pointer network, with its hidden state defined as heat, = tanh W val (8t; nh; emb(pn, - nz]] + beal) where emb(pn, m)) the embedding of the edge type between the parent node Pn, and the child n, (e.g. field right right for AssignStmt - ElementAccess) Depending on the type of valt, its representation could be either learned embedding of the production rule, word embedding, or subtree encoding given by the representation of its root node. We refer readers to A.2 for details.
Value Prediction:
3.2 TREE EDIT ENCODING
Given an edit pair (C_,Ch, C+),, aim to learn real-valued vector fa(C_, to represent the intent behind the edits. This is a crucial task and has been investigated several previous works. For example. Yin al. (2019), Panthappackel et al. (2020b), and Hoang et al. (2020) considered edits at the token level and used either a bag-of-edits encoder or sequence encoder to encode the differences between C_ and C'., a result, these edit encoders have abandoned the syntactic structure of tree edits. Yin et al.) (2019) further proposed graph edit encoder, which connects the input and output trees with labeled edges such as "Removed" and "Added", and then encodes the connected trees via a graph neural network. Although structural tree differences have been expressed in this edit encoder, the differences are modeled rather implicitly as the edit encoder has simply treated them as additional graph features.
encoding the sequence of structural edit actions (d1, dg.... ar) that transforms C- to C4. The encoder first computes representation a, for each action at, depending on the type of its operator:
Ogeap
W op emb(Stop) + bstop-
aDolete Weelete (emb(eelteDDD)) emb(pn, + bpelete:
Wa Waaglemb(Add); ny; emb(p,, embb) emb( wal.)] + baad;
Oada
ACopySahTrea
W (eoppaatteeeeeb/CCopyuuuul
n4; em;;ee,b(,,.,.,. emb(sub(reee) + beopySubTres-
The proposed edit encoder then feeds the sequence of action representations {ar into a bidirec- tional LSTM, whose last hidden state used as the edit representation fa(C'_,C) C4).
3.3 TRAINING AND INFERENCE
We jointly train the proposed editor and the edit encoder in an autoencoding style, following Yin et al. (2019). Specifically, given an edit pair (C_, C+)) the training set, we assume a gold-standard edit action sequence d'r which edits C_ to C+ (e.g. the edit action sequence in Fig. 1p. We seek to
maximize the probability of lf C+), C-) in training By decomposing the probability according to Eq. (2). this equivalent to jointly maximizing the probability of each edit decoder module making the gold decision at each time step. In practice, we use dynamic programming (pseudo code can be found in 1 to calculate the shortest tree edit sequence as ai.r and compute cross entropy loss for each edit decoder module.
(C=, C+) is real-valued vector and thus does not directly expose C.. We set it a low dimension following Yin et al. 2019) which bottlenecks the vector's ability to memorize the entire output.
We assume leit-to-right, top-down order when comparing the input/output tree. Future work can also consider other orders improve the editing quality (Gu et al. 2019a Welleck et al. 2019 Gois al. 2020
5

---

Published as a conference paper at ICLR 2021
At inference time, given input tree C_ and an edit representation fa (calculated either from C4) or another edit pair (C"_, C,,)), we generate one tree edit at each time step t by greedily deciding the operator, the node and the value. The generated edit is then applied to the tree so transits to -++1 deterministically. We then update the tree history representation 8t+1 for generating the next tree edit. The inference process ends when a Stop operator is chosen.
4 ROBUST STRUCTURAL EDITING VIA LMITATION LEARNING
A unique advantage that distinguishes our editor from existing ones is its potential to fix wrong edits and iteratively refine its own output. This is achievable because our editor can revise any part of a tree at any time. We investigate this hypothesis by training the proposed editor via imitation learning, where the editor learns to imitate gold edit actions ("expert demonstrations") under states it visits at the inference time. Here, define "state" 9t to include the current tree history 91.t and the edit representation fa. Our learning algorithm follows DAGGER (Ross et al. (01I]. where in each training iteration, for given (fa,C_, (_,,C)) tuple, we first run the editor to infer and apply sequence of edits resulting in a "trajectory" of (($1, ((s1,a1). a1)..., (sr,ar)). We then request a gold edit action nt (s²) for each state 8, visited by the editor. The collected state-gold edit action pairs aggregated to retrain the editor for the next iteration. This sampling and demonstration collecting DAGGERSAMPLING
is shown in Algoo I (Appendix B). Note that, in practice, instead of sampling a trajectory solely from the learning editor TT, the DAGGER algorithm samples from mixture policy n', with which the actual edit action a, at each step t comes from either me with a probability of 1 - 3 or the "expert" xt" with probability of (3.
strategy (denoted
To simulate the "expert", we calculate "dynamic oracles" (Goldberg & Nivre 2012) by comparing the current tree with the target output tree. For example, in Fig. 1] if our editor incorrectly takes "Add (AssignStmt + Expr]" at é = 2, the dynamic oracle will produce "Delete [Assignt maaagnStmtt + Expr] as the gold edit action at ( 3 to revoke the wrong edit. This thus provides a means for the editor to learn to correct mistakes that it will likely produce at inference time.
Preliminary results showed that the editor trained following DAGGERSAMPLING may fall into loop of repetitively deleting and adding the same component. We hypothesize that teaching the editor to imitate experts under unstable states (i.e. amid its initial full pass of editing) could be detri- mental. Therefore, we propose another sampling strategy, POSTREFINES AMPLING, which samples and collects sate-action pairs from the expert as a post refinement step (Algo. 2 in AApeeddxx B). Specifically, we first run our editor to finish its sequential editing, which gives the output tree gr (Line 2). If gr is different from target C+,, we run the expert policy x continue editing until it successfully reaches C+,, and return state-action pairs collected from the expert as training material for the editor (Line 3-5). When gr is correct, no further training data will be collected (Line 6-8).
5 EXPERIMENTS
5.1
EXPERIMENTAL SETUP
We test our methods on two source code edit datasets introduced by Yin et al. (2019), also largely following their experimental setting.
The GitHubEdits (GHE) dataset contains (C_,C4) pairs and their surrounding context collected from the commit logs of 54 GitHub C# projects. The dataset is split into train/dev/test sets of 91,372/ 1..72/10,,176 10,176 10,176 samples. jointly learn an edit representation fa(C_,Co C-) while training the editor to generate C., from C_. evaluation, we measure the accuracy of each editor based on whether they successfully edit C_ to the exact gold C4. Since the edit representation SA is calculated from the targeted (C',, C+) pair, we denote this setting as GHE-gold.
The second dataset, C#Fixers (Fixers), is relatively small, containing 2,878 (C=,C4) pairs. Unlike GHE, edit pairs in Fixers are built using 16 C# "fixers" with known semantics (e.g. removing redundant parentheses
way to perform refactoring). As standard, we this dataset only for testing purposes (i.e. all methods are first trained on CHE-gold), We consider a Fixers-gold setting similar GHE-gold to evaluate the accuracy of generating C,, from (fa(C_, C.),
Since edits in Fixers have known semantics, we also use Fixers to test methods in a one-shot setting (denoted as Fixers-one shot): For each (C_,C+) pair, select another (C',, (C,, pair from the

---

Published as a conference paper at ICLR 2021
same fixer category (which bears the same edit intent as (C_, C+) but is applied to different input) to infer the edit representation and evaluate the accuracy of generating C+ from (fa (C', C² ). C-). We follow Pantoaaaaanaaaateee backupppppallele et al. (2020a) and pick the first 100 samples at most per fixer category (the "seeds"), compute an edit representation of each one, and apply it to edit the others. We then report an average accuracy over the seeds the score for this fixer category. Because the sample size of each fixer category is highly imbalanced, we report both macro average (treating all categories equally) and micro average (dependent on the sample size) edit accuracies over the 16 fixer cate- gories In this one-shot evaluation, higher accuracy also implies that the learned edit representation generalizes better from the specific edit pair to represent the semantics of an edit category.
Compared with GHE/Fixers-gon gold, the Fixers-one shot setting is somewhat more realistic, since in practice one could only provide similar edits on other input trees as the edit specifications. However, GHE/Fixers-gol provides a more controllable learning benchmark. It investigates how well an editor can perform when its given edit representation has encoded the exact desired edits on the given input. Note that this is not trivial task as the edit representation has been "bottlenecked" within single continuous vector. Particularly for GHE, it covers way more diverse edit patterns than the 16 fixer categories by Fixers, making the GHE-gold evaluation also challenging. Consequently, in our experiments, we examine each model by analyzing their performance on all evaluation settings.
Baselines: We compare proposed neural editor (denoted as "Graph2Edit" f with two state- of-the-art editors: (1) Graph2Tree (Yin et al. 2019), a model that, like ours, represents a program in its AST form and models the editing of tree-structured data. However, instead of generating sequence of incremental edits, it decodes the edited tree in one pass; (2) CopySpan (Panthaplackel] al., 2020a),, a model that represents programs as sequences of tokens and edits them by directly generating the edited code tokens from scratch.
We also experiment with two edit encoders for learning edit representations. Besides our proposed structural edit encoder (denoted as "TreeDiff' Edit Encoder"). ) we consider a sequence edit encoder, which uses a bidirectional LSTM to compress three pieces of information: code tokens in C²_, code tokens in C4. as well as their differences represented by sequence of predefined edit tags (e.g. delete, add, or keep). This edit encoder (denoted as "Seq Edit Encoder") was shown offer more precise and generalizable edit representations than others tested in Yin et al. (2019).
In experiments, we reproduce and test baselines by using implementations kindly provided by their authors. We include all configuration and implementation details in Appendix C
5.2 MAIN RESULTS
Tab.
shows our experimental results, where we examine two questions:
(1) How does our incremental editor compare with one-pass baselines? On Fixers-one shot, when all editors use the Seq Edit Encoder. our editor outperforms others substantially by more than 9% macro accuracy and 7% micro accuracy. This im- plies that our editor is better at capturing generalizable semantics underlying the ed- its. Given that all editors use the same archi- tecture for the edit encoder, this also means that our editor encourages better edit repre- sentation learning in the edit encoder. The outstanding generalization ability of our editor demon- strates the advantage of modeling incremental edits; when our editor is trained to generate the edits rather than the edited tree from scratch, it implicitly drives its edit encoder to learn to capture the salient information about the edits (otherwise it has no means to generate the accurate edit sequence).
Table I: Test accuracy (%) of different editors and edit encoders. See more comparisons in D. Model
GHE-gold Fixers-gold
Fixers-one shot
macro miero
w/ Seq Edit Encoder:
CopySpan
67.40
87.07
20.64
24.20
Graph2Tree Graph2Edit
$7.13
79.48
28.49
35.53
54.49
71.90
37.49
42.55
w/ TreeDiff Edit Encoder:
Graph2Tree
67.06
82.35
36.17
42.35
Graph2Edit 69.35
91.59
36.10
41.34
Intriguingly, we observe inverse performance from the three editors when their edit representation is or is not inferred from the gold edit pair; editors performing better on GHE/Fixers-goll. (CopySpan
Note that this one-shot evaluation procedure is different from the one used by Yin et al. 2019), so the results from Table 5 Yin et al. (2019) are not comparable to ours. See C.T details. ""Graph" simply indicates the use of graph neural network encode tree.
7

---

Published as a conference paper at ICLR 2021
Table 2: Edited programs C+ from each editor (w/ Seq Edit Encoder) given (fa( on Fixers. We show where our editor succeeds (Example 1) and fails (Example 2). More examples can be found in D.2
Example
Example
: (VARO new SclectString(VAR1. VAR2. ToStrngg) C VARD. VARt- ColBegin;
+LITERAL)) ShouldBe (VARL))
C VARO. VAR1-VAR2. ColBeei,:
(VARD, SelectString(VAR1. (AAAH////VAAA..AR22HTTRR))))))) (VAR1);
C4)
C- ParsisatAeync((AROO,, VARI=>
wal.:eednaarrarna1aee Tall (VAR1. VAR2.
C_: VARD= (Excepttion)
ToString((+LLTEEALLLWA .ncreeeeettdddeeee
BrceptionrrooPPrttoWWCC Cause);
C4: PersictAryy=< wendta (VAR VAR2+
C. var VARC-VAR1.
Bxceptioofrro/PooooWWe (VAR2. Cause)
CupySpan
C+: ParsistasymccVABB VAR1=>-eendr.. Seaidderr.olllla..... TeR1(VAR1. VAR2+
O var VARO=VAR1.
+ VAR3. Itt.creeeeetttddeee(e)))
ExceptiooFFoo/rrtoo
Graph2Tree
C+ var VARO=VAR2, Cause;
VAR2+LITEMAL) IncrementtAdGGee ());
Graph2Edit C+: PermistAeyne (aallaameeeseaooo..11----soeee Tell(VAR1. VAR2+
C+: var VARG-WAR2 Cause;
LITERAL-VAR3 [ncressentttadeG):())))
Graph2Tree > Graph2Fdit) consistently obtain worse accuracies Fixers-one shot (CopySpan < Graph2Tree < Graph2Edit). We conjecture that when Seq Edit Encoder jointly trained with the baseline editors, it tends to memorize the specific patterns about C+ opposed to the generalizable information about the edits when trained with our editor, because the baseline editors are trained to decode the exact content of C+ from scratch. In comparison, this phenomenon is less prominent for Graph2Tree and more for CopySpan, since the former generates C+ in the form of an AST tree while the latter generates Cy. in the form of token sequence (which is exactly how C+. is encoded by the Seq Edit Encoder).
Case study & expressivity of structural edits: We further showcase the generation from each ed- itor (with Seq Edit Encoder) in the Fixers-one shot setting (Tab. 2). Example illustrates typical cases where our editor Graph2Edit succeeds while the bascline editors fail. The example is about re- moving a redundant ToString call. Our editor learns to transfer and apply this editing pattern even when the input tree C_ is very different from C"_, while other editors behave very sensitively to the specific content of C_. This is because, from the perspective of our editor, the edits required by subtree cor-
(C',.C,) and (C_, C+) are the same, both first deleting an Invocati www.aaiiinnxxpsssssi..m responding to "VAR1. V.R.. ToString()) and then copying back its AemberAccessExpp subtree corresponding to "VAR1. VAR2". In fact, we observe that in many cases, the actual tree edit that our editor needs to perform is irrelevant the surface form of the input tree C_. As our editor is trained to generate the actual tree edits, together with Seq Edit Encoder, it learns a better alignment between changing at the token level (e.g. from "VAR1. VAR2. ToString ()" to "VAR1. VAR2") and performing targeted edits at the tree level.
inn
On the other hand, this also means that our editor may fail when the desired edits for (C_, C+) bears a very different structure from the edits of (C',, C4), even if they very close the token level. Example 2 illustrates this situation where our edi- tor fails. In this example, editing C" involves removing a redundant type cast from MemberAccessExpressii on subtree (corresponding to "VAR2.ColBegin ColBegin") while the desired edits for C'_ require detaching the type cast from an Invocati InvocationExpressiic (VAR2.Cause)") Cause)"), "). Therefore, even if our editor can precisely capture
subtree (corresponding to
"VAR1 Exceptionnnii.....e onFromProto (VAR2. the structural edits expressed in (C",C",) it cannot edit C_ correctly. We observe that Graph2 Tree could also sensitive to this phenomenon while CopySpan runs successfully (although in many other cases, CopySpan produces ungrammatical programs, as we enumerate in 3 D.2).
Finally, we note that our editor also performs comparably with or better than Graph2Tree when they are both equipped with TreeDiff Edit Encoder, will discuss next.
(2) What is the influence of edit encoding? When replacing the Seq Edit Encoder with TreeD- iff Edit Encoder, we observe significant improvement for both Graph2Tree and Graph2Edit on GHE/Fixers-gol in the meantime, their performance on Fixers-one shot is comparable to the best accuracy. This implies that our proposed edit encoder is able to learn both more expressive and more generalizable edit representations. Particularly for our proposed Graph2Edit, it clearly outperforms Graph2Tree GHE//Fixers-gon gold and is comparable to the latter on Fixers-one shot.
8

---

Published as a conference paper at ICLR 2021
However, also notice that for Graph2Edit, switching to the TreeDiff Edit Encoder only helps the GHE/Fixers-gold scenario and results in a slight performance drop in the one-shot setting. This is likely because Graph2Edit has overfit to the specific edit representations during training, the same issue that CopySpan confronts, when the target outputs of the editor (ground-truth tree edits for Graph2Edit and ground-truth code tokens for CopySpan) have been exposed to the edit encoder (TreeDiff Edit Encoder for Graph2Edit and Seq Edit Encoder for CopySpan) in exactly the same format. We note that the issue comes with the fact that all models are trained on the GHE-gold training set while only tested on Fixers-one shot (see $ 3.3 and & 5.1). It would be ideal to train and test model on the Fixers-one shot setting, but the Fixers dataset is not large enough for this to be feasible. We leave such an evaluation as an important topic to explore in the future.
Finally, in $ D.3 we show the nearest neighbors of given edit pairs based on their edit representa- tions, which qualitatively also demonstrate the superiority of TreeDiff Edit Encoder.
5.3 IMITATION LEARNING EXPERIMENTS
We finally demonstrate that training our editor via imitation learning makes it more robust. We con- sider two data settings: 20% or full training data. In each case, we first pretrain our editor with gold edit sequences on the training set via supervised learning, equivalent to setting 3 to 1 in the first iteration of imitation learning, a commonly adopted strategy for DAGGER (Ross et al. 2011]. We then run another iteration of imitation learning on the same training set to sample states and collect dynamic expert demonstrations, following either DAGGERS AMPLING (Algo. T) or POSTREFIN SAMPLING (Algo. 2). Empirically, we observe worse performance when setting / = in DAGGER- SAMPLING. This is likely because in the editing tasks we experiment on, offering one-step expert demonstrations is not enough to teach the model complete all the remaining edits successfully. We eventually set 3 = 0.5. We include the experimental details and an analysis in 5 D.4
For the base editor, we use "Graph2Edit w/ Seq Edit Encoder," which is more prone to mistakes than "Graph2Edit w/ TreeDiff Edit Encoder" and thus presumably better testbed for robust learning algorithms. The experimen- tal results are show in Tab. 3 In the 20% training data setting, imita- tion learning improves supervised learn- ing slightly with DAGGERSAMPLING and by 1.5% accuracy with POSTRE- API.NM. Our analysis shows that the editor trained using DAGGER- SAMPLING learns to correct its previous wrong edits (e.g. Delete ["VAR1"] then Add [ Strringg")) However, may also fall into a local loop of repetitively deleting and adding the same component, which makes its edit length (T) generally longer than other editors. This situation is neatly remedied by using POSTREFINESAMPP AMPLIIGG to collect expert demonstra- tions. With this strategy, although we train the editor to correct its wrong edits as a post refinement step, the well trained editor is indeed enhanced to be more robust in making correct decisions in its initial full pass of editing (rather than making wrong decisions then revoking them). This strategy also improves the base editor under the full training data setting slightly.
Table 3:
Test (dev) accuracy by % of Graph2Edit w/ Seq Edit Encoder on GHE-gold after one iteration of imita- tion learning. Examples (simplified) illustrate how the base editor works when trained via supervised learning with different imitation learning strategies. Colors in- dicate correct or incorrect edits.
Supervised
DAGGER
POSTR
w/ 20% data w/ full data
42.30 (44.22)
42,70 (45 03)
43.94 (46.10)
54.49 (55.43)
53.85 (55.57)
54.91 (56.48)
Example
AddLTd->Tokees Add VAR1")
Add Tokkkn)) Add ["VARL")
Add Tokeoo
Add (Strllgg)")
Del ["VAR1")
Add [dd[" ["BtringX"]
Avg. edits (T) 7,480
11.549
7.594
6 CONCLUSION AND FUTURE WORK
This paper presented a generic model for incremental editing of tree-structured data and demon- strated its capability using program editing as an example. In the future, this model could be extended to other tasks such syntax-basee grammar error correction (Zhang & Wang] 2014) and sentence simplification (Feblowitz & Kauchak 2013), or incorporate natural language- based edit specification, where the editing process is triggered by natural language feedback or commands
(Suhr et al. 2018 ZZang al. 2019 Yao et al. 2019 2020 Elgohary et al. 2020).

---

Published as a conference paper at ICLR 2021
REFERENCES
Miltiadis Allamanis, Mare Brockschmidt, and Mahmoud Khademi. Learning to represent programs with graphs. In International Conference on Learning Representations, 2018. URL https:
//openeeveww.co new. wtr./oormmmmmm www.umm/oaEaaee....
Marc Brockschmidt, Miltiadis Allamanis, Alexander L Gaunt, and Oleksandr Polozov. Generative code modeling with graphs. In International Conference on Learning Representations, 2018.
Shaked Brody, Uri Alon, and Eran Yahav. A structural model for contextual code changes. Pro- ceedings of the ACM on Programming Languages, 4(00PSLA):1-28, 2020.
Saikat Chakraborty, Yangruibo Ding, Miltiadis Allamanis, and Baishakhi Ray. CODIT: Code editing with tree-based neural models. IEEE Transactions on Software Engineering, 2020.
Zimin Chen, Steve James Kommrusch, Michele Tufano, Louis-Noël Pouchet, Denys Poshyvanyk, and Martin Monperrus. Sequencer: prruuence-o-sequeeee learning for end-to-end program repair. IEEE Transactions on Software Engineering, 2019.
Noam Chomsky. Three models for the description of language. IRE Transactions on information theory, 2(3):1 1956.
Trevor Cohn, Phil Blunsom, and Sharon Goldwater. Inducing tree-substitution grammars. The
Journal of Machine Learning Research, 11:3053-3093 3096, 2010.
Elizabeth Dinella, Hanjun Dai, Ziyang Li, Mayur Naik, Le Song, and Ke Wang. Hoppity: Learning graph transformations to detect and fix bugs in programs. In International Conference on Learn- ing Representations, 2020.
net. wtt.:oooumm..-.eeess.....
Yue Dong, Zichao Li. Mehdi Rezagholizadeh, and Jackie Chi Kit Cheung. EditNTS: An neural programmer-interprece, model for sentence simplification through explicit editing. In Proceedings of the 57th Annual Meeting of the Association for Computational Linguistics, pp. 3393-3402,
2019.
Ahmed Elgohary, Saghar Hosseini, and Ahmed Hassan Awadallah. Speak to your parser: Interactive text-to-SQL. with natural language feedback. In Association for Computational Linguistics, 2020.
Dan Feblowitz and David Kauchak. Sentence simplification as tree transduction. In Proceedings of the second workshop predicting and improving text readability for target reader populations, pp. 1-10, 2013.
António Góis, Kyunghyun Cho, and André Martins. Learning non-monotonic automatic post-editing of translations from human orderings. In Proceedings of the 22nd Annual Conference of the European Association for Machine Translation, pp. 205-214, Lisboa, Portugal, November 2020. European Association for Machine Translation.
Yoav Goldberg and Joakim Nivre. A dynamic oracle for arc-eager dependency parsing. In Proceed- ings of COLING 2012, pp. 959-976, 2012.
Jiatao Gu, Yong Wang, Kyunghyun Cho, and Victor O.K. Li. Search engine guided neural machine translation. In Proceedings of the AAAI Conference Artificial Intelligence, volume 32, 2018.
Jiatao Gu, Qi Liu, and Kyunghyun Cho. Insertion-based decoding with automatically inferred gen-
eration order. Transactions of the Association for Computational Linguistics, 7:661-676, 2019a.
Jiatao Gu, Changhan Wang, and Junbo Zhao. Levenshtein transformer. In Advances in Neural Information Processing Systems, pp. 11181-11191, 2019bb.
Kelvin Guu, Tatsunori B Hashimoto, Yonatan Oren, and Percy Liang. Generating sentences by editing prototypes. Transactions of the Association for Computational Linguistics, 6:437-450, 2018.
Vincent J. Hellendoomn, Charles Sutton, Rishabh Singh, Petros Maniatis, and David Bieber. Global relational models of source code. In Internatiional Conference on Learning Representations, 2020. URLIhttpst pttttps://openreevvie wtwprrrrwweeeeeeeooorriiiiiie
1bRNNtT
10

---

Published as a conference paper at ICLR 2021
Thong Hoang. Hong Jin Kang. David Lo, and Julia Lawall. CC2Vee: Distributed representations of code changes. In Proceedings of the ACM/IEEE 42nd Interaational Conference on Software Engineering. pp. 518-529, New York, NY, USA, 2020. Association for Computing Machinery. ISBN 9781450371216, doi: 10. 10.1145/337781 13380061..
Hayate Iso, Chao Qiao, and Hang Li. Fact-based text editing. In Proceedings of the 58th Annual Meeting of the Association for Computational Linguistics, pp. 171-182, 2020.
Jason Lee, Elman Mansimov, and Kyunghyun Cho. Deterministic non non-autoregressive neural se- quence modeling by iterative refinement. In Proceedings of the 2018 Conference on Empirical Methods in Natural Language Processing, pp. 1173-1182, 2018.
Yujia Li, Daniel Tarlow, Marc Brockschmidt, and Richard Zemel. Gated graph sequence neural networks. arXiv preprint arXiv:1511.05493, 2015.
Eric Malmi, Sebastian Krause, Sascha Rothe, Daniil Mirylenka, and Aliaksei Severyn. Encode, tag, realize: High-precision text editing. In Proceedings of the 2019 Conference Empirical Methods in Natural Language Processing and the 9th International Joint Conference on Natural Language Processing (EMNLP-IJCNLP), pp. 5057-5068, 2019.
Sheena Panthaplackel, Miltiadis Allamanis, and Marc Brockschmidt. Copy that! editing sequences by copying spans. arXiv preprint trXiv:2006.0477,, 2020a.
Sheena Panthaplackel, Pengyu Nie, Milos Gligoric, Junyi Jessy Li, and Raymond Mooney. Learning to update natural language comments based on code changes. In Proceedings of the 58th Annual Meeting of the Association for Computational Linguistics, pp. 1853-1868, Online, July 2020b. Association for Computational Linguistics. doi: 10.18653/v1/2020 mcl-main.
Maxim Rabinovich, Mitchell Stern, and Dan Klein, Abstract syntax networks for code generation and semantic parsing. In Proceedings of the 55th Annual Meeting of the Association for Compu- fational Linguistics (Volume 1: Long Papers), pp. 1139-1149, 2017.
Stéphane Ross, Geoffrey Gordon, and Drew Bagnell. reduction of imitation learning and struc- tured prediction to no-regret online learning. In Proceedings of the fourteenth international con- ference on artificial intelligence and statistics, pp. 627-635, 2011.
Richard Shin, Illia Polosukhin, and Dawn Song. Towards specificationddiectedd program repair. Workshop Track at International Conference Learning Representations, 2018.
Michel Simard, Cyril Goutte, and Pierre Isabelle. Statistical based post-editing. In Human Language Technologies 2007: The Conference of the North American Chapter of the Association for Computational Linguistics; Proceedings of the Main Conference, pp. 508-515, Rochester, New York, April 2007. Association for Computational Linguistics.
Felix Stahlberg and Shankar Kumar. Seq2Edits: Sequence transduction using span-level edit op- crations. In Proceedings of the 2020 Conference on Empirical Methods in Natural Language Processing (EMNLP), pp. 5147-5159, 2020.
Mitchell Stern, William Chan, Jamie Kiros, and Jakob Uszkoreit. Insertion transformer: Flexible sequence generation via insertion operations. In International Conference on Machine Learning, pp. 5976-5985, 2019.
Alane Suhr, Srinivasan Iyer, and Yoav Artzi. Learning to map context-dependers sentences to exe- cutable formal queries. In Proceedings of the 2018 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, Volume I (Long Papers), pp. 2238-2243 2018
Daniel Tarlow, Subhodeep Moitra, Andrew Rice, Zimin Chen, Pierre-Antoine Manzagol, Charles Sutton, and Edward Aftandilian. Learning to fix build errors with graph2diff neural networks. arXiv preprint /91 2019.
Oriol Vinyals, Meire Fortunato, and Navdeep Jaitly. Pointer networks. In Advances in neural information processing systems, pp. 2692-2700, 2015.

---

Published as a conference paper at ICLR 2021
Thuy Vu and Gholamreza Haffari. Automatic post-editing of machine translation: A neural programmer--meerpeeer approach. In Proceedings of the 2018 Conference on Empirical Meth- ods in Natural Language Processing, pp. 103330048355 2018.
Daniel C Wang, Andrew W Appel, Jeffrey L Korn and Christopher S Serra. The zephyr abstract syntax description language. In DSL, volume 97, pp. 17-17, 1997.
Sean Welleck, Kianté Brantley, Hal Daumé lii, and Kyunghyun Cho. Non-monotonic sequential text generation. In International Conference on Machine Learning, pp. 6716-6726, 2019.
Yingce Xia, Fei Tian, Lijun Wu, Jianxin Lin, Tao Qin, Nenghai Yu, and Tie- Yan Liu. Deliberation networks: Sequence generation beyond one-pass decoding. In Advances in Neural Information Processing Systems, pp. 7784-1794, 2017.
Ziyu Yao, Yu Su, Huan Sun, and Wen-tau Yih. Model-based interactive semantic parsing: A unified framework and a text-to-SQL case study. In Proceedings of the 2019 Conference on Empirical Methods in Natural Language Processing and the 9th International Joint Conference on Natural Language Processing (EMNLP-IJCNLP)), pp. 5447-5458, 2019.
Ziyu Yao, Yiqi Tang, Wen-tau Yih, Huan Sun, and Yu Su. An imitation game for learning semantic parsers from user interaction. In Proceedings of the 2020 Conference Empirical Methods in Natural Language Processing (EMNLP), pp. 6883-6902, 2020.
Michihiro Yasunaga and Percy Liang. Graph-based, self-supervised program repair from diagnostic feedback. In International Conference Machine Learning (ICML), 2020.
Pengcheng Yin and Graham Neubig. syntactic neural model for general- panerrl-purpose code generation. In Proceedings of the 55th Annual Meeting of the Association for Computational Linguistics (Volume Long Papers), pp. 440-450, 2017.
Pengcheng Yin and Graham Neubig. TRANX:
A transition-based neural abstract syntax parser for semantic parsing and code generation. In Proceedings of the 2018 Conference on Empirical Methods in Natural Language Processing: System Demonstrations, pp. 7-12, 2018
Pengcheng Yin, Graham Neubig, Miltiadis Allamanis, Marc Brockschmidt, and Alexander L. Gaunt. Learning represent edits. International Conference on Learning Representations, 2019. URL
https:// //tpnreve///eeeeeeeww net /ttp://ooummi---11111111100
Longkai Zhang and Houfeng Wang. Go climb dependency tree and correct the grammatical errors. In Proceedings of the 2014 Conference on Empirical Methods in Natural Language Processing (EMNLP), pp. 266-277,50 2014
Rui Zhang, Tao Yu, Heyang Er, Sungrok Shim, Eric Xue, Xi Victoria Lin, Tianze Shi, Caiming Xiong, Richard Socher, and Dragomir Radev. baiting-based SQL query generation for cross- domain context-dependent questions. In Proceedings of the 2019 Conference on Empirical Meth- ods in Natural Language Processing and the 9th International Joint Conference on Natural Lan- guage Processing (EMNLP-JJCNLP), pp. 5341-5352, 2019.
Rui Zhao, David Bieber, Kevin Swersky, and Daniel Tarlow. Neural networks for modeling source code edits. arXiv preprint arXiv:1904.022. 2019.
12

---

Published as a conference paper at ICLR 2021
A MODEL ARCHITECTURE DETAILS
A.1 IMPLEMENTATION WITH ASDL
To implement the "dummy node" mechanism, we utilize the ASDL "field", which ensures the gram- matical correctness of every edit. In ASDL, children of each tree node are grouped under different fields, and each field has cardinality property (single, optional ?. or sequential +) indicating the number of nodes they can accept as grammatically valid children.
For single-cardinality fields that require exactly one child and optionally zero or one child, we attach one dummy node when they do not have a child. For ex- ample,
fields that require
in Fig. lb), when the MethodCall-roote subtree deleted, we automatically attach a Dummy node to its parent field "right" (which has single cardinality). Then the new node El emen TementAccess can be added by selecting Dummy and replacing with the new node. Similarly, after deriving node ElementAccess single-cardinality fields (i.e. obj and index). Note that, to add a new tree node or copy a subtree as child of a single/optional field, the Add CopySubTree operator needs to be applied to a dummy node, because the dummy node of a single/optional field indicates the only vacant position that is syntactically valid accept child for such fields. Then the new tree node or the copied subtree will simply replace the original dummy node of the field.
t 2, we automatically add Dummy node to each of its two
fields that accept multiple children, we always attach one dummy node as their rightmost child. For example, sequential field having two children A and B will have a child list of [A, B, Dummy]. Adding a new node in this case is implemented by selecting the right sibling of the target position and then inserting the new node to its left. For example, adding a new node C to the left of can then be achieved by selecting A and then inserting C before and adding to the right of B is done by selecting Dummy and then inserting C before Dummy (resulting in [A, B, C, Dummy)).
For sequential-cardinalie
A.2 TREE EDIT DECODER
In this section, we provide detailed formulations of node selection and value prediction in our pro- posed tree edit decoder.
Node Selection: Given a tree gt, there could exist an arbitrary number of tree nodes. Therefore, we design the node selection module similar to a pointer network (Vinyals al. 2015):
node, tanh W node emb(op)))pp op.)) bnode),
p(n,/s op,) = softmax(hfrode,,
where emb(op,) embeds the previously selected operator op., n, is the node representation, and W Woodes& brode are model parameters. The softmax is computed over all nodes n, E 9t-
Value Prediction: After deciding the target position (inferred from the selected node), adding new node or subtree to the current tree can be viewed as expanding its parent node in typical tree-based generation tasks (Yin & Neubig 2017 Rabinovich et al., 2017 Yin & Neubig 2018). We thus adapt the tree-based semantic parsing model of Yin & Neubig 2018 as our value predictor.
Recall that the Add operator adds new node to the tree by either applying production rule (val rude) or predicting a terminal token (val = tok), and the CopySubTree operator copies a subtree (vol = subtree) to expand the current tree. In all cases, only consider candidates that satisfy the underlying grammar constraints. The prediction probability is also calculated via a pointer network in order handle varying numbers of valid candidates in each decision situation:
hval,t tanh W vnt St; n4y emb(pn, + nt)] byat),
p( vollyss St. op,; ni)) = softmax (hi Wemb(wal,).
where Wost, bust and W are all model parameters, emb(pn, + n.) is the embedding of the edge type (or "field"; see 3 A. between the parent node Px, and the child ne (e.g. field "right" for AssignStmt right
ElementAccess), and emb( (val)) denotes the representation of the argument candidate: for production rules, it is their learned embedding: for terminal tokens, it is their word embedding; for subtree candidates, we use the representation of their root node as the encoding of the subtree.
13

---

Published as a conference paper at ICLR 2021
Algorithm 2 POSTREFNESAMPLING
Require: C=,C from training set, learning editor To, expert policy n
Algorithm DAGGERSAMPLING
Require: (fa, C_, C+) from training set, learn-
1: Let 91 =
ing editor Tg. expert policy n², 3 [0,1]
2: Sample a trajectory using (o(sa,g)) 91). De- note gr as the output tree by the editor.
1: Let 91 C_.
2: Let n = 3 + (1-11) BT
3: if gT * C+ then
3: Sample a trajectory from x (fA.91)
4: Sample a trajectory from T' (fa, ST);
4: Collect and return {ss x (s))) } for all states
5: Return {(st, x (st)) 2 T).
visited by n'.
6: else
7: Return empty collection.
8: end if
B IMITATION LEARNING ALGORIHTM
We present DAGGERSAMPLING and POSTREFINES in Algo. and Algo. 2 respectively.
C DATASETS AND CONFIGURATIONS
C.I DATASETS
For all datasets, use the preprocessed version by Yin et al. (2019) for a fair comparison. The pre- processing includes tokenizing each code snippet and converting it into a AST each (C_, dynamic programming algorithm to search for the shortest edit sequence from C_ to C.. The average length of gold edit sequences is 7.375 on GitHubEdits training set and 7.348 on C#Fixers.
Our evaluation of the Fixers-one shot setting Panthaplkkkl et al. (2020a). Specifically, for each fixer category, we pick its first 100 samples to compute 100 "seed" edit representations (for categories whose numbers of samples are smaller than 100, we use all of their N samples). We then apply each seed edit representation edit the remaining 99 samples (or N-1 samples for categories with less than 100 total samples), calculate one accuracy score for each seed, and report an average accuracy over the 100 seeds. This gives us an average score for each fixer category. Because the sample size of each fixer category is highly imbalanced, we report both macro average (treating all categories equally) and micro average (dependent on sample size) edit accuracies over the 16 fixer categories. Note that this is different from the evaluation procedure of Yin al. 2019). Yin et al. (219)) considered only 10 "seeds" per category (although each seed edit representation is applied to all samples in the category), and reported the best accuracy the category. We believe enlarging the number of "seeds" and reporting an average accuracy can better represent a model's capability. As result, the numbers in Table Yi et al. (2019) comparable with results reported in our Tab.
the 10 seeds as the score for
As introduced 3.3 for every (C_,C4) pair in the training set, we run dynamic programming algorithm to create the gold-standard edit action sequence. We elaborate the algorithm in Algo. (for simplicity, we omit the edit backtrace recording part). The algorithm edits source tree node Ca into a target tree node C² of the same type (and thus having the same fields), given memory of subtrees M that can be copied during edits. In practice, this subtree memory consists of all subtrees in the input tree C_. The algorithm compares the source and the target tree node field by field (Line 2). In each field f, we assume a left-to-right, top-down order when comparing the children of the source tree node Ct..f and the children of the target tree node C*. within this field. Cs.f (resp. C%.)) denotes the m-th (n-th) child of Os.f (C...). "CountTreeNode" counts the number of tree nodes within the subtree of root node.
D m, n) defines the shortest distance of editing C* (up to the m-th child) into Ct (up to the n-th child). In Line 4-19, the algorithm initializes the distance matrix with boundary cases; in Line
The ASDL grammar used for C# can be found at:
14

---

Published as a conference paper at ICLR 2021
Algorithm 3 TREESHIORTESTDIST
Require: Source tree node C and target tree node C* (assuming non-terminal nodes and have the same node type and fields), subtree memory M.
Ensure:
1: Initialize d 0; // total edit distance for all fields
2: for every field f of C* do // loop over aligned fields
3: M f- number of children in CSJ N < number of children in C*.,,
4: Initialize D as a matrix of (M + 1) by (N + 1). // distance matrix
5: Initialize D 0] <-
6: for m to M do
7: D(m. 0] D(m 1,0) 0] C is dummy and D(m 1, 1,0] otherwise. //deleting
tree node takes step; no need delete dummy nodes
8: end for
9:
for
N do
10:
field f is single/optional and Ofrif is a valid, non-dummy node then
11:
D n <- inf. //cannot add non-empty single/optional fields of C
12:
else C.d is dummy then
D <- D[0,
1]. //no need add dummy nodes
14:
else if Ct.. E M1 then
D(0, n] < D(0, n I]+ 1. copying subtree takes step
16:
else
D(0, nl < DI0, n 1] CounTTreeNode(Ctt)) // add nodes of C one by one,
each requiring 1 step
end end for
19:
20: for m = 1 to M do
21:
for
to N do
22:
01 D m 1, n. if C. dummy and D(m - n] + otherwise;
23:
022 D m.
if Ct. is dummy, D m, 1] if Ct. E M. and Dim,
1] + CounTrreeNode (Ct.)) otherwise:
24:
C.. 1 M) if C and Ct.f are both non-terminal nodes and have the same node type, D 1, 1] if m and Cf are both terminal tokens and have the same value, and inf otherwise;
0ig 4 D(m 11m-1117
TRESSSORTTTTT
25:
D D(m,n n. <- min(fi, U2 03).
end for end for
27:
28: + d NJ. add shortest distance of field f
29: end for
30: return as the total shortest edit distance.
20-27, it considers general cases. DIM,N .N] is thus the shortest distance of editing C*.f into C completely (Line 28). The final distance from C C' is the summation of shortest distances over all fields (Line 30).
To generate the shortest edit distance for (C-, C+), we run the TREESHOORTESTDIST algorithm with C and Ct being the roots of C_ and C+. respectively. Based on the backtrace records (omitted in Algo. 3). we produce the gold-standard edit action sequence, with one extra Stop edit action appended in the end to signal the end of the editing process. Note that this is global stop signal. As the model learns about when to stop editing the whole tree globally, it actually also learns about when stop editing any certain subtrees within it.
C.2 MODEL CONFIGURATIONS
Since surrounding contexts around the edited program are also provided in all datasets, we addi- tionally allow the value predictor & 3.1 to copy a terminal token from either the input tree's code tokens or the contexts. To this end, we introduce another bidirectional LSTM encoder encode the input code tokens as well as the contexts. The last hidden state is used to represent each token. The same design is also adopted in the two baseline editors.
15

---

Published as a conference paper at ICLR 2021
For the encoder of our neural editor, the dimension of word embedding and the tree node representa- tion is set to 128. The dimension of the bidirectional LSTM encoder for encoding imput code tokens and contexts is set to 64. The hidden state for tracking tree history is set to 256 dimensions. In the decoder side, the dimensions of the operator embedding, the field embedding, the production rule embedding, and the hidden vector in value prediction
to 32, 32, 128 and 256,, respectively.
For a fair comparison, we follow Yin et al. (2199) and Panthaplackel et al. 2020a) to encode a code edit into real-valued vector of 512 dimensions. For our TreeDiff Edit Encoder, each edit action is encoded into a vector of 256 dimensions. The bidirectional LSTM also has hidden state of 256 dimensions. When training SraphhEdiiGraphhTree joindy with TreeDiff Edit Encoder, common parameters that are designed for both the neural editor and the edit encoder (e.g. the operator/field embedding) are shared.
In experiments, we reproduce and evaluate baselines by using implementations kindly provided by their authors. This includes testing the baseline editors under exactly the same setting they were tested in their original paper (e.g. decoding using beam search of size 5 for Graph2Tree and 20 for CopySpan).
For the supervised learning, we train our Graph2Edit for 30 epochs on GitHubEdits training set, where the best model parameters are selected based on the editor's cross entropy loss on dev set. To enable more stable and reproducible results, we repeat the experiments for 3 times and report average performance.
D ADDITIONAL EXPERIMENTAL RESULTS
D.1 A MORE COMPREHENSIVE COMPARISON WITH EXISTING APPROACHES
We note that there are some other approaches by Yin et al. (2019) and Panthaplackel et al. (0200a) that are not included in our Tab. However, these approaches have been reported than those we mainly tested. For example, "Seq2Seq + Seq Edit" performs worse than "CopySpan
weaker
Seq Edit" on both GHE-goll and Fixers-one shot (micro) in Panthaplackel et al. (2020a); Yin jet al. (001 claimed that "Graph2Tree Seq Edit" is better than both "Seq2Seq + Seq Edit" and "Graph2Tree + Graph Edit". As we have slightly adjusted the evaluation settings (i.e. adding Fixers- gold and changing the evaluation procedure of Fixers-one shot compared with Yin al. (2019). results are largely missing for existing approaches. Therefore, we only re-tested and compared with existing state-of-the-art approaches (CopySpan and Graph2Tree) in main results ( 5.2 In Tab. 4 however, we include a more comprehensive set of existing approaches for reference.
Table 4: A more comprehensive comparison with existing approaches. numbers copied from original paper; -: missing evaluation in the original paper; other numbers without indication are re- ported by us. For baselines re-tested by us, we use implementations kindly provided by their authors and make sure that our reproduced version has comparable performance as what was reported in their paper.
Model
GHE-gold
Fixers-gold
Fixers-one shot macro micro
Seq2Seq + Seq Edit YYn et al. 2019
59.63"
Seq2Seq + Seg Edit (Re-implemenn) emented w/
64.40"
18.80
tricks by PPanthaplackel et al. (2020)))
CopySpan Seq Edit (Panthaplacke et al. 2020a)
67.40
87.07
20.64
24.20*
Graph2Tree + Seq Edit (Yin et al. 2019
57.13
79.48
28.49
35,53
Graph2Edit + Seq Edit (ours)
54.49
71.90
37.49
42.55
Graph2Trec Graph Edit (Yin et al. 2019
48.05*
Graph2Tree + TreeDiff Edit (w/ our edit encoder)
67.06
82,53
36.17
42.35
Graph2Edit + TifeDiff Edit (ours)
69.35
91.59
36.10
41.34
16

---

Published as a conference paper at ICLR 2021
D.2 MORE EDIT EXAMPLES
In Tab. 5, we include more examples from each editor (with Seq Edit Encoder) in the Fixers-one shot setting. Example 1-2 demonstrate that our proposed Graph2Edit editor can successfully iden- tify the correct target position to edit, even when the context of C_ is very different from that of C Consider Example for instance. Graph2Edit correctly locates the await keyword and its associ- ated expression "await VARO. GracefulStop (TimeSpan. Fro.aanonoomeeedndeee (LITERAL))" and then appends " ignrewwwt (false)" to the expression, all within the argument field of the outer "Assert. True () expression. Graph2Tree also tries to append ". "CCof igure t (false)" to the await expression, but as it generates the edited tree from scratch, it mistakenly copies an addi- tional argument to the "Assert. True ()" expression. CopySpan's generation misses right paren- thesis, leading to an ungrammatical program. Similarly in Example 2, only Graph2Edit performs the desired edits when the contexts are different for C"_ and C'..
On the other hand, Graph2Edit can fail when the correct edits require more than structural informa- tion. For example, to succeed in Example of Tab. 5] an editor needs to generalize the removal of redundant parentheses from literal variable name ("VAR4"" to a tracket-wrapped binary expression ("VAR2/LITERAL") We found that all editors fail in this case. Graph2Edit in this example correctly removes the parenthesized binary expression but can only copy the literal part ("LITERAL") back; Graph2Tree incorrectly revises the irrelevant VAR3 variable; CopySpan again produces an ungram- matical output. The target edits in Example 4 are even more complicated 8 It requires an editor to understand the use of the nameof operator to replace the explicit string literal. All editors fail to identify FEnuuUnderTest. ALLCAPITALS ToString ()" as another kind of string literal.
"A ded-anonymized instance of (C"L, C4) could be: (parameter, EnsurelsPosstiveeiniii ("parameter"), parameter. EnsureIsPosite PeosstiveFinti (nameof (parameter))). The nameof operator returns the name of the variable as string literal.
17

---

Published as a conference paper at ICLR 2021
Table Edited programs C+ from each editor (w/ Seq Edit Encoder) given (Sa [/a(C",C44 C-) on Fixers. We show where editor succeeds in Example 1-2 and fails in Example 3-4.
Example
(C",, CL)
Cl: await VARO. KriteAeyac (VAR1 (VAR1. Array, Offset VAR1. V
C await VARO. Write Array,
VAR1. VAR1.VAR2) Conf Configurrewaiittfaaaeea (falsee)
(C-, C-)
C_: Assert. Truea
PrracefuSScoo(Tineese PromSeconds (LITERAA)))
Assert. True (avait CracefulStop (TimeSSan. FromSeconds (LITERAL)).
Configgurakviit(falsss)))
CppySpan
FromSeconds CL: Assert. True True Arue (await VARO. SraccefuStoopTTmeeet (aaagogeeetmmppppa.rroeoeeeeaaa (LITTR8 (LITERAL)),
Configureevait((talse)
Graph2Tree Cl: Assert. True (await VANO. SraceffuSSoopTTineSpae Prr.eeeoneeone (LITERAL))
(LTTER)) ), await VARO.
GracefulStop (TimeSpan.
(racefulltopp(FimeSaa... www.:premmmmmaa..aaaaeaaaaaa (roTSeconds (rsaaaaccctcTTaaaaoooooooooooaan ifa.aaaaarrreeaaittai.aaallllll (fal=se))
Graph2Edit CL: Assert. True (await VARO. CracefulStop (TameSSan FromSecond (LITERAL))
Configureelaiit((aaee))
Example2
Ch: VARO (VARO)L (VAR1 !- mull VAR1. GetHashhoode)) O);
C VARO (VARO+LITERAL) (VAR1? Get.TashCCoee 0)
C_)
C_: var VARO (VAR1 mull VAR1. GetHashCooee () 0)
C_: var VARO = (VAR17.Get Gew.GGGeeHaeheeeee O);
CopySpan CL: VARO (VAR1 mull VAR1?. GetRashCooe () 0);
Graph2Tree C.: VARO (VAR1 mull VAR1 GetNaaahCode)) 0);
Graph2Edit C_:
(VAR17. G)ttHaahCoode(
Example
CL)
CL: PVARO VAR1, VARO. VAR2 VAR3. www.va.e.......eeeea.eeaeeaaa.ae Select(VARk Grab (VAR4))). Tolmmtabbeelsst()):
C.: Push VAR1, VARO. VAR2(VARO. VAR3. Select
Grab (VARA)) ) To Iomuutablelist
()))
CL),CL)
C_: VARO.
(VAR1 [(VARO/L.TTRRAI)), VAR3));
C_: AARO.Add(ApppyGeeen (VAR1 [VAR2/LITERAL] VAR3));
CopySpan C VARO VAADAAcC(pplyyAndarrrAAAALCCCC (WAAGIGAAAAATAAAAAAAAAATTEAAAAAA (LITERAL)), VAR3));
Graph2Tree C_: VARO AABD-Asddaaplyy@anarrvvvAlLLCCC (VAAEVLLTTEL/)LL) (VAR2/VAR2 VAR3) (AR3(V))3)))
Graph2Fdit Cl: (Al. [LITERAL.], VAR3));
Example 4
C": V.RO. www.eeeaaaPatttiieeeiieeeee.....
C² : VARO. (rwurertssoostttteeiinseoooooo (VARO));
(C_, C-)
Cl: Assert. Equal Ceeumnnnderreest.ALLAAPPTTI ToString(), EnunUnderTest. ALLCAPITALS.
Hunanize ());
Cl: Assert. Equal (nameof http://///ddeeeee...AAAAAAAAAAA
Hunanize()).
CopySpan Graph2Tree C_: Assert. Equal (nameof (VAR1));
C_: Assert. Equal (nameof (VAR1))):
Graph2Edit
Assert. Equal (EounUnder CCuur/ndeerTTss..AL.AAA...... ALLCAPITALS ToString(), Maamlbdderees..ALCAPPTIIII
(SharpNamee(AAl (VAR1));
D.3 EDIT REPRESENTATIONS OF TREEDIFF EDIT ENCODER
Tab. shows the nearest neighbors of given edit pairs from GHE dev set, based on the cosine sim- ilarity of their edit representations fa (C_,, C+) calculated by different edit encoders. The edit in Example means to swap function arguments (e.g. from "(VARO, VAR1)" " to "(VAR1, VARO) "). Intuitively such structural changes can be easily captured by our tree-level edit encoder. This is consistent with our results, which show that, for both Graph2Tree and Graph2Edit, TreeDiff Edit Encoder learns more consistent edit representations for this edit, while Seq Edit Encoder may con- fuse with edits that replace the original argument with a new one (e.g. modifying "VAAOO, VAR1)" to " (VAR2, "). Our proposed edit encoder also generalize from literals (e.g. swapping between " "VVAOO, VAR1) ") to more complex expressions (e.g. swapping between "(VARO. Value, LITERAL)") ") On the other hand, when the intended edits can be easily expressed token-level
18

---

Published as a conference paper at ICLR 2021
Table 6: The nearest neighbors of given edit pairs based on their edit representations.
Example
Exumple 2
C_: BoundsCheci<VARR VAR1);
C i var VAR0=GGe O);
C. BoundsChack (VARR, VARD>;
C4: var VAA0-Baat.ongrrraiiiadrrrrrr (L.TEERA))
Graph2Tree- - Seq Edit Encoder
Graph2Tree- Sey Edit Encoder
var VARO=new Profile@oasfigureeiiat))
C TelissssPoleelooneetttttttttttne (VARO, VARI);
var VARO=bev ProffIe().77BBA1))
Cl: Reelasseeoolaaccoaaaoooooorrrrre VARO);
C var VABD:PrgarreForSuucchaggggge
C_: ViggetPPooleeCCoomeeetoo (VARO, VAR1);
C var VMoorPrggrrreooorssvcaaagggg
C.i UngetPooladdGnmeecoor (VAR22, VARO);
C-: bool. VARO=trua;
C.: VARO. (LITELE,, VAR1);
C.: bool VMRD-CanBeNull (VAR1);
Cli VARO...OrnaaAA (VAR1, LITERAL);
Graph2Trce Tife Edit Encoder
Graph2Tree- - TreeDiff Edit Encoder
C var VARO=pew ProfilaConfigg (llaCooiirrrutiion)
CL: InternalLogger Error (LITERAL, VARG);
C5: var VARO=gev Profile (LITERAL)
Cs: InternalLogger Error Erzor (VARO, LITERAL);
Cl: Calcorichreaz():
CL: VARO. (LLTELI,, VAR1);
C5: SetDataSSurca (VARO, VARI);
Cl: VARO.Varn LITERAL);
C VARO-aeV VinS2PageFi1 SesnBpppeffBBBcccccooeee/e//eeee O
C+: VARD=nau Wr5SShroFFFuaaaaccccooorrrohghgn LITERAL))
C-: AssertRqual (VARg (VARO. Value, LITERAL);
C.: AssertE (LITERAL, VARO. Value);
Graph2Edit Seg Edit Encoder
Graph2Edit Sog Edit Encoder
C VARD=new Praffl (ddnriiguaation)))
CL: RellsssPolleeCCneettttttteaaaane (VARO, VARI);
C2: var VARO=Dev Profile (LITERAL);
Cl:: Rectasrreoolaccoometttrtttttttae VARO);
Cl: VARO.Dispoze():
C_: UnggetPolleddoonncccerrroaa VAR1);
VARD. (VRR)))
C.: UngettPooleddioneectorr (VAR2,, VARD);
VARO-VARI (VAR2);
C_: Reporttuuusecctnoortttvvvvv (VARO, VARI, VAR2);
C.: VARO=GatSpans (VA82, VARI);
C.: ReportuinueecItpporee (VAR2, VARO, VAR1);
- Edit Encoder
Graph2Edit -aenh22EiitTTeDDDifff Edit Encoder
CL: var VARO=aew trofileConfiiuuretion))
C_: VARO. Varn (LITERAL, VAR1);
c var VARO=Dau ProTEIa())7EBRt));
C.: VarnoV,,, LITERAL));
VARO-Thread. CatDomain () D.DDttaadyaanncoooonnyy
C.: Internallogger..oc Brrer (LITERAL, (LITERAL VARO);
Assemblybuillertceeee Run);
C+ VARO-Thread GetDenann() (aaaannn.Dttaaae Darftadbyamiccksnmm)yyM
Cli Internallogger.BBe Brror (VARO, LITERAL);
hesemblybbullborscceee. RunaadSave, htw.://reeceeee..aaaaaaa...ee LITERAL);
C_: AssertEquallVAR0 Value, LITERAL);
new DocumentsCrud() aagpsaeeaaasseessststaaaaaaaaa
Cli (LLTTEE VARO. Value);
: new DocusentaCrad()) pet.aaaaatttoooeetttayarrrrr11
editing (e.g. inserting an argument token), the edit encoders perform comparably, shown in Example 2. However, we still observe that TreeDiff Edit Encoder works better at interpreting the editing semantics of code snippets with complex structures (e.g. more complex edit pairs are retrieved).
D.4 MORE DETAILS ABOUT IMITATION LEARNING EXPERIMENTS
Experimental Setup We use "Graph2Edit w/ Seq Edit Encoder" as the base editor. We do not experiment with "Graph2Edit w/ TreeDiff Edit Encoder" as it performed very well on GHE-gol training set even without imitation learning. In fact, 80% of the remaining errors were due to issues such unknown tokens, which cannot be fixed with better training algorithms, the search space of our current model. We leave experimenting this model on harder datasets as future work. Like the main experiments & C.2), we ran the imitation learning experiments for three times and reported average performance in Tab.
they are outside
Analysis We provide a more detailed analysis about the imitation learning experiments, especially how the choice of 3 in DAGGERSAMPEI Graph2Edit+Seq Edit Encoder's ' results on the GHE dev set, when they are trained with 20% of the GHE training data. We observe that the SAGGERSAMPLING algorithm generally trains the editor to behave very unstably. The editor shows to "regret" its previous decisions (mostly about terminal tokens, the prediction of which is generally harder than that of non-terminal nodes on GHE). An example is shown in Tab. 3) where the DAGGERSAMPLING AMPLING editor first adds a token "VAR1" to the tree and then deletes it in the next step. This happens to around 23% of the examples (count=2,373 in Tab. 7) the dev set for DAGGERSAMPLING when 33 is set to 0 (i.e. when the editor samples all states from itself throughout the imitation learning process). Among them, 84% of the deletions (count=1,989) are correct; they remove the wrong token added in the previous step. However,
affects the model performance. Our analysis is based on
19

---

Published as a conference paper at ICLR 2021
also observe that the editor may then regret their correct deletions and add back the wrong tokens after "swinging" for few steps (42% the cases), revealing an interesting "add delete (- add delete)- add" hesitation phenomenon. Similarly, among the remaining 384 examples where the editor deletes a correct token that it previously added, we found out in 51% of the cases the editor will add back the correct token. This unstable behavior can easily lead of repetitively adding and then deleting the same token (447 cases), until the editor reaches the maximum edit length that we set hyper-parameter (70 in our experiments).
endless loop
Table Analysis of MAGGERSAMPLING algorithms with 8 being 0 and 0.5 dev set. We analyze each algorithm's 's behavior about "adding then deleting" the same token.
B
B 0.5
#of examples with add-then-delete
2,373
1,032
#of endless edit loop
447
605
#of add wrong token then delete
1,989
861
#of then add back
845
467
#of add correct token then delete
384
171
#of then add back
196
71
We hypothesize that setting B to 0 in the DAGGERSAMPLING algorithm has forced the editor to learn only single-step correction edits (i.e., the correction edit under the current state). In other words, even if the editor could imitate the expert demonstration and correct its mistake this single step, it still does not know how to proceed correctly for the next step. This is possibly the reason why the editor swings between adding then deleting the same token. interesting question why this problem shows more severely in our setting, compared with traditional imitation learning tasks (e.g. racing games). We hypothesize that editing tree-structured data for program revision requires more continuous and structured supervision, such as teaching the policy complete the entire generation of a subtree, rather than teaching to add only the next correct single tree node. We leave a deeper study of this problem to the future.
In experiments, to alleviate this problem, we propose to set 33 higher, because when the editor ex- ecutes actions from both itself and the expert, it is more likely to collect continuous sequence of correction edits. We show improved program editing accuracy of DAGGIRSAMPLING with B = 0.5 in Tab. 3 and analysis of its "add-then-delete" behavior in Tab. 7 Compared with when 0, this setting reduces the frequency of unstable editing. We also propose new sampling algorithm, We observe that the POSTREFINESAMPLE to perform much more stably than the DAGGERS SMMPLING algorithm. We observe almost no (less than 0.5% of dev examples) the aforementioned ald-then-delet behavior.
algorithm trains the editor
20


Reviews:
[{"review_id": "oSrjJPcDi-", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 7, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "## Summary\n\nThe paper proposes a general model for incremental editing of tree-structured\ndata such as abstract syntax trees. The editing operations include adding a\nnode, deleting a subtree, or copying a subtree. They also propose a novel edit\nencoder to learn to represent edits, and an imitation learning method to make\nthe model more robust.\n\n## Pros\n\n- The work has several interesting and valuable contributions:\n  + Compared to previous work, the model is much more general: it supports\n    general tree edits, is language agnostic, and can handle much longer edit\n    sequences.\n  + The novel edit encoder which directly encodes the edit actions is more\n    intuitively correct and also performs better than previous approaches.\n  + Imitation learning to make the model more robust is a natural idea that\n    suits incremental edits very well.\n- The source code will be released which -- given the general nature of the\n  model -- could enable further interesting research.\n\n## Concerns\n\n- The explanation for the results in Table 1 could be improved upon.\n  + I don't think the results support the claim that Seq Edit Encoder memorizes\n    specific patterns with the baselines as the micro average of Graph2Tree for\n    Fixers-one shot is very close to Graph2Edit.\n  + Even if we accept the claim, that would not explain the CopySpan >\n    Graph2Tree > Graph2Edit results on GHE-gold and Fixers-gold. The authors\n    state that Seq Edit memorizes specific patterns, TreeDiff Edit learns more\n    generalizable information, and Graph2Edit makes Seq Edit learn more\n    generalizable information. But they state that in order to solve GHE-gold,\n    we need specific patterns instead of generalization. So why does increasing\n    generalization by switching Seq Edit to TreeDiff Edit improve performance of\n    Graph2Edit on GHE-gold and Fixers-gold (which doesn't need generalization),\n    and decrease performance on Fixers-one shot (which needs generalization)?\n- Some of the contributions are not demonstrated clearly:\n  + The method's applicability to much longer edit sequences is not clearly\n    demonstrated, although the length of the edit sequences is mentioned briefly\n    in the Appendix.\n  + The imitation learning method is demonstrated only on \"Graph2Edit with Seq\n    Edit Encoder\", which is the less interesting case compared to \"Graph2Edit\n    with TreeDiff Edit Encoder\". From the previous experiment it's clear that\n    the TreeDiff encoder version is the practically relevant one and the one the\n    paper's about. As the Seq Edit encoder makes more mistakes and so it's\n    easier to improve, we don't know whether imitation learning helps in the\n    relevant case of the TreeDiff encoder. In my opinion this makes imitation\n    learning more of a digression and a less of an organic part of the paper.\n- The writing could be more precise at times. For example, the authors state\n  that they are adding subtrees as an edit operation, but as far as I\n  understand, they are adding individual nodes.\n\n## Reasons for ranking\n\nI believe that the model is an important step in learning to represent edits.\nHowever there are some problems with the experiments: some of the claims are not\nadequately supported and the explanations could be improved upon.\n\n## Minor comments\n\n- I found Figure 1 confusing at first, because there is essentially no caption\n  and the description of the figure comes much later in parts. It would be good\n  to either have a more substantial caption or to move the figure closer to the\n  explanations.\n- Table 2 precedes Table 1, which is confusing\n- It should be \"general\", not \"generic\", like \"general model for incremental editing\"\n- Page 3: Delete operators take a tree node ... and remove\n- The algorithms in the Appendix should be DaggerSampling and PostRefineSampling (missing \"l\").\n", "extra_scores": {}, "extra_text": {}}, {"review_id": "JiX3-3hTxWp", "reviewer": "AnonReviewer4", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "## Summary\n\nThis paper presents an approach to learn a model over incremental structural tree edits, that takes as input a partially formed tree and applies a sequence of transformations that edit the tree into a final form.  They focus on abstract syntax trees as used to represent expressions in programming languages, where the grammar is specified using the ASDL formalism.\n\nThey demonstrate their approach on two datasets: the GitHubEdits dataset and C#Fixers, showing improved performance relative to some baselines.\n\n## Overview\n\nThe motivation for this work is weakly specified.  Analogies are made to the fact that humans seem to edit objects in sequence, but not much more than that is provided.  The authors would do well to specify, or at least hypothesize as to what the benefits of sequences of edits over the alternative.\n\nWriting-wise, it is hard to tell what this paper actually contributes from the abstract or introduction.  Now, I would characterize it as presenting a template in which neural networks can be composed such that graph transformation sequences can be learned from data.\n\nThe claimed advantages over existing approaches are:\n- Supports general tree edits, whereas previous approaches are somehow more restricted\n- Language agnostic due to use of ASDL\n- Supports longer sequences of edits in practice\n\nA major problem is that these advantages are only weakly demonstrated, if at all: \n\n- What is a general tree edit?  One answer could be that any graph transformation can be encoded as an action in theri framework, or is it that it can be achieved through a sequence of steps?  The paper focuses on a very particular set of tree edits, so it is very unclear what is being claimed here.\n- Longer edit sequences.  No evidence is provided to support this claim.\n- Language agnosticism through ASDL is a valid claim, and useful.  It's not clear that generalizing any of the existing work to work with a general grammar would require much work though. \n\nMoreover, the work closest to this work (Dinella et al) is not compared against, neither experimentally, nor are the differences in the approaches detailed.  Why?\n\nOverall while I think a useful software package could be made based on this work (which the authors suggest is forthcoming and which itself could be presented as a publication of a much different kind), the delta over existing work has not been demonstrated enough for me to recommend publication.\n\n## Questions\n\n- In the LSTM encoding of an edit sequence, you have these four transformations to produce a_stop, a_Delete, a_Add, and a_CopySubTree.  What is the advantage of doing these transformations prior to having the LSTM read the result?\n- I cannot see where the embedding function $\\text{emb}$ is defined.  Is this learned, or fixed?\n\n\n", "extra_scores": {}, "extra_text": {}}, {"review_id": "I3Xj4X1EtRL", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "### Summary ###\nThe paper presents an approach for predicting edits in programs, by modeling the programs as trees. The approach is mainly an extension of Yin et al. (2019), with the main difference that the model is required to predict only the output **actions**, instead of generating the entire output tree as in Yin et al. (2019). This difference of predicting only output actions is shared with other previous work though.\nThe most interesting part in my opinion is the \"imitation learning\" improvement: during training, the model is trained to correct its own mistakes by \"imitating\" an expert that fixes the incorrect predictions.\n\nOverall, I vote for acceptance. Although the technical contribution is limited, the paper presents strong empirical results and a combination of interesting ideas. I think that the paper could be easily further improved, as detailed below.\n\n### Strengths ###\n1. The paper presents improved results over the Graph2Tree model (Yin et al. 2019) and over CopySpan (Panthaplackel et al., 2020a).\n\n2. The imitation learning part is very interesting, and its applicability for programs is novel as far as I know. I feel like maybe this should have been the main focus of the paper.\n\n### Weaknesses ###\n1. Limited novelty - the encoder, as far as I understand, is identical to the edit encoder of Graph2Tree (Yin et al. 2019). The decoder (\"editor\") is better, empirically and conceptually, than the decoder of Graph2Tree, but its main novelty is the prediction of the edit action itself, rather than generating the entire output tree. To me, this idea is not novel, as it was used in Tarlow et al. (2019), Dinella et al. (2020), and Brody et al. (2020).\n\n2. A conceptual comparison with previous work is missing. First, the work of Tarlow et al. (2019) is not cited at all (although their application is different, the approach is very similar). Second, a comparison to Hoppity (Dinella et al., 2020) and to C3PO (Brody et al., 2020) is presented in a single paragraph and contains the following arguments:\n\n(a) “While some recent works have examined models that make changes to trees for specific applications such as program bug fixing (Dinella et al., 2020) or edit completion (Brody et al., 2020), our method is designed to be generic and flexible in nature”\n-- I don't think that this is a fair argument. These previous works are as general as this paper, they were just demonstrated on slightly different datasets.\n\n(b) “it supports general tree edits including adding new tree nodes or copying a subtree, which are not fully allowed by previous work”\n-- Can't Hoppity add new tree nodes? Can you clarify the classes of edits that previous works could not express and that this paper can express?\n\n(c) “all tree edit operations are language-agnostic owing to the adoption of Abstract Syntax Description Language (ASDL; Wang et al. (1997)), which allows us to process arbitrary tree-based languages”\n-- I don't think that this is a fair argument. These previous works are language-agnostic as well, they just use a different AST \"format\". \n\n(d) “unlike the short edit sequences handled in previous work (e.g. up to three edits in Dinella et al. (2020)), we demonstrate our method’s applicability to much longer edit sequences”\n-- The fact that Hoppity was evaluated with 3 edit actions does not mean that it is not applicable for longer action sequences. This argument would have been valid if it was demonstrated empirically that Hoppity's accuracy decreases as the length of the sequence increases.  In that case, the imitation learning part might be a very natural fix (which was good! but not shown).\n\n\n3. Evaluation - it is unclear which datasets should we _really_ care about, and which are the main results. It seems that the proposed Graph2Edit model outperforms the Graph2Tree model (Yin et al. 2019) only in the \"gold\" datasets (GHE-gold and Fixers-gold), which expose (indirectly) the labels to the input. That is, these serve as \"intrinsic\" tasks that cannot really be compared across models. As far as I understand, Yin et al. (2019) argued that the \"Fixers-one shot\" is the dataset that really matters, and that GHE-gold and Fixers-gold are just \"intermediary\"/\"intrinsic\" training objectives. \nIn the \"intermediary\" datasets, Graph2Edit outperforms Graph2Tree, but it is not compared to \"Seq2seq encoder+editor\" which performed best in these datasets in Yin et al., 2019 (Table 4 in Yin et al., 2019).\nIn the one-shot dataset (Fixers one-shot) - Graph2Tree performs better than the proposed Graph2Edit model.\nSo, I am not sure what are the main results that the readers should focus on and what is the correct baseline. See question 1 below.\n\n### Questions for Authors ###\n1. Is the accuracy on the \"gold\" datasets (GHE-gold and Fixers-gold) really meaningful? Isn't this accuracy just an intermediary accuracy? \nAs far as I understand, when trained on these gold datasets: $f_{\\Delta}$ depend on $C_{+}$, and then $f_{\\Delta}$ is *used* in the prediction of $C_{+}$. I saw the footnote that says that  $f_{\\Delta}$ does not *directly* expose $C_{+}$. So it means that it *indirectly* expose $C_{+}$, right? Section 3.3 explicitly says that \"given an input tree $C_{-}$ and an edit representation  $f_{\\Delta}$ (calculated either from $<C_{-}, C_{+}>$ or another edit pair $<C'_{-}, C'_{+}>$), we generate one tree edit at a time step...\". \nSo, since in the gold dataset  $<C_{-}, C_{+}>$=$<C'_{-}, C'_{+}>$ , the authors model the \"actions leading to $C_{+}$\" given \"an encoding of $C_{+}$\"? \nI.e., are the output labels (indirectly) encoded in the input? \n\nThis is fine if we consider the gold datasets as intermediary/intrinsic objectives, and consider Fixers one-shot as the \"important\", downstream task. \nIf so, Graph2Tree (Yin et al., 2019) performs best on the Fixers one-shot dataset (which is the \"important\" dataset).\nIf not, and the gold datasets are meaningful on their own, then why there is no comparison to the seq2seq editor+decoder that Yin et al., 2019 found to perform best on the gold datasets?\n\n2. The paper states that the graph edit encoder of Yin et al. (2019) does \"not explicitly express the differences between the input and the output trees\". As it looks in Yin 2019 (Section 3.2), it seems that they represent the difference between the trees pretty explicitly, using edges such as \"Removed\", \"Added\" and \"Replaced\" between the old and the new tree. So, what is the main novelty compared to Yin et al. (2019) in this area?\n\n3. The main novelty in this paper compared to previous work, in my opinion, is the imitation learning training (Section 4). I wish the authors elaborated more on this, give examples, show how the parameter values affect the performance, etc.\n\n4. How long are the edit sequences, average, in the Fixers dataset? (in comparison to Hoppity's 3 edits per sequence)\n\n### Improving the Paper ###\nThe paper could be improved in the following ways:\n1. A conceptual discussion of the differences from previous work (Tarlow, Dinella, Brody).\n\n2. Is it possible to perform an empirical comparison with Hoppity? \n\n3. Other strong baselines would be Transformer+copy and bidirectional LSTM seq2seq+attention+copy mechanism, that copy individual tokens rather than spans as in CopySpan (Panthaplackel et al., 2020a). \nEven Section 5.2 of the paper says that the CopySpan baseline, which can copy large spans, memorizes too much.\nAnother straightforward baseline is a sequential **tagger**, that tags each individual token in $C_{-}$ with tags like KEEP/SWAP/DELETE, as in Malmi et al. (2019), and as Brody et al. (2020) adapted to code as their baseline.\n \n4. Adding more interesting examples in which the model succeeds (and fails). The paper claims \"applicability to much longer edit sequences\" (Section 1), but the example in Figure 1 converts `list.ElementAt(i+1)` to `list[i+1]`   (which might be syntactically-long, but not that \"difficult\") and the example in Table 2 only converts a `VAR2.ToString()` to `VAR2`  (which is also not very \"difficult\" or \"interesting\", because a simple sequence-tagger that is trained to delete tokens can produce such examples).  Ideally, the appendix could contain many additional examples like Table 2 (but also with longer edit sequences).\n\n### Minor questions and comments ###\n5. The paper's title contains the phrase \"*Incremental* Tree Transformations\". \nWhat is \"incremental\" about it? Doesn't the model mainly model a single \"action\" or \"transformation\" at a time? Doesn't the \"incrementality\" come from an LSTM \"decoder\" that sequentially predicts these actions? \n\n6. In Section 3.2 - Why is $a_{Stop}$ computed as $W_{Stop}emb(Stop)+b_{Stop}$, instead of just learning a single embedding vector, if all its components are trainable and used only in $a_{Stop}$?\n\n7. Typo in Section 4, Algorithm 1 and Algorithm 2:  \"Samping\" -> \"Sampling\"\n\n\n\n\n\n", "extra_scores": {}, "extra_text": {}}, {"review_id": "2YbLtvGQBMY", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 7, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "The paper presents a neural autoregressive model that learns to incrementally or iteratively perform edit actions on structured data. The authors focus specifically on abstract syntax tree representation of programs (e.g., C#). The model has two main parts:\n\n(1) Neural editor models p(a|) that iteratively performs tree edit actions such as sub-tree deleting or adding;\n(2) Edit encoder learns edit representations f_Delta by encoding the sequence of ground truth tree edit actions.\n\nThe authors also propose an imitation learning algorithm to train the editor and evaluate the model on source code edit datasets.\n\nThe idea of incremental tree transformation pretty much follows that of Hoppity by Dinella et al, ICLR 2020 for bug fixing of Javascript programs. Unlike Hoppity where each transformation step is done on a single node, this work extends to support sub-tree operations. However, adding a subtree is nothing but performing a sequence of single-node actions. The difference is that to ensure the syntactic validity of the tree at any point, the authors use a grammar specified a priori. This mechanism was proposed in semantic parsing by Yin et al., ACL 2017. Compared to Hoppity, this model has another SubTreeCopy operation, but it is a somewhat straightforward extension of the copy mechanism from Yin et al. \n\nAlthough the whole idea is not new, I think the paper presents a valued extension to existing work. The running example is intuitive, making the paper easy to follow. However, there are a number of parts that are unclear and need more clarity. I hope the authors address these during the rebuttal phase.\n\n1. The authors should be clear (e.g., before Equation 1 and in Section 3) about where the sequence actions {a_t} comes from and how sub-tree actions are represented (e.g., decomposed into single-node actions). Later in this experiment, the authors mention dynamic programming to compute the shortest tree edit sequence, but I feel that substantial discussion or an algorithmic description is needed.\n\n2. It is not clear to me whether f_Delta is learned jointly or separately from the parameters of p(a|). In Figure 1 and Equation 1, f_Delta does not depend on t and seems to be fixed.\n\n3. In the last paragraph of page 3, this sentence “the operator selects a dummy node (e.g. node Dummy) and replaces it with the added node” is not clear. Is there always at least one dummy node at any time? What is “the added node”?\n\n4. Another question about Add operation: if an Add operation is given and there is currently no dummy node, would it make more sense to specify the added location with respect to a parent node and its children?\n\n5. How does the model know when to stop adding a right sibling for constructor fields with *sequential* cardinality? Similarly, for an *optional* cardinality field, what does the model do on the attached dummy node if the field is indeed optional?\n\n6. It may be more natural to predict the node location n_t before the operation op_t. Equation 2 does the other way. Does this change the model in any way? \n\n7. To what extent this framework is language-agnostic? Despite the ASDL, even for the same language, different parsers can have different grammar specifications, so how easy is it to apply this framework for other languages? On the same note, since Hoppity is directly related, I am curious how this work compares to it on a same bug fixing task.\n\nFinally about the experiments, the authors compare to Graph2Tree and CopySpan. But it does not look like the source code for the baselines are available. Releasing the source code with that of the baselines would be helpful.\n\n\nMinor typos\n\n“Arbitary”: Section 3.1.1 paragraph 2.\n\n========== After discussion =============\n\nI have increased my score from 6 to 7.", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper proposes a model for predicting edits to trees given an edit specification that comes either from the ground truth before-after state (“gold” setting, like reconstruction error of auto-encoder) or from the before-after state of an analogous edit. The problem setting follows mostly from Yin et al (2019). 

There are several shortcomings of this paper:

1. The technical novelty of the model is somewhat limited, as it’s an assembly of components that have been used in related work. Authors insist in the discussion on the novelty of the tree edit encoder (Sec 3.2), but I think this is overstated. The related tree-edit models (e.g., Tarlow et al (2019)) perform a very similar encoding *in the decoder* when training with teacher-forcing. While it’s true that decoders are typically thought of as monolithic entities that generate a sequence of edits from a state, inside the teacher-forced training, the models are computing a representation of a prefix of ground truth edits, which are then repeatedly used to predict next edits. AFAIU, the proposal is basically to use this hidden representation as the edit encoder. 

2. The claim that the approach is more language agnostic than Dinella et al (2020) also seems shaky, as the authors admit in their response that language-specific grammars need to be handled specially. E.g., I expect that the authors of Dinella et al would find it easier to extend their existing code to use a new language than to adapt this approach.

3. The submission relies too heavily on the “gold” setting (where the target output is fed as an input), and I’m skeptical of their characterization of Yin et al’s intentions when the authors say in comments, “Because of this, models that are able to reproduce the desired output effectively have a demonstrably better inductive bias that allows them to do so efficiently. This was the original motivation expressed by Yin et al. (2019).”  I don’t see this stated in the Yin et al paper. I see Yin et al. characterizing this setting as an upper bound and saying “better performance with the gold-standard edit does not necessarily imply better (more generalizable) edit representation.” (Yin et al., 2019). It’s worrying that the proposed model only seems to do better in this setting, which would be very easy to game if one were aiming to directly optimize for it. 

Having said this, (1) is not a standard way to think about encoding edits, (2) is debatable, and we can hope that future work does not treat improvements in the “gold” setting as a valid research goal. Further, there is another contribution around imitation learning that the reviewers appreciate. In total, reviewers did an excellent job and generally believe the paper should be accepted. I won’t go against that recommendation.
Decision: Accept (Poster)