ANPL: Towards Natural Programming with Interactive Decomposition
Authors: Di Huang
Ziyuan Nan
Xing Hu
Pengwei Jin
Shaohui Peng
Yuanbo Wen
Rui Zhang
Zidong Du
Qi Guo
Yewen Pu
Yunji Chen
Venue: NeurIPS 2023 poster (2023)
Keywords: programming language
large language models
program synthesis
code generation
human-ai interaction

Abstract: 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.

ANPL: Towards Natural Programming with Interactive Decomposition
Di Huangh Ziyuan Nan 1.3.f Xing Hu', Pengwei Jin 13, Shaohui Peng", Yuanbo Wen Rui Zhang's Zidong Du', Qi Guo', Yewen Pu" & Yunji Chen 1.30
SKIL of Processors, Institute of Computing Technology, CAS
intelligeett Software Research Center, Institute of Software, CAS
3 UUniversity of Chinese Academy of Sciences 4 "Autodesk Research
wwt.ddip.pgitttie github.io http:://ppproopgghhbb...///A
Abstract
Though LLMs are capable of generating plausible programs, it's challenging to interact with the LLMs further 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, ANPL program consists of a set of input-outputs that it must satisfy, a "sketch" control/data flow expressed in precise code (c.g. Python), and "holes" - sub- modules to be implemented by the L.MM 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 particular hole, turning it into a sub-ANPL program that can be solved recursively. This workflow allows the users offload programming burdens to the LLM much as possible while retaining the ability to pinpoint and resolve bugs locally, without exposing the of the program to the LLM. We deploy ANPL on the Abstraction and Reasoning Corpus (ARC), set of unique tasks that are challenging for state-of- the-art AI systems, showing outperforms baseline programming systems that (a) without the ability to decompose tasks interactively and (b) without the guarantee that the modules can correctly composed together. Additional evaluations on APPS, HumanEyal, 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 dataset, providing insights into how humans decompose novel tasks programmatically.
Introduction
The rapid development Large Language Models (LLMs) has made significant progress in the realm of code generation tasks [7-10, 20, 23, 31, 33, 34, 42, 44, 47, 71]. Compared to traditional approaches program synthesis [21, 22] that were constrained specific, narrow domains (e.g., text manipulations), LLM-driven code generation can generate programs in a domain- (e.g., Python), making it broadly applicable. While LLM-driven code generators can save much of programmers' time in compiling typical programs programs that are similar to those present in their
language
Equual contributions.
*Corespponingg author. Contact: (huangdi, nanziyuan2 cyj) @ict.ac.cn.
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

Programming
Program
Python Program
Hole
Input
Cutput
ANPL Compiler ler
Decompose
langet
Task:
Holo mal
lonol gray
Data flow
odorel.gnd
catu pod
Hole
Debugging
ANPL Program
Python Program
Hole Traces
Expected
Hole
Redecompose
ANPL Compiler
Hole_
then
Hole
Explain Modify
Hole
Hole
Provide
Hole
wdeered
plock
euppurt grid
Figure 1: ANPL overview. Given programming task (e-g., input-output), the user decomposes it into an ANPL program, consisting of programmatically defined sketch (control/data flows, solid lines, programmed by the user and preserved by LLMs), and natural language holes (function modules, dashed lines, generated by LLMs). The ANPL compiler compiles it to Python program and checks the Python code against the task's input-output. If incorrect, the compiler generates debugging trace showing input-outputs for all the holes. The user can focus on debugging each hole independently. by either (1) decomposing further, (2) explaining and modifying its natural language description, or (3) providing correct I/O by adjusting its traces.
training data, it is unlikely that an LLM can compile user-specific program in 1-shot, without any additional user interventions [35, 62]. In software development, most code is not written perfectly on the first attempt, and users need to spend much effort on testing and debugging[46, 63]. Therefore, although using LLM for code generation can significantly reduce the cost of code writing in 1-shot, subsequent interactions editing and debugging an LLM--enerated program - remain an open challenge. This challenge is severe in two aspects: (1) The LLMM-genrrated program can be long and contain complex dataflows, making it difficult to make localized changes while ensuring the dataflows stay intact; (2) Language descriptions are inherently ambiguous to describe specific code edits.
We hypothesize that decomposition - breaking down a complex problem into simpler problems, common practice in program synthesis [2, 48], interactive dialogue systems [30, 72], and cognitive science [16, 27] to name few during the programming and debugging interaction between user and an LLM code generator can tackle these aforementioned difficulties. We propose the ANPL (Abstracted Natural Programming Language) system (Figure 1), which enables stable yet effective interactive editing/debugging to solve complex programming tasks that an LLM cannot correctly solve in 1-shot. The key design insight of ANPL. is decoupling the dataflow "sketch" (something that requires little user effort) and the tedious module implementation "holes" (automated with LLM). With ANPL, users have explicit control over the high-level task decomposition using the sketch, leaving the tedious work of function-leved holes implementation for LLMs. Each hole is stand-alone ANPL program, allowing the user to recursively decompose further.
We evaluated ANPL by conducting large-scale user study using the Abstraction and Reasoning Corpus (ARC) [14], a well-known corpus that consists of 400 unique tasks (in the training set). without predefined programmatic solutions. We recruited 19 Python programmers who interacted with our system for total of 440 man-hours. Compared to prior works evaluating L.LMs' code generation capabilities interaction with real users Xu et [69](166 man-hours), Vaithilingam et al. [61](7.87 man-hours), ours is the most comprehensive evaluation up-to-date to the best of

---

our knowledge. We find that programmers interacting with ANPL perform significantly better than interaction with the vanilla LLM (75.0% tasks solved vs. 58.4%). The interaction between users and ANPL resulted in DARC, dataset of programmatic Decomposition of ARC tasks, consisting of 300 instances of humans successfully decomposing ARC tasks to simpler tasks grounded in Python.
Specifically, this paper makes the following contributions:
We present ANPL, programming system that allows the user to explicitly manipulate dataflows while offloading the implementation of modules to an LLM, to decompose and ground programming tasks.
We evaluate ANPI. on a large-scale human study (440 man-hours) on a set of 400 ARC tasks, showing that programmers interacting with ANPL significaly outperform interaction with the vanilla LLM
We will release the collected programmatic decomposition dataset, DARC, to promote the development of research communities including LLMs, programming languages, human- computer interaction, and cognitive science.
Related Work
2.1 Code Generation with LLMs
LLMs have been applied to tackle the code generation problem, which is the task of automatically finding program satisfying user intent expressed in natural language or other specifications [7.
20, 23]. For example, Codex [9], GPT model finetuned on public code repositories from GitHub, demonstrates the potential of code generation with LLMs. With the idea of generating candidate programs and filtering, AlphaCode [34] samples large number of candidate programs and filters using input-output examples. Chen et al. [8] and Key al. [31] utilize formal specifications (e.g., test cases and assertions) generated by LLMs to verify the generated programs. Synchromesh [47] retrieves few-shot examples from training sets and then checks syntax, scope, typing rules, and contextual logic when synthesizing programs. Some work focuses on generating code based on feedback. CodeGen [44] factorizes a single program description into multiple parts and generates programs in multi-turns. Chen et al. [10]. Le et al. [33] and Madaan et al. [42] provide LLMs with feedback messages generated by exccutor, a critic network, LLMs themselves to improve performance. Although these efforts have achieved a high level of code generation quality, they do not incorporate interaction within the process of code generation. Basically, these methods can be integrated into our compiler to gain better compiling results. Another type of work, like Parsel, also utilizes the concept of decomposition [71]. Different from Parsel, our work an interactive system between users and LLMs, which allows users to debug programs through further clarifying and decomposing each module. Furthermore, conduct large-scale user study evaluate the effectiveness of our system.
2.2 User Interaction with LLMs
Interactions between humans and LLMs are necessary because it is difficult for LLMs to accurately understand user intent and generate correct answers in one shot [36, 52, 67, 70]. Among them, IntemGPT [39] finds it helpful to combine the advantages of non-language instructions (i.e. pointing instructions) and language instructions. Instead of pointing instructions, our system allows humans to specify control/data flow precisely with programmatic language while keeping details in natural language. Furthermore, we have conducted extensive human studies on the ARC benchmark, which sufficiently demonstrate the capabilities of our system.
2.3 Evaluation of LLM Code Generation Ability on Human Studies
Several works conduct human study on code generation tools to survey generation accuracy and user experience [4, 38, 61, 69]. However, these works focus on analyzing existing tools such as Copilot. The purpose of our human study is to verify the effectiveness our proposed interactive system, ANPL. Furthermore, ARC containing abstract problems is a harder benchmark than those in previous studies. Our human study takes 440 man-hours on this hard benchmark, greater than the usual 100 man-hours, producing reliable results.
3

---

Other related areas including programming with natural language and LLMs as an interpreter are discussed in the Appendix
3 ANPL: The Abstracted Natural Programming Language
ANPL is programming system that allows users to program and debug with natural language. It is Python-like and compatible with the original Python language, which provides users with great programming flexibility. In principle, we can apply our system to any programming language and in this paper, we have opted for Python as our base language. In this section, we will introduce ANPL's design principle and how to specify a ANPL program and then debug it.
3.1 Design Principle
The main idea under ANPL is to decouple the description of hole and sketch, which frees users from the tedious coding of function-level holes by allowing them to write the natural language and empowers them with the privilege of precisely setting sketch with few provided programming standards. Specifically, the sketch represents the control/data flow, and the hole represents the function module. This idea has been supported by the relevant experiences of early integrated systems like StreamBit [55] and SKETCH [54], which shows that users often have an idea about the general form of solution (a high-level strategy) but feel it challenging to implement the program details. For programming with the help of LLMs, it offers the following advantages: 1) The user-specified sketch convey user intent aimlessly rewriting the entire natural language program and regenerating it. 3) The relationships between modules are explicitly represented by the sketch, thus making it easier for the compiler to ensure that other correct parts are not affected by debugging actions when users are debugging the erroneous sections of the program, which not an easy task due the unpredictability of LLMs.
precisely. 2) It enables users to trace bugs along the sketch, rather than
3.2 Programming with ANPL
An ANPL program consists of a python-like sketch, and natural language holes.
Hole. A hole implements a function module with a natural language description, which will be fleshed out by LLMs during the compiling process. Each hole specified with a natural language description quoted by quotation marks or "**, When called, holes should be organized by specifying its input-output variables, serving as the interconnections. To define a hole, users can either 1) define a hole as sub-function with the function name, parameters, and descriptions, and then call the function with its function name and input-output variables, or 2) just define and call it with descriptions and ouput- variables inline.
Sketch. A sketch is the control/data flow connecting different holes, specified with a programmatic language. Users constitute the sketch by assigning names to variables and using them as hole parameters in data flow graph. Besides, users can write complex control flows with programmatic keywords (e.g., for, while, if) similar to that in Python to get more intricate ANPL programs.
An ANPL code example can be found in Figure 2, Figure 3, and Appendix D.I.
3.3 Debugging with ANPL
As an ANPL program is already decomposed into holes connected by the sketch, debugging over ANPL is targetted, where users can accurately locate bugs and make modifications to the relevant ANPL program.
Tracing. Tracing helps users to locate bugs. With the clear and explicit definition of sketch in ANPL, users allowed to detect bugs by checking the execution trace between high-level hole, which is not easy in previous work [71]. Users can either use the preset "Trace" option in ANPL or just directly insert breakpoints in the code with print.
Providing onput-output constraints. Users can provide input-output constraints, a typical gold standard for correctness, and ask the ANPL compiler to resynthesize the program to ensure the

---

def compLling(AMP)::
while "AMPL progran has bole" (AMPL):
hole "return the first hole AMPL program" (AMPL):
generated LINCANPL, descrdescripione, hole.I0s)
hapendency.graph "analyze generated sort" sort" (genarated_coda)
dependency graph with topology
entry_ "return antry
the dapendancy graph with topalogy (depandency-grapp) "the hole has been naned by the user" (hole):
uev_Gepandency-gge -graph "renove unrelated nodea in the dependency graph" (dappeddddee hole)
AMPL "fill the hole with generated code according to the dependency (AMP,, (ANPL, generated_code,
new www_dependeney-graae
alif len (antryynodeas) == 1:
ANPL "fill the hole vith generated code according to the dependency graph" (ANPL, goderated_code,
dependency_grapt)
dependency graph has multiple entry nodes, re-generate
return ANPL
def SamplingossfAAPPI...ol ANPL_new):
it 'APPL progran baa hole" (ANPL_.ne)):
AMPL_pew compilligg(NPLL_e/
ANPL "mergo two depondency graphs according to the norging principle of intention: user_nev user_old > LIM_old > LLM_nev"
(AMPL_old, 1AM,nee(AMPPL,11,, AMPL_new)
AMPL
Figure 2: The pseudo-code of ANPL compiler, consisting of the direct compiling process and the differential compiling process.
correctness of the compiled program. Each resynthesis will arise API call with batch size of 10 of the LLM.
Editing. ANPL allows users to debug they would in traditional programming languages. Specifi- cally, users can edit their code in four ways: 1) They can recursively decompose the original hole into lower-level holes connected by the sketch. 2) Reversely, they abstract low-level holes and the corresponding sketch to a higher-level hole. 3) They can explain and modify the natural language descriptions of holes. 4) They can change the sketch by coding (e.g., changing the input-output variables of holes).
In addition, ANPL has various syntactic sugars, for instance, implementing recursion with natural language by using the combinator, see Appendix for details.
4 The ANPL Compiler
One of the crucial tasks that compiler must undertake is to gain the trust of its users it should accurately reflect the underlying code and provide users with the possibility of debugging. To achieve this task, the ANPL compiler mainly focuses how to generate reliable executable program while still preserving the control/data flows specified by users, and 2) in the debugging process, how to allow users to modify and regenerate the erroneous parts of the program while preserving functionalities in the rest of the programs.
problems: 1) in the program generation process,
4.1 Compiling ANPL
Preserving the sketch. To ensure the consistency of control/data flows before and after compila- tion, we first extract control/data flow information from the sketch and individual natural language descriptions from the holes separately. Then, we traverse and implement these holes while ensuring the integrity of the sketch. Note that while LLMs take the entire ANPL. program as context to implement the program of its holes, the sketch is fixed during program generation.
5

---

Generating the holes. LLMs iterate over and fill the holes one by one in their appearing order. When filling, LLMs can automatically create name for the hole and decompose into sub-functions. The main problem is that L.MSs cannot implement holes reliably and may generate useless func- tions due their unpredietability. The proposed solution begins with analyzing and clarifying the dependency relationships among the generated functions, and then identifying which function serves as the implementation of the target hole. The fundamental principle that if the user explicitly names the hole, then any generated function with the same name as the user-specified one should be considered as the implementation of the hole, while other functions that it depends on are regarded as fub-functions of the hole; And otherwise, the function that does not depend on any other functions should be considered as the implementation of the hole. In the implementation. we first construct a dependency graph from the generated functions and find its entry nodes (nodes without any depen- dency on it) of the graph with topology sort. Then, we identify the target function based on three situations: 1) The user has named the hole and we just match it with the entry node's 's name and remove unrelated nodes. 2) There is only one entry node named by LLMS and we fill the target hole with it. 3) There are multiple entry nodes which means that there are multiple independent groups of functions and we cannot judge which one should be filled into the target hole, and thus we instruct LLMs re-generate the implementation.
Finally, we get a compiled Python program that preserves user-specified sketch and has a well- organized implementation of holes.
4.2 Compiling Differences
During the debugging process, users generate an updated ANPL program. The problem is how to modify the erroneous parts while preserving the rest of the compiled Python program.
We observe that this process can be modeled as the merging of dependency graphs. Specifically, the old ANPL program corresponds one dependency graph, and the new program debugged by users serves as another new dependency graph, and the merging process. For merging, we propose three assumptions:
the user's current intention takes priority over previous intentions, 2) the LLM's previous intentions take priority over the current intention, and 3) the user's 's intentions take priority over the LLM's intentions. Assumption 1) and Assumption 3) are obviously valid: It is precisely because the user wants to modify their previous intention or correct the compiled result with LLM errors that they will perform debugging operations. Assumption 2) holds because we want to minimize the impact of debugging the generated program: When the user's 's intention does not involve the code, the code should not undergo any changes due to LLM's s compilation.
Based on these assumptions, we can derive a fundamental principle for the priority of dependency graph merging: the user's current intention > the user's previous intention the LLM's previous intention > the LLM's current intention.
5 Human Studies
We conducted user study on 400 ARC training tasks to evaluate the effectiveness of ANPL compared to the original ChatGPT (GPT-3.5-turbo)) We hypothesized that if ANPL can help people to program with LLMs people should be able to solve more tasks and get the right program with less effort (i.e. time consumption) on solving and programming tasks.
5.1 Settings.
Stimuli. We use the ARC as our programming tasks. The ARC benchmark [14] was proposed to provide a standardized set of tasks that can be used to evaluate key aspects of human general intelligence, such as abstraction, generalization, object categorization, and so on [5, 13, 25, 29, 32, 40, 59, 60]. The primary objective of ARC is to require individuals to deduce a consistent procedure based on a limited number of abstract input-output examples, and then apply this procedure to generate a previously unseen output for a new input, as depicted in Figure It found that ARC representative programming dataset because 1) humans tend to solve them by coming up with

---

ANPL Program
SYSTON: Weach praslum do you senc to soloe"s 253
Input arid
Sestow Frece (See) followe by (Ratee) to secepe logut.
Hole
gial "Ford the columro with the wast pinela and the forst piotla (Gnpat, colored catar posel clepue grid, aast aroo
gray piaels
co urtr with the
aad Cooloreo.gree, fountt.gry)
2r pizels
SYSTOM: dMFt waass
Hole 2 Frot grag
you
qui EX/2/RA/12
Fenest gray
Furcecass
color the pixel blue
Panctton
t2x Code has Frange ruaber Comples
Hole
mein
cal colorddorid d
color pixets red
find.co leer Loo, feeeesst.eeetua.... www.feeet..aagg.podddde.oo
Fraegt
color 383) piapllsss.
Frange
output_grrid
sySteM, which Foxction do selecte
(nascyland colams with most, Flvest anyy www.la/calar platl Hwss/sstor ary, pinsla (er):
Figure 3: ANPL user interface. Participants utilize this programming interface to write and debug ANPL programs. The figure shows the ANPL program code entities along with corresponding sketch and holes diagrams. For a more detailed user interface, please refer to the Appendix E.3.
programs [1, 29j', and 2) the solution of ARC cannot be found on the internet, which make its problems unique enough for LLMs (and participants).
Participants. We recruited 19 primary Python programmers from our institution. Due to the difficulty of solving ARC problems by interactive programming, we first recruited more than 19 participants and then filtered out 19 of them by asking each person to complete ~~10 problems, checking if they can correctly operate the system, and asking if they wanted to continue. We paid an average of ~ $8.80 USD per hour a standard programmer's 's wage within our institution.
Design. 1) Each participant is randomly assigned set of non-overlapping ARC problems. The number of problems is different per participant depending on their preferred commitments. 2) There are two systems: System A, the ANPL, and System B, the original ChatGPT (GPT-3.5- turbo). Participants can interact with System B arbitrarily, including inspecting and changing Python programs manually. However, they cannot implement whole Python function from scratch without interacting with System B. 3) As the programming level of participants can have significant impact on their ability to solve ARC tasks, for each task, each participant used both System and System B, presented in random order. 4) The participants were informed that the first interaction is crucial in order to minimize the impact of subsequent interactions. The programming interface of System A is shown in Figure 3 and System B shares similar interface to System A.
Procedure. Given set of tasks, participants can decide on the order in which to complete them, as they may need to start with simpler ones first. Participants are asked to solve the problem by programming (or interacting) with System A (or B) to get Python program to solve the task. A soft time limit is 30 minutes which means that participants are suggested to give up after 30-minute try. The held-out test input-output examples provided in ARC are used to check the correctness of the generated Python program, and participants can use additional input-output examples to debug their program. Participants are shown some prompt templates for using System B, while no prompts are needed System A.
5.2 Results
Participants solve more tasks with ANPL. First, examine the problem-solving rate of ARC tackled by the participant when using different systems, shown in Figure 4. Specifi- cally, we compare System A (ANPL), System B (GPT + interaction, i.e. ChatGPT), System C (ANPL without interaction), and System D (vanilla GPT), where Systems C and D repre- sent the solving rate of one-shot generation without further interaction using Systems A and B. respectively. Results show that System A mean = 75.0%, 95%CI [70.8%, 79.1%). B mean 58.4%. 95%CI = [53.4%, 63.3%), C mean 23.5%, 95%CI = [19.4%, 27.5% and D mean 16.8% 95%CI = [13.2%, 20.6%]. where CI denotes confidence interval. Further- more, we conduct paired t-tests on these systems, all of which are shown significant (df =
the top results Kaggle competition of ARC are all based program synthesis techniques.
7

---

0.
0.-
04-
0.
0.5-
Solving rate
Solving rale
0.4
Solwing
6.4
6.4
02
0.-
Systems A
System A[rC]
2500
System
Number Interactions
Figure 4: Results of problem-solving rates. A: Solving rate of four systems. B: The relationship between solving rate and time consumption. C: The relationship between solving rate and number of interactions. Trace Calculated(TC) means the trace mode is considered into interactions.
System
0.8
Solving rate
0.6
0.4
0.2
0
4
5
6
7
10
11
12
13
14
15
16
17
18
User
Figure 5: User differences. The solving rate of different users using System A and System B.
399, p < 0001): A-B: 1= (12.,,,,,00.00...122222,2,,,,,,, A-C: 202.5883, 95
B-D: 1=3.646, 95%CC=(3300% 95%CI=[36.9% 9%.6%,,));;; C-D: t=3.152, 95%CI=[,.%% 11..2%% 11.0%]. In conclusion: 1) With large con- fidence, ANPL performs the best and allows users to solve more problems, with solving rate achieving 75.0% on average, while B achieves 58.4% (1 28.25%). 2) Programming with interaction (Systems and B) is always better than programming without interaction (Systems C and D). 3) Even for one-shot code generation, ANPL without interaction (System C) performs better than vanilla GPT (System D).
A-D:: -=23.5944444 05%
B-D: 1=16.911,
effort. Next, measure the user effort different systems. Figure illustrates the relationship between solving rate and time consumption, as well as the relationship between solving rate and the number of interactions. We find that compared with GPT, ANPL exhibits a rapid growth curve, implying a significant advantage in terms of efficiency in problem-solving Furthermore, estimate the coding effort, conduct comparative analysis of the average lines of code between ANPL. and the generated Python code. Some ARC task is simple and one of the main reasons for the time cost on simple tasks is that during programming, much time is spent waiting for GPT's response. The average waiting time is 14.6% for System A and 23.5% for System B. Besides, the were instructed solve the tasks as fast as possible and they chose not to program directly when using System A because it would require more effort. Another way to analyze user effort is calculate the lines of code. We find that the [min, max, mean] of lines of ANPL is [2. 76, 10.29] while the one of Python is [4, 113, 26.47], and note that writing natural language is simpler than coding. We also demo the ANPL's application on projects including MAGIC card game and LS-8 CPU with 67% lines of code reduction (See Appendix F.4).
ANPL
User differences. The characteristics of the ARC benchmark lead to significant variations in user performance. In order to measure such differences, we conducted an anonymous statistical analysis of users" solving rates while utilizing Systems A and B. Figure 5 shows that different users achieve variant solving rates. The (mean, max, min) solving rate achieved by users when using System (71.1%, 95.5%, 16.7 6.77% with variance 0.038, while System B is (57.2%. 84.2%, 33.3%) with variance

---

10.
1.00
1.00
0.70
Solving rate
0.0
Salving
Solving
0.2
Syewm
Systems A System A(TO)
500
1000
1600
2000
2000
2000
40
System
Time
Number of Interactions
Figure 6: Results of problem-solving solvvin rates when users can not see generated Python code and only interact with user interfaces and IO feedback. A: Solving rates of four systems. B: The relationship between solving rate and time consumption. C: The relationship between solving rate and number of interactions. Trace Calculated(TC) means the trace mode is considered into interactions.
0.022. This illustrates that although System A surpasses B in most cases and on three metrics, it exhibits greater instability, suggesting the presence of a certain learning cost compared with B.
ANPL performs even better for programming beginners. In order to simulate the situation where users are unable to understand Python code (programming beginners), we designed a new set of experiments with System A and System B. Neither system provides users with specific Python code; instead, users are required to complete tasks only based on user interfaces and IO feedback. We selected four users for the experiment. To mitigate the potential impact caused by varia- tions among users. Each user of 10 problems, which they had previously an- swered correctly using both System and Sys- tem B. In total, there were 40 problems admin- istered. Results (Figure 6) show that System A mean = 89.9%, 95%CI = 77,,4% 97.8%) B mean 37.2%, 95%CI [21.6%, 52.5%), C mean = 40.2%, 95%CI (24.3%, 55.6%). D mean 12.5%. 95%CI [2.9%. 25.0%]. With large confidence, ANPL performs the best and allows users solve more problems, with solv- ing rate achieving 89.9% on average, while B only achieves 37.2% (t 141.67%).
given set
resyn 9%
resyn
6%
edit 46%
trace
edit 46%
48%
(b)
Figure 7: The proportion of three interaction modes. (a) Time. (b) Frequency.
Percentage of different interaction modes.
be observed from Figure 7 that among all the available options, the majority of users prefer the "edit" action, accounting for 46.2% total number of interactions and 46.6% total time cost, followed by the "trace" action, which constitutes 47.5% total number of interactions and 44.6% total time cost. This trend aligns with the typical programming workflow, where smaller portion of time is dedicated to coding, while a significant portion is allocated testing and debugging.
The influence of the system order. We denote the order as "A-B" ("B-A") meaning that the user first use System A (B) and then System B (A). With "A-B". the solving rate System A is 75.5% (151/200) and System B is 62.5% (125/200). With "B-A", the solving rate of System A is 74.5% (149/200) and System B is 54.5% (109/200). We conclude that System B's performance increases 8% under the influence of System A, while System A's performance is more stable. This may be because System A tends to encourage users to approach problem-solving in sketch and hole decomposition manner, and this manner is subconsciously applied to the subsequent System B. Therefore, we believe that "thinking decomposition" " itself can bring about certain improvements, and A leads users to this thinking manner. Additional results shown in Appendix F.2.

---

5.3 DARC: A Recursive Decomposition Dataset of ARC Tasks
DARC contains all recorded interactions between participants and both the ANPL system and GPT- 3. 3.5-turbo all 400 ARC tasks. 300 of the 400 tasks can be successfully decomposed and grounded in Python using ANPL (Figure 8), with an average of 2.7 holes. Due to the characteristics of ARC, the data contained in DARC is not the only solution, and different users have significant impact the dataset. Still, the value of our dataset is tremendous, as it contains: programmatic decompositions of ARC tasks by humans using ANPL, Python code for 300 ARC tasks, and fine-grained interaction histories between users and a code- mode-generating LLM.
6 Conclusion
In this paper, we propose ANPL, a programming sys- tem that enables users to program and debug with natural language with inter- active decomposition. The system was evaluated large-scale user study on the 400 ARC tasks. Experimen- tal results show that with large confidence, program- mers interacting with ANPI. perform significantly better than interaction with the vanilla LLM (75.0% tasks solved vs. 58.4%). Further- more, will release the collected programmatic de- composition DARC dataset, which provides valuable insights into how humans decompose programmatic tasks into simpler ones using natural language and onput-outputs.
input_arid
Find the blue square
blue square
red square
Find the botton red square
overlap the squares
output grid
color black pixels overlap square green
Figure 8: An example in DARC.
7 Limitations
Our limitations and future work mainly focus on two aspects: the naturalization of LLM responses and library learning. Specifically, 1) the ANPL system should return easily understandable natural languages instead of Python code as a response to humans, and 2) how to build a natural language library community through library learning [19, 66] to allow users share and reuse programs made by each other. Please see our detailed limitations and broader impact in the Appendix B & C.
Acknowledgments and Disclosure of Funding
We thank Tianyun Ma and Yutong Wu for their effort in submission and rebuttal. Tianyun helped us analyze data and Yutong conducted the automatic code generation experiment.
This work is partially supported by the NSF of China (under Grants 62002338, 61925208. 62222214, 1,, 62102399, U22A2028, U19B2019), the National Key R&D Program of China (under Grant 2021ZD01 10102). CAS Project for Young Scientists in Basic Research (YSBR-029), Youth In- novation Promotion Association CAS and Xplore Prize.
References
[1] Samuel Acquaviva, Yewen Pu, Marta Kryven, Theodoros Sechopoulos, Catherine Wong, Gabrielle Ecanow, Maxwell I. Nye, Michael Henry Tessler, and Josh Tenenbaum. Communi- cating natural programs to humans and machines. In NeurIPS, 2022.
10

---

[2] Aws Albarghouthi, Sumit Gulwani, and Zachary Kincaid. Recursive program synthesis. In Computer Aided Verification: 25th International Conference, CAV 2013, Saint Petersburg, Russia, July 13-19, 2013. Proceedings 2.5, pages 934-950. Springer, 2013.
[3] Jacob Austin, Augustus Odena, Maxwell Nye, Maarten Bosma, Henryk Michalewski, David Dohan, Ellen Jiang, Carrie J. Cai, Michael Terry, Quoe V. Le, and Charles Sutton. Program synthesis with large language models. CoRR, thss2208.07732. 2021.
[4] Shraddha Barke, Michael B. James, and Nadia Polikarpova. Grounded copilot: How program- mers interact with code-generating models. Proc. ACM Program. Lang., 7(00PSLAT):8--11, 2023.
[5] Frederic Charles Bartlett and Frederic Bartlett. Remembering: A study in experimental and social psychology. Cambridge university press, 1995.
[6] Alan W. Biermann, Bruce W. Ballard, and Anne H. Sigmon. An experimental study of natural language programming. Int. J. Man Mach. Stud., 18(1):71-87, 1983.
[7] Sébastien Bubeck, Varun Chandrasekaran, Ronen Eldan, Johannes Gehrke, Eric Horvitz, Ece Kamar, Peter Lee, Yin Tat Lee, Yuanzhi Li, Scott M. Lundberg, Harsha Nori, Hamid Palangi, Marco Túlio Ribeiro, and Yi Zhang. Sparks of artificial general intelligence: Early experiments with GPT-4. CoRR, abs/2303. 12000..2212,.. 2023.
[8] Bei Chen, Fengji Zhang, Anh Nguyen, Daoguang Zan, Zeqi Lin, Jian-Guang Lou, and Weizhu Chen. Codet: Code generation with generated tests. CoRR, abs/2207. 10397, 2022.
[9] Mark Chen, Jerry Tworek, Heewoo Jun, Qiming Yuan, Henrique Pondé de Oliveira Pinto, Jared Kaplan, Harrison Edwards, Yuri Burda, Nicholas Joseph, Greg Brockman, Alex Ray, Raul Puri, Gretchen Krueger, Michael Petrov, Heidy Khlaaf, Girish Sastry, Pamela Mishkin, Brooke Chan, Scott Gray, Nick Ryder, Mikhail Pavlov, Alethea Power, Lukasz Kaiser, Mohammad Bavarian, Clemens Winter, Philippe Tillet, Felipe Petroski Such, Dave Cummings, Matthias Plappert, Fotios Chantzis, Elizabeth Barnes, Ariel fierbertVVoss, William Hebgen Guss, Alex Nichol, Alex Paino, Nikolas Tezak, Tang, Igor Babuschkin, Suchir Balaji, Shantanu Jain, William Saunders, Christopher Hesse, Andrew N. Carr. Jan Leike, Joshua Achiam, Vedant Misra, Evan Morikawa, Alee Radford, Matthew Knight, Miles Brundage, Mira Murati, Katic Mayer, Peter Welinder, Bob McGrew, Dario Amodei, Sam McCandlish, Ilya Sutskever, and Wojciech Zaremba. Evaluating large language models trained on code. CoRR, 0is/21077033744 2021.
[10] Xinyun Chen, Maxwell Lin, Nathanacl Schärli, and Denny Zhou. Teaching large language models to self-debug. CoRR, htss2304405128. 2023.
[11] Shuyao Cheng, Pengwei Jin, Qi Guo, Zidong Du, Rui Zhang, Yunhao Tian, Xing Hu, Yongwei Zhao, Yifan Hao, Xiangtao Guan, et al. Pushing the limits of machine design: Automated epu design with ai. arXiv preprint 2336v 2.006.244. /2456, 2023.
[12] Zhoujun Cheng, Tianbao Xie, Peng Shi, Chengzu Li, Rahul Nadkarni, Yushi Hu, Caiming Xiong, Dragomir Radev, Mari Ostendorf, Luke Zettlemoyer, Noah A. Smith, and Tao Yu. Binding language models in symbolie languages. CORR, abs/2210.02875,, 2022.
[13] Michelene TH Chi, Robert Glaser, and Marshall J Farr. The nature of expertise. Psychology Press, 2014.
[14] François Chollet. On the measure of intelligence. CoRR, abs/1911.01547,
[15] William R. Cook. Applescript. In HOPL, pages 1-21. ACM, 2007.
[16] Carlos G Correa, Mark Ho, Fred Callaway, and Thomas I. Griffiths. Resource-rational task decomposition to minimize planning costs. arXiv preprint arXiv:2007.13862 2020.
[17] Edsger W. Dijkstra. On the foolishness of "natural language programming". In Program Construction, volume 69 of Lecture Notes in Computer Science, pages 51-53. Springer, 1978.
11

---

[18] David Dohan, Winnie Xu, Aitor Lewkowycz, Jacob Austin, David Bieber, Raphael Gontijo Lopes, Yuhuai Wu, Henryk Michalewski, Rif A. Saurous, Jascha Sohl-Dickstein, Kevin Murphy, and Charles Sutton. Language model cascades. CoRR, wttp/220..10342... 2022.
[19] Kevin Ellis, Catherine Wong, Maxwell Nye. Mathias Sable-Meyer, Lue Cary, Lucas Morales, Luke Hewitt, Armando Solar-Lezama, and Joshua B Tenenbaum. Dreamcoder: Growing generalizable, interpretable knowledge with wake-sleep bayesian program learning. arXiv preprint arXivv2006.08888 2020.
[20] Daniel Fried, Armen Aghajanyan, Jessy Lin, Sida Wang, Eric Wallace, Freda Shi, Ruiqi Zhong, Wen-tau Yih, Luke Zettlemoyer, and Mike Lewis. Incoder: A generative model for code infilling and synthesis. CoRR, abs/2204.05999, 2022.
[21] S. Gulwani. Automating string processing in spreadsheets using input-output examples. In POPL '11, 2011.
[22] Sumit Gulwani and Mark Marron. Nlyze: interactive programming by natural language for spreadsheet data analysis and manipulation. In SIGMOD Conference, pages 803-814. ACM, 2014.
[23] Sumit Gulwani, Oleksandr Polozov, and Rishabh Singh. Program synthesis. Found. Trends Program. Lang., 4:1-119, 2017.
[24] Mark Halpern. Foundations of the case for natural-language programming. In AFIPS Fall Joint Computing Conference, volume 29 of AFIPS Conference Proceedings, pages 639-649, AFIPS / ACM/ Spartan Books, Washington D.C., 1966.
[25] Harry Harlow. The formation of learning sets. Psychological review, 56(1):51, 1949.
[26] Dan Hendrycks, Steven Basart, Saurav Kadavath, Mantas Mazeika, Akul Arora, Ethan Guo, Collin Burns, Samir Puranik, Horace He, Dawn Song, et al. Measuring coding challenge competence with apps. arXiv preprint arXiv:2/05.099330 2021.
[27] Mark K Ho, David Abel, Carlos G Correa, Michael I. Littman, Jonathan D Cohen, and Thomas L. Griffiths. People construct simplified mental representations to plan. Nature, 606(7912)::22) 136, 2022.
[28] Srinivasan Iyer, Ioannis Konstas, Alvin Cheung, Jayant Krishmamurthy, and Luke Zettlemoyer. Learning neural semantic parser from user feedback. In ACL (1), pages 963-973. Association for Computational Linguistics, 2017.
[29] Aysja Johnson, Wai Keen Vong, Brenden M. Lake, and Todd M. Gureckis. Fast and flexible: Human program induction abstract reasoning tasks. CoRR, abs/2103.05823, 2021.
[30] Siddharth Karamcheti, Dorsa Sadigh, and Percy Liang. Learning adaptive language interfaces through decomposition. arXiv preprint arXiv:20/0.05/90. 2020.
[31] Darren Key, Wen-Ding Li, and Kevin Ellis. I speak, you verify: Toward trustworthy neural program synthesis. CoRR, abs/2210.00 220.00888, 2022.
[32] Brenden M. Lake and Steven T. Piantadosi. People infer recursive visual concepts from just few examples. CoRR, abs/1 990400834, 2019.
[33] Hung Le, Yue Wang, Akhilesh Deepak Gotmare, Silvio Savarese, and Steven Chu-Hong Hoi. Coderl: Mastering code generation through pretrained models and deep reinforcement learning. In NeurlPS. 2022.
[34] Yujia Li, David H. Choi, Junyoung Chung, Nate Kushman, Julian Schrittwieser, Rémi Leblond, Tom Eccles, James Keeling, Felix Gimeno, Agustin Dal Lago, Thomas Hubert, Peter Choy, Cyprien de Masson d' Autume, Igor Babuschkin, Xinyun Chen, Po-Sen Huang, Johannes Welbl, Sven Gowal, Alexey Cherepanov, James Molloy, Daniel J. Mankowitz, Esme Sutherland Robson, Pushmeet Kohli, Nando de Freitas, Koray Kavukeuoglu, and Oriol Vinyals. Competition-level code generation with alphacode. CoRR, abs/2203.00 07881077111. 2022.
12

---

[35] Jenny T Liang, Chenyang Yang, and Brad A Myers. Understanding the usability of ai program- ming assistants. arXiv preprint arXiv:2303..7722, 2023.
[36] Yaobo Liang, Chenfei Wu, Ting Song, Wenshan Wu, Yan Xia, Yu Liu, Yang Ou, Shuai Lu, Lei Ji, Shaoguang Mao, Yun Wang, Linjun Shou, Ming Gong, and Nan Duan. Taskmatrix.ai. Com- pleting tasks by connecting foundation models with millions of apis. CoRR, abs/2303.16434 2023.
[37] Hugo Liu and Henry Lieberman. Programmatic semantics for natural language interfaces. In CHI Extended Abstracts, pages 1597-1600. ACM, 2005.
[38] Michael Xieyang Liu, Advait Sarkar, Carina Negreanu, Benjamin G. 7orn, Jack Williams, Neil Toronto, and Andrew D. Gordon. "what it wants me to say": Bridging the abstraction gap between end-user programmers and code-generating large language models. In CHI, pages 598:1-598:31, ACM, 2023.
[39] Zhaoyang Liu, Yinan Hc, Wenhai Wang. Weiyun Wang, Yi Wang, Shoufa Chen, Qinglong Zhang. Yang Yang. Qingyun Li, Jiashuo Yu, et al. Internchat: Solving vision-centric tasks by interacting with chatbots beyond language. arXiv preprint arXiv:2305.0560 2023.
[40] Tania Lombrozo. The structure and function of explanations. Trends in cognitive sciences, 10 410):464-40, 2006.
[41] Shuai Lu, Daya Guo, Shuo Ren, Junjie Huang, Alexey Svyatkovskiy, Ambrosio Blanco, Colin B. Clement, Dawn Drain, Daxin Jiang, Duyu Tang, Ge Li, Lidong Zhou, Linjun Shou, Long Zhou, Michele Tufano, Ming Gong, Ming Zhou, Nan Duan, Neel Sundaresan, Shao Kun Deng, Shengyu Fu, and Shujie Liu. Codexglue: A machine learning benchmark dataset for code understanding and generation. CoRR, abs/2102.04664, 2021.
[42] Aman Madaan, Niket Tandon, Prakhar Gupta, Skyler Hallinan, Luyu Gao, Sarah Wiegreffe, Uri Alon, Nouha Dziri, Shrimai Prabhumoye, Yiming Yang, Sean Welleck, Bodhisattwa Prasad Majumder, Shashank Gupta, Amir Yazdanbakhsh, and Peter Clark. Self-refine: Iterative refinement with self-feedback. CoRR. abs/2303, 17651, 2023.
[43] Lance A. Miller. Natural language programming: Styles, strategies, and contrasts. IBM Syst. J., 20(2):184-2155 1981.
[44] Erik Nijkamp, Bo Pang. Hiroaki Hayashi, Lifu Tu, Huan Wang, Yingbo Zhou, Silvio Savarese, and Caiming Xiong. Codegen: An open large language model for code with multi-tumn program synthesis. arXiv preprint arXiv:2203. 13474, 2022.
[45] R OpenAI. Gpt-4 technical report. arxiv 2303.08774. View in Article, 2023.
[46] Chris Parnin and Alessandro Orso. Are automated debugging techniques actually helping programmers? In ISSTA, pages 199-209. ACM, 2011.
[47] Gabriel Poesia, Alex Polozov, Vu Le, Ashish Tiwari, Gustavo Soares, Christopher Meek, and Sumit Gulwani. Synchromesh: Reliable code generation from pre-trained language models. In ICLR. OpenReview.net, 2022.
[48] Nadia Polikarpova, Ivan Kuraj, and Armando Solar-Lezane Program synthesis from polymor- phic refinement types. ACM SIGPLAN Notices, 51(6):222-538, 2016.
[49] Jean F. Sammet. The use of english programming language. Commun. ACM, 93)):22--23 1966.
[50] Timo Schick, Jane Dwivedi-Yas Yu, Roberto Dessi, Roberta Raileanu, Maria Lomeli, Luke Zettle- moyer, Nicola Cancedda, and Thomas Scialom. Toolformer: Language models can teach themselves to use tools. CoRR, abs/2302.04761, 2023.
[51] Imanol Schlag, Sainbayar Sukhbaatar, Asli Celikyilmaz, Wen-tau Yih, Jason Weston, Jürgen Schmidhuber, and Xian Li. Large language model programs. CoRR, abs/2305.0522 2023.
13

---

[52] Yongliang Shen, Kaitao Song, Xu Tan, Dongsheng Li, Weiming Lu, and Yueting Zhuang. Hug- gingept: Solving Al tasks with chatgpt and its friends in huggingface. CoRR, abs/2303.17588) 2023.
[53] Noah Shinn, Federico Cassano, Beck Labash, Ashwin Gopinath, Karthik Narasimhan, and Shunyu Yao. Reflexion: Language agents with verbal reinforcement learning. arXiv preprint arXiv:2303.11366, 14, 2023.
[54] Armando Solar-Lezama, Program synthesis by sketching. University of California, Berkeley, 2008.
[55] Armando Solar-Lezama, Rodric M. Rabbah, Rastislav Bodík, and Kemal Ebcioglu. Program- ming by sketching for bit-streaming programs. In PIDI, pages 281 281-294, ACM, 2005.
[56] Dídac Surís, Sachit Menon, and Carl Vondrick. Vipergpt: Visual inference via python execution for reasoning. CoRR, abx/2303.08$ 000000000.1...... 2023.
[57] Stefanie Tellex, Thomas Kollar, Steven Dickerson, Matthew R. Walter, Ashis Gopal Banerjee, Seth J. Teller, and Nicholas Roy. Understanding natural language commands for robotic navigation and mobile manipulation. In AAAI. AAAI Press, 2011.
[58] Stefanie Tellex, Ross A. Knepper, Adrian Li, Daniela Rus, and Nicholas Roy. Asking for help using inverse semantics. In Robotics: Science and Systems, 2014.
[59] Josh Tenenbaum. Building machines that learn and think like people. AAMAS, page International Foundation for Autonomous Agents and Multiagent Systems Richland, SC, USA/ / ACM, 2018.
[60] Lucas Y. Tian, Kevin Ellis, Marta Kryven, and Josh Tenenbaum. Learning abstract structure for drawing by efficient motor program induction. In NeurlPS, 2020.
[61] Priyan Vaithilingam,, Tianyi Zhang, and Elena L. Glassman. Expectation vs, experience: Evaluating the usability of code generation tools powered by large language models. In CHI Extended Abstracts, pages 332:1-332: ACM, 2022.
[62] Priyan Vaithilingam, Elena L Glassman. Peter Groenwegen, Sumit Gulwani, Austin Z Henley, Rohan Malpani, David Pugh. Arjun Radhakrishna, Gustavo Soares, Joey Wang, al. Towards more effective ai- ai-assisted programming: A systematic design exploration to improve visual studio intellicode's 's user experience. In IEEE/ACM International Conference on Software Engineering (ICSE). To appear, 2023.
[63] Iris Vessey. Expertise in debugging computer programs: A process analysis. Int. J. Man Mach. Stud., 23(5):459-499 1985.
[64] Sida I. Wang, Samuel Ginn, Percy Liang, and Christopher D. Manning. Naturalizing a pro- gramming language via interactive learning. In ACL (1), pages 929-938. Association for Computational Linguisties, 2017.
[65] Yushi Wang, Jonathan Berant, and Percy Liang. Building semantic parser overnight. In ACI.
(1), pages 1332-1342, The Association for Computer Linguistics, 2015.
[66] Catherine Wong, Kevin M Ellis, Joshua Tenenbaum, and Jacob Andreas. Leveraging language to learn program abstractions and search heuristics. In International Conference Machine Learning, pages 11193-1 1204. PMLR, 2021.
[67] Chenfei Wu, Shengming Yin, Weizhen Qi, Xiaodong Wang, Zecheng Tang, and Nan Duan. Visual chatgpt: Talking, drawing and editing with visual foundation models. CoRR, abs/2303.04671, 2023.
[68] Tongshuang Wu, Ellen Jiang, Aaron Donsbach, Jeff Gray, Alejandra Molina, Michael Terry, and Carrie J. Cai. Prompichainer: Chaining large language model prompts through visual programming. CoRR, abs/2203.06564 2022.
[69] Frank F. Xu, Bogdan Vasilescu, and Graham Neubig. In-ide code generation from natural language: Promise and challenges. ACM Trans. Softw. Eng. Methodol., 31(2):29:1229:77 2022.
14

---

[70] Zhengyuan Yang, Linjie Li, Jianfeng Wang, Kevin Lin. Ehsan Azarnasab, Faisal Ahmed, Zicheng Liu, Ce Liu, Michael Zeng. and Lijuan Wang. MM-REACT: prompting chatgpt for multimodal reasoning and action. CoRR, abs/2303.1 1381, 2023.
[71] Eric Zelikman, Qian Huang, Gabriel Poesia, Noah D. Goodman, and Nick Haber. Parsel: A unified natural language framework for algorithmic reasoning. CoRR, abs/2212.10561, 2022.
[72] Yichi Zhang and Joyce Chai. Hierarchical task learning from language instructions with unified transformers and seff-monitoring. arXiv preprint (rXiv:210600322, 2021.
15

---

Appendix
Table of Contents
A Additional Related Work
17
A.1 Programming with Natural Language
17
A.2 LLMs as an Interpreter
17
B Detailed Limitations and Future Work
C Broader Impacts
18
D ANPL Details
19
D.1 An ANPL Code Example
19
D.2
Syntactic Sugar
19
D.3
Implementation Details
19
E
Human Studies
20
E.1
Questionnaire
20
E.2
Tutorials
22
E.3
User Interface
22
E,4
Suggested Prompts for System
24
E.5
Task Assignment..
24
F
Additional Experiments and Analysis
26
F.I
Benchmarks
26
F2
Additional Analysis ARC
................................
26
F3
Human Studies on APPS
27
F4
Case Studies on "Long and Realistic" Programming Tasks
28
F5
Automatic Code Generation on HumanEval
28
DARC Details
32
Computational Resources
34
Case Study
35
16

---

A Additional Related Work
A.1 Programming with Natural Language
Due to the low learning requirements, programming with natural language has been seen an attractive programming mode since 1960s [6, 15, 17, 24, 37, 43, 49]. The relevant domains encompass semantic parsing [28, 65], language grounding [57, 58], and so on. Among these works, Wang et al. [64] is the most similar which let users build complex voxel structures by defining alternative, more natural syntax, and increasingly complex natural concepts, starting from a core programming language. However, they are restricted by the pre-defined natural language specifications and Nomain-specitfe languages while this paper focuses on unconstrained natural language and general-purpose languages like Python. Furthermore, it should be noted that the interactive processes involved in these studies rely on manually annotated data, whereas our system operates in a truly debugging fashion for programs composed of natural language.
A.2 LLMs as an Interpreter
LLMs have been embedded in programs as an interpreter, due to their capabilities of common sense question answering and simple natural language reasoning [50, 51, 68]. For example, Cheng et al. [12] leverages LLMs to generate programs for questions like "Is Mexico North America?" with Codex API calls like J(North America?, . ferico) and then answer it by executing and prompting. Dohan et al. [18] composes LLMs into a probabilistic programming framework, which allows control flow and dynamic structure. Different from these works, we focus leveraging LLMs to implement natural language modules into executable programs. We take the utilization of taking LLMs as parts of our generated programs future work.
B Detailed Limitations and Future Work
Though our system has shown excellent performance revealed by the large-scale human study, there are still three main limitations to our current system. The first limitation is the response of LLMs. ANPL gives users a detailed implementation of each hole in Python and asks them to further debug. This requires users to read Python code when editing ANPL programs. LLMs may employ certain APIs that users may not be familiar with, resulting in the implementation of function that deviates from the users' intended approach. Consequently, comprehending Python code becomes more challenging. Additionally, when LLMs automatically break down a function into fub-functions, identifying the specific sub-function containing bug becomes difficult for users. To enhance the user-friendlinnss of ANPL and alleviate the burden on users in terms of their code capabilities, how can ANPL provides concise summaries of each function in easily understandable natural language should be studied. These summaries would enable users to identify any misinterpretations or incorrect implementations based the corresponding descriptions, allowing them to modify their natural language descriptions accordingly without the need for complete redrafting.
Another limitation is the absence of comprchensive natural language libraries. In the context of code generation using LLMs, the quality of the prompt and the accompanying description assumes paramount importance. However, the creation of effective natural language descriptions necessitates considerable expertise in prompt engineering. In order to mitigate this issue, a natural language library should be established. The natural language content within this library is derived from two primary sources: library learning methods [66] and user contributions, and users can share and reuse natural language and corresponding implementations made by each other.
So far, ANPL has been limited to generating Python code for solving ARC problems through communication with users. However, as mentioned carlier, some ARC tasks cannot be fully addressed with Python programs alone and require the use of neural modules like object detection. Therefore, we need to integrate ANPL with neural modules, similar to works including Cheng et al. [12], Shen al. [52], Surís et al. [56]. This integration would further enhance the capabilities of the ANPL compiler and expand the range of tasks that ANPL can handle. Additionally, the application scope should not be confined solely to the ARC dataset but should extend to multiple domains, such as chip design, program writing, and robot control. For example, Cheng et al. [1]] automatically designed CPU with Binary Speculation Diagram (BSD), yielding modular micro-operations that can be utilized by ANPL compiler and makes it possible to use ANPL-designed CPUs in the future. However,
17

---

due to the unique characteristics of ARC itself and the limited availability of human resources, is well-suited for conducting user programmming experiments and human study reports. Thus, we have chosen ARC as the main platform for conducting our experiments and presenting our findings.
C Broader Impacts
On one hand, ANPL sheds light on the human- computer interaction paradigm by making the interaction more stable and reliable through low-cost predefined programming conventions. On the other hand, ANPL has the potential to promote the development of the programming field and broaden the scope of programming applications. For example, enables enables debug with natural language which can significantly lower the programming barrier. Furthermore, the proposed DARC dataset reveals how humans systematically decompose complex problems into simpler ones when faced with logical problems similar to ARC. This could provide further insights to cognitive science and foster advancements in related fields.
to program and
However, ANPL also raises safety challenges by producing code that is unaligned with user intent and can be misused. We refer readers to the broader impacts and hazard analysis discussed compre- hensively by Chen et al. [9] as the basic component of the ANPL compiler the LLM. Note that, compared to Chen al. [9]. more significant concern with the usage of ANPL is its lower barrier to entry, allowing individuals with limited programming experience to generate code. This may result in code generated by ANPL lacking the scrutiny and maintenance of experienced personnel, making more susceptible to misuse and thereby leading to more severe issues related to code security. Besides, since these users may have limited exposure open-source communities such as GitHub, models trained on corresponding data may face greater challenges user alignment.
18

---

D ANPL Details
D.I An ANPL Code Example
Figure 10 is an ANPL code example for the task shown in Figure 9. In this example, users first decom- pose the task into "Change the imput into four new arrays based on the central dividing 1ine in the and y directions" and "Find array that doesn't have just either define a hole by name like seperste_inpll with corresponding parameters, or they can just code a piece of natural language description like "Find array that doesn't have just color" and set the sketch by specifying input-output variables.
color". Then, users can
Figure 9: Task 64 of ARC.
soparate_inpinn (tt.utttttttttt).. (input))
"Caagg the input into four new arrays based on the central dividing line in the x and y directions"
def main wwwnniiiiinnnnne (input))
inputs seperate_input(ingg (input)
output "Find an array that doesn't have just one color" (inputs)
return output
Figure 10: An ANPL code example for task 64.
D.2 Syntactic Sugar
Recursion. ANPL employs a hole within the function's 's body to implement recursion, following the thought of Y Combinator. A function can indirectly invoke itself by passing its own reference to hole within its own body.
Figure 11 an example demonstrating the use hole-driven recursion with the Flood Fill algorithm. In this example, the floodfill function is passed as argument to the hole "apply floodfill adjacent pirels: above, below, right, and left". The semantics of the hole suggests that floodfill will be applied the adjacent pixels, establishing indirect recursion.
D.3 Implementation Details
ANPL. interacts with the LLM via the prompt shown in Figure 12. In the prompt, the code section will be substituted with all the executed codes up that point, and the hole section will be replaced
19

---

(grid, 1):
valid grid (grid, 5) grid(s, i]
return grid
else:
return "appy floodrill to adjacent pixela: above, belox, right, and lart"Ggri,, 1, floodri11)
Figure 11: Recursion in ANPL.
with the designated function name of the hole along with the natural language description given by the user. During the initial user input and function editing, it goes through sequence of five attempts, starting with a temperature parameter of and incrementing by 0.1 with each try until it succeeds. In the resynthesis stage, ANPL requests the underlying LLM to produce 10 potential completions for each prompt. The text that ChatGPT generates will be subject to a maximum token constraint of 1024.
syatem prompt
pythonCPT, your complete unimplenented functione given python code, __holo0, _hoole,, _hole2, Your implementation should align with the code and docunentation using Python.
which referred
and
# user prompt
"ppythnn (coda)
The Function needa be given Markdown format should used to return it.
** "python
(hola)
Figure 12: Prompts used in ANPL.
E
Human Studies
F.
Questionnaire
We conducted a survey to investigate users' programming abilities, LLM usage experiences, evalua- tions of system and system B, well as the perceived importance of various functionalities within system A. The detailed questions are as follows:
1. How would you rate your programming skills?
1: Non-programmer
2: Beginner, struggles with solving LeetCode medium-level problems
3: Familiar with a programming language, understands basic data structures and algorithms,
able to solve some LeetCode medium-level problems
4: Proficient in common data structures and algorithms, capable of solving many LeetCode medium-level problems
5: Skilled in data structures and algorithms, capable of solving LeetCode hard-level problems
2. How familiar are you with the Python language?
1: No exposure to Python.
2: Have used Python, familiar with basic syntax, but rarely used in daily activities.
3: Occasionally use Python to write simple scripts, not familiar with Python libraries such
NumPy and PyTorch.
4: Proficient in Python features, frequently use Python, and familiar with some libraries.
5: Mastery in Python and proficiency in using common libraries.
3. Have you used language models to generate code before?
20

---

4. How do you perceive the difficulty of ARC questions? (I: Very easy- 5: Very hard)
5. Do you find System (ANPL) useful? (1: Very dissatisfied 5: Very satisfied)
6. Do you find System (natural language) useful? (1: Very dissatisfied 5: Very satisfied)
7. How important do you consider the Trace feature of System A? (1: Very unimportant 5: Very important)
8. How important do you consider the Edit feature of System A? (1: Very unimportant - Very important)
9. How important do you consider the Resynthesis feature of System A? (I: Very unimportant
5: Very important)
The results shown in Figure 13. Participants in human study primary Python programmers and half them are not familiar with code generation with LLMs. The average score of system A is 4.05, significantly greater than system B which scores 2.58. System A achieves not only higher solving rate but also a better user experience than System B. Besides, most users find tracing and editing useful while resynthesizing less important, which shows the limitation of LLM code generation and indicates the importance of introducing user interaction solving complex tasks like ARC.
Programming Skits Reing
(2) Python Language Fanilirity
Language Modal Code Generation
(4) Dificuity ARC Questions
Uselumesss System (ANFL)
(6) Usefulness of System (Natural Language)
14
importance Trace Feature (System
(8) Importance Edit Festure (8ystem
(9) Importance of Resynthesie Festure (Sysiem
Figure 13: Questionnaire Analysis. The average score of System A is 4.05, and System B is 2.58.
21

---

E.2 Tutorials
The task requires you to solve ARC (Abstraction and Reasoning Corpus) tasks, each composed of several input-output pairs. These pairs maintain a uniform pattern and are structured as color grids with ten distinct colors: black, blue, red, green, yellow, grey, pink, orange, teal, and maroon.
The goal is to deduce patterns from the input-output pairs and communicate your solution to the system. this experiment, you will interact with two systems: System A and System System accepts ANPL inputs, whereas System B functions on full natural language. Both systems aim to generate Python code that transforms the input into the expected output.
Each task requires working with both systems in specific order provided in the task assignment. To begin, find the ARC task solution independently (solve the task in your mind, i.e. with Python). With a solution in hand, activate the system, which will initiate a timer.
Your target is to instruct the systems to generate accurate Python code based your solution. We will evaluate the program strictly on the test input and output, yet it's essential for you to confirm that your program is capable of successfully handling all the training input and output. Once the correct code is produced, the system will automatically deactivate. Perseverance is crucial, but if the system fails to generate the accurate code within 30 minutes, you permitted to terminate the process. If task proves overly challenging at any point, it's acceptable to stop prematurely.
System A is comprised of three primary operations. The trace operation allows for function name to be entered, which triggers the program to run on a test input and displays all the input and output data of the selected function. The edit operation allows for direct changes to function's 's body, including alterations to the sketch and hole. This operation has four sub-operations:
Splitting the original function into multiple holes linked by the sketch.
Turning the original code into a hole and attempting code generation.
Changing the natural language description associated with the hole.
Modifying the sketch while maintaining the generated hole.
The resynthesis operation requires the user provide correct input and output examples. The system then generates numerous functions and tests in which one meets these examples. The provided examples are kept for future use, and multiple sets of examples can be provided by the user.
System incorporates two operations. The chat operation allows the user to interact with the system using natural language, leading to code generation modification based on these descriptions, The remove history operation allows the user to select and delete some historical conversation data?.
E.3
User Interface
The user interface consists of 4 components: tracing operation, editing operation, resynthesizing operation, and grid editor.
Tracing. The tracing operation has three panels, namely function selection, visual IO, and textual 10, see Figure 14. The function selection section allows users to choose from a list of available functions eligible for tracing. After selecting a function, IOs shown users within the visual IO and the textual 10 panels, where the visual IO panel visualizes the 10 into grids and the textual IO panel prints the 10 NumPy arrays.
Editing. The editing operation has three panels: function selection, function editing, and code synthesis, see Figure 15. The function selection panel serves the same purpose as the one in the tracing operation. After selection, users can modify ANPL code in the function editing panel and submit it to the LLM for code generation. They can then view the code generation progress in the code synthesis panel.
Note that participants were free to delete or modify their chat content and they can even write an ANPL program and then "compile" it by hand when using System B. Also, we did not explicitly forbid the users to write Python code in our experiment they write Python code if they want.
22

---

SYSTDK: Wifch consand would you Wike to do7 Trace [X] Edit" [J] Resynohests [4]
Renove To [1] dare (1/977771
Functiions
Function Select
Functtion on
Code: han
The number To Examples
Bain
Code
insert. to..tto.fii First
Fronpt Fronpt
generate.nce gen..gr1
SYSTEM: Which
Function
select? featn/rourr sivels
foserr. /twer/
www.errree..eeerreeir.oo msto
SPSTER WIRUT 1o
Tepurs Outpur
Visual IO
I0Exumple -d
input_arid
Textual 10
the
input_orid: grid: CEDy
V DA
0,
Di
9.
DR, 0,
0,
[o, 9. 8, 9, 9, 9D3)
autzut: arm ((E2, 9,
Figure 14: The tracing operation. Users can check the execution trace between high-level holes.
SYSTPM: Which comsand smuld
1ike to do? [13 Traee
[2] idite [X] Recynthexis
[4] Reanve TD [S] Quin (8/2/8/4/533
Functtions
Function Select
Functtin nase
has Code or has Pronpt
The number of IO Exueples
asin
Code
count pixels
Proept
SYSTEM: With function do want le select? (asin/sumt /imer Tast /ommerate main
SYSTEN: P Plezse input your code for kain
SYSIIE:: Please enter your sepl code
SYSTEM: Press [Eac] fol Towed by [Encer] to accept Ieput.
Function Edit
oddf cain(inuu.ggiie grid: ap.ndarray) +> np.ndarray:
c.n
input, you
see
wulciple pixels.
Fan
Hist count.pfsels(inew weffssssssnuuc.ooo
color_list insert_last_ter firstttooi
ans_grid qemerate return wwwp:/wwwwwdduuu.errooommm color_7iat)
Code Synthesis
Synthestzing...
Figure 15: The editing operation. Users can edit the existing ANPL program through further decomposition just modifying the code natural language.
Resynthesizing. The resynthesis operation has three panels: function selection, IO entering, and code synthesis, see Figure 16. The function selection panel and the code synthesis panel serve the same purpose the ones mentioned above. The 10 entering panel enables users to constrain the programs generated by the L.LM by providing IOs. Specifically, LIM generates a set of 10 candidate Python programs, and subsequently selects the program(s) that satisfy the given IO constraints the compiled program.
Grid editor. In order to facilitate the transition for users between visual IO (i.e. colored grids) and textual I0 (i.e. NumPy array), we have implemented grid editor (Figure 17). This editor consists of the following elements:
1. Resize: Allows users to specify the dimensions of the grid.
2. Generate: Generate the corresponding grids by inputting Numpy array.
3. Reset: Reinitializes the current grid to its initial state.
4. Copy:
Converts the current grid into Numpy array and copies it to the clipboard.
5. Graphical editing area: Provides three operations, including edit, select, and flood fill, along with 10 different colors, for direct editing of the colored grids
Note that this editor was provided as a supplementary tool to all systems, so it has no impact on the final experimental results.
23

---

you
(2) (3) Resyntheets [4] (1/2/3/6/53
Function Select
Funcetion on nome
has
Code or has Pronpt
the rumber of 10 txasples
count count_p we1s generate_
Prompe Proupt
SUSTER Wttch finchhfunction. 20. you nant, 50, select? Locuez aimer las, 10.7..00 firat/oonoratt now artdl counT, piNols
Outpus exappie for counc plaess impur_ge 0,
arrayy[[s,
(9,
(9.
SSSTEP:: Pl Please enter the va lue output.
13,0,51
SYSTEP: Synthestzinn.....
Code Synthesis
SYSTE%:
Figure 16: The resynthesis operation. Users can provide 10 constraints and ask the compiler to resynthesize the program.
Resize Grid
Change grid size:
2"3
Resize
text used generate grid:
0ra3([[1..33]j22..3
Generate
grid
Resel grid
Copy!
Convert the current matrix to text and copy to the cliphoard
Graphical editing area
Edit
Select
Flood fill
Edit mode
Color selection
Figure 17: The grid editor.
E.4 Suggested Prompts for System B
Users can input natural language without restrictions in system B. To enhance the user experience, offer them suggested prompt template shown in Figure 18.
E.5
Task Assignment
Table provides an assignment for ARC tasks. Each number corresponds to a question; a number highlighted in blue instructs of System before System B, whereas orange number, conversely, denotes System be operated before System A.
24

---

You are a skilled Python progranmer.
Your task is to write Python code to transform the input grid into the output grid.
In the input grid, should see
To make output grid, you should
Return your Python code
"python
import numpy
black, blue, red, green, yellow, grey, pink, orange, teal, maroon range (10)
def main(taput.grid: up. up.nderray) -> up ndarray::
Figure 18: prompt for System B.
User id
Tasks
4. 36 48 50 116 128 222 230 309 384
6.74 101 102 104 139 141 150 152 218 235 247 257 279 289 312 332
340 343 356 368 370 374 382
21 61 65 69 86 92 164 165 182 183 186 227 234 258 261 262 271
307 310 344 378 379 386
3
0.8:22 75 95 108 125 140 157 192 198 202 205 228 237 245 255 265
280 339 346 363 365 371 381
4
24 37 68 71 80 87 98 114 124 166 170 200 206 208 241 272 297 298
301 302 303 315 317 319 327 336 360 361 389 398
5
16 30 56 62 70 111 120 130 142 151 173 180 185
212 215 226 275
295 347 364 388 393 397
53.63 IO5 135 137 159 176 224 244
260
278 300
320 341 359
7
10 35 90 144 161 162 175 199 219 231 236 263
287 299
323 333 345
91 112 126 129 168 181 190 191 193 248 264 285 306 387 391
18 26 41 77 79 122
127
131
160
223
252
277 292
321
338
129 38 42 54 88
96
99
115
136
145
147
153
246
283 308
322 355
380 383 385
13 31 32 57 118 132 138 149 225 240 251 267 270 286 304
313.314 353 396
12
15 64 83 117 119 155 156 167 189 210 214 221 233 242 254 256
276 293 296 305 325 354 367 369 376 392 395
13
5.77 33 51 82 123 134 172 177 178 201 216 229
232 243 282 288 311
330 358 377 399
14
20 47 73 171 187 195 217 220 328 337 351
15
11.99 46 60 93 106 107 110 113 163 184 209 213 239 274 326 333 342
372
16
39 67 76 78 103 158 179 188 204 207 253 266 294 334 335 348 350
357 362 366 390 394
17
377 109 133 197 259
18
19 45 52 66 72 84 85 89 100 121 143 146 148 154 169 174 194 196
203 238 249 250 268 269 273 284 290 291 324 329 349 352 373 375
Table 1: Task assignment. Blue: use System A and then System B. Orange: use System B and then
System A
25

---

F
Additional Experiments and Analysis
In this section, we discuss the reasons for choosing ARC as our main benchmark, conduct further analysis of experimental results, and provide additional results on other tasks to comprchensively demonstrate the advantages and capabilities of ANPL.
F.1 Benchmarks
Why do we choose ARC instead of typical code generation benchmarks like HumanEval [9] and APPS [26]. We evaluate ANPL ARC instead of common code generation benchmarks [3, 9, 41, 44] according to the following three reasons: (1) We clarify that what we are measuring is the system's 's ability convey the user's intent through interaction, not the system's 's ability solve problems on its own (e.g. the user has a correct algorithmic solution in mind, but is tedious to realize it in Python). In this regard, ARC's features (easy for humans understand and solve but difficult to express via programming) would be more suitable than typical programming datasets such as MBPP and EvaanEEal. (2) We find that typical programming datasets are simpler for programming compared with ARC. The average line of code of MBPP, HumanEval, APPS, and ARC are 6.71, 7.78, 19.95, and 26.47 respectively. Competition datasets like APPS challenge the users to solve the tasks rather than generate code that fulfills users' intents. (3) Solutions for common code generation benchmarks can be found on the Internet, which runs the risk of data contamination. On the other hand, it is unlikely programmatic (python) solutions for ARC exist in any online corpus, making tasks ARC unique enough for LLMs and participants of human study. However, to fully present the advantage and capability of ANPL, we have supplemented additional experiments with human studies on APPS benchmark, case studies on "realistic and long" programs, and automatic code generation on HumanEval benchmark.
Why does the standard of "success" the accuracy of the training I/Os. Our experiment assesses the system's 's capacity to fulfill user intents rather than users' ability to design generalizable algorithms. User intent is defined as writing program to pass the provided I/Os. Thus, we present the solving rate of test I/O in the main paper. Although it is a simplified setting, it is appropriate and sufficient taking into account the 440 man-hours invested already. However, we understand that readers may be interested in other information related to ARC itself, such as whether the Python code can be used to generate I/Os or whether DARC can provide insights into human decomposition strategies. Thus, we included the accuracy of all I/Os in the appendix as addition.
F.2
Additional Analysis on ARC
The importance of the control structures and holes. In order to analyze the significance of the programming model, we conduct an analysis on the proportion of control structures (e.g., for, while, if) and holes in programs that were correct in both system A and system B, and the proportion of programs that were correct in system A but incorrect in system B. In the programs that were correct in both systems, 47.8% utilized control flow, maintaining an average of 2.47 holes. On the other hand, remarkable 97.4% of programs that were correctly functioning in system A but failed in system incorporated control flow, and had an increased average of 3.37 holes. Results show that the introduction of control structure and hole has significant positive impact on the user's ability to accomplish highly complex tasks.
The distribution of time and the number of interactions. Furthermore, we conduct an analysis of the time consumption and the number of interactions involved in solved problems. That is, we filter the problems that can be solved by both systems A and B, collect the time and number of interactions spent by users, and then construct the two distributions shown Figure 19. Results show that, for these tasks, system A exhibits faster completion times and fewer interaction counts (without TC) compared to system B, with slight advantages in terms of time and interaction. Nevertheless, this advantage is not highly pronounced, which could be attributed to the relatively low difficulty level of the problems that both system A and system B are capable of solving.
Generalization ability. We further examine the accuracy of programs from System A and System using all 10 cases, see Table 2. System A and system B have similar generalization abilities based on the observation that for tasks passed on test cases by both two systems (224), the number of tasks
26

---

System
0.00125
0.20
System
System A TC
0.00100
0.15
Density
0.00075
0.10
0.00050
0.00025
0.05
0.00000
0.00
1000
3000
50
Time
Interaction
Figure 19: The distribution of time and the number of interactions. Trace Calculated (TC) means the trace mode considered into interactions.
B
dx
xx
Total
11
177
5
45
227
JX
10
32
31
73
XX
3
100
Total
194
40
166
400
Table 2: Generalization on ARC. / /mmans the compiled Python program passes both train cases and test cases. Xmmeass the Python program passes the test cases but fails train cases. XXmeans the program fails in all the cases.
that system A failed to generalize on all IO cases is 10/224 and the number system B is 5/224, and these numbers have significant differences. Thus, conclude that programs failed to generalize to all IO cases because of the difficulty of the corresponding tasks and the designing of the underlying algorithm, which is independent of the usage of systems.
GPT-4 results on System and D. During the experiment, we didn't have access to the GPT-4 API and it impossible to conduct another large-scale human study for GPT-4 now. However, can measure the solving rate w/o the interaction of ANPL+GPT-4 (System C) and GPT-4 (System D) with existing data: From the result in Table 3, we can conclude that (1) although a more advanced LLM would achieve higher accuracy, the utilization of ANPL always results in an improvement. (2) ARC still remains difficult for GPT-4 to give 1-shot answer, making intent clarification a persistent challenge in using LLMs as programming assistants.
F.3 Human Studies on APPS
Here we aim discuss the generalization ability of ANPL on typical programming tasks and compare ANPL on programming ability against Parsel (not automatic code generation ability).
We conduct small study with 4 participants and 20 randomly selected APPS-interview problems. Other domains considered were MBPP, HvmanEval, and APPS-competition problems. We did not choose MBPP and HumanEval because they much simpler compared with ARC, with many questions solvable using just few lines of Python code (The [min, max, mean] of lines of ARC's (passed) program [4. 113. 26.47] while MBPP is [2. 50. 6.71]. HumanEval [2, 32, 7.781). Also, we did not test on competition-leww
tasks limited by user ability. Each participant was instructed to solve each problem with three systems (ANPL, GPT-3.5-turo,, and Parsel) appearing in random order for a total of 30 minutes per system. We replicated Parsel with GPT-3.5 (0T-3.5-turbo because Codex is no longer available. As shown in Figure 20: (1) ANPL outperforms the original GPT-3.5-turbee and Parsel in final solving rate and solving time which is consistent with the result on ARC. Specifically, ANPL achieves 100% solving rate, GPT-3.5-turbo achieves 85%, and Parsel achieves 55%. Also, the 1-shot performance (without interaction) of them is 30%, 0%, and 15% respectively. (2) The solving rate for APPS-interview higher than one on ARC, indicating APPS-interview is easier than ARC for human interaction. In fact, the challenge of APPS lies in how users solve the tasks
27

---

Table 3: GPT-4 and GPT-3.5-turbo results on System C and D
LLM
System C (ours w/o inter.)
System D
GPT-3.5-turbo
23.50 %
16.75%
GPT-4
30.50
23.50%
Solving role:
66
Sodveng
0.50
System
Cysten A
60
003
600
5.2
1200
Number of Interactions
Figure 20: Results of HmPS-interview. A: Solving rate of four systems, where System A is ANPL, System B is GPT-3.5-turbo System C is Parsel, System is ANPL w/o interaction, System E is GPT-3.5-turbe w/o interaction, System D is Parsel w/o modifying. Note that Systems C and D here are different from the main paper. Parsel is replicated with GPT-3.5-turbo and set to sample 10 Python programs each time, which has the sampling number the resynthesis operation of ANPL. B: The relationship between solving rate and time consumption. C: The relationship between solving rate and number of interactions. Note that Parsel cannot effectively facilitate interaction it is presented as dashed line.
rather than grounding users' intents to code. (3) Parsel performs the worst because Parsel and ANPL have different design objectives: ANPL is designed to ground user intent code through interaction while Parsel is designed for automatic reasoning without human intervention. Specifically, Parsel does not even retain the context of past interactions. This leaves the only method for "debugging" to continuously modify the initial Parsel code and provide more I/Os until it can be compiled to Python single attempt.
Overall, we conclude that (1) ANPL is generalizable to different domains and (2) ANPL and Parsel substantially different systems: ANPL is designed significantly reduce programming complexity and assure code quality. where the users can iteratively interact with the system safely ground their minds code; While Parsel is primarily reasoning system, where the programming task is given to it "as is" and leverages the capabilities of LLM to decompose and ground it to code without any user interventions.
interactive programming system to
F.4
Case Studies on "Long and Realistic" Programming Tasks
To further show the ANPL's generalization ability. conduct a qualitative study by using ANPL to compile several projects drawn from CS courses and GitHub: text editor, robot control, naive MAGIC card game, and I-S-8 CPU. These tasks the prototypes of realistic applications and representative in terms of the program form with complex control flows and many sub-functions. They are much longer (198 lines of code average) than existing program synthesis benchmarks (MBPP[6.71) Humannval[77788]] APPS(19.95).
It is shown in Figure 21 that ANPL can be used to implement these applications with much less coding effort (with 33.21% lines code) and obviously lower programming barrier (by using natural language) than Python. Such results show that ANPL has the potential to be adopted in real scenarios with great superiority of lower programming complexity and better code quality assurance.
F55 Automatic Code Generation on HumanEval
Settings. Following Parsel [71], we generated 100 test cases with temperature==0.6 for each problem in HumanEval. Then we generated 4 high-level solutions with temperature=0.6 and corresponding ANPL codes with temperature=0.2 and Deasence_penalty0... 1. For each ANPI. code, we generated 16 Python implementations for each function. Then we sampled the programs composed of generated
28

---

rettre Leeeory's (8) 256. colie
"reptetere:
free pykec dta inpert DISEPION
cipab:
signat "backsgace 1ts Defloe the carnorPaasttio (tevt_acito".
Plapert Mere:
cart will
oobrsoos--taae sugart
your fund
fef stee oo
BROLLLC Japort
del to tf oppesent cond,
det impesioo, rRgA ragh, caule su reparter, If calh, paan cnto the
exscerty and ced
MOTE
maiech
the hiskest foeer
kare, sannd 300
te its respective stots
ANPL
"Ieit DNCURREEEr with
register
lermer poittonn" cliphbare"
det regel cand, plageri,
Taft rotor, right 2210" calor Tritaalus ceslies with left se right and
"Tit Finction stoale support
caloilaned and conpored
wille storal to "pxtec""
def eatoicects, dedid:
inttiatiue comrstcpy,
This Fureton iestializes setory
intemityy
reect stuck sest_aditar lrest pelltrr
Flayerd create (oecka) 211
giaper
player21s
mate(ilegats):
Calortate ts and ihs unienssty eeviation the oa
313
craviplaerrs
Cutssalieee/meryCooa (Cs, filepont) walt rarning
Cse get
rignl a Iepatt]
presertess eath chsone. 1plagari)
indest "suppay
correction, fectomecrr action, factor)
return
"eguiteral
rebure, ''maary' (el
TTag'
frai patrocki aarmeters legart
140
HA suafffcttcard: fard, saxtert,cr
Playeri
36
5 fras totrioaa taala inpart
lepart
aurerr_resitior: sedl -s str
reglt int, raga:
<pet did11
Drivetase
Textfoursar.ree thees!
ee bater carettrett:: tand, player:
(Hlrggal 1
<palter +
sef solce www.aaaeettt....... un
1BB asf text wet.olttor.aa wwstttettttttlie
correction: facton: flaas) fleats
177
storel "bachseacel) to www.r//eeloenssrrrrreoo
iepepiaentrs str, magas int, dichs
Lantce'ar_1aat)
ter, sigratl
Cart, playeri: Plager, player: slager) liees
coa regsttrr 1177) an
regidtere
223
textitest
Python
1011 caultec11
Calorseneer - 1912
reflactionn)
Any tast:
enitort "teck "aack
cer inteistine Switeeessrt: Parts
226
teat seteactttrr rreds, stsce1) (I
care from hare:!)
def tuptinetr, caal: sedress
for
Neterioot.31
ststers
ewaeratalplaee. (cand.rane)
soler, seeer
Diccletr: Any) Here:
coal regasters (Hrrgt
retura He Lavter, right mottrr
texl poitort wor.ooorrrrooooaaaaa Cardoriassttiee
(Cvr, Sefecsefecee,, Type: (aad-119e3)1
"aenary [iasdress)
malrr
wnte(:
inde the cand ana ware to chione: '1
115 del sutttalzee censrytepa: Dictistr.
2t0 with
MOTE
def wedhtl:
Acitoor eicttl
Plaas enter
pristt Chraall teaut,
correction_
instiation wettrrittttttttttttttttttteeeeee
right t
chstre (anteasiee))
139
while
256
wiile signal in "ouDEETT
lentgizyer Fundll
calle Souee coller senter?
Atcenl)
enter Inden.1)
342
canorylcpe, fileseth) unile rannings
211
148
color, Lath [BLk,, willl),
263
alceal a (eput))
358
e4111)
(a)
(b)
(c)
(d)
Figure 21: The ANPL and Python code of four projects: (a) LS-8 CPU (b) a robot controller (c) a text editor (d) naive MAGIC. We present part of the code and mark the ANPL code and its corresponding Python code with the same background color.
functions and evaluated them by generated test cases. If one program passed all the test cases, it would be chosen as the final submission and evaluated by the real test cases. Otherwise, we would debug for each function of the program that passed the most generated test cases. In function-level debug, we used the execution traces to ask LLM for 8 fixed functions with temperature=0.6. Then we repeated the evaluation and debug processes for at most 2 rounds. For LLMs chosen, we use GPT-3.5-turbo-O0S: and GPT-4-0314" Our prompts are shown in Figure 22, 23, 24, 25.
Results. As shown in Table 4, we can conclude that although ANPL. itself is not designed for automatic code generation tasks, due to its explicit recursive decomposition property, this framework has a certain advantage when used for automatic code generation. It achieved 76.22% on GPT-3.5 and 86.59% on GPT-4 both significantly surpassing the original LLM model. Furthermore, the design of ANPL for natural programming debugging was not reflected in this test, so there is still room for improvement in ANPL's performance in automatic code generation tasks, which we will consider as future work
NNot that we did not check the detailed date carefully and this might be different from the other's choices due OpenAl API change
29

---

Method
LLM
Pass @ 1
Original
GPT-3.5
56.7
CodeTT [8. 53]
GPT-3.5
65.8
Reflexion [53]
GPT-3.5
68.1
ANPL (ours)
GPT-3.5
76.22
Original [45]
GPT-4
67
Original [7]
GPT-4
82
Original [53]
GPT-4
80.1
Reflexion [53]
GPT-4
91.0
(Parsel + CodeT) [71]
GPT-4
85.1
ANPL (ours)
GPT-4
86.59
Table GPT-3.5 and GPT-4 Pass@
accuracy on HumanEval [9].
Question-
(question)
Task
Give assert test for this question in the following format. Each assert statement should
assert
You should only output the assert test. Omit explanations or any additional text.
Figure 22: Test generation prompt for HumanEval.
Question........
(question]
-..-- -aa--Taskk----
Propose clever and efficient high-level solution this problem. Consider all edge and failure modes.
Some common strategies include:
Constructive algorithms, Binary search, Depth-firat search (DFS) and similar algorithms, Dynamic programming, Bitmaske, force, Greedy algorithme, Graphs, pointers, Trees, Geometry, Graph matchings, Hashing, Probabilities, Data structures, Sortings, Games, Number theory, Combinatorics, Divide and conquer, Disjoint set union (DSU), Expression parsing
Let's think step by step to come up with clever algorithm.
You should only output high-level solution without any pseudocode or code.
Figure 23: High-level solution prompt for HumanEval.
30

---

Question- {question)
-..- Solu-oontnin.......
(nolution)
Task---..
Translate the solution for the problen into python code in the following format:
.r..--Progaam......
python code
should define some helper functions before function (func_name) decompose Each
function should be described by docstring.
You should only output the python code! Omit explanations or any additional text!
Figure 24: Translation ANPL prompt for HumanEval.
Question-
(question)
S...--Solutioo.........
(solution)
Here an program implementation the solution.
---------g-- Program----.
(program)
Here a function the program with input-output traces.
-..--Fuuctoon--..
Task.....
If there are some mistakes or exceptions in the function, return the fixed function. You can + define helper functions before it to decompose it into sub-functions.
Your output should be in the following format:
(func_name)
The description of the function.
should only output the function code! Omit explanations or any additionsl text!
Figure 25: Function-level debug prompt for HumanEval.
31

---

G
DARC Details
time
role
action
content
ddef main(input):
centers 'traverse the input which is 2- 2-dim numpy array, return
positions which satisfies that there is no grey in its 3*3 neighbor (input)
scores "for each position in the centers, count the yellow position in its 3*3 neighbar (input, centers)
max score np.max(scores)
1684141011.7822
user
enter code
center center_yellow centers(scores==max score)
center black centers(scorest=max score]
output = 'for each position the position list, make its 3'3 neighbor yellow (input, center yellow)
output 'for each position the position list, make its neighbor
black' (output, center black)
return output'
1684141011.7899
system
parser
user enter correct code"
Figure 26: The header of CSV files.
def main(input);
numpy array, return positions there no grey its 3+3 neighbor" (input)
input which
scores "for each position in the centers, count the yellow position in its 3+3 neighber neighbor"(input,, centers)
center_ yellow, center, center_black "return the center with the max scores and other centers (ceaters, scores)
+
output "for each position in the position 1iat, make its 343 neighbor yellos" (input, oante__yellos) output "for each position in the position 1iat, make its 343 neighbor black" (output, center_black) output
Figure 27: An ANPL program in DARC.
(2)
(3)
(4)
Figure 28: The trace of the given ANPL program. (2) Centers framed by red rectangles and mark scores inside each rectangle.
The Recursive Decomposition Dataset of ARC Tasks (DARC) an assemblage of interaction records associated with 400 ARC tasks. These records involve the intercommunication between users, the system, and GPT-3.5-turbe Figure 26 presents the header of each CSV file. For each interaction, data concerning the role, action, content, and timestamp are completely collected and stored. The result is the entire user interaction history with our systems can perfectly replayed at later time. However, the response from L.MSs will be different for the following reasons: (1) we used temperature 1.0, which will cause different tokens to sampled (2) the GPT-3.5-ture implementation might be changed, which is outside of our control.
32

---

import numpy
from lyping import
(black, red, green, yellox, grey, pink, orange, teal, marcon) rango
List[Tupleliat, int]l, scores: up. ap.ndarzay) Tuple Juple[List([uplle [int, - int]l, List(fuplefint, int]]]:
def cettee
nax_acore (a.oax(acores)
max_centers [i] for i in range(enn(centere) if scores [i] -- max_score] other_centent ceaer_ceetrrse. [centers(i] for i in range(lenccontartt if scores (i] max_score] return centers, other_centers)
fond_poiitions, without_grey, weibgggrre.eeibrreeeee...... positions
(input: up. ap.adarray) (impur [Tuple int]]:
for range(1, input. [o]-1):
for in range(1, imput. shapee
if np.all (i-1: j-1:j+2] !- grey):
pasitions, appendd 1))
retura positions
def make_ped nake_neightt www.ors.ylllooiipiiitt ap.ndarray, positions: List (Tuplellin,, int]]) ap.ndarray: for position positions: input [position[(]] ppoitiioooo (0] poeition (eeitien(()-lpppettiio((133 input
yellow
def nake htt._oooggbbbrbbalaaaaaaeaeo (inputt up. adarrar positions: (Tuple (int, int]]) >> ap.ndarray:
for position in poaitions: input [po 1:position[[]] 2, [oeition[i] 1:position[[] 2] black return input
def count_yyelloo naighhors (input: up.ndarray,
List (huplaasn,,, intll) ap.ndarray:
up. 2ee (le((err)s)))
for i, position (contrat) scores(i] up. (pp.ouniinuut (positioon 1:position(0) position[1] 1:position[1] yellow)
return scores
def main(input):
centers fond_posiiional wetchout.gre__eiigee (input))
scores count_yellov. new.o_negghoor centere)
contar_yellow, black
www.mm_cccors_cettrreeeeeee center scores)
output poo_nooihhorr__yllooiege cantar_yallos)
output nake_neighbore__e (ottbbrr,,bbcccuutuuuuuu. center_black
return output
Figure 29: The compiled Python program in DARC.
300 the 400 ARC tasks were effectively decomposed and converted into Python using the ANPL, averaging 2.7 holes per task these tasks solves the test-input, but some may fail to generalize to other oututss see Appendix F.2. The DARC dataset not only houses the final solutions the ARC tasks but also encapsulates the diverse groblem-solving approaches employed by different users. Crucially, it is a dataset detailing how humans decompose abstract procedural tasks into simpler sub-tasks, and ground each task into program (e.g. Python) in collaboration with an LLM. We give an example an ANPL. program, the compiled Python program and corresponding trace Figure 27, Figure 29 and Figure 28.
33

---

The DARC dataset provides valuable window into the system's 's task completion processes. By documenting ANPL decompositions, Python code, and detailed interaction histories, it permits to gain insights into the practical application of Language Learning Models (LLMs) for programming. We hope that this dataset will useful for others seeking understand and refine similar systems.
H
Computational Resources
For our human study, LLM APIs were called 4304 times for System A (10.76 per task), and 1923 times for System B (4.81 per task). The distributions of the number of LLM API calls are presented in Figure 30. Since System A generates 10 candidates when resynthesizing, the number of API calls on several tasks exceeds forty times. For most tasks, the number of interactions in the two systems is less than twenty.
100
Number of tasks
60
20
LLM API calls of System
LLM API calls of System B
Figure 30: LLM API calls of Systems A and B.
34

---

I
Case Study
case of user interaction. Figure 31 serves illustrative instance. Initially, the user enters the ANPL code into the system, which consequently produces a function for every hole and automatically verifies the code's validity. Upon encountering a programming error, the system issues a warning to the user. In response, the user examines the input and output of the hod_ssslllesttt unit function and discovers doesn't t align with expectations. The user then adjusts natural language description, leading to ANPL successfully meeting the test input and output samples following code regeneration. Eventually, the system presents the complete code to the user, as shown the Figure 32.
Generate find smallest unit extend unit change_blut blue to red
def natn( input_grid: n
unit "find the smallest iepeating unit" (inpu((itt_grid)
out = "exlend the unit to 9x3 gundt( "change blue pixels red"(out)
return out
Type Error
Trace find und_smallest_mm unit
Input
Output (2, 2) Expected
Edit find smallest unit there is small grid repeating from top to down, find and return
ANPL Correct
Figure 31: User Interaction with System and Subsequent Code Generation Process
Difficult Tasks. From the overall 400 tasks under consideration, several tasks pose significant challenge to users because is hard or impossible find the solving logic. We present one case in Figure 33.
User-Specific Solution. The potential solution of the ARC problem is heavily reliant on the user's algorithm design, which has an impact on the difficulty of programming, For instance, in the ARC task illustrated in Figure 34, some users might attempt to identify the color pattern across each row or column. Others might note the black square's location, then rotate the grid 90 degrees and select the grid the same position as the answer. The first approach quite challenging. often too demanding to be completed within time constraint. Conversely, the latter method leverages the rotational symmetry of the grid, enabling a direct translation into the correct Python code, climinating the need for debugging.
35

---

import t numpy as up from typing import
(black, blue, red, green, yellow, grey, pink, orange, teal, narcon) rango(10)
def piap (input.grrr .p.ndarrry) +> up. .ddrray:
**.
Given nunpy arrey, function snallest repeating grid
(vidth, height) iaput_grid.ehape
for in range width+1);
if width == 0: for j in range(1, height+!): if height X - 0:
unit input_grid(:1, :j]
up. (mp. tiletunit, (width//1, hright//f) :height] input_grid): unit
input_grid
extend (unit: mp. adarray) up. :d.rrayyy
Given & 20 nunpy arrey, this function extende the arrey to 9x3 grid. (uidth, haight.) = shape if width > 9 and height >- 3: return unit[:9, :3]
else:
extended_unis unit Ep.zoroz((S,, 3), dtyperunit.deypa. for (9):
range
extended_unitll [ii jl unit(i width, X height]
return extended_unit
def chango_ blun_to_reddunit. up. ad.ndar))y)
>> mp.ndarray:
Given 20 nunpy arrey, this function changes all blue pizels to red.
unit [unit =u blue] red unit
main(tnpat_gricl np.ndarray): find_ama amallest__untt(npput out extend_ uniituuittee out change_blue, ro_ee_t_rr_tretuu ze turn out
Figure 32: The code synthesized by ANPL.
36

---

Figure 33: Unsolvable ARC task for the user.
Figure 34: Example of an ARC task demonstrating differing user strategies.
37


Reviews:
[{"review_id": "89PnqvDhcb", "reviewer": "Reviewer_NKWp", "summary": "ANPL proposes a Sketch guided program synthesis using Natural Language in an interactive fashion.The results show better interactive coding than base LLM.", "questions": "1. How do we extend the system to a general purpose program decomposition problem solving method?", "limitations": "The limitations section need considerable improvement.", "rating": 6, "confidence": 3, "soundness": 2, "presentation": 3, "contribution": 2, "strengths": "The paper shows potential in using sketch guided methods in conjunction with LM inference. It can be a good tool to use for debugging and potentially to teach programming.", "weaknesses": "Though the method show promise, some amount of work is necessary to justify the applicability of the system in wider settings. Some proof of guarantee on how the sketch helps in overall synthesis can also throw some light to the reader on why a system like this can be useful and should be adopted by wider research community. Some specific points:\n\n1. Although an interesting direction, it would have been great to see the performance of the model in general purpose programming tasks, and not only for debugging.\n\n2. The availability of only a specific syntax seem very limiting to applicability. It is not clear on how to use the system for new domains.\n\n3. Some recent works on LLM that work in conjunction with Sketch guided synthesis seem to be missing.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank you for your review comments! Your main concerns were about the generality of the programming framework and the adequacy of the references to related works.\nWe have tried our best to address your concerns by incorporating additional experiments and adding related works. Please refer to the response below for more details.\nHowever, due to the brevity of your statement, some aspects may not have been fully understood, and we kindly request you provide a more detailed and specific elaboration of your points. This will help us improve the quality of the paper.\n\n## Weaknesses\n\n> 1.Although an interesting direction, it would have been great to see the performance of the model in general purpose programming tasks, and not only for debugging.\n\nIt should be noticed that ANPL **is a general-purpose programming framework** and can be applied to various tasks since it is a superset of Python (i.e. we can achieve anything that can be done with Python using ANPL). This is also stated in the first paragraph of Section 3.\n\nTo provide more evidence of ANPL's generalizability, we conducted additional experiments related to the APPS dataset and several long programming tasks. Please see the details in the response (1) (2) (3) and the supplementary pdf of our Global Rebuttal.\nBriefly speaking, we conducted a 20 APPS tasks human study, in which ANPL achieves 100%, GPT-3.5-turbo achieves 85%, and Parsel achieves 55%. This shows the advantage of ANPL in general typical programming tasks.\nAlso, we implemented several realistic and long projects including text editor, robot controller, naive MAGIC card game, and LS-8 CPU, which shows the generalizability of ANPL.\n\nWe should clarify that ANPL is designed to grounding user intent to code through interaction which is different from code generation but also an important direction for LLM programming assistants because it is hard for LLMs and other code generation techniques to understand the user intent and generate correct code in 1-shot .\n\nIt would be most helpful for us if you can elaborate on what you mean by \"not only for debugging\". If you can give us a few example tasks you have in mind, we'll be able to address your concerns better.\n\n> 2.The availability of only a specific syntax seem very limiting to applicability. It is not clear on how to use the system for new domains.\n\nANPL is a general-purpose programming framework. Perhaps there was a misunderstanding caused by our experiments on the ARC dataset, as the input-output format for that task is similar (specific syntax). However, ANPL can be used to address any programming-related problems with Python. To demonstrate this, we have included additional experiments on the APPS dataset and conducted extensive experiments on long program development using ANPL (please refer to the experiments mentioned in the previous question and Global Rebuttal (1-3)).\n\nIn addition, if we have any misunderstandings about the issue, please respond to us promptly, and we will provide the corresponding responses.\n\n> 3.Some recent works on LLM that work in conjunction with Sketch guided synthesis seem to be missing.\n\nThanks for your reminder. We planned to add the following sketch-guided references to the related work section:\n\n[1] Self-planning Code Generation with Large Language Models\n\n[2] SKCODER: A Sketch-based Approach for Automatic Code Generation\n\n[3] Representing partial programs with blended abstract semantics\n\nAmong them, [1] proposes to generate code with the planning phase and implementation phase, where LLM outputs solution steps in the planning phase and then generates the code step by step in the implementation phase. [2] retrieves similar code snippets from a codebase and then extracts the relevant code sketch to guide the following synthesis process. [3] represents unfinished code with the help of \"hole\" and approximates its semantics using neural networks to guide the synthesis by execution.\n\nDifferent from them, our work focuses on incorporating user interaction within the process of code generation by introducing a natural language programming framework, which allows users to program and debug to clarify their intent progressively. Although they have also employed the concepts of \"sketch\" and \"hole\", the specific definitions are different. In our work, the \"sketch\" represents the control/data flow written by users while the \"hole\" represents natural language. In theirs, for example, the \"sketch\" in [1] represents the high-level natural language plan, the \"sketch\" in [2] represents the relevant part of the retrieved code, and the \"hole\" in [3] represents unfinished code.\n\nAlso, it would be helpful if you can point us to a few specific ones you have in mind for us to make a comparison.\n\n## Questions\n\n> 1.How do we extend the system to a general purpose program decomposition problem solving method?\n\nAs mentioned above, ANPL is already a general-purpose programming framework and can be applied to various tasks since it is a superset of Python. We have conducted an additional human study on APPS dataset and we have implemented several representative long programming tasks to show ANPL's potential in real-world applications (see Global Rebuttal (1-3)). One way to extend ANPL is to let LLM generate high-level plans with ANPL automatically, which can be seen as a kind of new prompting technique by prompting with control/data flows instead of purely natural language. We take it as our future work.\n\nWe hope the rebuttal is adequate in addressing some of your concerns, and if so, please update your review in accordance."}, {"review_id": "3brbB0dblz", "reviewer": "Reviewer_neh7", "summary": "The paper proposes ANLP, a framework that interactively gets the definition of the data flow of a program from user input, and then fill the \"holes\" in the sketched program using LLMs. The authors conducted comprehensive human experiments on the Abstraction and Reasoning Corpus by letting human subjects solve the problems using an off-the-shelf language model and the ANPL-wrapper language model. The results show that with ANLP people are better at solving ARC problems.", "questions": "1. Does ANPL work well for complicated data flows and longer programs?\n2. Does ANPL work for real world applications at larger scales?", "limitations": "The authors have addressed the limitations.", "rating": 6, "confidence": 4, "soundness": 2, "presentation": 2, "contribution": 2, "strengths": "1. Splitting the burden of reasoning between human programmers and language models is reasonable. Humans can focus on higher-level planning and leave the implementation details to language models.\n2. The evaluation with human subjects is convincing. In terms of solving rate and efficiency, it's clear that ANPL is easier to use than bare ChatGPT.\n3. Letting users define the dataflow in a python-like language is friendly for programmers and easy for the model to understand.", "weaknesses": "1. The idea of decomposing a task into modular functions is not new. As the authors have mentioned, even under the LLM setting it's been used by Parsel (https://arxiv.org/pdf/2212.10561.pdf). Even though the authors emphasizes the novelty of human interaction, I don't find your system significantly different from theirs. Of course your human evaluation is much more comprehensive.\n2. Evaluating on ARC alone seems not enough. While the tasks seem good for testing the reasoning ability, it is not clear whether ANPL can work for real-world applications that help actual programmers. The definition of data flow can get complicated and harder for the model to understand as the program gets longer.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your review comments! Your concerns were about the differences between ANPL and other similar work like Parsel, as well as the applicability of ANPL to a broader range of complicated real-world tasks. For the former, we have provided a detailed explanation and examples in our response. As for the latter, we have conducted an additional experiment on APPS, where ANPL achieves 100%, GPT-3.5-turbo achieves 85%, and Parsel achieves 55%. Please refer to the detailed responses below and the Global Rebuttal for more information.\n\n## Weaknesses\n\n> 1.The difference from Parsel.\n\nUnlike Parsel which generates an implementation in Python from the problem description in 1-shot. ANPL allows the user to gradually clarify their intents through interactions. This enables the final code to converge gradually towards the correct direction.\nSpecifically, compared with Parsel, we have the following distinctions:\n\n1. **Control/data flows**. ANPL enables users to define explicit control/data flow and control flow while Parsel cannot due to the ambiguity in natural language (which indicates that our compiler design is entirely different). For example, we cannot extract the explicit data flow from the following Parsel code (randomly selected from the Parsel paper) because `tokens` is not defined as variables and we do not know the relationship between the three `tokens`:\n\n    ``` Python\n    tokenize(s): Convert a string into a list of tokens, including parens.\n    ... (omitted I/Os)\n    read_from_tokens(tokens): Translate tokens to their corresponding atoms, using parentheses for nesting lists.\n    ... (omitted I/Os)\n    ```\n    The natural language-defined control flow relies on LLM's code generation capabilities and thus its complexity is severely restricted. This makes Parsel challenging to extend to real-world applications with complicated control/data flows.\n    In comparison, ANPL allows users to define control/data flows either implicitly in natural language or explicitly in code, which is more flexible and can be applied to more complicated tasks.\n\n2. **The debugging process**. Parsel faces difficulty in pinpointing bugs and modifying specific subfunctions due to the need for regenerating a whole new executable program for each change. ANPL, on the other hand, excels in precise adjustments without altering user-validated code. Debugging with LLMs, as discussed in Section 4, is complex due to unpredictable behavior, and resolving this hinges on ANPL's compiler implementation.\n\nA small experimental comparison between ANPL and Parsel can be found in the Global Rebuttal (1) (2), where for 20 APPS-interview tasks human study, ANPL achieves 100%, GPT-3.5-turbo achieves 85%, and Parsel can only achieve 55% because it is not designed for human interaction. In fact, whether in terms of design concepts or programming interfaces, ANPL and Parsel are not similar to each other. We suspect that the \"resemblance\" may arise because about 80% of both ANPL and Parsel codes are composed of natural language and function signatures which are the common parts among different natural language programming frameworks. A better approach to discerning the differences between the two is to compare their compiler algorithms. We will revise our paper to make this clearer.\n\n> 2.Evaluating on ARC alone seems not enough. ... The data flow can get complicated and harder for the model to understand as the program gets longer.\n\nExperimentally, we have conducted additional experiments on the APPS dataset and several long programming tasks to demonstrate ANPL's potential in real-world applications (with the longest programming consisting of 306 lines of Python). Details are shown in the Global Rebuttal (1) (2) (3). Also, we explained the choice of ARC in the Global Rebuttal (4).\nBriefly speaking, ANPL consistently outperforms baselines on the APPS experiment and can generalize to real-world applications like text editor, robot controller, naive MAGIC card game, and LS-8 CPU. We choose ARC because (a) ARC is much more difficult than MBPP and HumanEval and (b) what we are measuring is the system's ability to convey the user's intent through interaction, not the system's ability to solve problems on its own (e.g. the user has a correct algorithmic solution in mind, but it is tedious to realize it in Python).\n\nTheoretically, the complicated data flow does not make it difficult for the model to understand because the ANPL compiler parses data flow using parsing algorithms leveraging ASTs directly rather than relying on LLMs to generate the right code, which means that the data flow never needs to be \"understood\" by LLMs. This makes the (de)composition process much more stable, controllable, and extendable.\n\n## Questions\n\n> 1.Does ANPL work well for complicated data flows and longer programs?\n\nYes, it does. As stated in weakness 2, the complexity of the data control flow does not affect the compilation effectiveness of ANPL. In fact, the programs in ARC are already long compared with other datasets: The (min, max, mean) of lines of ARC's (passed) program is (4, 113, 26.47) while MBPP is (2, 50, 6.71), HumanEval is (2, 32, 7.78), and APPS is (1, 297, 19.95).\n\nAdditionally, we have presented ANPL examples of programming tasks with complex control/data flows (Global Rebuttal (3) and Figure 2 in the pdf), all of which could be compiled and executed. The longest compiled Python code among them has 306 lines of Python code.\n\n> 2.Does ANPL work for real world applications?\n\nAs mentioned above, we have conducted an additional human study on APPS dataset and we have implemented several representative long programming tasks to show ANPL's potential in real-world applications. However, we also acknowledge that ANPL, as a newly emerged programming framework, is fragile, so its development requires collective efforts from the community.\n\nWe hope the rebuttal addresses some of your concerns. If so, please update your review in accordance.\n"}, {"review_id": "LsMZiKQzOH", "reviewer": "Reviewer_tgZy", "summary": "This paper proposes ANPL, a programming system for user interaction with an LLM for code generation. The main idea is to have the user generate high-level dataflow and program structure, while directing the LLM to fill in the \"holes.\" They present results of a user study of ANPL, where users are asked to write programs to solve ARC tasks, and show that ANPL outperforms a baseline of (undirected) user interaction with GPT-3.5 via ChatGPT, and one-shot program synthesis using ANPL and GPT-3.5. ", "questions": "Can you provide results for users aggregated by the language model code generation experience?\n\nThe performance of System B appears to saturate very quickly. This could be due to a degradation in performance of System B over time, for instance, as the context grows too long. Were the contexts for the LLMs reset at any point for either ANPL or System B?", "limitations": "Yes", "rating": 5, "confidence": 3, "soundness": 4, "presentation": 4, "contribution": 2, "strengths": "This paper presents a novel method of incorporating LLMs into a programming workflow. A major strength is the design of ANPL. Though the idea of decoupling a synthesis problem into a hole and a sketch is not new in program synthesis (or even neural program synthesis [1]), the application (and execution) here for an LLM-driven coding assistant seems novel and natural.\n\nThe user study is also significant, and contains a lot of great analysis.\n\nThe writing is also very clear.\n\n[1] Nye, Maxwell, et al. \"Representing Partial Programs with Blended Abstract Semantics.\" International Conference on Learning Representations. 2020.", "weaknesses": "My major concern is that the main contributions are (1) a programming system and (2) its evaluation. There is not much novelty on LLMs or even neural program synthesis.\n\nSome additional points about the design of the user study:\n- Most users in the user study were unfamiliar with code generation using LLMs (Figure 5 in the appendix), and only 1 prompt was provided as example (Figure 10 in the appendix). Therefore, it's not clear how much the difference in performance is due to inexperienced users of System B. For instance, the design of the study could have provided both the ANPL prompt (Figure 4 in the appendix) to the users as well, or given them some basic training first.\n- ARC is designed as a test of human intelligence, so the performance of a human + ANPL on ARC doesn't directly translate into performance on writing programs. Ideally the results would have included an additional dataset designed for synthesis (such as MBPP or HumanEval).", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your review! Your concerns mainly involve some questions about the experimental setup. In response to this, we have provided comprehensive explanations and conducted an additional experiment on APPS and complicated programs. The results show that ANPL still outperforms baselines and can generalize to broader domains. Please refer to the detailed responses below and the Global Rebuttal for more information.\n\n## Weaknesses\n\n> Most users in the user study were unfamiliar with code generation using LLMs... Therefore, it's not clear how much the difference in performance is due to inexperienced users of System B. For instance, the design of the study could have provided the ANPL prompt (Figure 4 in the appendix) to the users as well, or given them some basic training first.\n\nAlthough some users are unfamiliar with System B, they are equally unfamiliar with System A. We believe that a quick learning curve is also one of the advantages of System A.\n\nIn fact, before commencing the formal testing, we allowed them to play with the two systems. Furthermore, compared with related works (like Parsel), the two prompts mentioned in the problem are quite straightforward: System A's prompt merely asks the LLM to fill in the hole based on natural language, while System B's prompt provides users with a task format reference. Thus, the prompt plays a minimal role in the performance gap between the two systems. See the results on the relationship between user experience and performance below in Question 1.\n\n> ARC is designed as a test of human intelligence... Ideally the results would have included an additional dataset designed for synthesis (such as MBPP or HumanEval)\n\nWe should clarify that what we are measuring is the system's ability to convey the user's intent through interaction, not the system's ability to solve problems on its own (e.g. the user has a correct algorithmic solution in mind, but it is tedious to realize it in Python). In this regard, ARC's features, which are easy for humans to understand and solve but difficult to express via programming, would be more suitable.\nDatasets such as HumanEval and MBPP are much simpler in comparison to ARC, with many questions solvable using just a few lines of Python code (the average line of code of MBPP, HumanEval, APPS, and ARC are 6.71, 7.78, 19.95, and 26.47 respectively).\n\nTo show ANPL's generalization ability, we conducted an additional experiment on the APPS dataset and tested the capabilities of ANPL in implementing long programs. The results show that ANPL outperforms the original GPT-3.5-turbo and Parsel on APPS and can be applied to real-world applications with complicated control/data flows and long programs including text editor, robot controller, naive MAGIC card game, and LS-8 CPU. Specifically, for 20 APPS-interview tasks in human study, ANPL achieves 100%, GPT-3.5-turbo achieves 85%, and Parsel achieves 55%. More details are shown in the Global Rebuttal (1) (2) (3). Also, we explained the choice of ARC in the Global Rebuttal (4).\n\n## Questions\n\n> ..results for users aggregated by the language model code generation experience?\n\nIt is no longer feasible to find another group of users with rich experience in LLM code generation, but from the perspective of usage experience and problem-solving rate, we get the following table.\n\n| LLM code generation experience | System A | System B | System C | System D  |\n|--------------------------------|----------|----------|----------|-----------|\n|1|68.52%|63.08%|24.87%|17.90%|\n|2|71.57%|53.77%|21.49%|19.22%|\n|3|84.39%|51.82%|40.35%|21.49%|\n|4|63.64%|50.38%|13.04%|0.00%|\n|5|80.65%|45.16%|11.43%|14.29%|\n\nIt is shown that there is no significant relationship between the user's LLM code generation experience and solving rate. Sometimes, users with an experience level of 1 can achieve higher accuracy compared to those with an experience level of 5. Therefore, user experience does not significantly influence the final accuracy. Additionally, we conducted a comprehensive 440-hour human study, which, to the best of our knowledge, is exceedingly thorough and the most intricate human study experiment within the field related to LLMs. Taking all these factors into consideration, we believe that this experiment is reliable.\n\n> The performance of System B appears to saturate very quickly. ... Were the contexts for the LLMs reset at any point for either ANPL or System B?\n\nThe performance of System B saturates very quickly because it is difficult for LLMs to understand the user intent through chat. LLMs cannot accurately identify where the understanding gap between itself and the user arises. And this is precisely the significance of ANPL - ANPL allows users to interact effectively with LLM in a manner similar to debugging, ensuring that the user intent is almost always understood by LLM as the interaction progresses. Therefore, ANPL's performance improves continuously as user interactions go on.\n\nIn fact, in the experiment, users were free to delete or modify their chat content and they can even write an ANPL program and then \"compile\" it by hand when using System B. In doing so, we ensured that the comparative experiment between System A and B was fair. We will revise the paper to make this clearer.\n\nWe hope the rebuttal is adequate in addressing some of your concerns, and if so, please update your review in accordance."}, {"review_id": "n8sW51MHcI", "reviewer": "Reviewer_ecZq", "summary": "In this paper, the authors introduce Abstracted Natural Programming Language (ANPL), a programming language and system to improve Large Language Model (LLM) assisted programming. ANPL programs are structured in a top-down manner; a top level program called the \"sketch\" solves the task by specifying the data-flow between multiple secondary level sub-functions called \"holes\". Each \"hole\" encapsulates a textual description of its targeted functionality. This ANPL program is then translated into a conventional python program via the ANPL compiler, which uses LLMs to implement the \"holes\".  Further, to help debug the generated/compiled program, the system provides features such as exposing execution traces and intelligently merging novel user edits to hole descriptions. Human study shows that compared to using LLMs naively, ANPL helps users solve programming tasks faster and with higher success rate. Finally, the paper also contributes a dataset of textual decomposition (by humans) of 300/400 reasoning tasks in the ARC benchmark, which can provide insights into how humans decompose programming tasks.", "questions": "I thank the authors for providing an extensive appendix which answers many of the questions I had. However, a few more are as follows:\n\n1) How often do users get the \"sketch\" wrong - are there some cases where the failure is due to wrong sketch while the hole implementations are correct? \n\n2) Can the authors briefly talk about the learning curve of using ANPL? \n\n3) Can the authors justify the choice for using train-fail-test-success as successful programs while measuring success rate?\n\n\n", "limitations": "The authors have adequately addressed the limitations and potential negative societal impact of their work.", "rating": 7, "confidence": 4, "soundness": 3, "presentation": 2, "contribution": 2, "strengths": "### Originality\nThe idea of improving programming by decomposing the program into sketches and holes in itself is not a novel idea (the authors properly cite previous works along this direction). However, structuring a LLM-augmented programming interface around this system is indeed novel.  \n\n### Quality\nThe paper is well written. Further, it presents insightful experiments and ablations in the main paper as well as the extended appendix.\n\n### Significance\nThis paper targets the fastly-evolving direction of LLM assisted programming, and hence will be of interest to the research community at large. While \"sketch-hole decompostion\" is commonly used in LLM assisted programming, this paper provides a thorough human study to firmly establish the benefits of such an approach. \n", "weaknesses": "While overall I believe its a well written paper, there are certain weaknesses with the presentation and the experiments section.\n\n### Presentation / Clarity\n\n1) The main paper does not clearly show *what* an ANPL program looks like - what is the input to the LLM?. The main paper only refers to Figure 1 which shows an ANPL program pictorially. While the ANPL compiler (written in ANPL) is in the paper, I believe it would be easier to understand the system with a clearer and explicit presentation of what a \"sketch\" is and what a \"hole\" is programmatically.\n\n2) The main paper does not discuss the actual interface that the user uses (only shown in the appendix). As this is a crucial contribution of a \"programming\" system, I think it should also be shown in the main paper.\n\n3) In general, the paper entangles a methodology contribution (using a sketch-hole paradigm for LLM assisted programming) with a system contribution (The interface, debugging features, merging features, test-case creation tools). \n\n### Experiments \n\n1) The interface seem to have additional features such as grid editor to create test cases etc. which may contribute to the user success. This make it harder the discern what parts of ANPL are essential. \n\n2) An important baseline missing is users directly programming in python. On roughly 30% of the tasks, even with ANPL users take ~15 mins. Looking at the ARC challenge examples, I think directly programming in python may be faster than programming with ANPL (or the other baselines). \n\n3) Program solutions which satisfy test cases but fail for train cases are counted as \"successful\" while measuring the success rate.  (Refer Table 2 appendix and results in the main paper).  If we count only the cases where both test and train cases are successful, the performance drops to 56.7% for ANPL versus 48.5% for naive LLM usage, which is significantly lower than the numbers used in the main paper. I think that successful programs should satisfy both train and test cases.\n\n### Others\n\n1) Many real world programming tasks are unlike the problems in ARC. Hence, its unclear if ANPL would be better than naive LLM systems in typical programming use-cases as well.\n\n2) Another drawback of using ARC is that many tasks may involve sub-functions which are similar. Therefore users may benefit from know \"what prompts works better\" for certain sub-functions, and use them directly in future prompts (sort of saving the previously discovered functions). Therefore, a task benchmark where the tasks were more diverse might have been more suitable. \n\n3) As GPT-4 seems to be much more performant than GPT-3.5 (used in the experiments) I wonder if the gap between ANPL and naive LLM usage is further decreased when larger LLMs are used. \n\n \n\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thanks for your review comments! We provide detailed responses to all of your concerns. We'll revise our paper to make your concerns clear. We have a space limit so please let us know of any additional comments.\n## Weaknesses\n### Presentation\nThanks for the suggestions and we'll revise the paper.\nHowever, we want to clarify that our main contribution is clear: designing the programming system to address the inability of existing LLMs that hardly clarify a user's intent precisely when a misunderstanding arises. Techniques like sketch-hole, merging, etc. are key aspects of making such a system.\n### Experiments\n> 1.The interface seem to have additional features such as grid editor... make it harder the discern what parts of ANPL are essential.\n\nSorry for the misunderstanding. The grid editor is provided for both System A and B. It is just a tool to improve the user experience. The comparison between the two systems is absolutely fair.\n> 2.... directly programming may be faster than programming with ANPL.\n\nIn fact, Python and ANPL are fully compatible as mentioned in Sec. 3. The reason for the time cost on simple tasks is that during programming, much time is spent waiting for GPT's response. The average waiting time is 14.6% for System A and 23.5% for System B. Besides, the users were instructed to solve the tasks as fast as possible and they choose not to program directly when using System A because it would require more effort.\n\nIt is impossible to recruit the same users for Python experiments, but we can demonstrate the user effort in ANPL and Python as the lines of code: the [min, max, mean] of lines of ANPL is [2, 76, 10.29] while the one of Python is [4, 113, 26.47], and note that writing natural language is simpler than coding.\nWe also demo the ANPL's application on projects including MAGIC card game and LS-8 CPU with 67% lines of code reduction, see Global Rebuttal (3). \n> 3.The standard of \"successful\"...\n\nOur experiment assesses the system's capacity to fulfill user intents rather than users' ability to design generalizable algorithms. User intent is defined as writing a program to pass the provided I/Os. Thus, we present the solving rate of test I/O in the main paper. Although it is a simplified setting, it is appropriate and sufficient taking into account the 440 man-hours invested already.\n\nHowever, we understand that readers may be interested in other information related to ARC itself, such as whether the Python code can be used to generate I/Os or whether DARC can provide insights into human decomposition strategies. Thus, we included the accuracy of all I/Os in the appendix as an addition.\n### Others\n> 1....if ANPL would be better in typical programming use-case.\n\nWe have conducted additional experiments on the APPS dataset and implemented several representative long programming tasks to show ANPL's generalization ability. The results show that ANPL outperforms baselines consistently. Please refer to Global Rebuttal (1) (2) (3) for more details.\n\nIn addition, using ARC as a programming task is actually appropriate.\nWhat we are measuring is the system's ability to convey the user's intent through interaction, not the system's ability to solve problems on its own. In this regard, ARC's features, which are easy for humans to understand and solve but difficult to express via programming, would be suitable. Refer to Global Rebuttal (4) for more details.\n> 2.... the drawback of ARC is users may benefit from knowing \"what prompts work better\" for certain sub-functions...\n\nAs mentioned above, we have provided additional experiments on the APPS dataset to show ANPL's advantage (Global Rebuttal (1)).\n\nHowever, this concern might be a misunderstanding because\n(a) ARC already encompasses a large diversity of concepts based on its design principle [1] and is more complicated than datasets such as HumanEval and MBPP (Global Rebuttal (4)). In fact, even competition datasets involve repetitive algorithmic codes, such as BFS, DFS, DP, etc.\n(b) Users can do exactly the same thing with GPT so it won't have any impact on the comparison between the two methods.\n\nActually, this is a very interesting problem i.e. \"library learning with ANPL/prompt\", which is discussed in the paper's future work.\n\n[1] On the Measure of Intelligence\n> 3.... if the gap between ANPL and naive LLM usage is further decreased when larger LLMs are used.\n\nDuring the experiment, we didn't have access to the GPT-4 API and it is impossible to conduct another large-scale human study for GPT-4 now. However, we can measure the solving rate w/o the interaction of ANPL+GPT-4 (System C) and GPT-4 (System D) with existing data:\n|LLM|System C|System D|\n|-|-|-|\n|GPT-3.5-turbo|23.5%|16.75%|\n|GPT-4| 30.5%|23.5%|\n\nWe can conclude that (a) although a more advanced LLM would achieve higher accuracy, the utilization of ANPL always results in an improvement.\n(b) ARC still remains difficult for GPT-4 to give a 1-shot answer, making intent clarification a persistent challenge in using LLMs as programming assistants.\n\n## Questions\n> 1.How often do users get the \"sketch\" wrong...\n\nDetermining when a situation belongs to \"writing a wrong sketch\" is difficult. Instead, we quantify the frequency of users modifying the main function, which encompasses cases of writing a wrong sketch. We find that in 45.67% of successful tasks, users have modified the main function but finally they got the right code, showing that users often make mistakes when coding but the mistakes can usually be corrected through interaction.\n> 2.... learning curve of using ANPL?\n\nThe learning curve of ANPL is shown below.\n|time stamp|1|2|3|4|5|6|7|\n|-|-|-|-|-|-|-|-|\n|solving rate|80.11%|77.30%|77.22%|84.58%|71.13%|57.78%|70.83%|\n\nWe conclude that there is no significant learning curve. This might be due to substantial variations in difficulty across different tasks.\n> 3....why using train-fail-test-success as success?\n\nPlease refer to Weaknesses-experiments-3 provided above."}]

Author rebuttal:
We thank the reviewers and ACs for their time and effort. 

We are glad the reviewers acknowledge the following contributions:novel and reasonable for proposing a LLM programming system by introducing extensive (i.e. non 1-shot)user interactions(neh7, tgZy, ecZq); comprehensive human study and strong empirical results (neh7, tgZy, ecZq), and clear presentations (tgZy).

In this response, we will summarize and address the important concerns raised:

(1) The generalization ability of ANPL to different domains.

(2) Comparison of ANPL against Parsel (https://arxiv.org/pdf/2212.10561.pdf), a non-interactive LLM-backed compiler that also compiles natural language to code.

(3) Can ANPL compile "realistic" and "long" programs effectively?

(4) Why did we choose ARC as our benchmark?

(5) A minor misunderstanding on the "sketches and holes" program synthesis paradigm.
### (1) The generalization ability of ANPL and (2) Comparison against Parsel

We conduct a small study with 4 participants and 20 randomly selected APPS-interview problems. Other domains considered were MBPP, HumanEval, and APPS-competition problems. We did not choose MBPP and HumanEval because they are much simpler compared with ARC, with many questions solvable using just a few lines of Python code (The [min, max, mean] of lines of ARC's (passed) program is [4, 113, 26.47] while MBPP is [2, 50, 6.71], HumanEval is [2, 32, 7.78]). Also, we did not test on competition-level tasks limited by user ability. Each participant was instructed to solve each problem with three systems (ANPL, GPT-3.5-turbo, and Parsel) appearing in a random order for a total of 30 minutes per system. We replicated Parsel with GPT-3.5-turbo because Codex is no longer available.

As shown in supplemented pdf Figure 1:

(a) ANPL outperforms the original GPT-3.5-turbo and Parsel in final solving rate and solving time which is consistent with the result on ARC. Specifically, ANPL achieves 100% solving rate, GPT-3.5-turbo achieves 85%, and Parsel achieves 55%. Also, the 1-shot performance (without interaction) of them is 30%, 0%, and 15% respectively.

(b) The solving rate for APPS-interview is higher than the one on ARC, indicating APPS-interview is easier than ARC for human interaction. In fact, the challenge of APPS lies in how users solve the tasks rather than grounding users' intents to code.

(c) Parsel performs the worst because Parsel and ANPL have different design objectives: ANPL is designed to grounding user intent to code through interaction while Parsel is designed for automatic reasoning without human intervention. Specifically, Parsel does not even retain the context of past interactions. This leaves the only method for "debugging" is to continuously modify the initial Parsel code and provide more I/Os until it can be compiled to Python in a single attempt.

Overall, we conclude that
(a) ANPL is generalizable to different domains and
(b)
ANPL and Parsel are substantially different systems: ANPL is designed as an interactive programming system to significantly reduce programming complexity and assure code quality, where the users can iteratively interact with the system to safely ground their minds to code; While Parsel is primarily a reasoning system, where the programming task is given to it "as is" and it leverages the capabilities of LLM to decompose and ground it to code without any user interventions.
### (3) Can ANPL compile "realistic" and "long" programs effectively?

To further show the ANPL's generalization ability, we conduct a qualitative study by using ANPL to compile several projects drawn from CS courses and GitHub: text editor, robot control, naive MAGIC card game, and LS-8 CPU. These tasks are the prototypes of realistic applications and are representative in terms of the program form with complex control flows and many sub-functions. They are much longer (198 lines of code on average) than existing program synthesis benchmarks (MBPP[6.71], HumanEval[7.78], APPS[19.95])

It is shown in pdf Figure 2 that ANPL can be used to implement these applications with much less coding effort (with 33.21% lines of code) and obviously lower programming barrier (by using natural language) than Python. Also, the current system including GPT-4 and Parsel cannot solve these problems easily in our test. Such results show that ANPL has the potential to be adopted in real scenarios with great superiority of lower programming complexity and better code quality assurance.
### (4) Why did we choose ARC as our benchmark?

We clarify that what we are measuring is the system's ability to convey the user's intent through interaction, not the system's ability to solve problems on its own (e.g. the user has a correct algorithmic solution in mind, but it is tedious to realize it in Python). In this regard, ARC's features (easy for humans to understand and solve but difficult to express via programming) would be more suitable than typical programming datasets such as MBPP and HumanEval.

We find that typical programming datasets are simpler for programming compared with ARC. The average line of code of MBPP, HumanEval, APPS, and ARC are 6.71, 7.78, 19.95, and 26.47 respectively.
Competition datasets like APPS challenge the users to solve the tasks rather than how to generate code that fulfills users' intents.

### (5) A minor misunderstanding of the "sketches and holes" program synthesis paradigm.

Sketches + holes is a classical program synthesis paradigm and we are in no way claiming that as a contribution. We merely leverage it as a way of explaining our work in a language familiar to the community.  We will make this point clearer in our draft.
We will make this point clearer in our draft.

We hope our responses have convincingly addressed all reviewer's concerns by conducting supplementary experiments and giving detailed explanations. Please do not hesitate to let us know of any additional comments.

Meta-review: This submission presents ANLP, a programming system that mediates between a user and a backend LLM through a sketching approach. Rather than focusing on generating programs in a single step, this system aims to help users express high-level ideas as executable code. A user interface helps users to sketch a high-level data flow with holes, where each hole is annotated with a natural language description. Initial solutions can be tuned by inspecting the inputs and output of each hole individually, allowing for example to specify IO constraints for each hole.

Reviewers agree that the proposed method is useful to help users program, especially for debugging or teaching purposes, and that it improves over directly using an LLM.

However, reviewers also raised the issue of a somewhat confusing presentation: many misunderstandings arose from the writing and required clarification during the rebuttal phase, though these mainly require smaller changes to the text. A bigger issue is that even though the programming system is the core contribution, its user interface is only discussed in the supplement at this time. I would encourage the authors to think about how to make it easier for readers to understand what the user interface actually looks like (e.g., what is the first thing a user sees when trying to solve a new problem).

The fact that the utility of the system was evaluated using a substantial user study was appreciated by reviewers, but questions remained on the chosen dataset (the Abstraction and Reasoning Corpus). During the rebuttal phase, the authors provided additional experiments on the more standard APPS dataset, involving longer programs. I will note that personally, I believe that the problem decomposition dataset obtained during the user study (DARC) is a particularly important contribution.

Overall, I agree with the reviewers that this is an interesting paper that deserves presentation at NeurIPS.
Decision: Accept (poster)