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 \emph{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 manner of 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 maintain libraries of command sequences.