Synthesizing Pattern Programs from Examples

Synthesizing Pattern Programs from Examples

Sunbeom So, Hakjoo Oh

Proceedings of the Twenty-Seventh International Joint Conference on Artificial Intelligence
Main track. Pages 1618-1624. https://doi.org/10.24963/ijcai.2018/224

We describe a programming-by-example system that automatically generates pattern programs from examples. Writing pattern programs, which produce various patterns of characters, is one of the most popular programming exercises for entry-level students. However, students often find it difficult to write correct solutions by themselves. In this paper, we present a method for synthesizing pattern programs from examples, allowing students to improve their programming skills efficiently. To that end, we first design a domain-specific language that supports a large class of pattern programs that students struggle with. Next, we develop a synthesis algorithm that efficiently finds a desired program by combining enumerative search, constraint solving, and program analysis. We implemented the algorithm in a tool and evaluated it on 40 exercises gathered from online forums. The experimental results and user study show that our tool can synthesize instructive solutions from 1–3 example patterns in 1.2 seconds on average.
Keywords:
Knowledge Representation and Reasoning: Automated Reasoning and Theorem Proving
Humans and AI: Computer-Aided Education