Title: Glass-Box Program Synthesis: A Machine Learning Approach,
Abstract: Recently proposed models which learn to write computer programs from data use
either input/output examples or rich execution traces. Instead, we argue that a
novel alternative is to use a glass-box loss function, given as a program
itself that can be directly inspected. Glass-box optimization covers a wide
range of problems, from computing the greatest common divisor of two integers,
to learning-to-learn problems.
In this paper, we present an intelligent search system which learns, given
the partial program and the glass-box problem, the probabilities over the space
of programs. We empirically demonstrate that our informed search procedure
leads to significant improvements compared to brute-force program search, both
in terms of accuracy and time. For our experiments we use rich context free
grammars inspired by number theory, text processing, and algebra. Our results
show that (i) performing 4 rounds of our framework typically solves about 70%
of the target problems, (ii) our framework can improve itself even in domain
agnostic scenarios, and (iii) it can solve problems that would be otherwise too
slow to solve with brute-force search.