Hostname: page-component-78c5997874-g7gxr Total loading time: 0 Render date: 2024-11-03T05:50:02.422Z Has data issue: false hasContentIssue false
  • English
  • Français

TCHR: a framework for tabled CLP

Published online by Cambridge University Press:  26 February 2008

TOM SCHRIJVERS ,
BART DEMOEN  and
DAVID S. WARREN
TOM SCHRIJVERS
Affiliation:
Dept. of Computer Science, K.U.Leuven, Belgium (e-mail: [email protected], [email protected])
BART DEMOEN
Affiliation:
Dept. of Computer Science, K.U.Leuven, Belgium (e-mail: [email protected], [email protected])
DAVID S. WARREN
Affiliation:
Dept. of Computer Science, State University of New York at Stony Brook, USA (e-mail: [email protected])
Get access Rights & Permissions [Opens in a new window]

Abstract

Tabled Constraint Logic Programming is a powerful execution mechanism for dealing with Constraint Logic Programming without worrying about fixpoint computation. Various applications, e.g. in the fields of program analysis and model checking, have been proposed. Unfortunately, a high-level system for developing new applications is lacking, and programmers are forced to resort to complicated ad hoc solutions.

This papers presents TCHR, a high-level framework for tabled Constraint Logic Programming. It integrates in a light-weight manner Constraint Handling Rules (CHR), a high-level language for constraint solvers, with tabled Logic Programming. The framework is easily instantiated with new application-specific constraint domains. Various high-level operations can be instantiated to control performance. In particular, we propose a novel, generalized technique for compacting answer sets.

Keywords

Constraint logic programmingConstraint handling rulesTabled execution
Type
Regular Papers
Information
Theory and Practice of Logic Programming , Volume 8 , Issue 4 , July 2008 , pp. 491 - 526
Copyright
Copyright © Cambridge University Press 2008

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

Clark, K. L. 1987. Negation as failure. In Logic and Databases, Gallaire, H. and Minker, J., Eds. Plenum Press, New York, 293–322.Google Scholar
Codish, M., Demoen, B., and Sagonas, K. 1998. Semantic-based program analysis for logic-based languages using XSB. International Journal of Software Tools for Technology Transfer 2 (1) (Jan.), 29–45.CrossRefGoogle Scholar
Cui, B. 2000. A System for Tabled Constraint Logic Programming. Ph.D. thesis, State University of New York at Stony Brook.Google Scholar
Cui, B. and Warren, D. S. 2000a. A system for tabled constraint logic programming. In CL 2000: Proceedings of the 1st International Conference on Computational Logic, Lloyd, J. W., Dahl, V., Furbach, U., Kerber, M., Lau, K.-K., Palamidessi, C., Pereira, L. M., Sagiv, Y., and Stuckey, P. J., Eds. Lecture Notes in Computer Science, vol. 1861. Springer Verlag, London, UK, 478–492.CrossRefGoogle Scholar
Cui, B. and Warren, D. S. 2000b. Attributed variables in XSB. In Electronic Notes in Theoretical Computer Science, Dutra, I. et al. , Eds. vol. 30. Elsevier, 67–80.Google Scholar
Demoen, B. 2004. hProlog. http://www.cs.kuleuven.be/~bmd/hProlog/.Google Scholar
Du, X., Ramakrishnan, C. R., and Smolka, S. A. 2000. Tabled resolution + constraints: A recipe for model checking real-time systems. In IEEE Real Time Systems Symposium. Orlando, Florida, 175–184.Google Scholar
Duck, G. J., García de la Banda, M., and Stuckey, P. J. 2004. Compiling ask constraints. In ICLP'04: Proceedings of the 20th International Conference on Logic Programming. Lecture Notes in Computer Science, vol. 3132. Springer Verlag, St-Malo, France, 105–119.Google Scholar
Duck, G. J., Stuckey, P. J., Garcíade la Banda, M. de la Banda, M., and Holzbaur, C. 2004. The refined operational semantics of constraint handling rules. In ICLP'04: Proceedings of the 20th International Conference on Logic Programming. Lecture Notes in Computer Science, vol. 3132. Springer Verlag, St-Malo, France, 90–104.Google Scholar
Frühwirth, T. 1998. Theory and practice of constraint handling rules. Journal of Logic Programming 37 (1–3) (October), 95–138.Google Scholar
Frühwirth, T. and Abdennadher, S. 2003. Essentials of Constraint Programming. Cognitive Technologies. Springer Verlag, New York (IX, 145p).CrossRefGoogle Scholar
Guo, H.-F. and Gupta, G. 2004. Simplifying dynamic programming via tabling. In Proc. 6th International Symposium on Practical Aspects of Declarative Languages, Hentenryck, P. V., Ed. Lecture Notes in Computer Science, vol. 3819. Springer Verlag, 163–177.CrossRefGoogle Scholar
Holzbaur, C. 1992. Metastructures vs. Attributed Variables in the Context of Extensible Unification. Tech. Rep. TR-92-23, Austrian Research Institute for Artificial Intelligence, Vienna, Austria.Google Scholar
Holzbaur, C. and Frühwirth, T. 2000. A prolog constraint handling rules compiler and runtime system. Special Issue Journal of Applied Artificial Intelligence on Constraint Handling Rules 14 (4) (April), 369–388.Google Scholar
Jaffar, J. and Lassez, J.-L. 1987. Constraint logic programming. In POPL '87: Proceedings of the 14th ACM SIGACT-SIGPLAN symposium on Principles of programming languages. ACM Press, New York, NY, USA, 111–119.Google Scholar
Jaffar, J. and Maher, M. J. 1994. Constraint logic programming: A survey. Journal of Logic Programming 19/20, 503–581.CrossRefGoogle Scholar
Kanellakis, P. C., Kuper, G. M., and Revesz, P. Z. 1995. Constraint query languages. In Selected papers of the 9th annual ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems. Academic Press, Inc., Orlando, FL, USA, 26–52.Google Scholar
Marriott, K. and Stuckey, P. J. 1998. Programming with Constraints: An Introduction. MIT Press. Cambridge, MA, USA.Google Scholar
Mukund, M., Ramakrishnan, C. R., Ramakrishnan, I. V., and Verma, R. 2000. Symbolic bisimulation using tabled constraint logic programming. In International Workshop on Tabulation in Parsing and Deduction. Vigo, Spain, 1–9.Google Scholar
Pemmasani, G., Ramakrishnan, C. R., and Ramakrishnan, I. V. 2002. Efficient model checking of real time systems using tabled logic programming and constraints. In International Conference on Logic Programming. Lecture Notes in Computer Science. Springer, Copenhagen, Denmark, 405–410.Google Scholar
Rao, P., Ramakrishnan, C. R., and Ramakrishnan, I. V. 1996. A thread in time saves tabling time. In Joint International Conference and Symposium on Logic Programming, Meher, M. J. (Ed.). September 2–6, 1996, Bonn, Germany. MIT Press, Cambridge, MA, USA, 112–126.Google Scholar
Saraswat, V. A. and Rinard, M. 1990. Concurrent constraint programming. In POPL'90: Proceedings of the 17th ACM SIGPLAN-SIGACT symposium on Principles of programming languages. ACM Press, New York, NY, USA, 232–245.CrossRefGoogle Scholar
Sarna-Starosta, B. and Ramakrishnan, C. R. 2003. Constraint-based model checking of data-independent systems. In 5th International Conference on Formal Engineering Methods, ICFEM 2003, Dong, J. S. and Woodcock, J., Eds. Lecture Notes in Computer Science, vol. 2885. Springer-Verlag, 579–598.Google Scholar
Sarna-Starosta, B. and Ramakrishnan, C. R. 2007. Compiling constraint handling rules for efficient tabled evaluation. In PADL'07: Ninth International Symposium on Practical Aspects of Declarative Languages, Hanus, M., Ed. Lecture Notes in Computer Science. Springer Verlag, 170–184.Google Scholar
Schrijvers, T. 2005. Analyses, Optimizations and Extensions of Constraint Handling Rules. Ph.D. thesis, Department of Computer Science, K.U.Leuven, Leuven, Belgium.Google Scholar
Schrijvers, T. and Demoen, B. 2004. The K.U.Leuven CHR system: Implementation and application. In First Workshop on Constraint Handling Rules: Selected Contributions, Frühwirth, T. and Meister, M., Eds. Ulm, Germany, 1–5.Google Scholar
Schrijvers, T., Demoen, B., Duck, G., Stuckey, P., and Frühwirth, T. 2006. Automatic implication checking for CHR constraints. In Electronic Notes in Theoretical Computer Science. vol. 147. 93–111.Google Scholar
Schrijvers, T. and Frühwirth, T. 2006. Optimal union-find in constraint handling rules. Theory and Practice of Logic Programming 6 (1&2), 213–224.Google Scholar
Schrijvers, T. and Warren, D. S. 2004. Constraint handling rules and tabled execution. In ICLP'04: Proceedings of the 20th International Conference on Logic Programming, Demoen, B. and Lifschitz, V., Eds. Lecture Notes in Computer Science, vol. 3132. Springer Verlag, St-Malo, France, 120–136.Google Scholar
Schrijvers, T., Warren, D. S., and Demoen, B. 2003. CHR for XSB. In CICLOPS 2003: Proceedings of the Colloquium on Implementation of Constraint and LOgic Programming Systems, Lopes, R. and Ferreira, M., Eds. University of Porto, Mumbai, India, 7–20.Google Scholar
Toman, D. 1996. Computing the well-founded semantics for constraint extensions of Datalog. In Proceedings of CP'96 Workshop on Constraint Databases. Number 1191 in Lecture Notes in Computer Science. Cambridge, MA, USA, 64–79.Google Scholar
Toman, D. 1997a. Constraint databases and program analysis using abstract interpretation. In Constraint Databases and Their Applications, Second International Workshop on Constraint Database Systems (CDB '97), Gaede, V., Brodsky, A., Günther, O., Srivastava, D., Vianu, V., and Wallace, M., Eds. Lecture Notes in Computer Science, vol. 1191. Springer Verlag, 246–262.Google Scholar
Toman, D. 1997b. Memoing evaluation for constraint extensions of datalog. Constraints: An International Journal, Special Issue on Constraints and Databases 2 (3/4) (December), 337–359.CrossRefGoogle Scholar
Warren, D. S. et al. 2005. The XSB Programmer's Manual: version 2.7, vols. 1 and 2. http://xsb.sf.net.Google Scholar
Wielemaker, J. 2004. SWI-Prolog release 5.4.0. http://www.swi-prolog.org/.Google Scholar
Wolper, P. 1986. Expressing interesting properties of programs in propositional temporal logic. In POPL '86: Proceedings of the 13th ACM SIGACT-SIGPLAN symposium on Principles of programming languages. ACM Press, New York, NY, USA, 184–193.CrossRefGoogle Scholar