Semantics-aware Program Sampling

We present an algorithm for specifying and sampling from distributions over programs via a perturb-max approximation. Prior work is generally limited to sampling from priors over program syntax (for example, assigning lower probability to longer programs). We demonstrate a simple modification to our sampling algorithm that allows interpolation between such syntactic priors and priors over semantics (that is, the behavior of the program on its inputs, or the set of class labels when the program is viewed as a statistical model).