[go: up one dir, main page]
More Web Proxy on the site http://driver.im/
Skip to main content
Springer Nature Link
Log in

Logic Program Specialisation

  • Conference paper
Partial Evaluation (DIKU 1998)

Part of the book series: Lecture Notes in Computer Science ((LNAI,volume 1706))

Included in the following conference series:

Abstract

Declarative programming languages, are high-level programming languages in which one only has to state what is to be computed and not necessarily how it is to be computed. Logic programming and functional programming are two prominent members of this class of programming languages. While functional programming is based on the λ-calculus, logic programming has its roots in first-order logic and automated theorem proving. Both approaches share the view that a program is a theory and execution consists in performing deduction from that theory.

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

Access this chapter

Log in via an institution

Institutional subscriptions

Preview

Unable to display preview. Download preview PDF.

Unable to display preview. Download preview PDF.

Similar content being viewed by others

References

  1. E. Albert, M. Alpuente, M. Falaschi, P. Julián and G. Vidal. Improving Control in Functional Logic Program Specialization. In G. Levi, editor, Static Analysis. Proceedings of SAS’98, LNCS 1503, pages 262–277, Pisa, Italy, September 1998. Springer-Verlag.

    Chapter  Google Scholar 

  2. M. Alpuente, M. Falaschi, and G. Vidal. Narrowing-driven partial evaluation of functional logic programs. In H. Riis Nielson, editor, Proceedings of the 6th European Symposium on Programming, ESOP’96, LNCS 1058, pages 45–61. Springer-Verlag, 1996.

    Google Scholar 

  3. L. O. Andersen. Partial evaluation of C and automatic compiler generation. In U. Kastens and P. Pfahler, editors, 4th International Conference on Compiler Construction, LNCS 641, pages 251–257, Paderborn, Germany, 1992. Springer-Verlag.

    Chapter  Google Scholar 

  4. L. O. Andersen. Program Analysis and Specialization for the C Programming Language. PhD thesis, DIKU, University of Copenhagen, May 1994. (DIKU report 94/19).

    Google Scholar 

  5. K. R. Apt. Introduction to logic programming. In J. van Leeuwen, editor, Handbook of Theoretical Computer Science, chapter 10, pages 495–574. North-Holland Amsterdam, 1990.

    Google Scholar 

  6. K. R. Apt. From Logic Programming to Prolog. Prentice Hall, 1997.

    Google Scholar 

  7. K. R. Apt and R. N. Bol. Logic programming and negation: A survey. The Journal of Logic Programming, 19 & 20:9–72, May 1994.

    Article  MathSciNet  MATH  Google Scholar 

  8. K. R. Apt and H. Doets. A new definition of SLDNF-resolution. The Journal of Logic Programming, 8:177–190, 1994.

    Article  MathSciNet  MATH  Google Scholar 

  9. K. R. Apt and M. H. van Emden. Contributions to the theory of logic programming. Journal of the ACM, 29(3):841–862, 1982.

    Article  MathSciNet  MATH  Google Scholar 

  10. K. Benkerimi and P. M. Hill. Supporting transformations for the partial evaluation of logic programs. Journal of Logic and Computation, 3(5):469–486, October 1993.

    Article  MathSciNet  MATH  Google Scholar 

  11. K. Benkerimi and J. W. Lloyd. A partial evaluation procedure for logic programs. In S. Debray and M. Hermenegildo, editors, Proceedings of the North American Conference on Logic Programming, pages 343–358. MIT Press, 1990.

    Google Scholar 

  12. R. Bol. Loop checking in partial deduction. The Journal of Logic Programming, 16(1&2):25–46, 1993.

    Article  MathSciNet  MATH  Google Scholar 

  13. A. Bondorf. Towards a self-applicable partial evaluator for term rewriting systems. In D. Bjørner, A. P. Ershov, and N. D. Jones, editors, Partial Evaluation and Mixed Computation, pages 27–50. North-Holland, 1988.

    Google Scholar 

  14. A. Bondorf. A self-applicable partial evaluator for term rewriting systems. In J. Diaz and F. Orejas, editors, TAPSOFT’89, Proceedings of the International Joint Conference on Theory and Practice of Software Development, LNCS 352, pages 81–96, Barcelona, Spain, March 1989. Springer-Verlag.

    Google Scholar 

  15. A. Bossi and N. Cocco. Preserving universal termination through unfold/fold. In G. Levi and M. Rodriguez-Artalejo, editors, Proceedings of the Fourth International Conference on Algebraic and Logic Programming, LNCS 850, pages 269–286, Madrid, Spain, 1994. Springer-Verlag.

    Chapter  Google Scholar 

  16. A. Bossi, N. Cocco, and S. Dulli. A method for specialising logic programs. ACM Transactions on Programming Languages and Systems, 12(2):253–302, 1990.

    Article  Google Scholar 

  17. A. Bossi, N. Cocco, and S. Etalle. Transformation of left terminating programs: The reordering problem. In M. Proietti, editor, Logic Program Synthesis and Transformation. Proceedings of LOPSTR’95, LNCS 1048, pages 33–45, Utrecht, The Netherlands, September 1995. Springer-Verlag.

    Chapter  Google Scholar 

  18. M. Bruynooghe, D. De Schreye, and B. Martens. A general criterion for avoiding infinite unfolding during partial deduction. New Generation Computing, 11(1):47–79, 1992.

    Article  MATH  Google Scholar 

  19. R. M. Burstall and J. Darlington. A transformation system for developing recursive programs. Journal of the ACM, 24(1):44–67, 1977.

    Article  MathSciNet  MATH  Google Scholar 

  20. D. Chan. Constructive negation based on the completed database. In Proceedings of the Joint International Conference and Symposium on Logic Programming, pages 111–125, Seattle, 1988. IEEE, MIT Press.

    Google Scholar 

  21. D. Chan and M. Wallace. A treatment of negation during partial evaluation. In H. Abramson and M. Rogers, editors, Meta-Programming in Logic Programming, Proceedings of the Meta88 Workshop, June 1988, pages 299–318. MIT Press, 1989.

    Google Scholar 

  22. K. L. Clark. Negation as failure. In H. Gallaire and J. Minker, editors, Logic and Data Bases, pages 293–322. Plenum Press, 1978.

    Google Scholar 

  23. W. Clocksin and C. Mellish. Programming in Prolog (Third Edition). Springer-Verlag, 1987.

    Google Scholar 

  24. C. Consel and O. Danvy. Tutorial notes on partial evaluation. In Proceedings of ACM Symposium on Principles of Programming Languages (POPL≐93), Charleston, South Carolina, January 1993. ACM Press.

    Google Scholar 

  25. D. De Schreye and S. Decorte. Termination of logic programs: The never ending story. The Journal of Logic Programming, 19 & 20:199–260, May 1994.

    Article  MathSciNet  MATH  Google Scholar 

  26. D. De Schreye, M. Leuschel, and B. Martens. Tutorial on program specialisation (abstract). In J. W. Lloyd, editor, Proceedings of ILPS’95, the International Logic Programming Symposium, Portland, USA, December 1995. MIT Press.

    Google Scholar 

  27. M. Denecker. Knowledge Representation and Reasoning in Incomplete Logic Programming. PhD thesis, Department of Computer Science, K.U.Leuven, 1993.

    Google Scholar 

  28. P. Derensart, A. Ed-Dbali, and L. Cervoni. Prolog: The Standard, Reference Manual. Springer-Verlag, 1996.

    Google Scholar 

  29. N. Dershowitz. Termination of rewriting. Journal of Symbolic Computation, 3:69–116, 1987.

    Article  MathSciNet  MATH  Google Scholar 

  30. N. Dershowitz and J.-P. Jouannaud. Rewrite systems. In J. van Leeuwen, editor, Handbook of Theoretical Computer Science, Vol. B, pages 243–320. Elsevier, MIT Press, 1990.

    Google Scholar 

  31. N. Dershowitz and Z. Manna. Proving termination with multiset orderings. Communications of the ACM, 22(8):465–476, 1979.

    Article  MathSciNet  MATH  Google Scholar 

  32. K. Doets. Levationis laus. Journal of Logic and Computation, 3(5):487–516, 1993.

    Article  MathSciNet  MATH  Google Scholar 

  33. K. Doets. Prom Logic to Logic Programming. MIT Press, 1994.

    Google Scholar 

  34. W. Drabent. What is failure ? An apporach to constructive negation. Acta Informatica, 32:27–59, 1995.

    Article  MathSciNet  MATH  Google Scholar 

  35. A. Ershov. Mixed computation: Potential applications and problems for study. Theoretical Computer Science, 18:41–67, 1982.

    Article  MathSciNet  MATH  Google Scholar 

  36. M. Fitting. First-Order Logic and Automated Theorem Proving. Springer-Verlag, 1990.

    Google Scholar 

  37. H. Pujita and K. Purukawa. A self-applicable partial evaluator and its use in incremental compilation. New Generation Computing, 6(2 & 3):91–118, 1988.

    Google Scholar 

  38. D. A. Puller and S. Abramsky. Mixed computation of prolog programs. New Generation Computing, 6(2 & 3):119–141, June 1988.

    MATH  Google Scholar 

  39. J. Gallagher. A system for specialising logic programs. Technical Report TR-91-32, University of Bristol, November 1991.

    Google Scholar 

  40. J. Gallagher. Tutorial on specialisation of logic programs. In Proceedings of PEPM’93, the ACM Sigplan Symposium on Partial Evaluation and Semantics-Based Program Manipulation, pages 88–98. ACM Press, 1993.

    Google Scholar 

  41. J. Gallagher and M. Bruynooghe. The derivation of an algorithm for program specialisation. New Generation Computing, 9(3 & 4):305–333, 1991.

    Article  MATH  Google Scholar 

  42. R. Glück and M. H. Sørensen. Partial deduction and driving are equivalent. In M. Hermenegildo and J. Penjam, editors, Programming Language Implementation and Logic Programming. Proceedings, Proceedings of PLILP’94, LNCS 844, pages 165–181, Madrid, Spain, 1994. Springer-Verlag.

    Chapter  Google Scholar 

  43. R. Glück and M. H. Sørensen. A roadmap to supercompilation. In O. Danvy, R. Glück, and P. Thiemann, editors, Proceedings of the 1996 Dagstuhl Seminar on Partial Evaluation, LNCS 1110, pages 137–160, Schloß Dagstuhl, 1996. Springer-Verlag.

    Google Scholar 

  44. C. A. Gurr. A Self-Applicable Partial Evaluator for the Logic Programming Language Gödel. PhD thesis, Department of Computer Science, University of Bristol, January 1994.

    Google Scholar 

  45. J. Herbrand. Investigations in proof theory. In J. van Heijenoort, editor, From Frege to Gödel: A Source Book in Mathematical Logic, 1879–1931, pages 525–581. Harvard University Press, 1967.

    Google Scholar 

  46. G. Higman. Ordering by divisibility in abstract algebras. Proceedings of the London Mathematical Society, 2:326–336, 1952.

    Article  MathSciNet  MATH  Google Scholar 

  47. P. Hill and J. W. Lloyd. The Gödel Programming Language. MIT Press, 1994.

    Google Scholar 

  48. J.-M. Jacquet. Constructing Logic Programs. Wiley, Chichester, 1993.

    MATH  Google Scholar 

  49. N. D. Jones. The essence of program transformation by partial evaluation and driving. In M. S. Neil D. Jones, Masami Hagiya, editor, Logic, Language and Computation, LNCS 792, pages 206–224. Springer-Verlag, 1994.

    Chapter  Google Scholar 

  50. N. D. Jones. An introduction to partial evaluation. ACM Computing Surveys, 28(3):480–503, September 1996.

    Article  Google Scholar 

  51. N. D. Jones, C. K. Gomard, and P. Sestoft. Partial Evaluation and Automatic Program Generation. Prentice Hall, 1993.

    Google Scholar 

  52. S. Kleene. Introduction to Metamathematics. van Nostrand, Princeton, New Jersey, 1952.

    MATH  Google Scholar 

  53. H.-P. Ko and M. E. Nadel. Substitution and refutation revisited. In K. Purukawa, editor, Logic Programming: Proceedings of the Eighth International Conference, pages 679–692. MIT Press, 1991.

    Google Scholar 

  54. 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 Ninth Annual ACM SIGACT-SIGPLAN Symposium on Principles of Programming Languages. Albuquerque, New Mexico, pages 255–267, 1982.

    Google Scholar 

  55. J. Komorowski. An introduction to partial deduction. In A. Pettorossi, editor, Proceedings Meta’92, LNCS 649, pages 49–69. Springer-Verlag, 1992.

    Google Scholar 

  56. R. Kowalski. Predicate logic as a programming language. In Proceedings IFIP Congress, pages 569–574. IEEE, 1974.

    Google Scholar 

  57. J. B. Kruskal. Well-quasi ordering, the tree theorem, and Vazsonyi’s conjecture. Transactions of the American Mathematical Society, 95:210–225, 1960.

    MathSciNet  MATH  Google Scholar 

  58. L. Lafave and J. Gallagher. Constraint-based partial evaluation of rewriting-based functional logic programs. In N. Fuchs, editor, Proceedings of the International Workshop on Logic Program Synthesis and Transformation (LOPSTR’97), LNCS 1463, Leuven, Belgium, July 1998.

    Google Scholar 

  59. J.-L. Lassez, M. Maher, and K. Marriott. Unification revisited. In J. Minker, editor, Foundations of Deductive Databases and Logic Programming, pages 587–625. Morgan-Kaufmann, 1988.

    Google Scholar 

  60. M. Leuschel. Advanced Logic Program Specialisation. In J. Hatcliff, T. Mogensen, and P. Thiemann, editors, DIKU 1998 International Summerschool on Partial Evaluation, LNCS 1706, pages 271–292, Copenhagen, Denmark, July 1998. Springer-Verlag. In this volume.

    Google Scholar 

  61. M. Leuschel. On the power of homeomorphic embedding for online termination. In G. Levi, editor, Static Analysis. Proceedings of SAS’98, LNCS 1503, pages 230–245, Pisa, Italy, September 1998. Springer-Verlag.

    Google Scholar 

  62. M. Leuschel and D. De Schreye. Towards creating specialised integrity checks through partial evaluation of meta-interpreters. In Proceedings of PEPM’95, the ACM Sigplan Symposium on Partial Evaluation and Semantics-Based Program Manipulation, pages 253–263, La Jolla, California, June 1995. ACM Press.

    Google Scholar 

  63. M. Leuschel and D. De Schreye. Constrained partial deduction and the preservation of characteristic trees. New Generation Computing, 16(3):283–342, 1998.

    Article  Google Scholar 

  64. M. Leuschel and D. De Schreye. Creating specialised integrity checks through partial evaluation of meta-interpreters. The Journal of Logic Programming, 36:149–193, 1998.

    Article  MathSciNet  MATH  Google Scholar 

  65. M. Leuschel, B. Martens, and D. De Schreye. Controlling generalisation and polyvariance in partial deduction of normal logic programs. ACM Transactions on Programming Languages and Systems, 20(1):208–258, January 1998.

    Article  Google Scholar 

  66. M. Leuschel, B. Martens, and K. Sagonas. Preserving termination of tabled logic programs while unfolding. In N. Fuchs, editor, Proceedings of the International Workshop on Logic Program Synthesis and Transformation (LOPSTR’97), LNCS 1463, Leuven, Belgium, July 1998.

    Google Scholar 

  67. M. Leuschel and M. H. Sørensen. Redundant argument filtering of logic programs. In J. Gallagher, editor, Proceedings of the International Workshop on Logic Program Synthesis and Transformation (LOPSTR’96), LNCS 1207, pages 83–103, Stockholm, Sweden, August 1996. Springer-Verlag.

    Chapter  Google Scholar 

  68. J. W. Lloyd. Foundations of Logic Programming. Springer-Verlag, 1987.

    Google Scholar 

  69. J. W. Lloyd and J. C. Shepherdson. Partial evaluation in logic programming. The Journal of Logic Programming, 11(3& 4):217–242, 1991.

    Article  MathSciNet  MATH  Google Scholar 

  70. A. Martelli and U. Montanari. An efficient unification algorithm. ACM Transactions on Programming Languages and Systems, 4(2):258–282, April 1982.

    Article  MATH  Google Scholar 

  71. B. Martens. On the Semantics of Meta-Programming and the Control of Partial Deduction in Logic Programming. PhD thesis, K.U. Leuven, February 1994.

    Google Scholar 

  72. B. Martens and D. De Schreye. Automatic finite unfolding using well-founded measures. The Journal of Logic Programming, 28(2):89–146, August 1996.

    Article  MathSciNet  MATH  Google Scholar 

  73. B. Martens, D. De Schreye, and T. Horváth. Sound and complete partial deduction with unfolding based on well-founded measures. Theoretical Computer Science, 122(1–2):97–117, 1994.

    Article  MathSciNet  MATH  Google Scholar 

  74. B. Martens and J. Gallagher. Ensuring global termination of partial deduction while allowing flexible polyvariance. In L. Sterling, editor, Proceedings ICLP’95, pages 597–613, Kanagawa, Japan, June 1995. MIT Press.

    Google Scholar 

  75. A. Miniuissi and D. J. Sherman. Squeezing intermediate construction in equational programs. In O. Danvy, R. Glück, and P. Thiemann, editors, Proceedings of the 1996 Dagstuhl Seminar on Partial Evaluation, LNCS 1110, pages 284–302, Schloß Dagstuhl, 1996. Springer-Verlag.

    Google Scholar 

  76. T. Mogensen and A. Bondorf. Logimix: A self-applicable partial evaluator for Prolog. In K.-K. Lau and T. Clement, editors, Logic Program Synthesis and Transformation. Proceedings of LOPSTR’92, pages 214–227. Springer-Verlag, 1992.

    Google Scholar 

  77. L. Naish. Higher-order logic programming in Prolog. Technical Report 96/2, Department of Computer Science, University of Melbourne, 1995.

    Google Scholar 

  78. U. Nilsson and J. Małuszyński. Logic, Programming and Prolog. Wiley, Chichester, 1990.

    MATH  Google Scholar 

  79. S. Owen. Issues in the partial evaluation of meta-interpreters. In H. Abramson and M. Rogers, editors, Meta-Programming in Logic Programming, Proceedings of the Meta88 Workshop, June 1988, pages 319–339. MIT Press, 1989.

    Google Scholar 

  80. M. Paterson and M. Wegman. Linear unification. Journal of Computer and System Sciences, 16(2):158–167, 1978.

    Article  MathSciNet  MATH  Google Scholar 

  81. A. Pettorossi and M. Proietti. Transformation of logic programs: Foundations and techniques. The Journal of Logic Programming, 19&20:261–320, May 1994.

    Article  MathSciNet  MATH  Google Scholar 

  82. S. Prestwich. An unfold rule for full Prolog. In K.-K. Lau and T. Clement, editors, Logic Program Synthesis and Transformation. Proceedings of LOPSTR’92, Workshops in Computing, pages 199–213, University of Manchester, 1992. Springer-Verlag.

    Google Scholar 

  83. M. Proietti and A. Pettorossi. Semantics preserving transformation rules for Prolog. In Proceedings of the ACM Symposium on Partial Evaluation and Semantics based Program Manipulation, PEPM’91, Sigplan Notices, Vol. 26, N. 9, pages 274–284, Yale University, New Haven, U.S.A., 1991.

    Google Scholar 

  84. M. Proietti and A. Pettorossi. The loop absorption and the generalization strategies for the development of logic programs and partial deduction. The Journal of Logic Programming, 16(1 & 2):123–162, May 1993.

    Article  MathSciNet  MATH  Google Scholar 

  85. T. C. Przymusinksi. On the declarative and procedural semantics of logic programs. Journal of Automated Reasoning, 5(2):167–205, 1989.

    MathSciNet  Google Scholar 

  86. R. Reiter. On closed world data bases. In H. Gallaire and J. Minker, editors, Logic and Data Bases, pages 55–76. Plenum Press, 1978.

    Google Scholar 

  87. A. Robinson. A machine-oriented logic based on the resolution principle. Journal of the ACM, 12(1):23–41, 1965.

    Article  MathSciNet  MATH  Google Scholar 

  88. D. Sahlin. Mixtus: An automatic partial evaluator for full Prolog. New Generation Computing, 12(1):7–51, 1993.

    Article  MATH  Google Scholar 

  89. J. C. Shepherdson. Language and equality theory in logic programming. Technical Report PM-91-02, University of Bristol, 1991.

    Google Scholar 

  90. M. H. Sørensen and R. Glück. Introduction to Supercompilation. In J. Hatcliff, T. Mogensen, and P. Thiemann, editors, DIKU 1998 International Summerschool on Partial Evaluation, LNCS 1706, pages 246–270, Copenhagen, Denmark, July 1998. Springer-Verlag. In this volume.

    Google Scholar 

  91. M. H. Sørensen and R. Glück. An algorithm of generalization in positive supercompilation. In J. W. Lloyd, editor, Proceedings of ILPS’95, the International Logic Programming Symposium, pages 465–479, Portland, USA, December 1995. MIT Press.

    Google Scholar 

  92. M. H. Sørensen, R. Glück, and N. D. Jones. Towards unifying partial evaluation, deforestation, supercompilation, and GPC. In D. Sannella, editor, Programming Languages and Systems — ESOP’ 94. Proceedings, LNCS 788, pages 485–500, Edinburgh, Scotland, 1994. Springer-Verlag.

    Chapter  Google Scholar 

  93. M. H. Sørensen, R. Glück, and N. D. Jones. A positive supercompiler. Journal of Functional Programming, 6(6):811–838, 1996.

    Article  MATH  Google Scholar 

  94. L. Sterling and R. D. Beer. Metainterpreters for expert system construction. The Journal of Logic Programming, 6(1 & 2):163–178, 1989.

    Article  Google Scholar 

  95. L. Sterling and E. Shapiro. The Art of Prolog. MIT Press, 1986.

    Google Scholar 

  96. P. J. Stuckey. Constructive negation for constraint logic programming. In Proceedings, Sixth Annual IEEE Symposium on Logic in Computer Science, pages 328–339, Amsterdam, The Netherlands, July 1991. IEEE Computer Society Press.

    Google Scholar 

  97. P. J. Stuckey. Negation and constraint logic programming. Information and Computation, 118(1):12–33, April 1995.

    Article  MathSciNet  MATH  Google Scholar 

  98. V. F. Turchin. The concept of a supercompiler. ACM Transactions on Programming Languages and Systems, 8(3):292–325, 1986.

    Article  MATH  Google Scholar 

  99. D. H. D. Warren. Higher-order extensions to Prolog: Are they needed? In J. E. Hayes, D. Michie, and Y.-H. Pao, editors, Machine Intelligence 10, pages 441–454. Ellis Horwood Ltd., Chicester, England, 1982.

    Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Department of Electronics and Computer Science, University of Southampton Highfield, Southampton, SO17 1BJ, UK

    Michael Leuschel

Authors
  1. Michael Leuschel
    View author publications

    You can also search for this author in PubMed Google Scholar

Editor information

Editors and Affiliations

  1. Department of Computing and Information Sciences, Kansas State University, 234 Nichols Hall, Manhattan, KS, 66506, USA

    John Hatcliff

  2. DIKU, Københavns Universitet, Universitetsparken 1, DK-2100, København Ø, Denmark

    Torben Æ Mogensen

  3. Institut für Informatik, Universität Freiburg, Universitätsgelände Flugplatz, D-79110, Freiburg i.Br., Germany

    Peter Thiemann

Rights and permissions

Reprints and permissions

Copyright information

© 1999 Springer-Verlag Berlin Heidelberg

About this paper

Cite this paper

Leuschel, M. (1999). Logic Program Specialisation. In: Hatcliff, J., Mogensen, T.Æ., Thiemann, P. (eds) Partial Evaluation. DIKU 1998. Lecture Notes in Computer Science, vol 1706. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-47018-2_5

Download citation

  • DOI: https://doi.org/10.1007/3-540-47018-2_5

  • Publisher Name: Springer, Berlin, Heidelberg

  • Print ISBN: 978-3-540-66710-0

  • Online ISBN: 978-3-540-47018-2

  • eBook Packages: Springer Book Archive

Publish with us

Policies and ethics

Search

Navigation