Learning one subprocedure per lesson

sierra is a program that learns procedures incrementally from examples, where an example is a sequence of actions. sierra learns by completing explanations. Whenever the current procedure is inadequate for explaining (parsing) the current example, sierra formulates a new subprocedure whose instantiation completes the explanation (parse tree). The key to sierra's success lies in supplying a small amount of extra information with the examples. Instead of giving it a set of examples, under which conditions correct learning is provably impossible, it is given a sequence of "lessons," where a lesson is a set of examples that is guaranteed to introduce only one subprocedure. This permits unbiased learning, i.e., learning without a priori, heuristic preferences concerning the outcome.