Program Synthesis Through Learning the Input-Output Behavior of Commands

Program synthesis writes programs on behalf of humans, increasing software development productivity. Existing systems select a proper sequence of commands by assembling them in various ways and analyzing their meanings, which is accurate and fast when a detailed specification is given for each available command, including the syntax and semantics. However, preparing this specification is burdensome and must be repeated to add or modify available commands. We propose a synthesis system that requires moderate groundwork to achieve sufficient accuracy and speed. The proposed system receives the syntax of the available commands and learns their meanings independently by writing programs and observing their input-output behavior. Using the learned knowledge, the system selects a likely sequence of commands and gradually revises them to converge to a target program. We validated the system by synthesizing 1,000 integer-manipulation programs out of 245,410 possible programs. The system synthesized most of the programs within 1,000 revisions, which is 80% faster than the state-of-the-art system based on machine-learned input-output patterns. In addition, greater than 10% of the programs were synthesized within several revisions. We believe that the proposed system provides a basis for synthesis systems based on learning input-output behavior.