{"ID":5439231,"CreatedAt":"2026-07-01T01:17:58.482524686Z","UpdatedAt":"2026-07-02T12:53:03.444329135Z","DeletedAt":null,"paper_url":"https://arxiv.org/abs/2606.30703","arxiv_id":"2606.30703","title":"NSynC: Normalised Synthesis of Computation","abstract":"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.","short_abstract":"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...","url_abs":"https://arxiv.org/abs/2606.30703","url_pdf":"https://arxiv.org/pdf/2606.30703v1","authors":"[\"Zoey Shepherd\",\"Ohad Kammar\",\"Elizabeth Polgreen\"]","published":"2026-06-29T13:15:35Z","proceeding":"cs.PL","tasks":"[\"cs.PL\"]","methods":"[]","has_code":false}