Program Optimization with Local Search

• Author / Creator

  Abdollahi, Fatemeh

• Recent advancements in large language models and program synthesis have enabled the development of powerful programming assistance tools. These tools are designed to help the programmer while writing a program in an online setting. In this thesis we introduce a programming assistant that can optimize a compilable version of a program with respect to a comparable objective.

  We propose a local search approach for improving programs written by humans using bottom-up search algorithms. We present Program Optimization with Locally Improving Search (POLIS), which exploits the structure of a program, defined by its lines, in order to split the optimization into small program synthesis tasks that can be solved by the existing synthesis algorithms. POLIS iterates over lines of the program, trying to improve a single line at a time, while keeping the other lines fixed. It continues to iterate until it is unable to improve the objective value of the program or runs out of time.

  Our hypothesis is that humans are capable of thinking abstractly and at a high level but they sometimes miss some details of their program. Computer agents, on the other hand, can figure out the details of a program efficiently, whether it is to optimize numerical values in a program or synthesize programs for programming tasks that can be solved with short programs. We leverage this ability of program synthesis algorithms and use them to optimize each line of a program iteratively. Thus, we optimize the human-written program by optimizing each line of it.

  We evaluated POLIS in a 27-person user study where the participants wrote programs for playing two single-agent games: Lunar Lander and Highway. In this study, participants were rewarded based on their programs’ score. Results demonstrate that while human programmers may be capable of writing effective high-level program structures, they often fail to optimize important details of the programs. POLIS substantially improved the quality of all programs evaluated while preserving the high- level structure the programmers designed. These results show that this approach could be used as a helpful programming assistant for problems with measurable and comparable objectives.

• Subjects / Keywords

  • AI Programming Assistance
  • Program Synthesis
  • Local Search
  • Program Optimization

• Graduation date

  Spring 2023

• Type of Item

  Thesis

• Degree

  Master of Science

• DOI

  https://doi.org/10.7939/r3-cyyx-q940

• License

  This thesis is made available by the University of Alberta Libraries with permission of the copyright owner solely for non-commercial purposes. This thesis, or any portion thereof, may not otherwise be copied or reproduced without the written consent of the copyright owner, except to the extent permitted by Canadian copyright law.