J. P. Gallagher
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.
- 1.K. Benkerimi and J.W. Lloyd. A partial evaluation procedure for logic programs. In S.K. Debray and M. Hermenegildo, editors, Proceedings of the North American Conjerence on Logw Programming, Austin, pages 343-358, MIT Press, 1990. Google Scholar
Digital Library
- 2.D. Chan and M. Wallace. A treatment of negation during partial evaluation. In H. Abramson and M.H. Rogers, editors, Meta-Programming in Logic Programming, MIT Press, 1989. Google ScholarDigital Library
- 3.C. Chang and R.C.-T Lee. Symbolic Logic and Mechanical Theorem Promng. Academic Press, 1973. Google ScholarDigital Library
- 4.O. Danvy. Tutorial notes on partial evaluation. In 20th Annual A CM SIGPLAN-SIGACT Symposium on Principles Of programming Languages, Charleston, Sth. Carolina, Janu~ry 1993. Google ScholarDigital Library
- 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.Google Scholar
- 6.D.A. de Waal and J. Gallagher. Specialising a Theorem Prover. Technical Report CSTR-92-33, University of Bristol, November 1992.Google Scholar
- 7.H. Fujita. Art Algorithm for Partial Evaluation with Constraints. Technical Report TM-0484, ICOT, August 1991.Google Scholar
- 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.Google Scholar
- 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.Google Scholar
- 10.J. Gallagher. A System }or Specialising Logic programs. Technical Report TR-91-32, University of Bristol, November 1991.Google Scholar
- 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.Google Scholar
- 12.J. Gallagher and M. Bruynooghe. The derivation of an algorithm for program specialisation. New Generation Computing, 6(2), 1991.Google Scholar
- 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.Google Scholar
- 14.J. Gallagher, M. Codish, and E.Y. Shapiro. Specialisation of prolog and fcp programs using abstract interpretation. New Generation Computing, 6:159-186, 1988. Google ScholarDigital Library
- 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.Google Scholar
- 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.Google Scholar
- 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.Google Scholar
- 18.P.M. Hill and J.W. Lloyd. Analysis of meta- programs. In H. Abramson and M.H. Rogers, editors, Meta-Prograrnming in Logic Programming, MIT Press, 1989. Google ScholarDigital Library
- 19.P.M. Hill and J.W. Lloyd. The GS"del report. Technical Report TR-91-02, University of Bristol, March 1991.Google Scholar
- 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.Google Scholar
- 21.H.J. Komorowski. Partial evaluation as a means for inferencing data structures in an applicative language" a theory and implementation in the case of prolog. In 9th A CM Symposium on Principles of Programming Languages; Albuquerque, New Mexico, pages 255 - 267, 1982. Google ScholarDigital Library
- 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.Google Scholar
- 23.A. Lakhotia. A Workbench for Developing Logic Programs By Stepwise Enhancement. PhD thesis, Dept. of Computer Engineering ~nd Science, Case Western Reserve University, 1989. Google ScholarDigital Library
- 24.J. Lam. Control Structures in Partial Evaluation of Pure Prolog. Technical Report Masters Thesis, Department of Computational Science, University of Saskatchewan, 1989.Google Scholar
- 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.Google Scholar
- 26.J.W. Lloyd. Foundations of Logic Programming: 2nd Edition. Springer-Verlag, 1987. Google ScholarDigital Library
- 27.J.W. Lloyd and J.C. Shepherdson. Partial Evaluation in Logic Programming. Journal of Logic Programming, 11(3 & 4):217-242, 1991. Google ScholarDigital Library
- 28.D.W. Loveland. Automated theorem proving: a log, cal basis. North-Holland, 1978. Google ScholarDigital Library
- 29.D. De Schreye M. Bruynooghe and B. Krekels. Compiling control. Journal of Logic Programming, 6):135-162, 1989. Google ScholarDigital Library
- 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.Google Scholar
- 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.Google Scholar
- 32.D.L. Poole and R. Goebel. Gracefully ~dding negation and disjunction to Prolog. In E. Shapiro, editor, Third International Conference on Logic Programming, pages 635-641, Lecture Notes in Computer Science, Springer-Verlag, 1986. Google ScholarDigital Library
- 33.S. Safra and E.Y. Shapiro. Meta interpreters for real. In H-J. Kugler, editor, Proc. 1FIP'86, Dublin, North- Holland, 1986.Google Scholar
- 34.D. Sahlin. An Automatic Partial Evaluator for Full Prolog. PhD thesis, The Royal Institute of Technology, 1991.Google Scholar
- 35.D. Sahfin. The mixtus approach to ~utomatic partim evaluation for full prolog. In S. Debray and M. Hermenegildo, editors, Proceedings of the North American Conference on Logic Programming, MIT Press, 1990. Google ScholarDigital Library
- 36.H. Seld. On the power of Alexander templates. In Proceedings of the 8th A CM SIGACT-SIGMOD- SIGART Symposium on Principles of Database Systems, Philadelphia, Pennsylvania, 1989. Google ScholarDigital Library
- 37.D. Smith. Partial evaluation of pattern matching in constraint logic programming languages. In PEPM'91, Proc. of the A CM Symposium on Partial Evaluation and Semantics-Based Program Transformation, SIC- PLAN Notices Vol. 26, No. 9, September 1991. Google ScholarDigital Library
- 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.Google Scholar
- 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.Google Scholar
- 40.A. Takeuchi. Affinity between meta interpreters and partial evaluation. In H-J. Kugler, editor, Proc. IFIP'86, Dublin, North-Holland, 1986.Google Scholar
- 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.Google Scholar
- 42.E. Yardeni and E.Y. Shapiro. A type system for logic programs. Journal of Logic Programm,ng, 10(2):125- 154, 1990. Google ScholarDigital Library
Index Terms
- Tutorial on specialisation of logic programs
Recommendations
Paraconsistent Logic Programs
JELIA '02: Proceedings of the European Conference on Logics in Artificial IntelligenceWe propose a framework which extends Antitonic Logic Programs [2] to an arbitrary complete bilattice of truth-values, where belief and doubt are explicitly represented. Based on Fitting's ideas, this framework allows a precise definition of important ...
A Fixpoint Semantics and an SLD-Resolution Calculus for Modal Logic Programs
We propose a modal logic programming language called MProlog, which is as expressive as the general modal Horn fragment. We give a fixpoint semantics and an SLD-resolution calculus for MProlog in all of the basic serial modal logics KD, T, KDB, B, KD4, ...
Reviews
Kevin Denis Reilly
Specialization of logic programs currently depends heavily on partial evaluation (PE) for theoretical foundations and core methods. For example, a “basic” PE algorithm based on the theory provides an opening for abstract interpretation in effecting global termination. If real metaprogramming specializations or AI applications, for example, are goals, specialization includes efficiency considerations, such as avoidance of such problems as poor control choices, expansive use of storage, and loss of program indexing information. In order to cover all these topics, Gallagher sacrifices proofs and provides abundant examples keyed to topics such as renaming for structure specialization (string matching), abstract interpretation (list reversal and a model elimination prover), and metaprogram specialization (an interpreter for ground representation of programs). The author's “SP” implementation is employed in the examples and in support of other experimentally based claims, such as the choice of unfolding rules. The reader needs a background in logic programming fundamentals along with knowledge of programming languages, especially Prolog and LISP, to which comparisons are made. A few typos mar the paper slightly, and unfolding is discussed before it is defined. The paper's level of difficulty varies, partly because of differences in the depth of the exposition and the breadth of the subject. Several references cite publications that exist only as technical reports or proceedings paper s; “tutorial” needs to be understood in this light. The paper's strengths include its broad scope, connecting theory and practice, and its part in a plea elaborated over several papers (by Gallagher and others) for greater exploitation of program analysis techniques in logic program specialization.
Access critical reviews of Computing literature here
Become a reviewer for Computing Reviews.
Comments