Abstract
We consider the problem of specializing constraint logic programs w.r.t. constrained queries. We follow a transformational approach based on rules and strategies. The use of the rules ensures that the specialized program is equivalent to the initial program w.r.t. a given constrained query. The strategies guide the application of the rules so to derive an efficient specialized program. In this paper we address various issues concerning the development of an automated transformation strategy. In particular, we consider the problems of when and how we should unfold, replace constraints, introduce generalized clauses, and apply the contextual constraint replacement rule. We propose a solution to these problems by adapting to our framework various techniques developed in the field of constraint programming, partial evaluation, and abstract interpretation. In particular, we use: (i) suitable solvers for simplifying constraints, (ii) well-quasi-orders for ensuring the termination of the unfoldings and for activating clause generalizations, and (iii) widening operators for ensuring the termination of the generalization process.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
N. Bensaou and I. Guessarian. Transforming constraint logic programs. Theoretical Computer Science, 206:81–125, 1998.
A. Bossi, N. Cocco, and S. Dulli. A method for specializing logic programs. ACM Transactions on Programming Languages and Systems, 12(2):253–302, April 1990.
C. Consel and S. C. Khoo. Parameterized partial evaluation. ACM Transactions on Programming Languages and Systems, 15(3):463–493, 1993.
P. Cousot and R. Cousot. Abstract interpretation: A unified lattice model for static analysis of programs by construction of approximation of fixpoints. In Proceedings 4th ACM-SIGPLAN Symposium on Principles of Programming Languages (POPL’ 77), pages 238–252. ACM Press, 1977.
D. De Schreye, R. Glück, J. Jørgensen, M. Leuschel, B. Martens, and M. H. Sørensen. Conjunctive partial deduction: Foundations, control, algorithms, and experiments. Journal of Logic Programming, 41(2-3):231–277, 1999.
N. Dershowitz and J.-P. Jouannaud. Rewrite systems. In J. van Leeuwen, editor, Handbook of Theoretical Computer Science, volume B, pages 243–320. Elsevier, 1990.
S. Etalle and M. Gabbrielli. Transformations of CLP modules. Theoretical Computer Science, 166:101–146, 1996.
F. Fioravanti, A. Pettorossi, and M. Proietti. Rules and strategies for contextual specialization of constraint logic programs. In M. Leuschel, editor, Proceedings of the ICLP’99 Workshop on Optimization and Implementation of Declarative Programming Languages, WOID’ 99, Las Cruces University, New Mexico, USA, pages 1–9, December 2-3, 1999.
T. Frühwirth. Theory and practice of Constraint Handling Rules. Journal of Logic Programming, Special Issue on Constraint Logic Programming, pages 95–138, October 1998.
T. J. Hickey and D. A. Smith. Towards the partial evaluation of CLP languages. In Proceedings ACM Symposium on Partial Evaluation and Semantics Based Program Manipulation, PEPM’ 91, New Haven, CT, USA, SIGPLAN Notices, 26, 9, pages 43–51. ACM Press, 1991.
C. Holzbaur. OFAI clp(q,r) manual, Edition 1.3.2. Technical Report TR-95-09, Austrian Research Institute for Artificial Intelligence, Vienna, 1995.
J. Jaffar and M. Maher. Constraint logic programming: A survey. Journal of Logic Programming, 19/20:503–581, 1994.
J. Jaffar, M. Maher, K. Marriott, and P. Stuckey. The semantics of constraint logic programming. Journal of Logic Programming, 37:1–46, 1998.
N. D. Jones, C. K. Gomard, and P. Sestoft. Partial Evaluation and Automatic Program Generation. Prentice Hall, 1993.
M. Leuschel. Improving homeomorphic embedding for online termination. In P. Flener, editor, Proceedings of LOPSTR’98, Manchester, UK, June 1998, Lecture Notes in Computer Science 1559, pages 199–218. Springer-Verlag, 1999.
M. Leuschel, B. Martens, and D. De Schreye. Controlling generalization and polyvariance in partial deduction of normal logic programs. ACM Transactions on Programming Languages and Systems, 20(1):208–258, 1998.
M. Leuschel and D. De Schreye. Constrained partial deduction. In F. Bry, B. Freitag, and D. Seipel, editors, Proceedings of the 12th Workshop Logische Programmierung (WLP’97), pages 116–126, Munich, Germany, September 1997.
J. W. Lloyd and J. C. Shepherdson. Partial evaluation in logic programming. Journal of Logic Programming, 11:217–242, 1991.
M. J. Maher. A transformation system for deductive database modules with perfect model semantics. Theoretical Computer Science, 110:377–403, 1993.
K. Marriott and P. Stuckey. The 3 R’s of optimizing constraint logic programs: Refinement, Removal and Reordering. In POPL’93: Proceedings ACM SIGPLAN Symposium on Principles of Programming Languages, pages 334–344, 1993.
A. Pettorossi and M. Proietti. A theory of logic program specialization and generalization for dealing with input data properties. In O. Danvy, R. Glück, and P. Thiemann, editors, Proceedings of the Dagstuhl Seminar on Partial Evaluation, Lecture Notes in Computer Science 1110, pages 386–408. Springer-Verlag, 1996.
S. Prestwich. Online partial deduction of large programs. In Proceedings ACM Sigplan Symposium on Partial Evaluation and Semantics-Based Program Manipulation, PEPM’ 93, Copenhagen, Denmark, pages 111–118. ACM Press, 1993.
G. Puebla and M. Hermenegildo. Abstract multiple specialization and its application to program parallelization. J. of Logic Programming. Special Issue on Synthesis, Transformation and Analysis of Logic Programs, 41(2&3):279–316, November 1999.
D. Sahlin. Mixtus: An automatic partial evaluator for full Prolog. New Generation Computing, 12:7–51, 1993.
M. H. Sørensen and R. Glück. An algorithm of generalization in positive supercompilation. In J. W. Lloyd, editor, Proceedings of the 1995 International Logic Programming Symposium (ILPS’ 95), pages 465–479. MIT Press, 1995.
A. Wrzos-Kaminska. Partial evaluation in constraint logic programming. In Z. W. Ras and M. Michalewicz, editors, Proceedings of the 9th International Symposium on Foundations of Intelligent Systems, Zakopane, Poland, Lecture Notes in Computer Science 1079, pages 98–107. Springer-Verlag, 1996.
Author information
Authors and Affiliations
Rights and permissions
Copyright information
© 2001 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Fioravanti, F., Proietti, M., Pettorossi, A. (2001). Automated Strategies for Specializing Constraint Logic Programs. In: Logic Based Program Synthesis and Transformation. LOPSTR 2000. Lecture Notes in Computer Science, vol 2042. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-45142-0_8
Download citation
DOI: https://doi.org/10.1007/3-540-45142-0_8
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-42127-6
Online ISBN: 978-3-540-45142-6
eBook Packages: Springer Book Archive