분할 정복 및 요약해석 기반 JavaScript 프로그램 합성

Abstract

프로그램 합성이란 사용자의 의도와 요구에 맞는 프로그램을 자동 생성하는 기술로서, 개발 생산성을 향상시키는데 사용될 수 있다. 본 논문에서는 사용자로부터 입력 받은 입출력 예제를 만족시키는 자바스크립트 프로그램을 자동으로 합성하는 방법을 제시한다. 제시하는 프로그램 합성 알고리즘은 분할 정복에 기반하여 프로그램 탐색을 효율적으로 하는 Version Space Algebra 기반 합성기법에 기반하며, 요약해석(Abstract Interpretation)을 활용하여 무한한 탐색공간을 유한하게 만들어 바람직한 프로그램을 빠르게 찾아낸다. 본 논문에서 제시한 방법을 총 140개의 문자열과 정수 프로그램 합성 문제에 대해 적용해 본 결과, 평균 9초 이내에 원하는 프로그램이 생성되는 것을 확인하였다.

Program synthesis aims to automatically generate a program that satisfies the user intent expressed in the form of a high-level specification. Recent years have witnessed a surge in interest in applying this technology to a wide range of problems. Program synthesis can help improve software development productivity. In this paper, we present an algorithm for synthesizing Javascript programs from input-output examples. Our approach was based on a synergistic combination of the version space algebra-based approach, which can efficiently solve synthesis problems through divide-and-conquer, and abstract interpretation, which can be used to finitize infinite search spaces. We have implemented our approach and evaluated it in 140 problems of synthesizing string- and integer-manipulating programs. On average, the desirable programs were generated within nine seconds.