Question Selection for Multimodal Code Search Synthesis Using Probabilistic Version Spaces
- 29 April 2025
- journal article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Software Engineering
- Vol. 51 (6) , 1724-1744
Abstract
Searching the occurrences of specific code patterns (code search) is a common task in software engineering, and programming by example (PBE) techniques have been applied to ease customizing code patterns. However, previous PBE tools only synthesize programs meeting the input-output examples, which may not always align with the user intent. To bridge this gap, this paper proposes Excalibur, a multi-modal (example and natural language description) and interactive synthesizer for code search. Excalibur ensures that the generated programs are correct for the provided examples (soundness) and include the user-intended program (bounded completeness). Furthermore, Excalibur helps the user identify the user-intended program through question-answer interaction. To minimize the required interaction efforts, question selection is crucial. To improve question selection for code search, we propose probabilistic version spaces (ProbVS), in which the user-intended program’s probability is high and others are low. ProbVS combines traditional version spaces for compactly representing extensive programs and large language models (on the user-provided natural language description) for adjusting programs’ probabilities to align with users’ intents. Extensive experiments on a benchmark of 44 tasks demonstrated the effectiveness of Excalibur and ProbVS and demystified how ProbVS affects probability distributions and how the configurable parameters affect ProbVS.Keywords
Funding Information
- Hong Kong Research Grant Council/General Research Fund (16205821)
- National Natural Science Foundation of China (62272218)
- Natural Sciences and Engineering Research Council of Canada Discovery Grant (RGPIN-2022-03744, DGECR-2022-00378)
- FRQNT/NSERC NOVA program (2024-NOVA-346499)
- Leading-edge Technology Program of the Jiangsu Natural Science Foundation (BK20202001)
This publication has 36 references indexed in Scilit:
- Solving olympiad geometry without human demonstrationsNature, 2024
- Overfitting in Synthesis: Theory and Practice2019
- Encyclopedia of Social Network Analysis and Mining2018
- Learning a Static Analyzer from Data2017
- Soufflé: On Synthesis of Program Analyzers2016
- SPOON: A library for implementing analyses and transformations of Java source codeSoftware: Practice and Experience, 2015
- Predicting a Correct Program in Programming by Example2015
- Z3: An Efficient SMT Solver2008
- Basic Methods of Probabilistic Context Free Grammars1992
- Learning regular sets from queries and counterexamplesInformation and Computation, 1987