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.
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)