Technical Report PHD-2017-09

Title: Exact Programming by Example
Authors: Dana Drachsler Cohen
Supervisors: Eran Yahav
Abstract: The vast majority of computer users do not know how to code, and thus can only leverage computers to the extent provided by distributed softwares. The abundance of softwares that target the same domains demonstrates that off-the-shelf softwares can be complex for users or not sufficiently suitable for their needs. Programming by example (PBE) has flourished in recent years to mitigate exactly this problem and enable users to write their own programs by describing their intent only through examples, without writing or examining a single piece of code. An inherent problem of PBE is that examples often under-specify the full intent of the users and thus PBE algorithms must heuristically choose one program from many non-equivalent programs. While this approach has been shown to be successful in some cases, it cannot guarantee that the user's intent will be fully captured, and is thus impractical in many cases.

In this work, we study the problem of learning the exact user intent from examples. We model user intent as formulas over an arbitrary set of predicates and study several classes of formulas. We start with conjunctive formulas capturing patterns in streams. We then study conjunctive and disjunctive formulas over arbitrary predicates. We finally study the class of disjunctive normal form (DNF) formulas, which implies that any formula can be learned. These algorithms are inspired by exact learning algorithms that were shown to be successful in other domains (e.g., learning automata). Our setting is novel in that the types of predicates were limited in previous works, and thus too the expressibility of user intent.

In the last part of this work, we define the notion of abstract examples and show that it can help to drastically reduce the number of examples posed in the learning process. Abstract examples provide a middle ground between concrete examples and formulas that describe program behavior on multiple examples. We show an algorithm that describes a program through abstract examples. This algorithm can extend previous PBE synthesizers with the ability to communicate to the user a candidate program in an intuitive language. User acceptance of a set of abstract examples covering the input domain implies that the candidate program is guaranteed to capture his intent. We exemplify this approach on the string and bit vector domains.

CopyrightThe above paper is copyright by the Technion, Author(s), or others. Please contact the author(s) for more information

Remark: Any link to this technical report should be to this page (, rather than to the URL of the PDF or PS files directly. The latter URLs may change without notice.

To the list of the PHD technical reports of 2017
To the main CS technical reports page

Computer science department, Technion