Building Community Driven Libraries
of Natural Programs

Leonardo Hernandez Cano * 1 Yewen Pu * 2 Robert Hawkins 3 Josh Tenenbaum 4 Armando Solar-Lezama 1

Abstract

the task. With the advancement of Large Language Models(LLMs), recent works have increasingly leveraged programmatic representations of policies (Liang et al., 2022; Volumet al., 2022) and planning (Huang et al., 2022; 2023; Silver et al., 2022), to take the advantage of LLMs’ ability
to connect programs to natural language intents. Under
these formulations, a human instructs the agent throughprogramming, either directly or with natural language, andthe agent executes the program by producing a sequenceof appropriate actions. Compared to learning from demonstrations, end-to-end RL, and trajectory optimizations, programmatic learning is more generalizable (Inala et al., 2020;
Trivedi et al., 2021) and user-interaction efficient(Bunel
et al., 2018).

A typical way in which a machine acquires knowledge from humans is through programs – sequences of executable commands that can be composed hierarchically. By building a library of
programs, a machine can quickly learn how to
perform complex tasks. However, as programs
are typically created for specific situations, they
become brittle when the contexts change, making
it difficult compound knowledge learned from different teachers and contexts. We present natural
programming, a library building procedure where
each program is represented as a search problem containing both a goal and linguistic hints
on how to decompose it into sub-goals. A natural program is executed via search in a mannerof hierarchical planning and guided by a large
language model, effectively adapting learned programs to new contexts. After each successful execution, natural programming learns by improving
search, rather than memorizing the solution sequence of commands. Simulated studies and a human experiment (n=360) on a simple crafting environment demonstrate that natural programming
can robustly compose programs learned from different users and contexts, solving more complex
tasks when compared to baselines that maintainlibraries of command sequences.

A key tenant of a well learned skill is its robustness in theface of changing contexts. For instances: An agent operating
a robot in different environments (Mesesan et al., 2019; Linet al., 2019); A controller directing traffic in different hoursof the day(Padakandla, 2021); A software operating under
different dependencies(Garlan et al., 2009). As programs
are explicit sequences of commands, they are brittle when
the context changes. This brittleness accumulates in higher
level programs, as failure in any sub-program results in total
failure. As people tend to give context-specific instructions(Sumers et al., 2022; Bonawitz et al., 2011) (i.e. “hardcoding a program” (Brown et al., 1998)), it is difficult tocompound programmatic knowledge learned from different
teachers and contexts (Garlan et al., 2009; Chaturvedi, 2019;
Taylor, 2010; AlOmar et al., 2020).
On the other hand, humans readily generalize skills learned
from different teachers and contexts. Recent works studying human to human instruction generation (Tessler et al.,2021a; Acquaviva et al., 2021; McCarthy et al., 2021b)
reveal that instead of giving overtly detailed procedures, humans successfully “program” each other by providing goals
and guidelines: The goal constraints the intended outcome;The guidelines increases the chances of the listener finding
a solution. Work in situated actions (Suchman & Suchman,2007) suggests that humans accomplish a task not by following an exact plan, but by improvising to adapt to the context
at hand. Drawing inspirations from these concepts, we
present Natural Programming (NP), a novel programming

1. Introduction
By compounding knowledge learned from different teachers,
a student can solve increasingly complex tasks. A typicalway which computers acquire knowledge from humans isthrough programming – explicit instructions on how to do*
1
Equal contribution
CSAIL, MIT, USA 2 Autodesk
Department of Psychology, UW-Madison, USA 4 Department
of Brain and Cognitive Sciences, MIT, USA. Correspondence
to: Leonardo Hernandez Cano <leohc@mit.edu>, Yewen Pu<yewen.pu@autodesk.com>.
3

Interactive Learning with Implicit Human Feedback Workshop at
ICML 2023

1

Building Community Driven Libraries of Natural Programs

Figure 1: An overview of Natural Programming in three generations on the CraftLite environment, with different users
and contexts. The crafting rule for a stick vary across generations, in the first generation, one needs to use a wood anda plank, while in the second and third generations, one need to use just the wood. At each generation (green, blue, red),the user programs the robot using a search problem, and the robot solves it via search, and builds a library of natural
programs – mappings from search problems to sequences of other search problems. In the third generation, the robot isable to compose the rope program (learned from the first user) with the alternative stick program (learned from the seconduser) to craft a bow.
system that interacts with an user using search problems –consisting of a machine-interpretable goal1 and a natural
language hint. Given a search problem, NP searches fora solution in the style of hierarchical planning (Kaelbling& Lozano-Pérez, 2011; Konidaris et al., 2018; Silver et al.,2021b; Devin et al., 2017), guided by the linguistic hintusing a LLM. By keeping a library of search problems, NP
allows itself to search for new solutions in different situations, while still benefiting from past knowledge gained
elsewhere.

baselines on both simulation and a large scale user study(n=360, type=crowd-workers, total time=90 hours) demonstrates that NP learns best from different users and contexts
2.

2. Related Works
We are concerned with the problem of creating a system thatcan learn from different teachers and contexts through programming. Programmatic policies, RL under non-stationary
environments, and library learning are key aspects of ourwork. We highlight literature in these different areas toprovide contexts for our own work, which lies in the intersection of these fields.

This work makes the following contributions:
Formalism – Formalizing the problem of Generational Programming under changing Contexts (GPC) to study how tocreate a programmatic system that can learn from different
teachers and contexts.

Programs as Policies and Planners Programs are a staple representation for robot policies. Compared to end-toend policies, programmatic policies (Andreas et al., 2017;
Yang et al., 2021) are more generalizable (Inala et al., 2020;
Trivedi et al., 2021), interpretable (Zhan et al., 2020; Bastani
et al., 2018), and easier for humans to communicate (Bunel
et al., 2018). Likewise, it is customary for planners (Shiarlis

System – Developing the Natural Programming (NP) system, a novel programming system that maintains a libraryof search problems to tackle the GPC problem.
Evaluation – Developing CraftLite, a simple yet fully
fledged programming environment to study the GPC problem at scale. Evaluation of our system against realistic
1

2
We will open source the CraftLite environment and all
the collected user-interaction dataset as welle.g. input-output examples, assertions, constraints

2Building Community Driven Libraries of Natural Programsand the every dynamics t ∈ T deterministic.

et al., 2018; Konidaris et al., 2018; Silver et al., 2021a) toadopt a programmatic representation. With the advancement of LLMs, recent works have increasingly embraced aprogrammatic representation in policy (Liang et al., 2022;
Volum et al., 2022) and planning (Huang et al., 2022; 2023;
Silver et al., 2022), to take the advantage of LLMs’ ability
to translate between natural languages and programs.

Contextual Markov Decision Process The CMDP (Hallak
et al., 2015) maps a context c = (g, s, t) into a specific
MDP M(g, s, t) = (S, A, s, t, Rg ), where S and A are theset of states and actions, and s, t, Rg are a specific startingstate, transition function, and goal-conditioned reward
function respectively. Each generation i has a generationspecific MDP Mi = (S, A, si , ti , Rgi ) where S and A are
fixed across generations, while si , ti , Rgi changes acrossgenerations. An MDP Mi can receive a sequence of actions[a1 . . . ak ] and produce a final state Mi ([a1 . . . ak ]) = s′iusing the transition function. The goal g is a predicate
function over states g(s) ∈ {0, 1}.

RL and Planning with Changing Dynamics The robust
operation of agents under changing dynamics (Hallak et al.,2015; Padakandla, 2021; Choi, 2000; Xie et al., 2022) isof crucial importance in realistic scenarios. Methods suchas (Banerjee et al., 2017; Mesesan et al., 2019; Lin et al.,2019) calibrate a learned policy to adapt to novel environments, while (Arumugam et al., 2017; 2019; Kaelbling,
1993; Squire et al., 2015; Bodik et al., 2010) maintains
a hierarchy of goal representations, allowing the agent to
re-plan as environments change.

Generational Learning Let A[E] denotes a learning agent
A parameterized by experience E. At each generation i, theagent A[Ei ] interacts with the user ui within environment
M(ci ), which produces a reward and a new experience(ri , ei ) = interact(ui , A[Ei ], M(ci )). The agent learns
by growing its experience Ei+1 = Ei ∪ {ei }, which ispassed onto the next generation. The
Pobjective of GLC is tomaximize cumulative reward r = i ri .

Library Learning In library learning, a system continually grows a library of programs, becoming more competentin solving complex tasks over time. The library learning
can be self-driven (Ellis et al., 2020), guided by language(Wong et al., 2021), or in direct interactions with a community of users (Wang et al., 2017; 2016; McCarthy et al.,2021a; Karamcheti et al., 2020).

3.2. Generational Programming under changing
Contexts (GPC)
A GPC problem is a specific kind of GLC where the interaction takes place via programming, and the agent, a
programming system, learns from experience by building
a library. See Figure 2. Specifically, given a context ci ,The user constructs a program pi . The programming system A[Li ], parameterized by the library Li , executes the
program, producing a action sequence and an experienceai , ei . The sequence ai is carried out on the environment
M(ci )(ai ), resulting in a reward if the goal g is satisfiedg(M(ci )(ai )). The agent learns from the experience ei bybuilding the new library Li+1 . The programming systems
in a GPC differ by their respective forms of programs, how
they execute these programs, and how they maintain andgrow their libraries – the crux of this work.

Overall Compared to works in robust policy and planning,
we focus on interactive learning from users as a mean ofacquiring new abstractions and search strategies. Compared
to works in library learning, we focus on goal driven task
decompositions to account for changing contexts. Taskoriented dialogue systems (Suhr et al., 2019; Fast et al.,2018; Wang et al., 2015) are different from our work as they
do not perform library learning 3 .

3. Generational Programming under
Changing Contexts
We first define the general problem of generational learning
under changing contexts, then extend it to the setting where
the learning takes the form of programming.

4. Programming Systems
We describe two baseline programming systems, direct programming and direct synthesis, that keep libraries of functions. For each, we explain the forms of programs theyrequire, how they execute a program to produce an action
sequence, and how they grow libraries across generations.

3.1. Generational Learning under changing Contexts(GLC)
A GLC problem is a tuple (U, G, S, T , M), consisting ofsequences (representing different generations) of users
U = u1 . . . un , goals G = g1 . . . gn , starting states
S = s1 . . . sn , dynamics T = t1 . . . tn , and a contextual
markov decision process CMDP M. This work considers
the setting where the set of goals G is finite and enumerable,
3

4.1. Direct Programming (DP)DP emulates library building in traditional programming,
where a library of functions can be accessed and expanded
by a community of users. For this work, we consider asimple family programs without variables and control flows

i.e. these systems cannot acquire higher level programs over

time

3

Building Community Driven Libraries of Natural Programs

Figure 2: The GPC (generational programming under changing context) problem at a particular generation. Given a
particular context, the user writes a program. This program is then executed by the agent (a programming system) producing
a sequence of actions, which is then carried out on the contextual MDP, resulting in a reward. The agent also generates anexperience, allowing it to build a better library for future generations.
4. The library L is a mapping from a function name f.name– a string, to a function body f.body – a sequence of actions.
L[name] = [a1 . . . ak ], ai ∈ A. The user u produces a
program p by reasoning over the context c and the library
L. u : (c, L) → p. The program p can take two forms: (1)executing an existing function; (2) defining a new function.

Execution via Search DS searches for an action sequencea such that, once carried out in M(c), satisfies the goal g.
In a typical program synthesis fashion (Devin et al., 2017;
Ellis et al., 2020), it performs rejection sampling6 :Algorithm 1: DS Execution
DS ( ( g , h i n t ) , M(c) , L ) =f o r Li i n L1 , L2 , . . . , Lmax_len :repeat n _ i t e r times :f _ 1 . . . f _ i ∼ propose(f1 . . . fi ∈ Li |(g, hint), Li )a = f _ 1 . body + . . . + f _ i . bodyi f g(M(c)(a)) :return a
return F a i l .

Execution The program is a single string name, which theuser selects from the library L, and the corresponding action
sequence L[name] is produced. No experience is producedby the system.
Function Definition The user gives DP a mapping
namenew → [name1 . . . namek ]. The system produces
a concatenated action sequence anew = L[name1 ] +· · · + L[namek ]. The system also produces an experiencee = namenew → anew .

The search is incremental, where DS attempts to first finda single program f ∈ L that satisfies the goal g, and whenthat fails, expands the search to [f1 , f2 ] ∈ L2 , and so on.

Generational Library Learning DP starts with the libraryof primitives L1 = LA = {“a1” → [a1 ] . . . “an” →[an ] ∀ai ∈ A}, where all the actions in A maybe referred
to by their names. DP grows the library as user adds new
functions to it Li+1 = Li ∪ {namenew → anew }.

Propose The rejection sampling is guided by a propose
function in the manner of language-guided synthesis(Wonget al., 2021; Li et al., 2022), where depending on the linguistic hint, certain combinations of functions become more
likely to be sampled. This is crucial as the search space of Li
grows exponentially as i increases. The difficulty of having
a good propose function is a lack of data – prior approaches
such as (Wong et al., 2021; Li et al., 2022; Suhr et al., 2019;
Wang et al., 2015) required significant labeling efforts ofpaired instances of natural-language to programs (in ourcase, function sequences). Instead, we look to pretrained
LLMs as a source of prior knowledge. Specifically, we consider two “backends” of our propose function, one based on
semantic similarities, the other based on prompting:

4.2. Direct Synthesis (DS)DS augments DP with language-guided program synthesis,
where the system searches the library for a satisfying sequence. DS maintains a library of functions L same as inDP, and in addition, it is made aware of the set of goals G
and can query the environment M(c) as a black box5 .
Programs are Search Problems The user u programs DS
by querying it with a search problem q = (g, hint) ∈ Q,
where Q = G × N L, a cross product of all goals and all natural language strings. Specifically, u : (g, s, t) → (g, hint).
Instead of browsing the library L, the user specifies the goalg to DS directly, along with a hint on how to achieve it.

proposesim (f1 . . . fi |(g, hint), Li )∝∥embedLLM (f1 .name + · · · + fi .name)−embedLLM (hint)∥
proposeprompt (f1 . . . fi |(g, hint), Li )=LLM(prompt[hint,L])

proposesim ranks the function composition f1 . . . fi based

4

think of a system of macros
i.e. the dynamics of M(c) hidden from the agent, but it cantake actions and observe outcomes5

6
most program synthesis approaches adopt the generate andcheck framework

4Building Community Driven Libraries of Natural Programs

on how similar their concatenated strings are is to thehint, based on their embedded distances under a LLM.
proposeprompt simply gives an instruction tuned LLM withthe hint and a subset of the library’s content, and queries
the LLM for a sequence of function names. Keep in mind
that it is not the contribution of this work to find the best
implementation for the propose function, but rather, wehighlight that our approaches are compatible with standard
techniques.

case q i s ( g , h i n t ) :decompose = Queue ( [ p r o p o s e ( q , L ) . . . n _ t i m e s ] )q s _ i = decompose . pop ( ) ( l a b e l : A)
cur_state = s
for q s _ i _ j in qs_i :n x t _ s t a t e = NP (c u r _ s t a t e , q s _ i _ j , L , M(c))
i f n e x t _ s t a t e i s not F a i l :cur_state = nxt_stateelse :
g o t o (A)i f q . goal ( c u r _ s t a t e ) :return c u r _ s t a t ee l s e i f decompose i s empty :return F a i l .
else :
g o t o (A)Generational Library Learning DS starts with a library ofprimitives L1 = LA . Given a search problem q = (g, hint),
DS only produces a sequence a when g(M(c)(a)), ande = hint → a is added to the library. Doing so achieves
compression (Ellis et al., 2020) – making a long sequence offunctions (that is difficult to search for) to a single function.
4.3. Brittleness of Functions

The most salient aspect of the NP execution is the recursive
call to NP itself7 . Thus, unlike DS, NP can keep decomposing until a satisfying sequence is found. Both DS and NP
share the same propose implementation. In practice, we
implement Algorithm 2 with a priority queue and caching
to avoid redundant executions.

Consider a particular sequence a1 made under a particular
CMDP M(c1 ) which satisfies the goal g. While sequence
a1 satisfies the goal g(M(c1 )(a1 )), the same sequence isunlikely to satisfy the same goal under a different context
c2 , i.e. g(M(c1 )(a1 )) ̸= g(M(c2 )(a1 )). As a result, whencontexts change, much of the functions in the library L canno longer satisfy the goals they are written for.

Generational Library Learning When Algorithm 2 finds
a satisfying a, NP produces an experience in the form of
a search tree (Figure 1, middle row), consisting of the correctly chosen decomposition steps. Each correct decomposition is a mapping q → q1 . . . qj ∈ P. They are added to L
(Figure 1).

5. Natural Programming
Notice the discrepancy in the DS system: it takes in search
problems, yet maintains a library of a different kind – alibrary of explicit action sequences. What if we maintaina library of search problems as well? A natural programnp ∈ P is a mapping from a search problem to a sequenceof primitives or other search problems. P = {Q ⇒ (LA ∪Q) × · · · × (LA ∪ Q)}. The Natural Programming system
maintains a library of natural programs L ⊂ P.

6. CraftLite
To study the effects of different programming systems in
the context of GPC, we introduce a simple programming
environment, CraftLite, with the following desiderata:(1) Can be used as a multi-generational GPC problem. (2)Crowd workers can consistently learn how to “program”
it in under 5 minutes – so a large scale user study would
not be prohibitively expensive. (3) Has a real-time (∼2s)
responsiveness to accommodate for end-user interactions.

Programs are Search Problems The interface of DS and
NP are exactly the same – given a context, an user produces
a search problem q ∈ Q for the system.
Execution via Recursive Decomposition Given q =(g, hint), NP searches for a satisfying action sequence inthe manner of hierarchical planning similar to the MAXQ
(Dietterich, 2000) algorithm. For simplicity, we have NP
only returning a satisfying final state s′ or F ail if it cannot
finds it – the satisfying action sequence a can be recovered by instrumenting book-keeping variables. We also use
M(c)(s, a) to denote taking an action step a with a startingstate s on M(c).

6.1. CraftLite as a Conditional MDP
State A state consists of an inventory of multiple items, twocrafting input slots, and a single crafting output. There 29
total possible items in CraftLite.
Action There are only 2 kinds of actions, input_x where
x is an item name, and craft. input_x moves an existing item in the inventory to the input slots, and craft
moves the transformed item in the output slot back to theinventory, consuming the inputs. Thus, there are 30 total
actions.

Algorithm 2: NP Execution
NP ( s , q , L , M(c) ) :case q i s Action :r e t u r n M(c) ( s , a )75

the goto is only there for ease of explanation!

Building Community Driven Libraries of Natural Programs

Dynamics The dynamic is dictated by the recipe book,which dictates which two input items can be successfullytransformed into an output item. Out of the 29 items, 4 are“raw materials”, and 25 are “craftable items” with 2 possible
crafting rules: For instance, a stick is made with rock+plankin one version while wood+plank in another. A recipe bookcan be randomly generated by choosing one version of thecrafting rules – there are 225 possible recipe books total.
Depending on the particular recipe book, the most complex
item can take up to 87 action steps. Thus, the raw commandsequence complexity of CraftLite is 3087 .

CraftLite? RQ2: Does the capability of NP improve ata faster rate across generations? RQ3: Does NP allows theuser to achieve more tasks with fewer efforts?
7.1. Simulated Study
We conduct a simulation study with a large number of simulated, idealized users to study the relative effectiveness of
NP vs DS as a function of changing dynamics.
Controlling Dynamics In CraftLite, every craftable
item has 2 possible rules. We can control how much dynamics can vary from one generation to next by adjusting
the probability r, of how likely the second rule is chosen.
A r = 0 would cause the generated recipe to only containthe first rule for every item, i.e. no dynamic changes acrossgenerations, while a r = 0.5 will uniformly sample oneof the 225 possible recipe books – the most difficult setup
where dynamics changes most.

Goal is a list of goal items, which generates a reward
when it is first added to the inventory.
6.2. The GPC Problem using CraftLite
The GPC set up for CraftLite is slightly different fromthat defined in Section 3 to allow for an user to interact witha programming system for an extended period of time in thesame environment.

Batches At every generation, the context contains: (1) A
set of 6 randomly chosen “leaf items” were used as goals– craftable items that are not required to craft other items.
(2) The starting state consisting of 4 raw materials. (3) A
randomly generated recipe with a particular r value. A batch
consists of 20 generations of 2 conditions, DS vs NP, where
the same generation shares the context.

Session A session gi at generation i consists of: an user ui ,a programming system with library A[Li ], and a context
ci . The context ci = (gi , s0 , ti ) consists of: a list of goal
items gi = gi1 . . . gir , the starting state si , and a randomly
generated recipe book ti . At the start of the interaction, a
CMDP M(ci ) is created. Within a specified time limit (e.g.,
10 minutes), a user ui interacts with A[Li ] to craft as many
goal items as possible under the same environment M(ci ).

(usim , DS, c1 ), . . . , (usim , DS, c20 );(usim , NP, c1 ), . . . , (usim , NP, c20 )Chains The participants are organized into “cultural
chains”(Tamariz & Kirby, 2016; Tessler et al., 2021b) collaborating with the same programming system. A chain isa sequence sessions: (u1 , A, c1 ), . . . (un , A, cn ). The programming system starts with the initial library L1 . Thislibrary is updated after every interaction with an user, andpersists to the next generation.

For each 3 value of r = [0, 0.25, 0.5], we generate 5 batches
each.
Simulated Users The simulated user is idealized. It will attempt first to craft a given goal item, and wait some amountof time until the solver succeeds or fails. If the solver succeeds, it moves onto the next item. If the solver fails, it
recursively attempts to craft a pre-requisite item. We do not
simulate an user for DP, and defer evaluation of DP to a realhuman experiment.

Batch A batch consists of multiple chains (one for each programming system) with a paired sequence of contexts. For
instance, the following is a batch of 2 conditions A1 , A2 ,2n participants, and paired contexts c1 . . . cn :Session Each session has a total of 2 minutes time limit, andthe solver timeout after 10 seconds.

(u1 , A1 , c1 ), . . . , (un , A1 , cn );(un+1 , A2 , c1 ), . . . , (un+n , A2 , cn );7. Experiments

Results RQ1: As we can see, when dynamics are kept
constant (r = 0.0), DS and NP performs identically on
CraftLite. However, as dynamics vary more (r = 0.25,
r = 0.50), the performance of NP is superior to that of
DS (Figure 4). RQ2: Similarly, we find NP improves at afaster rate across generations compared to DS under more
dynamics variations. RQ3: Because these are simulated
users, we defer the measurement of user efforts to the more
realistic scenario of a human experiment.

We seek to answer the following research questions.
RQ1: Is NP effective at solving the GPC problems in

Propose Back-end We found that for CraftLite, even if
we give a lenient solver timeout of 10 seconds, enough for a

6.3. User Interface of CraftLite
The user interface of CraftLite consists of a left programmatic panel based on Blockly (Pasternak et al., 2017),
and a right panel showing the current state. See Figure 3

6Building Community Driven Libraries of Natural Programs

Figure 3: The CraftLite UI. The DP programming system allows the user to manually define new functions, and browse
a library of existing functions. The DS / NP system only allows user to give a search problem. The game state shows aninventory of current items, and a list of goal items to be completed. All systems have a recipe book the user can browse,
which encodes the dynamics.

Figure 4: Simulation on how different programming systems perform under different amount of dynamic changes acrossgenerations. Total of 600 idealized simulated users. r = 0.0 no dynamic change and r = 0.5 most dynamic change. Error
bars are 95% CIs (nboot=1000), dots represent individual sessions outcomes.
prompting back-end to give a response, the similarity based
propose function is always faster. A comparison of semanticdistance vs prompting can be found in the supplement.

seconds, but the user can cancel the solver at any point.
7.2.1. R ESULTS
RQ1: More items are built overall with NP Across allbatches and generations, we find that NP allows people tobuild the most goal items overall (Figure 5A; DP mean
= 1.7 items, 95%CI = [1.6, 1.9], DS mean = 2.4 items,
95%CI = [2.3, 2.6], NP mean = 2.9 items, 95%CI =[2.7, 3.1]). Both synthesis-based systems perform significantly better overall than direct programming (t(71) =5.6, p < 0.001 for DP vs. DS; t(71) = 7.9, p < 0.001 forDP vs. NP, paired). Compared to the DS, NP produced
significantly more items (t(143) = 4.7, p < 0.001).

7.2. Human Experiment
Procedure We recruited 360 participants from the Prolificcrowdsourcing platform. Participants were recruited fromthe U.K. and the U.S., excluding people without English
proficiency. We paid an average of $12.06 USD per hour,
including bonuses for $0.4 USD per “goal”. In total, we ran
360 sessions across 12 batches of paired contexts, and of
a length of 12 generations. 6 batches containing all three
conditions (DP, DS, NP) and 6 only containing the two ofgreatest interest (DS, NP). Each session is 10 minutes. The
DS and NP solver is set to have a maximum timeout of 30

7

Building Community Driven Libraries of Natural Programs

Direct Programming

Natural Programming

C
6

5

5

4
3
2

4
3
2

D
6

6

5

5

# items built

6# items built

B# items built# items built

A

Direct Synthesis

4
3
2
1

1

condition

1

3

5

7

9

11

3
2
1

1
DP DS NP

4

10

30

100

300

# interactions(individual effort)

generation in chain

0

50

100 150 200

library size(community effort)

Figure 5: Natural programming (NP) enables (A) more items to be build overall, (B) improves significantly as successive
generations interact with the system, and (C-D) reduces the effort required to reach the same performance. Error bars are
95% CIs; low-transparency dots represent individual sessions; low-transparency lines represent regression fits for individual
chains.
95%CI = [0.2, 0.6]). Concretely, among participants thatcrafted exactly 2 items, DP required an average of 156 submissions, DS required 81 submissions, and NP only required
63 submissions. Similar results were found for collective
effort – the total library size (i.e., unique and successful previous interactions) that has accumulated at the given pointin the chain (Figure 5D).

RQ2: NP chains improve more rapidly Next, we consider how NP improves as additional users in a chain interact with the system (Figure 5B). We fit a (Bayesian)mixed-effects linear regression model predicting the number of items built as a function of the generation in the chain(integer from 1 to 12), the programming system (categorical, NP vs. DS vs. DP), and corresponding interaction
terms. First, examining the NP condition alone, we foundthat performance improved significantly across generations,(b = 6.24, 95% credible interval = [3.3, 9.3]). We foundthat this slope was meaningfully larger than the DS condition (diff = +3.4, 95% credible interval = [−0.5, 7.1])
and the DP condition (diff = 8.6, 95% credible interval= [3.5, 13.5]).

8. Conclusion
We define a new class of problems, GPC, to study how anagent can learn from different teachers and contexts programmatically. We developed the NP system – based on ahierarchical planner that learns new abstractions and decomposition rules from users. We demonstrate NP is efficient insolving GPC problems in the CraftLite domain throughboth simulations and a large (n=360) user study.

RQ3: NP requires less effort What properties of NP enable these performance benefits? We know it is not due
to the difference of user interface, as DS and NP uses exactly the same interface. In this section, we argue insteadthat NP reduces the amount of effort required to obtain thesame results. We tested this effect by running Bayesian
mixed-effects regressions predicting the number of items
built as a function of effort and the programming system being used. We consider two different metrics of effort. First,
we examine individual effort, the (log) number of “submissions” – registered every time a user attempts to executea program – made by a user to the programming system(Figure 5C). At a given level of effort, we found that participants in the NP condition were able to craft significantly
more items than those in DP condition (diff = 1.25 items,
95%CI = [0.8, 1.7]) or the DS condition (diff = 0.42 items,

Limitations The immediate limitations of this work is
CraftLite is rudimentary in its complexity. Scaling up
NP requires better propose implementations – for instance,a faster LLM+prompting, and taking in current state ascontext. Scaling up GPC requires a richer task domain
than CraftLite, yet still making it intuitive for end-users
for a systematic evaluation. Ultimately, a richer task domain will cost more money. The more subtle limitationof this work is the perfect mutual understanding of goals
between user to agents (DS and NP). This is possible in
CraftLite, but more generally, this is the complex topic
of AI-alignment(Gabriel, 2020). How to robustly compose
knowledge when under imperfect mutual understandings ofgoals is an exciting field for future research.
8

Building Community Driven Libraries of Natural Programs

References

Brown, W. J., Malveau, R. C., McCormick, H. W. S., andMowbray, T. J. AntiPatterns: Refactoring Software, Architectures, and Projects in Crisis: Refactoring Software,Architecture and Projects in Crisis. John Wiley and Sons,
1998.

Acquaviva, S., Pu, Y., Kryven, M., Wong, C., Ecanow, G. E.,
Nye, M., Sechopoulos, T., Tessler, M. H., and Tenenbaum,
J. B. Communicating natural programs to humans andmachines. arXiv preprint arXiv:2106.07824, 2021.

Bunel, R., Hausknecht, M., Devlin, J., Singh, R., andKohli, P. Leveraging grammar and reinforcement
learning for neural program synthesis. arXiv preprint
arXiv:1805.04276, 2018.

AlOmar, E. A., Rodriguez, P. T., Bowman, J., Wang, T.,
Adepoju, B., Lopez, K., Newman, C., Ouni, A., andMkaouer, M. W. How do developers refactor code to
improve code reusability? In Reuse in Emerging Software
Engineering Practices: 19th International Conference on
Software and Systems Reuse, ICSR 2020, Hammamet,
Tunisia, December 2–4, 2020, Proceedings 19, pp. 261–
276. Springer, 2020.

Chaturvedi, S. On composition, Dec 2019. URL https://shalabh.com/programmable-systems/
on-composition.html.
Choi, P.-M. Reinforcement learning in nonstationary environments. Hong Kong University of Science and Technology (Hong Kong), 2000.

Andreas, J., Klein, D., and Levine, S. Modular multitask
reinforcement learning with policy sketches. In International Conference on Machine Learning, pp. 166–175.
PMLR, 2017.

Devin, C., Gupta, A., Darrell, T., Abbeel, P., and Levine, S.
Learning modular neural network policies for multi-task
and multi-robot transfer. In 2017 IEEE International Conference on Robotics and Automation (ICRA), pp. 2169–
2176, May 2017. doi: 10.1109/ICRA.2017.7989250.

Arumugam, D., Karamcheti, S., Gopalan, N., Wong, L. L.,
and Tellex, S. Accurately and efficiently interpreting
human-robot instructions of varying granularities. arXiv
preprint arXiv:1704.06616, 2017.

Dietterich, T. G. Hierarchical reinforcement learning withthe maxq value function decomposition. Journal of artificial intelligence research, 13:227–303, 2000.

Arumugam, D., Karamcheti, S., Gopalan, N., Williams,
E. C., Rhee, M., Wong, L. L., and Tellex, S. Grounding
natural language instructions to semantic goal representations for abstraction and generalization. Autonomous
Robots, 43:449–468, 2019.

Ellis, K., Wong, C., Nye, M., Sable-Meyer, M., Cary, L.,
Morales, L., Hewitt, L., Solar-Lezama, A., and Tenenbaum, J. B. Dreamcoder: Growing generalizable, interpretable knowledge with wake-sleep bayesian program
learning. arXiv preprint arXiv:2006.08381, 2020.

Banerjee, T., Liu, M., and How, J. P. Quickest change
detection approach to optimal control in markov decision
processes with model changes. In 2017 American control
conference (ACC), pp. 399–405. IEEE, 2017.

Fast, E., Chen, B., Mendelsohn, J., Bassen, J., and Bernstein,
M. S. Iris: A conversational agent for complex tasks.
In Proceedings of the 2018 CHI conference on humanfactors in computing systems, pp. 1–12, 2018.

Bastani, O., Pu, Y., and Solar-Lezama, A. Verifiable reinforcement learning via policy extraction. Advances inneural information processing systems, 31, 2018.

Gabriel, I. Artificial intelligence, values, and alignment.
Minds and machines, 30(3):411–437, 2020.
Garlan, D., Allen, R., and Ockerbloom, J. Architectural
mismatch: Why reuse is still so hard. IEEE software, 26(4):66–69, 2009.

Bodik, R., Chandra, S., Galenson, J., Kimelman, D., Tung,N., Barman, S., and Rodarmor, C. Programming withangelic nondeterminism. In Proceedings of the 37th
annual ACM SIGPLAN-SIGACT symposium on Principles of programming languages, POPL ’10, pp. 339–
352, New York, NY, USA, January 2010. Association
for Computing Machinery. ISBN 978-1-60558-479-9.
doi: 10.1145/1706299.1706339. URL https://doi.
org/10.1145/1706299.1706339.

Hallak, A., Di Castro, D., and Mannor, S.
Contextual markov decision processes. arXiv preprint
arXiv:1502.02259, 2015.
Huang, W., Abbeel, P., Pathak, D., and Mordatch, I. Language models as zero-shot planners: Extracting actionable knowledge for embodied agents. arXiv preprint
arXiv:2201.07207, 2022.

Bonawitz, E., Shafto, P., Gweon, H., Goodman, N. D.,
Spelke, E., and Schulz, L. The double-edged sword of
pedagogy: Instruction limits spontaneous exploration anddiscovery. Cognition, 120(3):322–330, 2011.

Huang, W., Xia, F., Shah, D., Driess, D., Zeng, A., Lu,
Y., Florence, P., Mordatch, I., Levine, S., Hausman,9Building Community Driven Libraries of Natural ProgramsK., et al. Grounded decoding: Guiding text generation
with grounded models for robot control. arXiv preprint
arXiv:2303.00855, 2023.

Padakandla, S. A survey of reinforcement learning algorithms for dynamically varying environments. ACM
Comput. Surv., 54(6), jul 2021. ISSN 0360-0300.
doi: 10.1145/3459991. URL https://doi.org/10.
1145/3459991.

Inala, J. P., Bastani, O., Tavares, Z., and Solar-Lezama,
A. Synthesizing programmatic policies that inductively
generalize. In 8th International Conference on Learning
Representations, 2020.

Pasternak, E., Fenichel, R., and Marshall, A. N. Tips forcreating a block language with blockly. In 2017 IEEE
Blocks and Beyond Workshop (B&B), pp. 21–24, 2017.
doi: 10.1109/BLOCKS.2017.8120404.

Kaelbling, L. P. Learning to achieve goals. In IJCAI, volume 2, pp. 1094–8. Citeseer, 1993.

Shiarlis, K., Wulfmeier, M., Salter, S., Whiteson, S., andPosner, I. TACO: Learning task decomposition via temporal alignment for control. In Dy, J. and Krause, A. (eds.),
Proceedings of the 35th International Conference on Machine Learning, volume 80 of Proceedings of Machine
Learning Research, pp. 4654–4663. PMLR, 10–15 Jul
2018. URL https://proceedings.mlr.press/
v80/shiarlis18a.html.

Kaelbling, L. P. and Lozano-Pérez, T. Hierarchical task andmotion planning in the now. In 2011 IEEE International
Conference on Robotics and Automation, pp. 1470–1477,
May 2011. doi: 10.1109/ICRA.2011.5980391. ISSN:
1050-4729.
Karamcheti, S., Sadigh, D., and Liang, P. Learning adaptive language interfaces through decomposition. arXiv
preprint arXiv:2010.05190, 2020.

Silver, T., Chitnis, R., Tenenbaum, J., Kaelbling, L. P., andLozano-Pérez, T. Learning symbolic operators for task
and motion planning. In 2021 IEEE/RSJ International
Conference on Intelligent Robots and Systems (IROS), pp.
3182–3189. IEEE, 2021a.

Konidaris, G., Kaelbling, L. P., and Lozano-Perez, T. Fromskills to symbols: Learning symbolic representations for
abstract high-level planning. Journal of Artificial Intelligence Research, 61:215–289, 2018.
Li, Y., Choi, D., Chung, J., Kushman, N., Schrittwieser, J.,
Leblond, R., Eccles, T., Keeling, J., Gimeno, F., Dal Lago,A., et al. Competition-level code generation with alphacode. Science, 378(6624):1092–1097, 2022.

Silver, T., Chitnis, R., Tenenbaum, J., Kaelbling, L. P., andLozano-Pérez, T. Learning Symbolic Operators for Task
and Motion Planning. In 2021 IEEE/RSJ International
Conference on Intelligent Robots and Systems (IROS), pp.
3182–3189, September 2021b. doi: 10.1109/IROS51168.
2021.9635941. ISSN: 2153-0866.

Liang, J., Huang, W., Xia, F., Xu, P., Hausman, K., Ichter,
B., Florence, P., and Zeng, A. Code as policies: Language
model programs for embodied control. arXiv preprint
arXiv:2209.07753, 2022.

Silver, T., Hariprasad, V., Shuttleworth, R. S., Kumar, N.,
Lozano-Pérez, T., and Kaelbling, L. P. Pddl planningwith pretrained large language models. In NeurIPS 2022
Foundation Models for Decision Making Workshop, 2022.

Lin, X., Guo, P., Florensa, C., and Held, D. Adaptive variance for changing sparse-reward environments. In 2019
International Conference on Robotics and Automation(ICRA), pp. 3210–3216. IEEE, 2019.

Squire, S., Tellex, S., Arumugam, D., and Yang, L. Grounding english commands to reward functions. In Robotics:
Science and Systems, 2015.

McCarthy, W., Hawkins, R., Holdaway, C., Wang, H., andFan, J. Learning to communicate about shared procedural abstractions. In Proceedings of the 43rd Annual
Conference of the Cognitive Science Society, 2021a.

Suchman, L. and Suchman, L. A. Human-machine reconfigurations: Plans and situated actions. Cambridge university press, 2007.

McCarthy, W. P., Hawkins, R., Wang, H., Holdaway, C.,
and Fan, J. E. Learning to communicate about sharedprocedural abstractions. In Proceedings of the Annual
Meeting of the Cognitive Science Society, volume 43,2021b.

Suhr, A., Yan, C., Schluger, J., Yu, S., Khader, H.,
Mouallem, M., Zhang, I., and Artzi, Y. Executing instructions in situated collaborative interactions. arXiv
preprint arXiv:1910.03655, 2019.
Sumers, T., Hawkins, R., Ho, M. K., Griffiths, T., andHadfield-Menell, D. How to talk so ai will learn: Instructions, descriptions, and autonomy. Advances in Neural
Information Processing Systems, 35:34762–34775, 2022.

Mesesan, G., Englsberger, J., Garofalo, G., Ott, C., andAlbu-Schäffer, A. Dynamic walking on compliant anduneven terrain using dcm and passivity-based whole-bodycontrol. In 2019 IEEE-RAS 19th International Conference on Humanoid Robots (Humanoids), pp. 25–32.
IEEE, 2019.

Tamariz, M. and Kirby, S. The cultural evolution of language. Current Opinion in Psychology, 8:37–43, 2016.
10

Building Community Driven Libraries of Natural Programs

Taylor,M.
Whatever happened to programming?,
Mar 2010.
URL https://reprog.wordpress.com/2010/03/03/
whatever-happened-to-programming/.

Yang, Y., Inala, J. P., Bastani, O., Pu, Y., Solar-Lezama, A.,
and Rinard, M. Program synthesis guided reinforcement
learning for partially observed environments. Advances inneural information processing systems, 34:29669–29683,
2021.

Tessler, M. H., Madeano, J., Tsividis, P. A., Harper, B.,
Goodman, N. D., and Tenenbaum, J. B. Learning to solve
complex tasks by growing knowledge culturally acrossgenerations. arXiv preprint arXiv:2107.13377, 2021a.

Zhan, E., Tseng, A., Yue, Y., Swaminathan, A., andHausknecht, M. Learning calibratable policies using
programmatic style-consistency. In International Conference on Machine Learning, pp. 11001–11011. PMLR,
2020.

Tessler, M. H., Tsividis, P. A., Madeano, J., Harper, B., andTenenbaum, J. B. Growing knowledge culturally acrossgenerations to solve novel, complex tasks. arXiv preprint
arXiv:2107.13377, 2021b.
Trivedi, D., Zhang, J., Sun, S.-H., and Lim, J. J. Learningto synthesize programs as interpretable and generalizable policies. Advances in neural information processing
systems, 34:25146–25163, 2021.
Volum, R., Rao, S., Xu, M., DesGarennes, G. A., Brockett,C., Van Durme, B., Deng, O., Malhotra, A., and Dolan, B.
Craft an iron sword: Dynamically generating interactive
game characters by prompting large language models
tuned on code. In The Third Wordplay: When Language
Meets Games Workshop, 2022.
Wang, S. I., Liang, P., and Manning, C. D. Learning language games through interaction. In Proceedings of the54th Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers), pp. 2368–
2378, 2016.
Wang, S. I., Ginn, S., Liang, P., and Manning, C. D. Naturalizing a programming language via interactive learning.
In Proceedings of the 55th Annual Meeting of the Association for Computational Linguistics (Volume 1: Long
Papers), pp. 929–938, 2017.
Wang, Y., Berant, J., and Liang, P. Building a semantic
parser overnight. In Proceedings of the 53rd Annual
Meeting of the Association for Computational Linguistics
and the 7th International Joint Conference on Natural
Language Processing (Volume 1: Long Papers), pp. 1332–
1342, 2015.
Wong, C., Ellis, K. M., Tenenbaum, J., and Andreas, J.
Leveraging language to learn program abstractions andsearch heuristics. In International Conference on Machine Learning, pp. 11193–11204. PMLR, 2021.
Xie, A., Sodhani, S., Finn, C., Pineau, J., and Zhang, A.
Robust policy learning over multiple uncertainty sets.
In International Conference on Machine Learning, pp.
24414–24429. PMLR, 2022.
11