Nothing Special   »   [go: up one dir, main page]
Skip to main content
SpringerLink
Log in

A knowledge-based framework for automated software synthesis

  • Published:
Automated Software Engineering Aims and scope Submit manuscript

Abstract

Automated software synthesis is one of the central techniques used in knowledge-based software engineering to enhance the quality and efficiency of software development. Although many software synthesis systems have been developed, automatic control of these systems remains a difficult problem. Our goal is to reduce user interaction in transformational and schema-based synthesizers by means of significant advances in control mechanisms.

This paper describes an approach for synthesis control that integrates a blackboard control architecture with an existing synthesis system. We present a framework language called MetaMorphos that allows explicit representations of control knowledge for use in selecting appropriate synthesis actions. MetaMorphos represents control decisions explicitly in terms of actions, events, and states. It is task-specific and contains knowledge about programming and how to select synthesizing methods based on given features. By employing a blackboard control architecture, our synthesis controller provides adaptability for dynamic control behaviors and flexibility to handle unanticipated situations during software development.

Applying MetaMorphos in the domain of software synthesis, we illustrate how we use MetaMorphos to select appropriate transformations, data structure and algorithm schemas during the synthesis. An example shows how MetaMorphos handles the difficult problem of selecting schemas for two very similar problems which, in the best case, require different solutions.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
$34.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

Explore related subjects

Discover the latest articles, news and stories from top researchers in related subjects.

References

  • B. Abbot, T. Bapty, C. Biegl, G. Karsaiand, and J. Sztipanovits. Model-based software synthesis.IEEE Software, May: 1993.

  • D. Barstow.Knowledge-Based Program Construction. Elsevier-North Holland, 1979.

  • D. Barstow, H. E. Shrobe, and E. Sandewal, editors.Interactive Programming Environments. McGraw-Hill, 1984.

  • S. Bhansali.Domain-Based Program Synthesis using Planning and Derivational Analogy. Ph.D. thesis, Department of Computer Science, University of Illinois at Urbana-Champaign, Technical report UIUCDCS R-91-1701, 1991.

  • S. Bhansali and M. Harandi. Synthesis of UNIX programs using derivational analogy. To appear inMachine Learning Journal; also Technical Report KSL-92-02, Knowledge Systems Laboratory, Stanford University, Stanford, CA, 1992.

  • L. Blaine and A. Goldberg. Dtre—A semi-automatic transformation system. In B. Moller, editor,Constructing Programs from Specification, pp. 165–204, North-Holland, Amsterdam, 1991.

    Google Scholar 

  • J. G. Carbonell. Learning by analogy: Formulating and generalizing plans from past experience, chapter 5, pp. 571–590. 1986.

  • B. Chandrasekaran. Design problem solving: A task analysis.AI Magazine, 11(4):59–71, 1990.

    Google Scholar 

  • R. Davis and B. G. Buchanan. Meta-level knowledge. InRule-based Expert Systems, B. G. Buchanan and E. H. Shortliffe, editors, Chapter 28. Addison-Wesley, 1984.

  • N. Dershowitz. Programming by analogy. In R. S. Michalski, J. G. Carbonell and T. M. Mitchell, editors,Machine Learning: An Artificial Intelligence Approach, Volume II, pp. 395–424. Morgan Kaufmann Publishers, Los Altos, CA, 1986.

    Google Scholar 

  • R. Englemore and T. Morgan, editors.Blackboard Systems. Addison-Wesley, 1988.

  • M. S. Feather. A survey and classification of some program transformation approaches and techniques. In L. Meertens, editor,Proc. IFIP TC 2 Working Conference on Program Specification and Transformation, North-Holland, Amsterdam, 1987.

    Google Scholar 

  • M. S. Feather. Specification evolution and program (re)transformation. InProceedings of the Fifth Conference on Knowledge-Based Software Assistant, 1990.

  • S. Fickas. Automating the transformational development of software.IEEE Transactions on Software Engineering, SE-11(11):1268–1277, 1985.

    Google Scholar 

  • S. Fickas and B. R. Helm. Knowledge representation and reasoning in the design of composite systems.IEEE Transactions on Software Engineering, SE-18(6):470–482, 1992.

    Google Scholar 

  • A. Gans, T. Confrey, and B. Hayes-Roth. How WATCH works: Documentation for the WATCH, NEWWATCH, and METAWATCH programs. Technical Report KSL-90-03, Knowledge Systems Laboratory, Stanford University, 1990.

  • A. Garvey and B. Hayes-Roth. An empirical analysis of explicit vs. implicit control architectures. In V. Jagannathan, R. Dodhiawala, and L. S. Baum, editors,Blackboard Architectures and Applications. Academic Press, 1989.

  • H. Graves, J. Louie, and T. Mullen. A code synthesis experiment. InProceedings of the Seventh Knowledge-Based Software Engineering Conference, 1992.

  • C. Green. Application of theorem proving to problem solving. InProceedings of the First International Joint Conference on Artificial Intelligence, Washington, D.C., pp. 219–239, 1969.

  • M. T. Harandi and S. Bhansali. APU: An automatic programmer for UNIX. InProceedings of the 2nd International IEEE Conference on Tools for Artificial Intelligence (TAI 90), pp. 410–416, 1990.

  • J. Harvey and B. Hayes-Roth. WATCH: Inductive abstraction of control knowledge. Masters Thesis, Knowledge Systems Laboratory, Stanford University, 1987.

  • B. Hayes-Roth and F. Hayes-Roth. A cognitive model of planning.Cognitive Science, 3(4):275–309, 1979.

    Google Scholar 

  • B. Hayes-Roth and M. Hewett. Learning control heuristics in BB1. Technical Report STAN-CS-85-1036, Stanford University, 1985.

  • B. Hayes-Roth. A blackboard architecture for control.Artificial Intelligence Journal, 26:251–321; reprinted in A. Bond and L. Gasser, editors,Readings in Distributed Artificial Intelligence, Morgan Kaufmann, 1988.

    Google Scholar 

  • B. Hayes-Roth, A. Garvey, M. V. Johnson, Jr., and M. Hewett. A modular and layered environment for reasoning about action. Technical Report KSL-86-38, Stanford University, 1986a.

  • B. Hayes-Roth, M. V. Johnson, A. Garvey, and M. Hewett. Application of the BB1 blackboard control architecture to arrangement-assembly tasks.Journal of Artificial Intelligence in Engineering, 1(2):85–94, 1986b.

    Google Scholar 

  • B. Hayes-Roth, M. Hewett, M. V. Johnson Jr., and A. Garvey. ACCORD: A framework for a class of design tasks. Technical Report KSL-88-19, Stanford University, 1988a.

  • B. Hayes-Roth and M. Hewett. BB1: An implementation of the blackboard control architecture. In R. Engelmore and T. Morgan, editors,Blackboard Systems. Addison-Wesley, Wokingham, England, 1988.

    Google Scholar 

  • B. Hayes-Roth, B. Buchanan, O. Lichtarge, M. Hewett, R. Altman, J. Brinkley, C. Cornelius, B. Duncan, and O. Jardetzky. PROTEAN: Deriving protein structure from constraints. In R. Engelmore and T. Morgan, editors,Blackboard Systems. Addison-Wesley, Wokingham, England, 1988b.

    Google Scholar 

  • B. Hayes-Roth, R. Washington, R. Hewett, M. Hewett, and A. Seiver. Intelligent real-time monitoring and control. InProceedings of the Eleventh International Joint Conference on Artificial Intelligence, Detroit, 1989.

  • V. Jagannathan, R. Dodhiawala, and L. S. Baum, editors.Blackboard Architectures and Applications. Academic Press, 1989.

  • R. K. Jüllig. Applying formal software synthesis.IEEE Software, May: 1993.

  • R. K. Jüllig and Y. V. Srinivas. Diagrams for software synthesis. InProceedings of the Eighth Knowledge-Based Software Engineering Conference, 1993.

  • E. Kant. A knowledge-based approach to using efficiency estimation in program synthesis. InProceedings of the First International Conference on Artificial Intelligence, Menlo Park, CA, pp. 219–329, 1979.

  • E. Kant. On the efficient synthesis of efficient programs.Artificial Intelligence Journal, 20(3):253–306, 1983.

    Google Scholar 

  • E. Kant and D. R. Barstow. The refinement paradigm: The interaction of coding and efficiency knowledge in program synthesis. In D. R. Barstow, H. E. Shrobe, and E. Sandewall, editors,Interactive Programming Environments. McGraw-Hill, 1984.

  • E. Kant, F. Daube, W. MacGregor, and J. Wald. Scientific programming by automated synthesis. In M. Lowry and R. D. McCartney, editors,Automating Software Design, pp. 169–206. AAAI Press, 1991.

  • E. Kant. Synthesis of mathematical-modeling software.IEEE Software, May: 1993.

  • M. Lowry and R. McCartney, editors.Automating Software Design. AAAI Press/The MIT Press, 1991.

  • R. McCartney. Synthesizing algorithms with performance constraints. InProceedings of the Sixth National Conference on Artificial Intelligence, pp. 149–154, 1987.

  • M. L. Maher. Process models for design synthesis.AI Magazine, 11(4):49–58, 1990.

    Google Scholar 

  • Z. Manna and R. Waldinger. A deductive approach to program synthesis. In C. Rich and R. C. Waters, editors,Readings in Artificial Intelligence and Software Engineering, pp. 3–34. Morgan-Kaufmann, 1986.

  • P. Michel, L. Ulrich, and P. Duzy, editors.The Synthesis Approach to Digital System Design. Kluwer Academic Publishers, 1992.

  • W. R. Murray. Dynamic instructional planning in the BB1 blackboard architecture. In V. Jagannathan, R. Dodhiawala, and L. S. Baum, editors,Blackboard Architectures and Applications. Academic Press, Boston, 1989.

    Google Scholar 

  • W. Pardee and B. Hayes-Roth. Intelligent real-time control of material processing. Technical Report No. 1, Rockwell International, Science Center, Palo Alto Laboratory, 1987.

  • T. Parsons.Introduction to Compiler Construction. Computer Science Press, Freeman, New York, 1992.

    Google Scholar 

  • H. Partsch and R. Steinbrüggen. Program transformation systems.Computing Surveys, 15(3):199–236, 1983.

    Google Scholar 

  • C. Rich and R. C. Waters.The Programmer's Apprentice. ACM Press, 1990.

  • C. Rich and Y. A. Feldman. Seven layers of knowledge representation and reasoning in support of software development.IEEE Transactions on Software Engineering, SE-18(6):451–469, 1992.

    Google Scholar 

  • R. Schulman and B. Hayes-Roth. ExAct: A module for explaining actions. Technical Report KSL-87-8, Knowledge Systems Laboratory, Stanford University, 1987.

  • R. Sedgewick.Algorithms. Addison-Wesley, 1988.

  • D. Setliff. On the automatic selection of data structure and algorithms. In M. Lowry and R.D. McCartney, editors,Automating Software Design, pp. 207–226. AAAI Press, 1991.

  • D. Setliff and R. A. Rutenbar. Knowledge representation and reasoning in a software synthesis architecture.IEEE Transactions on Software Engineering, SE-18(6):523–533, 1992.

    Google Scholar 

  • D. R. Smith. Derived preconditions and their use in program synthesis. In D. W. Loveland, editor.Sixth Conference on Automated Deduction, Lecture Notes in Computer Science, volume 138, pp. 172–193. Springer-Verlag, Berlin, 1982.

    Google Scholar 

  • D. R. Smith. KIDS: A semiautomatic program development system.IEEE Transactions on Software Engineering, 16(9):1024–1043, 1990.

    Google Scholar 

  • D. R. Smith. KIDS—A knowledge-based software development system. In Lowry, M. and R.D. McCartney, editors,Automating Software Design, pp. 483–514. AAAI Press, 1991.

  • D. R. Smith. Track assignment in an air traffic control system: A rational reconstruction of system design. InProceedings of the Seventh Knowledge-Based Software Engineering Conference, 1992.

  • D. R. Smith and E. A. Parra. Transformational approach to transportation scheduling. InProceedings of the Eighth Knowledge-Based Software Engineering Conference, 1993.

  • T. E. Smith and D. E. Setliff. Towards supporting design phase synthesis. InProceedings of the Eighth Knowledge-Based Software Engineering Conference, 1993.

  • J. F. Sowa.Conceptual Structures: Information Processing in Mind and Machine. Addison-Wesley, Reading, MA, 1984.

    Google Scholar 

  • I. D. Tommelein, M. V. Johnson, B. Hayes-Roth, and R. E. Levitt. SIGHTPLAN: A blackboard expert system for construction site layout. In J. S. Gero, editor,Expert Systems in Computer-Aided Design, pp. 153–167. North-Holland, Amsterdam, 1987.

    Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Computer Science and Engineering Department, Florida Atlantic University, P.O. Box 3091, 33431-0091, Boca Raton, FL

    Rattikorn Hewett

  2. Department of Computer Sciences, University of Texas at Austin, Taylor Hall 2.124, 78712-1188, Austin, TX

    Micheal Hewett

Authors
  1. Rattikorn Hewett
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Micheal Hewett
    View author publications

    You can also search for this author in PubMed Google Scholar

Rights and permissions

Reprints and permissions

About this article

Cite this article

Hewett, R., Hewett, M. A knowledge-based framework for automated software synthesis. Autom Software Eng 1, 281–314 (1994). https://doi.org/10.1007/BF00871706

Download citation

  • Issue Date:

  • DOI: https://doi.org/10.1007/BF00871706

Keywords

Search

Navigation