Programming-by-example has become an increasingly popular component in software development
tools, human-robot interaction, and end-user programming.
The user gives the system one or more examples of an input and an output for a program they
have in mind, and the system returns one or more candidate programs that would return
the same outputs for those inputs. The user can select one of the candidates,
or think of more examples to add that hopefully help the computer guess the program or a sufficiently
equivalent program that was in the user’s head.
It’s not an easy task for the human to pick examples that help their non-human collaborator
in this exercise, the computer, guess the right program.
There are a lot of reasons for this. The computer is not another human whose thought
process we can imagine, with a shared context we can assume.
It’s also cognitively effortful for the human to analyze the input space and how that
maps to the outputs they want and which small set of examples most fully specifies what
they want. A handful of examples, which is all the human
ever really wants to come up with, can be generalized into a program in many different
ways. Finally, regardless of whether the user is
an experienced programmer or an inexperienced end-user, programs can be difficult to read
and are definitely effortful to mentally apply to current and hypothetical future inputs.
In this work, we demonstrate how a new interface between the human and the computer can address
the latter three challenges. Our key insight is that it is more natural
for users to clarify their intent on top of the original examples they give, rather than
inspecting and annotating the programs synthesized by a foreign PBE system. We call this new
interaction model as "interacting with augmented examples."
Our model provides two types of augmentations on user-provided examples.
Semantic augmentation allows users to specify how their examples should be generalized by
the synthesizer. They can mark some characters as literal so the synthesizer will treat these
characters verbatim. They can also mark some characters to a character family, like digits,
so the synthesizer will generalize those characters to the specified character family.
Data augmentation allows users to ask for additional input-output examples from the
synthesizer to help them understand and validate the behavior of a synthesized program. They
can also compare and contrast the behavior of two similar programs by soliciting some
distinguishing examples. We implement and demonstrate this interaction
model in the domain of regular expressions. Because one, regular expression is a popular
mechanism for text processing and data wrangling. And two, it is often considered hard to master
even for experienced programmers. The basic synthesis algorithm performs a top-down
enumerate search. It starts from an empty program and keeps expanding it following the
DSL grammar to compose different kinds of programs.
If a user marks a letter A as literal, the synthesizer will prioritize A when composing
programs instead of generalizing A to any letters.
To automatically generate additional inputs, we first convert a regex to a deterministic
finite automaton or a DFA. By traversing this DFA, we can generate all kinds of strings
accepted by the regex. We also convert the regex to the complement
of its DFA and use the same algorithm to systematically generate negative examples that are rejected
by the regex. A user study with 12 students show that, when
interacting with augmented examples, all participants finished tasks with an average of 3.3 synthesis
iterations. In contrast, when participants can only manually add counterexamples and
regex annotations, only 4 participants finished the tasks with significantly more synthesis
iterations. Participants felt twice more confident in
the synthesis result, as well as less mental demand and frustration, when interacting with
augmented examples. We also did a case study with 20 regex tasks
asked in Stack Overflow and demonstrated that our interaction model can be used to solve
various realistic tasks effectively. In summary, we proposed this new idea of interacting
with augmented examples and demonstrated its feasibility and usefulness in the regular
expression domain. Through a user study, we show that participants found it much easier
and felt more confident to guide a synthesizer with augmented examples.