Abstract: Programming by demonstration (PBD) enables users to construct programs to automate repetitive tasks without writing a line of code. The key idea in PBD is to generalize from the user's demonstration to a robust program that will work in new situations. Previous approaches to PBD have employed heuristic, domain-specific algorithms to generalize from a small number of examples. In my talk, I propose a domain-independent machine learning approach to PBD that is capable of learning useful programs from a small number of examples. I answer two thorny questions: (1) How do we construct the search space of possible program statements? (2) How do we search this large space efficiently? My approach is based on the concept of version space algebra: construct a complex search space by composing smaller, more restricted spaces. I illustrate this approach with SMARTedit, a PBD system for text editing that automates repetitive editing tasks. In some cases, SMARTedit is capable of learning a correct program given only a single example. Finally, I generalize this framework beyond programming by demonstration to the broader problem of learning programs from traces of their execution behavior.