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 synthesizes 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 solution for a new problem. We present experimental results to assess APU's performance, taking into account the cost of retrieving analogs from a sizable case library. We discuss the significance of the results and some of the issues in using derivational analogy to synthesize programs.
Article PDF
Similar content being viewed by others
References
Barstow, D. (1979).Knowledge based program construction. New York: Elsevier North Holland.
Baxter, I.D. (1990).Transformational maintenance by reuse of design histories. Doctoral dissertation. Department of Computer Science, University of California, Irvine. Technical report 90-36.
Bhansali, S. (1991).Domain-based program synthesis using planning and derivational analogy. Doctoral dissertation, Department of Computer Science, University of Illinois at Urbana-Champaign. Technical report UIUCDCS R-91-1701.
Bhansali, S., & Harandi, M.T. (1990a). APU: automating UNIX programming.IEEE International Conference on Tools for Artificial Intelligence (pp. 410–416), Washington, DC: IEEE Computer Society Press.
Bhansali, S., & Harandi, M.T. (1990b). The role of derivational analogy in reusing program design.Fifth Annual Knowledge-Based Software Assistant Conference (pp. 28–41). Syracuse, NY.
Blumenthal, B. (1990). Empirical comparisons of some design replay algorithms.Eighth National Conference on Artificial Intelligence (pp. 902–707). Boston, MA: AAAI Press/The MIT Press.
Burstein, M. H. (1986). Concept formation by incremental analogical reasoning and debugging. In R.S. Michalski, J.G. Carbonell, & T.M. Mitchell (Eds.),Machine learning: An artificial intelligence approach (Vol. 2). San Mateo, CA: Morgan Kaufmann.
Carbonell, J.G. (1983). Derivational analogy and its role in problem solving.Third National Conference on Artificial Intelligence (pp. 64–69). Washington, DC: Morgan Kaufmann.
Carbonell, J.G., & Veloso, M. (1988). Integrating derivational analogy into a general problem solving architecture.DARPA Workshop on Case-Based Reasoning (pp. 104–124). Clearwater Beach, FL: Morgan Kaufmann.
Dershowitz, N.D. (1985). Synthetic programming.Artificial Intelligence, 25, 323–373.
Dershowitz, N.D. (1986). Programming by analogy. In R.S. Michalski, J.G. Carbonell, & T.M. Mitchell (Eds.),Machine learning: An artificial intelligence approach (Vol. 2). San Mateo, CA: Morgan Kaufmann.
Gentner, D. (1983) Structure-mapping: a theoretical framework for analogy.Cognitive Science, 7(2, 155–170.
Goldberg, A. (1990). Reusing software developments. (Technical Report KES.U.90.2). Palo Alto, CA: Kestrel Institute.
Greiner, R. (1988). Learning by understanding analogies.Artificial Intelligence, 35 81–125.
Harandi, M.T., & Bhansali, S. (1989). Program derivation using analogy.Eleventh International Joint Conference on Artificial Intelligence (pp. 389–394). Detroit, MI: Morgan Kaufmann.
Hickman, A.K., & Lovett, M.C. (1991). Partial match and search control via internal analogy.Thirteenth Annual Conference of the Cognitive Science Society. Chicago, IL: Lawrence Erlbaum.
Huhns, M., & Acosta, R. (1987). Argo: an analogical reasoning system for solving design problems (Technical Report AI/CAD-092-87). Austin TX: Microelectronics and Computer Technology.
Kambhampati, S. (1989).Flexible reuse and modification in hierarchical planning. Doctoral dissertation, Department of Computer Science, University of Maryland, College Park. Technical Report CS-TR-2334.
Kambhampati, S. (1990a). Mapping and retrieval during plan reuse: a validation structure based approach.Eighth National Conference on Artificial Intelligence (pp. 170–175). Boston, MA: AAAI Press/The MIT Press.
Kambhampati, S. (1990b). A theory of plan modification.Eighth National Conference on Artificial Intelligence (pp. 176–182). Boston, MA: AAAI Press/The MIT Press.
Katz, S., Richter, C.A., & The, K.S. (1989). PARIS: a system for reusing partially interpreted schemas. In T.J. Biggerstaff & A.J. Perlis (Eds.),Software reusability (Vol. 1): Concepts and models. New York: ACM Press.
Kedar-Cabelli, S.T. (1985). Purpose-directed analogy.Seventh Annual Conference of the Cognitive Science Society (pp. 150–159). Irvine, CA: Lawrence Erlbaum.
Mendenhall, W., Scheaffer, R.L., & Wackerley, D.D. (1981).Mathematical statistics with applications. Boston, MA: Duxbury Press.
Minton, S. (1988).Learning effective search control knowledge: An explanation-based approach. Boston, MA: Kluwer.
Miryala, K., & Harandi, M.T. (1991). Automatic derivation of formal software specifications from informal descriptions.IEEE Transactions on Software Engineering, 17(10, 1126–1142.
Mostow, J. (1989). Design by derivational analogy: issues in the automated replay of design plans.Artificial Intelligence, 40, 119–184.
Mostow, J., Barley, M., & Weinreich, T. (1989). Automated reuse of design plans.International Journal for Artificial Intelligence and Engineering, 4(4, 181–196.
Mostow, J., & Fisher, G. (1989). Replaying transformational derivations of heuristic search algorithms in DIOGENES.DARPA Workshop on Case-Based Reasoning (pp. 94–99). Pensacola Beach, FL: Morgan Kaufmann.
Sacerdoti, E. (1974). Planning in a hierarchy of abstraction spaces.Artificial Intelligence, 5, 115–135.
Sacerdoti, E. (1977).A structure for plans and behavior. Amsterdam: North-Holland.
Stefik, M. (1981). Planning and metaplanning (MOLGEN: Part 2).Artificial Intelligence, 16, 141–169.
Steier, D. (1987). CYPRESS-Soar: a case study in search and learning in algorithm design.Tenth International Joint Conference on Artificial Intelligence (pp. 327–330). Milan, Italy: Morgan Kaufmann.
Steinberg, L.I., & Mitchell, T.M. (1985). The REDESIGN system: a knowledge-based approach to VLSI CAD.IEEE Design & Test, 2, 45–54.
Stickel, M.E. (1981). A unification algorithm for associative-commutative functions.Journal of the ACM, 28(3, 423–434.
Veloso, M., & Carbonell, J.G. (1991). Learning by analogical replay in PRODIGY: first results.European Working Session on Learning. Porto, Portugal: Springer-Verlag.
Waters, R.C. (1985). The programmer's apprentice: a session with KBEmacs.IEEE Transactions on Software Engineering, 11(11, 1296–1320.
Wile, D.S. (1983). Program developments: formal explanations of implementations.Communications of the ACM, 26(11, 902–911.
Author information
Authors and Affiliations
Rights and permissions
About this article
Cite this article
Bhansali, S., Harandi, M.T. Synthesis of UNIX programs using derivational analogy. Mach Learn 10, 7–55 (1993). https://doi.org/10.1007/BF00993480
Received:
Accepted:
Issue Date:
DOI: https://doi.org/10.1007/BF00993480