Reference: Bhansali, S. & Harandi, M. T. Synthesis of UNIX Programs using Derivational Analogy. 1992.
Abstract: The feasibility of derivational analogy as a mechanism for improving problem- solving behavior has been shown for a variety of problem domains by several researchers. However, most of the implemented systems have been empirically evaluated in the restricted context of an already supplied base analog, or on a few isolated examples. In this paper we describe a derivational analogy based system, APU, that sythesizes UNIX shell scripts from a high-level problem specification. APU uses top down decomposition of problems, employing a hierarchical planner and a layered knowledge base of rules, and is able to speed up the derivation of programs by using derivational analogy. We assume that the problem specification is encoded in the vocabulary used by the rules. We describe APU's retrieval heuristics that exploit this assumption to automatically retrieve a good analog for a target problem from a case library, as well as its replay algorithm that enables it to effectively reuse the solution of an analogous problem to derive a solutuion for a new problem. We present experimental results to assess APU's performance, taking into account the cost of retrieving analogs form a sizable case library. We discuss the significance of the results and some of the issues in using derivational analogy to synthesize programs.
Full paper available as ps.