# programming_by_example_using_least_general_generalizations__c353c184.pdf

Programming by Example using Least General Generalizations

Mohammad Raza Microsoft Research Cambridge 21 Station Road, Cambridge, CB1 2FB, U.K. a-moraza@microsoft.com

Sumit Gulwani Microsoft Research Redmond One Microsoft Way, Redmond, WA 98052-6399, U.S.A. sumitg@microsoft.com

Natasa Milic-Frayling Microsoft Research Cambridge 21 Station Road, Cambridge, CB1 2FB, U.K. natasamf@microsoft.com

Recent advances in Programming by Example (PBE) have supported new applications to text editing, but existing approaches are limited to simple text strings. In this paper we address transformations in richly formatted documents, using an approach based on the idea of least general generalizations from inductive inference, which avoids the scalability issues faced by stateof-the-art PBE methods. We describe a novel domain specific language (DSL) that expresses transformations over XML structures describing richly formatted content, and a synthesis algorithm that generates a minimal program with respect to a natural subsumption ordering in our DSL. We present experimental results on tasks collected from online help forums, showing an average of 4.17 examples required for task completion.

Introduction The area of Programming by Example, or PBE (Lieberman 2001; Gulwani 2012), has recently been gaining renewed interest, especially in the domain of text editing (Gulwani 2011; Manshadi, Gildea, and Allen 2013; Liang, Jordan, and Klein 2010; Lau et al. 2003) and has also seen successful adoption in commercial end user applications such as the recent Flash Fill feature in Microsoft Excel (Gulwani 2011). These advances have, however, been limited to relatively simple editing scenarios on small unstructured text strings and cannot, for example, address structural transformations in richly formatted documents, e.g., word processing or presentation documents created by standard office productivity tools. Performing repetitive formatting operations in such documents is a common and demanding task, particularly for long documents or across large document collections, as we observed from many user requests in online help forums. Existing features such as styles or templates allow some degree of abstraction, but are limited in functionality and suffer from discoverability issues. On the other hand, macro programming languages are very powerful but above the skillset of most end users. We propose a PBE interaction that would naturally be suited to such tasks, allowing the user to provide some examples of the desired transformations using the

Copyright c 2014, Association for the Advancement of Artificial Intelligence (www.aaai.org). All rights reserved.

standard WYSIWYG editing interface, from which the system can infer a general program to apply to whole documents. An important challenge faced by PBE approaches in general is the delicate balance that must be achieved between the expressivity of the domain specific language (DSL) of transformations and the efficiency of the synthesis algorithm, because the more expressive the DSL, the more complex is the search space of possible programs, and the harder it is to effectively maintain and search within this space. For instance, recent state-of-the-art approaches use DAG based data structures to handle sophistication of the underlying transformation language (Gulwani 2011; Singh and Gulwani 2012b; Manshadi, Gildea, and Allen 2013; Singh and Gulwani 2012a). However, they only scale to relatively small unstructured strings (for example, Flash Fill only permits transformations on strings up to 256 characters) because of their complexity that is exponential in the number of examples and high degree polynomial in the size of each example. Hence, such approaches, even if they could express the underlying transformations, would not scale to our setting of transformations between large XML structures that describe richly formatted documents (most modern office suites work with XML-based file formats1). In this paper we propose a PBE approach to structural format transformations which, in contrast to above-mentioned methods, avoids explicit generation of all consistent programs by incorporating the ranking strategy implicitly into the synthesis algorithm. After all, the end goal in any PBE task is to find a single satisfying program rather than the set of all possible satisfying programs. Our approach is based on the notion of least general generalization from Plotkin s work on inductive inference (Plotkin 1970; 1971), which laid the foundations for the field of inductive logic programming. In this work the θsubsumption relation was proposed as a tractable alternative to implication when inferring generalizations over first order formulae, and the syntactic anti-unification algorithm was described for inferring a least generalization with respect to subsumption. In our case, we are not working with logic formulae; our first contribution is a DSL that expresses transformations on ordered trees (including variable, function, and

1including Open Office, Microsoft Office, Apple i Work

Proceedings of the Twenty-Eighth AAAI Conference on Artificial Intelligence

loop expressions) and we show how programs in this DSL are naturally ordered by a similar subsumption relation. Our second contribution is a program synthesis algorithm which, given a set of input-output examples, generates a program in our DSL that satisfies all the examples. Using techniques similar to syntactic anti-unification, the algorithm generates a minimal program with respect to the subsumption ordering, without constructing a represention of all possible satisfying programs, which can be exponential in the size of examples.

Motivation In a repetitive formatting task, the users usually have some intended selection criteria to specify items to change, which, in general, may be independent from the actual transformation they want to apply to these items, as we have observed in help forums. The selection criteria may, for example, be all text boxes containing text with Arial font of size 12, while the desired alteration may be change every such text box to a table with a particular configuration. Hence, the programs in our DSL must accurately characterise both the selection criteria for the applicable inputs as well as the desired outputs to ensure that only items relevant to the task are affected. We consider an example of the above text box to table transformation task in Figure 1, where we use a simplified XML format to illustrate the state before and after the transformation in Figures 1(a) and 1(b) (attributes at nodes are shown inside boxes). Initially the text box contains three paragraphs (with text P1 , P2 and P3 ), and satisfies the requirement of Arial font of size 12. In the output this is changed to a table with a certain height, border, font type and color, but the same text content and bold settings as the input. In this simplified format we only show some properties for illustration although, in practice, specifications contain many more elements, attributes, and substructures. In Figures 1(c) and 1(d) we illustrate a program in our DSL that satisfies this example, specifying both the selection criteria and the transformation intended for this task. A program consists of two expressions describing the form of the applicable inputs and the outputs. The input expression in Figure 1(c) describes a tree that has a root element text Box with a certain number of child subtrees that each has a root element para, with font Arial and size 12, and any text value, color or bold setting (expressed by variables X1, X2, X3). The output expression in Figure 1(d) specifies a tree with root table and the same number of child subtrees as the input (expressed by iteration variable I1). Each subtree has root table Row and two children specifying row properties and a single cell. The text and bold values in the cell are the same as in the input (variables X1 and X3) while color, size, and font are constant. While this program specifies precisely the selection criterion and the transformation that is intended for this task, there are many other possible programs in the DSL that can satisfy the example transformation in Figures 1(a) and 1(b). For example, instead of a loop the program may assert exactly 3 paragraphs in the input or, instead of a single cell in each row, there could be a loop expression to allow for

multiple cells. Similarly for attribute values, the input expression may have specified variables over all the attributes, or specify the value blue for color rather than the variable X2. Using all the examples provided for a given task, our program synthesis algorithm makes such choices by inferring a minimal generalization over the input and the output states and by mapping variables between the input and output states to generate a well-formed program satisfying all the examples.

Domain Specific Language In this section we define the model of XML specifications that we use in this paper and the syntax and semantics of the domain specific language (DSL) used to express transformations on these structures. We model XML specifications as ordered trees in which every node has an associated element and a map from attributes to values.

Definition 1 (Tree model) Given fixed sets of elements Elm, attributes Att and literal values Lit, we define trees t T by the following grammar:

t := 0 | r | t t r := (e, m)[t]

where 0 is the empty tree, r is a rooted tree and t t is a parallel composition of trees as ordered siblings. A rooted tree r is of the form (e, m)[t] with root node (e, m) and subtree t. A node (e, m) consists of an element e Elm and a partial map from attributes to literal values m : Att Lit. We impose the structural congruences that parallel composition is associative, i.e., (t1 t2) t3 = t1 (t2 t3), and has identity 0, i.e., t 0 = 0 t = t.

We next define the DSL for transforming XML trees which is agnostic of any particular XML schemas and hence generically applicable. The syntax of the DSL is given in Figure 2, which we first discuss before giving the formal semantics in the next section. A program Prog(τ1, τ2) consists of a pair of tree expressions τ1, τ2, where τ1 describes the applicable input trees to the program and τ2 describes the output tree. For example, Figures 1(c) and 1(d) illustrate the input and output tree expressions for the text to table program. A tree expression is a parallel composition of atomic expressions, where an atomic expression is either a rooted tree expression or a loop expression. A rooted tree expression (e, φ)[τ] describes a rooted tree that has root element e, attribute map described by φ and subtree described by τ. An attribute map expression φ may use literals, variables or function expressions to express the values that a particular attribute may take. For example, in Figure 1(d), there is a rooted subtree with root element table Cell at which the text and bold attributes have variable values while color , font and size attributes have literal values. Function expressions may be used to describe transformations of attribute values from input to output. For example, in Figure 1(d) we could have text = f(X1) to indicate that the text value at that node changes according to some text transformation function f (e.g., syntactic transformations such as name or date format changes (Gulwani 2011)). On numeric-valued attributes we may have, for example, size = X in the input and size = X + 3 in the out-

text= P3 color= blue font= Arial size= 12 bold= 1

text= P2 color= blue font= Arial size= 12 bold= 1

text= P1 color= blue font= Arial size= 12 bold= 0

(a) Example input state

text= P3 color= red font= Times size= 12 bold= 1

border= 1 height= 2

text= P2 color= red font= Times size= 12 bold= 1

border= 1 height= 2

text= P1 color= red font= Times size= 12 bold= 0

border= 1 height= 2

(b) Example output state

Loop(I1, para)

text= X1 color= X2 font= Arial size= 12 bold= X3

(c) Program input

Loop(I1, table Row)

text= X1 color= red font= Times size= 12 bold= X3

border= 1 height= 2

(d) Program output

Figure 1: Example input and output states and satisfying program for the text box to table transformation task

put. In general, we assume a fixed set of functions between literal values that are available in our DSL. Loop expressions allow for structural variations in the trees by expressing an arbitrary number of sibling trees in a parallel composition. An expression Loop(I, ρ) describes any number of sibling trees, each described by rooted tree expression ρ. The loop iterator I is used to relate loop expressions between input and output tree expressions. For example, in Figure 1 there are loop expressions in the program input and output that are related by the iterator I1. When applying the program to an input such as in Figure 1(a), the iterator I1 is used to determine the number of loop iterations when instantiating the output (3 in this case) as well as the valuations of the variables for each iteration (X1, X2 and X3). Note that the language does not permit nested loop expressions at the same level of parallel composition (e.g. (I1, (I2, ρ)) but loop expressions can be nested inside subtrees (e.g. (I1, ρ) where ρ contains I2). For example, if every paragraph in Figure 1(a) were fragmented into a number of runs and each run should appear in a separate column in the output table, that may be expressed by a program in our DSL by using a nested loop expression to represent varying number of table cells in each table row. We define Var(τ), Iter(τ) and FExp(τ) for the set of variables, iterators, and function expressions that appear in tree expression τ respectively. These sets are similarly defined for programs, atomic and rooted tree expressions, and attribute map expressions. We define the set of root elements in τ as Root(τ) =

{e} τ = (e, φ)[τ ] or τ = Loop(I, (e, φ)[τ ]) [

i 1..n Root(αi) τ = α1 . . . αn

The well-formedness constraint ( ) in Figure 2 ensures unambiguous matching of expressions with concrete trees, as well as tractable inference in the presence of loops. Note that every concrete tree is a valid tree expression, since any t T is an expression τ with Var(τ) = Iter(τ) = FExp(τ) = .

Semantics When a program Prog(τ1, τ2) is applied to a concrete tree t, a valuation of variables and iterators is inferred for the input

Program P := Prog(τ1, τ2)

Tree Exp τ := 0 | α | τ τ with constraint ( )

Atomic Tree Exp α := ρ | Loop(I, ρ) where I Iter

Rooted Tree Exp ρ := (e, φ)[τ] where e Elm

Att Map Exp φ : Att Val

Val := Lit Var FExp

FExp := f(X) where f : Lit Lit X Var

Var := X, X1, X2, . . .

Iter := I, I1, I2, . . .

( ) if τ = α1 . . . αn then τ is well-formed if j <k<ℓ. Root(αj)=Root(αℓ) Root(αj)=Root(αk)

if αi = Loop(I, ρ) then j = i. Root(αi) = Root(αj)

Figure 2: Syntax of domain specific language

tree expression τ1 to match t. This valuation is then applied to the output tree expression τ2 to instantiate the output tree that is the result of the program. If no valuation can be found to convert the output to a concrete tree then the program is not applicable on the given input tree. Formally, we have JProg(τ1, τ2)Kt = t σ = Match(τ1, t) t = Apply(τ2, σ) t T otherwise where the valuation is represented by a subsititution σ, and the Match and Apply functions are used to generate σ from the input and apply it to the output. A substitution maps variables to literal values and iterators to a sequence of substitutions in which each substitution represents an iteration of the loop and contains the valuation of variables to apply in that iteration. Definition 2 (Substitution) A substitution σ Subs maps variables to literals and iterators to a sequence of substitutions. Thus σ : (Var Lit) (Iter Subsn) where n N. A substitution is a partial map and we write σ(X) = or σ(I) = when σ is undefined on X or I. We say σ and σ are compatible, written σ#σ , iff σ(X) = σ (X) on all X in which both are defined and if for any I we have σ(I) = (σ1, ..., σn) and σ (I) = (σ 1, ..., σ m) then n = m and σi#σ i for all i.

Match(τ, t) =

τ = 0 and t = 0 Match(φ, m) Match(τ1, t1) Match(τ2, t2) τ = (e, φ)[τ1] τ2 and t = (e, m)[t1] t2 Match(τ , t ) [I 7 (Match(ρ, r1), . . . , Match(ρ, rn))] τ = Loop(I, ρ) τ and t = r1 . . . rn t where

i.Root(ri)=Root(ρ) and Root(ρ) Root(τ ) otherwise

Apply(τ, σ) =

(e, Apply(φ, σ))[Apply(τ , σ)] τ = (e, φ)[τ ] Apply(ρ, σ1) . . . Apply(ρ, σn) τ = Loop(I, ρ) σ(I) = (σ1, . . . , σn) Loop(I, ρ) τ = Loop(I, ρ) σ(I)=

Apply(α, σ) Apply(τ , σ) τ = α τ

Match(φ, m) =

φ(a) Var [φ(a) 7 m(a)] a.φ(a) Var φ(a) = m(a)

Apply(φ, σ) = φ such that dom(φ ) = dom(φ) and

ℓ φ(a) = X σ(X) = ℓ f(ℓ) φ(a) = f(X) σ(X) = ℓ φ(a) otherwise

Figure 3: Match and Apply functions used in the semantics of programs

The union of substitutions σ σ is undefined if σ and σ are not compatible, and is otherwise defined as σu as follows. For variable X we have σu(X) = σ(X) or σu(X) = σ (X) if either are defined, and σu(X) = otherwise. For iterator I we have σu(I) =

σ(I) σ(I) = σ (I) =

σ (I) σ (I) = σ(I) =

(σ1 σ 1, . . . , σn σ n) σ(I) = (σ1, . . . , σn)

σ (I) = (σ 1, . . . , σ n) otherwise

The definitions of the Match and Apply functions are given in Figure 3 where they are defined recursively over the inductive structure of tree and attribute map expressions. The Match(τ, t) function returns a substitution that matches expression τ with concrete tree t. It builds such a substitution by taking the union of substitutions from separate substructures; the substitution is undefined if any of these unions are undefined. The Apply(τ, σ) function instantiates variables and loops in expression τ using the substitution σ, and any variables or iterators in τ that are not in σ remain uninstantiated. Programs in our DSL have a natural generality ordering given by a subsumption relation with respect to substitutions, which is analagous to the subsumption relation between first order formulae given in (Plotkin 1970). The program synthesis algorithm we describe in the next section infers programs that are minimal with respect to this ordering.

Definition 3 (Subsumption) For programs P = (τ1, τ2) and P = (τ 1, τ 2) we say that P subsumes P , written P P, iff there exists a substitution σ such that Apply(τ1, σ) = τ 1 and Apply(τ2, σ) = τ 2.

Synthesis Algorithm In this section we describe the program synthesis algorithm which, given a set of input-output examples of trees, returns

a program in our DSL that satisfies all the examples. In summary, the algorithm proceeds by constructing least general tree expressions over all the input trees and all the output trees, and then relates the variables in these two expressions to construct a valid satisfying program. The algorithm is defined in Figure 4, where the following definitions are used. For a tree t and an element e, we define First Root(t, e) iff t = r t and Root(r)={e}. We define a scope s Scopes as a sequence of iterators to represent a nested loop context, so that s := | I | I I

where is sequence concatenation. We also define

ΨVar : Scopes Valn Var

to be an injective map that assigns a distinct variable for a given scope and sequence of n values, and

ΨIter : Scopes Nn Iter

to be an injective map that assigns a distinct iterator for a given scope and sequence of n numbers. The maps ΨVar and ΨIter are used to generate unique variables and iterators when constructing expressions, which is a technique adapted from the first order syntactical anti-unification algorithm of (Plotkin 1970; 1971). In our case, since the generalizations are over tree expressions that may include variables and nested loop expressions, we define the mappings to be conditional on scopes in order to prevent name clashes in different nested loop contexts. To infer transformations between literal values, we assume a given black box function

Infer Literal Function : P(Lit) (Lit Lit)

which infers a function that satisfies the given input-output examples of literals or returns if no such function can be generated. Our implementation supports linear numeric transformations and syntactic string transformations using (Gulwani 2011).

1: function Infer Program((t1, t 1), . . . , (tn, t n)) 2: τ1 := Infer Tree Exp( , (t1, . . . , tn)) 3: τ2 := Infer Tree Exp( , (t 1, . . . , t n)) 4: for all X (Var(τ2) Var(τ1)) do 5: for all X Var(τ1) in the same scope as X do 6: f :=Infer Literal Function(Get Literals(X , X)) 7: if f = then 8: τ2 := τ2[X\f(X )] 9: if Var(τ2) Var(τ1) Iter(τ2) Iter(τ1) then 10: FAIL 11: return Prog(τ1, τ2) 1: function Infer Tree Exp(s, (t1, . . . , tn)) 2: if i. ti = 0 then 3: return 0 4: let e be such that j. First Root(tj, e) and i. e Root(ti) First Root(ti, e) 5: if no such e exists then 6: FAIL 7: for all i = 1 . . . n do 8: let ti = ri,1 . . . ri,Mi t i where e Root(t i) and j. Root(ri,j) = {e} 9: τ := Infer Tree Exp(s, (t 1, . . . , t n)) 10: if M1 = . . . = Mn then 11: for all j = 1 . . . M1 do 12: ρj := Infer Root Exp(s, (r1,j, . . . , rn,j)) 13: return ρ1 . . . ρM1 τ 14: I := ΨIter(s, M1, . . . , Mn) 15: ρ:=Infer Root Exp(s I, (r1,1,..., r1,M1, r2,1,..., rn,Mn)) 16: return Loop(I, ρ) τ 1: function Infer Root Exp(s , (r1, . . . , rn)) 2: if i. ri = (e, mi)[ti] then 3: φ := Infer Att Map(s, (m1, . . . , mn)) 4: τ := Infer Tree Exp(s, (t1, . . . , tn)) 5: return (e, φ)[τ] 6: else FAIL 1: function Infer Att Map(s , (m1, . . . , mn)) 2: if i, j. dom(mi) = dom(mj) then FAIL 3: let φ be a new attribute map 4: for all a dom(m1) do 5: if i. mi(a) = v then 6: φ(a) := v 7: else 8: φ(a) := ΨVar(s, m1(a), . . . , mn(a)) 9: return φ 1: function Get Literals(X1, X2) 2: let (s, v1, . . . , vn) = Ψ 1 Var(X1) 3: let (s , v 1, . . . , v m) = Ψ 1 Var(X2) 4: if n = m s = s then return 5: R := 6: for all i = 1 . . . n do 7: if vi, v i Var then 8: R:=R Get Literals(vi,v i) 9: else if vi, v i Lit then 10: R:=R {(vi, v i)} 11: else return 12: return R

Figure 4: Program synthesis algorithm

We next describe each of the functions in Figure 4. The main function is Infer Program, which returns a program from the given set of input-output pairs of trees. It starts by constructing tree expressions τ1 and τ2 over all the input trees and all the output trees (lines 1 and 2). It then attempts to replace every variable in τ2 not appearing in τ1 by a function of an input variable (lines 4-7), using Infer Literal Function. The Get Literals(X , X) function returns a set of pairs of literals that represent instantiations of the variables X and X, as determined by the ΨVar mapping. A program constructed from τ1 and τ2 is returned at the end if τ2 contains only variables and iterators appearing in τ1. Infer Tree Exp takes a scope and trees t1, . . . , tn, and returns a tree expression that generalizes over the given trees (the scope represents the loop context and is empty in the first call). If all trees are empty then the empty tree is simply returned (line 3). At line 4, the algorithm chooses the next root element to generalize over, which is selected as an element that occurs as the first root in all the expressions if it occurs at all (if no such element exists e.g. e1, e2 and e2, e1, then failure occurs as no unifying expressions can be found in line with the well-formedness constraint ( ) in Figure 2). The root element s number of occurrences in each tree ti is given by Mi and t i are the rest of the sibling trees (line 8). At line 9, a recursive call is made to find the generalization τ over the rest of the sibling trees. If the root element has the same number of occurrences in all the given trees, then loops need not be inferred on this element. Hence at line 12, a rooted tree expression ρj is inferred for each occurrence of the root element over all the examples and these are concatenated together with the result of the recursive call to give the final result. However, if the root element does not have the same number of occurrences among all examples, then a loop expression must be inferred for this element. To infer a loop, the algorithm uses the ΨIter map to generate a new iterator based on the occurrences of the root element in each of the examples. The loop expression is then generated by inferring a rooted tree expression over all occurrences of the root element in all examples, under the scope of the new iterator (line 15). Infer Root Exp infers a rooted tree expression given a scope and sequence of rooted trees. All given trees must have the same root element and the result is constructed as a combination of the generalizations inferred on the attribute maps and the subtrees recursively. Infer Att Map takes a scope and attribute maps, and returns a generalizing attribute map expression that introduces variables over attributes that do not have a consistent value across all the given attribute maps.

Theorem 1 (Soundness and minimality) If we have that Infer Literal Function is sound and we have Infer Program((t1, t 1), . . . , (tn, t n)) = P then i. JPKti = t i P . ( i. JP Kti = t i) P P P P

The proof follows by induction, by checking that for the generalization created at every step, a satisfying minimal substitution exists for every given example. For instance, in the base case of Infer Att Map, for each example mi there exists

a σi such that Apply(φ, σi) = mi, where for every generated variable X =ΨVar(s, v1, ..., vn) in φ we have σi(X)=vi.

Implementation and Extensions

We have implemented an add-in for Microsoft Power Point 2013, called Flash Format, which automates repetitive editing tasks in richly formatted presentation documents based on examples that the user can provide using the standard Power Point editing interface. These edits are reflected in the underlying XML specification of the document which, in this case, is the Office Open XML file format (OOXML) (International Organization for Standardization 2008). The system is based on the DSL and the algorithm described above, and incorporates the following extensions to the core algorithm to optimize for certain cases that arise in practice. Disjunctions. Some tasks may be expressed by a set of programs in our DSL if a single program cannot express the entire task. For instance, if a task involves different transformations on different inputs, a set of programs can be used to represent a case statement describing different selection conditions and corresponding outputs, e.g., if the user gives examples of text boxes changing colour and arrows becoming thicker, then this may be expressed as a disjunction of two programs describing each transformation separately. Although such disjunctive tasks could in theory be accomplished by the user through a succession of independent subtasks, our system applies the following optimization: if for a given set of examples a single program that covers all the examples cannot be found, then the system searches for a set of programs over a partition of the example set. Domain specific information. A number of attributes and elements in the Power Point OOXML format relate to nonvisual or meta properties of objects (e.g., object IDs, language settings) or minor visual properties (e.g., autofit options, space before/after). Our system is designed to avoid sensitivity of inferred programs to specific settings for a fixed set of such properties and always assigns variables rather than literal values for such properties when inferring generalizations.

Experimental Evaluation

We performed an evaluation of the system using examples from online help forums (http://www.msofficeforums.com, http://www.vbaexpress.com/forum). Forums serve a wide range of topics (e.g., help with VBA syntax, Power Point interface/features) and so we manually searched for questions about repetitive formatting tasks. In these requests the users describe repetitive tasks that they would like to automate and an expert usually provides a code in the macro programming language VBA that fulfills the task. We chose 18 such questions from Power Point forums and 2 questions from Word forums concerning tables that could also be applicable to editing in Power Point. Figure 5 shows the results of our evaluation on the 20 questions (T1 - T20) in which we applied our system to automate the specified task from examples. The tasks cover a wide range of formatting features in Power Point documents, including shapes, images, charts, tables, bullets, margins,

Task R1 R2 R3 Avg T1 2 2 2 2 T2 4 4 3 3.7 T3 4 5 5 4.7 T4 13 11 11 11.7 T5 3 3 2 2.7 T6 2 4 2 2.7 T7 4 2 3 3 T8 8 7 8 7.7 T9 3 3 3 3 T10 11 10 11 10.7

Task R1 R2 R3 Avg T11 2 4 2 2.7 T12 4 6 7 5.7 T13 2 2 2 2 T14 2 3 3 2.7 T15 2 2 2 2 T16 6 5 5 5.3 T17 3 4 3 3.3 T18 2 2 3 2.3 T19 2 3 3 2.7 T20 3 3 3 3

Figure 5: Number of examples required in 20 forum tasks

fonts, borders, size, positioning, scaling, colors, styles, and indents. In a few cases the task also involved requests other than formatting (e.g., importing images and then formatting), in which case we only addressed the formatting component. Most tasks had specific selection criteria on where to apply changes, e.g., change only text of a certain font and size (T11), change only circle shapes that are red in color (T15), change the indentation of any text that has a certain font but only when it appears inside a table (T19). Five of the tasks had no selection criteria (changes were required everywhere). Since actual documents associated with the tasks were not available in the forum questions, we chose them either from a collection of files from the internet or, if the task described a particular document structure, then we created a sample document based on that description (e.g., presentation contains a chart on each slide). For each task we conducted three runs (R1, R2, R3), in which a different set of examples was given to the system. The number of examples required in all the runs are shown in Figure 5. Overall, an average of 4.17 examples were required for task completion (maximum 13 and minimum 2), with execution times normally under a second and not exceeding 5 seconds for any execution on any task. For 15 of the 20 tasks it was possible to generate a single (non-disjunctive) program in our DSL to complete the task.

Related Work A number of Programming by Example techniques have been developed recently for automating repetitive data manipulation tasks, including syntactic and semantic string transformations (Gulwani 2011; Singh and Gulwani 2012a; Liang, Jordan, and Klein 2010; Menon et al. 2013), number transformations (Singh and Gulwani 2012b), and spreadsheet table layout transformations (Harris and Gulwani 2011). Programming by demonstration (PBD) is also a closely related technique (Lau et al. 2003; Witten and Mo 1993; Miller and Myers 2001) where transformations are inferred from the trace of actions that the user performs rather than the input and output states, as in PBE. The problem that we address and the method of inferring transformations in structured documents with XML representations are beyond the scope of all of this previous work. A recent work on integrating PBE with natural language program-

ming (Manshadi, Gildea, and Allen 2013) shows that for syntactic string transformations fewer examples are required in the presence of natural language specifications. Thus, it would be interesting to explore ways to combine this method with our least general generalization approach. A number of machine learning methods have been applied to learning XML document transformations in the context of information integration and extraction (Gilleron et al. 2006; Chidlovskii and Fuselier 2005; Tsochantaridis et al. 2005). In particular, (Gilleron et al. 2006) show how Conditional Random Fields (CRF) can be applied to achieve relatively high precision in node labelling with around 20 examples. However, the set of editing tasks that can be expressed through labelling of a predefined XML trees is limited. In general, in the interactive PBE setting the aim is to have a very small number of examples (usually less than 10), which is hard to achieve by statistical modelling methods. Our DSL has been designed specifically for this setting: it supports explicit specification of the selection criteria in input expressions to target the highly selective nature of the transformations we consider. This design is also in contrast to approaches using existing XML transformation languages such as XSLT (Stube 2004). Indeed, output tree expressions in such languages are explicitly defined but constraints on input structure would be more challenging to infer. The technique of the least general generalization that we use is based on Plotkin s work on inductive inference (Plotkin 1970; 1971), which laid the foundations of inductive logic programming. A range of methods have since been explored in the inference of logic programs from examples (Muggleton and Feng 1990). We use Plotkin s ideas in a PBE setting where we formulate least generalizations in a novel DSL for expressing XML transformations. While our work lies outside of logic programming, interesting related work is on feature terms (At-Kaci and Podelski 1993; Carpenter 1992), a generalization of first order terms that are used in formalizing object oriented declarative languages. While set-valued features in feature terms bear a similarity to our iteration variables, the notion of subsumption in the former case is different. Indeed, it requires a 1-1 matching between elements in set-valued features while, in our case, the iteration variables allow a varying number of elements in ordered sequences. As described in (Ontanon and Meseguer 2012), set-valued features also lead to efficiency challenges when checking subsumption between feature terms while, in our ordered setting, subsumption can be checked in time that is linear in tree size.

Conclusion We have described a Programming by Example approach which extends the applicability of the paradigm to the domain of structural transformations in richly formatted documents. This is based on the notion of least general generalization which provides an implicit ranking strategy and avoids the scalability issues in state of the art PBE systems. Our DSL and algorithm have been designed with a natural subsumption ordering on programs with respect to which we can find minimal programs efficiently, while also delivering expressivity sufficient to handle target transformations with

support for variables, functions, and loop expressions in the language. Experiments on forum examples demonstrate the feasibility of the approach and its applicability to interactive editing of complex documents. Apart from the evaluation of our method on forum examples presented here, we are also conducting user studies and exploring alternative user interfaces to observe how users respond to a system based on least generalizations and how they can effectively give examples to complete repetitive tasks. We also plan to explore the application of our approach to other structured transformation domains such as program transformations in software development environments (Meng, Kim, and Mc Kinley 2011). This may require extending the DSL features, e.g., loops using more sophisticated boolean conditions. Increased expressivity usually means that more examples are needed in PBE approaches, and it would therefore be interesting to explore techniques such as (Manshadi, Gildea, and Allen 2013) to integrate natural language input with our approach in order to target more complex domains.

Acknowledgments We would like to thank the anonymous reviewers for their very helpful feedback that has improved this paper.

References At-Kaci, H., and Podelski, A. 1993. Towards a Meaning of LIFE. J. Log. Program. 16(3):195 234. preliminary version: PLILP 1991: 255-274. Carpenter, B. 1992. The Logic of Typed Feature Structures. Cambridge: Cambridge University Press. Chidlovskii, B., and Fuselier, J. 2005. A Probabilistic Learning Method for XML Annotation of Documents. In Kaelbling, L. P., and Saffiotti, A., eds., IJCAI, 1016 1021. Professional Book Center. Gilleron, R.; Jousse, F.; Tellier, I.; and Tommasi, M. 2006. XML Document Transformation with Conditional Random Fields. In Fuhr, N.; Lalmas, M.; and Trotman, A., eds., INEX, volume 4518 of Lecture Notes in Computer Science, 525 539. Springer. Gulwani, S. 2011. Automating String Processing in Spreadsheets using Input-Output Examples. In Principles of Programming Languages (POPL), 317 330. Gulwani, S. 2012. Synthesis from Examples: Interaction Models and Algorithms. In 14th International Symposium on Symbolic and Numeric Algorithms for Scientific Computing (SYNASC), 8 14. Harris, W. R., and Gulwani, S. 2011. Spreadsheet Table Transformations from Examples. In Hall, M. W., and Padua, D. A., eds., Programming Language Design and Implementation (PLDI), 317 328. ACM. International Organization for Standardization. 2008. Office Open XML File Formats. ISO/IEC 29500-1:2008. Lau, T. A.; Wolfman, S. A.; Domingos, P.; and Weld, D. S. 2003. Programming by Demonstration Using Version Space Algebra. Machine Learning 53(1-2):111 156.

Liang, P.; Jordan, M. I.; and Klein, D. 2010. Learning programs: A hierarchical bayesian approach. In Frnkranz, J., and Joachims, T., eds., International Conference on Machine Learning, 639 646. Omnipress. Lieberman, H., ed. 2001. Your Wish is My Command: Programming by Example. Morgan Kaufmann Publishers. Manshadi, M. H.; Gildea, D.; and Allen, J. F. 2013. Integrating programming by example and natural language programming. In des Jardins, M., and Littman, M. L., eds., AAAI. AAAI Press. Meng, N.; Kim, M.; and Mc Kinley, K. S. 2011. Systematic Editing: Generating Program Transformations from an Example. In Hall, M. W., and Padua, D. A., eds., PLDI, 329 342. ACM. Menon, A. K.; Tamuz, O.; Gulwani, S.; Lampson, B. W.; and Kalai, A. 2013. A Machine Learning Framework for Programming by Example. In ICML (1), volume 28 of JMLR Proceedings, 187 195. JMLR.org. Miller, R. C., and Myers, B. A. 2001. Interactive Simultaneous Editing of Multiple Text Regions. In USENIX Annual Technical Conference, 161 174. Muggleton, S., and Feng, C. 1990. Efficient Induction of Logic Programs. In First Conference on Algorithmic Learning Theory, 368 381. Ontanon, S., and Meseguer, P. 2012. Efficient Operations in Feature Terms Using Constraint Programming. In Muggleton, S.; Tamaddoni-Nezhad, A.; and Lisi, F. A., eds., ILP, volume 7207 of Lecture Notes in Computer Science, 270 285. Springer. Plotkin, G. D. 1970. A Note on Inductive Generalization. Machine Intelligence 5:153 163. Plotkin, G. D. 1971. A Further Note on Inductive Generalization. Machine Intelligence 6:153 163. Singh, R., and Gulwani, S. 2012a. Learning Semantic String Transformations from Examples. PVLDB 5(8):740 751. Singh, R., and Gulwani, S. 2012b. Synthesizing Number Transformations from Input-Output Examples. In Madhusudan, P., and Seshia, S. A., eds., Computer Aided Verification (CAV), volume 7358 of Lecture Notes in Computer Science, 634 651. Springer. Stube, B. 2004. Automatic Generation of XSLT by Simultaneous Editing. Massachusetts Institute of Technology (Ph D Thesis). Tsochantaridis, I.; Joachims, T.; Hofmann, T.; and Altun, Y. 2005. Large Margin Methods for Structured and Interdependent Output Variables. Journal of Machine Learning Research 6:1453 1484. Witten, I. H., and Mo, D. 1993. TELS: learning text editing tasks from examples. In Watch what I do: programming by demonstration, 183 203.