Distance Guided Programming by Examples

Program synthesis has the potential to save user's efforts and reduce bugs. The status quo is that it is still very challenging to synthesize programs for solving complicated problems. Examples are provided to help understand problem itself. Motivated by early works on artificial intelligence, modeling human solving problem as a process of searching a path from an initial state to the target state, we propose a synthesis method for programming by example, which is named as DistGuided (Distance Guided) by using a metric to measure the distance between the current state to the target state of a program. This metric is usually provided by domain experts and is often commonly available.  

DistGuided is instantiated by combining a bottom-up enumeration algorithm. It is evaluated with typical benchmarks on domain STRING and domain BITVEC , where multiple distance metrics naturally exist. Compared with baseline approaches, the experimental results show that our approach demonstrates improved efficiency in most of the cases. Furthermore, domain knowledge, captured in the distance metric, is proven to be helpful.