Track papers across labs, topics, and trends.
Search papers, labs, and topics across Lattice.
This paper introduces NSynC, a synthesis-by-semantics approach that directly enumerates the semantics of a programming language to eliminate semantic duplication in inductive program synthesis. By focusing on the normal forms of the simply-typed lambda calculus with sums, the method ensures that each candidate program is semantically unique, leading to more meaningful evaluations. The results demonstrate a geometric mean speedup of 8.93x on a synthetic benchmark suite compared to traditional unrestricted algorithms, significantly enhancing synthesis efficiency.
Eliminating semantic duplication in program synthesis can accelerate evaluations by nearly 9 times, transforming the efficiency of algorithm development.
Inductive program synthesis algorithms search a space of programs to find one that meets some specification. Enumerating according to the syntax of a programming language leads to a large search space, and hence slow synthesis, due in large part to semantic duplication. A synthesiser may have to evaluate -- and reject -- multiple semantically identical but syntactically different programs, wasting resources. To avoid this duplication, we present NSynC, a synthesis-by-semantics approach. By enumerating the semantics of the target language directly, we guarantee that each candidate program is semantically unique and that each evaluation of a candidate is meaningful. Specifically, we search the space of normal forms for the simply-typed lambda calculus with sums using a top-down, type-directed synthesis algorithm. Our preliminary results show a geomean speedup of 8.93x on a synthetic benchmark suite over the unrestricted algorithm.