  Though LLMs are capable of generating plausible programs, it's challenging to
interact with the LLMs further to revise the program, especially if the user's
specific requirements are different from the initial proposal. In this paper,
we introduce ANPL, an interactive programming system that ensures users can
always refine the generated code towards their specific programmatic intents
via structured decompositions. Borrowing the paradigm of sketching from program
synthesis, an ANPL program consists of a set of input-outputs that it must
satisfy, a ``sketch'' -- control/data flow expressed in precise code (e.g.
Python), and ``holes'' -- sub-modules to be implemented by the LLM specified
with natural language. The user revises an ANPL program by either modifying the
sketch, changing the language used to describe the holes, or providing
additional input-outputs to a particular hole, turning it into a sub-ANPL
program that can be solved recursively. This workflow allows the users to
offload programming burdens to the LLM as much as possible while retaining the
ability to pinpoint and resolve bugs locally, without exposing the rest of the
program to the LLM. We deploy ANPL on the Abstraction and Reasoning Corpus
(ARC), a set of unique tasks that are challenging for state-of-the-art AI
systems, showing it outperforms baseline programming systems that (a) without
the ability to decompose tasks interactively and (b) without the guarantee that
the modules can be correctly composed together. Additional evaluations on APPS,
HumanEval, and real-world programming tasks have validated that the ANPL
framework is applicable to multiple programming domains. We release the ANPL
solutions to the ARC tasks as a dataset, providing insights into how humans
decompose novel tasks programmatically. See our code at
https://iprc-dip.github.io/ANPL/.
