Tutorial on specialisation of logic programs

ABSTRACT

In this tutorial the specialisation of declarative logic programs is presented. The main correctness results are given, and the outline of a basic algorithm for partial evaluation of a logic program with respect to a goal. The practical considerations of gaining efficiency (and not losing any) are discussed. A renaming scheme for performing structure specialisation is then described, and illustrated on a well-known string matching example. The basic algorithm is enhanced by incorporating abstract interpretation. A two-phase specialisation is then described and illustrated, in which partial evaluation is followed by the detection and removal of useless clauses. This is shown for the specialisation of a proof procedure for first order logic. The specialisation of meta programs is very important in logic programming, and the ground representation for object programs has to be handled. Some techniques for doing this are described. Comparisons are made in the tutorial to similar work in other programming languages, and the similarities and differences between them and logic program specialisation is discussed.

REFERENCES

• 1: Kerima Benkerimi , John W. Lloyd, A partial evaluation procedure for logic programs, Proceedings of the 1990 North American conference on Logic programming, p.343-358, January 1990, Austin, Texas, United States
• 2: D. Chan , M. Wallace, A treatment of negation during partial evaluation, Meta-programming in logic programming, MIT Press, Cambridge, MA, 1989
• 3: Chin-Liang Chang , Richard C. Lee , Richard Char-Tung Lee, Symbolic Logic and Mechanical Theorem Proving, Academic Press, Inc., Orlando, FL, 1997
• 4: Charles Consel , Olivier Danvy, Tutorial notes on partial evaluation, Proceedings of the 20th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.493-501, March 1993, Charleston, South Carolina, United States [doi>10.1145/158511.158707]
• 5: D.A. de Waal and J. Gallagher. Specialisation of a unification algorithm. In T. Clement and K.-K. Lau, editors, Logic Program Synthesis and Transformation, Manchester 1991, pages 205-221, Workshops in Computing, Springer-Verlag, 1992.
• 6: D.A. de Waal and J. Gallagher. Specialising a Theorem Prover. Technical Report CSTR-92-33, University of Bristol, November 1992.
• 7: H. Fujita. Art Algorithm for Partial Evaluation with Constraints. Technical Report TM-0484, ICOT, August 1991.
• 8: H. Fujita and K. Furukawa. A self-applicable partial evaluator and its use in incremental compilation. In D. Bjerner, Ershov A, and N. Jones, editors, Proc. of PEPM, Workshop on partial evaluation and mixed computation, 1988.
• 9: J. Gallagher. Static analysis for logic program specialisation. In M. Billaud et al., editor, WSA-92: Analyse Statique, pages 285-294, Universitfi Bordeaux i, 1992.
• 10: J. Gallagher. A System }or Specialising Logic programs. Technical Report TR-91-32, University of Bristol, November 1991.
• 11: J. Gallagher. Transforming logic programs by specialising interpreters. In ECAI.86, Proc. of the 7th European Conference on Artificial Intelligence, Brighton, England, pages 109-t22, 1986.
• 12: J. Gallagher and M. Bruynooghe. The derivation of an algorithm for program specialisation. New Generation Computing, 6(2), 1991.
• 13: J. Gallagher and M. Bruynooghe. Some low-level source transformations for logic programs. In M. Bruynooghe, editor, Proceedings of Meta90 Workshop on Meta Programming in Logic, Leuven, Belgium, 1990.
• 14: J. Gallagher , M. Codish , E. Shapiro, Specialisation of Prolog and FCP programs using abstract interpretation, New Generation Computing, v.6 n.2-3, p.159-186, March-April 1988 [doi>10.1007/BF03037136]
• 15: 3. Gallagher and D.A. de Waal. Deletion of redundant unary type predicates from logic programs. In K.K. Lau and T. Clement, editors, Logic Program Synthesis and Trans}ormation, pages 151-167, Springer-Verlag, 1993.
• 16: J. Gallagher and D.A. de Waal. Regular Approximations of Logic Programs and Their Uses. Technical Report CSTR-92..06, University of Bristol, March 1992.
• 17: C. Gurr. Specialising the Ground Representation in the Logic progcarnming Language Gb'del. Technical Report, Department of Computer Science, University of Bristol, November 1992.
• 18: P. M. Hill , J. W. Lloyd, Analysis of meta-programs, Meta-programming in logic programming, MIT Press, Cambridge, MA, 1989
• 19: P.M. Hill and J.W. Lloyd. The GS"del report. Technical Report TR-91-02, University of Bristol, March 1991.
• 20: K. Kahn and M. Carisson. The compilation of prolog programs without the use of a prolog compiler. In International Conference on Fifth Generation Computer Systems, Tokyo, 1984.
• 21: H. Jan Komorowski, Partial evaluation as a means for inferencing data structures in an applicative language: a theory and implementation in the case of prolog, Proceedings of the 9th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.255-267, January 25-27, 1982, Albuquerque, Mexico [doi>10.1145/582153.582181]
• 22: H.J. Komorowski. Synthesis of Programs in the Framework of Partial Deduction. Technical Report 81, Department of Computer Science, /~bo Akademi, Lemmink~inengatan 14, SF-20520 Abo, Finland., 1989.
• 23: Arun Lakhotia, A workbench for developing logic programs by stepwise enhancement, Case Western Reserve University, Cleveland, OH, 1990
• 24: J. Lam. Control Structures in Partial Evaluation of Pure Prolog. Technical Report Masters Thesis, Department of Computational Science, University of Saskatchewan, 1989.
• 25: G. Levi and G. Sardu. "partial evaluation of rectaprograms in a multiple worlds logic language. In D. Bj0rner, Ershov A, and N. Jones, editors, Proc. of PEPM, Workshop on partial evaluation and mixed computation, 1988.
• 26: J. W. Lloyd, Foundations of logic programming; (2nd extended ed.), Springer-Verlag New York, Inc., New York, NY, 1987
• 27: J. W. Lloyd , J. C. Shepherdson, Partial evaluation in logic programming, Journal of Logic Programming, v.11 n.3-4, p.217-242, Oct./Nov. 1991 [doi>10.1016/0743-1066(91)90027-M]
• 28: Donald W Loveland, Automated theorem proving: A logical basis (Fundamental studies in computer science), sole distributor for the U.S.A. and Canada, Elsevier North-Holland, 1978
• 29: Maurice Bruynooghe , Danny de Schreye , Bruno Krekels, Compiling control, Journal of Logic Programming, v.6 n.1-2, p.135-162, Jan./Mar. 1989 [doi>10.1016/0743-1066(89)90033-2]
• 30: K. Marriott, L. Naish, and J-L. Lassez. Most specific logic programs. In Proceedings of the Fifth International Conference and Symposium on Logic Programming, Washington, August 1988.
• 31: T. Mogensen and A. Bondorf. Logimix: a selfapplicable partial evaluator for prolog. In K.K. Lau and T. Clement, editors, Logic Program Synthesis and Transformation, Springer-Verlag, 1993.
• 32: David L Poole , Randy Goebel, Gracefully adding negation and disjunction to Prolog, Proceedings on Third international conference on logic programming, p.635-641, September 1986, London, United Kingdom
• 33: S. Safra and E.Y. Shapiro. Meta interpreters for real. In H-J. Kugler, editor, Proc. 1FIP'86, Dublin, North- Holland, 1986.
• 34: D. Sahlin. An Automatic Partial Evaluator for Full Prolog. PhD thesis, The Royal Institute of Technology, 1991.
• 35: Dan Sahlin, The Mixtus approach to automatic partial evaluation of full Prolog, Proceedings of the 1990 North American conference on Logic programming, p.377-398, January 1990, Austin, Texas, United States
• 36: H. Seki, On the power of Alexander templates, Proceedings of the eighth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.150-159, March 1989, Philadelphia, Pennsylvania, United States [doi>10.1145/73721.73737]
• 37: Donald A. Smith, Partial evaluation of pattern matching in constraint logic programming languages, ACM SIGPLAN Notices, v.26 n.9, p.62-71, Sept. 1991
• 38: L. Sterling. Incremental flavor-mixing of metainterpreters for expert system construction. In Proc. 3rd Int. Symp. on Logic programming, Salt Lake City, Utah, pages 20-27, 1986.
• 39: M.E. Stickel. A Prolog Technology Theorem Prover. In International Synposium on Logic Programming, Atlantic City, NJ, pages 211-217, Feb. 6-9 1984.
• 40: A. Takeuchi. Affinity between meta interpreters and partial evaluation. In H-J. Kugler, editor, Proc. IFIP'86, Dublin, North-Holland, 1986.
• 41: R. Venken. Partial evalu~.tion of prolog and its application to source-to-source transformation and query optimisation. In Proceedings of ECAI'84, Pisa, 1984.
• 42: Eyal Yardeni , Ehud Shapiro, A type system for logic program, Journal of Logic Programming, v.10 n.2, p.125-153, Feb. 1991 [doi>10.1016/0743-1066(91)80002-U]

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.4 MATHEMATICAL LOGIC AND FORMAL LANGUAGES
      F.4.1 Mathematical Logic
          Subjects: Logic and constraint programming

Additional Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.2 Language Classifications

          Nouns: Prolog
      D.3.4 Processors
          Subjects: Interpreters

  F. Theory of Computation
  F.3 LOGICS AND MEANINGS OF PROGRAMS

General Terms:
Algorithms, Languages, Theory