Title: Reconciling Enumerative and Symbolic Search in Syntax-Guided Synthesis,
Abstract: Syntax-guided synthesis aims to find a program satisfying semantic
specification as well as user-provided structural hypothesis. For syntax-guided
synthesis there are two main search strategies: concrete search, which
systematically or stochastically enumerates all possible solutions, and
symbolic search, which interacts with a constraint solver to solve the
synthesis problem. In this paper, we propose a concolic synthesis framework
which combines the best of the two worlds. Based on a decision tree
representation, our framework works by enumerating tree heights from the
smallest possible one to larger ones. For each fixed height, the framework
symbolically searches a solution through the counterexample-guided inductive
synthesis approach. To compensate the exponential blow-up problem with the
concolic synthesis framework, we identify two fragments of synthesis problems
and develop purely symbolic and more efficient procedures. The two fragments
are decidable as these procedures are terminating and complete. We implemented
our synthesis procedures and compared with state-of-the-art synthesizers on a
range of benchmarks. Experiments show that our algorithms are promising.