Enhanced Enumeration Techniques for Syntax-Guided Synthesis of Bit-Vector Manipulations
Syntax-guided synthesis has been a prevalent theme in various computer-aided programming systems. However, the domain of bit-vector synthesis poses several unique challenges that have not yet been sufficiently addressed and resolved. In this paper, we propose a novel synthesis approach that incorporates a distinct enumeration strategy based on various factors. Technically, this approach weighs in subexpression recurrence by term-graph-based enumeration, avoids useless candidates by example-guided filtration, prioritizes valuable components identified by large language models. This approach also incorporates a bottom-up deduction step to enhance the enumeration algorithm by considering subproblems that contribute to the deductive resolution. The implementation of the enhanced enumeration techniques, named Biten, outperforms state-of-the-art solvers in terms of the number of solved problems, execution time, and solution size. Notably, Biten successfully solved 32 synthesis problems for the first time, including 6 renowned Hacker’s Delight problems.
Wed 17 JanDisplayed time zone: London change
10:30 - 11:50 | |||
10:30 20mTalk | Implementation and Synthesis of Math Library FunctionsDistinguished Paper POPL | ||
10:50 20mTalk | Enhanced Enumeration Techniques for Syntax-Guided Synthesis of Bit-Vector Manipulations POPL | ||
11:10 20mTalk | Efficient Bottom-Up Synthesis for Programs with Local Variables POPL Xiang Li University of Michigan, Ann Arbor, Xiangyu Zhou University of Michigan, Rui Dong University of Michigan, Yihong Zhang University of Washington, Xinyu Wang University of Michigan Pre-print | ||
11:30 20mTalk | Optimal Program Synthesis via Abstract Interpretation POPL Stephen Mell University of Pennsylvania, Steve Zdancewic University of Pennsylvania, Osbert Bastani University of Pennsylvania |