Glass-Box Program Synthesis: A Machine Learning Approach

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 scoring 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)
running our framework iteratively can considerably increase
the number of problems solved, (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.