Search
1996 Volume 11
Article Contents
RESEARCH ARTICLE   Open Access    

Developing correct and efficient logic programs by transformation*

More Information
  • The complex process of deriving programs from specifications is often divided into the following three steps: (i) the derivation of formal specifications from the informal ones; (ii) the validation of the formal specifications; and (iii) the derivation of executable programs from the formal specifications.
  • 加载中
  • Apt KR and Turini F, (eds) 1995. Meta-Logics for Logic Programming, MIT Press.

    Google Scholar

    Arsac J and Kodratoff Y, 1982. “Some techniques for recursion removal from recursive functions” ACM Trans Programming Languages and Systems4(2) 295–322.

    Google Scholar

    Benkerimi K and Lloyd JW, 1990. “A partial evaluation procedure for logic programs” In: Debray S and Hermenegildo M (eds.), Logic Programming: Proceedings of the 1990 North American Conference, Austin, Texas, 343–358. MIT Press.

    Google Scholar

    Bossi A, Cocco N and Dulli S, 1990. “A method for specializing logic programs” ACM Trans Programming Languages and Systems12(2) 253–302.

    Google Scholar

    Bossi A, Cocco N and Etalle S, 1996. “Transforming left-terminating programs: The reordering problem” In: Proietti M (ed.), Logic Program Synthesis and Transformation, Proceedings LOPSTR ‘95, Utrecht, The Netherlands, 33–45, Springer-Verlag.

    Google Scholar

    Boyer RS and Moore JS, 1975. “Proving theorems about Lisp functions” Journal of the ACM22(1) 129–144.

    Google Scholar

    Brogi A, Mancarella P, Pedreschi D and Turini F, 1990. “Composition operators for logic theories” In: Lloyd JW (ed.), Proceedings of the Symposium on Computational Logic117–134, Springer-Verlag.

    Google Scholar

    Brough DR and Hogger CJ, 1987. “Compiling associativity into logic programs” Journal of Logic Programming4345–359.

    Google Scholar

    Brough DR and Hogger CJ, 1991. “Grammar-related transformation of logic programs” New Generation Computing9(1)115–134.

    Google Scholar

    Bruynooghe M, De Schreye D and Krekels B, 1989. “Compiling control” Journal of Logic Programming6135–162.

    Google Scholar

    Burstall RM and Darlington J, 1977. “A transformation system for developing recursive programs” Journal of the ACM24(1) 44–67.

    Google Scholar

    Clark KL and Tärnlund S-Å, 1977. “A first order theory of data and programs” Proceedings Information Processing ‘77939–944, North-Holland.

    Google Scholar

    Consel C, 1996. “Program adaptation based on program transformation” Position paper for the MIT Workshop on Strategic Directions of Computing Research, (to appear in SIGPLAN Notices).

    Google Scholar

    Debray SK1985. “Optimizing almost-tail-recursive Prolog programs” Proceedings IFIP International Conference on Functional Programming Languages and Computer Architecture Nancy France. Lecture Notes in Computer Science 201, 204–219, Springer-Verlag.

    Google Scholar

    Debray SK, 1988. “Unfold/fold transformation and loop optimization of logic programs” Proceedings of SIGPLAN 88 Conference on Programming Language Design and Implementation Atlanta, Georgia. SIGPLAN Notices 23(7) 297–307.

    Google Scholar

    Debray SK and Jain M, 1994. “A simple program transformation for parallelism” In: Bruynooghe M (ed.), Proceedings of the 1994 International Symposium on Logic Programming305–319, MIT Press.

    Google Scholar

    Debray SK and Warren DS, 1989. “Functional computations in logic programs” ACM TOPLAS11(3) 451–481.

    Google Scholar

    Flener P and Deville Y, 1993. “Logic program synthesis from incomplete specifications” Journal of Symbolic Computation15775–805.

    Google Scholar

    Fuchs NE and Fromherz MPJ, 1992. “Schema-based transformation of logic programs” In: Clement T and Lau K-K (eds.), Logic Program Synthesis and Transformation, Proceedings LOPSTR‘91, Manchester, UK, 111–125, Springer-Verlag.

    Google Scholar

    Fuchs NE and Schwitter R, 1995. “Specifying logic programs in controlled natural language” Workshop on Computational Logic for Natural Language Processing, Proceedings CLNLP ‘95, Edinburgh University.

    Google Scholar

    Futamura Y, 1971. “Partial evaluation of computation process—an approach to a compiler-compiler” Systems, Computers, Controls2(5) 45–50.

    Google Scholar

    Gallagher JP, 1988. “Transforming programs by specializing interpreters” Proceedings Seventh European Conference on Artificia1 Intelligence, ECAI ‘86109–122.

    Google Scholar

    Gallagher JP, 1993. “Tutorial on specialization of logic programs’ Proceedings of ACM SIGPLAN Symposium on Partial Evaluation and Semantics Based Program Manipulation, PEPM ‘93 Copenhagen, Denmark, 88–98, ACM Press.

    Google Scholar

    Gallagher JP and de Waal DA, 1993. “Deletion of redundant unary type predicates from logic programs” Proceedings of LoPSTr ’92Manchester, UK, 151–167, Springer-Verlag.

    Google Scholar

    Gegg-Harrison TS, 1995. “Representing logic program schemata in λ-Prolog” In: Sterling L (ed.), Proceedings of the 12th International Conference on Logic Programming,467–481.

    Google Scholar

    Huet G and Lang B, 1978. “Proving and applying program transformation expressed with second-order patterns” Acta Informatica1131–55.

    Google Scholar

    Jones ND, Gomard CK and Sestoft P, 1993. Partial Evaluation and Automatic Program Generation, Prentice Hall.

    Google Scholar

    Kirschenbaum M, Lakhotia A and Sterling L, 1989. “Skeletons and techniques for Prolog programming” TR 89–170, Case Western Reserve University.

    Google Scholar

    Komorowski HJ, 1982. “Partial evaluation as a means for inferencing data structures in an applicative language: A theory and implementation in the case of Prolog” Ninth ACM Symposium on Principles of Programming LanguagesAlbuquerque, New Mexico, 255–267.

    Google Scholar

    Komorowski HJ, 1989. “Towards synthesis of programs in the partial deduction framework” Proceedings of the Workshop on Automating Software DesignDetroit, MI, 138–143, Kestrel Institute.

    Google Scholar

    Kott L, 1985. “Unfold/fold program transformation” Algebraic Methods in Semantics411–434, Cambridge University Press.

    Google Scholar

    Lakhotia A and Sterling L, 1988. “Composing recursive logic programs with clausal join” New Generation Computing6(2 & 3) 211–226.

    Google Scholar

    Lakhotia A and Sterling L, 1990. “ProMix: A Prolog partial evaluation system” In: Sterling L (ed.), The Practice of Prolog137–179, MIT Press.

    Google Scholar

    Leuschel M, De Schreye D and de Waal A, 1996. “A conceptual embedding of folding into partial deduction: Towards a maximal integration” Report CW 225, K.U. Leuven, Belgium.

    Google Scholar

    Lloyd JW, 1987. Foundations of Logic Programming, Springer-Verlag.

    Google Scholar

    Lloyd JW and Shepherdson JC, 1991. “Partial evaluation in logic programming” Journal of Logic Programming1117–242.

    Google Scholar

    Martens B, De Schreye D and Bruynoogh M, 1992. “Sound and complete partial deduction with unfolding based on well-founded measures” Proceedings of the International Conference on Fifth Generation Computer Systems473–480, Ohmsha Ltd., lOS Press.

    Google Scholar

    Mogensen T and Bondorf A, 1993. “Logimix: A self-applicable partial evaluation for Prolog” In: Lau KK and Clement T (eds.), Logic Program Synthesis and Transformation, Proceedings LOPSTR ‘92Manchester, UK, 214–227, Springer-Verlag.

    Google Scholar

    Partsch HA, 1990. Specification and Transformation of Programs, Springer-Verlag.

    Google Scholar

    Paterson MS and Hewitt CE, 1970. “Comparative schematology” Conference on Concurrent Systems and Parallel Computation Project MACWoods Hole, MA, 119–127.

    Google Scholar

    Pettorossi A and Proietti M, 1994. “Transformation of logic programs: Foundations and techniques” Journal of Logic Programming19(20) 261–320.

    Google Scholar

    Pettorossi A and Proietti M, 1996. “A theory of logic program specialization and generalization for dealing with input data properties” Proceedings of the Dagstuhl Seminar on Partial Evaluation Lecture Notes in Computer Science1110, 386–408, Springer-Verlag.

    Google Scholar

    Pettorossi A, Proietti M and Renault S, 1996. “Enhancing partial deduction via unfold/fold rules” Logic Program Synthesis and Transformation, Proceedings of LOPSTR ‘96Stockholm, Sweden,Springer-Verlag (to appear in: Lecture Notes in Computer Science).

    Google Scholar

    Prestwich S, 1993. “Online partial deduction of large programs” Proceedings ACM Sigplan Symposium on Partial Evaluation and Semantics-Based Program Manipulation, PEPM ‘93Copenhagen, Denmark, 111–118, ACM Press.

    Google Scholar

    Proietti M and Pettorossi A, 1993. “The loop absorption and the generalization strategies for the development of logic programs and partial deduction” Journal of Logic Programming16(1–2) 123–161.

    Google Scholar

    Proietti M and Pettorossi A, 1994a. “Completeness of some transformation strategies for avoiding unnecessary logical variables” In: Van Hentenryck P (ed.), Proceedings of the Eleventh International Conference on Logic Programming (ICLP ‘94)Ligure S Margherita, Italy , 0613–18, 714–729, MIT Press.

    Google Scholar

    Proietti M and Pettorossi A, 1994b. “Synthesis of programs from unfold/fold proofs” In: Deville Y (ed.), Logic Program Synthesis and Transformation, Proceedings of LOPSTR ‘93Louvain-la-Neuve, Belgium, 141–158, Springer-Verlag.

    Google Scholar

    Proietti M and Pettorossi A, 1995. “Unfolding-definition-folding, in this order, for avoiding unnecessary variables in logic programs” Theoretical Computer Science142(1) 89–124.

    Google Scholar

    Safra S and Shapiro E, 1986. “Meta interpreters for real” In: Kugler HJ (ed.), Proceedings Information Processing 86271–278, North-Holland.

    Google Scholar

    Sahlin D, 1993. “Mixtus: An automatic partial evaluator for full Prolog” New Generation Computing127–51.

    Google Scholar

    Sawamura H and Takeshima T, 1985. “Recursive unsolvability of determinacy, solvable cases of determinacy and their application to Prolog optimization” Proceedings of the International Symposium on LogicBoston, 200–207, IEEE Press.

    Google Scholar

    Seki H, 1991. “Unfold/fold transformation of stratified programs” Theoretical Computer Science86107–139.

    Google Scholar

    Seki H and Furukawa K, 1987. “Notes on transformation techniques for generate and test logic programs” Proceedings of the International Symposium on Logic Programming, San Francisco, 215–223, IEEE Press.

    Google Scholar

    Smith DR, 1993. “Automating the design of algorithms” In: Möller B, Partsch H and Schuman S (eds.), Formal Program Development, IFIP TC2/ WG 2.1 State-of-the-Art Report Lecture Notes in Computer Science755, 324–354,Springer-Verlag.

    Google Scholar

    Sterling L, 1986. “Incremental flavour-mixing of meta-interpreters for expert system construction” Proceedings 3rd International Symposium on Logic Programming, Salt Lake City, Utah, 20–27, IEEE Press.

    Google Scholar

    Sterling LS and Yalcinalp LÜ, 1996. “Logic programming and software engineering” Knowledge Engineering Review (this issue).

    Google Scholar

    Takeuchi A, 1986. “Affinity between meta-interpreters and partial evaluation” In: Kugler HJ (ed.), Proceedings of Information Processing ‘86279–282, North-Holland.

    Google Scholar

    Takeuchi A and Furukawa K, 1986. “Partial evaluation of Prolog programs and its application to metaprogramming” In: Kugler HJ (ed.), Proceedings of Information Processing “86, 415–420, North-Holland.

    Google Scholar

    Tamaki H and Sato T, 1984. “Unfold/fold transformation of logic programs” In: Tärnlund SA (ed.), Proceedings of the Second International Conference on Logic Programming, Uppsala, Sweden, 127–138.

    Google Scholar

    Tarau P and Boyer M, 1990. “Elementary logic programs” In: Deransart P and Maluszynski J (eds.), Proceedings PLILP ‘90, 159–173, Springer-Verlag.

    Google Scholar

    Toni F and Kowalski R, 1995. “Reduction of abductive logic programs to normal logic programs” In: Sterling L (ed.), Proceedings of the 12th International Conference on Logic Programming367–381, MIT Press.

    Google Scholar

    Vasconcelos WW and Fuchs NE, 1996. “An opportunistic approach for logic program analysis and optimization using enhanced schema-based transformations” In: Proietti M (ed.), Logic Program Synthesis and Transformation, Proceedings LOPSTR ‘95, Utrecht, The Netherlands, Lecture Notes in Computer Science 1048, 174–188, Springer-Verlag.

    Google Scholar

  • Cite this article

    Alberto Pettorossi, Maurizio Proietti. 1996. Developing correct and efficient logic programs by transformation*. The Knowledge Engineering Review. 11:31 doi: 10.1017/S0269888900008031
    Alberto Pettorossi, Maurizio Proietti. 1996. Developing correct and efficient logic programs by transformation*. The Knowledge Engineering Review. 11:31 doi: 10.1017/S0269888900008031

Article Metrics

Article views(18) PDF downloads(55)

Other Articles By Authors

RESEARCH ARTICLE   Open Access    

Developing correct and efficient logic programs by transformation*

The Knowledge Engineering Review  11 Article number: 10.1017/S0269888900008031  (1996)  |  Cite this article

Abstract: The complex process of deriving programs from specifications is often divided into the following three steps: (i) the derivation of formal specifications from the informal ones; (ii) the validation of the formal specifications; and (iii) the derivation of executable programs from the formal specifications.

    • Copyright © Cambridge University Press 19961996Cambridge University Press
References (62)
  • About this article
    Cite this article
    Alberto Pettorossi, Maurizio Proietti. 1996. Developing correct and efficient logic programs by transformation*. The Knowledge Engineering Review. 11:31 doi: 10.1017/S0269888900008031
    Alberto Pettorossi, Maurizio Proietti. 1996. Developing correct and efficient logic programs by transformation*. The Knowledge Engineering Review. 11:31 doi: 10.1017/S0269888900008031
  • Catalog

      /

      DownLoad:  Full-Size Img  PowerPoint
      Return
      Return