  This paper introduces a local search method for improving an existing program
with respect to a measurable objective. Program Optimization with Locally
Improving Search (POLIS) exploits the structure of a program, defined by its
lines. POLIS improves a single line of the program while keeping the remaining
lines fixed, using existing brute-force synthesis algorithms, and continues
iterating until it is unable to improve the program's performance. POLIS was
evaluated with a 27-person user study, where participants wrote programs
attempting to maximize the score of two single-agent games: Lunar Lander and
Highway. POLIS was able to substantially improve the participants' programs
with respect to the game scores. A proof-of-concept demonstration on existing
Stack Overflow code measures applicability in real-world problems. These
results suggest that POLIS could be used as a helpful programming assistant for
programming problems with measurable objectives.
