Dimensions in program synthesis

The probabilistic inference based program synthesis technique described in [36] can take advantage of the existence of initial buggy piece of code. The core idea of this technique is to model the program as a graph consisting of instructions and states as potentially unknown variables, connected by constraint nodes, and then use belief propagation to infer both the intermediate program states and the instructions that satisfy all the constraints.

The space of programs can be qualified by at least two attributes:

  1. The operators used in this program
  2. The control structure of the program

Machine-learning based techniques:

  • Probabilistic inference
    • A graph of instructions and states, connected by constraint nodes
    • Belief propagation

Constraint generation (why? What for?)

Farkas Lemma

  • Unified Programming Interface
  • A Modular that allows reuse of various synthesis components
  • Combine the power of various search techniques and machine learning techniques?