Synthesizing Pattern Programs from Examples

1 Introduction

Writing pattern programs is one of the most popular programming exercises for novice programmers, where the task is to write a program that produces patterns of characters or stars that are arranged according to some logical rules. Examples include geometric patterns such as triangles, squares, and parallelograms.

Learning to write pattern programs in introductory programming courses is important because of two reasons. First, pattern programs provide excellent opportunities for enhancing key programming skills that involve nontrivial nested loops and conditional statements. Secondly, students can acquire logical thinking by trying to discover hidden rules in the pattern examples.

In this paper, we describe a programming-by-example system that automatically learns pattern programs from examples. Beginners often find it difficult to write correct pattern programs by themselves. Unfortunately, manually providing guidance in online/offline classes simply does not scale for the increasingly large number of students. Our goal is to build

Hakjoo Oh

Korea University hakjoo oh@korea.ac.kr

an automated tool that can help students to improve their programming skills without human teachers.

To that end, we first studied various online forums and designed a domain-specific language that supports a large class of pattern programs that students struggle with. Next, we developed a novel synthesis algorithm that effectively combines enumerative search, constraint solving, and program analysis. The crux of our algorithm is the automatic provision of program components that are required to write correct programs. We demonstrate this capability in Section 2.

We implemented our approach in a tool, PAT, and evaluated it on 40 benchmark problems gathered from online forums. Some of the benchmarks are challenging even for skilled programmers, requiring them to discover complex rules hidden in the patterns. The experimental results show that our approach is remarkably efficient; PAT can synthesize the desired programs only from 1-3 example patterns in 1.2 seconds on average. Further, our user study with 23 undergraduate students shows that PAT can aid them by providing instructive code; 91% responded that programs generated by PAT have qualities that are higher than or similar to humanwritten code, in terms of simplicity and readability.

We summarize our contributions below:

• We present a new programming-by-example system that automatically synthesizes pattern programs from examples. We make our tool and data publicly available. 1
• We present a novel synthesis algorithm that combines three techniques: enumerative search, constraint solving, and program analysis. This combination enables PAT to efficiently synthesize pattern programs.
• We provide detailed evaluations of the tool with 40 pattern tasks from online forums and 23 students.

2 Illustrative Examples

In this section, we illustrate our tool, PAT, with two programming problems gathered from online forums.

To use our tool, it suffices to provide example patterns only. Without any other hints from a user, PAT is able to generate a program that reproduces the patterns while generalizing the behavior beyond the given examples.

1 http://prl.korea.ac.kr/pat

Problem 1 (Isosceles Triangle) The first problem is to write a program that displays isosceles triangles (i.e., triangle with two equal sides). One possible example pattern is as follows:

Given this pattern, PAT takes 0.04 seconds to synthesize a program below that draws the pattern:

for i in N do: for j in N - i do: print for j in 2 ∗ i - 1 do: print ⋆ print

The outermost loop iterates through the rows of the triangle, where N represents the number of the rows to be displayed. In each iteration of the rows, two inner loops are used to print N - i blanks ( ) followed by 2 ∗ i -1 star symbols (⋆). Also, the program puts a newline ( ) upon completion of each row. In this case, PAT can generate the program from a single example pattern.

Problem 2 (Hollow square with diagonals) Consider the problem of generating hollow squares with diagonals inside:

This problem has remained unanswered in an online forum 2 for seven months.

With PAT, however, we can solve this problem in 5.2s. Given the two examples above, PAT generates the following:

for i in N do: for j in N do: if ( i = 1 || i = N || j = 1 || j = i || j = N - i + 1 || j = N): print ⋆ else: print print

The program prints out ⋆ when one of the following conditions holds: the first row (i = 1), the last row (i = N), the first column (j = 1), the last column (j = N), the lowerright-oriented diagonal (j = i), and the upper-right-oriented diagonal (j = N - i + 1). PAT accomplishes this by introducing a conditional statement within the nested loops.

We finish this section by summarizing key features of PAT demonstrated through the examples:

• PAT is able to quickly generate instructive solutions for a broad range of pattern programming tasks, which allows students to benefit without asking questions and waiting responses in online forums for months.

2 http://codeforwin.org/2015/07/c-program-to-print-diamond-

star-pattern.html, accessed 31-Jan-2018

• PAT does not require any hints from a user. PAT automatically infers program components such as integers necessary for writing the program. By contrast, existing program synthesizers typically require the user to manually provide such components, which is unrealistic for end-users. We provide detailed discussion in Section 6.
• PAT works with only few example patterns, minimizing the burden of writing examples on users. In our experiments, it was enough to provide 1-3 examples to obtain desired programs.

3 Domain-Specific Language (DSL)

Figure 1 presents our domain-specific language (DSL) for describing patterns. In program synthesis, choosing a right DSL is a key to success [Gulwani et al., 2017], as the DSL plays an important role in balancing expressiveness for a target domain and efficiency of a synthesis algorithm. General-purpose languages such as C are excessive for our purpose, only to impair the efficiency of the synthesis procedure. Thereby, we have carefully designed our DSL based on pattern programming tasks that novices struggle with by studying online forums. Syntax We observed that a large number of pattern programs share a common structure and therefore made the following design decisions:

• A program (r) is a single loop (for i in N do c; ) that iterates through rows of the pattern, where each row is followed by a newline symbol ( ). Variables N and i are fixed over the program, which denote the number of rows and the iterator, respectively.
• The body (c) of the row-loop consists of a sequence of column loops. A column loop (for j in a do p) iterates through columns for a times. j is a fixed variable that is used in all column-loops.
• The body (p) of a column-loop consists of a symbol (l ∈ {⋆, }) or a conditional expression (if b l1 l2).
• An arithmetic expression (a) is a linear expression (x ∗ N + y ∗ i + z) that only involves variables N and i, where x, y, and z are integer constants. At first glance, this seems overly restrictive, but most ⋆-patterns can be captured with this expression.
• A boolean expression (b) includes equalities for the beginning of the row (i = 1), the end of the row (i = N) and the column index (j = a), or a disjunction (b1 || b2).

A program may have holes (♦,△,©,□) during the synthesis process, but the holes never appear in a final program. Expressiveness Informally, our DSL is able to express patterns with following characteristics:

1. Patterns consisting of straight lines that are inclined at various angles (e.g., X-pattern in Problem 2).
2. Patterns consisting of subpatterns that are horizontally aligned (e.g., a subpattern is hidden on the left of the main pattern in Problem 1, drawn using blanks).

The first- and second features can be captured because, in our DSL, arithmetic expressions are linear and programs can have multiple inner column-loops, respectively.

Figure 2: Semantics of the DSL

However, PAT may not be able to write patterns in which subpatterns are vertically aligned, since those patterns usually require multiple outer loops while our program has only one outer loop. Nevertheless, PAT can be useful in those cases, too. For example, imagine a pattern where an upper half is a triangle and a lower half is a square. Even if a student does not know how to write a corresponding solution at once, it is relatively easy to observe that different pattern rules may be needed to implement each of two subpatterns (triangle and square) and thereby two outer loops may be needed to write a total solution. Then, based on this observation, the student can get a final solution by separately applying PAT to each subpattern and combining the results.

Semantics A program in our DSL evaluates to a string over Σ = {⋆, , }. The semantics is formally defined in Figure 2. Let X be a set of program variables, i.e., X = {i, j, N}. A memory state m is a partial function from variables to integers (Z), i.e., m ∈ M = X → Z. Then, the semantics of the DSL is defined by the functions A[[a]] : M → Z, B[[b]] : M → B (= {true, false}), P[[p]] : M → Σ, and C[[c]] : M → Σ∗ . We write · for string concatenations, i.e., n· k=1 Ak = A1 · · · An. Semantics of holes is undefined.

Synthesis Problem Suppose we are given a set of example patterns E ⊂ Σ∗ . Then, our goal is to find a complete program in the DSL that correctly describes the given patterns. Formally, we aim to find the body c of the outer loop such that

where m = [N ↦→ rowe] and rowe is the number of rows (i.e., the number of s) in each example e.

4 Synthesis Algorithm

Now we present our algorithm for efficiently solving the synthesis problem, which combines enumerative search, constraint solving, and static program analysis.

Algorithm 1 Synthesis Algorithm

Input: A set of examples E Output: A program consistent with E 1: W ← {s0} where s0 = □ 2: Γ←a candidate set of integer triplets 3: repeat 4: Pick the smallest state s fromW 5: if s is a terminal state then 6: if solution(s) then return (for i in N do (s; )) 7: else 8: W ←W ∪ next(s) 9: until W = ∅

4.1 Enumerative Search

Enumerative search has been used as one of the most effective ways in program synthesis [Udupa et al., 2013; Feser et al., 2015; Lee et al., 2016; So and Oh, 2017; Feng et al., 2017]. Below, we transform the synthesis problem to a state-search problem and describe a basic enumerative algorithm for it. Search Problem Suppose a synthesis task E is given. We define a transition system (S,⇝, s0, F) where S is a set of states, (⇝) ⊆ S × S is a transition relation, s0 ∈ S is an initial state, and F ⊆ S is a set of final solution states.

• States: A state s ∈ S is a column-loop statement c that possibly has holes (♦, △, ©, □).
• Initial State: An initial state s0 is a column-loop hole □.
• Transition Relation: Transition relation (⇝) ⊆ S × S determines next states directly reachable from the current state. Figure 3 shows the relation as a set of inference rules, where ⇝a, ⇝b, ⇝p, and ⇝ denote the one-step transition of arithmetic expressions, boolean expressions, symbols, and column-loops, respectively. That is, holes are replaced with any other syntactic components of the same type. Given a state s, we write next(s) for the set of all immediate following states from s, i.e., next(s) = {s′ | s ⇝ s′ }.
• Solution States: Let us write s ̸⇝ to denote a terminal state, i.e., a state without holes. Then, a state s is a solution of the synthesis problem iff s is a terminal state and it is consistent with all of the given examples:

In the transition relation for arithmetic holes

we assume that a finite set Γ ⊂ Z×Z×Z of integer triples is given at the moment, which will be described in Section 4.2. Note that, with this assumption, the successors (i.e., next(s)) of a state s are always finite.

Search Algorithm Algorithm 1 shows the basic architecture of our synthesis algorithm. The algorithm initializes the workset W with s0 (line 1). Then, at line 2, we compute the set of integer triples Γ that will be used in programs (Section 4.2). We pick and remove the smallest sized state s from

W (line 4), where the sizes are estimated by our heuristic cost model based on the principle of Occam's razor. If the chosen state is a solution state, we return a program where a body c is that state (line 6). Otherwise, we obtain next states of s, add them to the workset (line 8), and then repeat the loop.

A standard way of improving enumerative search is to prune away syntactically different but semantically equivalent program states (e.g., [Feser et al., 2015; Lee et al., 2016; So and Oh, 2017]). We use three techniques to do so.

First, we exclude states that have unsatisfiable (i.e., always false) expressions, by checking boolean satisfiability. For example, consider a state below:

Note that the condition (j = N - i + 1) is unsatisfiable since the enclosing loop iterates only N - i times (i.e., N - i < N - i + 1). Pruning the above state is safe, due to the enumerative search for a simpler and semantically equivalent alternative (□; for j in N -i do ). Secondly, we simplify a state that has syntactically the same boolean expressions. For example, (i = 1 || i = 1 || △) is simplified to (i = 1 || △). Lastly, we reorder boolean expressions in a particular order. For instance, assuming (i = -) precedes (j = -) in the order, (j = 1 || i = 1) is rewritten as (i = 1 || j = 1). These three optimizations are implicitly conducted by next(s).

4.2 Constraint Solving for Inferring Integers

A key feature of our algorithm is that the set Γ ⊂ Z × Z × Z of integer component triples is automatically inferred from example patterns. Achieving this consists of two steps. First, we generate constraints that encode necessary conditions for solutions. Secondly, we solve the constraints using an offthe-shelf SMT solver to obtain a model (i.e., Γ).

Specifically, given a set E of examples, we generate formula ΦE = ∧e∈E (φe ∧ ϕe), where φe and ϕe are generated as follows:

1. φe constrains the number of iterations of column-loops. Note that every column-loop in a solution program cannot iterate beyond the columns of each given example e. Also, a column-loop iterates at least zero times. Combining these two conditions, we generate

where colie denotes the number of columns (up to the position right before a newline) at ith row in an example e ∈ E. The linear expression in φe is an arithmetic expression a (Figure 1) where N is replaced with rowe.

1. ϕe limits the values of z so that the absolute value of z is smaller than the number of rows in each example:

The second condition ϕe is intended to rewrite a large value of z by a small one with additional variables (N or i). We do this rewriting because programs with smaller constant terms are likely to generalize better than those with larger constant terms do. We can still find solution programs even with this extra condition, if we can represent an expression with a large z (≥ |rowe|) by expressions with small zs (< |rowe|). For example, supposing the number of rows of a given example is 5 (i.e., rowe = 5), we can rewrite an arithmetic expression 6 by N + 1.

Note that solving the constraint ΦE always produces a finite number of integer triples Γ. To see why, first observe that ΦE has a series of inequalities over x, y, and z, connected by conjunctions. Then, we need to show that any two of x, y, z are finitely bounded through the inequalities: in our case, y and z. We explain y-case first. Assuming the number of rows in each example is at least two (i.e., ∀e ∈ E.rowe ≥ 2), we can conclude the range of y is finite from φe, because only the coefficients of ys vary in each conjunct of φe, and each conjunct in φe has both a lower- and upper bound (0 and colie , respectively). For example, from φe in Example 1 (i.e., the first four conjuncts), we get -1 ≤ y ≤ 2. Secondly, from ϕe, we can easily see that z also has a finite range.

Example 1 Consider the Problem 1 in Section 2. We can generate constraints that correspond to the given example:

where rowe = 4, and col1 e through col4 e are 4,5,6,7, respectively. Solving the constraints, we get Γ = { (-1, 1, 3), (-1, 2, 2), (-1, 2, 3), (0, 0, 0), (0, 0, 1), (0, 0, 2), (0, 0, 3), (0, 1, -1), (0, 1, 0), (0, 1, 1), (0, 1, 2), (0, 1, 3), (0, 2, -2), (0, 2, -1), (1, -1, 0), (1, -1, 1), (1, 0, -3), (1, 0, -2), (1, 0, -1), (1, 0, 0), (1, 1, -3), (1, 1, -2), (1, 1, -1), (2, -1, -3) }. Observe that (1,-1,0) and (0,2,-1) appears in the solution program.

4.3 Pruning using Static ProgramAnalysis

We observed that many candidates encountered during the enumerative search can never reach solution states, only hindering search for solutions. A common example is given in Example 2. Our goal is to effectively prune away this type of candidates in a safe manner. To achieve the goal, we design a static analysis, which enables us to identify states that eventually fail to be solutions, and perform pruning using it.

Figure 4: Abstract semantics

Designing analysis In order to identify failure candidates, we first define abstract semantic functions in Figure 4: ̂ A[[a]] : ̂M → ̂Z, ̂ B[[b]] : ̂M → ̂B, ̂ P[[p]] : ̂M → 2Σ, and ̂ C[[c]] : ̂M→ 2Σ∗ . An abstract memory state ̂m ∈ ̂M is a mapping from variables to abstract integers (̂Z), where ̂Z = {⊤̂A} ∪ Z with a partial order z1 ⊑̂Z z2 ⇐⇒ (z2 = ⊤̂A). ̂B = {⊤̂B , ̂ true,̂ false} is abstract boolean values with a partial order b1 ⊑̂B b2 ⇐⇒ (b2 = ⊤̂B ).

A key component in designing the analysis is to define sound semantics for holes, in order to over-approximate all possible concrete behaviors of terminal states reachable from a current candidate state. For the arithmetic- and boolean expressions holes (♦, △), we conservatively assign top values, i.e., ̂ A[[♦]](̂m) = ⊤̂A and ̂ B[[△]](̂m) = ⊤̂B . For the symbol hole (©), we take the union of ⋆ and , i.e., ̂ P[[©]]( ̂m) = {⋆}∪{ }. Lastly, we compute the column-loop hole (□) as Kleene Star on star and blank, i.e., ̂ C[[□]] = ({⋆} ∪ { })∗ . A novel aspect is that we use regex operations for overapproximations of string values.

Pruning with analysis Suppose a set of examples E ⊂ Σ∗ is given, and we are exploring a candiate s. Then, we prune the candidate if the following predicate pruned(s) holds:

where ̂m = [N ↦→ rowe]. That is, we prune the candidate iff the over-approximated result obtained by running the analysis on the candidate does not contain the desired output (i.e., the given example) for some examples e ∈ E, since all further search of such the candidate will fail to produce solutions.

Example 2 Suppose the pattern example of Problem 1 in Section 2 is given. Then, a candidate ((for j in i do ⋆);□) needs not be searched further, because the analysis result on the candidate (the right below, starting with ⋆) does not contain the expected output (the left below, starting with ):

We finalize our synthesis algorithm by revising next(s):

5 Evaluation

Experimental setup To demonstrate the effectiveness of our approach, we collected 40 benchmarks from several online forums. These problems are comprised of various geometric patterns that are helpful for students' learning, including challenging ones. All of the experiments were conducted on MacBook Pro with Intel Core i7 and 16GB of memory.

Algorithm performance The experimental results show that our synthesis algorithm is remarkably efficient; PAT solves the benchmarks 1.2 seconds on average, only from 1-3 examples (the column "Final" and "Ex" in Table 1). However, when we performed only the enumerative search (Section 4.1, 4.2) without our program-analysis-guided pruning (Section 4.3), seven of the benchmarks timed out (> 1 hour), as shown in the column "Enum" in Table 1. Assuming the running time of each of the seven benchmark as 1 hour, the average running time becomes 737.9 seconds (x615 slowdown). This result indicates two things. First, although our DSL is restrictive to introductory pattern programs, its search space is never trivial, hence an effective pruning method should be applied. Secondly, our pruning is powerful to dramatically cut down on the search space.

After the experiments, we manually checked that all of the synthesized programs are correct. Also, as demonstrated in Section 2, the generated programs are explainable, understandable and instructive, capturing core pattern rules of the given pattern examples.

User study We also evaluated PAT with 23 undergraduates, who have taken the introductory programming course, in order to inspect whether PAT is actually helpful to students. The study proceeded as follows. We first requested the students to solve several pattern programming problems, and submit their code in the C language. After receiving the code, we asked the students to freely use PAT in our web demo page for one day. Finally, we asked four survey questions:

• Q1. Programs generated by PAT are overall simple and easy to understand.
• Q2. Compared to their own submitted programs, programs generated by PAT are simpler and easier to understand.
• Q3. PAT helps to learn programming.
• Q4. PAT is easy to use.

These questions were designed to evaluate code qualities of PAT (Q1, Q2), helpfulness in learning programming (Q3), and usability (Q4). Note that Q2 is a rigorous version of Q1, in that the students can answer to Q1 just by running PAT for certain patterns and observing generated solutions, without efforts to solve problems. Especially for Q3, we requested to describe reasons for their answers, allowing multiple responses. In the demo page, programs written by PAT were displayed after converted into C from our DSL.

Table 2 shows results of our survey. For Q1 and Q2, the students highly appreciated both code simplicity and readability of PAT. Notably, for Q2, 91% responded that PAT's programs have higher or similar qualities, compared to code written by themselves. We believe that reasons for this result may come from our simple DSL design and our search strategy, which prefers a small-sized candidate first (Section 4.1).

In particular, for the benchmark #39, our manual study on the 10 correct submissions reveals that, only two successfully captured core pattern rules. The remaining eight were composed of messy rules without core rules, although they are somehow correct; the worst case solution consisted of 54 lines in C with 7 inner loops (vs. 18 lines with one inner loop by PAT). For Q3, 74% agreed that PAT is helpful in learning programming. For Q4, no negative answers were reported.

We further examined reasons behind students' answers for Q3. 74% (17 students) answered "Agree" for following reasons: improving programming skills by learning instructive code generated by PAT (71%, 12/17), realtime-feedback without asking to human instructors (65%, 11/17), and role as an automated teacher for shy students who are reluctant to ask in classrooms (47%, 8/17).

In contrast, among the three students who disagreed with Q3, one expressed that PAT's code are hard to follow, which conflicts with the majority. The rest two disagreed, worrying about students' blind reliance on PAT without enough endeavors to solve problems. However, we still believe that PAT can be helpful under proper guidance of instructors, e.g., allowing to use PAT only after submitting assignments.

Finally, we collected additional feedback for future improvements: translations into other languages (e.g., Java), and dealing with more complex patterns. The former can be easily done. For the latter, we believe that extending PAT to solve programming-competition-level pattern problems, which require to write complicated recursive functions with nontrivial arguments 3 , is one interesting research direction.

6 RelatedWork

Automatic programming tutor There have been a number of researches on building intelligent programming tutor systems that aim to help novice programmers: generating feedback on semantic errors in students' submissions [Kim et al., 2016; Singh et al., 2013; Gulwani et al., 2014; Kaleeswaran et al., 2016], step-by-step hint generation for Haskell [Gerdes et al., 2017] and Python [Rivers and Koedinger, 2017], and many others. Our work differs from prior works in two ways. First, PAT can help students who do not know how to start writing programs by synthesizing solutions from examples, while prior works aim at producing feedback on code already written by students. Secondly, to the best of our knowledge, PAT is the first automatic tutor that helps to practice pattern programs.

Comparisons with other synthesis approaches In many program synthesis applications, the DSL has played a key role in speeding up search process by reasonably restricting search space on target domains: automating string manipulation in spreadsheet [Gulwani, 2011; Kini and Gulwani, 2015; Raza et al., 2015; Wu and Knoblock, 2015; Ellis and Gulwani, 2017], automated data extraction [Raza and Gulwani, 2017], and transformations on tree data structures [Yaghmazadeh et al., 2016], etc. In this context, we designed the DSL for efficiently synthesizing pattern programs.

Technically, our algorithm differs from previous works in two aspects. First, most notably, by applying constraint solving, PAT can automatically infer integer components, which will be used in a solution program, without manual provision from end-users. By easing burden on users in this way, we believe that our idea of applying constraint solving for inferring program components can benefit many other program synthesizers, e.g., [Wang et al., 2017; So and Oh, 2017]. Secondly, we developed an effective and safe pruning method that performs static program analysis using regex operations.

7 Conclusion

In this paper, we presented a new programming-by-example system that synthesizes pattern programs from examples. We first carefully designed the DSL for efficiently synthesizing a variety of pattern programs. Next, we developed a novel synthesis algorithm that combines enumerative search, constraint solving, and program analysis. We demonstrated the effectiveness of our approach with 40 pattern tasks, and the helpfulness with 23 students.

3 e.g., https://www.acmicpc.net/problem/2447

Acknowledgments

We thank Joonho Lee and Dowon Song for discussions on designing the survey questions. This work was supported by Samsung Research Funding & Incubation Center of Samsung Electronics under Project Number SRFC-IT1701-09. This research was also supported by Basic Science Research Program through the National Research Foundation of Korea (NRF) funded by the Ministry of Science, ICT & Future Planning (NRF-2016R1C1B2014062).